Opened 4 years ago
Last modified 11 months ago
#21729 needs_info enhancement
Implement Didier Caucal's structural description of Cayley graphs
Reported by:  amri  Owned by:  

Priority:  minor  Milestone:  sage7.5 
Component:  graph theory  Keywords:  cayley graphs 
Cc:  jason, boothby, jmantysalo, dimpase  Merged in:  
Authors:  Amritanshu Prasad  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/amri/structural_cayley21729 (Commits)  Commit:  50d4e57e89ed0b5f6949c3786e4e109f309171d5 
Dependencies:  Stopgaps: 
Description (last modified by )
In a recent preprint https://arxiv.org/abs/1609.08272 titled Structural characterization of Cayley graphs, Didier Caucal has proved that a directed graph is Cayley if and only if it is strongly connected, simple, deterministic, and vertex transitive.
The present method for determining if a graph is Cayley in Sage involves looking for a free transitive subgroup of the automorphism group, which appears to be slower for directed graphs. Moreover, it uses optional gap packages, which are not needed here. This method works only for directed graphs, and is sensitive to edge labels.
Change History (22)
comment:1 Changed 4 years ago by
 Branch set to u/amri/structural_cayley21729
 Commit set to 38e51e4b488fc2f8797e3cd227e02fa9a09b4156
comment:2 Changed 4 years ago by
It runs a little faster than the existing code, even though my implementation is probably far from optimized.
sage: G = groups.permutation.Mathieu(9) sage: S = Set(G).subsets().random_element() sage: gr = G.cayley_graph(generators=list(S)) sage: %timeit gr.is_cayley() 100 loops, best of 3: 14.5 ms per loop sage: %timeit gr.is_cayley_directed() 100 loops, best of 3: 6.92 ms per loop
comment:3 Changed 4 years ago by
 Cc ncohen added
comment:4 Changed 4 years ago by
 Commit changed from 38e51e4b488fc2f8797e3cd227e02fa9a09b4156 to 45d3073eaddd5ba82967ca75a6d9c870e417e866
Branch pushed to git repo; I updated commit sha1. New commits:
45d3073  Added documentation for DiGraph.is_cayley_directed

comment:5 Changed 4 years ago by
 Cc jason boothby added
 Description modified (diff)
 Status changed from new to needs_review
comment:6 Changed 4 years ago by
More speed testing (see noticable improvement):
sage: G = groups.permutation.DiCyclic(4) sage: D = G.cayley_graph() sage: %timeit D.is_cayley() 10 loops, best of 3: 6.82 ms per loop sage: %timeit D.is_cayley_directed() 1000 loops, best of 3: 343 µs per loop
sage: G = groups.permutation.PGL(2,4) sage: D = G.cayley_graph() sage: %timeit D.is_cayley() 1 loop, best of 3: 96.8 ms per loop sage: %timeit D.is_cayley_directed() 1000 loops, best of 3: 1.25 ms per loop
We try a random graph
sage: D = digraphs.RandomDirectedGN(20) sage: %timeit D.is_cayley() The slowest run took 6.25 times longer than the fastest. This could mean that an intermediate result is being cached. 10 loops, best of 3: 4.01 ms per loop sage: %timeit D.is_cayley_directed() The slowest run took 10.74 times longer than the fastest. This could mean that an intermediate result is being cached. 1000000 loops, best of 3: 1.31 µs per loop
comment:7 Changed 4 years ago by
 Commit changed from 45d3073eaddd5ba82967ca75a6d9c870e417e866 to 50d4e57e89ed0b5f6949c3786e4e109f309171d5
Branch pushed to git repo; I updated commit sha1. New commits:
50d4e57  algorithm for checking if digraph is Cayley now uses has_multiple_edges() method

comment:8 Changed 4 years ago by
 Cc jmantysalo added; ncohen removed
New commits:
50d4e57  algorithm for checking if digraph is Cayley now uses has_multiple_edges() method

comment:9 Changed 4 years ago by
At least seen_ends
is now unused.
This can be done in two lines,
seen = set() not any(e[2] in seen or seen.add(e[2]) for v in self for e in self.outgoing_edge_iterator(v))
but your version might be easier to read.
I still hope that someone who has read the paper can review this.
comment:10 Changed 4 years ago by
I think the documentation should include a warning saying that the result has not been published in a refereed medium yet. While the author is certainly a respected researcher, it's in itself is not a guarantee for correctness.
comment:11 Changed 4 years ago by
I don't think it's correct to say that this is a faster algorithm to determine if the graph is Cayley. This is an algorithm to do this for a special class of edgelabelled (di)graphs. It's not clear at all that this method can be efficiently extended to the unlabelled case (and indeed nothing of this is claimed in the paper).
In the docstring
+ A directed graph with labeled edges is Cayley if and only if it is + strongly connected, vertex transitive, simple and deterministic.
the main result of the paper is misstated; certainly not every labelling of edges can be considered. Certainly for each vertex each outedge on it must have a different label. And a directed labelled Cayley graph has more restrictions of labelsthere must be exactly k different labels, for k the outdegree of the (di)graph.
comment:12 followup: ↓ 14 Changed 4 years ago by
In this setting, a Cayley graph *is* a directed graph with edges labeled by generators. Dima rightly points out that if the edge labeling is changed, then the algorithm will not recognize the graph as Cayley. I pointed this out in the documentation:
+ This method is sensitive to edge labels:: + + sage: g = DiGraph([(1, 2, 1), (2, 3, 1), (3, 1, 1), (2, 1, 1), (3, 2, 1), (1, 3, 1)]) + sage: g.is_cayley() + True + sage: g.is_cayley_directed() + False
Do you think I should make it more prominent? And of course, it is for this reason that the algorithm runs so fast  it uses the additional information (edge labels) which the earlier (Sabidussi) algorithm does not take into account.
comment:13 Changed 4 years ago by
 Cc dimpase added
comment:14 in reply to: ↑ 12 ; followup: ↓ 16 Changed 4 years ago by
Replying to amri:
In this setting, a Cayley graph *is* a directed graph with edges labeled by generators. Dima rightly points out that if the edge labeling is changed, then the algorithm will not recognize the graph as Cayley. I pointed this out in the documentation:
+ This method is sensitive to edge labels:: + + sage: g = DiGraph([(1, 2, 1), (2, 3, 1), (3, 1, 1), (2, 1, 1), (3, 2, 1), (1, 3, 1)]) + sage: g.is_cayley() + True + sage: g.is_cayley_directed() + FalseDo you think I should make it more prominent? And of course, it is for this reason that the algorithm runs so fast  it uses the additional information (edge labels) which the earlier (Sabidussi) algorithm does not take into account.
The problem this ticket solve is the following:
given a digraph D with edge labels 1,2,...,k, decide if there exists a group G generated by g_1,...,g_k so that D is the Cayley graph of G w.r.t. the generators g_1,...,g_k, right?
This is much more restrictive and much easier than recognising whether a digraph is a Cayley graph w.r.t. some group G with some set of generators.
In fact, it is straightforward to read the group off a Cayley graph with edge labels, and so I don't see why this is so interesting (it's good to have, but probably the punchline of the paper in question is somewhere else). Indeed, if the arc (ij) is labelled by g this just means that the permutation g maps i to j, and so you can reconstruct all the permutations, or get stuck at some pointthe latter simply means that it's not a Cayley graph w.r.t. the set of generators corresponding to edge labels.
comment:15 followup: ↓ 17 Changed 4 years ago by
As a complement on the discussion on sagedev, you may consider method G._scream_if_not_simple()
that raises an error if the graph is not simple (loops or multiple edges).
David.
comment:16 in reply to: ↑ 14 ; followup: ↓ 20 Changed 4 years ago by
Replying to dimpase:
While I agree that it is easy to read off a group from its Cayley graph when the edges are labeled, I believe that recognizing the graph to be Cayley is less easy. You could, for example take the group with generators the out edges from some node, and then use as relations the cycle language of that node (which forms a subgroup). However, you would still need to check that the graph you have is the Cayley graph of this group you have constructed. This turns out to be equivalent to vertextransitivity.
Replying to amri:
In this setting, a Cayley graph *is* a directed graph with edges labeled by generators. Dima rightly points out that if the edge labeling is changed, then the algorithm will not recognize the graph as Cayley. I pointed this out in the documentation:
+ This method is sensitive to edge labels:: + + sage: g = DiGraph([(1, 2, 1), (2, 3, 1), (3, 1, 1), (2, 1, 1), (3, 2, 1), (1, 3, 1)]) + sage: g.is_cayley() + True + sage: g.is_cayley_directed() + FalseDo you think I should make it more prominent? And of course, it is for this reason that the algorithm runs so fast  it uses the additional information (edge labels) which the earlier (Sabidussi) algorithm does not take into account.
The problem this ticket solve is the following:
given a digraph D with edge labels 1,2,...,k, decide if there exists a group G generated by g_1,...,g_k so that D is the Cayley graph of G w.r.t. the generators g_1,...,g_k, right?
This is much more restrictive and much easier than recognising whether a digraph is a Cayley graph w.r.t. some group G with some set of generators.
In fact, it is straightforward to read the group off a Cayley graph with edge labels, and so I don't see why this is so interesting (it's good to have, but probably the punchline of the paper in question is somewhere else). Indeed, if the arc (ij) is labelled by g this just means that the permutation g maps i to j, and so you can reconstruct all the permutations, or get stuck at some pointthe latter simply means that it's not a Cayley graph w.r.t. the set of generators corresponding to edge labels.
comment:17 in reply to: ↑ 15 ; followup: ↓ 18 Changed 4 years ago by
Replying to dcoudert:
As a complement on the discussion on sagedev, you may consider method
G._scream_if_not_simple()
that raises an error if the graph is not simple (loops or multiple edges). David.
I am not sure I understand how this works. Can you point me to a similar example?
comment:18 in reply to: ↑ 17 Changed 4 years ago by
Replying to amri:
Replying to dcoudert:
As a complement on the discussion on sagedev, you may consider method
G._scream_if_not_simple()
that raises an error if the graph is not simple (loops or multiple edges). David.I am not sure I understand how this works. Can you point me to a similar example?
sage: G = Graph([(0,1)]) sage: G._scream_if_not_simple() sage: G = Graph([(0,1), (0,1)], multiedges=True) sage: G._scream_if_not_simple()  ValueError Traceback (most recent call last) <ipythoninput4598886da2d1f> in <module>() > 1 G._scream_if_not_simple() /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in _scream_if_not_simple(self, allow_loops, allow_multiple_edges) 1295 "meantime if you want to use it please disallow "+name+" using "+ 1296 functions+".") > 1297 raise ValueError(msg) 1298 1299 def networkx_graph(self, copy=True): ValueError: This method is not known to work on graphs with multiedges. Perhaps this method can be updated to handle them, but in the meantime if you want to use it please disallow multiedges using allow_multiple_edges(). sage: try: ....: G._scream_if_not_simple() ....: print "I'm simple" ....: except: ....: print "I'm not simple" ....: I'm not simple
you can also decide to tolerate loops but not multiedges or the opposite.
sage: G = Graph([(0,1), (0,1)], multiedges=True) sage: G._scream_if_not_simple(allow_multiple_edges=True) sage: G._scream_if_not_simple(allow_loops=True)  ValueError Traceback (most recent call last) <ipythoninput845f9140e8d3e> in <module>() > 1 G._scream_if_not_simple(allow_loops=True) /Users/dcoudert/sage/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in _scream_if_not_simple(self, allow_loops, allow_multiple_edges) 1295 "meantime if you want to use it please disallow "+name+" using "+ 1296 functions+".") > 1297 raise ValueError(msg) 1298 1299 def networkx_graph(self, copy=True): ValueError: This method is not known to work on graphs with multiedges. Perhaps this method can be updated to handle them, but in the meantime if you want to use it please disallow multiedges using allow_multiple_edges().
comment:19 Changed 4 years ago by
A few comments:
 In method
is_deterministic
, please useself.vertex_iterator()
andself.outgoing_edge_iterator(v)
. Also,seen_ends = set()
but not used.  the
EXAMPLES
section should show the interest for your new method, notis_cayley
only.  I think that references should now be placed in the global bibliography file. See #21454
 Add in method a SEEALSO section with :meth:
~sage.graphs.digraph.DiGraph.is_cayley_directed
 What if the digraph has loops?
comment:20 in reply to: ↑ 16 Changed 4 years ago by
Replying to amri:
Replying to dimpase:
While I agree that it is easy to read off a group from its Cayley graph when the edges are labeled, I believe that recognizing the graph to be Cayley is less easy. You could, for example take the group with generators the out edges from some node, and then use as relations the cycle language of that node (which forms a subgroup). However, you would still need to check that the graph you have is the Cayley graph of this group you have constructed. This turns out to be equivalent to vertextransitivity.
Checking transitivity of a permutation group given by generators is quite easy and can be done very efficiently.
What is however less obvious is how to check is that you get a group acting regularly (i.e. transitively and with trivial vertex stabiliser). And this is something I did not mention in my previous comment.
For this, the quickest way I know is to write down the Schreier generators for the point stabiliser and check that they are all trivial. This seems to be possible to do in time O(nr), with n the number of vertices and r number of group generators.
Does the paper offer anything faster?
comment:21 followup: ↓ 22 Changed 11 months ago by
 Status changed from needs_review to needs_info
I agree with Dima, this characterization is certainly not new, and probably not the punchline of the article advertised in the description. For example, it corresponds to the characterization of Galois covers in algebraic topology (see e.g. the book of A. Hatcher).
Dima: following these steps it is enough to check for a single vertex stabilizer
 Test whether the graph
G
is connected and at each vertex there are exactly an input and an output edges of each label. If not returnFalse
.  Build the permutation group
P
acting on the vertices ofG
that consists in "following the labels" (one generator per label). Note that the transitivity ofP
is equivalent to the connectivity ofG
.  Pick a vertex
v0
ofG
. If the vertex stabilizer inP
ofv0
is trivial then returnTrue
otherwise returnFalse
.
The reason that it works is that vertex stabilizers are conjugate (since the group P
acts transitively on the vertices).
As pointed out by Dima, testing whether an unlabelled graph is Cayley is much more interesting. It is certainly doable starting from the automorphism group of the graph and analyzing the vertex stabilizer of a point.
comment:22 in reply to: ↑ 21 Changed 11 months ago by
Replying to vdelecroix:
As pointed out by Dima, testing whether an unlabelled graph is Cayley is much more interesting. It is certainly doable starting from the automorphism group of the graph and analyzing the vertex stabilizer of a point.
it's much harder than that: the full automorphism group can be bigger, so one needs to look up all the transitive subgroups (up to conjugation) and check whether one of them is regular.
New commits:
Added working code.
Improved performance for chacking simple and deterministic