Search code examples
pythongraphbytegraph-theoryisomorphism

How can we interpret the graph information after certificate in Pynauty?

Cross-posted on pynauty_read_certificate.

Pynauty is a Python/C extension module using library components from the Nauty package by Brendan McKay.

In Pynauty, the function certificate can compute a certificate based on the canonical labeling of vertices. It returns the certificate as a byte string.

g=Graph(number_of_vertices=19, directed=False,
 adjacency_dict = {
  0: [1, 7, 11, 14, 17, 18],
  1: [2, 3, 4, 5, 6],
  7: [8, 9, 10],
  11: [12, 13],
  14: [15, 16],
  12: [13],
  13: [17],
  17: [18],
  18: [8],
  8: [9],
  9: [10],
  10: [15],
  15: [16],
  16: [2],
  2: [3],
  3: [4],
  4: [5],
  5: [6],
  6: [12],
 },
 vertex_coloring = [
 ],
)
g1=certificate(g)

I will see this:

b'\x00\x00\x00\x00\x00\x80\x01 \x00\x00\x00\x00\x00\x80\x02 \x00\x00\x00\x00\x00\x80\x00\xc0\x00\x00\x00\x00\x00 \x04\x01\x00\x00\x00\x00\x00 \x08\x02\x00\x00\x00\x00\x00 \x00\x03\x00\x00\x00\x00\x00 \x00\x0c\x00\x00\x00\x00\x00 \x00\x14\x00\x00\x00\x00\x00@"\x00\x00\x00\x00\x00\x00@\t\x00\x00\x00\x00\x00\x00\x00\x94\x00\x00\x00\x00\x00\x00@$\x00\x00\x00\x00\x00\x00\x00A\x08\x00\x00\x00\x00\x00\x000\x10\x00\x00\x00\x00\x00@\x80@\x00\x00\x00\x00\x00\x00H\x80\x00\x00\x00\x00\x00@\x00\xe0\x00\x00\x00\x00\x00\xa0\xd2\x00\x00\x00\x00\x00\x00@\x00\x1f'

Is the certificate returned in another form of input graph? I don't know if this process is reversible. Because g1 is in the form of bytes, I can't see the graph it represents, or, in other words, the information about the graph represented by g1 from its result. (Its vertex labels have likely been relabeled based on the canonical labeling).

If it is possible to convert them into the graph6 format for storage, it would indeed be a good choice. This format allows for compatibility with various other tools, such as showg, which can read and manipulate graphs in graph6 format.

Solution

  • This is using nauty's internal dense format, described in nauty and Traces User’s Guide (Version 2.8.6) section 3.

    Here's a hacky way to get a graph out of it:

    set_length = len(g1) // g.number_of_vertices
sets = [g1[set_length*k:set_length*(k+1)] for k in range(g.number_of_vertices)]
neighbors = [[i for i in range(set_length * 8) if st[-1 - i//8] & (1 << (7 - i%8))] for st in sets]
g_canon = Graph(number_of_vertices=g.number_of_vertices, directed=False, adjacency_dict={i: neighbors[i] for i in range(g.number_of_vertices)})

    Check:

    >>> certificate(g_canon) == certificate(g)
True
>>> from pynauty import canon_label
>>> canon_label(g_canon)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]

    (Cross-posted from https://github.com/pdobsan/pynauty/issues/30#issuecomment-1564066767)