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

[lichengzhang1]

Cross-posted on how-can-we-interpret-the-graph-information-after-certificate-in-pynauty

This may not be a software issue, but I'm writing my confusion here.

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

• certificate

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'

I belive that these bytes represent a graph that is not human-readable.

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.

[rburing]

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]

[pdobsan]

On Fri, May 26, 2023 at 02:07:39AM -0700, Ricardo Buring wrote:

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

Nice, you've beat me to it. Maybe I add a similar function written in C to the next release.

Peter

[salotz]

Glad this issue is here to explain what the certificate is! My hunch was essentially correct, but searching the user guide for "certificate" returns nothing and the pynauty documentation doesn't explain at all.