Constraints over graph variables

Overview of constraints on graph variables.

Graph variables represent directed or undirected graphs. They are useful for modeling problems involving networks, routes, connectivity, and structural properties. This section presents the main graph constraints available in Choco-solver.

Creating Graph Variables

Graph variables have a lower bound (kernel) and an upper bound (envelope) representing the minimum and maximum edges that must or can be included:

// Create an undirected graph on 5 nodes
UndirectedGraph lb = new UndirectedGraph(5);
UndirectedGraph ub = new UndirectedGraph(5);
ub.addEdges(new int[][]{
    {0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 0}  // forms a complete edge set
});
GraphVar gv = model.undirectedGraphVar("graph", lb, ub);

// Create a directed graph
DirectedGraph dlb = new DirectedGraph(5);
DirectedGraph dub = new DirectedGraph(5);
dub.addEdges(new int[][]{{0, 1}, {1, 2}, {2, 3}, {3, 4}});
GraphVar dv = model.directedGraphVar("digraph", dlb, dub);

Node and Edge Counting

Node count

The nbNodes constraint relates the number of nodes to an integer variable:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
IntVar nbN = model.intVar("nbN", 1, 5);
model.nbNodes(g, nbN).post();

The nodeInducedGraphVar and nodeInducedDigraphVar create node-induced subgraphs (where edges exist only between selected nodes):

GraphVar fullGraph = model.undirectedGraphVar("full", lb, ub);
GraphVar subgraph = model.nodeInducedGraphVar("sub", nlb, nub);
// subgraph will be the node-induced subgraph of fullGraph

Edge count

The nbEdges constraint counts the number of edges:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
IntVar nbE = model.intVar("nbE", 0, 10);
model.nbEdges(g, nbE).post();

The nbLoops constraint counts self-loops (edges from a node to itself):

GraphVar g = model.directedGraphVar("g", lb, ub);
IntVar nbL = model.intVar("nbL", 0, 5);
model.nbLoops(g, nbL).post();

Loop set constraint

The loopSet constraint retrieves the set of nodes with self-loops:

GraphVar g = model.directedGraphVar("g", lb, ub);
SetVar loops = model.setVar("loops", new int[]{}, new int[]{0, 1, 2, 3, 4});
model.loopSet(g, loops).post();

Structural Constraints

Symmetry and antisymmetry

The symmetric constraint ensures that if edge $(i,j)$ exists, then edge $(j,i)$ also exists (making a directed graph undirected in structure):

GraphVar g = model.directedGraphVar("g", lb, ub);
model.symmetric(g).post();

The antisymmetric constraint ensures no edge exists in both directions:

GraphVar g = model.directedGraphVar("g", lb, ub);
model.antisymmetric(g).post();

Transitivity

The transitivity constraint ensures that if $(i,j)$ and $(j,k)$ exist, then $(i,k)$ must exist:

GraphVar g = model.directedGraphVar("g", lb, ub);
model.transitivity(g).post();

Subgraph constraint

The subgraph constraint ensures one graph is a subgraph of another (all edges in the first are in the second):

GraphVar g1 = model.undirectedGraphVar("g1", lb1, ub1);
GraphVar g2 = model.undirectedGraphVar("g2", lb2, ub2);
model.subgraph(g1, g2).post();  // g1 ⊆ g2

Channeling Constraints

Nodes channeling

The nodesChanneling constraint links nodes to a set variable:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
SetVar nodes = model.setVar("nodes", new int[]{}, new int[]{0, 1, 2, 3, 4});
model.nodesChanneling(g, nodes).post();

The nodeChanneling constraint links a specific node to an integer variable:

GraphVar g = model.directedGraphVar("g", lb, ub);
IntVar n = model.intVar("node", 0, 4);
model.nodeChanneling(g, 2, n).post();  // relates node 2 to variable n

Edge channeling

The edgeChanneling constraint relates edges to boolean variables:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
BoolVar[][] edges = new BoolVar[5][5];
// edge[i][j] is true iff edge (i,j) exists in g
model.edgeChanneling(g, edges).post();

Neighbors/Successors/Predecessors channeling

The neighborsChanneling constraint links each node to its set of neighbors:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
SetVar[] neighbors = model.setVarArray("neighbors", 5, new int[]{}, new int[]{0, 1, 2, 3, 4});
model.neighborsChanneling(g, neighbors).post();  // neighbors[i] = neighbors of node i

The successorsChanneling and predecessorsChanneling constraints apply to directed graphs:

GraphVar g = model.directedGraphVar("g", lb, ub);
SetVar[] successors = model.setVarArray("succ", 5, new int[]{}, new int[]{0, 1, 2, 3, 4});
model.successorsChanneling(g, successors).post();  // successors[i] = nodes reachable from i

Degree Constraints

Minimum and maximum degree

The minDegree and maxDegree constraints set bounds on node degrees:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
model.minDegree(g, 2).post();  // all nodes must have degree ≥ 2
model.maxDegree(g, 4).post();  // all nodes must have degree ≤ 4

The degrees constraint links each node to an integer variable representing its degree:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
IntVar[] degrees = model.intVarArray("deg", 5, 0, 4);
model.degrees(g, degrees).post();  // degrees[i] = degree of node i

In-degree and out-degree (directed graphs)

For directed graphs:

GraphVar g = model.directedGraphVar("g", lb, ub);
IntVar[] inDegrees = model.intVarArray("inDeg", 5, 0, 4);
IntVar[] outDegrees = model.intVarArray("outDeg", 5, 0, 4);
model.inDegrees(g, inDegrees).post();      // in-degree constraints
model.outDegrees(g, outDegrees).post();    // out-degree constraints
model.minInDegree(g, 1).post();            // all nodes must have in-degree ≥ 1
model.maxOutDegree(g, 3).post();           // all nodes must have out-degree ≤ 3

Connectivity Constraints

Connected components

The nbConnectedComponents constraint counts the number of connected components:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
IntVar nbCC = model.intVar("nbCC", 1, 5);
model.nbConnectedComponents(g, nbCC).post();

The sizeConnectedComponents constraint retrieves the size of each connected component:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
SetVar[] ccSizes = model.setVarArray("ccSize", 5, new int[]{}, new int[]{0, 1, 2, 3, 4});
model.sizeConnectedComponents(g, ccSizes).post();

Full connectivity

The connected constraint ensures the graph is fully connected:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
model.connected(g).post();  // graph must be connected

The biconnected constraint ensures the graph is biconnected (no cut vertices):

GraphVar g = model.undirectedGraphVar("g", lb, ub);
model.biconnected(g).post();

Directed connectivity

The stronglyConnected constraint ensures all nodes are mutually reachable:

GraphVar g = model.directedGraphVar("g", lb, ub);
model.stronglyConnected(g).post();

The nbStronglyConnectedComponents counts strongly connected components:

GraphVar g = model.directedGraphVar("g", lb, ub);
IntVar nbSCC = model.intVar("nbSCC", 1, 5);
model.nbStronglyConnectedComponents(g, nbSCC).post();

Reachability

The reachability constraint ensures that every node is reachable from a source node:

GraphVar g = model.directedGraphVar("g", lb, ub);
model.reachability(g, 0).post();  // all nodes must be reachable from node 0

Cycles and Paths

Acyclic constraints

The noCycle constraint ensures the graph is acyclic:

GraphVar g = model.directedGraphVar("g", lb, ub);
model.noCycle(g).post();

The noCircuit constraint (undirected) ensures no cycles exist:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
model.noCircuit(g).post();

Cycle existence

The cycle constraint forces a Hamiltonian cycle (a cycle visiting each node exactly once):

GraphVar g = model.directedGraphVar("g", lb, ub);
model.cycle(g).post();

Tree Constraints

Tree and forest

The tree constraint ensures the graph is a tree (connected, acyclic, with n-1 edges for n nodes):

GraphVar g = model.undirectedGraphVar("g", lb, ub);
model.tree(g).post();

The forest constraint ensures the graph is a forest (acyclic, can have multiple connected components):

GraphVar g = model.undirectedGraphVar("g", lb, ub);
model.forest(g).post();

Directed trees and forests

For directed graphs:

GraphVar g = model.directedGraphVar("g", lb, ub);
model.directedTree(g).post();   // a directed tree rooted at node 0
model.directedForest(g).post();  // a directed forest

Advanced Structural Constraints

Cliques

The nbCliques constraint counts the number of maximal cliques:

GraphVar g = model.undirectedGraphVar("g", lb, ub);
IntVar nbC = model.intVar("nbCliques", 0, 5);
model.nbCliques(g, nbC).post();

Diameter

The diameter constraint limits the graph diameter (maximum shortest path between any two nodes):

GraphVar g = model.undirectedGraphVar("g", lb, ub);
model.diameter(g, 3).post();  // maximum diameter is 3

Optimization Constraints

Traveling Salesman Problem (TSP)

The tsp constraint models the Traveling Salesman Problem with edge weights:

GraphVar g = model.directedGraphVar("g", lb, ub);
int[][] distances = {{0, 10, 15}, {10, 0, 35}, {15, 35, 0}};
IntVar cost = model.intVar("tspCost", 0, 1000);
model.tsp(g, distances, cost).post();

Directed Cost Minimum Spanning Tree (DCMST)

The dcmst constraint models a minimum spanning tree for directed graphs:

GraphVar g = model.directedGraphVar("g", lb, ub);
int[][] costs = {{0, 5, 10}, {5, 0, 15}, {10, 15, 0}};
IntVar cost = model.intVar("dcmstCost", 0, 1000);
model.dcmst(g, costs, cost).post();

Views on Graph Variables

Graph variables support several views for working with their components:

GraphVar g = model.undirectedGraphVar("g", lb, ub);

// Get the set of all nodes
SetVar nodes = model.graphNodeSetView(g);

// Get the set of successors for a specific node (directed graphs)
SetVar succ = model.graphSuccessorsSetView((DirectedGraphVar) g, 2);

// Get subgraph induced by a set of nodes
SetVar nodeSet = model.setVar("nodes", new int[]{}, new int[]{0, 1, 2, 3, 4});
GraphVar subgraph = model.nodeInducedSubgraphView(g, nodeSet, false);

Last modified May 8, 2026: Update website (924b883)