Changeset 2040:c7bd55c0d820 in lemon-0.x for lemon/bpugraph_adaptor.h

Timestamp:

04/07/06 11:51:23 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2679

Message:

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

Some BpUgraph? improvments

File:

• lemon/bpugraph_adaptor.h (modified) (5 diffs)

lemon/bpugraph_adaptor.h

@@ -104 +104 @@
     Node target(const Edge& e) const { return graph->target(e); }
 
+    Node aNode(const UEdge& e) const { return graph->aNode(e); }
+    Node bNode(const UEdge& e) const { return graph->bNode(e); }
+
+    bool aNode(const Node& n) const { return graph->aNode(n); }
+    bool bNode(const Node& n) const { return graph->bNode(n); }
+
     typedef NodeNumTagIndicator<Graph> NodeNumTag;
     int nodeNum() const { return graph->nodeNum(); }
@@ -123 +129 @@
     }
   
-    Node addNode() const { return graph->addNode(); }
+    Node addANode() const { return graph->addANode(); }
+    Node addBNode() const { return graph->addBNode(); }
     UEdge addEdge(const Node& source, const Node& target) const { 
       return graph->addEdge(source, target); 
@@ -282 +289 @@
 
   /// \ingroup graph_adaptors
+  ///
+  /// \brief Trivial Bipartite Undirected Graph Adaptor
+  ///
+  /// Trivial Bipartite Undirected Graph Adaptor. It does not change
+  /// the functionality of the adapted graph.
   template <typename _BpUGraph>
   class BpUGraphAdaptor 
@@ -311 +323 @@
     typedef typename Parent::BNode ANode;
     typedef typename Parent::ANode BNode;
+    typedef typename Parent::Edge Edge;
+    typedef typename Parent::UEdge UEdge;
+
+    bool direction(const Edge& e) const { return !Parent::direction(e); }
+    Edge direct(const UEdge& e, bool b) const { return Parent::direct(e, !b); }
+
+    Node aNode(const UEdge& e) const { return Parent::bNode(e); }
+    Node bNode(const UEdge& e) const { return Parent::aNode(e); }
+
+    bool aNode(const Node& n) const { return Parent::bNode(n); }
+    bool bNode(const Node& n) const { return Parent::aNode(n); }
 
     void firstANode(Node& i) const { Parent::firstBNode(i); }
@@ -408 +431 @@
 
 
+  template <typename _BpUGraph, 
+            typename _ANMatchingMap, typename _BNMatchingMap>
+  class MatchingBpUGraphAdaptorBase 
+    : public BpUGraphAdaptorBase<const _BpUGraph>
+  {
+  public:
+    
+    typedef _BpUGraph Graph;
+    typedef _ANMatchingMap ANodeMatchingMap;
+    typedef _BNMatchingMap BNodeMatchingMap;
+
+    typedef BpUGraphAdaptorBase<const _BpUGraph> Parent;
+
+  protected:
+    
+    MatchingBpUGraphAdaptorBase() {}
+
+    void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) {
+      anode_matching = &_anode_matching;
+    }
+
+    void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) {
+      bnode_matching = &_bnode_matching;
+    }
+
+  public:
+
+    typedef typename Parent::Node Node;
+    typedef typename Parent::Edge Edge;
+
+    void firstOut(Edge& edge, const Node& node) const {
+      if (Parent::aNode(node)) {
+        Parent::firstOut(edge, node);
+        if (edge != INVALID && (*anode_matching)[node] == edge) {
+          Parent::nextOut(edge);
+        }
+      } else {
+        edge = (*bnode_matching)[node] != INVALID ?
+          Parent::direct((*bnode_matching)[node], false) : INVALID;
+      }
+    }
+
+    void nextOut(Edge& edge) const {
+      if (Parent::aNode(Parent::source(edge))) {
+        Parent::nextOut(edge);
+        if (edge != INVALID && (*anode_matching)[Parent::aNode(edge)] == edge) {
+          Parent::nextOut(edge);
+        }
+      } else {
+        edge = INVALID;
+      }
+    }
+ 
+    void firstIn(Edge& edge, const Node& node) const {
+      if (Parent::aNode(node)) {
+        edge = (*bnode_matching)[node] != INVALID ?
+          Parent::direct((*anode_matching)[node], false) : INVALID;
+      } else {
+        Parent::firstIn(edge, node);
+        if (edge != INVALID && (*bnode_matching)[node] == edge) {
+          Parent::nextIn(edge);
+        }
+      }
+    }
+
+    void nextIn(Edge& edge) const {
+      if (Parent::aNode(Parent::target(edge))) {
+        edge = INVALID;
+      } else {
+        Parent::nextIn(edge);
+        if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) {
+          Parent::nextIn(edge);
+        }
+      }
+    } 
+
+  private:
+    ANodeMatchingMap* anode_matching;
+    BNodeMatchingMap* bnode_matching;
+  };
+
+
+  /// \ingroup graph_adaptors
+  ///
+  /// \brief Bipartite graph adaptor to implement matching algorithms.
+  ///
+  /// Bipartite graph adaptor to implement matchings. It implements
+  /// the residual graph of the matching.
+  template <typename _BpUGraph, 
+            typename _ANMatchingMap, typename _BNMatchingMap>
+  class MatchingBpUGraphAdaptor 
+    : public BpUGraphAdaptorExtender<
+    MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> > 
+  { 
+  public:
+
+    typedef _BpUGraph BpUGraph;
+    typedef _BpUGraph Graph;
+    typedef _ANMatchingMap ANodeMatchingMap;
+    typedef _BNMatchingMap BNodeMatchingMap;
+    typedef BpUGraphAdaptorExtender<
+      MatchingBpUGraphAdaptorBase<BpUGraph, 
+                                  ANodeMatchingMap, BNodeMatchingMap> > 
+    Parent;
+
+  protected:
+    MatchingBpUGraphAdaptor() : Parent() {}
+
+  public:
+
+    MatchingBpUGraphAdaptor(const Graph& _graph, 
+                            ANodeMatchingMap& _anode_matching,
+                            BNodeMatchingMap& _bnode_matching) {
+      setGraph(_graph);
+      setANodeMatchingMap(_anode_matching);
+      setBNodeMatchingMap(_bnode_matching);
+    }
+
+  };
+
 }