COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 155:8c6292ec54c6 in lemon-0.x for src/work/marci


Ignore:
Timestamp:
03/04/04 20:38:07 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@217
Message:

graph wrappers

Location:
src/work/marci
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • src/work/marci/edmonds_karp_demo.cc

    r146 r155  
    66#include <edmonds_karp.hh>
    77#include <time_measure.h>
     8#include <graph_wrapper.h>
    89
    910using namespace hugo;
    … …  
    5859  ListGraph::EdgeMap<int> cap(G);
    5960  readDimacsMaxFlow(std::cin, G, s, t, cap);
     61/*
     62  typedef TrivGraphWrapper<ListGraph> TGW;
     63  TGW gw(G);
     64  TGW::EachNodeIt sw;
     65  gw.getFirst(sw);
     66  std::cout << "p1:" << gw.nodeNum() << std::endl;
     67  gw.erase(sw);
     68  std::cout << "p2:" << gw.nodeNum() << std::endl;
     69
     70  typedef const ListGraph cLG;
     71  typedef TrivGraphWrapper<const cLG> CTGW;
     72  CTGW cgw(G);
     73  CTGW::EachNodeIt csw;
     74  cgw.getFirst(csw);
     75  std::cout << "p1:" << cgw.nodeNum() << std::endl;
     76  //cgw.erase(csw);
     77  std::cout << "p2:" << cgw.nodeNum() << std::endl;
     78*/
    6079
    6180  {

  • src/work/marci/graph_wrapper.h

    r148 r155  
    1313
    1414    typedef typename Graph::NodeIt NodeIt;
     15    typedef typename Graph::EachNodeIt EachNodeIt;
     16
    1517    typedef typename Graph::EdgeIt EdgeIt;
    16  
    17     typedef typename Graph::EachNodeIt EachNodeIt;
    18 
    1918    typedef typename Graph::OutEdgeIt OutEdgeIt;
    2019    typedef typename Graph::InEdgeIt InEdgeIt;
    21     typedef typename Graph::SymEdgeIt SymEdgeIt;
     20    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    2221    typedef typename Graph::EachEdgeIt EachEdgeIt;
    23 
    24     int nodeNum() const { return graph->nodeNum(); }
    25     int edgeNum() const { return graph->edgeNum(); }
    2622   
    2723    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    2824    template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    2925      return graph->getFirst(i, p); }
    30     //template<typename I> I next(const I i); { return graph->goNext(i); }
    31     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     26   
     27    template<typename I> I getNext(const I& i) const {
     28      return graph->getNext(i); }
     29    template<typename I> I& next(I &i) const { return graph->next(i); }   
    3230
    3331    template< typename It > It first() const {
    3432      It e; getFirst(e); return e; }
    3533
    36     template< typename It > It first(NodeIt v) const {
     34    template< typename It > It first(const NodeIt& v) const {
    3735      It e; getFirst(e, v); return e; }
    3836
    3937    NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    4038    NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     39
     40    template<typename I> bool valid(const I& i) const
     41      { return graph->valid(i); }
     42 
     43    //template<typename I> void setInvalid(const I &i);
     44    //{ return graph->setInvalid(i); }
     45
     46    int nodeNum() const { return graph->nodeNum(); }
     47    int edgeNum() const { return graph->edgeNum(); }
    4148 
    4249    template<typename I> NodeIt aNode(const I& e) const {
    … …  
    4552      return graph->bNode(e); }
    4653 
    47     //template<typename I> bool valid(const I& i)
    48     //{ return graph->valid(i); }
    49  
    50     //template<typename I> void setInvalid(const I &i);
    51     //{ return graph->setInvalid(i); }
    52  
    5354    NodeIt addNode() const { return graph->addNode(); }
    5455    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
    … …  
    5859 
    5960    void clear() const { graph->clear(); }
    60  
     61   
    6162    template<typename T> class NodeMap : public Graph::NodeMap<T> {
    6263    public:
    63       NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
    64       NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
    65     };
    66     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
    67  
     64      NodeMap(const TrivGraphWrapper<Graph>& _G) :
     65        Graph::NodeMap<T>(*(_G.G)) { }
     66      NodeMap(const TrivGraphWrapper<Graph>& _G, T a) :
     67        Graph::NodeMap<T>(*(_G.G), a) { }
     68    };
     69    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
     70    public:
     71      EdgeMap(const TrivGraphWrapper<Graph>& _G) :
     72        Graph::EdgeMap<T>(*(_G.G)) { }
     73      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
     74        Graph::EdgeMap<T>(*(_G.G), a) { }
     75    };
     76   
    6877    void setGraph(Graph& _graph) { graph = &_graph; }
    69     Graph& getGraph() { return (*graph); }
     78    Graph& getGraph() const { return (*graph); }
    7079 
    7180    //TrivGraphWrapper() : graph(0) { }
    … …  
    7483
    7584  template<typename Graph>
    76   class ConstTrivGraphWrapper {
    77     const Graph* graph;
     85  class RevGraphWrapper
     86  {
     87    Graph* graph;
    7888 
    7989  public:
    8090    typedef Graph BaseGraph;
    8191
    82     typedef typename Graph::NodeIt NodeIt;
     92    typedef typename Graph::NodeIt NodeIt;   
     93    typedef typename Graph::EachNodeIt EachNodeIt;
     94 
    8395    typedef typename Graph::EdgeIt EdgeIt;
    84  
    85     typedef typename Graph::EachNodeIt EachNodeIt;
    86 
    87     typedef typename Graph::OutEdgeIt OutEdgeIt;
    88     typedef typename Graph::InEdgeIt InEdgeIt;
    89     typedef typename Graph::SymEdgeIt SymEdgeIt;
     96    typedef typename Graph::OutEdgeIt InEdgeIt;
     97    typedef typename Graph::InEdgeIt OutEdgeIt;
     98    //typedef typename Graph::SymEdgeIt SymEdgeIt;
    9099    typedef typename Graph::EachEdgeIt EachEdgeIt;
    91 
    92     int nodeNum() const { return graph->nodeNum(); }
    93     int edgeNum() const { return graph->edgeNum(); }
    94100   
    95101    template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    96102    template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    97103      return graph->getFirst(i, p); }
    98     //template<typename I> I next(const I i); { return graph->goNext(i); }
    99     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     104
     105    template<typename I> I getNext(const I& i) const {
     106      return graph->getNext(i); }
     107    template<typename I> I& next(I &i) const { return graph->next(i); }   
    100108
    101109    template< typename It > It first() const {
    102110      It e; getFirst(e); return e; }
    103111
    104     template< typename It > It first(NodeIt v) const {
     112    template< typename It > It first(const NodeIt& v) const {
    105113      It e; getFirst(e, v); return e; }
    106114
    107     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    108     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     115    NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
     116    NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
     117 
     118    template<typename I> bool valid(const I& i) const
     119      { return graph->valid(i); }
     120 
     121    //template<typename I> void setInvalid(const I &i);
     122    //{ return graph->setInvalid(i); }
    109123 
    110124    template<typename I> NodeIt aNode(const I& e) const {
    … …  
    112126    template<typename I> NodeIt bNode(const I& e) const {
    113127      return graph->bNode(e); }
    114  
    115     //template<typename I> bool valid(const I& i)
    116     //{ return graph->valid(i); }
    117  
    118     //template<typename I> void setInvalid(const I &i);
    119     //{ return graph->setInvalid(i); }
    120  
     128
    121129    NodeIt addNode() const { return graph->addNode(); }
    122130    EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) const {
    123131      return graph->addEdge(tail, head); }
    124132 
    125     template<typename I> void erase(const I& i) const { graph->erase(i); }
    126  
    127     void clear() const { graph->clear(); }
    128  
    129     template<typename T> class NodeMap : public Graph::NodeMap<T> {
    130     public:
    131       NodeMap(const Graph& _G) : Graph::NodeMap<T>(_G) { }
    132       NodeMap(const Graph& _G, T a) : Graph::NodeMap<T>(_G, a) { }
    133     };
    134     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
    135  
    136     void setGraph(const Graph& _graph) { graph = &_graph; }
    137     const Graph& getGraph() { return (*graph); }
    138  
    139     //ConstTrivGraphWrapper() : graph(0) { }
    140     ConstTrivGraphWrapper(const Graph& _graph) : graph(&_graph) { }
    141   };
    142 
    143 
    144   template<typename Graph>
    145   class RevGraphWrapper
    146   {
    147     Graph* graph;
    148  
    149   public:
    150     typedef Graph BaseGraph;
    151 
    152     typedef typename Graph::NodeIt NodeIt;
    153     typedef typename Graph::EdgeIt EdgeIt;
    154  
    155     typedef typename Graph::EachNodeIt EachNodeIt;
    156  
    157     typedef typename Graph::OutEdgeIt InEdgeIt;
    158     typedef typename Graph::InEdgeIt OutEdgeIt;
    159     typedef typename Graph::SymEdgeIt SymEdgeIt;
    160     typedef typename Graph::EachEdgeIt EachEdgeIt;
    161 
    162133    int nodeNum() const { return graph->nodeNum(); }
    163134    int edgeNum() const { return graph->edgeNum(); }
    164    
    165     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    166     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    167       return graph->getFirst(i, p); }
    168     //template<typename I> I next(const I i); { return graph->goNext(i); }
    169     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    170 
    171     template< typename It > It first() const {
    172       It e; getFirst(e); return e; }
    173 
    174     template< typename It > It first(NodeIt v) const {
    175       It e; getFirst(e, v); return e; }
    176 
    177     NodeIt head(const EdgeIt& e) const { return graph->tail(e); }
    178     NodeIt tail(const EdgeIt& e) const { return graph->head(e); }
    179  
    180     template<typename I> NodeIt aNode(const I& e) const {
    181       return graph->aNode(e); }
    182     template<typename I> NodeIt bNode(const I& e) const {
    183       return graph->bNode(e); }
    184  
    185     //template<typename I> bool valid(const I i);
    186     //{ return graph->valid(i); }
    187  
    188     //template<typename I> void setInvalid(const I &i);
    189     //{ return graph->setInvalid(i); }
    190  
    191     NodeIt addNode() { return graph->addNode(); }
    192     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
    193       return graph->addEdge(tail, head); }
    194  
    195     template<typename I> void erase(const I& i) { graph->erase(i); }
    196  
    197     void clear() { graph->clear(); }
    198  
    199     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
    200     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
    201  
     135 
     136    template<typename I> void erase(const I& i) const { graph->erase(i); }
     137 
     138    void clear() const { graph->clear(); }
     139
     140    template<typename T> class NodeMap : public Graph::NodeMap<T> {
     141    public:
     142      NodeMap(const RevGraphWrapper<Graph>& _G) :
     143        Graph::NodeMap<T>(*(_G.G)) { }
     144      NodeMap(const RevGraphWrapper<Graph>& _G, T a) :
     145        Graph::NodeMap<T>(*(_G.G), a) { }
     146    };
     147    template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
     148    public:
     149      EdgeMap(const RevGraphWrapper<Graph>& _G) :
     150        Graph::EdgeMap<T>(*(_G.G)) { }
     151      EdgeMap(const RevGraphWrapper<Graph>& _G, T a) :
     152        Graph::EdgeMap<T>(*(_G.G), a) { }
     153    };
     154
    202155    void setGraph(Graph& _graph) { graph = &_graph; }
    203     Graph& getGraph() { return (*graph); }
     156    Graph& getGraph() const { return (*graph); }
    204157
    205158    //RevGraphWrapper() : graph(0) { }
    … …  
    207160  };
    208161
    209   template<typename Graph>
    210   class SymGraphWrapper
    211   {
    212     Graph* graph;
    213  
     162
     163//   template<typename Graph>
     164//   class SymGraphWrapper
     165//   {
     166//     Graph* graph;
     167 
     168//   public:
     169//     typedef Graph BaseGraph;
     170
     171//     typedef typename Graph::NodeIt NodeIt;
     172//     typedef typename Graph::EdgeIt EdgeIt;
     173 
     174//     typedef typename Graph::EachNodeIt EachNodeIt;
     175   
     176//     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
     177//     //iranyitatlant, ami van
     178//     //mert csak 1 dolgot lehet be typedef-elni
     179//     typedef typename Graph::OutEdgeIt SymEdgeIt;
     180//     //typedef typename Graph::InEdgeIt SymEdgeIt;
     181//     //typedef typename Graph::SymEdgeIt SymEdgeIt;
     182//     typedef typename Graph::EachEdgeIt EachEdgeIt;
     183
     184//     int nodeNum() const { return graph->nodeNum(); }
     185//     int edgeNum() const { return graph->edgeNum(); }
     186   
     187//     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
     188//     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
     189//       return graph->getFirst(i, p); }
     190//     //template<typename I> I next(const I i); { return graph->goNext(i); }
     191//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
     192
     193//     template< typename It > It first() const {
     194//       It e; getFirst(e); return e; }
     195
     196//     template< typename It > It first(NodeIt v) const {
     197//       It e; getFirst(e, v); return e; }
     198
     199//     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
     200//     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
     201 
     202//     template<typename I> NodeIt aNode(const I& e) const {
     203//       return graph->aNode(e); }
     204//     template<typename I> NodeIt bNode(const I& e) const {
     205//       return graph->bNode(e); }
     206 
     207//     //template<typename I> bool valid(const I i);
     208//     //{ return graph->valid(i); }
     209 
     210//     //template<typename I> void setInvalid(const I &i);
     211//     //{ return graph->setInvalid(i); }
     212 
     213//     NodeIt addNode() { return graph->addNode(); }
     214//     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
     215//       return graph->addEdge(tail, head); }
     216 
     217//     template<typename I> void erase(const I& i) { graph->erase(i); }
     218 
     219//     void clear() { graph->clear(); }
     220 
     221//     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
     222//     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
     223 
     224//     void setGraph(Graph& _graph) { graph = &_graph; }
     225//     Graph& getGraph() { return (*graph); }
     226
     227//     //SymGraphWrapper() : graph(0) { }
     228//     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
     229//   };
     230
     231
     232  template<typename Graph, typename Number, typename FlowMap, typename CapacityMap>
     233  class ResGraphWrapper {
    214234  public:
    215235    typedef Graph BaseGraph;
    216 
    217236    typedef typename Graph::NodeIt NodeIt;
    218     typedef typename Graph::EdgeIt EdgeIt;
    219  
    220237    typedef typename Graph::EachNodeIt EachNodeIt;
     238  private:
     239    typedef typename Graph::OutEdgeIt OldOutEdgeIt;
     240    typedef typename Graph::InEdgeIt OldInEdgeIt;
     241    const Graph* G;
     242    FlowMap* flow;
     243    const CapacityMap* capacity;
     244  public:
     245    ResGraphWrapper(const Graph& _G, FlowMap& _flow,
     246             const CapacityMap& _capacity) :
     247      G(&_G), flow(&_flow), capacity(&_capacity) { }
     248//     ResGraphWrapper(const ResGraphWrapper& res_graph_wrapper) :
     249//       G(res_graph_wrapper.G), flow(res_graph_wrapper.flow), capacity(res_graph_wrapper.capacity) { }
     250    class EdgeIt;
     251    class OutEdgeIt;
     252    friend class EdgeIt;
     253    friend class OutEdgeIt;
     254
     255    class EdgeIt {
     256      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     257    protected:
     258      //const ResGraph3<Graph, Number, FlowMap, CapacityMap>* resG;
     259      const Graph* G;
     260      FlowMap* flow;
     261      const CapacityMap* capacity;
     262      //OldSymEdgeIt sym;
     263      OldOutEdgeIt out;
     264      OldInEdgeIt in;
     265      bool out_or_in; //true, iff out
     266    public:
     267      EdgeIt() : out_or_in(true) { }
     268      EdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) :
     269        G(&_G), flow(&_flow), capacity(&_capacity), out_or_in(true) { }
     270      //EdgeIt(const EdgeIt& e) : G(e.G), flow(e.flow), capacity(e.capacity), out(e.out), in(e.in), out_or_in(e.out_or_in) { }
     271      Number free() const {
     272        if (out_or_in) {
     273          return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
     274        } else {
     275          return (/*resG->*/flow->get(in));
     276        }
     277      }
     278      bool valid() const {
     279        return out_or_in && out.valid() || in.valid(); }
     280      void augment(Number a) const {
     281        if (out_or_in) {
     282          /*resG->*/flow->set(out, /*resG->*/flow->get(out)+a);
     283        } else {
     284          /*resG->*/flow->set(in, /*resG->*/flow->get(in)-a);
     285        }
     286      }
     287      void print() {
     288        if (out_or_in) {
     289          std::cout << "out ";
     290          if (out.valid())
     291            std::cout << G->id(G->tail(out)) << "--"<< G->id(out) <<"->"<< G->id(G->head(out));
     292          else
     293            std::cout << "invalid";
     294        }
     295        else {
     296          std::cout << "in ";
     297          if (in.valid())
     298            std::cout << G->id(G->head(in)) << "<-"<< G->id(in) <<"--"<< G->id(G->tail(in));
     299          else
     300            std::cout << "invalid";
     301        }
     302        std::cout << std::endl;
     303      }
     304    };
     305
     306    Number free(OldOutEdgeIt out) const {
     307      return (/*resG->*/capacity->get(out)-/*resG->*/flow->get(out));
     308    }
     309    Number free(OldInEdgeIt in) const {
     310      return (/*resG->*/flow->get(in));
     311    }
     312
     313    class OutEdgeIt : public EdgeIt {
     314      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     315    public:
     316      OutEdgeIt() { }
     317    private:
     318      OutEdgeIt(const Graph& _G, NodeIt v, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
     319        //out=/*resG->*/G->template first<OldOutEdgeIt>(v);
     320        G->getFirst(out, v);
     321        while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     322        if (!out.valid()) {
     323          out_or_in=0;
     324          //in=/*resG->*/G->template first<OldInEdgeIt>(v);
     325          G->getFirst(in, v);
     326          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     327        }
     328      }
     329    public:
     330      OutEdgeIt& operator++() {
     331        if (out_or_in) {
     332          NodeIt v=/*resG->*/G->aNode(out);
     333          ++out;
     334          while( out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     335          if (!out.valid()) {
     336            out_or_in=0;
     337            G->getFirst(in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
     338            while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     339          }
     340        } else {
     341          ++in;
     342          while( in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     343        }
     344        return *this;
     345      }
     346    };
     347
     348    class EachEdgeIt : public EdgeIt {
     349      friend class ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>;
     350      typename Graph::EachNodeIt v;
     351    public:
     352      EachEdgeIt() { }
     353      //EachEdgeIt(const EachEdgeIt& e) : EdgeIt(e), v(e.v) { }
     354      EachEdgeIt(const Graph& _G, FlowMap& _flow, const CapacityMap& _capacity) : EdgeIt(_G, _flow, _capacity) {
     355        out_or_in=true;
     356        G->getFirst(v);
     357        if (v.valid()) G->getFirst(out, v); else out=OldOutEdgeIt();
     358        while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     359        while (v.valid() && !out.valid()) {
     360          ++v;
     361          if (v.valid()) G->getFirst(out, v);
     362          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     363        }
     364        if (!out.valid()) {
     365          out_or_in=0;
     366          G->getFirst(v);
     367          if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
     368          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     369          while (v.valid() && !in.valid()) {
     370            ++v;
     371            if (v.valid()) G->getFirst(in, v);
     372            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     373          }
     374        }
     375      }
     376      EachEdgeIt& operator++() {
     377        if (out_or_in) {
     378          ++out;
     379          while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     380          while (v.valid() && !out.valid()) {
     381            ++v;
     382            if (v.valid()) G->getFirst(out, v);
     383            while (out.valid() && !(EdgeIt::free()>0) ) { ++out; }
     384          }
     385          if (!out.valid()) {
     386            out_or_in=0;
     387            G->getFirst(v);
     388            if (v.valid()) G->getFirst(in, v); else in=OldInEdgeIt();
     389            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     390            while (v.valid() && !in.valid()) {
     391              ++v;
     392              if (v.valid()) G->getFirst(in, v);
     393              while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     394            } 
     395          }
     396        } else {
     397          ++in;
     398          while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     399          while (v.valid() && !in.valid()) {
     400            ++v;
     401            if (v.valid()) G->getFirst(in, v);
     402            while (in.valid() && !(EdgeIt::free()>0) ) { ++in; }
     403          }
     404        }
     405        return *this;
     406      }
     407    };
     408
     409    void getFirst(EachNodeIt& v) const { G->getFirst(v); }
     410    void getFirst(OutEdgeIt& e, NodeIt v) const {
     411      e=OutEdgeIt(*G, v, *flow, *capacity);
     412    }
     413    void getFirst(EachEdgeIt& e) const {
     414      e=EachEdgeIt(*G, *flow, *capacity);
     415    }
     416   
     417    EachNodeIt& next(EachNodeIt& n) const { return G->next(n); }
     418
     419    OutEdgeIt& next(OutEdgeIt& e) const {
     420      if (e.out_or_in) {
     421        NodeIt v=G->aNode(e.out);
     422        ++(e.out);
     423        while( G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     424        if (!G->valid(e.out)) {
     425          e.out_or_in=0;
     426          G->getFirst(e.in, v); //=/*resG->*/G->template first<OldInEdgeIt>(v);
     427          while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     428        }
     429      } else {
     430        ++(e.in);
     431        while( G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     432      }
     433      return e;
     434    }
     435
     436    EachEdgeIt& next(EachEdgeIt& e) const {
     437      if (e.out_or_in) {
     438        ++(e.out);
     439        while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     440          while (G->valid(e.v) && !G->valid(e.out)) {
     441            ++(e.v);
     442            if (G->valid(e.v)) G->getFirst(e.out, e.v);
     443            while (G->valid(e.out) && !(e.free()>0) ) { ++(e.out); }
     444          }
     445          if (!G->valid(e.out)) {
     446            e.out_or_in=0;
     447            G->getFirst(e.v);
     448            if (G->valid(e.v)) G->getFirst(e.in, e.v); else e.in=OldInEdgeIt();
     449            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     450            while (G->valid(e.v) && !G->valid(e.in)) {
     451              ++(e.v);
     452              if (G->valid(e.v)) G->getFirst(e.in, e.v);
     453              while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     454            } 
     455          }
     456        } else {
     457          ++(e.in);
     458          while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     459          while (G->valid(e.v) && !G->valid(e.in)) {
     460            ++(e.v);
     461            if (G->valid(e.v)) G->getFirst(e.in, e.v);
     462            while (G->valid(e.in) && !(e.free()>0) ) { ++(e.in); }
     463          }
     464        }
     465        return e;
     466      }
    221467   
    222     //FIXME tag-ekkel megcsinalni, hogy abbol csinaljon
    223     //iranyitatlant, ami van
    224     //mert csak 1 dolgot lehet be typedef-elni
    225     typedef typename Graph::OutEdgeIt SymEdgeIt;
    226     //typedef typename Graph::InEdgeIt SymEdgeIt;
    227     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    228     typedef typename Graph::EachEdgeIt EachEdgeIt;
    229 
    230     int nodeNum() const { return graph->nodeNum(); }
    231     int edgeNum() const { return graph->edgeNum(); }
    232    
    233     template<typename I> I& getFirst(I& i) const { return graph->getFirst(i); }
    234     template<typename I, typename P> I& getFirst(I& i, const P& p) const {
    235       return graph->getFirst(i, p); }
    236     //template<typename I> I next(const I i); { return graph->goNext(i); }
    237     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    238 
    239     template< typename It > It first() const {
    240       It e; getFirst(e); return e; }
    241 
    242     template< typename It > It first(NodeIt v) const {
    243       It e; getFirst(e, v); return e; }
    244 
    245     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    246     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
    247  
    248     template<typename I> NodeIt aNode(const I& e) const {
    249       return graph->aNode(e); }
    250     template<typename I> NodeIt bNode(const I& e) const {
    251       return graph->bNode(e); }
    252  
    253     //template<typename I> bool valid(const I i);
    254     //{ return graph->valid(i); }
    255  
    256     //template<typename I> void setInvalid(const I &i);
    257     //{ return graph->setInvalid(i); }
    258  
    259     NodeIt addNode() { return graph->addNode(); }
    260     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
    261       return graph->addEdge(tail, head); }
    262  
    263     template<typename I> void erase(const I& i) { graph->erase(i); }
    264  
    265     void clear() { graph->clear(); }
    266  
    267     template<typename T> class NodeMap : public Graph::NodeMap<T> { };
    268     template<typename T> class EdgeMap : public Graph::EdgeMap<T> { };
    269  
    270     void setGraph(Graph& _graph) { graph = &_graph; }
    271     Graph& getGraph() { return (*graph); }
    272 
    273     //SymGraphWrapper() : graph(0) { }
    274     SymGraphWrapper(Graph& _graph) : graph(&_graph) { }
     468
     469    template< typename It >
     470    It first() const {
     471      It e;
     472      getFirst(e);
     473      return e;
     474    }
     475
     476    template< typename It >
     477    It first(NodeIt v) const {
     478      It e;
     479      getFirst(e, v);
     480      return e;
     481    }
     482
     483    NodeIt tail(EdgeIt e) const {
     484      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
     485    NodeIt head(EdgeIt e) const {
     486      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
     487
     488    NodeIt aNode(OutEdgeIt e) const {
     489      return ((e.out_or_in) ? G->aNode(e.out) : G->aNode(e.in)); }
     490    NodeIt bNode(OutEdgeIt e) const {
     491      return ((e.out_or_in) ? G->bNode(e.out) : G->bNode(e.in)); }
     492
     493    int id(NodeIt v) const { return G->id(v); }
     494
     495    bool valid(NodeIt n) const { return G->valid(n); }
     496    bool valid(EdgeIt e) const {
     497      return e.out_or_in ? G->valid(e.out) : G->valid(e.in); }
     498
     499    template<typename T> class NodeMap : public Graph::NodeMap<T> {
     500    public:
     501      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G)
     502        : Graph::NodeMap<T>(*(_G.G)) { }
     503      NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G,
     504              T a) : Graph::NodeMap<T>(*(_G.G), a) { }
     505    };
     506
     507//     template <typename T>
     508//     class NodeMap {
     509//       typename Graph::NodeMap<T> node_map;
     510//     public:
     511//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : node_map(*(_G.G)) { }
     512//       NodeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : node_map(*(_G.G), a) { }
     513//       void set(NodeIt nit, T a) { node_map.set(nit, a); }
     514//       T get(NodeIt nit) const { return node_map.get(nit); }
     515//     };
     516
     517    template <typename T>
     518    class EdgeMap {
     519      typename Graph::EdgeMap<T> forward_map, backward_map;
     520    public:
     521      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G) : forward_map(*(_G.G)), backward_map(*(_G.G)) { }
     522      EdgeMap(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& _G, T a) : forward_map(*(_G.G), a), backward_map(*(_G.G), a) { }
     523      void set(EdgeIt e, T a) {
     524        if (e.out_or_in)
     525          forward_map.set(e.out, a);
     526        else
     527          backward_map.set(e.in, a);
     528      }
     529      T get(EdgeIt e) {
     530        if (e.out_or_in)
     531          return forward_map.get(e.out);
     532        else
     533          return backward_map.get(e.in);
     534      }
     535    };
     536
    275537  };
    276538
    … …  
    423685//   };
    424686
    425 
    426 // // FIXME: comparison should be made better!!!
    427 //   template<typename Graph, typename T, typename LowerMap, typename FlowMap, typename UpperMap>
    428 //   class ConstResGraphWrapper
    429 //   {
    430 //     const Graph* graph;
    431 //     const LowerMap* low;
    432 //     FlowMap* flow;
    433 //     const UpperMap* up;
    434 //   public:
    435 //     typedef Graph BaseGraph;
    436 
    437 //     typedef typename Graph::NodeIt NodeIt;
    438 //     typedef typename Graph::EdgeIt EdgeIt;
    439  
    440 //     typedef typename Graph::EachNodeIt EachNodeIt;
    441    
    442 //     class OutEdgeIt {
    443 //     public:
    444 //       //Graph::NodeIt n;
    445 //       bool out_or_in;
    446 //       typename Graph::SymEdgeIt sym;
    447 //     };
    448 //     class InEdgeIt {
    449 //     public:
    450 //       //Graph::NodeIt n;
    451 //       bool out_or_in;
    452 //       typename Graph::OutEdgeIt sym;
    453 //     };
    454 //     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    455 //     //typedef typename Graph::EachEdgeIt EachEdgeIt;
    456 
    457 //     int nodeNum() const { return graph->nodeNum(); }
    458 //     //int edgeNum() const { return graph->edgeNum(); }
    459 
    460 //     NodeIt& getFirst(NodeIt& n) const { return graph->getFirst(n); }
    461 
    462 //     // EachEdge and SymEdge  is missing!!!!
    463 //     // EdgeIt <-> In/OutEdgeIt conversion is missing!!!!
    464 
    465    
    466 //     //FIXME
    467 //     OutEdgeIt& getFirst(OutEdgeIt& e, const NodeIt& n) const
    468 //       {
    469 //      e.n=n;
    470 //      graph->getFirst(e.o,n);
    471 //      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    472 //        graph->goNext(e.o);
    473 //      if(!graph->valid(e.o)) {
    474 //        graph->getFirst(e.i,n);
    475 //        while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    476 //          graph->goNext(e.i);
    477 //      }
    478 //      return e;
    479 //       }
    480 // /*
    481 //   OutEdgeIt &goNext(OutEdgeIt &e)
    482 //   {
    483 //   if(graph->valid(e.o)) {
    484 //   while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    485 //   graph->goNext(e.o);
    486 //   if(graph->valid(e.o)) return e;
    487 //   else graph->getFirst(e.i,e.n);
    488 //   }
    489 //   else {
    490 //   while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    491 //   graph->goNext(e.i);
    492 //   return e;
    493 //   }
    494 //   }
    495 //   OutEdgeIt Next(const OutEdgeIt &e) {OutEdgeIt t(e); return goNext(t);}
    496 // */
    497 //     //bool valid(const OutEdgeIt e) { return graph->valid(e.o)||graph->valid(e.i);}
    498 
    499 //     //FIXME
    500 //     InEdgeIt& getFirst(InEdgeIt& e, const NodeIt& n) const
    501 //       {
    502 //      e.n=n;
    503 //      graph->getFirst(e.i,n);
    504 //      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    505 //        graph->goNext(e.i);
    506 //      if(!graph->valid(e.i)) {
    507 //        graph->getFirst(e.o,n);
    508 //        while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    509 //          graph->goNext(e.o);
    510 //      }
    511 //      return e;
    512 //       }
    513 // /*
    514 //   InEdgeIt &goNext(InEdgeIt &e)
    515 //   {
    516 //   if(graph->valid(e.i)) {
    517 //   while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    518 //   graph->goNext(e.i);
    519 //   if(graph->valid(e.i)) return e;
    520 //   else graph->getFirst(e.o,e.n);
    521 //   }
    522 //   else {
    523 //   while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    524 //   graph->goNext(e.o);
    525 //   return e;
    526 //   }
    527 //   }
    528 //   InEdgeIt Next(const InEdgeIt &e) {InEdgeIt t(e); return goNext(t);}
    529 // */
    530 //     //bool valid(const InEdgeIt e) { return graph->valid(e.i)||graph->valid(e.o);}
    531 
    532 //     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    533 //     //template<typename I> I next(const I i); { return graph->goNext(i); }
    534 
    535 //     template< typename It > It first() const {
    536 //       It e; getFirst(e); return e; }
    537 
    538 //     template< typename It > It first(NodeIt v) const {
    539 //       It e; getFirst(e, v); return e; }
    540 
    541 //     NodeIt head(const EdgeIt& e) const { return graph->head(e); }
    542 //     NodeIt tail(const EdgeIt& e) const { return graph->tail(e); }
    543  
    544 //     template<typename I> NodeIt aNode(const I& e) const {
    545 //       return graph->aNode(e); }
    546 //     template<typename I> NodeIt bNode(const I& e) const {
    547 //       return graph->bNode(e); }
    548  
    549 //     //template<typename I> bool valid(const I i);
    550 //     //{ return graph->valid(i); }
    551  
    552 //     //template<typename I> void setInvalid(const I &i);
    553 //     //{ return graph->setInvalid(i); }
    554  
    555 //     NodeIt addNode() { return graph->addNode(); }
    556 //     EdgeIt addEdge(const NodeIt& tail, const NodeIt& head) {
    557 //       return graph->addEdge(tail, head); }
    558  
    559 //     template<typename I> void erase(const I& i) { graph->erase(i); }
    560  
    561 //     void clear() { graph->clear(); }
    562  
    563 //     template<typename S> class NodeMap : public Graph::NodeMap<S> { };
    564 //     template<typename S> class EdgeMap : public Graph::EdgeMap<S> { };
    565  
    566 //     void setGraph(const Graph& _graph) { graph = &_graph; }
    567 //     const Graph& getGraph() { return (*graph); }
    568 
    569 //     //ConstResGraphWrapper() : graph(0) { }
    570 //     ConstResGraphWrapper(const Graph& _graph) : graph(&_graph) { }
    571 //   };
    572 
    573 
    574 
    575 
    576 
    577687} //namespace hugo
    578688
Note: See TracChangeset for help on using the changeset viewer.