This repository is the official implementation of the paper “Beyond adjacency: Graph encoding with reachability and shortest paths”. Please cite as:

• Shiqiang Zhang, Ruth Misener. "Beyond adjacency: Graph encoding with reachability and shortest paths." arXiv preprint arXiv:2509.20247 (2025).

The BibTex reference is:

 @article{zhang2025beyond,
      title = {Beyond adjacency: Graph encoding with reachability and shortest paths},
      author= {Shiqiang Zhang and Ruth Misener},
      journal = {arXiv preprint arXiv:2509.20247},
      year = {2025},
 }

Requirements

This repository relies on Gurobi to formulate the graph spaces using integer pragramming. A license is needed to use Gurobi. Please follow the instructions to obtain a free academic license.

Documentation

Please see our paper for technical details. See graph_encoding.py for our implementation of both the general graph encoding and its simplified version. See symmetry_breaking.py for three types of lexicographic constraints. All experiments in our paper could be duplicated using main.py.

Graph encoding

One only needs one command to encode the graph space, and one more command to support weak connectivity.

To encode connected, undirected graphs with N nodes, run this command:

general_encoding(model, N, directed=False, connected=True)

To encode weakly connected DAGs with N nodes, run this command:

general_encoding(model, N, directed=True, acyclicity=True)
simplified_encoding(model, N, directed=False, graph_space="underlying")

Symmetry breaking

To break symmetry over connected, undirected graphs with N nodes, run this command:

symmetry_breaking(model, N)

To break symmetry over weakly connected DAGs, run this command:

symmetry_breaking(model, N, directed=True, acyclicity=True)

Example

We provide the following example for illustration purposes, where we count the number of feasible solutions for connected, undirected graphs with 6 nodes after breaking symmetry. The result should be 262.

import gurobipy as gp
from graph_encoding import general_encoding, simplified_encoding
from symmetry_breaking import symmetry_breaking

# maximal number of nodes
N = 6
# build a Gurobi model
model = gp.Model()

# general graph encoding
general_encoding(model, N, directed=False, connected=True)
# symmetry breaking
symmetry_breaking(model, N)

# set search mode to find all feasible solutions
model.Params.PoolSearchMode = 2
# pool of solutions
model.Params.PoolSolutions = 100000000
# time limit
model.Params.TimeLimit = 36000
# solve the model
model.optimize()
# number of feasible solutions
print(model.SolCount)

Contributors

Shiqiang Zhang. Funded by BASF SE, Ludwigshafen am Rhein.