#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 dimpase):
Replying to [comment:6 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.
no, the point is that a group is already known (e.g. as it is for the Odd
graphs). Then to represent a graph one just needs to store the
representatives of
the orbits on the edges of the graph. This allows one to compute with
graphs one cannot even store in memory, if all the edges are stored! It's
matter of designing a reasonable backend that tackles this.
>
> 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`
A short answer is that I look for substructures satisfying certain
properties. E.g., maximum cliques, or some convex substructures...
Dima
>
> Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/12243#comment:7>
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.
