Opened 10 years ago

Closed 9 years ago

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

Reported by: Owned by: jason jason, ncohen, rlm major sage-5.0 graph theory beginner sd35.5 sage-5.0.beta0 Nathan Carter Karl-Dieter Crisman N/A

```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:

or here:

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.

### comment:1 Changed 10 years ago by jason

• Description modified (diff)

### comment:2 Changed 10 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 10 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 10 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 9 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:7 Changed 9 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.

### comment:8 Changed 9 years ago by ncarter

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

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

• Status changed from needs_work to needs_review

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

### comment:12 Changed 9 years ago by ncarter

• Status changed from needs_review to needs_work

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

### comment:13 Changed 9 years ago by ncarter

• Status changed from needs_work to needs_review

OK give that a try.

### comment:14 Changed 9 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 9 years ago by kcrisman

• Description modified (diff)

### comment:16 Changed 9 years ago by jdemeyer

• Milestone changed from sage-4.8 to sage-5.0

### comment:17 Changed 9 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.