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 [$$E,1..2] of $$N: arc,
array [$$N] of int: balance,
array [$$E] of var int: flow)
|
Defines a network flow constraint. Parameters:
|
network_flow_cost
predicate network_flow_cost(array [$$E,1..2] of $$N: arc,
array [$$N] of int: balance,
array [$$E] of int: weight,
array [$$E] 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:
|