COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 238:ad3bdd78f4f6 in lemon-0.x


Ignore:
Timestamp:
03/23/04 14:31:02 (20 years ago)
Author:
marci
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@336
Message:

.

Location:
src/work
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • src/work/iterator_bfs_demo.cc

    r236 r238  
    262262      cout << endl;
    263263    }
     264//     for(GW::EdgeIt e=gw.first<GW::EdgeIt>(); gw.valid(e); gw.next(e)) {
     265//       cout << edge_name.get(e) << " ";
     266//     }
     267//     cout << endl;
    264268
    265269    cout << "bfs from t ..." << endl;

  • src/work/marci/graph_wrapper.h

    r237 r238  
    334334    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt OutEdgeIt;
    335335
     336    RevGraphWrapper(GraphWrapper _gw) :
     337      GraphWrapperSkeleton<GraphWrapper>(_gw) { } 
     338
    336339    Node head(const Edge& e) const
    337340      { return GraphWrapperSkeleton<GraphWrapper>::tail(e); }
    338341    Node tail(const Edge& e) const
    339342      { return GraphWrapperSkeleton<GraphWrapper>::head(e); }
    340    
    341     RevGraphWrapper(GraphWrapper _gw) :
    342       GraphWrapperSkeleton<GraphWrapper>(_gw) { } 
    343343  };
    344344
    345345
    346 
    347 //   template<typename Graph>
     346//   template<typename GraphWrapper>
    348347//   class UndirGraphWrapper {
    349348//   protected:
    350 //     Graph* graph;
    351  
     349//     //Graph* graph;
     350//     GraphWrapper gw;
     351
    352352//   public:
    353 //     typedef Graph BaseGraph;
    354 
    355 //     typedef typename Graph::Node Node;
    356 //     typedef typename Graph::NodeIt NodeIt;
     353//     typedef GraphWrapper BaseGraph;
     354
     355//     typedef typename GraphWrapper::Node Node;
     356//     typedef typename GraphWrapper::NodeIt NodeIt;
    357357
    358358//     //typedef typename Graph::Edge Edge;
    … …  
    363363
    364364//     //private:
    365 //     typedef typename Graph::Edge GraphEdge;
    366 //     typedef typename Graph::OutEdgeIt GraphOutEdgeIt;
    367 //     typedef typename Graph::InEdgeIt GraphInEdgeIt;
     365//     typedef typename GraphWrapper::Edge GraphEdge;
     366//     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
     367//     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
    368368//     //public:
    369369
    370370//     //UndirGraphWrapper() : graph(0) { }
    371 //     UndirGraphWrapper(Graph& _graph) : graph(&_graph) { }
    372 
    373 //     void setGraph(Graph& _graph) { graph = &_graph; }
    374 //     Graph& getGraph() const { return (*graph); }
     371//     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
     372
     373//     //void setGraph(Graph& _graph) { graph = &_graph; }
     374//     //Graph& getGraph() const { return (*graph); }
    375375 
    376376//     class Edge {
    377 //       friend class UndirGraphWrapper<Graph>;
     377//       friend class UndirGraphWrapper<GraphWrapper>;
    378378//       bool out_or_in; //true iff out
    379379//       GraphOutEdgeIt out;
    … …  
    400400
    401401//     class OutEdgeIt : public Edge {
    402 //       friend class UndirGraphWrapper<Graph>;
     402//       friend class UndirGraphWrapper<GraphWrapper>;
    403403//     public:
    404404//       OutEdgeIt() : Edge() { }
    405405//       OutEdgeIt(const Invalid& i) : Edge(i) { }
    406 //       OutEdgeIt(const UndirGraphWrapper& _G, const Node& n) : Edge() {
     406//       OutEdgeIt(const UndirGraphWrapper<GraphWrapper>& _G, const Node& n)
     407//      : Edge() {
    407408//      out_or_in=true;
    408 //      _G.graph->first(out, n);
    409 //      if (!(_G.graph->valid(out))) {
     409//      _G.gw.first(out, n);
     410//      if (!(_G.gw.valid(out))) {
    410411//        out_or_in=false;
    411 //        _G.graph->first(in, n);
     412//        _G.gw.first(in, n);
    412413//      }
    413414//       }
    … …  
    416417//     OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
    417418//       e.out_or_in=true;
    418 //       graph->first(e.out, n);
    419 //       if (!(graph->valid(e.out))) {
     419//       gw.first(e.out, n);
     420//       if (!(gw.valid(e.out))) {
    420421//      e.out_or_in=false;
    421 //      graph->first(e.in, n);
     422//      gw.first(e.in, n);
    422423//       }
    423424//       return e;
    … …  
    426427//     OutEdgeIt& next(OutEdgeIt& e) const {
    427428//       if (e.out_or_in) {
    428 //      Node n=graph->tail(e.out);
    429 //      graph->next(e.out);
    430 //      if (!graph->valid(e.out)) {
     429//      Node n=gw.tail(e.out);
     430//      gw.next(e.out);
     431//      if (!gw.valid(e.out)) {
    431432//        e.out_or_in=false;
    432 //        graph->first(e.in, n);
     433//        gw.first(e.in, n);
    433434//      }
    434435//       } else {
    435 //      graph->next(e.in);
     436//      gw.next(e.in);
    436437//       }
    437438//       return e;
    … …  
    439440
    440441//     Node aNode(const OutEdgeIt& e) const {
    441 //       if (e.out_or_in) return graph->tail(e); else return graph->head(e); }
     442//       if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
    442443//     Node bNode(const OutEdgeIt& e) const {
    443 //       if (e.out_or_in) return graph->head(e); else return graph->tail(e); }
     444//       if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
    444445
    445446//     typedef OutEdgeIt InEdgeIt;
    446447
    447 //     template<typename I> I& first(I& i) const { return graph->first(i); }
     448//     template<typename I> I& first(I& i) const { return gw.first(i); }
    448449// //     template<typename I, typename P> I& first(I& i, const P& p) const {
    449450// //       return graph->first(i, p); }
    450451   
    451452//     template<typename I> I getNext(const I& i) const {
    452 //       return graph->getNext(i); }
    453 //     template<typename I> I& next(I &i) const { return graph->next(i); }   
     453//       return gw.getNext(i); }
     454//     template<typename I> I& next(I &i) const { return gw.next(i); }   
    454455
    455456//     template< typename It > It first() const {
    … …  
    459460//       It e; first(e, v); return e; }
    460461
    461 //     Node head(const Edge& e) const { return graph->head(e); }
    462 //     Node tail(const Edge& e) const { return graph->tail(e); }
     462//     Node head(const Edge& e) const { return gw.head(e); }
     463//     Node tail(const Edge& e) const { return gw.tail(e); }
    463464
    464465//     template<typename I> bool valid(const I& i) const
    465 //       { return graph->valid(i); }
     466//       { return gw.valid(i); }
    466467 
    467468//     //template<typename I> void setInvalid(const I &i);
    468469//     //{ return graph->setInvalid(i); }
    469470
    470 //     int nodeNum() const { return graph->nodeNum(); }
    471 //     int edgeNum() const { return graph->edgeNum(); }
     471//     int nodeNum() const { return gw.nodeNum(); }
     472//     int edgeNum() const { return gw.edgeNum(); }
    472473 
    473474// //     template<typename I> Node aNode(const I& e) const {
    … …  
    476477// //       return graph->bNode(e); }
    477478 
    478 //     Node addNode() const { return graph->addNode(); }
     479//     Node addNode() const { return gw.addNode(); }
    479480// // FIXME: ez igy nem jo, mert nem
    480481// //    Edge addEdge(const Node& tail, const Node& head) const {
    481482// //      return graph->addEdge(tail, head); }
    482483 
    483 //     template<typename I> void erase(const I& i) const { graph->erase(i); }
    484  
    485 //     void clear() const { graph->clear(); }
    486    
    487 //     template<typename T> class NodeMap : public Graph::NodeMap<T> {
     484//     template<typename I> void erase(const I& i) const { gw.erase(i); }
     485 
     486//     void clear() const { gw.clear(); }
     487   
     488//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
    488489//     public:
    489 //       NodeMap(const UndirGraphWrapper<Graph>& _G) :
    490 //      Graph::NodeMap<T>(_G.getGraph()) { }
    491 //       NodeMap(const UndirGraphWrapper<Graph>& _G, T a) :
    492 //      Graph::NodeMap<T>(_G.getGraph(), a) { }
     490//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
     491//      GraphWrapper::NodeMap<T>(_G.gw) { }
     492//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
     493//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
    493494//     };
    494495
    495 //     template<typename T> class EdgeMap : public Graph::EdgeMap<T> {
     496//     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
    496497//     public:
    497 //       EdgeMap(const UndirGraphWrapper<Graph>& _G) :
    498 //      Graph::EdgeMap<T>(_G.getGraph()) { }
    499 //       EdgeMap(const UndirGraphWrapper<Graph>& _G, T a) :
    500 //      Graph::EdgeMap<T>(_G.getGraph(), a) { }
     498//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
     499//      GraphWrapper::EdgeMap<T>(_G.gw) { }
     500//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
     501//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
    501502//     };
    502503//   };
    … …  
    504505
    505506  template<typename GraphWrapper>
    506   class UndirGraphWrapper {
     507  class UndirGraphWrapper : public GraphWrapperSkeleton<GraphWrapper> {
    507508  protected:
    508     //Graph* graph;
    509     GraphWrapper gw;
     509//    GraphWrapper gw;
    510510
    511511  public:
    512     typedef GraphWrapper BaseGraph;
    513 
    514     typedef typename GraphWrapper::Node Node;
    515     typedef typename GraphWrapper::NodeIt NodeIt;
    516 
    517     //typedef typename Graph::Edge Edge;
    518     //typedef typename Graph::OutEdgeIt OutEdgeIt;
    519     //typedef typename Graph::InEdgeIt InEdgeIt;
    520     //typedef typename Graph::SymEdgeIt SymEdgeIt;
    521     //typedef typename Graph::EdgeIt EdgeIt;
     512    //typedef GraphWrapper BaseGraph;
     513
     514    typedef typename GraphWrapperSkeleton<GraphWrapper>::Node Node;
     515    typedef typename GraphWrapperSkeleton<GraphWrapper>::NodeIt NodeIt;
    522516
    523517    //private:
    524     typedef typename GraphWrapper::Edge GraphEdge;
    525     typedef typename GraphWrapper::OutEdgeIt GraphOutEdgeIt;
    526     typedef typename GraphWrapper::InEdgeIt GraphInEdgeIt;
     518    typedef typename GraphWrapperSkeleton<GraphWrapper>::Edge GraphEdge;
     519    typedef typename GraphWrapperSkeleton<GraphWrapper>::OutEdgeIt GraphOutEdgeIt;
     520    typedef typename GraphWrapperSkeleton<GraphWrapper>::InEdgeIt GraphInEdgeIt;
    527521    //public:
    528522
    529523    //UndirGraphWrapper() : graph(0) { }
    530     UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
     524    UndirGraphWrapper(GraphWrapper _gw) :
     525      GraphWrapperSkeleton<GraphWrapper>(_gw) { } 
     526
     527    //UndirGraphWrapper(GraphWrapper _gw) : gw(_gw) { }
    531528
    532529    //void setGraph(Graph& _graph) { graph = &_graph; }
    … …  
    574571    };
    575572
     573    typedef OutEdgeIt InEdgeIt;
     574
     575    class EdgeIt : public Edge {
     576      friend class UndirGraphWrapper<GraphWrapper>;
     577    protected:
     578      NodeIt v;
     579    public:
     580      EdgeIt() : Edge() { }
     581      EdgeIt(const Invalid& i) : Edge(i) { }
     582      EdgeIt(const UndirGraphWrapper<GraphWrapper>& _G)
     583        : Edge() {
     584        out_or_in=true;
     585        //Node v;
     586        _G.first(v);
     587        if (_G.valid(v)) _G.gw.first(out); else out=INVALID;
     588        while (_G.valid(v) && !_G.gw.valid(out)) {
     589          _G.gw.next(v);
     590          if (_G.valid(v)) _G.gw.first(out);
     591        }
     592      }
     593    };
     594
    576595    OutEdgeIt& first(OutEdgeIt& e, const Node& n) const {
    577596      e.out_or_in=true;
    … …  
    583602      return e;
    584603    }
     604
     605    EdgeIt& first(EdgeIt& e) const {
     606      e.out_or_in=true;
     607      //NodeIt v;
     608      first(e.v);
     609      if (valid(e.v)) gw.first(e.out, e.v); else e.out=INVALID;
     610      while (valid(e.v) && !gw.valid(e.out)) {
     611        gw.next(e.v);
     612        if (valid(e.v)) gw.first(e.out, e.v);
     613      }
     614      return e;
     615    }
     616
     617    template<typename I> I& first(I& i) const { return gw.first(i); }
     618    template<typename I, typename P> I& first(I& i, const P& p) const {
     619      return graph->first(i, p); }
    585620
    586621    OutEdgeIt& next(OutEdgeIt& e) const {
    … …  
    598633    }
    599634
     635    EdgeIt& next(EdgeIt& e) const {
     636      //NodeIt v=tail(e);
     637      gw.next(e.out);
     638      while (valid(e.v) && !gw.valid(e.out)) {
     639        next(e.v);
     640        if (valid(e.v)) gw.first(e.out, e.v);
     641      }
     642      return e;
     643    }
     644
     645    template<typename I> I& next(I &i) const { return gw.next(i); }   
     646   
     647    template<typename I> I getNext(const I& i) const {
     648      return gw.getNext(i); }
     649
     650    template< typename It > It first() const {
     651      It e; first(e); return e; }
     652
     653    template< typename It > It first(const Node& v) const {
     654      It e; first(e, v); return e; }
     655
     656//    Node head(const Edge& e) const { return gw.head(e); }
     657//    Node tail(const Edge& e) const { return gw.tail(e); }
     658
     659//    template<typename I> bool valid(const I& i) const
     660//      { return gw.valid(i); }
     661 
     662//    int nodeNum() const { return gw.nodeNum(); }
     663//    int edgeNum() const { return gw.edgeNum(); }
     664 
     665//     template<typename I> Node aNode(const I& e) const {
     666//       return graph->aNode(e); }
     667//     template<typename I> Node bNode(const I& e) const {
     668//       return graph->bNode(e); }
     669
    600670    Node aNode(const OutEdgeIt& e) const {
    601671      if (e.out_or_in) return gw.tail(e); else return gw.head(e); }
    602672    Node bNode(const OutEdgeIt& e) const {
    603673      if (e.out_or_in) return gw.head(e); else return gw.tail(e); }
    604 
    605     typedef OutEdgeIt InEdgeIt;
    606 
    607     template<typename I> I& first(I& i) const { return gw.first(i); }
    608 //     template<typename I, typename P> I& first(I& i, const P& p) const {
    609 //       return graph->first(i, p); }
    610    
    611     template<typename I> I getNext(const I& i) const {
    612       return gw.getNext(i); }
    613     template<typename I> I& next(I &i) const { return gw.next(i); }   
    614 
    615     template< typename It > It first() const {
    616       It e; first(e); return e; }
    617 
    618     template< typename It > It first(const Node& v) const {
    619       It e; first(e, v); return e; }
    620 
    621     Node head(const Edge& e) const { return gw.head(e); }
    622     Node tail(const Edge& e) const { return gw.tail(e); }
    623 
    624     template<typename I> bool valid(const I& i) const
    625       { return gw.valid(i); }
    626  
    627     //template<typename I> void setInvalid(const I &i);
    628     //{ return graph->setInvalid(i); }
    629 
    630     int nodeNum() const { return gw.nodeNum(); }
    631     int edgeNum() const { return gw.edgeNum(); }
    632  
    633 //     template<typename I> Node aNode(const I& e) const {
    634 //       return graph->aNode(e); }
    635 //     template<typename I> Node bNode(const I& e) const {
    636 //       return graph->bNode(e); }
    637  
    638     Node addNode() const { return gw.addNode(); }
     674 
     675//    Node addNode() const { return gw.addNode(); }
     676
    639677// FIXME: ez igy nem jo, mert nem
    640678//    Edge addEdge(const Node& tail, const Node& head) const {
    641679//      return graph->addEdge(tail, head); }
    642680 
    643     template<typename I> void erase(const I& i) const { gw.erase(i); }
    644  
    645     void clear() const { gw.clear(); }
    646    
    647     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
    648     public:
    649       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
    650         GraphWrapper::NodeMap<T>(_G.gw) { }
    651       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
    652         GraphWrapper::NodeMap<T>(_G.gw, a) { }
    653     };
    654 
    655     template<typename T> class EdgeMap : public GraphWrapper::EdgeMap<T> {
    656     public:
    657       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
    658         GraphWrapper::EdgeMap<T>(_G.gw) { }
    659       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
    660         GraphWrapper::EdgeMap<T>(_G.gw, a) { }
    661     };
    662   };
     681//    template<typename I> void erase(const I& i) const { gw.erase(i); }
     682 
     683//    void clear() const { gw.clear(); }
     684   
     685//     template<typename T> class NodeMap : public GraphWrapper::NodeMap<T> {
     686//     public:
     687//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
     688//      GraphWrapper::NodeMap<T>(_G.gw) { }
     689//       NodeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
     690//      GraphWrapper::NodeMap<T>(_G.gw, a) { }
     691//     };
     692
     693//     template<typename T> class EdgeMap :
     694//       public GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T> {
     695//     public:
     696//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G) :
     697//      GraphWrapperSkeleton<GraphWrapper>::EdgeMap<T>(_G.gw) { }
     698//       EdgeMap(const UndirGraphWrapper<GraphWrapper>& _G, T a) :
     699//      GraphWrapper::EdgeMap<T>(_G.gw, a) { }
     700//     };
     701   };
    663702
    664703
Note: See TracChangeset for help on using the changeset viewer.