COIN-OR::LEMON - Graph Library

Changeset 212:c07e4dd32438 in lemon-0.x


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

.

Location:
src/work
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/list_graph.h

    r208 r212  
    429429      //protected:
    430430    public: //for alpar
    431       EdgeIt(const ListGraph&) {
     431      EdgeIt(const ListGraph& G) {
    432432        node_item* v=G._first_node;
    433433        if (v) edge=v->_first_out_edge; else edge=0;
  • src/work/marci/graph_wrapper.h

    r199 r212  
    3030    Graph& getGraph() const { return (*graph); }
    3131   
    32     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
    33     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
    34       return graph->/*getF*/first(i, p); }
     32    template<typename I> I& first(I& i) const { return graph->first(i); }
     33    template<typename I, typename P> I& first(I& i, const P& p) const {
     34      return graph->first(i, p); }
    3535   
    3636    template<typename I> I getNext(const I& i) const {
     
    3939
    4040    template< typename It > It first() const {
    41       It e; /*getF*/first(e); return e; }
     41      It e; first(e); return e; }
    4242
    4343    template< typename It > It first(const Node& v) const {
    44       It e; /*getF*/first(e, v); return e; }
     44      It e; first(e, v); return e; }
    4545
    4646    Node head(const Edge& e) const { return graph->head(e); }
     
    8383      EdgeMap(const TrivGraphWrapper<Graph>& _G, T a) :
    8484        Graph::EdgeMap<T>(_G.getGraph(), a) { }
     85    };
     86  };
     87
     88  template<typename GraphWrapper>
     89  class GraphWrapperSkeleton {
     90  protected:
     91    GraphWrapper gw;
     92 
     93  public:
     94    typedef typename GraphWrapper::BaseGraph BaseGraph;
     95
     96    typedef typename GraphWrapper::Node Node;
     97    typedef typename GraphWrapper::NodeIt NodeIt;
     98
     99    typedef typename GraphWrapper::Edge Edge;
     100    typedef typename GraphWrapper::OutEdgeIt OutEdgeIt;
     101    typedef typename GraphWrapper::InEdgeIt InEdgeIt;
     102    //typedef typename GraphWrapper::SymEdgeIt SymEdgeIt;
     103    typedef typename GraphWrapper::EdgeIt EdgeIt;
     104
     105    //GraphWrapperSkeleton() : gw() { }
     106    GraphWrapperSkeleton(GraphWrapper& _gw) : gw(_gw) { }
     107
     108    void setGraph(BaseGraph& _graph) { gw.setGraph(_graph); }
     109    BaseGraph& getGraph() const { return gw.getGraph(); }
     110   
     111    template<typename I> I& first(I& i) const { return gw.first(i); }
     112    template<typename I, typename P> I& first(I& i, const P& p) const {
     113      return gw.first(i, p); }
     114   
     115    template<typename I> I getNext(const I& i) const { return gw.getNext(i); }
     116    template<typename I> I& next(I &i) const { return gw.next(i); }   
     117
     118    template< typename It > It first() const {
     119      It e; this->first(e); return e; }
     120
     121    template< typename It > It first(const Node& v) const {
     122      It e; this->first(e, v); return e; }
     123
     124    Node head(const Edge& e) const { return gw.head(e); }
     125    Node tail(const Edge& e) const { return gw.tail(e); }
     126
     127    template<typename I> bool valid(const I& i) const { return gw.valid(i); }
     128 
     129    //template<typename I> void setInvalid(const I &i);
     130    //{ return graph->setInvalid(i); }
     131
     132    int nodeNum() const { return gw.nodeNum(); }
     133    int edgeNum() const { return gw.edgeNum(); }
     134 
     135    template<typename I> Node aNode(const I& e) const { return gw.aNode(e); }
     136    template<typename I> Node bNode(const I& e) const { return gw.bNode(e); }
     137 
     138    Node addNode() const { return gw.addNode(); }
     139    Edge addEdge(const Node& tail, const Node& head) const {
     140      return gw.addEdge(tail, head); }
     141 
     142    template<typename I> void erase(const I& i) const { gw.erase(i); }
     143 
     144    void clear() const { gw.clear(); }
     145   
     146    template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
     147    public:
     148      NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
     149        GraphWrapper::NodeMap<T>(_G.gw) { }
     150      NodeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
     151        GraphWrapper::NodeMap<T>(_G.gw, a) { }
     152    };
     153
     154    template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
     155    public:
     156      EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G) :
     157        GraphWrapper::EdgeMap<T>(_G.gw) { }
     158      EdgeMap(const GraphWrapperSkeleton<GraphWrapper>& _G, T a) :
     159        GraphWrapper::EdgeMap<T>(_G.gw, a) { }
    85160    };
    86161  };
     
    110185    Graph& getGraph() const { return (*graph); }
    111186   
    112     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
    113     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
    114       return graph->/*getF*/first(i, p); }
     187    template<typename I> I& first(I& i) const { return graph->first(i); }
     188    template<typename I, typename P> I& first(I& i, const P& p) const {
     189      return graph->first(i, p); }
    115190
    116191    template<typename I> I getNext(const I& i) const {
     
    119194
    120195    template< typename It > It first() const {
    121       It e; /*getF*/first(e); return e; }
     196      It e; first(e); return e; }
    122197
    123198    template< typename It > It first(const Node& v) const {
    124       It e; /*getF*/first(e, v); return e; }
     199      It e; first(e, v); return e; }
    125200
    126201    Node head(const Edge& e) const { return graph->tail(e); }
     
    228303      OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() {
    229304        out_or_in=true;
    230         _G.graph->/*getF*/first(out, n);
     305        _G.graph->first(out, n);
    231306        if (!(_G.graph->valid(out))) {
    232307          out_or_in=false;
    233           _G.graph->/*getF*/first(in, n);
     308          _G.graph->first(in, n);
    234309        }
    235310      }
    236311    };
    237312
    238     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
     313    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
    239314      e.out_or_in=true;
    240       graph->/*getF*/first(e.out, n);
     315      graph->first(e.out, n);
    241316      if (!(graph->valid(e.out))) {
    242317        e.out_or_in=false;
    243         graph->/*getF*/first(e.in, n);
     318        graph->first(e.in, n);
    244319      }
    245320      return e;
     
    252327        if (!graph->valid(e.out)) {
    253328          e.out_or_in=false;
    254           graph->/*getF*/first(e.in, n);
     329          graph->first(e.in, n);
    255330        }
    256331      } else {
     
    267342    typedef OutEdgeIt InEdgeIt;
    268343
    269     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
    270 //     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
    271 //       return graph->/*getF*/first(i, p); }
     344    template<typename I> I& first(I& i) const { return graph->first(i); }
     345//     template<typename I, typename P> I& first(I& i, const P& p) const {
     346//       return graph->first(i, p); }
    272347   
    273348    template<typename I> I getNext(const I& i) const {
     
    276351
    277352    template< typename It > It first() const {
    278       It e; /*getF*/first(e); return e; }
     353      It e; first(e); return e; }
    279354
    280355    template< typename It > It first(const Node& v) const {
    281       It e; /*getF*/first(e, v); return e; }
     356      It e; first(e, v); return e; }
    282357
    283358    Node head(const Edge& e) const { return graph->head(e); }
     
    349424//     int edgeNum() const { return graph->edgeNum(); }
    350425   
    351 //     template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
    352 //     template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
    353 //       return graph->/*getF*/first(i, p); }
     426//     template<typename I> I& first(I& i) const { return graph->first(i); }
     427//     template<typename I, typename P> I& first(I& i, const P& p) const {
     428//       return graph->first(i, p); }
    354429//     //template<typename I> I next(const I i); { return graph->goNext(i); }
    355430//     //template<typename I> I &goNext(I &i); { return graph->goNext(i); }
    356431
    357432//     template< typename It > It first() const {
    358 //       It e; /*getF*/first(e); return e; }
     433//       It e; first(e); return e; }
    359434
    360435//     template< typename It > It first(Node v) const {
    361 //       It e; /*getF*/first(e, v); return e; }
     436//       It e; first(e, v); return e; }
    362437
    363438//     Node head(const Edge& e) const { return graph->head(e); }
     
    456531    private:
    457532      OutEdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG, Node v) : Edge() {
    458         resG.graph->/*getF*/first(out, v);
     533        resG.graph->first(out, v);
    459534        while( resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
    460535        if (!resG.graph->valid(out)) {
    461536          out_or_in=0;
    462           resG.graph->/*getF*/first(in, v);
     537          resG.graph->first(in, v);
    463538          while( resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
    464539        }
     
    472547//        if (!out.valid()) {
    473548//          out_or_in=0;
    474 //          G->/*getF*/first(in, v);
     549//          G->first(in, v);
    475550//          while( in.valid() && !(Edge::free()>0) ) { ++in; }
    476551//        }
     
    491566      EdgeIt(const Invalid& i) : Edge(i) { }
    492567      EdgeIt(const ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>& resG) : Edge() {
    493         resG.graph->/*getF*/first(v);
    494         if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v); else out=OldOutEdgeIt(INVALID);
     568        resG.graph->first(v);
     569        if (resG.graph->valid(v)) resG.graph->first(out, v); else out=OldOutEdgeIt(INVALID);
    495570        while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
    496571        while (resG.graph->valid(v) && !resG.graph->valid(out)) {
    497572          resG.graph->next(v);
    498           if (resG.graph->valid(v)) resG.graph->/*getF*/first(out, v);
     573          if (resG.graph->valid(v)) resG.graph->first(out, v);
    499574          while (resG.graph->valid(out) && !(resG.free(out)>0) ) { resG.graph->next(out); }
    500575        }
    501576        if (!resG.graph->valid(out)) {
    502577          out_or_in=0;
    503           resG.graph->/*getF*/first(v);
    504           if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v); else in=OldInEdgeIt(INVALID);
     578          resG.graph->first(v);
     579          if (resG.graph->valid(v)) resG.graph->first(in, v); else in=OldInEdgeIt(INVALID);
    505580          while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
    506581          while (resG.graph->valid(v) && !resG.graph->valid(in)) {
    507582            resG.graph->next(v);
    508             if (resG.graph->valid(v)) resG.graph->/*getF*/first(in, v);
     583            if (resG.graph->valid(v)) resG.graph->first(in, v);
    509584            while (resG.graph->valid(in) && !(resG.free(in)>0) ) { resG.graph->next(in); }
    510585          }
     
    517592//        while (v.valid() && !out.valid()) {
    518593//          ++v;
    519 //          if (v.valid()) G->/*getF*/first(out, v);
     594//          if (v.valid()) G->first(out, v);
    520595//          while (out.valid() && !(Edge::free()>0) ) { ++out; }
    521596//        }
    522597//        if (!out.valid()) {
    523598//          out_or_in=0;
    524 //          G->/*getF*/first(v);
    525 //          if (v.valid()) G->/*getF*/first(in, v); else in=OldInEdgeIt();
     599//          G->first(v);
     600//          if (v.valid()) G->first(in, v); else in=OldInEdgeIt();
    526601//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
    527602//          while (v.valid() && !in.valid()) {
    528603//            ++v;
    529 //            if (v.valid()) G->/*getF*/first(in, v);
     604//            if (v.valid()) G->first(in, v);
    530605//            while (in.valid() && !(Edge::free()>0) ) { ++in; }
    531606//          } 
     
    536611//        while (v.valid() && !in.valid()) {
    537612//          ++v;
    538 //          if (v.valid()) G->/*getF*/first(in, v);
     613//          if (v.valid()) G->first(in, v);
    539614//          while (in.valid() && !(Edge::free()>0) ) { ++in; }
    540615//        }
     
    544619    };
    545620
    546     NodeIt& /*getF*/first(NodeIt& v) const { return graph->/*getF*/first(v); }
    547     OutEdgeIt& /*getF*/first(OutEdgeIt& e, Node v) const {
     621    NodeIt& first(NodeIt& v) const { return graph->first(v); }
     622    OutEdgeIt& first(OutEdgeIt& e, Node v) const {
    548623      e=OutEdgeIt(*this, v);
    549624      return e;
    550625    }
    551     EdgeIt& /*getF*/first(EdgeIt& e) const {
     626    EdgeIt& first(EdgeIt& e) const {
    552627      e=EdgeIt(*this);
    553628      return e;
     
    563638        if (!graph->valid(e.out)) {
    564639          e.out_or_in=0;
    565           graph->/*getF*/first(e.in, v);
     640          graph->first(e.in, v);
    566641          while( graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
    567642        }
     
    579654          while (graph->valid(e.v) && !graph->valid(e.out)) {
    580655            graph->next(e.v);
    581             if (graph->valid(e.v)) graph->/*getF*/first(e.out, e.v);
     656            if (graph->valid(e.v)) graph->first(e.out, e.v);
    582657            while (graph->valid(e.out) && !(free(e.out)>0) ) { graph->next(e.out); }
    583658          }
    584659          if (!graph->valid(e.out)) {
    585660            e.out_or_in=0;
    586             graph->/*getF*/first(e.v);
    587             if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v); else e.in=OldInEdgeIt(INVALID);
     661            graph->first(e.v);
     662            if (graph->valid(e.v)) graph->first(e.in, e.v); else e.in=OldInEdgeIt(INVALID);
    588663            while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
    589664            while (graph->valid(e.v) && !graph->valid(e.in)) {
    590665              graph->next(e.v);
    591               if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v);
     666              if (graph->valid(e.v)) graph->first(e.in, e.v);
    592667              while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
    593668            } 
     
    598673          while (graph->valid(e.v) && !graph->valid(e.in)) {
    599674            graph->next(e.v);
    600             if (graph->valid(e.v)) graph->/*getF*/first(e.in, e.v);
     675            if (graph->valid(e.v)) graph->first(e.in, e.v);
    601676            while (graph->valid(e.in) && !(free(e.in)>0) ) { graph->next(e.in); }
    602677          }
     
    609684    It first() const {
    610685      It e;
    611       /*getF*/first(e);
     686      first(e);
    612687      return e;
    613688    }
     
    616691    It first(Node v) const {
    617692      It e;
    618       /*getF*/first(e, v);
     693      first(e, v);
    619694      return e;
    620695    }
     
    709784      for(NodeIt n=this->template first<NodeIt>(); this->valid(n); this->next(n)) {
    710785        OutEdgeIt e;
    711         ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
     786        ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
    712787        first_out_edges.set(n, e);
    713788      }
     
    740815    //typedef typename ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::EdgeIt EdgeIt;
    741816
    742     NodeIt& /*getF*/first(NodeIt& n) const {
    743       return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
    744     }
    745 
    746     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
     817    NodeIt& first(NodeIt& n) const {
     818      return ResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
     819    }
     820
     821    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
    747822      e=first_out_edges.get(n);
    748823      return e;
    749824    }
    750825   
    751     //ROSSZ template<typename I> I& /*getF*/first(I& i) const { return /*getF*/first(i); }
    752     //ROSSZ template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
    753     //  return /*getF*/first(i, p); }
     826    //ROSSZ template<typename I> I& first(I& i) const { return first(i); }
     827    //ROSSZ template<typename I, typename P> I& first(I& i, const P& p) const {
     828    //  return first(i, p); }
    754829   
    755830    //template<typename I> I getNext(const I& i) const {
     
    758833
    759834    template< typename It > It first() const {
    760       It e; /*getF*/first(e); return e; }
     835      It e; first(e); return e; }
    761836
    762837    template< typename It > It first(const Node& v) const {
    763       It e; /*getF*/first(e, v); return e; }
     838      It e; first(e, v); return e; }
    764839
    765840    //Node head(const Edge& e) const { return graph->head(e); }
     
    839914    }
    840915
    841     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const {
    842       ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(e, n);
     916    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
     917      ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(e, n);
    843918      while (valid(e) && (dist.get(tail(e))/*+1!=*/>=dist.get(head(e))))
    844919        ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::next(e);
     
    857932    }
    858933
    859     NodeIt& /*getF*/first(NodeIt& n) const {
    860       return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::/*getF*/first(n);
     934    NodeIt& first(NodeIt& n) const {
     935      return ErasingResGraphWrapper<Graph, Number, FlowMap, CapacityMap>::first(n);
    861936    }
    862937
     
    875950    //Graph& getGraph() const { return (*graph); }
    876951   
    877     //template<typename I> I& /*getF*/first(I& i) const { return graph->/*getF*/first(i); }
    878     //template<typename I, typename P> I& /*getF*/first(I& i, const P& p) const {
    879     //  return graph->/*getF*/first(i, p); }
     952    //template<typename I> I& first(I& i) const { return graph->first(i); }
     953    //template<typename I, typename P> I& first(I& i, const P& p) const {
     954    //  return graph->first(i, p); }
    880955   
    881956    //template<typename I> I getNext(const I& i) const {
     
    884959
    885960    template< typename It > It first() const {
    886       It e; /*getF*/first(e); return e; }
     961      It e; first(e); return e; }
    887962
    888963    template< typename It > It first(const Node& v) const {
    889       It e; /*getF*/first(e, v); return e; }
     964      It e; first(e, v); return e; }
    890965
    891966    //Node head(const Edge& e) const { return graph->head(e); }
     
    9711046//     int edgeNum() const { return graph->edgeNum(); }
    9721047
    973 //     Node& /*getF*/first(Node& n) const { return graph->/*getF*/first(n); }
     1048//     Node& first(Node& n) const { return graph->first(n); }
    9741049
    9751050//     // Edge and SymEdge  is missing!!!!
     
    9771052
    9781053//     //FIXME
    979 //     OutEdgeIt& /*getF*/first(OutEdgeIt& e, const Node& n) const
     1054//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const
    9801055//       {
    9811056//      e.n=n;
    982 //      graph->/*getF*/first(e.o,n);
     1057//      graph->first(e.o,n);
    9831058//      while(graph->valid(e.o) && fmap.get(e.o)>=himap.get(e.o))
    9841059//        graph->goNext(e.o);
    9851060//      if(!graph->valid(e.o)) {
    986 //        graph->/*getF*/first(e.i,n);
     1061//        graph->first(e.i,n);
    9871062//        while(graph->valid(e.i) && fmap.get(e.i)<=lomap.get(e.i))
    9881063//          graph->goNext(e.i);
     
    9971072//   graph->goNext(e.o);
    9981073//   if(graph->valid(e.o)) return e;
    999 //   else graph->/*getF*/first(e.i,e.n);
     1074//   else graph->first(e.i,e.n);
    10001075//   }
    10011076//   else {
     
    10101085
    10111086//     //FIXME
    1012 //     InEdgeIt& /*getF*/first(InEdgeIt& e, const Node& n) const
     1087//     InEdgeIt& first(InEdgeIt& e, const Node& n) const
    10131088//       {
    10141089//      e.n=n;
    1015 //      graph->/*getF*/first(e.i,n);
     1090//      graph->first(e.i,n);
    10161091//      while(graph->valid(e.i) && fmap.get(e.i)>=himap.get(e.i))
    10171092//        graph->goNext(e.i);
    10181093//      if(!graph->valid(e.i)) {
    1019 //        graph->/*getF*/first(e.o,n);
     1094//        graph->first(e.o,n);
    10201095//        while(graph->valid(e.o) && fmap.get(e.o)<=lomap.get(e.o))
    10211096//          graph->goNext(e.o);
     
    10301105//   graph->goNext(e.i);
    10311106//   if(graph->valid(e.i)) return e;
    1032 //   else graph->/*getF*/first(e.o,e.n);
     1107//   else graph->first(e.o,e.n);
    10331108//   }
    10341109//   else {
     
    10461121
    10471122//     template< typename It > It first() const {
    1048 //       It e; /*getF*/first(e); return e; }
     1123//       It e; first(e); return e; }
    10491124
    10501125//     template< typename It > It first(Node v) const {
    1051 //       It e; /*getF*/first(e, v); return e; }
     1126//       It e; first(e, v); return e; }
    10521127
    10531128//     Node head(const Edge& e) const { return graph->head(e); }
Note: See TracChangeset for help on using the changeset viewer.