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.
In this section: bounded_dpath, bounded_path, circuit, connected, d_weighted_spanning_tree, dag, dconnected, dpath, dreachable, dsteiner, dtree, network_flow, network_flow_cost, path, reachable, steiner, subcircuit, subgraph, tree, weighted_spanning_tree.
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)


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)


circuit¶
1. predicate circuit(array [$$E] of var $$E: x)
2. predicate circuit(array [$$E] of var opt $$E: x)


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:

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:

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:

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:

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)


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)


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:

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)


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:

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:

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)


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)


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:

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)


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)


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:
