# Ticket #13721(closed enhancement: fixed)

Opened 6 months ago

## Additional tests for graph symmetries

Reported by: Owned by: azi jason, ncohen, rlm major sage-5.7 graph theory rbeezer, ncohen N/A Nathann Cohen, Tom Boothby Jernej Azarija sage-5.7.beta1

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 :

## Change History

### comment:1 Changed 6 months ago by azi

• Status changed from new to needs_review

### comment:2 Changed 6 months ago by boothby

• Status changed from needs_review to needs_work

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.
1. 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.
1. 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.

### comment:3 Changed 6 months ago by 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?

1. I kind of a agree. I thought it might be useful since this patch already defines the notion of semi-symmetric graphs.
1. 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.

### comment:4 Changed 6 months ago by 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.

1. 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. ;)
1. Okay, yeah, I shouldn't be asking for new features.

### comment:5 Changed 6 months ago by 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.

1. I agree! I am for both options depending on what others think.
Last edited 6 months ago by azi (previous) (diff)

### comment:6 Changed 6 months ago by 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

### comment:7 follow-up: ↓ 8 Changed 6 months ago by 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.
1. 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?
1. That is a good point! This could be solved by having an optional argument that supplies the automorphism group to the named functions!
1. Hahaha agree about the wording - I am waiting for the right time to tell it to someone IRL :-)

5.

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

### comment:8 in reply to: ↑ 7 Changed 6 months ago by 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.

1. 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 :-)

1. That is a good point! This could be solved by having an optional argument that supplies the automorphism group to the named functions!
1. Hahaha agree about the wording - I am waiting for the right time to tell it to someone IRL :-)

5.

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

+1

Nathann

### comment:9 Changed 6 months ago by ncohen

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

Nathann

### comment:10 Changed 6 months ago by ncohen

>_<

Another try : OnSets,OnTuples and OnPairs.

### comment:11 Changed 6 months ago by 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.

Last edited 6 months ago by boothby (previous) (diff)

### comment:12 Changed 6 months ago by 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 :-))))?

Last edited 6 months ago by azi (previous) (diff)

### comment:13 Changed 6 months ago by 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

### comment:14 Changed 6 months ago by 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

### comment:15 Changed 5 months ago by 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.

### comment:16 Changed 5 months ago by azi

• Status changed from needs_work to needs_review

### comment:17 Changed 5 months ago by ncohen

• Status changed from needs_review to needs_work

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

• 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

### comment:18 Changed 5 months ago by 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.

### comment:19 Changed 5 months ago by ncohen

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

### comment:20 Changed 5 months ago by 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))

```

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

### comment:21 Changed 5 months ago by 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

```
Last edited 5 months ago by azi (previous) (diff)

### comment:22 Changed 5 months ago by ncohen

Apply trac_13721_graph_symmetries.2.patch

### comment:23 Changed 5 months ago by 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

### comment:24 Changed 4 months ago by 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?

### comment:25 Changed 4 months ago by 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.is_vertex_transitive()
False
sage: d.is_vertex_transitive()
True
```

Nathann

### comment:26 Changed 4 months ago by 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.

Last edited 4 months ago by azi (previous) (diff)

### comment:27 Changed 4 months ago by 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

### comment:28 Changed 4 months ago by 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

### comment:29 Changed 4 months ago by 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

### comment:30 Changed 4 months ago by azi

Hello!!!

The latest patch should reflect your remark now!

Best,

Jernej

### comment:31 Changed 4 months ago by ncohen

• Status changed from needs_work to positive_review

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

### comment:32 Changed 4 months ago by ncohen

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

Nathann

### comment:33 Changed 4 months ago by 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.

### comment:34 Changed 4 months ago by ncohen

• Reviewers set to Nathann Cohen

### comment:35 Changed 4 months ago by ncohen

• Summary changed from Additional tests for graph symmetries and an improvement of is_vertex_transitive to Additional tests for graph symmetries

### comment:36 Changed 4 months ago by jdemeyer

• Milestone changed from sage-5.6 to sage-5.7

### comment:37 Changed 4 months ago by jdemeyer

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

### comment:38 Changed 4 months ago by boothby

• Reviewers changed from Nathann Cohen to Nathann Cohen, Tom Boothby

### comment:39 Changed 4 months ago by ncohen

• Description modified (diff)

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

### comment:40 Changed 4 months ago by jdemeyer

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