#12243: Girth of a graph fails for non-integer vertices
----------------------------+-----------------------------------------------
Reporter: rbeezer | Owner: jason, ncohen, rlm
Type: defect | Status: needs_review
Priority: minor | Milestone: sage-4.8
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: | Author: Rob Beezer
Merged: | Dependencies:
----------------------------+-----------------------------------------------
Changes (by newvalueoldvalue):
* status: new => needs_review
* author: => Rob Beezer
Old description:
> The Odd graph, {{{O_3}}}, is the Petersen Graph, which has girth 5.
>
> {{{
> sage: P = graphs.PetersenGraph()
> sage: P.girth()
> 5
> sage: K = graphs.OddGraph(3)
> sage: K.is_isomorphic(P)
> True
> sage: K.girth()
> +Infinity
> }}}
>
> But the result implies there are no cycles in K.
>
> See sage-devel thread
>
> http://groups.google.com/group/sage-
> devel/browse_thread/thread/8dc807a3710e3dee
>
> for more discussion.
New description:
The Odd graph, {{{O_3}}}, is the Petersen Graph, which has girth 5.
{{{
sage: P = graphs.PetersenGraph()
sage: P.girth()
5
sage: K = graphs.OddGraph(3)
sage: K.is_isomorphic(P)
True
sage: K.girth()
+Infinity
}}}
But the result implies there are no cycles in K.
See sage-devel thread
http://groups.google.com/group/sage-
devel/browse_thread/thread/8dc807a3710e3dee
for more discussion.
'''Apply:'''
1. [attachment:trac_12243-graph-girth-vertices.patch]
--
Comment:
Turns out it was rather straightforward to collect vertices already
examined in the main loop as the keys of a dictionary ({{{seen}}}). Then
problematic comparison that assumed integer value vertices is just replace
by a check on the presence of the vertex as a key in the dictionary.
Some rudimentary timings on 4.8.alpha3
Heawood Graph (n=14):
Stock - 823 us; Patched - 839 us
Odd Graph, `O_7`, relabeled (n=1716):
Stock - 612 ms; Patched - 633 ms
So no real harm has been done for graphs with integer vertices.
However, with the patch, and without relabeling, `O_7` takes 2.44 s.
Pretty bad you might say. However, consider that it takes 9.5 s to
relabel the graph! (Which is the current work-around.) So not so bad
really. ;-)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12243#comment:1>
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.
