Opened 9 years ago

Closed 8 years ago

#10757 closed defect (fixed)

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

Reported by: jason Owned by: jason, ncohen, rlm
Priority: major Milestone: sage-5.0
Component: graph theory Keywords: beginner sd35.5
Cc: Merged in: sage-5.0.beta0
Authors: Nathan Carter Reviewers: Karl-Dieter Crisman
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by kcrisman)

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.

Attachments (2)

trac-10757-laplacian-div-by-0.patch (1.4 KB) - added by ncarter 8 years ago.
trac-10757-laplacian-div-by-0-with-doctest.patch (1.9 KB) - added by ncarter 8 years ago.
adding a doctest this time

Download all attachments as: .zip

Change History (19)

comment:1 Changed 9 years ago by jason

  • Description modified (diff)

comment:2 Changed 9 years ago by 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}}

comment:3 Changed 9 years ago by 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

comment:4 Changed 9 years ago by jason

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

comment:5 Changed 8 years ago by ncarter

  • Status changed from new to needs_review

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.

comment:6 Changed 8 years ago by ncarter

  • Keywords sd35.5 added

comment:7 Changed 8 years ago by 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.

Changed 8 years ago by ncarter

comment:8 Changed 8 years ago by ncarter

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

comment:9 Changed 8 years ago by jason

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

comment:10 Changed 8 years ago by kcrisman

  • Authors set to Nathan Carter
  • Reviewers set to Karl-Dieter Crisman
  • Status changed from needs_review to needs_work

This needs a test for the original problem.

comment:11 Changed 8 years ago by ncarter

  • Status changed from needs_work to needs_review

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

comment:12 Changed 8 years ago by ncarter

  • Status changed from needs_review to needs_work

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

Changed 8 years ago by ncarter

adding a doctest this time

comment:13 Changed 8 years ago by ncarter

  • Status changed from needs_work to needs_review

OK give that a try.

comment:14 Changed 8 years ago by kcrisman

  • Status changed from needs_review to positive_review

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

comment:15 Changed 8 years ago by kcrisman

  • Description modified (diff)

comment:16 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-4.8 to sage-5.0

comment:17 Changed 8 years ago by jdemeyer

  • Merged in set to sage-5.0.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.