Opened 9 years ago
Closed 9 years ago
#12243 closed defect (fixed)
Girth of a graph fails for non-integer vertices
Reported by: | rbeezer | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.0 |
Component: | graph theory | Keywords: | |
Cc: | ncohen | Merged in: | sage-5.0.beta0 |
Authors: | Rob Beezer | Reviewers: | Nathann Cohen |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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:
Attachments (1)
Change History (13)
Changed 9 years ago by
comment:1 Changed 9 years ago by
- Description modified (diff)
- Status changed from new to needs_review
comment:2 follow-up: ↓ 3 Changed 9 years ago by
- Reviewers set to Nathann Cohen
- Status changed from needs_review to positive_review
Hellooooo !!
Well, this patch does the trick for this implementation and fixed the bug, hence it's good to go !
On the other hand, this kind of things will really need to be rewritten decently in Cython... To give an idea, the work done by this Python function is more or less (actually, less) than the work done by the "diameter" function, which has been rewritten not so long ago.
sage: g = graphs.OddGraph(7) sage: %timeit g.diameter() 5 loops, best of 3: 155 ms per loop
Well, thank you very much for this bugfix though :-)
Nathann
comment:3 in reply to: ↑ 2 ; follow-up: ↓ 4 Changed 9 years ago by
Replying to ncohen:
Thanks for the review and the advice along the way.
On the other hand, this kind of things will really need to be rewritten decently in Cython...
I agree. But (maybe) better to be slow and correct than fast and wrong. ;-) I'll look forward to the Cythonization.
Rob
comment:4 in reply to: ↑ 3 ; follow-ups: ↓ 5 ↓ 8 Changed 9 years ago by
I agree. But (maybe) better to be slow and correct than fast and wrong. ;-) I'll look forward to the Cythonization.
Of course of course, not to mention that we usually keep the duplicate implementations to check each other, and also just in case one appears to be bugged later !
Do you use the girth function much ? I'm randomly finding out that people around use Graph functions I wouldn't expect them to, and it's a pity otherwise I would know which kind of things should be reimplemented more efficiently first !
I wish people would complain more about speed problems in the graph library :-p
Nathann
comment:5 in reply to: ↑ 4 ; follow-up: ↓ 6 Changed 9 years ago by
Replying to ncohen:
I agree. But (maybe) better to be slow and correct than fast and wrong. ;-) I'll look forward to the Cythonization.
Of course of course, not to mention that we usually keep the duplicate implementations to check each other, and also just in case one appears to be bugged later !
Do you use the girth function much ? I'm randomly finding out that people around use Graph functions I wouldn't expect them to, and it's a pity otherwise I would know which kind of things should be reimplemented more efficiently first !
I wish people would complain more about speed problems in the graph library
:-p
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...
Dima
comment:6 in reply to: ↑ 5 ; follow-ups: ↓ 7 ↓ 11 Changed 9 years ago by
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
comment:7 in reply to: ↑ 6 Changed 9 years ago by
Replying to 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
comment:8 in reply to: ↑ 4 ; follow-up: ↓ 9 Changed 9 years ago by
Replying to ncohen:
Do you use the girth function much ? I'm randomly finding out that people around use Graph functions I wouldn't expect them to, and it's a pity otherwise I would know which kind of things should be reimplemented more efficiently first !
I am teaching a course on algebraic graph theory here at AIMS in South Africa. So one of the topics is Moore graphs and cages, where girth is one of the characterizing properties. I'd like the students to be able to determine girth (by-hand) for things like the Odd Graph. Thus, having Sage to help with this is very useful.
You are right - I tend to take these highly symmetric graphs as-built and explore their properties, not so much manipulating them. Especially when teaching. So having them "read-only" would meet many of my purposes. And Dima's idea to carry more group-theoretic information is a good one, though it seems a big job to figure out how to do that "right" and then exploit it consistently.
Rob
comment:9 in reply to: ↑ 8 Changed 9 years ago by
Replying to rbeezer:
Replying to ncohen:
Do you use the girth function much ? I'm randomly finding out that people around use Graph functions I wouldn't expect them to, and it's a pity otherwise I would know which kind of things should be reimplemented more efficiently first !
I am teaching a course on algebraic graph theory here at AIMS in South Africa. So one of the topics is Moore graphs and cages, where girth is one of the characterizing properties. I'd like the students to be able to determine girth (by-hand) for things like the Odd Graph. Thus, having Sage to help with this is very useful.
one can rely on GAP's package GRAPE for this (ideally, it should even be possible to write a backend based on it). I showed a bit of this on #9136, constructing the Schlaefli graph.
Dima
You are right - I tend to take these highly symmetric graphs as-built and explore their properties, not so much manipulating them. Especially when teaching. So having them "read-only" would meet many of my purposes. And Dima's idea to carry more group-theoretic information is a good one, though it seems a big job to figure out how to do that "right" and then exploit it consistently.
One idea might be a GRAPE-based graph backend.
Rob
comment:10 Changed 9 years ago by
- Milestone changed from sage-4.8 to sage-5.0
comment:11 in reply to: ↑ 6 Changed 9 years ago by
Replying to ncohen:
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.
I thought about this for last few days too -- about immutable graphs that holds some information about itself. It is great that Sage focus on the speed of code execution, but when I use it, it is mostly interactive playing with relatively small graphs. In this case interface matters more than computational complexity. Immutable, functional way of work is quite handy. It something like Stefan was talking about in #7304.
Another thing is that as I agree that BipartiteGraph? class doesn't handle it's job, it is sometimes really nice to be sure that you work with a bipartite or a planar graph all the way. For example, the current Graph class loudly presents if it contains multiple edges or loops in its str -- this has nothing to do with a Python type system, like the BipartiteGraph? class does, but serves the same purpose.
So, if this would be up to me, I would create not just new backend, but new class ImmutableGraph?, that would beside standard functions offer something like fix_* and follow_* (for * in [planar, bipartite, chordal, ...]). Fixing some property would cause firing exceptions whenever the property is broken, following would just cause to keep the state updated and printed from str. Then, I guess, BipartiteGraph? could be made obsolete.
Well, I see that now I'm talking about something completely different than you. :-) And it is maybe stupid. I'll just think about it more in coming days.
comment:12 Changed 9 years ago by
- Merged in set to sage-5.0.beta0
- Resolution set to fixed
- Status changed from positive_review to closed
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):
Odd Graph,
O_7
, relabeled (n=1716):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. ;-)