First time here? Check out the FAQ!

Ask Your Question
1

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

asked 1 year ago

licheng gravatar image

updated 1 year ago

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 Gc(G), and c(G)==c(H) if and only if GH.)

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:

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
2

answered 1 year ago

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

Preview: (hide)
link

Comments

Very nice!

licheng gravatar imagelicheng ( 1 year ago )

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: 1 year ago

Seen: 811 times

Last updated: May 26 '23