Undirected graphs are sent as directed ones to dreadnaut (and bliss)

[TJenrich]

With respect to bliss, I already mentioned that observation in the final comment to issue #17. Now I saw that it also applies to dreadnaut and can have drastic consequences, not just an unnecessary doubling of the data to transmit. An example (on my Intel Pentium (R) Dual-Core E5500 at 2.80 GHz): For the $Fi{_23}$ graph (on 31671 vertices) dreadnaut needs just 58 seconds to read the input (about 620 MB) and execute the contained commands (in order to deliver automorphism group generators) if the command d (to set dreadnaut's option digraph from the default value FALSE to TRUE) is removed from the begin of the input. In contrast, when the original input is used, it takes more than (sorry, I want to go to bed now) 90 MINUTES for the same task.

[lhsoicher]

Thank you @TJenrich for bringing this issue to my attention. I will need to do something about this for the next release of GRAPE. Interestingly, both nauty and bliss seem to have no particular problem with the Fi22 graph (with 3510 vertices and degree 693) treated as a directed graph.

[TJenrich]

Thank you @lhsoicher for your answer. Funny: Just before seeing your comment I experimented with the Fi22 graph, too. You wrote that nauty and bliss do not have a (particular) problem with it. One can see it that way, but: In the directed mode, dreadnaut takes more time and the number of generators is bigger. Here are the summaries from the two dreadnaut runs (first undirected mode, second directed mode):

level 1: 1 orbit; 1 fixed; index 3510 1 orbit; grpsize=1.291235033088e14; 9 gens; 33 nodes; maxlev=7 cpu time = 1.92 seconds

level 1: 1 orbit; 1 fixed; index 3510 1 orbit; grpsize=1.291235033088e14; 16 gens; 82 nodes; maxlev=10 cpu time = 10.37 seconds

For reproduction purposes, here is the construction of the Fi22 graph (named Graf) that I have used:

LoadPackage("atlasrep");; LoadPackage("grape");; G:=AtlasGroup("Fi22"); H:=AtlasSubgroup(G,1); o:=Set(Orbits(H)[2]);; oo:=Orbit(G,o,OnSets);; G3510:=Action(G,oo,OnSets); H3510:=Action(H,oo,OnSets); List(Orbits(H3510),x->x[1]); #[2,8] OrbitLengths(H3510); #[ 2816, 693 ] Graf:=NullGraph(G3510);; AddEdgeOrbit(Graf,[1,8]);

[TJenrich]

Dear @lhsoicher, as you probably know, dreadnaut integrates not just nauty but also Traces. When running dreadnaut, one can switch to Trace by the command At . Typing that command and then feeding the data for the just considered Fi22 graph as undirected graph results in even faster execution and reduction of the number of generators. Here is the summary:

1 orbit; grpsize=1.291235033088e14; 2 gens; 24 nodes (2 peak); maxlev=6 cpu time = 0.20 seconds

In the case of the Fi23 graph, the summaries of the dreadnaut runs (in undirected mode) are (first nauty, second Traces):

1 orbit; grpsize=4.089470473293e18; 9 gens; 73 nodes (42 bad leaves); maxlev=7 cpu time = 56.51 seconds

1 orbit; grpsize=4.089470473293e18; 2 gens; 59 nodes (24 interrupted, 2 peak); maxlev=7 cpu time = 15.78 seconds

The runtime relations are consistent with the test statistics given in the appendix of (the arXiv article 1301.1493) "Practical graph isomorphism, II" by McKay and Piperno, the authors of nauty and Traces. The reduction of the number of generators can be even more important for some puposes. On the other hand, Traces needs considerable more memory than nauty, as observed in the case of the Fi23 graph. So, I also propose that you allow the GRAPE user to switch not just between bliss and dreadnaut but also between nauty and Traces.

[TJenrich]

Surely, it needs some effort to enable GRAPE to read the output of dreadnaut not just in nauty mode but also in Traces mode. But there can be a big difference of the numbers of generators depending on whether nauty or Traces is used, even for rather tiny graphs, as the one constructed by:

LoadPackage("grape"); V:=[ [1,1,0,0], [-1,1,0,0], [1,-1,0,0], [-1,-1,0,0], [1,0,1,0], [-1,0,1,0], [1,0,-1,0], [-1,0,-1,0], [1,0,0,1], [-1,0,0,1], [1,0,0,-1], [-1,0,0,-1], [0,1,1,0], [0,-1,1,0], [0,1,-1,0], [0,-1,-1,0], [0,1,0,1], [0,-1,0,1], [0,1,0,-1], [0,-1,0,-1], [0,0,1,1], [0,0,-1,1], [0,0,1,-1], [0,0,-1,-1]]; Adf := function (x,y); return((x<>y) and (V[x]*V[y]<>0)); end; Graf:=Graph(Group(()),[1..24],OnPoints, Adf); Aut:=AutomorphismGroup(Graf);

With the command d removed from the start of the dreadnaut input, I have got these execution summaries (first nauty, second Traces):

1 orbit; grpsize=339738624; 17 gens; 132 nodes; maxlev=13 cpu time = 0.00 seconds

1 orbit; grpsize=339738624; 6 gens; 53 nodes (2 peak); maxlev=9 cpu time = 0.00 seconds

I tried to find in the "nauty Traces User's Guide (Version 2.7)" a hint on known redundancy of the generator sets that could be used to select just the essential ones but did not succeed. But I am not absolutely sure that that was not my failure.

[lhsoicher]

Thank you @TJenrich for your comments and experimental results regarding nauty vs Traces. I will certainly consider providing the functionality and documentation to support the option for a user to use Traces in the next major release of GRAPE, which may not happen for a while.

The observation that Traces tends to produce a smaller generating set than nauty for the automorphism group of a graph may be (in part) due to the fact that, unlike nauty, Traces does not necessarily produce a (base and) strong generating set for the automorphism group, but any serious computation with this automorphism group would require the construction of a base and strong generating set, which would likely introduce further generators.

[TJenrich]

Dear @lhsoicher, thank you for your (basically) positive response to my suggestions and other comments and for being (relatively) clear with respect to a potential integration of (some of) the proposals into GRAPE.

[lhsoicher]

@TJenrich please note.In the current GRAPE release (version 4.8.4, which is not yet included in a main GAP release), simple graphs are now output as undirected graphs for both dreadnaut/nauty and bliss.