#12243: Girth of a graph fails for non-integer vertices
-----------------------------+----------------------------------------------
Reporter: rbeezer | Owner: jason, ncohen, rlm
Type: defect | Status: positive_review
Priority: minor | Milestone: sage-4.8
Component: graph theory | Keywords:
Work_issues: | Upstream: N/A
Reviewer: Nathann Cohen | Author: Rob Beezer
Merged: | Dependencies:
-----------------------------+----------------------------------------------
Comment(by ncohen):
> well, I discussed at the Sage Days in Seattle in Jan 2011 one possible
speedup, namely, for graphs with known automorphisms these kinds of
computations can be done orbit-wise. But nothing has been done in this
direction...
Hmmm... `:-/`
Well, I thought about this too while thinking about this specific problem
: to obtain the girth of a vertex-transitive graph one BFS is actually
sufficient instead of n, but well... Computing the automorphism group to
improve girth computations seems a bit expensive though.
But I guess it all boils down to a much more fundamental issue : I guess
that people working on symmetric graphs do not spend much time changing
the graph structure, do they ? It's not my field so I have no idea, but I
guess that in your case it would make much more sense to work on immutable
graphs which, as you say, can be enriched with a lot more information than
just the adjacencies.. On such graphs it would make sense to cache
informations like the automorphism group `O_o`
I am actually writing some C-level graph backend for efficient
computations without wasting time with calls to Python methods... For my
applications having immutable graphs sounded like a bad idea (because we
would have to maintain the properties over changes like edge
addition/removal in the graph...The BipartiteGraph class actually show how
impractical that is) but if you do not change the structure often that's a
totally different problem.
By the way, what do you do with graphs ? What I actually need is a survey
of what people use these methods for, otherwise I can do nothing but
develop it exclusively for my own needs `:-D`
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12243#comment:6>
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.
