COIN-OR::LEMON - Graph Library

source: lemon-0.x/lemon/bipartite_matching.h @ 2048:b1a605b2f03c

Last change on this file since 2048:b1a605b2f03c was 2040:c7bd55c0d820, checked in by Balazs Dezso, 18 years ago

Bipartite Graph Max Cardinality Matching (Hopcroft-Karp)
Test for it

Some BpUgraph? improvments

File size: 14.0 KB
Line 
1/* -*- C++ -*-
2 *
3 * This file is a part of LEMON, a generic C++ optimization library
4 *
5 * Copyright (C) 2003-2006
6 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 *
9 * Permission to use, modify and distribute this software is granted
10 * provided that this copyright notice appears in all copies. For
11 * precise terms see the accompanying LICENSE file.
12 *
13 * This software is provided "AS IS" with no warranty of any kind,
14 * express or implied, and with no claim as to its suitability for any
15 * purpose.
16 *
17 */
18
19#ifndef LEMON_BIPARTITE_MATCHING
20#define LEMON_BIPARTITE_MATCHING
21
22#include <lemon/bpugraph_adaptor.h>
23#include <lemon/bfs.h>
24
25#include <iostream>
26
27///\ingroup matching
28///\file
29///\brief Maximum matching algorithms in bipartite graphs.
30
31namespace lemon {
32
33  /// \ingroup matching
34  ///
35  /// \brief Bipartite Max Cardinality Matching algorithm
36  ///
37  /// Bipartite Max Cardinality Matching algorithm. This class implements
38  /// the Hopcroft-Karp algorithm wich has \f$ O(e\sqrt{n}) \f$ time
39  /// complexity.
40  template <typename BpUGraph>
41  class MaxBipartiteMatching {
42  protected:
43
44    typedef BpUGraph Graph;
45
46    typedef typename Graph::Node Node;
47    typedef typename Graph::ANodeIt ANodeIt;
48    typedef typename Graph::BNodeIt BNodeIt;
49    typedef typename Graph::UEdge UEdge;
50    typedef typename Graph::UEdgeIt UEdgeIt;
51    typedef typename Graph::IncEdgeIt IncEdgeIt;
52
53    typedef typename BpUGraph::template ANodeMap<UEdge> ANodeMatchingMap;
54    typedef typename BpUGraph::template BNodeMap<UEdge> BNodeMatchingMap;
55
56
57  public:
58
59    /// \brief Constructor.
60    ///
61    /// Constructor of the algorithm.
62    MaxBipartiteMatching(const BpUGraph& _graph)
63      : anode_matching(_graph), bnode_matching(_graph), graph(&_graph) {}
64
65    /// \name Execution control
66    /// The simplest way to execute the algorithm is to use
67    /// one of the member functions called \c run().
68    /// \n
69    /// If you need more control on the execution,
70    /// first you must call \ref init() or one alternative for it.
71    /// Finally \ref start() will perform the matching computation or
72    /// with step-by-step execution you can augment the solution.
73
74    /// @{
75
76    /// \brief Initalize the data structures.
77    ///
78    /// It initalizes the data structures and creates an empty matching.
79    void init() {
80      for (ANodeIt it(*graph); it != INVALID; ++it) {
81        anode_matching[it] = INVALID;
82      }
83      for (BNodeIt it(*graph); it != INVALID; ++it) {
84        bnode_matching[it] = INVALID;
85      }
86      matching_value = 0;
87    }
88
89    /// \brief Initalize the data structures.
90    ///
91    /// It initalizes the data structures and creates a greedy
92    /// matching.  From this matching sometimes it is faster to get
93    /// the matching than from the initial empty matching.
94    void greedyInit() {
95      matching_value = 0;
96      for (BNodeIt it(*graph); it != INVALID; ++it) {
97        bnode_matching[it] = INVALID;
98      }
99      for (ANodeIt it(*graph); it != INVALID; ++it) {
100        anode_matching[it] = INVALID;
101        for (IncEdgeIt jt(*graph, it); jt != INVALID; ++jt) {
102          if (bnode_matching[graph->bNode(jt)] == INVALID) {
103            anode_matching[it] = jt;
104            bnode_matching[graph->bNode(jt)] = jt;
105            ++matching_value;
106            break;
107          }
108        }
109      }
110    }
111
112    /// \brief Initalize the data structures with an initial matching.
113    ///
114    /// It initalizes the data structures with an initial matching.
115    template <typename MatchingMap>
116    void matchingInit(const MatchingMap& matching) {
117      for (ANodeIt it(*graph); it != INVALID; ++it) {
118        anode_matching[it] = INVALID;
119      }
120      for (BNodeIt it(*graph); it != INVALID; ++it) {
121        bnode_matching[it] = INVALID;
122      }
123      matching_value = 0;
124      for (UEdgeIt it(*graph); it != INVALID; ++it) {
125        if (matching[it]) {
126          ++matching_value;
127          anode_matching[graph->aNode(it)] = it;
128          bnode_matching[graph->bNode(it)] = it;
129        }
130      }
131    }
132
133    /// \brief Initalize the data structures with an initial matching.
134    ///
135    /// It initalizes the data structures with an initial matching.
136    /// \return %True when the given map contains really a matching.
137    template <typename MatchingMap>
138    void checkedMatchingInit(const MatchingMap& matching) {
139      for (ANodeIt it(*graph); it != INVALID; ++it) {
140        anode_matching[it] = INVALID;
141      }
142      for (BNodeIt it(*graph); it != INVALID; ++it) {
143        bnode_matching[it] = INVALID;
144      }
145      matching_value = 0;
146      for (UEdgeIt it(*graph); it != INVALID; ++it) {
147        if (matching[it]) {
148          ++matching_value;
149          if (anode_matching[graph->aNode(it)] != INVALID) {
150            return false;
151          }
152          anode_matching[graph->aNode(it)] = it;
153          if (bnode_matching[graph->aNode(it)] != INVALID) {
154            return false;
155          }
156          bnode_matching[graph->bNode(it)] = it;
157        }
158      }
159      return false;
160    }
161
162    /// \brief An augmenting phase of the Hopcroft-Karp algorithm
163    ///
164    /// It runs an augmenting phase of the Hopcroft-Karp
165    /// algorithm. The phase finds maximum count of edge disjoint
166    /// augmenting paths and augments on these paths. The algorithm
167    /// consists at most of \f$ O(\sqrt{n}) \f$ phase and one phase is
168    /// \f$ O(e) \f$ long.
169    bool augment() {
170
171      typename Graph::template ANodeMap<bool> areached(*graph, false);
172      typename Graph::template BNodeMap<bool> breached(*graph, false);
173
174      typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);
175
176      std::vector<Node> queue, bqueue;
177      for (ANodeIt it(*graph); it != INVALID; ++it) {
178        if (anode_matching[it] == INVALID) {
179          queue.push_back(it);
180          areached[it] = true;
181        }
182      }
183
184      bool success = false;
185
186      while (!success && !queue.empty()) {
187        std::vector<Node> newqueue;
188        for (int i = 0; i < (int)queue.size(); ++i) {
189          Node anode = queue[i];
190          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
191            Node bnode = graph->bNode(jt);
192            if (breached[bnode]) continue;
193            breached[bnode] = true;
194            bpred[bnode] = jt;
195            if (bnode_matching[bnode] == INVALID) {
196              bqueue.push_back(bnode);
197              success = true;
198            } else {           
199              Node newanode = graph->aNode(bnode_matching[bnode]);
200              if (!areached[newanode]) {
201                areached[newanode] = true;
202                newqueue.push_back(newanode);
203              }
204            }
205          }
206        }
207        queue.swap(newqueue);
208      }
209
210      if (success) {
211
212        typename Graph::template ANodeMap<bool> aused(*graph, false);
213       
214        for (int i = 0; i < (int)bqueue.size(); ++i) {
215          Node bnode = bqueue[i];
216
217          bool used = false;
218
219          while (bnode != INVALID) {
220            UEdge uedge = bpred[bnode];
221            Node anode = graph->aNode(uedge);
222           
223            if (aused[anode]) {
224              used = true;
225              break;
226            }
227           
228            bnode = anode_matching[anode] != INVALID ?
229              graph->bNode(anode_matching[anode]) : INVALID;
230           
231          }
232         
233          if (used) continue;
234
235          bnode = bqueue[i];
236          while (bnode != INVALID) {
237            UEdge uedge = bpred[bnode];
238            Node anode = graph->aNode(uedge);
239           
240            bnode_matching[bnode] = uedge;
241
242            bnode = anode_matching[anode] != INVALID ?
243              graph->bNode(anode_matching[anode]) : INVALID;
244           
245            anode_matching[anode] = uedge;
246
247            aused[anode] = true;
248          }
249          ++matching_value;
250
251        }
252      }
253      return success;
254    }
255
256    /// \brief An augmenting phase of the Ford-Fulkerson algorithm
257    ///
258    /// It runs an augmenting phase of the Ford-Fulkerson
259    /// algorithm. The phase finds only one augmenting path and
260    /// augments only on this paths. The algorithm consists at most
261    /// of \f$ O(n) \f$ simple phase and one phase is at most
262    /// \f$ O(e) \f$ long.
263    bool simpleAugment() {
264
265      typename Graph::template ANodeMap<bool> areached(*graph, false);
266      typename Graph::template BNodeMap<bool> breached(*graph, false);
267
268      typename Graph::template BNodeMap<UEdge> bpred(*graph, INVALID);
269
270      std::vector<Node> queue;
271      for (ANodeIt it(*graph); it != INVALID; ++it) {
272        if (anode_matching[it] == INVALID) {
273          queue.push_back(it);
274          areached[it] = true;
275        }
276      }
277
278      while (!queue.empty()) {
279        std::vector<Node> newqueue;
280        for (int i = 0; i < (int)queue.size(); ++i) {
281          Node anode = queue[i];
282          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
283            Node bnode = graph->bNode(jt);
284            if (breached[bnode]) continue;
285            breached[bnode] = true;
286            bpred[bnode] = jt;
287            if (bnode_matching[bnode] == INVALID) {
288              while (bnode != INVALID) {
289                UEdge uedge = bpred[bnode];
290                anode = graph->aNode(uedge);
291               
292                bnode_matching[bnode] = uedge;
293               
294                bnode = anode_matching[anode] != INVALID ?
295                  graph->bNode(anode_matching[anode]) : INVALID;
296               
297                anode_matching[anode] = uedge;
298               
299              }
300              ++matching_value;
301              return true;
302            } else {           
303              Node newanode = graph->aNode(bnode_matching[bnode]);
304              if (!areached[newanode]) {
305                areached[newanode] = true;
306                newqueue.push_back(newanode);
307              }
308            }
309          }
310        }
311        queue.swap(newqueue);
312      }
313     
314      return false;
315    }
316
317    /// \brief Starts the algorithm.
318    ///
319    /// Starts the algorithm. It runs augmenting phases until the optimal
320    /// solution reached.
321    void start() {
322      while (augment()) {}
323    }
324
325    /// \brief Runs the algorithm.
326    ///
327    /// It just initalize the algorithm and then start it.
328    void run() {
329      init();
330      start();
331    }
332
333    /// @}
334
335    /// \name Query Functions
336    /// The result of the %Matching algorithm can be obtained using these
337    /// functions.\n
338    /// Before the use of these functions,
339    /// either run() or start() must be called.
340   
341    ///@{
342
343    /// \brief Returns an minimum covering of the nodes.
344    ///
345    /// The minimum covering set problem is the dual solution of the
346    /// maximum bipartite matching. It provides an solution for this
347    /// problem what is proof of the optimality of the matching.
348    /// \return The size of the cover set.
349    template <typename CoverMap>
350    int coverSet(CoverMap& covering) {
351
352      typename Graph::template ANodeMap<bool> areached(*graph, false);
353      typename Graph::template BNodeMap<bool> breached(*graph, false);
354     
355      std::vector<Node> queue;
356      for (ANodeIt it(*graph); it != INVALID; ++it) {
357        if (anode_matching[it] == INVALID) {
358          queue.push_back(it);
359        }
360      }
361
362      while (!queue.empty()) {
363        std::vector<Node> newqueue;
364        for (int i = 0; i < (int)queue.size(); ++i) {
365          Node anode = queue[i];
366          for (IncEdgeIt jt(*graph, anode); jt != INVALID; ++jt) {
367            Node bnode = graph->bNode(jt);
368            if (breached[bnode]) continue;
369            breached[bnode] = true;
370            if (bnode_matching[bnode] != INVALID) {
371              Node newanode = graph->aNode(bnode_matching[bnode]);
372              if (!areached[newanode]) {
373                areached[newanode] = true;
374                newqueue.push_back(newanode);
375              }
376            }
377          }
378        }
379        queue.swap(newqueue);
380      }
381
382      int size = 0;
383      for (ANodeIt it(*graph); it != INVALID; ++it) {
384        covering[it] = !areached[it] && anode_matching[it] != INVALID;
385        if (!areached[it] && anode_matching[it] != INVALID) {
386          ++size;
387        }
388      }
389      for (BNodeIt it(*graph); it != INVALID; ++it) {
390        covering[it] = breached[it];
391        if (breached[it]) {
392          ++size;
393        }
394      }
395      return size;
396    }
397
398    /// \brief Set true all matching uedge in the map.
399    ///
400    /// Set true all matching uedge in the map. It does not change the
401    /// value mapped to the other uedges.
402    /// \return The number of the matching edges.
403    template <typename MatchingMap>
404    int quickMatching(MatchingMap& matching) {
405      for (ANodeIt it(*graph); it != INVALID; ++it) {
406        if (anode_matching[it] != INVALID) {
407          matching[anode_matching[it]] = true;
408        }
409      }
410      return matching_value;
411    }
412
413    /// \brief Set true all matching uedge in the map and the others to false.
414    ///
415    /// Set true all matching uedge in the map and the others to false.
416    /// \return The number of the matching edges.
417    template <typename MatchingMap>
418    int matching(MatchingMap& matching) {
419      for (UEdgeIt it(*graph); it != INVALID; ++it) {
420        matching[it] = it == anode_matching[graph->aNode(it)];
421      }
422      return matching_value;
423    }
424
425
426    /// \brief Return true if the given uedge is in the matching.
427    ///
428    /// It returns true if the given uedge is in the matching.
429    bool matchingEdge(const UEdge& edge) {
430      return anode_matching[graph->aNode(edge)] == edge;
431    }
432
433    /// \brief Returns the matching edge from the node.
434    ///
435    /// Returns the matching edge from the node. If there is not such
436    /// edge it gives back \c INVALID.
437    UEdge matchingEdge(const Node& node) {
438      if (graph->aNode(node)) {
439        return anode_matching[node];
440      } else {
441        return bnode_matching[node];
442      }
443    }
444
445    /// \brief Gives back the number of the matching edges.
446    ///
447    /// Gives back the number of the matching edges.
448    int matchingValue() const {
449      return matching_value;
450    }
451
452    /// @}
453
454  private:
455
456    ANodeMatchingMap anode_matching;
457    BNodeMatchingMap bnode_matching;
458    const Graph *graph;
459
460    int matching_value;
461 
462  };
463
464}
465
466#endif
Note: See TracBrowser for help on using the repository browser.