Additional tests for graph symmetries

[azi]

The following ticket aims at enhancing the is_vertex_transitive method and introducing new symmetry tests for graphs namely if a graph is edge-transitive, arc-transitive, half-transitive and semi-symmetric.

I am still struggling to digest all sage development conventions so it might well be that the code is not yet in the proper format. I apologize for the inconvenience and hope someone can correct this.

Following are some comments related to the patch.

• is_vertex_transitive. This function has been changed so that it uses GAP to test transitivity. In addition a quick check for regularity has been added. The change was tested using the following function

  def f(n):
      for i in xrange(1,n+1):
          c = 0 
          for el in graphs.nauty_geng(str(n)):
              if el.is_vertex_transitive():
                  c+=1
          print i,c
  

and the results are

%timeit f(10) 5 loops, best of 3: 567 s per loop

for the old function and

%timeit f(10) 5 loops, best of 3: 222 s per loop

for the improvement.

• is_edge_transitive. This new function tests if a graph is edge-transitive. The main idea of the this test was suggested by Tom Boothby, see this sage-devel  post.

• is_arc_transitive. Similar to the edge-transitive case. I believe there is a more efficient way to test for arc-transitivity but for now I suppose this one is good enough.

• is_half_transitive. This function tests if a graph is vertex and edge-transitive but not arc-transitive. As a speedup it uses the fact that a half-transitive graph is Eulerian (see Lemma 3.2.2 in the book Algebraic graph theory by Godsil and Royle.)

• is_semi_symmetric. Tests if a graph is regular, edge-transitive but not vertex-transitive. Again we use the fact that such graphs are always bipartite (Lemma 3.2.1 in Godsil & Royle) to speed up the test.

Apply :

• trac_13721_graph_symmetries.5.patch
• trac_13721-rev.2.patch

[boothby]

I haven't tested this, but I've got a couple of comments so far.

1. Edges of graphs can be labeled. The graph Graph([(0,1,0),(0,1,1)]) will be counted as edge-transitive by this implementation, which is wrong. I recognize the irony of this: the slapdash code I posted to sage-devel has the same issue. My recommendation is to add a parameter edge_labels=True because that's the default 'round these parts. You'll get errors if unhashable edge labels are used, but that is also true of line_graph so I think this is acceptable.

2. I'd drop the is_symmetric alias. That's partially motivated by my dislike for the term (full disclosure). But it's mostly because the Graph class already has so many methods, we shouldn't frivolously add aliases.

3. It would be really nice if is_arc_transitive took an extra parameter so you could check if a graph is (for example) 2-arc transitive.

[azi]

Hello!

1 . Is there any other way to solve 1. It seems like a serious limitation not to allow line graphs by default. Perhaps a careful relabelling of the graph?

2. I kind of a agree. I thought it might be useful since this patch already defines the notion of semi-symmetric graphs.

3. I agree I had that one in mind after this patch is pushed forward since I haven't worked with k-arc-transitive graphs yet and don't feel comfortable in writing a patch for it.

[boothby]

1. There's been a misunderstanding here. My point is that

sage: G = Graph([(0,1,[])])
sage: G.line_graph()

results in an error because lists are not hashable (and vertices of graphs must be hashable). And so, I think that it's reasonable for the same graph to fail in other places because of the same reason. Also, this should be documented.

2. I'd like somebody else's opinion here. I love the amount of stuff we can do with graphs... but I hate the length of the list. ;)

3. Okay, yeah, I shouldn't be asking for new features.

[azi]

1. If I understand correctly, modifying the code to make use of edge labels would break in the following scenario

sage: G = graphs.PetersenGraph()
sage: L = G.line_graph()
sage: L.is_arc_transitive()

If so, then I believe this is a serious limitation that needs to be solved. I can see many real life scenarios in which one needs to these types of things on line graphs.

2. I agree! I am for both options depending on what others think.

[ncohen]

Hellooooooo Jernej !

First, thank you ver much for these patches ! I love to have fun with the graphs' automorphism groups these days -- though I really am a beginner -- and it is nice to see Sage improve on that side :-)

I have many questions, though :

• Why do you insist on returnin the group ? It feels like it is a very complicated object that shouldn't be built unless necessary :-) I do agree that the current implementation seems QUITE wasteful when just checking that a graph is indeed vertex_transitive. But I do not really get what the four lines after new_partition = ... actually do. Isn't it totally equivalent to check that the two partitions are equal up to reordering ? Something like that should do the trick, as (if I make no mistake) the partition can only be more refined than the one given as an input) : sorted(map(len,partition)) == sorted(map(len,new_partition)) And I expect that this plugged with the current code, should be faster than calling GAP :-)
• You write is_edge_transitive by copying the graph twice. Wouldn't it work to just build the automorphism group, and then ask GAP to give you the order or the Orbit of *only one edge* with the permutation group acts on it ? I think that this can be done (and probably faster), but I am a beginner with GAP so perhaps you are right.
• Not sure if this can also be done on is_arc_transitive, because we are not talking of sets anymore, but of ordered pairs.
• return self.is_edge_transitive() and self.is_vertex_transitive() and not self.is_arc_transitive() this line makes Sage compute the automorphism group 3 times, but I have no idea how bad it is. Perhaps not worth the trouble.
• is_symmetric I share Tom's advice on aliases ^^;. His wording is actually very nice : "I love the amount of stuff we can do with graphs... but I hate the length of the list." :-P
• There are some problems with the documentation and doctests : the way it is written (the "::" are not placed where they should) many doctests do not appear correctly on the HTML documentation.
• The way it is written, the function is_edge_transitive is a member of DiGraph? objects. When in doubt, the behaviour of the method should be made clear in the documentation. Or else we can move it to Graph.py :-)

Nathann

[azi]

Hello ncooohen!!1

Thank you for the review. Let me answer the points as posted by you.

1. I am not sure if this can be done without computing the automorphism of the group. Note however that the resulting group is represented with generators and is probably not that expensive. I have no clue what the partition thing is meant to do (most likely something related to the previous version of the code that computed orbits). What exactly do you mean by refined partition? I don't understand this part.

2. I agree. Though I am not sure how to get the orbit for an action that acts on edges (not on vertices.) I am not sure this is possible. Can someone verify this?

3. That is a good point! This could be solved by having an optional argument that supplies the automorphism group to the named functions!

4. Hahaha agree about the wording - I am waiting for the right time to tell it to someone IRL :-)

5.

6. This should most likely be moved to Graph.py

[ncohen]

Helloooooooooo !!

1. I am not sure if this can be done without computing the automorphism of the group.

Well, I guess that it cannot, but it can be done without dealing manually in Sage with an automorphism group that is internally built by the automorphism_group function (possibly Nauty), even when return_group is set to False. From what I understand of the algorithm, the partition that is returned consists in the orbits of the graphs's vertices. Hence in our case, the graph is transitive if and only if the partition returned has only one element in it (--> the whole vertex set). When the partition given as an input is *NOT* this trivial partition, the algorithm considers that vertices from differents sets of the partition are of a different "kind" (or color, or type, or whatever) and returns the orbits of the graphs respecting the vertices' kind/color/type/whatever. The small patch I attach replaces a nasty loop by a unique line, and your example of code returns the same answers for the values I was able to compute, and all tests pass on all files of the graph/ folder :-)

What exactly do you mean by refined partition ?

By "refined", I mean that each set of the new partition is a subset of one set of the former partition.

2. I agree. Though I am not sure how to get the orbit for an action that acts on edges (not on vertices.) I am not sure this is possible. Can someone verify this?

Well. I am no GAP expert but I used to use it with a guy who knew much better what he did with it, and I can still understand the code's meaning. What I have is the following : if G is a GAP Group acting on a set (of vertices), then you can compute the orbit of a pair of edges like that :

gap('Orbit(G,[1,6],OnSets)') 

And it looks like there is another keyword for ordered sets : OnTuples?. There is even one made especially for pairs : OnPairs?. So I guess that gap('Orbit(G,my_edge,OnSets?)') would do the trick for edge-transitivity, and gap('Orbit(G,my_edge,OnPairs?)') for arc-transitivity :-)

3. That is a good point! This could be solved by having an optional argument that supplies the automorphism group to the named functions!

4. Hahaha agree about the wording - I am waiting for the right time to tell it to someone IRL :-)

5.

6. This should most likely be moved to Graph.py

+1

Nathann

[ncohen]

Argggggggg.... Nasty TRAC. There is no "question mark". They keywords are OnSets?, OnTuples? and OnPairs?.

Nathann

[ncohen]

>_<

Another try : OnSets,OnTuples and OnPairs.

[boothby]

Okay, I just realized something stupid... I think I'll go with the excuse that I had a fever for why I didn't notice this sooner. If there are two different edge labels, then G is not edge transitive. Otherwise, we can safely ignore the labels.

Edit: this is all wrong. TIL: a fever is not as stupid-making as a lack of coffee.

[azi]

I still wasn't able to take the time to implement the changes! Hopefully next week I'll find the required time :-)

In the meantime I was wondering if this OnSets?,OnTuples? thing is supported directly under the PermuationGroup? class. I couldn't find it, but it would be nice to have it there and not rely on GAP directly. This would allow to abstract GAP out of graph theory and allow for transparent implementation of transitivity tests (in case it is changed from GAP to something else in the future).

If this is not yet supported, then is someone willing to ask the group theory guys if they are willing to add this feature in the future :-))))?

[ncohen]

HMmmmmmmm.... >_<

Well, I am having a very hard time getting (#13102) inside of Sage (6 months old), but if you send messages on sage-devel perhaps other guys will notice .. ^^;

Nathann

[ncohen]

This being said, you do not really want to get the output of Orbit with OnSets or OnTuple inside of Sage : it takes some time to build this Sage version of the output, and you just want to obtain the cardinality of it :-)

Nathann

[azi]

Hello!

Nathan, I have now modified the patch to use your suggestion. That is, the code now directly uses gap OrbitLength? on sets/tuples to decide if a graph is edge/arc-transitive.

Comments and suggestions are appreciated!

[ncohen]

Helloooooooooo Jernej ! I loooooooooooooove this patch, thank you so much for working on it ! :-D

Several comments :

• You make useless copies of the graph. The purpose of these two lines

  G = self.relabel(T,inplace=False) 
  e = list(G.edges(labels=False)[0])
  

  is just to get ONE edge of the graph with 0...n-1 coordinates !! To do this, you copy the whole graph with the first line, get the list of ALL EDGES in the second line, and ignore them all to only get the first of them. What's the point ? You can get the same result with this :

  e = self.edge_iterator(labels = False).next()
  e = T[e[0]], T[e[1]]
  

• You can replace

  if not self.is_eulerian(): 
     return False  
  return self.is_edge_transitive() and self.is_vertex_transitive() and not self.is_arc_transitive()
  

  by

  return self.is_eulerian() and self.is_edge_transitive() and self.is_vertex_transitive() and not self.is_arc_transitive()
  

  Or rather (to make it easier to read) :

  return (self.is_eulerian() and 
          self.is_edge_transitive() and
          self.is_vertex_transitive() and
          not self.is_arc_transitive())
  

  (and the same goes for is_semi_symmetric).
• The documentation of is_half_transitive and is_semi_symmetric appears to be wrong. When you have a :: somewhere, what should follow is an indented block of Sage code. And the result should appear nicely in the output of sage -docbuild reference html (that's the point of these :: commands).
• Your functions are added to the file generic_graph.py which means that they will also be methods of DiGraphs objects. Could you add to the docstring of is_edge_transitive and is_arc_transitive an explanation of their meaning when self is a DiGraph? ? The expected meaning of is_edge_transitive for DiGraphs? is actually the one obtained by is_arc_transitive. Or do you think that is_edge_transitive should only be a method of Graph ?

Thank you again for this patch ! I'll be glad to see it in Sage :-)

Nathann

[azi]

Hello Mr. Cohen!!!1

Thanks for the review! I have implemented the suggested changes (whoops for the relabel thing :) ) except the one of "merging" is_eulerian() with the other conditions for is_semi_symmetric (and other analogues of this.)

The reason being that by definition a graph is semi-symmetric if it is edge/vertex-transitive and not arc-transitive. And this is one logical condition. The other (being an Eulerian graph) is just an optimization since a semi-symmetric graph is always Eulerian and is somehow a different logical unit than the direct definition of a semi-symmetric graph. So I much rather like it to be separate for clarity sake and in case some other guys will add additional optimizations like that in the near future.

Let me know if you still think its better to mix all conditions together!

PS. I believe I have now fixed the documentation but I was not able to test it (doing things on a remote shell and its a mess to copy the files up and down). Hopefully its fine now.

[ncohen]

Patch rebased on 5.6.beta2 (which includes #8952)

[ncohen]

I wrote a patch (trac_13721-rev.patch ) that changes the following :

• The links toward the methods were broken (they point toward GenericGraph while the methods are now in Graph)
• def is_edge_transitive was not properly indented.
• adds documentation to all methods
• fixes Sphinx problems

And I just noticed that after all that the patch does not work....

sage: graphs.PetersenGraph().is_edge_transitive()
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/home/ncohen/.Sage/devel/sage-2/sage/graphs/<ipython console> in <module>()

/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/graphs/graph.pyc in is_edge_transitive(self)
   2426         e = T[e[0]], T[e[1]]
   2427 
-> 2428         return gap("OrbitLength("+str(A._gap_())+"," + str(e) + ",OnSets);") == self.size()
   2429 
   2430     def is_arc_transitive(self):

/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/interfaces/interface.pyc in __call__(self, x, name)
    193             
    194         if isinstance(x, basestring):
--> 195             return cls(self, x, name=name)
    196         try:
    197             return self._coerce_from_special_method(x)

/home/ncohen/.Sage/local/lib/python2.7/site-packages/sage/interfaces/expect.pyc in __init__(self, parent, value, is_name, name)
   1306             except (TypeError, KeyboardInterrupt, RuntimeError, ValueError), x:
   1307                 self._session_number = -1
-> 1308                 raise TypeError, x
   1309         self._session_number = parent._session_number
   1310 

TypeError: Gap terminated unexpectedly while reading in a large line:
Gap produced error output
Error, OnSets: <set> must be a set (not a permutation (small))

   executing Read("/home/ncohen/.sage/temp/grotte/13489/interface/tmp13502");

And obvously the file graph.py does not pass all tests as it should :

~/sage/graphs$ sage -t graph.py
sage -t  "devel/sage-2/sage/graphs/graph.py"                
...
4 items had failures:
   4 of  11 in __main__.example_15
   2 of   7 in __main__.example_16
   1 of   7 in __main__.example_17
   2 of   9 in __main__.example_18
***Test Failed*** 9 failures.
For whitespace errors, see the file /home/ncohen/.sage/tmp/graph_13567.py
	 [20.2 s]
 
----------------------------------------------------------------------
The following tests failed:


	sage -t  "devel/sage-2/sage/graphs/graph.py"
Total time for all tests: 20.2 seconds

Nathann

[azi]

hm... Sorry Nathan for causing you some extra work with this mess! I have no clue how come it worked before swiftly...

Anyhow I have integrated your changes and fixed the gap issue

azi@bodysnatcher:~$ sage -t ./sage-5.4.rc2/devel/sage-gsym/sage/graphs/graph.py 
sage -t  "devel/sage-gsym/sage/graphs/graph.py"             
         [14.3 s]
 
----------------------------------------------------------------------
All tests passed!
Total time for all tests: 14.3 seconds

[ncohen]

Apply trac_13721_graph_symmetries.2.patch

[ncohen]

Helloooooooo again !

Well, the patch still does not apply on Sage even if that is no big deal (the last version is 5.6.beta1 and not 5.4, see [1]), but I have another question : why do you prefer to use {{{ new_partition, T = self.automorphism_group(partition,translation=True) new_partition.is_transitive(domain=[T[x] for x in cell]) }}} rather than

new_partition, T = self.automorphism_group(partition,return_group=False,translation=True)
len(partition)=len(new_partition)

As I understand it, new_partition is necessarily more refined than partition, and they have the same length if and only if the group of automorphisms of G which respect partition has as orbits the list partition, which is exactly what we want O_o

By the way, as it is the variable that you name new_partition is not a partition, but a Group.

Nathann

Nathann

[1]  https://groups.google.com/forum/?fromgroups#!forum/sage-release

[azi]

Nathann!

I honestly tried to recall what I was thinking there but I cannot remember. I suggest we leave the vertex-transitive code as is, other than checking if the graph is not regular! Also, would it be wise to put the vertex_transitive part into the graph.py file or does it work as expected on digraphs as well?

[ncohen]

Hellooooooooooooooooo !

We can do as you say, but in that case I will create a ticket afterward to fix only that part, for I believe I should be simplified :-)

As for DiGraph? objects, we can indeed use is_vertex_transitive on them (and it makes sense !)

sage: d = DiGraph()
sage: d.add_edge(0,1)
sage: d.is_vertex_transitive()
False
sage: d.add_edge(1,0)         
sage: d.is_vertex_transitive()
True

Nathann

[azi]

Hello Nathann!

Could you check if this patch makes sense to you? After that we can create a new ticket specifically for the vertex-transitive thing.

[ncohen]

Well, the patch that you just uploaded still contains the following line O_o

if new_partition.is_transitive(domain=[T[x] for x in cell]) == False:

Nathann

[azi]

FML. I am so bad with this revision system thing (somehow it produced the wrong patch)

I have now removed the vertex-transitive thing out completely. Let us ship just the additional symmetries test here and consider the VT case separately.

Thank you for you patience Nathann

[ncohen]

Hellooooooooooooo !! Well, now it's my turn to try your patience ^^;

I'm sorry that I did not notice it earlier, but there's something I do not like inside the is_eulerian function. It does not just test that all degrees are even, but also that the graph is connected. Because if your graph is the union of two cycles, "then there is no tour that visits all edges" :-/

So I guess that you will have to replace your call to is_eulerian by : all(d%2 == 0 for d in self.degree())

Nathann

[azi]

Hello!!!

The latest patch should reflect your remark now!

Best,

Jernej

[ncohen]

Helloooooooooo !!

Well, as far as I know this patch now does its job perfectly, so it's good to go (except for this small useless patch that fixes a Sphinx warning, nothing to worry about).

Thank you for this patch, and sorry for this last delay ! Now what do we do about thix small fix in the is_vertex_transitive method ? Do you create it, or do you prefer me to do it instead ? That's totally up to you !

Nathann

[ncohen]

Apply trac_13721_graph_symmetries.5.patch, trac_13721-rev.2.patch

Nathann

[azi]

Hello!

Thanks go to you for your patience and suggestions! Also sorry for the long delays on my side!

I'll now open the vertex-transitive ticket and hopefully you can fill in the necessary tasks for the ticket.

[jdemeyer]

Please clarify which patch(es) have to be applied.

[ncohen]

Apply trac_13721_graph_symmetries.5.patch, trac_13721-rev.2.patch