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 )
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. }
Attachments (2)
Change History (19)
comment:1 Changed 9 years ago by
- Description modified (diff)
comment:2 Changed 9 years ago by
comment:3 Changed 9 years ago by
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
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
- 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
- Keywords sd35.5 added
comment:7 Changed 8 years ago by
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
comment:8 Changed 8 years ago by
Previous attachment update just tweaked documentation as per Jason Grout's suggestion.
comment:9 Changed 8 years ago by
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
- 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
- Status changed from needs_work to needs_review
Added doctest, as per Karl-Dieter's correction.
comment:12 Changed 8 years ago by
- Status changed from needs_review to needs_work
Oh, fiddlesticks...that was a mistaken upload. Will fix in a moment...
comment:13 Changed 8 years ago by
- Status changed from needs_work to needs_review
OK give that a try.
comment:14 Changed 8 years ago by
- 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
- Description modified (diff)
comment:16 Changed 8 years ago by
- Milestone changed from sage-4.8 to sage-5.0
comment:17 Changed 8 years ago by
- Merged in set to sage-5.0.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
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}}