this repo has no description
dekker.one
1/* -*- mode: C++; c-basic-offset: 2; indent-tabs-mode: nil -*- */
2/*
3 * Main authors:
4 * Patrick Pekczynski <pekczynski@ps.uni-sb.de>
5 *
6 * Copyright:
7 * Patrick Pekczynski, 2004
8 *
9 * This file is part of Gecode, the generic constraint
10 * development environment:
11 * http://www.gecode.org
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining
14 * a copy of this software and associated documentation files (the
15 * "Software"), to deal in the Software without restriction, including
16 * without limitation the rights to use, copy, modify, merge, publish,
17 * distribute, sublicense, and/or sell copies of the Software, and to
18 * permit persons to whom the Software is furnished to do so, subject to
19 * the following conditions:
20 *
21 * The above copyright notice and this permission notice shall be
22 * included in all copies or substantial portions of the Software.
23 *
24 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
25 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
26 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
27 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
28 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
29 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
30 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
31 *
32 */
33
34namespace Gecode { namespace Int { namespace Sorted {
35
36 /**
37 * \brief Glover's maximum matching in a bipartite graph
38 *
39 * Compute a matching in the bipartite convex intersection graph with
40 * one partition containing the x views and the other containing
41 * the y views. The algorithm works with an implicit array structure
42 * of the intersection graph.
43 *
44 * Union-Find Implementation of F.Glover's matching algorithm.
45 *
46 * The idea is to mimick a priority queue storing x-indices
47 * \f$[i_0,\dots, i_{n-1}]\f$, s.t. the upper domain bounds are sorted
48 * \f$D_{i_0} \leq\dots\leq D_{i_{n-1}}\f$ where \f$ D_{i_0}\f$
49 * is the top element
50 *
51 */
52
53 template<class View>
54 inline bool
55 glover(ViewArray<View>& x, ViewArray<View>& y,
56 int tau[], int phi[], OfflineMinItem sequence[], int vertices[]) {
57
58 int xs = x.size();
59 OfflineMin seq(sequence, vertices, xs);
60 int s = 0;
61 seq.makeset();
62
63 for (int z = 0; z < xs; z++) { // forall y nodes
64 int maxy = y[z].max();
65 // creating the sequence of inserts and extractions from the queue
66 for( ; s <xs && x[s].min() <= maxy; s++) {
67 seq[s].iset = z;
68 seq[z].rank++;
69 }
70 }
71
72 // offline-min-procedure
73 for (int i = 0; i < xs; i++) {
74 // the upper bound of the x-node should be minimal
75 int perm = tau[i];
76 // find the iteration where \tau(i) became a matching candidate
77 int iter = seq[perm].iset;
78 if (iter<0)
79 return false;
80 int j = 0;
81 j = seq.find_pc(iter);
82 // check whether the sequence is valid
83 if (j >= xs)
84 return false;
85 // if there is no intersection between the matching candidate
86 // and the y node then there exists NO perfect matching
87 if (x[perm].max() < y[j].min())
88 return false;
89 phi[j] = perm;
90 seq[perm].iset = -5; //remove from candidate set
91 int sqjsucc = seq[j].succ;
92 if (sqjsucc < xs) {
93 seq.unite(j,sqjsucc,sqjsucc);
94 } else {
95 seq[seq[j].root].name = sqjsucc; // end of sequence achieved
96 }
97
98 // adjust tree list
99 int pr = seq[j].pred;
100 if (pr != -1)
101 seq[pr].succ = sqjsucc;
102 if (sqjsucc != xs)
103 seq[sqjsucc].pred = pr;
104 }
105 return true;
106 }
107
108 /**
109 * \brief Symmetric glover function for the upper domain bounds
110 *
111 */
112 template<class View>
113 inline bool
114 revglover(ViewArray<View>& x, ViewArray<View>& y,
115 int tau[], int phiprime[], OfflineMinItem sequence[],
116 int vertices[]) {
117
118 int xs = x.size();
119 OfflineMin seq(sequence, vertices, xs);
120 int s = xs - 1;
121 seq.makeset();
122
123 int miny = 0;
124 for (int z = xs; z--; ) { // forall y nodes
125 miny = y[z].min();
126 // creating the sequence of inserts and extractions from the queue
127 for ( ; s > -1 && x[tau[s]].max() >= miny; s--) {
128 seq[tau[s]].iset = z;
129 seq[z].rank++;
130 }
131 }
132
133 // offline-min-procedure
134 for (int i = xs; i--; ) {
135 int perm = i;
136 int iter = seq[perm].iset;
137 if (iter < 0)
138 return false;
139 int j = 0;
140 j = seq.find_pc(iter);
141 if (j <= -1)
142 return false;
143 // if there is no intersection between the matching candidate
144 // and the y node then there exists NO perfect matching
145 if (x[perm].min() > y[j].max())
146 return false;
147 phiprime[j] = perm;
148 seq[perm].iset = -5;
149 int sqjsucc = seq[j].pred;
150 if (sqjsucc >= 0) {
151 seq.unite(j, sqjsucc, sqjsucc);
152 } else {
153 seq[seq[j].root].name = sqjsucc; // end of sequence achieved
154 }
155
156 // adjust tree list
157 int pr = seq[j].succ;
158 if (pr != xs)
159 seq[pr].pred = sqjsucc;
160 if (sqjsucc != -1)
161 seq[sqjsucc].succ = pr;
162 }
163 return true;
164 }
165
166}}}
167
168// STATISTICS: int-prop
169