Relabeling

[pdobsan]

Write a procedure to create a new graph by relabeling an existing graph according to a permutation of its vertices.

Rewrite/extend isomorphism and canonical labeling tests using relabeling by random permutations.

Related branch: relabeling

[sammorley-short]

@pdobsan: let me know if you'd like me to take a look at the code at any point, or contribute in any other way. Happy to help!

[pdobsan]

On Sat, Jul 17, 2021 at 05:29:07PM -0700, sammorley-short wrote: @pdobsan: let me know if you'd like me to take a look at the code at any point, or contribute in any other way. Happy to help!

Yes please have a look at it. As you can see the isomorphism tests pass for all graphs. The canonical labeling however seems to be not invariant under random relabeling. The canon_label tests fall for most graphs, depending on the relabeling. Multiple runs gives different results, sometimes with very long running times.

[pdobsan]

I have cleaned all tests up a bit. In particular I removed the `delete_random_edge` part from `test_canonlabel.py`. It did not make any sense, non isomorphic graphs can have the same canonical labeling. I am not clear about isomorphic ones yet. Made a target just for canonlabel, invoke it as `make canonlabel-test`. Most graphs "fail" when the random permutation of vertices is applied.

[CharHeap]

Hi!

I was surprised to find that re-applying canon_label to a canonized graph (using the relabelling given by canon_label) would not give the identity. So I guess this issue still persists and it still fails on most graphs?

@sammorley-short could you possibly look into that and fix the function? I can provide examples of (simple) graphs where the function failed for me.

[CharHeap]

Because the graph is simple (just 4 nodes) I'll leave it here:

g1 = Graph(number_of_vertices = 4, directed = False,
    adjacency_dict = {
        0: [2, 3],
        1: [2, 3],
    },
    vertex_coloring = [
    ],
)

canon_label(g1)
# [0, 2, 3, 1]

# applied the relabelling on g1 to get g2:
g2 = Graph(number_of_vertices = 4, directed = False,
    adjacency_dict = {
        0: [1, 3],
        2: [1, 3],
    },
    vertex_coloring = [
    ],
)

canon_label(g2)
# [0, 1, 3, 2]

To my understanding canon_label(g2) should return the identity, meaning [0, 1, 2, 3]?

[CharHeap]

What seems to work for now is creating the canon graph from the certificate as described here: #30 (comment)
for which canon_label returns the identity.

In my case:

g_canon = Graph(number_of_vertices=4, directed=False,
 adjacency_dict = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2],
 },
 vertex_coloring = [
 ],
)

canon_label(g_canon)
[0, 1, 2, 3]

[CharHeap]

P.S.: It was even possible to remove one direction of each undirected edge to get

g_canon_undirected = Graph(number_of_vertices=4, directed=False,
 adjacency_dict = {
  0: [1, 2],
  1: [3],
  2: [3],
  3: [],
 },
 vertex_coloring = [
 ],
)

For which canon_label(g_canon_undirected) still returns [0, 1, 2, 3] :)

Note: to get a relabeling I then used networkx's isomorphism.GraphMatcher(g_original_nx, g_canon_nx).isomorphisms_iter() where g_original_nx and g_canon_nx are networkx graphs from the original and the canon adjacency dictionaries.

[pdobsan]

On Wed, Sep 20, 2023 at 01:43:45PM -0700, CharHeap wrote: What seems to work for now is creating the canon graph from the certificate as described here: #30 (comment) for which `canon_label` returns the identity.

Please note that a canon_graph() function is already implemented but not released yet. So with the current repo, your graph should work like below. In [3]: g1 = Graph(number_of_vertices = 4, directed = False, ...: adjacency_dict = { ...: 0: [2, 3], ...: 1: [2, 3], ...: }, ...: vertex_coloring = [ ...: ], ...: ) In [4]: canon_label(canon_graph(g1)) Out[4]: [0, 1, 2, 3]

[CharHeap]

On Wed, Sep 20, 2023 at 01:43:45PM -0700, CharHeap wrote: What seems to work for now is creating the canon graph from the certificate as described here: #30 (comment) for which canon_label returns the identity.
Please note that a canon_graph() function is already implemented but not released yet. So with the current repo, your graph should work like below. In [3]: g1 = Graph(number_of_vertices = 4, directed = False, ...: adjacency_dict = { ...: 0: [2, 3], ...: 1: [2, 3], ...: }, ...: vertex_coloring = [ ...: ], ...: ) In [4]: canon_label(canon_graph(g1)) Out[4]: [0, 1, 2, 3]

Thanks for your reply.

It's true that canon_label returns the identity after canon_graph has been applied, but that is not what I need. I need/was expecting canon_label(g1) to return a re-labeling that, when applied to g1, makes it canon.

I had a look at the graph_canonlab function in nautywrap.c and as far as I can tell it just lists the labels of the canon_graph? It looks like that is not the relabelling I need..

How could I compute a relabelling efficiently? My call to networkx's GraphMatcher isomorphisms_iter worked but quickly becomes infeasible for larger meshes.

EDIT: I compared the mappings I had tediously computed with networkx and the output of canon_label and noticed that I had just interpreted the output wrongly. As an example: [3, 4, 0, 1, 2], here I though I had to map 0 to 3, 1 to 4, 2 to 0 and so on.. When in fact I need to map it the other way around! 3 to 0, 4 to 1, 0 to 2.. So at index i of the canon_label output you don't find the target of i but its source instead. So my mapping needs to be:

mapping = {s: t for t, s in enumerate(pynauty.canon_label(g))}