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: sage-7.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_cayley-21729 (Commits) Commit: 50d4e57e89ed0b5f6949c3786e4e109f309171d5
Dependencies: Stopgaps:

Description (last modified by amri)

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 amri

  • Branch set to u/amri/structural_cayley-21729
  • Commit set to 38e51e4b488fc2f8797e3cd227e02fa9a09b4156

New commits:

d423defAdded working code.
38e51e4Improved performance for chacking simple and deterministic

comment:2 Changed 4 years ago by amri

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 amri

  • Cc ncohen added

comment:4 Changed 4 years ago by git

  • Commit changed from 38e51e4b488fc2f8797e3cd227e02fa9a09b4156 to 45d3073eaddd5ba82967ca75a6d9c870e417e866

Branch pushed to git repo; I updated commit sha1. New commits:

45d3073Added documentation for DiGraph.is_cayley_directed

comment:5 Changed 4 years ago by amri

  • Cc jason boothby added
  • Description modified (diff)
  • Status changed from new to needs_review

comment:6 Changed 4 years ago by amri

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 git

  • Commit changed from 45d3073eaddd5ba82967ca75a6d9c870e417e866 to 50d4e57e89ed0b5f6949c3786e4e109f309171d5

Branch pushed to git repo; I updated commit sha1. New commits:

50d4e57algorithm for checking if digraph is Cayley now uses has_multiple_edges() method

comment:8 Changed 4 years ago by amri

  • Cc jmantysalo added; ncohen removed

New commits:

50d4e57algorithm for checking if digraph is Cayley now uses has_multiple_edges() method

comment:9 Changed 4 years ago by jmantysalo

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 dimpase

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.

Last edited 4 years ago by dimpase (previous) (diff)

comment:11 Changed 4 years ago by dimpase

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 edge-labelled (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 labels---there must be exactly k different labels, for k the out-degree of the (di)graph.

comment:12 follow-up: Changed 4 years ago by 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()
+            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 amri

  • Cc dimpase added

comment:14 in reply to: ↑ 12 ; follow-up: Changed 4 years ago by dimpase

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()
+            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.

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 point---the latter simply means that it's not a Cayley graph w.r.t. the set of generators corresponding to edge labels.

comment:15 follow-up: Changed 4 years ago by dcoudert

As a complement on the discussion on sage-dev, 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 ; follow-up: Changed 4 years ago by 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 vertex-transitivity.

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()
+            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.

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 point---the 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 ; follow-up: Changed 4 years ago by amri

Replying to dcoudert:

As a complement on the discussion on sage-dev, 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 dcoudert

Replying to amri:

Replying to dcoudert:

As a complement on the discussion on sage-dev, 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)
<ipython-input-4-598886da2d1f> in <module>()
----> 1 G._scream_if_not_simple()

/Users/dcoudert/sage/local/lib/python2.7/site-packages/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)
<ipython-input-8-45f9140e8d3e> in <module>()
----> 1 G._scream_if_not_simple(allow_loops=True)

/Users/dcoudert/sage/local/lib/python2.7/site-packages/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 dcoudert

A few comments:

  • In method is_deterministic, please use self.vertex_iterator() and self.outgoing_edge_iterator(v). Also, seen_ends = set() but not used.
  • the EXAMPLES section should show the interest for your new method, not is_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 dimpase

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 vertex-transitivity.

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 follow-up: Changed 11 months ago by vdelecroix

  • 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 return False.
  • Build the permutation group P acting on the vertices of G that consists in "following the labels" (one generator per label). Note that the transitivity of P is equivalent to the connectivity of G.
  • Pick a vertex v0 of G. If the vertex stabilizer in P of v0 is trivial then return True otherwise return False.

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 dimpase

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.

Note: See TracTickets for help on using tickets.