# 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.

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

## 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.

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