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


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)


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:

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:
