Digraphs
Digraphs copied to clipboard
digraphs
Is2EdgeTransitive performance update
Is2EdgeTransitive is currently very slow and space inefficient. The current implementation computes the cartesian product of the edges, then filters them to only include 2 edges, and computes a 2-edge orbit via the action OnTuplesTuples. If merged, Is2EdgeTransitive is rewritten to avoid these problems. See below comments.
I think you're still working on this, is that right @frankiegillis ?
Yes, currently benchmarking the two methods for computing the orbit of a 2-edge: Method 1 (Compute the orbit directly) against Method 2 (Compute the stabiliser).
Here are some plots. To benchmark, I generated random digraphs using RandomDigraph using the edge probability as a way of controlling the average orbit length.
It turns out that Method 1 is almost always faster, apart from when tested on the list of named digraphs when it is much slower. I don't think this is a case of Method 2 being fast, but Method 1 being unusually slow. I'm looking into this.
I've thought of a possible better way to compute Is2EdgeTransitive:
A 2-edge in a digraph D is a triple (u, v, w) of distinct vertices such that (u, v) and (v, w) are (directed) edges. In what follows, I call the vertex v the center of the 2-edge (u, v, w).
The idea is that if D is 2-edge transitive, then it must be transitive on 2-edge centers (since each 2-edge has a unique center). Therefore, every center must have the same in-degree and the same out-degree. The new algorithm first iterates through the vertices of D to form the list of 2-edge centers, returning false if any 2-edge centers have a different in-degree or out-degree. The number of 2-edges can then be calculated from knowing the in and out degree of a single vertex (minus loops, etc) and multiplying this by the number of 2-edge centers.
The orbit length of a single 2-edge is the calculated using the stabilizer method, as by this point we already know that D is regular on 2-edge centers, so is likely (though of course not guaranteed, see Frucht's graph for an example of a 3-regular graph with a trivial automorphism group) to be highly symmetric. Testing on both random and named digraphs confirms the stabilizer method to be faster.
This new method has two distinct advantages: finding the number of 2-edges is now O(Vertices), and the method may now return false before any orbit calculation occurs. It's also helpful to already have clues about the degree of symmetry of D and therefore know the stabilizer method is very likely to be much faster.
I also tested using DigraphRemoveLoops versus removing the loops in place during the main for loop. At the moment, using DigraphRemoveLoops turns out to be slightly faster. I think this is because it first checks HasDigraphHasLoops and then DigraphHasLoops so has the possibility of returning much faster. Either way, removing the vertices is generally quick compared to the other steps of computing the automorphism group and finding the 2-edge stabilizer, so for the sake of readability DigraphRemoveLoops wins.
If anything else needs to be changed or fixed I'm happy to continue working on this.
Here is some evidence that this new method is significantly faster than simply looping through all possible 2-edges
This PR also renames IsTwoEdgeTransitive to Is2EdgeTransitive. So either we should add a synonym, or this is a non-backwards-compatible breaking change that needs to be merged into the dev-2.0 branch, as things stand.
