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 rbeezer)

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. trac_12243-graph-girth-vertices.patch

Attachments (1)

trac_12243-graph-girth-vertices.patch (1.7 KB) - added by rbeezer 9 years ago.

Download all attachments as: .zip

Change History (13)

Changed 9 years ago by rbeezer

comment:1 Changed 9 years ago by rbeezer

  • Authors set to Rob Beezer
  • Description modified (diff)
  • Status changed from new to needs_review

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. ;-)

comment:2 follow-up: Changed 9 years ago by ncohen

  • 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: Changed 9 years ago by rbeezer

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: Changed 9 years ago by 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

Nathann

comment:5 in reply to: ↑ 4 ; follow-up: Changed 9 years ago by dimpase

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: Changed 9 years ago 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

comment:7 in reply to: ↑ 6 Changed 9 years ago by dimpase

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: Changed 9 years ago by 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.

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 dimpase

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 jdemeyer

  • Milestone changed from sage-4.8 to sage-5.0

comment:11 in reply to: ↑ 6 Changed 9 years ago by brunellus

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 jdemeyer

  • Merged in set to sage-5.0.beta0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.