bug in graph embedding?

[Nikos Apostolakis]

Hello group,

I'm looking at embeddings of complete gaphs and I think I've found a bug: I defined the complete graph k12 as a (sort of) Cayley graph of the group Z₂²× Z₃ as follows:

g12 = AbelianGroup(3, [2, 2, 3], names='ABC')
[A, B, C] = g12.gens()

k12 = Graph()
for x in g12:
for y in [A, B, A*B]:
if not (x*y, x) in k12.edges():
k12.add_edge((x, x*y))
for y in [C, A*C, B*C, A*B*C]:
k12.add_edge((x, x*y))

# The cyclic order around the vertices:
cy = [ C, A*C, C^-1, A*C^1, B*C, A*B*C, B*C^-1, A*B*C^-1, A, B, A*B ]

# The rotation dictionary
imb = {v : [ v*x for x in cy] for v in g12 }

k12.set_embedding(imb)
k12._check_embedding_validity()
# # ==>
# True
# # <==

So far so good. But then when I try to compute the genus (which should come out as 22) and the faces I get an error:

k12.genus(on_embedding=imb)

---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
in ()
----> 1 k12.genus(on_embedding=imb)

/Applications/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in genus(self, set_embedding, on_embedding, minimal, maximal, circular, ordered)
4046 if on_embedding: #i.e., if on_embedding True (returns False if on_embedding is of type dict)
4047 try:
-> 4048 faces = len(self.faces(self._embedding))
4049 except AttributeError:
4050 raise AttributeError('graph must have attribute _embedding set to compute current (embedded) genus')

/Applications/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in faces(self, embedding)
4183 while (len(edgeset) > 0):
4184 neighbors = embedding[path[-1][-1]]
-> 4185 next_node = neighbors[(neighbors.index(path[-1][-2])+1)%(len(neighbors))]
4186 tup = (path[-1][-1],next_node)
4187 if tup == path[0]:

ValueError: 1 is not in list

and then for faces:

k12.faces()

---------------------------------------------------------------------------
ValueError Traceback (most recent call last)
in ()
----> 1 k12.faces()

/Applications/sage/local/lib/python2.7/site-packages/sage/graphs/generic_graph.pyc in faces(self, embedding)
4183 while (len(edgeset) > 0):
4184 neighbors = embedding[path[-1][-1]]
-> 4185 next_node = neighbors[(neighbors.index(path[-1][-2])+1)%(len(neighbors))]
4186 tup = (path[-1][-1],next_node)
4187 if tup == path[0]:

ValueError: 1 is not in list

Is this a bug or am I doing something wrong?

Please, if it's not a touble, cc me in any answers. Thanks in advance.

Nikos

--

Οι ελαφροί ας με λέγουν ελαφρόν.
Στα σοβαρά πράγματα ήμουν πάντοτε
επιμελέστατος.

The frivolous can call me frivolous. In serious matters I've always been most diligent.
  K. P. Kavafy

[Nathann Cohen]

Hello,

I'm looking at embeddings of complete gaphs and I think I've found a bug: I defined the complete graph k12 as a (sort of) Cayley graph of the group Z₂²× Z₃ as follows:

First, it seems that the Python code you copy/pasted in your message lost its indentation. Thus, I have no way to make sure that the identation I used is the one that you used.

This being said, it seems that the problem comes from your dictionary 'imb': it should associated, to each vertex v of your graph, the list of its neighbors in some cyclic ordering. What Sage seems to say, however, is that while A*C appear in the list associated to 1, it is unable to find 1 in the list associated to A*C.

I will try to make the error message more helpful.

Nathann

[Nikos Apostolakis]

On Wednesday, January 21, 2015 at 8:11:23 AM UTC-5, Nathann Cohen wrote:

Hello,

I'm looking at embeddings of complete gaphs and I think I've found a bug: I defined the complete graph k12 as a (sort of) Cayley graph of the group Z₂²× Z₃ as follows:

First, it seems that the Python code you copy/pasted in your message lost its indentation. Thus, I have no way to make sure that the identation I used is the one that you used.

Sorry about that.  For what is worth here is the code with indentation:

k12 = Graph()
for x in g12:

....for y in [A, B, A*B]:
........if not (x*y, x) in k12.edges():
............k12.add_edge((x, x*y))
....for y in [C, A*C, B*C, A*B*C]:
........k12.add_edge((x, x*y))

the reset is all oneliners.

This being said, it seems that the problem comes from your dictionary 'imb': it should associated, to each vertex v of your graph, the list of its neighbors in some cyclic ordering. What Sage seems to say, however, is that while A*C appear in the list associated to 1, it is unable to find 1 in the list associated to A*C.

You're riight.  After looking carefully at my definition of cy (the cyclic order of the non zero group elements that give the cyclic order of the edges around each vertext) I noticed that instead of A*C^-1 I had AC^1. Once I corrected that everything works.

However shouldn't _check_embedding_validity detect that something was wrong with my dictionary? I did give

k12._check_embedding_validity()

and sage returned True.

Anyway sorry for my silly mistake and thanks a lot for your help.

Nikos

[Nathann Cohen]

Hello again!!!

> You're riight. After looking carefully at my definition of cy (the cyclic
> order of the non zero group elements that give the cyclic order of the edges
> around each vertext) I noticed that instead of A*C^-1 I had AC^1. Once I
> corrected that everything works.

Cool. Mystery solved.

> However shouldn't _check_embedding_validity detect that something was wrong
> with my dictionary? I did give
>
> k12._check_embedding_validity()
>
> and sage returned True.

This is totally right. For this reason, I created a new trac ticket
[1] which contains some new code for Sage: it will be able to catch
the bug you encountered, and will raise much more meaningful messages
than 'True/False' when something does not occur as expected. In your
case, the code would break at this moment:

sage: k12.set_embedding(imb)
...
ValueError: The list associated with vertex A contains >1 occurrences of: [C]

Now here is the deal: new code, when it is written, must be reviewed.
Consequently, it will not be merged into Sage before somebody comes,
reads it and checks that it all works, then sets the ticket to
positive_review. This is a lot of work and things to learn when you do
not know Sage's workflow, but on the other hand nobody can add
anything into Sage unless somebody volunteers to do that job. If you
were willing to give it a try it would definitely help get this patch
reviewed+merged quickly. Some documentation to start the
sage-development-adventure can be found there:
http://www.sagemath.org/doc/developer/

> Anyway sorry for my silly mistake and thanks a lot for your help.

Look at what happened: you found Sage misbehaving somewhere, asked a
question, and as a result Sage is being patched and will not make the
same mistake again. That's how free software works, and if nobody
reports the problems they just stay as they are.

Thanks for the report, and thanks for your help and time if you have
some to spare for Sage.

Good evening,

Nathann

[1] http://trac.sagemath.org/ticket/17656

[Nikos Apostolakis]

Hi Nathan,

thanks for fixing this.  For the next two weeks or so I expect to be very busy.  I can do some reading and try to figure out how the process works, but I'm not sure how much time I'll have to spare.  Realistically I may have some time in mid February.

Nikos

--
You received this message because you are subscribed to a topic in the Google Groups "sage-support" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-support/TsXzNtwuPvo/unsubscribe.
To unsubscribe from this group and all its topics, send an email to sage-support...@googlegroups.com.
To post to this group, send email to sage-s...@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.