Generated on Sat Feb 7 2015 02:01:25 for Gecode by doxygen 1.8.9.1
matching.hpp
Go to the documentation of this file.
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  * Last modified:
10  * $Date: 2009-09-08 21:10:29 +0200 (Tue, 08 Sep 2009) $ by $Author: schulte $
11  * $Revision: 9692 $
12  *
13  * This file is part of Gecode, the generic constraint
14  * development environment:
15  * http://www.gecode.org
16  *
17  * Permission is hereby granted, free of charge, to any person obtaining
18  * a copy of this software and associated documentation files (the
19  * "Software"), to deal in the Software without restriction, including
20  * without limitation the rights to use, copy, modify, merge, publish,
21  * distribute, sublicense, and/or sell copies of the Software, and to
22  * permit persons to whom the Software is furnished to do so, subject to
23  * the following conditions:
24  *
25  * The above copyright notice and this permission notice shall be
26  * included in all copies or substantial portions of the Software.
27  *
28  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
29  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
30  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
31  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
32  * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
33  * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
34  * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
35  *
36  */
37 
38 namespace Gecode { namespace Int { namespace Sorted {
39 
57  template<class View>
58  inline bool
60  int tau[], int phi[], OfflineMinItem sequence[], int vertices[]) {
61 
62  int xs = x.size();
63  OfflineMin seq(sequence, vertices, xs);
64  int s = 0;
65  seq.makeset();
66 
67  for (int z = 0; z < xs; z++) { // forall y nodes
68  int maxy = y[z].max();
69  // creating the sequence of inserts and extractions from the queue
70  for( ; s <xs && x[s].min() <= maxy; s++) {
71  seq[s].iset = z;
72  seq[z].rank++;
73  }
74  }
75 
76  // offline-min-procedure
77  for (int i = 0; i < xs; i++) {
78  // the upper bound of the x-node should be minimal
79  int perm = tau[i];
80  // find the iteration where \tau(i) became a maching candidate
81  int iter = seq[perm].iset;
82  if (iter<0)
83  return false;
84  int j = 0;
85  j = seq.find_pc(iter);
86  // check whether the sequence is valid
87  if (j >= xs)
88  return false;
89  // if there is no intersection between the matching candidate
90  // and the y node then there exists NO perfect matching
91  if (x[perm].max() < y[j].min())
92  return false;
93  phi[j] = perm;
94  seq[perm].iset = -5; //remove from candidate set
95  int sqjsucc = seq[j].succ;
96  if (sqjsucc < xs) {
97  seq.unite(j,sqjsucc,sqjsucc);
98  } else {
99  seq[seq[j].root].name = sqjsucc; // end of sequence achieved
100  }
101 
102  // adjust tree list
103  int pr = seq[j].pred;
104  if (pr != -1)
105  seq[pr].succ = sqjsucc;
106  if (sqjsucc != xs)
107  seq[sqjsucc].pred = pr;
108  }
109  return true;
110  }
111 
116  template<class View>
117  inline bool
119  int tau[], int phiprime[], OfflineMinItem sequence[],
120  int vertices[]) {
121 
122  int xs = x.size();
123  OfflineMin seq(sequence, vertices, xs);
124  int s = xs - 1;
125  seq.makeset();
126 
127  int miny = 0;
128  for (int z = xs; z--; ) { // forall y nodes
129  miny = y[z].min();
130  // creating the sequence of inserts and extractions from the queue
131  for ( ; s > -1 && x[tau[s]].max() >= miny; s--) {
132  seq[tau[s]].iset = z;
133  seq[z].rank++;
134  }
135  }
136 
137  // offline-min-procedure
138  for (int i = xs; i--; ) {
139  int perm = i;
140  int iter = seq[perm].iset;
141  if (iter < 0)
142  return false;
143  int j = 0;
144  j = seq.find_pc(iter);
145  if (j <= -1)
146  return false;
147  // if there is no intersection between the matching candidate
148  // and the y node then there exists NO perfect matching
149  if (x[perm].min() > y[j].max())
150  return false;
151  phiprime[j] = perm;
152  seq[perm].iset = -5;
153  int sqjsucc = seq[j].pred;
154  if (sqjsucc >= 0) {
155  seq.unite(j, sqjsucc, sqjsucc);
156  } else {
157  seq[seq[j].root].name = sqjsucc; // end of sequence achieved
158  }
159 
160  // adjust tree list
161  int pr = seq[j].succ;
162  if (pr != xs)
163  seq[pr].pred = sqjsucc;
164  if (sqjsucc != -1)
165  seq[sqjsucc].succ = pr;
166  }
167  return true;
168  }
169 
170 }}}
171 
172 // STATISTICS: int-prop
173 
bool glover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phi[], OfflineMinItem sequence[], int vertices[])
Glover's maximum matching in a bipartite graph.
Definition: matching.hpp:59
Bounds consistent sortedness propagator.
Definition: sorted.hh:63
void max(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:57
Item used to construct the OfflineMin sequence.
Definition: sortsup.hpp:121
bool revglover(ViewArray< View > &x, ViewArray< View > &y, int tau[], int phiprime[], OfflineMinItem sequence[], int vertices[])
Symmetric glover function for the upper domain bounds.
Definition: matching.hpp:118
void sequence(Home home, const IntVarArgs &x, const IntSet &s, int q, int l, int u, IntConLevel)
Post propagator for .
Definition: sequence.cpp:51
Gecode::IntArgs i(4, 1, 2, 3, 4)
View arrays.
Definition: array.hpp:234
void min(Home home, FloatVar x0, FloatVar x1, FloatVar x2)
Post propagator for .
Definition: arithmetic.cpp:75
Node * x
Pointer to corresponding Boolean expression node.
Definition: bool-expr.cpp:253
Offline-Min datastructure Used to compute the perfect matching between the unsorted views x and the s...
Definition: sortsup.hpp:150
void unite(int a, int b, int c)
Unite two sets a and b and label the union with c.
Definition: sortsup.hpp:215
int size(void) const
Return size of array (number of elements)
Definition: array.hpp:1215
Gecode toplevel namespace
void makeset(void)
Initialization of the datastructure.
Definition: sortsup.hpp:232