Girth of Kneser graphs

[Rob Beezer]

The OddGraph (special case of a Kneser graph) has vertices that are
sets, but this seems to lead to the computation of the girth reporting
it has no cycles. The code for computing the girth looks like a
fairly straight-forward depth-first search. Does something about the
nature of the vertices have to change? They look hashable to me, so
it may not be that simple. Any ideas?

Rob

sage: P = graphs.PetersenGraph()
sage: P.girth()
5
sage: K = graphs.OddGraph(3)
sage: K.is_isomorphic(P)
True
sage: K.girth()
+Infinity
sage: H = copy(K)
sage: H.relabel()
sage: H.girth()
5
sage: type(K.vertices()[0])
<class 'sage.sets.set.Set_object_enumerated_with_category'>

[Nathann Cohen]

Helloooooooooo !!!

Well, I just looked at this piece of code and I guess the answer is clear. It contains a "if u<i: continue", where u and i are vertices.

By the way, I can not believe this thing is still written in Python ! O_o

Nathann

[Rob Beezer]

On Dec 31, 11:57 am, Nathann Cohen <nathann.co...@gmail.com> wrote:
> Well, I just looked at this piece of code and I guess the answer is clear.
> It contains a "if u<i: continue", where u and i are vertices.

OK, that explains it. I was looking for just this sort of thing when
I (quickly) scanned the code, but missed it.

Aside from totally rewriting the routine to be faster, would the
following make sense for a fix?

(a) Have i come from the complete list of vertices rather than the
vertex iterator.

(b) Compare the indices of i and u in the complete list.

Yes, it would be slower. But it might also be correct. ;-) I do not
see an efficient way to impose/exploit an arbitrary ordering on the
vertices, short of stuffing them all in a list.

Rob

[Nathann Cohen]

Helloooooooo !! 

> Aside from totally rewriting the routine to be faster, would the
> following make sense for a fix?
>
> (a) Have  i  come from the complete list of vertices rather than the
> vertex iterator.
>
> (b) Compare the indices of  i  and  u  in the complete list.
>
> Yes, it would be slower.  But it might also be correct.  ;-)  I do not
> see an efficient way to impose/exploit an arbitrary ordering on the
> vertices, short of stuffing them all in a list.

Well, yep I guess. The first loop iterates on all vertices, so for this one a

"for i_id, i in enumerate(self.vertex_iterator())" would be in order. And to obtain the id corresponding to v, I guess the best is to build a dictionnary associating each vertex to its index at the beginning of the algorithm.

If you need it to be fixed quickly, that's probably the best option ! But it hurts the eyes, because all the Graph methods spend a lot of time converting the ID to the Sage labels already, which is crazy if we try to convert them back as soon as we get them :-D

Nathann

[Rob Beezer]

On Dec 31, 12:21 pm, Nathann Cohen <nathann.co...@gmail.com> wrote:
> Well, yep I guess. The first loop iterates on all vertices, so for this one
> a
>
> "for i_id, i in enumerate(self.vertex_iterator())" would be in order. And
> to obtain the id corresponding to v, I guess the best is to build a
> dictionnary associating each vertex to its index at the beginning of the
> algorithm.

OK, thanks for the advice. I'll put a link here if I get around to
writing a patch.

> If you need it to be fixed quickly, that's probably the best option ! But
> it hurts the eyes, because all the Graph methods spend a lot of time
> converting the ID to the Sage labels already, which is crazy if we try to
> convert them back as soon as we get them :-D

Well, I "need" it for Tuesday. ;-) But not desperately. Would the
backends for graphs easily/efficiently support something like
G.index(u) to get the integer behind a vertex u quickly and
easily? It seems this would be useful for all the places where the
code assumes vertices are integers (or at least ordered).

Thanks,
Rob

[Nathann Cohen]

> > "for i_id, i in enumerate(self.vertex_iterator())" would be in order. And
> > to obtain the id corresponding to v, I guess the best is to build a
> > dictionnary associating each vertex to its index at the beginning of the
> > algorithm.

Oh, sorry ! Beware when you write the reverse dictionary, for the
order of the vertices in vertex_iterator may not be the same as the
one returned by vertices() !!!

> Well, I "need" it for Tuesday.  ;-)  But not desperately.  Would the
> backends for graphs easily/efficiently support something like
> G.index(u)  to get the integer behind a vertex  u  quickly and
> easily?  It seems this would be useful for all the places where the
> code assumes vertices are integers (or at least ordered).

Well, they already do this at Cython level, but I guess they do it the
same way --> with a reverse dictionary. Recently I have spent some
time over the Graph backend and I guess I will have several patches to
write there... Especially because we now have iterators in Cython :-)

Nathann

[Rob Beezer]

On Dec 31 2011, 12:41 pm, Rob Beezer <goo...@beezer.cotse.net> wrote:
>  I'll put a link here if I get around to writing a patch.

http://trac.sagemath.org/sage_trac/ticket/12243