this repo has no description
dekker.one
1include "fzn_steiner.mzn";
2include "fzn_steiner_reif.mzn";
3include "fzn_dsteiner.mzn";
4include "fzn_dsteiner_reif.mzn";
5include "weighted_spanning_tree.mzn";
6
7/** @group globals.graph
8 Constrains the subgraph \a ns and \a es of a given directed graph to be a weighted spanning tree rooted at \a r of weight \a W.
9
10 \a N is the number of nodes in the given graph
11 \a E is the number of edges in the given graph
12 \a from is the leaving node 1..\a N for each edge
13 \a to is the entering node 1..\a N for each edge
14 \a w is the weight of each edge
15 \a r is the root node (which may be variable)
16 \a ns is a Boolean for each node whether it is in the subgraph
17 \a es is a Boolean for each edge whether it is in the subgraph
18 \a K is the weight of the tree
19*/
20predicate dsteiner(int: N, int: E, array[int] of int: from, array[int] of int: to, array[int] of int: w,
21 var int: r, array[int] of var bool: ns, array[int] of var bool: es, var int: K) =
22 assert(index_set(from) = 1..E,"dsteiner: index set of from must be 1..\(E)") /\
23 assert(index_set(to) = 1..E,"dsteiner: index set of to must be 1..\(E)") /\
24 assert(index_set(ns) = 1..N,"dsteiner: index set of ns must be 1..\(N)") /\
25 assert(index_set(es) = 1..E,"dsteiner: index set of es must be 1..\(E)") /\
26 assert(index_set(w) = 1..E,"dsteiner: index set of w must be 1..\(E)") /\
27 if forall(n in 1..N)(is_fixed(ns[n]) /\ fix(ns[n])) then
28 d_weighted_spanning_tree(N,E,from,to,w,r,es,K)
29 else
30 fzn_dsteiner(N,E,from,to,w,r,ns,es,K)
31 endif;
32
33/** @group globals.graph
34 Constrains the set of edges \a es of a given undirected graph to be a weighted spanning tree of weight \a W.
35
36 \a N is the number of nodes in the given graph
37 \a E is the number of edges in the given graph
38 \a from is the leaving node 1..\a N for each edge
39 \a to is the entering node 1..\a N for each edge
40 \a w is the weight of each edge
41 \a ns is a Boolean for each node whether it is in the subgraph
42 \a es is a Boolean for each edge whether it is in the subgraph
43 \a K is the weight of the tree
44**/
45predicate steiner(int: N, int: E, array[int] of int: from, array[int] of int: to, array[int] of int: w,
46 array[int] of var bool: ns, array[int] of var bool: es, var int: K) =
47 assert(index_set(from) = 1..E,"steiner: index set of from must be 1..\(E)") /\
48 assert(index_set(to) = 1..E,"steiner: index set of to must be 1..\(E)") /\
49 assert(index_set(ns) = 1..N,"steiner: index set of ns must be 1..\(N)") /\
50 assert(index_set(es) = 1..E,"steiner: index set of es must be 1..\(E)") /\
51 assert(index_set(w) = 1..E,"steiner: index set of w must be 1..\(E)") /\
52 if forall(n in 1..N)(is_fixed(ns[n]) /\ fix(ns[n])) then
53 weighted_spanning_tree(N,E,from,to,w,es,K)
54 else
55 fzn_steiner(N,E,from,to,w,ns,es,K)
56 endif;
57
58%-----------------------------------------------------------------------------%