normalized laplacian throws an error if the graph has an isolated vertex

[jason]

sage: g=Graph({0:[],1:[2]})
sage: g.laplacian_matrix(normalized=True)
---------------------------------------------------------------------------
ZeroDivisionError                         Traceback (most recent call last)

/Users/grout/sage-trees/sage-4.6.1/devel/sage-main/sage/misc/<ipython console> in <module>()

/Users/grout/sage/local/lib/python2.6/site-packages/sage/graphs/generic_graph.pyc in kirchhoff_matrix(self, weighted, indegree, normalized, **kwds)
    938 
    939         if normalized:
--> 940             Dsqrt = diagonal_matrix([1/sqrt(D[i,i]) for i in range(D.nrows())])
    941             return Dsqrt*(D-M)*Dsqrt
    942         else:

/Users/grout/sage/local/lib/python2.6/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__div__ (sage/structure/element.c:11950)()

/Users/grout/sage/local/lib/python2.6/site-packages/sage/structure/coerce.so in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:6152)()

/Users/grout/sage/local/lib/python2.6/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__div__ (sage/structure/element.c:11931)()

/Users/grout/sage/local/lib/python2.6/site-packages/sage/rings/integer.so in sage.rings.integer.Integer._div_ (sage/rings/integer.c:11648)()

/Users/grout/sage/local/lib/python2.6/site-packages/sage/rings/integer_ring.so in sage.rings.integer_ring.IntegerRing_class._div (sage/rings/integer_ring.c:5069)()

ZeroDivisionError: Rational division by zero

See the definition of normalized laplacian here:

 http://mathworld.wolfram.com/LaplacianMatrix.html

or here:

 http://en.wikipedia.org/wiki/Laplacian_matrix

Basically, this function ignores the part of the definition that says that an isolated vertex should have an all-zero row and column.

Also, coding things up straight from the definition might make the function faster anyway (rather than multiplying matrices). If we do need to multiply matrices, I think it would be sufficient to make $D^{{1/2}$ have a 1 if the corresponding row represented an isolated vertex.}

---

Apply trac-10757-laplacian-div-by-0-with-doctest.patch .

[jason]

In fact, I think an easy way to fix this (though maybe not the most efficient) is to just change {{1/sqrt(D[i,i])}} in the problematic line to {{1/sqrt(D[i,i]) if D[i,i]>0 else 1}}

[jason]

In fact, I think an easy way to fix this (though maybe not the most efficient) is to just change 1/sqrt(D[i,i]) in the problematic line to 1/sqrt(D[i,i]) if D[i,i]>0 else 1

[jason]

The docs would also need to be changed to mention what happens if we have an isolated vertex.

[ncarter]

The above patch implements the suggested fix, and the corresponding documentation changes. Testing indicates that the original poster's bug goes away when this patch is applied.

[jason]

The documentation is slightly unclear about what matrix is "the matrix" in the exceptional case. I just mentioned this to Nathan and he's updating the docs.

[ncarter]

Previous attachment update just tweaked documentation as per Jason Grout's suggestion.

[jason]

The code looks good to me. If someone downloads it and verifies that it works, then positive review from me.

[kcrisman]

This needs a test for the original problem.

[ncarter]

Added doctest, as per Karl-Dieter's correction.

[ncarter]

Oh, fiddlesticks...that was a mistaken upload. Will fix in a moment...

[ncarter]

adding a doctest this time

[ncarter]

OK give that a try.

[kcrisman]

Looks good. Could have made it a "TEST" instead of putting it in examples, but clearly that's not important. Positive review.

[kcrisman]

Apply trac-10757-laplacian-div-by-0-with-doctest.patch .