Multigraph isomorphism broken in graphs with self-loops
This is a dangerous bug for users to not realize. Minimal working example:
import graph_tool as gt
import graph_tool.topology
print gt.__version__
g = gt.Graph(directed=False)
g.add_vertex(4)
g.add_edge(0,0)
g.add_edge(0,3); g.add_edge(0,3);
g.add_edge(2,3); g.add_edge(2,3);
g.add_edge(2,1); g.add_edge(2,1);
h = gt.Graph(directed=False)
h.add_vertex(4)
h.add_edge(0,0)
h.add_edge(1,1)
h.add_edge(0,3); h.add_edge(0,3);
h.add_edge(2,3);
h.add_edge(2,1);
h.add_edge(3,1);
print gt.topology.isomorphism(g,h)
This returns True
, when clearly the graphs are not isomorphic. Tested on version 2.2.31 (commit 245d1e2c, Thu Mar 27 11:28:39 2014 +0100)
. The adj matrices:
print graph_tool.spectral.adjacency(g).todense().astype(int)
print graph_tool.spectral.adjacency(h).todense().astype(int)
[[2 0 0 2]
[0 0 2 0]
[0 2 0 2]
[2 0 2 0]]
[[2 0 0 2]
[0 2 1 1]
[0 1 0 1]
[2 1 1 0]]