The Graph Isomorphism problem asks whether two given graphs are isomorphic, that is, if a bijection (one-to-one mapping) of vertices between the graphs exists such that the adjacency structure is preserved.
You can run this example without installation in cloud-based IDEs that support the Development Containers specification (aka "devcontainers").
For development environments that do not support devcontainers, install
requirements:
pip install -r requirements.txt
If you are cloning the repo to your local system, working in a virtual environment is recommended.
Your development environment should be configured to access Leap’s Solvers. You can see information about supported IDEs and authorizing access to your Leap account here.
To run this demo locally, open up Jupyter Lab with a terminal. Run this command:
jupyter lab
In Jupyter Lab, you can open the notebook by clicking on the
Graph_Isomorphism_Lecture.ipynb file in VS Code-based IDEs.
The notebook provided covers encoding the objective and constraints of the Graph Isomorphism problem with our open source D-Wave Ocean tools.
Wiki page on Graph Isomorphism.
Circuit Equivalence example in dwave-examples.
Released under the Apache License 2.0. See license here.