Skip to content
GitLab
Projects Groups Topics Snippets
  • /
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
    • Contribute to GitLab
  • Register
  • Sign in
  • graph-tool graph-tool
  • Project information
    • Project information
    • Activity
    • Labels
    • Members
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributor statistics
    • Graph
    • Compare revisions
  • Issues 48
    • Issues 48
    • List
    • Boards
    • Service Desk
    • Milestones
  • Merge requests 0
    • Merge requests 0
  • CI/CD
    • CI/CD
    • Pipelines
    • Jobs
    • Schedules
  • Deployments
    • Deployments
    • Environments
    • Releases
  • Monitor
    • Monitor
    • Incidents
  • Analytics
    • Analytics
    • Value stream
    • CI/CD
    • Repository
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar

Please use the issue tracker only to report bugs (i.e. errors in the library that need to be fixed) or feature requests.

For questions about how to compile, install or use the library, please use instead the web forum at https://forum.skewed.de/c/graph-tool.


(If unsure, use the forum first.)


IMPORTANT: When opening new issues, please choose the BUG template from the drop-down menu, and fill out the required information.

  • Tiago Peixoto
  • graph-toolgraph-tool
  • Issues
  • #180
Closed
Open
Issue created Aug 20, 2014 by Travis Hoppe@travis.hoppe

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]]

broken

Assignee
Assign to
Time tracking