# 4.2.2.8. Graph constraints¶

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.

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

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