#10757: normalized laplacian throws an error if the graph has an isolated vertex
-----------------------------------+----------------------------------------
Reporter: jason | Owner: jason, ncohen, rlm
Type: defect | Status: positive_review
Priority: major | Milestone: sage-4.8
Component: graph theory | Keywords: beginner sd35.5
Work_issues: | Upstream: N/A
Reviewer: Karl-Dieter Crisman | Author: Nathan Carter
Merged: | Dependencies:
-----------------------------------+----------------------------------------
Old description:
> {{{
> 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.
New description:
{{{
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 [attachment:trac-10757-laplacian-div-by-0-with-doctest.patch].
--
Comment(by kcrisman):
Apply [attachment:trac-10757-laplacian-div-by-0-with-doctest.patch].
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/10757#comment:15>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
