Opened 8 years ago
Closed 8 years ago
#13721 closed enhancement (fixed)
Additional tests for graph symmetries
Reported by: | azi | Owned by: | jason, ncohen, rlm |
---|---|---|---|
Priority: | major | Milestone: | sage-5.7 |
Component: | graph theory | Keywords: | |
Cc: | rbeezer, ncohen | Merged in: | sage-5.7.beta1 |
Authors: | Jernej Azarija | Reviewers: | Nathann Cohen, Tom Boothby |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
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 :
Attachments (7)
Change History (47)
comment:1 Changed 8 years ago by
- Status changed from new to needs_review
comment:2 Changed 8 years ago by
- Status changed from needs_review to needs_work
comment:3 Changed 8 years ago by
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?
- I kind of a agree. I thought it might be useful since this patch already defines the notion of semi-symmetric graphs.
- 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 8 years ago by
- 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.
- 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. ;)
- Okay, yeah, I shouldn't be asking for new features.
comment:5 Changed 8 years ago by
- 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.
- I agree! I am for both options depending on what others think.
comment:6 Changed 8 years ago by
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 8 years ago by
Hello ncooohen!!1
Thank you for the review. Let me answer the points as posted by you.
- 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.
- 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?
- That is a good point! This could be solved by having an optional argument that supplies the automorphism group to the named functions!
- Hahaha agree about the wording - I am waiting for the right time to tell it to someone IRL :-)
5.
- This should most likely be moved to Graph.py
comment:8 in reply to: ↑ 7 Changed 8 years ago by
Helloooooooooo !!
- 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.
- 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 :-)
- That is a good point! This could be solved by having an optional argument that supplies the automorphism group to the named functions!
- Hahaha agree about the wording - I am waiting for the right time to tell it to someone IRL :-)
5.
- This should most likely be moved to Graph.py
+1
Nathann
comment:9 Changed 8 years ago by
comment:10 Changed 8 years ago by
>_<
Another try : OnSets
,OnTuples
and OnPairs
.
comment:11 Changed 8 years ago by
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.
comment:12 Changed 8 years ago by
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 :-))))?
comment:13 Changed 8 years ago by
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 8 years ago by
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 8 years ago by
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!
comment:16 Changed 8 years ago by
- Status changed from needs_work to needs_review
comment:17 Changed 8 years ago by
- Status changed from needs_review to needs_work
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()
byreturn 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 foris_semi_symmetric
). - The documentation of
is_half_transitive
andis_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 ofsage -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 ofDiGraphs
objects. Could you add to the docstring ofis_edge_transitive
andis_arc_transitive
an explanation of their meaning whenself
is a DiGraph? ? The expected meaning ofis_edge_transitive
for DiGraphs? is actually the one obtained byis_arc_transitive
. Or do you think thatis_edge_transitive
should only be a method ofGraph
?
Thank you again for this patch ! I'll be glad to see it in Sage :-)
Nathann
comment:18 Changed 8 years ago by
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 8 years ago by
Patch rebased on 5.6.beta2 (which includes #8952)
Changed 8 years ago by
comment:20 Changed 8 years ago by
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 inGraph
) 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
comment:21 Changed 8 years ago by
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
Changed 8 years ago by
comment:22 Changed 8 years ago by
Apply trac_13721_graph_symmetries.2.patch
comment:23 Changed 8 years ago by
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
comment:24 Changed 8 years ago by
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 8 years ago by
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
Changed 8 years ago by
comment:26 Changed 8 years ago by
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.
comment:27 Changed 8 years ago by
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
Changed 8 years ago by
comment:28 Changed 8 years ago by
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 8 years ago by
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
Changed 8 years ago by
comment:30 Changed 8 years ago by
Hello!!!
The latest patch should reflect your remark now!
Best,
Jernej
comment:31 Changed 8 years ago by
- 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 8 years ago by
Apply trac_13721_graph_symmetries.5.patch, trac_13721-rev.2.patch
Nathann
comment:33 Changed 8 years ago by
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 8 years ago by
- Reviewers set to Nathann Cohen
Changed 8 years ago by
Changed 8 years ago by
comment:35 Changed 8 years ago by
- Summary changed from Additional tests for graph symmetries and an improvement of is_vertex_transitive to Additional tests for graph symmetries
comment:36 Changed 8 years ago by
- Milestone changed from sage-5.6 to sage-5.7
comment:37 Changed 8 years ago by
Please clarify which patch(es) have to be applied.
comment:38 Changed 8 years ago by
- Reviewers changed from Nathann Cohen to Nathann Cohen, Tom Boothby
comment:39 Changed 8 years ago by
- Description modified (diff)
Apply trac_13721_graph_symmetries.5.patch, trac_13721-rev.2.patch
comment:40 Changed 8 years ago by
- Merged in set to sage-5.7.beta1
- Resolution set to fixed
- Status changed from positive_review to closed
I haven't tested this, but I've got a couple of comments so far.
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 parameteredge_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 ofline_graph
so I think this is acceptable.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.is_arc_transitive
took an extra parameter so you could check if a graph is (for example) 2-arc transitive.