Ask Your Question
1

Can the bytes returned by pynauty's "certificate" function be converted into a graph format readable by Sage?

asked 2023-05-26 08:44:07 +0200

licheng gravatar image

updated 2023-05-26 08:56:09 +0200

I know nauty has been integrated with Sage. Has pynauty been integrated in Sage 10?

I am using Sage 9.5, and it doesn't seem to have pynauty integrated. So, I installed this third-party package. I'm particularly interested in one of its functions, certificate. The function "certificate" serves a similar purpose to the canonical_label in Sage. (A canonical graph is the representative graph of an isomorphism class by some canonization function $c$. If $G$ and $H$ are graphs, then $G \cong c(G)$, and $c(G)==c(H)$ if and only if $G \cong H$.)

However, certificate(g) provides bytes instead of a graph. I'm not sure how to interpret them. I'm thinking of converting a graph after applying certificate(g) into the graph format used in Sage.

from pynauty import *
g = Graph(5)
g.connect_vertex(0, [1, 2, 3])
g.connect_vertex(2, [1, 3, 4])
g.connect_vertex(4, [3])
print(g)
g1=certificate(g)

b'\x00\x00\x00\x00\x00\x00\x00(\x00\x00\x00\x00\x00\x00\x00\x18\x00\x00\x00\x00\x00\x00\x00\x98\x00\x00\x00\x00\x00\x00\x00h\x00\x00\x00\x00\x00\x00\x00\xf0'

I cannot convert the above bytes to graphs. It preferable to preserve its "canonical" form when converting the bytes into a graph format in Sage.

I opened an issue on the developer's interface, but it seems like there hasn't been a response yet. See the following link:

edit retag flag offensive close merge delete

1 Answer

Sort by » oldest newest most voted
2

answered 2023-05-26 11:09:32 +0200

rburing gravatar image

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/is....)

edit flag offensive delete link more

Comments

Very nice!

licheng gravatar imagelicheng ( 2023-05-26 14:45:04 +0200 )edit

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: 2023-05-26 08:44:07 +0200

Seen: 416 times

Last updated: May 26 '23