Ask Your Question
2

The canonical labels in SageMath are different from those in nauty.

asked 2024-07-21 14:18:50 +0100

licheng gravatar image

updated 2024-07-21 14:43:09 +0100

Here are the canonical labels obtained from SageMath:

 sage: g=Graph('E{EG').canonical_label()
 sage: for vertex in g.vertices():
 ....:         neighbors = g.neighbors(vertex)
 ....:         print(f"Vertex {vertex}: {neighbors}")

Vertex 5: [1, 2, 3, 4]
Vertex 1: [5, 2]
Vertex 2: [5, 1]
Vertex 3: [5, 0]
Vertex 0: [3, 4]
Vertex 4: [5, 0]

However, for the same graph, the canonical labels I obtained using nauty are as follows.

echo 'E{EG' |labelg |showg

Graph 1, order 6.
  0 : 4 5;
  1 : 4 5;
  2 : 3 5;
  3 : 2 5;
  4 : 0 1;
  5 : 0 1 2 3;

As we see, the canonical labels in SageMath are different from those in nauty. Consequently, the graph6 strings they produce are also different.

Nauty: E@ro (by running echo 'E{EG' |labelg)

Sage: EK`w (by running Graph('E{EG').canonical_label().graph6_string())

Is it a bug? I would like to ask if there is a command in SageMath to make it consistent with the software nauty .

edit retag flag offensive close merge delete

1 Answer

Sort by ยป oldest newest most voted
2

answered 2024-07-21 15:24:19 +0100

rburing gravatar image

updated 2024-07-21 15:27:52 +0100

Yes they are different, the documentation of canonical_label states that it takes an algorithm parameter, and the default is to use bliss if it is available. There is no nauty option because SageMath currently has only a very limited integration of nauty, only using some of its executables to generate graphs.

Relevant:

Here is a workaround, using the labelg executable (assuming SageMath has nauty installed):

def nauty_canonical_label(g):
    from sage.env import SAGE_NAUTY_BINS_PREFIX
    import subprocess
    labelg = subprocess.run([SAGE_NAUTY_BINS_PREFIX + 'labelg', '-q'], input=g.graph6_string(), encoding='ascii', capture_output=True)
    return labelg.stdout.strip()

Example:

sage: nauty_canonical_label(Graph('E{EG'))
'E@ro'
edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2024-07-21 14:18:50 +0100

Seen: 233 times

Last updated: Jul 21