# 4.2.2.11. Graph constraints

Many of these constraints operate on graphs that are represented as lists of edges. The constraints take a given (fixed) graph as arguments, which is represented using two arrays, `from` and `to`, representing the graph with edges `(from[i],to[i])`, where `from[i]` and `to[i]` are nodes of the graph.

## bounded_dpath

 ```1. predicate bounded_dpath(int: N, int: E, array [int] of int: from, array [int] of int: to, array [int] of int: w, var int: s, var int: t, array [int] of var bool: ns, array [int] of var bool: es, var int: K) 2. predicate bounded_dpath(array [int] of \$\$N: from, array [int] of \$\$N: to, array [int] of int: w, var \$\$N: s, var \$\$N: t, array [\$\$N] of var bool: ns, array [int] of var bool: es, var int: K) ``` Constrains the subgraph ns and es of a given directed graph to be a path from s to t of weight K. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge w: the weight of each edge s: the source node (which may be variable) t: the dest node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph K: the cost of the path Constrains the subgraph ns and es of a given directed graph to be a path from s to t of weight K. Parameters: from: the leaving node for each edge to: the entering node for each edge w: the weight of each edge s: the source node (which may be variable) t: the dest node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph K: the cost of the path

## bounded_path

 ```1. predicate bounded_path(int: N, int: E, array [int] of int: from, array [int] of int: to, array [int] of int: w, var int: s, var int: t, array [int] of var bool: ns, array [int] of var bool: es, var int: K) 2. predicate bounded_path(array [int] of \$\$N: from, array [int] of \$\$N: to, array [int] of int: w, var \$\$N: s, var \$\$N: t, array [\$\$N] of var bool: ns, array [int] of var bool: es, var int: K) ``` Constrains the subgraph ns and es of a given undirected graph to be a path from s to t of weight K. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge w: the weight of each edge s: the source node (which may be variable) t: the dest node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph K: the cost of the path Constrains the subgraph ns and es of a given undirected graph to be a path from s to t of weight K. Parameters: from: the leaving node for each edge to: the entering node for each edge w: the weight of each edge s: the source node (which may be variable) t: the dest node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph K: the cost of the path

## circuit

 ```1. predicate circuit(array [\$\$E] of var \$\$E: x) 2. predicate circuit(array [\$\$E] of var opt \$\$E: x) ``` Constrains the elements of x to define a circuit where x[i] = j means that j is the successor of i. Constrains the elements of x to define a circuit where x[i] = j means that j is the successor of i. Absent elements do not take part in the circuit.

## connected

 ```predicate connected(array [\$\$E] of \$\$N: from, array [\$\$E] of \$\$N: to, array [\$\$N] of var bool: ns, array [\$\$E] of var bool: es) ``` Constrains the subgraph ns and es of a given undirected graph to be connected. Parameters: from: is the leaving node for each edge to: is the entering node for each edge ns: is a Boolean for each node whether it is in the subgraph es: is a Boolean for each edge whether it is in the subgraph

## d_weighted_spanning_tree

 ```predicate d_weighted_spanning_tree(int: N, int: E, array [int] of int: from, array [int] of int: to, array [int] of int: w, var int: r, array [int] of var bool: es, var int: K) ``` Constrains the set of edges es of a given directed graph to be a weighted spanning tree rooted at r of weight W. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge w: the weight of each edge r: the root node (which may be variable) es: a Boolean for each edge whether it is in the subgraph K: the weight of the tree

## dag

 ```predicate dag(array [\$\$E] of \$\$N: from, array [\$\$E] of \$\$N: to, array [\$\$N] of var bool: ns, array [\$\$E] of var bool: es) ``` Constrains the subgraph ns and es of a given directed graph to be a DAG. Parameters: from: the leaving node for each edge to: the entering node for each edge ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph

## dconnected

 ```predicate dconnected(array [\$\$E] of \$\$N: from, array [\$\$E] of \$\$N: to, array [\$\$N] of var bool: ns, array [\$\$E] of var bool: es) ``` Constrains the subgraph ns and es of a given directed graph to be connected. Parameters: from: the leaving node for each edge to: the entering node for each edge ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph

## dpath

 ```1. predicate dpath(int: N, int: E, array [int] of int: from, array [int] of int: to, var int: s, var int: t, array [int] of var bool: ns, array [int] of var bool: es) 2. predicate dpath(array [int] of \$\$N: from, array [int] of \$\$N: to, var \$\$N: s, var \$\$N: t, array [\$\$N] of var bool: ns, array [int] of var bool: es) ``` Constrains the subgraph ns and es of a given directed graph to be a path from s to t. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge s: the source node (which may be variable) t: the dest node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph Constrains the subgraph ns and es of a given directed graph to be a path from s to t. Parameters: from: the leaving node for each edge to: the entering node for each edge s: the source node (which may be variable) t: the dest node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph

## dreachable

 ```1. predicate dreachable(int: N, int: E, array [int] of int: from, array [int] of int: to, var int: r, array [int] of var bool: ns, array [int] of var bool: es) 2. predicate dreachable(array [int] of \$\$N: from, array [int] of \$\$N: to, var \$\$N: r, array [\$\$N] of var bool: ns, array [int] of var bool: es) ``` Constrains the subgraph ns and es of a given directed graph to be reachable from r. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge r: the root node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph Constrains the subgraph ns and es of a given directed graph to be reachable from r. Parameters: from: the leaving node for each edge to: the entering node for each edge r: the root node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph

## dsteiner

 ```predicate dsteiner(int: N, int: E, array [int] of int: from, array [int] of int: to, array [int] of int: w, var int: r, array [int] of var bool: ns, array [int] of var bool: es, var int: K) ``` Constrains the subgraph ns and es of a given directed graph to be a weighted spanning tree rooted at r of weight W. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge w: the weight of each edge r: the root node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph K: the weight of the tree

## dtree

 ```1. predicate dtree(int: N, int: E, array [int] of int: from, array [int] of int: to, var int: r, array [int] of var bool: ns, array [int] of var bool: es) 2. predicate dtree(array [\$\$E] of \$\$N: from, array [\$\$E] of \$\$N: to, var \$\$N: r, array [\$\$N] of var bool: ns, array [\$\$E] of var bool: es) ``` Constrains the subgraph ns and es of a given directed graph to be a tree rooted at r. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge r: the root node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph Constrains the subgraph ns and es of a given directed graph to be at tree rooted at r. Parameters: from: the leaving node for each edge to: the entering node for each edge r: the root node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph

## network_flow

 ```predicate network_flow(array [int,1..2] of int: arc, array [int] of int: balance, array [int] of var int: flow) ``` Defines a network flow constraint. Parameters: arc: a directed arc of the flow network. Arc i connects node arc[i,1] to node arc[i,2]. balance: the difference between input and output flow for each node. flow: the flow going through each arc.

## network_flow_cost

 ```predicate network_flow_cost(array [int,1..2] of int: arc, array [int] of int: balance, array [int] of int: weight, array [int] of var int: flow, var int: cost) ``` Defines a network flow constraint with cost. Parameters: arc: a directed arc of the flow network. Arc i connects node arc[i,1] to node arc[i,2]. balance: the difference between input and output flow for each node. weight: the unit cost of the flow through the arc. flow: the flow going through each arc. cost: the overall cost of the flow.

## path

 ```1. predicate path(int: N, int: E, array [int] of int: from, array [int] of int: to, var int: s, var int: t, array [int] of var bool: ns, array [int] of var bool: es) 2. predicate path(array [int] of \$\$N: from, array [int] of \$\$N: to, var \$\$N: s, var \$\$N: t, array [\$\$N] of var bool: ns, array [int] of var bool: es) ``` Constrains the subgraph ns and es of a given undirected graph to be a path from s to t. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge s: the source node (which may be variable) t: the dest node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph Constrains the subgraph ns and es of a given undirected graph to be a path from s to t. Parameters: from: the leaving node for each edge to: the entering node for each edge s: the source node (which may be variable) t: the dest node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph

## reachable

 ```1. predicate reachable(int: N, int: E, array [int] of int: from, array [int] of int: to, var int: r, array [int] of var bool: ns, array [int] of var bool: es) 2. predicate reachable(array [int] of \$\$N: from, array [int] of \$\$N: to, var \$\$N: r, array [\$\$N] of var bool: ns, array [int] of var bool: es) ``` Constrains the subgraph ns and es of a given undirected graph to be reachable from r. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge r: the root node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph Constrains the subgraph ns and es of a given undirected graph to be reachable from r. Parameters: from: the leaving node for each edge to: the entering node for each edge r: the root node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph

## steiner

 ```predicate steiner(int: N, int: E, array [int] of int: from, array [int] of int: to, array [int] of int: w, array [int] of var bool: ns, array [int] of var bool: es, var int: K) ``` Constrains the set of edges es of a given undirected graph to be a weighted spanning tree of weight W. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge w: the weight of each edge ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph K: the weight of the tree

## subcircuit

 ```predicate subcircuit(array [\$\$E] of var \$\$E: x) ``` Constrains the elements of x to define a subcircuit where x[i] = j means that j is the successor of i and x[i] = i means that i is not in the circuit.

## subgraph

 ```1. predicate subgraph(int: N, int: E, array [int] of int: from, array [int] of int: to, array [int] of var bool: ns, array [int] of var bool: es) 2. predicate subgraph(array [\$\$E] of \$\$N: from, array [\$\$E] of \$\$N: to, array [\$\$N] of var bool: ns, array [\$\$E] of var bool: es) ``` Constrains that ns and es is a subgraph of a given directed graph. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph Constrains that ns and es is a subgraph of a given directed graph. Parameters: from: the leaving node for each edge to: the entering node for each edge ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph

## tree

 ```1. predicate tree(int: N, int: E, array [int] of int: from, array [int] of int: to, var int: r, array [int] of var bool: ns, array [int] of var bool: es) 2. predicate tree(array [\$\$E] of \$\$N: from, array [\$\$E] of \$\$N: to, var \$\$N: r, array [\$\$N] of var bool: ns, array [\$\$E] of var bool: es) ``` Constrains the subgraph ns and es of a given undirected graph to be a tree rooted at r. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge r: the root node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph Constrains the subgraph ns and es of a given undirected graph to be at tree rooted at r. Parameters: from: the leaving node for each edge to: the entering node for each edge r: the root node (which may be variable) ns: a Boolean for each node whether it is in the subgraph es: a Boolean for each edge whether it is in the subgraph

## weighted_spanning_tree

 ```predicate weighted_spanning_tree(int: N, int: E, array [int] of int: from, array [int] of int: to, array [int] of int: w, array [int] of var bool: es, var int: K) ``` Constrains the set of edges es of a given undirected graph to be a weighted spanning tree of weight W. Parameters: N: the number of nodes in the given graph E: the number of edges in the given graph from: the leaving node 1..N for each edge to: the entering node 1..N for each edge w: the weight of each edge es: a Boolean for each edge whether it is in the subgraph K: the weight of the tree