3
$\begingroup$

I need to compute canonical forms of many (~10^6-10^8) vertex-facets incidence graphs of polytope. Two rather big examples I want to consider are

  • the 600-cell with 120 vertices and 600 facets (dimension 4), and
  • the smallest known counter example to the Hirsch bound with 40 vertices and 36426 facets (dimension 20).

The two options that seem to be best suited to compute these canonical forms are nauty and bliss. My questions are

  • Is there another option that I have overseen?

  • I have not found any benchmark comparisons between the two, so should I prefer one over the other?

  • Does the property of being bipartite make a difference in which to choose?

Many Thanks! -- this is not a strictly mathematical question, but I hope it is still suitable here.

The graphs that are test cases can be found in dreadnaut format here: counter example to the Hirsch conjecture, 600-cell, and 1000 typical examples.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

You can find a comparison at http://pallini.di.uniroma1.it under the "experiments" link, and Traces is there too. It's hard to tell in advance what will work best. Either your graphs are like typical graphs of these sizes, in which case all the algorithms will be fast enough, or they are much harder, in which case some care is needed. If you send me a handful of typical examples in one of the two formats that are used at http://pallini.di.uniroma1.it/Graphs.html , I will give more precise advice.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Great, thanks for the offer -- I will send you some graphs later today once I got them into the desired format! $\endgroup$
    – Christian Stump
    Commented Jun 13, 2016 at 11:33
  • $\begingroup$ It starts at vertex 0, so should have \$=0 not \$=1. Also there are no line breaks in the file so some numbers are joined together. After fixing it as I think it should be, nauty (sparse mode) finishes in 0.02 seconds. It is easy because the vertices on the small side have a mixture of degrees. Vertex 40 (the first on the big side) has anomalous 40; should it? $\endgroup$
    – Brendan McKay
    Commented Jun 13, 2016 at 12:39
  • $\begingroup$ @Christian : I don't have access to that file. Also, you might have received an access request via gmail, but I don't use that address for email. $\endgroup$
    – Brendan McKay
    Commented Jun 13, 2016 at 23:35
  • $\begingroup$ @Christian: The 600-cell is easy because the automorphism group is large. Sparse nauty 0.00055 sec, bliss 0.00141 sec, Traces 0.00061 sec. For the previous large irregular graph: sparse nauty 0.013 sec, bliss 0.064 sec, Traces 0.019 sec. A more difficult example would be highly regular without automorphisms. $\endgroup$
    – Brendan McKay
    Commented Jun 14, 2016 at 22:34
  • $\begingroup$ I moved the links to the examples to the end of the question, so it becomes easier to find in case someone wants to find them. $\endgroup$
    – Christian Stump
    Commented Jun 15, 2016 at 14:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .