COIN-OR::LEMON - Graph Library

Changeset 368:0beed7a49063 in lemon-0.x


Ignore:
Timestamp:
04/21/04 22:48:00 (16 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@496
Message:

experimental bipartite graph wrapper

Location:
src/work
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/list_graph.h

    r354 r368  
    540540
    541541  class UndirListGraph : public ListGraph {
     542  public:
    542543    typedef SymEdgeIt OutEdgeIt;
    543544    typedef SymEdgeIt InEdgeIt;
  • src/work/marci/graph_wrapper.h

    r363 r368  
    44
    55#include <invalid.h>
     6#include <iter_map.h>
    67
    78namespace hugo {
     
    863864      this->next(f);
    864865      first_out_edges->set(this->tail(e), f.e);
     866    }
     867  };
     868
     869  /// A wrapper for composing a bipartite graph.
     870  /// \c _graph have to be a reference to an undirected graph \c Graph
     871  /// and
     872  /// \c _s_false_t_true_map is an \c IterableBoolMap
     873  /// reference containing the elements for the
     874  /// color classes S and T.
     875  /// It results in a directed graph such that the edges are oriented from
     876  /// S to T.
     877  template<typename Graph>
     878  class BipartiteGraphWrapper : public GraphWrapper<Graph> {
     879    typedef IterableBoolMap< typename Graph::NodeMap<int> > SFalseTTrueMap;
     880    SFalseTTrueMap* s_false_t_true_map;
     881   
     882  public:
     883    BipartiteGraphWrapper(Graph& _graph, SFalseTTrueMap& _s_false_t_true_map)
     884      : GraphWrapper<Graph>(_graph), s_false_t_true_map(&_s_false_t_true_map) {
     885    }
     886    typedef typename GraphWrapper<Graph>::Node Node;
     887    //using GraphWrapper<Graph>::NodeIt;
     888    typedef typename GraphWrapper<Graph>::Edge Edge;
     889    //using GraphWrapper<Graph>::EdgeIt;
     890    class SNodeIt {
     891      Node n;
     892    public:
     893      SNodeIt() { }
     894      SNodeIt(const Invalid& i) : n(i) { }
     895      SNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
     896        _G.s_false_t_true_map->first(n, false);
     897      }
     898      operator Node() const { return n; }
     899    };
     900    class TNodeIt {
     901      Node n;
     902    public:
     903      TNodeIt() { }
     904      TNodeIt(const Invalid& i) : n(i) { }
     905      TNodeIt(const BipartiteGraphWrapper<Graph>& _G) {
     906        _G.s_false_t_true_map->first(n, true);
     907      }
     908      operator Node() const { return n; }
     909    };
     910    class OutEdgeIt {
     911    public:
     912      typename Graph::OutEdgeIt e;
     913    public:
     914      OutEdgeIt() { }
     915      OutEdgeIt(const Invalid& i) : e(i) { }
     916      OutEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
     917        if (!(*(_G.s_false_t_true_map))[_n])
     918          e=OutEdgeIt(*(_G.graph), typename Graph::Node(_n));
     919        else
     920          e=INVALID;
     921      }
     922      operator Edge() const { return Edge(typename Graph::Edge(e)); }
     923    };
     924    class InEdgeIt {
     925    public:
     926      typename Graph::InEdgeIt e;
     927    public:
     928      InEdgeIt() { }
     929      InEdgeIt(const Invalid& i) : e(i) { }
     930      InEdgeIt(const BipartiteGraphWrapper<Graph>& _G, const Node& _n) {
     931        if ((*(_G.s_false_t_true_map))[_n])
     932          e=InEdgeIt(*(_G.graph), typename Graph::Node(_n));
     933        else
     934          e=INVALID;
     935      }
     936      operator Edge() const { return Edge(typename Graph::Edge(e)); }
     937    };
     938
     939    using GraphWrapper<Graph>::first;
     940    SNodeIt& first(SNodeIt& n) const { n=SNodeIt(*this); return n; }
     941    TNodeIt& first(TNodeIt& n) const { n=TNodeIt(*this); return n; }
     942
     943    using GraphWrapper<Graph>::next;
     944    SNodeIt& next(SNodeIt& n) const {
     945      this->s_false_t_true_map->next(n); return n;
     946    }
     947    TNodeIt& next(TNodeIt& n) const {
     948      this->s_false_t_true_map->next(n); return n;
     949    }
     950
     951    Node tail(const Edge& e) {
     952      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
     953        return Node(this->graph->tail(e));
     954      else
     955        return Node(this->graph->head(e));     
     956    }
     957    Node head(const Edge& e) {
     958      if (!(*(this->s_false_t_true_map))[this->graph->tail(e)])
     959        return Node(this->graph->head(e));
     960      else
     961        return Node(this->graph->tail(e));     
     962    }
     963
     964    Node aNode(const OutEdgeIt& e) const {
     965      return Node(this->graph->aNode(e.e));
     966    }
     967    Node aNode(const InEdgeIt& e) const {
     968      return Node(this->graph->aNode(e.e));
     969    }
     970    Node bNode(const OutEdgeIt& e) const {
     971      return Node(this->graph->bNode(e.e));
     972    }
     973    Node bNode(const InEdgeIt& e) const {
     974      return Node(this->graph->bNode(e.e));
    865975    }
    866976  };
  • src/work/marci/makefile

    r358 r368  
    1 #CXX3 = g++-3.0
    21CXX2 = g++-2.95
    3 #CXX3.3 = g++
    42CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
    53CXX=$(CXX3)
    64CC=$(CXX)
    7 #CXXFLAGS = -W -Wall -ansi -pedantic -I. -I.. -I../alpar
    85#LEDAROOT ?= /ledasrc/LEDA-4.1
    96BOOSTROOT ?= /home/marci/boost
     
    1310
    1411LEDABINARIES = leda_graph_demo leda_bfs_dfs max_bipartite_matching_demo
    15 BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand
     12BINARIES = edmonds_karp_demo iterator_bfs_demo macro_test lg_vs_sg bfsit_vs_byhand bipartite_graph_wrapper_test
    1613#gw_vs_not preflow_demo_boost edmonds_karp_demo_boost preflow_demo_jacint preflow_demo_athos edmonds_karp_demo_alpar preflow_demo_leda
    1714
Note: See TracChangeset for help on using the changeset viewer.