COIN-OR::LEMON - Graph Library

Changeset 2040:c7bd55c0d820 in lemon-0.x


Ignore:
Timestamp:
04/07/06 11:51:23 (14 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

Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed
  • lemon/Makefile.am

    r2038 r2040  
    3232        bin_heap.h \
    3333        bpugraph_adaptor.h \
     34        bipartite_matching.h \
     35        bucket_heap.h \
    3436        color.h \
    3537        config.h \
     
    5456        johnson.h \
    5557        kruskal.h \
    56         bucket_heap.h \
    5758        list_graph.h \
    5859        lp.h \
  • lemon/bpugraph_adaptor.h

    r2031 r2040  
    104104    Node target(const Edge& e) const { return graph->target(e); }
    105105
     106    Node aNode(const UEdge& e) const { return graph->aNode(e); }
     107    Node bNode(const UEdge& e) const { return graph->bNode(e); }
     108
     109    bool aNode(const Node& n) const { return graph->aNode(n); }
     110    bool bNode(const Node& n) const { return graph->bNode(n); }
     111
    106112    typedef NodeNumTagIndicator<Graph> NodeNumTag;
    107113    int nodeNum() const { return graph->nodeNum(); }
     
    123129    }
    124130 
    125     Node addNode() const { return graph->addNode(); }
     131    Node addANode() const { return graph->addANode(); }
     132    Node addBNode() const { return graph->addBNode(); }
    126133    UEdge addEdge(const Node& source, const Node& target) const {
    127134      return graph->addEdge(source, target);
     
    282289
    283290  /// \ingroup graph_adaptors
     291  ///
     292  /// \brief Trivial Bipartite Undirected Graph Adaptor
     293  ///
     294  /// Trivial Bipartite Undirected Graph Adaptor. It does not change
     295  /// the functionality of the adapted graph.
    284296  template <typename _BpUGraph>
    285297  class BpUGraphAdaptor
     
    311323    typedef typename Parent::BNode ANode;
    312324    typedef typename Parent::ANode BNode;
     325    typedef typename Parent::Edge Edge;
     326    typedef typename Parent::UEdge UEdge;
     327
     328    bool direction(const Edge& e) const { return !Parent::direction(e); }
     329    Edge direct(const UEdge& e, bool b) const { return Parent::direct(e, !b); }
     330
     331    Node aNode(const UEdge& e) const { return Parent::bNode(e); }
     332    Node bNode(const UEdge& e) const { return Parent::aNode(e); }
     333
     334    bool aNode(const Node& n) const { return Parent::bNode(n); }
     335    bool bNode(const Node& n) const { return Parent::aNode(n); }
    313336
    314337    void firstANode(Node& i) const { Parent::firstBNode(i); }
     
    408431
    409432
     433  template <typename _BpUGraph,
     434            typename _ANMatchingMap, typename _BNMatchingMap>
     435  class MatchingBpUGraphAdaptorBase
     436    : public BpUGraphAdaptorBase<const _BpUGraph>
     437  {
     438  public:
     439   
     440    typedef _BpUGraph Graph;
     441    typedef _ANMatchingMap ANodeMatchingMap;
     442    typedef _BNMatchingMap BNodeMatchingMap;
     443
     444    typedef BpUGraphAdaptorBase<const _BpUGraph> Parent;
     445
     446  protected:
     447   
     448    MatchingBpUGraphAdaptorBase() {}
     449
     450    void setANodeMatchingMap(ANodeMatchingMap& _anode_matching) {
     451      anode_matching = &_anode_matching;
     452    }
     453
     454    void setBNodeMatchingMap(BNodeMatchingMap& _bnode_matching) {
     455      bnode_matching = &_bnode_matching;
     456    }
     457
     458  public:
     459
     460    typedef typename Parent::Node Node;
     461    typedef typename Parent::Edge Edge;
     462
     463    void firstOut(Edge& edge, const Node& node) const {
     464      if (Parent::aNode(node)) {
     465        Parent::firstOut(edge, node);
     466        if (edge != INVALID && (*anode_matching)[node] == edge) {
     467          Parent::nextOut(edge);
     468        }
     469      } else {
     470        edge = (*bnode_matching)[node] != INVALID ?
     471          Parent::direct((*bnode_matching)[node], false) : INVALID;
     472      }
     473    }
     474
     475    void nextOut(Edge& edge) const {
     476      if (Parent::aNode(Parent::source(edge))) {
     477        Parent::nextOut(edge);
     478        if (edge != INVALID && (*anode_matching)[Parent::aNode(edge)] == edge) {
     479          Parent::nextOut(edge);
     480        }
     481      } else {
     482        edge = INVALID;
     483      }
     484    }
     485 
     486    void firstIn(Edge& edge, const Node& node) const {
     487      if (Parent::aNode(node)) {
     488        edge = (*bnode_matching)[node] != INVALID ?
     489          Parent::direct((*anode_matching)[node], false) : INVALID;
     490      } else {
     491        Parent::firstIn(edge, node);
     492        if (edge != INVALID && (*bnode_matching)[node] == edge) {
     493          Parent::nextIn(edge);
     494        }
     495      }
     496    }
     497
     498    void nextIn(Edge& edge) const {
     499      if (Parent::aNode(Parent::target(edge))) {
     500        edge = INVALID;
     501      } else {
     502        Parent::nextIn(edge);
     503        if (edge != INVALID && (*bnode_matching)[Parent::bNode(edge)] == edge) {
     504          Parent::nextIn(edge);
     505        }
     506      }
     507    }
     508
     509  private:
     510    ANodeMatchingMap* anode_matching;
     511    BNodeMatchingMap* bnode_matching;
     512  };
     513
     514
     515  /// \ingroup graph_adaptors
     516  ///
     517  /// \brief Bipartite graph adaptor to implement matching algorithms.
     518  ///
     519  /// Bipartite graph adaptor to implement matchings. It implements
     520  /// the residual graph of the matching.
     521  template <typename _BpUGraph,
     522            typename _ANMatchingMap, typename _BNMatchingMap>
     523  class MatchingBpUGraphAdaptor
     524    : public BpUGraphAdaptorExtender<
     525    MatchingBpUGraphAdaptorBase<_BpUGraph, _ANMatchingMap, _BNMatchingMap> >
     526  {
     527  public:
     528
     529    typedef _BpUGraph BpUGraph;
     530    typedef _BpUGraph Graph;
     531    typedef _ANMatchingMap ANodeMatchingMap;
     532    typedef _BNMatchingMap BNodeMatchingMap;
     533    typedef BpUGraphAdaptorExtender<
     534      MatchingBpUGraphAdaptorBase<BpUGraph,
     535                                  ANodeMatchingMap, BNodeMatchingMap> >
     536    Parent;
     537
     538  protected:
     539    MatchingBpUGraphAdaptor() : Parent() {}
     540
     541  public:
     542
     543    MatchingBpUGraphAdaptor(const Graph& _graph,
     544                            ANodeMatchingMap& _anode_matching,
     545                            BNodeMatchingMap& _bnode_matching) {
     546      setGraph(_graph);
     547      setANodeMatchingMap(_anode_matching);
     548      setBNodeMatchingMap(_bnode_matching);
     549    }
     550
     551  };
     552
    410553}
    411554
  • test/Makefile.am

    r2025 r2040  
    1616        arborescence_test \
    1717        bfs_test \
     18        bipartite_matching_test \
    1819        counter_test \
    1920        dfs_test \
     
    5657arborescence_test_SOURCES = arborescence_test.cc
    5758bfs_test_SOURCES = bfs_test.cc
     59bipartite_matching_test_SOURCES = bipartite_matching_test.cc
    5860counter_test_SOURCES = counter_test.cc
    5961dfs_test_SOURCES = dfs_test.cc
Note: See TracChangeset for help on using the changeset viewer.