COIN-OR::LEMON - Graph Library

Changeset 2076:10681ee9d8ae in lemon-0.x


Ignore:
Timestamp:
05/12/06 11:51:45 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2739
Message:

Extenders modified

UGraphBaseExtender => UndirGraphExtender?
BpUGraphBaseExtender merged into BpUGraphExtender

Location:
lemon
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/base_extender.h

    r2031 r2076  
    3838  /// \brief BaseExtender for the UGraphs
    3939  template <typename Base>
    40   class UGraphBaseExtender : public Base {
     40  class UndirGraphExtender : public Base {
    4141
    4242  public:
     
    4949
    5050    class Edge : public UEdge {
    51       friend class UGraphBaseExtender;
     51      friend class UndirGraphExtender;
    5252
    5353    protected:
     
    276276  };
    277277
    278 
    279   /// \ingroup graphbits
    280   ///
    281   /// \brief BaseExtender for the BpUGraphs
    282   template <typename Base>
    283   class BpUGraphBaseExtender : public Base {
    284   public:
    285     typedef Base Parent;
    286     typedef BpUGraphBaseExtender Graph;
    287 
    288     typedef typename Parent::Node Node;
    289     typedef typename Parent::Edge UEdge;
    290 
    291 
    292     using Parent::first;
    293     using Parent::next;
    294 
    295     using Parent::id;
    296 
    297     class ANode : public Node {
    298       friend class BpUGraphBaseExtender;
    299     public:
    300       ANode() {}
    301       ANode(const Node& node) : Node(node) {
    302         LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
    303                      typename Parent::NodeSetError());
    304       }
    305       ANode(Invalid) : Node(INVALID) {}
    306     };
    307 
    308     void first(ANode& node) const {
    309       Parent::firstANode(static_cast<Node&>(node));
    310     }
    311     void next(ANode& node) const {
    312       Parent::nextANode(static_cast<Node&>(node));
    313     }
    314 
    315     int id(const ANode& node) const {
    316       return Parent::aNodeId(node);
    317     }
    318 
    319     class BNode : public Node {
    320       friend class BpUGraphBaseExtender;
    321     public:
    322       BNode() {}
    323       BNode(const Node& node) : Node(node) {
    324         LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
    325                      typename Parent::NodeSetError());
    326       }
    327       BNode(Invalid) : Node(INVALID) {}
    328     };
    329 
    330     void first(BNode& node) const {
    331       Parent::firstBNode(static_cast<Node&>(node));
    332     }
    333     void next(BNode& node) const {
    334       Parent::nextBNode(static_cast<Node&>(node));
    335     }
    336  
    337     int id(const BNode& node) const {
    338       return Parent::aNodeId(node);
    339     }
    340 
    341     Node source(const UEdge& edge) const {
    342       return aNode(edge);
    343     }
    344     Node target(const UEdge& edge) const {
    345       return bNode(edge);
    346     }
    347 
    348     void firstInc(UEdge& edge, bool& direction, const Node& node) const {
    349       if (Parent::aNode(node)) {
    350         Parent::firstOut(edge, node);
    351         direction = true;
    352       } else {
    353         Parent::firstIn(edge, node);
    354         direction = static_cast<UEdge&>(edge) == INVALID;
    355       }
    356     }
    357     void nextInc(UEdge& edge, bool& direction) const {
    358       if (direction) {
    359         Parent::nextOut(edge);
    360       } else {
    361         Parent::nextIn(edge);
    362         if (edge == INVALID) direction = true;
    363       }
    364     }
    365 
    366     int maxUEdgeId() const {
    367       return Parent::maxEdgeId();
    368     }
    369 
    370     UEdge uEdgeFromId(int id) const {
    371       return Parent::edgeFromId(id);
    372     }
    373 
    374     class Edge : public UEdge {
    375       friend class BpUGraphBaseExtender;
    376     protected:
    377       bool forward;
    378 
    379       Edge(const UEdge& edge, bool _forward)
    380         : UEdge(edge), forward(_forward) {}
    381 
    382     public:
    383       Edge() {}
    384       Edge (Invalid) : UEdge(INVALID), forward(true) {}
    385       bool operator==(const Edge& i) const {
    386         return UEdge::operator==(i) && forward == i.forward;
    387       }
    388       bool operator!=(const Edge& i) const {
    389         return UEdge::operator!=(i) || forward != i.forward;
    390       }
    391       bool operator<(const Edge& i) const {
    392         return UEdge::operator<(i) ||
    393           (!(i.forward<forward) && UEdge(*this)<UEdge(i));
    394       }
    395     };
    396 
    397     void first(Edge& edge) const {
    398       Parent::first(static_cast<UEdge&>(edge));
    399       edge.forward = true;
    400     }
    401 
    402     void next(Edge& edge) const {
    403       if (!edge.forward) {
    404         Parent::next(static_cast<UEdge&>(edge));
    405       }
    406       edge.forward = !edge.forward;
    407     }
    408 
    409     void firstOut(Edge& edge, const Node& node) const {
    410       if (Parent::aNode(node)) {
    411         Parent::firstOut(edge, node);
    412         edge.forward = true;
    413       } else {
    414         Parent::firstIn(edge, node);
    415         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    416       }
    417     }
    418     void nextOut(Edge& edge) const {
    419       if (edge.forward) {
    420         Parent::nextOut(edge);
    421       } else {
    422         Parent::nextIn(edge);
    423         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    424       }
    425     }
    426 
    427     void firstIn(Edge& edge, const Node& node) const {
    428       if (Parent::bNode(node)) {
    429         Parent::firstIn(edge, node);
    430         edge.forward = true;   
    431       } else {
    432         Parent::firstOut(edge, node);
    433         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    434       }
    435     }
    436     void nextIn(Edge& edge) const {
    437       if (edge.forward) {
    438         Parent::nextIn(edge);
    439       } else {
    440         Parent::nextOut(edge);
    441         edge.forward = static_cast<UEdge&>(edge) == INVALID;
    442       }
    443     }
    444 
    445     Node source(const Edge& edge) const {
    446       return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
    447     }
    448     Node target(const Edge& edge) const {
    449       return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
    450     }
    451 
    452     int id(const Edge& edge) const {
    453       return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
    454     }
    455     Edge edgeFromId(int id) const {
    456       return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
    457     }
    458     int maxEdgeId() const {
    459       return (Parent::maxId(UEdge()) << 1) + 1;
    460     }
    461 
    462     bool direction(const Edge& edge) const {
    463       return edge.forward;
    464     }
    465 
    466     Edge direct(const UEdge& edge, bool direction) const {
    467       return Edge(edge, direction);
    468     }
    469 
    470     int edgeNum() const {
    471       return 2 * Parent::edgeNum();
    472     }
    473 
    474     int uEdgeNum() const {
    475       return Parent::edgeNum();
    476     }
    477 
    478   };
    479 
    480278}
    481279
  • lemon/bits/graph_adaptor_extender.h

    r2041 r2076  
    454454    typedef typename Parent::UEdge UEdge;
    455455
    456     Node oppositeNode(const UEdge& edge, const Node& node) const {
    457       return source(edge) == node ?
    458         target(edge) : source(edge);
    459     }
    460 
    461456
    462457    int maxId(Node) const {
  • lemon/bits/graph_extender.h

    r2046 r2076  
    735735
    736736    typedef typename Parent::Node Node;
    737     typedef typename Parent::BNode BNode;
    738     typedef typename Parent::ANode ANode;
    739     typedef typename Parent::Edge Edge;
    740737    typedef typename Parent::UEdge UEdge;
     738
     739
     740    using Parent::first;
     741    using Parent::next;
     742
     743    using Parent::id;
     744
     745    class ANode : public Node {
     746      friend class BpUGraphExtender;
     747    public:
     748      ANode() {}
     749      ANode(const Node& node) : Node(node) {
     750        LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
     751                     typename Parent::NodeSetError());
     752      }
     753      ANode(Invalid) : Node(INVALID) {}
     754    };
     755
     756    void first(ANode& node) const {
     757      Parent::firstANode(static_cast<Node&>(node));
     758    }
     759    void next(ANode& node) const {
     760      Parent::nextANode(static_cast<Node&>(node));
     761    }
     762
     763    int id(const ANode& node) const {
     764      return Parent::aNodeId(node);
     765    }
     766
     767    class BNode : public Node {
     768      friend class BpUGraphExtender;
     769    public:
     770      BNode() {}
     771      BNode(const Node& node) : Node(node) {
     772        LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
     773                     typename Parent::NodeSetError());
     774      }
     775      BNode(Invalid) : Node(INVALID) {}
     776    };
     777
     778    void first(BNode& node) const {
     779      Parent::firstBNode(static_cast<Node&>(node));
     780    }
     781    void next(BNode& node) const {
     782      Parent::nextBNode(static_cast<Node&>(node));
     783    }
     784 
     785    int id(const BNode& node) const {
     786      return Parent::aNodeId(node);
     787    }
     788
     789    Node source(const UEdge& edge) const {
     790      return aNode(edge);
     791    }
     792    Node target(const UEdge& edge) const {
     793      return bNode(edge);
     794    }
     795
     796    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
     797      if (Parent::aNode(node)) {
     798        Parent::firstFromANode(edge, node);
     799        direction = true;
     800      } else {
     801        Parent::firstFromBNode(edge, node);
     802        direction = static_cast<UEdge&>(edge) == INVALID;
     803      }
     804    }
     805    void nextInc(UEdge& edge, bool& direction) const {
     806      if (direction) {
     807        Parent::nextFromANode(edge);
     808      } else {
     809        Parent::nextFromBNode(edge);
     810        if (edge == INVALID) direction = true;
     811      }
     812    }
     813
     814    class Edge : public UEdge {
     815      friend class BpUGraphExtender;
     816    protected:
     817      bool forward;
     818
     819      Edge(const UEdge& edge, bool _forward)
     820        : UEdge(edge), forward(_forward) {}
     821
     822    public:
     823      Edge() {}
     824      Edge (Invalid) : UEdge(INVALID), forward(true) {}
     825      bool operator==(const Edge& i) const {
     826        return UEdge::operator==(i) && forward == i.forward;
     827      }
     828      bool operator!=(const Edge& i) const {
     829        return UEdge::operator!=(i) || forward != i.forward;
     830      }
     831      bool operator<(const Edge& i) const {
     832        return UEdge::operator<(i) ||
     833          (!(i.forward<forward) && UEdge(*this)<UEdge(i));
     834      }
     835    };
     836
     837    void first(Edge& edge) const {
     838      Parent::first(static_cast<UEdge&>(edge));
     839      edge.forward = true;
     840    }
     841
     842    void next(Edge& edge) const {
     843      if (!edge.forward) {
     844        Parent::next(static_cast<UEdge&>(edge));
     845      }
     846      edge.forward = !edge.forward;
     847    }
     848
     849    void firstOut(Edge& edge, const Node& node) const {
     850      if (Parent::aNode(node)) {
     851        Parent::firstFromANode(edge, node);
     852        edge.forward = true;
     853      } else {
     854        Parent::firstFromBNode(edge, node);
     855        edge.forward = static_cast<UEdge&>(edge) == INVALID;
     856      }
     857    }
     858    void nextOut(Edge& edge) const {
     859      if (edge.forward) {
     860        Parent::nextFromANode(edge);
     861      } else {
     862        Parent::nextFromBNode(edge);
     863        edge.forward = static_cast<UEdge&>(edge) == INVALID;
     864      }
     865    }
     866
     867    void firstIn(Edge& edge, const Node& node) const {
     868      if (Parent::bNode(node)) {
     869        Parent::firstFromBNode(edge, node);
     870        edge.forward = true;   
     871      } else {
     872        Parent::firstFromANode(edge, node);
     873        edge.forward = static_cast<UEdge&>(edge) == INVALID;
     874      }
     875    }
     876    void nextIn(Edge& edge) const {
     877      if (edge.forward) {
     878        Parent::nextFromBNode(edge);
     879      } else {
     880        Parent::nextFromANode(edge);
     881        edge.forward = static_cast<UEdge&>(edge) == INVALID;
     882      }
     883    }
     884
     885    Node source(const Edge& edge) const {
     886      return edge.forward ? Parent::aNode(edge) : Parent::bNode(edge);
     887    }
     888    Node target(const Edge& edge) const {
     889      return edge.forward ? Parent::bNode(edge) : Parent::aNode(edge);
     890    }
     891
     892    int id(const Edge& edge) const {
     893      return (Parent::id(static_cast<const UEdge&>(edge)) << 1) +
     894        (edge.forward ? 0 : 1);
     895    }
     896    Edge edgeFromId(int id) const {
     897      return Edge(Parent::fromUEdgeId(id >> 1), (id & 1) == 0);
     898    }
     899    int maxEdgeId() const {
     900      return (Parent::maxUEdgeId(UEdge()) << 1) + 1;
     901    }
     902
     903    bool direction(const Edge& edge) const {
     904      return edge.forward;
     905    }
     906
     907    Edge direct(const UEdge& edge, bool direction) const {
     908      return Edge(edge, direction);
     909    }
     910
     911    int edgeNum() const {
     912      return 2 * Parent::uEdgeNum();
     913    }
     914
     915    int uEdgeNum() const {
     916      return Parent::uEdgeNum();
     917    }
    741918
    742919    Node oppositeNode(const UEdge& edge, const Node& node) const {
     
    745922    }
    746923
    747     using Parent::direct;
    748924    Edge direct(const UEdge& edge, const Node& node) const {
    749925      return Edge(edge, node == Parent::source(edge));
     
    765941    }
    766942    int maxId(Edge) const {
    767       return Parent::maxEdgeId();
     943      return maxEdgeId();
    768944    }
    769945    int maxId(UEdge) const {
  • lemon/edge_set.h

    r2031 r2076  
    338338  template <typename _Graph>
    339339  class ListUEdgeSet
    340     : public UEdgeSetExtender<UGraphBaseExtender<ListEdgeSetBase<_Graph> > > {
    341 
    342   public:
    343 
    344     typedef UEdgeSetExtender<UGraphBaseExtender<
     340    : public UEdgeSetExtender<UndirGraphExtender<ListEdgeSetBase<_Graph> > > {
     341
     342  public:
     343
     344    typedef UEdgeSetExtender<UndirGraphExtender<
    345345      ListEdgeSetBase<_Graph> > > Parent;
    346346   
     
    670670  template <typename _Graph>
    671671  class SmartUEdgeSet
    672     : public UEdgeSetExtender<UGraphBaseExtender<SmartEdgeSetBase<_Graph> > > {
    673 
    674   public:
    675 
    676     typedef UEdgeSetExtender<UGraphBaseExtender<
     672    : public UEdgeSetExtender<UndirGraphExtender<SmartEdgeSetBase<_Graph> > > {
     673
     674  public:
     675
     676    typedef UEdgeSetExtender<UndirGraphExtender<
    677677      SmartEdgeSetBase<_Graph> > > Parent;
    678678   
  • lemon/full_graph.h

    r2061 r2076  
    442442  };
    443443
    444   typedef UGraphExtender<UGraphBaseExtender<FullUGraphBase> >
     444  typedef UGraphExtender<UndirGraphExtender<FullUGraphBase> >
    445445  ExtendedFullUGraphBase;
    446446
     
    519519    };
    520520
    521     class Edge {
     521    class UEdge {
    522522      friend class FullBpUGraphBase;
    523523    protected:
    524524      int id;
    525525
    526       Edge(int _id) { id = _id;}
     526      UEdge(int _id) { id = _id;}
    527527    public:
    528       Edge() {}
    529       Edge (Invalid) { id = -1; }
    530       bool operator==(const Edge i) const {return id==i.id;}
    531       bool operator!=(const Edge i) const {return id!=i.id;}
    532       bool operator<(const Edge i) const {return id<i.id;}
     528      UEdge() {}
     529      UEdge (Invalid) { id = -1; }
     530      bool operator==(const UEdge i) const {return id==i.id;}
     531      bool operator!=(const UEdge i) const {return id!=i.id;}
     532      bool operator<(const UEdge i) const {return id<i.id;}
    533533    };
    534534
     
    569569    }
    570570 
    571     void first(Edge& edge) const {
     571    void first(UEdge& edge) const {
    572572      edge.id = _edgeNum - 1;
    573573    }
    574     void next(Edge& edge) const {
     574    void next(UEdge& edge) const {
    575575      --edge.id;
    576576    }
    577577
    578     void firstOut(Edge& edge, const Node& node) const {
     578    void firstFromANode(UEdge& edge, const Node& node) const {
    579579      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    580580      edge.id = (node.id >> 1) * _bNodeNum;
    581581    }
    582     void nextOut(Edge& edge) const {
     582    void nextFromANode(UEdge& edge) const {
    583583      ++(edge.id);
    584584      if (edge.id % _bNodeNum == 0) edge.id = -1;
    585585    }
    586586
    587     void firstIn(Edge& edge, const Node& node) const {
     587    void firstFromBNode(UEdge& edge, const Node& node) const {
    588588      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    589589      edge.id = (node.id >> 1);
    590590    }
    591     void nextIn(Edge& edge) const {
     591    void nextFromBNode(UEdge& edge) const {
    592592      edge.id += _bNodeNum;
    593593      if (edge.id >= _edgeNum) edge.id = -1;
     
    605605    }
    606606 
    607     static int id(const Edge& edge) {
     607    static int id(const UEdge& edge) {
    608608      return edge.id;
    609609    }
    610     static Edge edgeFromId(int id) {
    611       return Edge(id);
    612     }
    613     int maxEdgeId() const {
     610    static UEdge uEdgeFromId(int id) {
     611      return UEdge(id);
     612    }
     613    int maxUEdgeId() const {
    614614      return _edgeNum - 1;
    615615    }
     
    635635    }
    636636
    637     Node aNode(const Edge& edge) const {
     637    Node aNode(const UEdge& edge) const {
    638638      return Node((edge.id / _bNodeNum) << 1);
    639639    }
    640     Node bNode(const Edge& edge) const {
     640    Node bNode(const UEdge& edge) const {
    641641      return Node(((edge.id % _bNodeNum) << 1) + 1);
    642642    }
     
    664664
    665665    typedef True EdgeNumTag;
    666     int edgeNum() const { return _edgeNum; }
     666    int uEdgeNum() const { return _edgeNum; }
    667667
    668668  };
    669669
    670670
    671   typedef BpUGraphExtender< BpUGraphBaseExtender<
    672     FullBpUGraphBase> > ExtendedFullBpUGraphBase;
     671  typedef BpUGraphExtender<FullBpUGraphBase> ExtendedFullBpUGraphBase;
    673672
    674673
  • lemon/grid_ugraph.h

    r2037 r2076  
    348348
    349349
    350   typedef UGraphExtender<UGraphBaseExtender<
    351     GridUGraphBase> > ExtendedGridUGraphBase;
     350  typedef UGraphExtender<UndirGraphExtender<GridUGraphBase> >
     351  ExtendedGridUGraphBase;
    352352
    353353  /// \ingroup graphs
  • lemon/list_graph.h

    r2031 r2076  
    567567  /**************** Undirected List Graph ****************/
    568568
    569   typedef UGraphExtender<UGraphBaseExtender<
    570     ListGraphBase> > ExtendedListUGraphBase;
     569  typedef UGraphExtender<UndirGraphExtender<ListGraphBase> >
     570  ExtendedListUGraphBase;
    571571
    572572  /// \addtogroup graphs
     
    652652    };
    653653
    654     struct EdgeT {
     654    struct UEdgeT {
    655655      int aNode, prev_out, next_out;
    656656      int bNode, prev_in, next_in;
     
    660660    std::vector<NodeT> bNodes;
    661661
    662     std::vector<EdgeT> edges;
     662    std::vector<UEdgeT> edges;
    663663
    664664    int first_anode;
     
    686686    };
    687687
    688     class Edge {
     688    class UEdge {
    689689      friend class ListBpUGraphBase;
    690690    protected:
    691691      int id;
    692692
    693       explicit Edge(int _id) { id = _id;}
     693      explicit UEdge(int _id) { id = _id;}
    694694    public:
    695       Edge() {}
    696       Edge (Invalid) { id = -1; }
    697       bool operator==(const Edge i) const {return id==i.id;}
    698       bool operator!=(const Edge i) const {return id!=i.id;}
    699       bool operator<(const Edge i) const {return id<i.id;}
     695      UEdge() {}
     696      UEdge (Invalid) { id = -1; }
     697      bool operator==(const UEdge i) const {return id==i.id;}
     698      bool operator!=(const UEdge i) const {return id!=i.id;}
     699      bool operator<(const UEdge i) const {return id<i.id;}
    700700    };
    701701
     
    741741    }
    742742 
    743     void first(Edge& edge) const {
     743    void first(UEdge& edge) const {
    744744      int aNodeId = first_anode;
    745745      while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) {
     
    753753      }
    754754    }
    755     void next(Edge& edge) const {
     755    void next(UEdge& edge) const {
    756756      int aNodeId = edges[edge.id].aNode >> 1;
    757757      edge.id = edges[edge.id].next_out;
     
    771771    }
    772772
    773     void firstOut(Edge& edge, const Node& node) const {
     773    void firstFromANode(UEdge& edge, const Node& node) const {
    774774      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    775775      edge.id = aNodes[node.id >> 1].first_edge;
    776776    }
    777     void nextOut(Edge& edge) const {
     777    void nextFromANode(UEdge& edge) const {
    778778      edge.id = edges[edge.id].next_out;
    779779    }
    780780
    781     void firstIn(Edge& edge, const Node& node) const {
     781    void firstFromBNode(UEdge& edge, const Node& node) const {
    782782      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    783783      edge.id = bNodes[node.id >> 1].first_edge;
    784784    }
    785     void nextIn(Edge& edge) const {
     785    void nextFromBNode(UEdge& edge) const {
    786786      edge.id = edges[edge.id].next_in;
    787787    }
     
    798798    }
    799799 
    800     static int id(const Edge& edge) {
     800    static int id(const UEdge& edge) {
    801801      return edge.id;
    802802    }
    803     static Edge edgeFromId(int id) {
    804       return Edge(id);
    805     }
    806     int maxEdgeId() const {
     803    static UEdge uEdgeFromId(int id) {
     804      return UEdge(id);
     805    }
     806    int maxUEdgeId() const {
    807807      return edges.size();
    808808    }
     
    828828    }
    829829
    830     Node aNode(const Edge& edge) const {
     830    Node aNode(const UEdge& edge) const {
    831831      return Node(edges[edge.id].aNode);
    832832    }
    833     Node bNode(const Edge& edge) const {
     833    Node bNode(const UEdge& edge) const {
    834834      return Node(edges[edge.id].bNode);
    835835    }
     
    875875    }
    876876
    877     Edge addEdge(const Node& source, const Node& target) {
     877    UEdge addEdge(const Node& source, const Node& target) {
    878878      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
    879879      int edgeId;
     
    883883      } else {
    884884        edgeId = edges.size();
    885         edges.push_back(EdgeT());
     885        edges.push_back(UEdgeT());
    886886      }
    887887      if ((source.id & 1) == 0) {
     
    904904      }
    905905      bNodes[edges[edgeId].bNode >> 1].first_edge = edgeId;
    906       return Edge(edgeId);
     906      return UEdge(edgeId);
    907907    }
    908908
     
    919919    }
    920920
    921     void erase(const Edge& edge) {
     921    void erase(const UEdge& edge) {
    922922      if (edges[edge.id].prev_out != -1) {
    923923        edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out;
     
    954954
    955955
    956   typedef BpUGraphExtender< BpUGraphBaseExtender<
    957     ListBpUGraphBase> > ExtendedListBpUGraphBase;
     956  typedef BpUGraphExtender< ListBpUGraphBase > ExtendedListBpUGraphBase;
    958957
    959958  /// \ingroup graphs
  • lemon/smart_graph.h

    r2031 r2076  
    120120    static int id(Edge e) { return e.n; }
    121121
     122    /// \brief Returns the node from its \c id.
     123    ///
     124    /// Returns the node from its \c id. If there is not node
     125    /// with the given id the effect of the function is undefinied.
    122126    static Node nodeFromId(int id) { return Node(id);}
    123127
     128    /// \brief Returns the edge from its \c id.
     129    ///
     130    /// Returns the edge from its \c id. If there is not edge
     131    /// with the given id the effect of the function is undefinied.
    124132    static Edge edgeFromId(int id) { return Edge(id);}
    125133
     
    351359  /**************** Undirected List Graph ****************/
    352360
    353   typedef UGraphExtender<UGraphBaseExtender<SmartGraphBase> >
     361  typedef UGraphExtender<UndirGraphExtender<SmartGraphBase> >
    354362  ExtendedSmartUGraphBase;
    355363
     
    389397    };
    390398
    391     struct EdgeT {
     399    struct UEdgeT {
    392400      int aNode, next_out;
    393401      int bNode, next_in;
     
    397405    std::vector<NodeT> bNodes;
    398406
    399     std::vector<EdgeT> edges;
     407    std::vector<UEdgeT> edges;
    400408
    401409  public:
     
    415423    };
    416424
    417     class Edge {
     425    class UEdge {
    418426      friend class SmartBpUGraphBase;
    419427    protected:
    420428      int id;
    421429
    422       Edge(int _id) { id = _id;}
     430      UEdge(int _id) { id = _id;}
    423431    public:
    424       Edge() {}
    425       Edge (Invalid) { id = -1; }
    426       bool operator==(const Edge i) const {return id==i.id;}
    427       bool operator!=(const Edge i) const {return id!=i.id;}
    428       bool operator<(const Edge i) const {return id<i.id;}
     432      UEdge() {}
     433      UEdge (Invalid) { id = -1; }
     434      bool operator==(const UEdge i) const {return id==i.id;}
     435      bool operator!=(const UEdge i) const {return id!=i.id;}
     436      bool operator<(const UEdge i) const {return id<i.id;}
    429437    };
    430438
     
    459467    }
    460468 
    461     void first(Edge& edge) const {
     469    void first(UEdge& edge) const {
    462470      edge.id = edges.size() - 1;
    463471    }
    464     void next(Edge& edge) const {
     472    void next(UEdge& edge) const {
    465473      --edge.id;
    466474    }
    467475
    468     void firstOut(Edge& edge, const Node& node) const {
     476    void firstFromANode(UEdge& edge, const Node& node) const {
    469477      LEMON_ASSERT((node.id & 1) == 0, NodeSetError());
    470478      edge.id = aNodes[node.id >> 1].first;
    471479    }
    472     void nextOut(Edge& edge) const {
     480    void nextFromANode(UEdge& edge) const {
    473481      edge.id = edges[edge.id].next_out;
    474482    }
    475483
    476     void firstIn(Edge& edge, const Node& node) const {
     484    void firstFromBNode(UEdge& edge, const Node& node) const {
    477485      LEMON_ASSERT((node.id & 1) == 1, NodeSetError());
    478486      edge.id = bNodes[node.id >> 1].first;
    479487    }
    480     void nextIn(Edge& edge) const {
     488    void nextFromBNode(UEdge& edge) const {
    481489      edge.id = edges[edge.id].next_in;
    482490    }
     
    493501    }
    494502 
    495     static int id(const Edge& edge) {
     503    static int id(const UEdge& edge) {
    496504      return edge.id;
    497505    }
    498     static Edge edgeFromId(int id) {
    499       return Edge(id);
    500     }
    501     int maxEdgeId() const {
     506    static UEdge uEdgeFromId(int id) {
     507      return UEdge(id);
     508    }
     509    int maxUEdgeId() const {
    502510      return edges.size();
    503511    }
     
    523531    }
    524532
    525     Node aNode(const Edge& edge) const {
     533    Node aNode(const UEdge& edge) const {
    526534      return Node(edges[edge.id].aNode);
    527535    }
    528     Node bNode(const Edge& edge) const {
     536    Node bNode(const UEdge& edge) const {
    529537      return Node(edges[edge.id].bNode);
    530538    }
     
    552560    }
    553561
    554     Edge addEdge(const Node& source, const Node& target) {
     562    UEdge addEdge(const Node& source, const Node& target) {
    555563      LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError());
    556       EdgeT edgeT;
     564      UEdgeT edgeT;
    557565      if ((source.id & 1) == 0) {
    558566        edgeT.aNode = source.id;
     
    567575      bNodes[edgeT.bNode >> 1].first = edges.size();
    568576      edges.push_back(edgeT);
    569       return Edge(edges.size() - 1);
     577      return UEdge(edges.size() - 1);
    570578    }
    571579
     
    582590
    583591    typedef True EdgeNumTag;
    584     int edgeNum() const { return edges.size(); }
     592    int uEdgeNum() const { return edges.size(); }
    585593
    586594  };
    587595
    588596
    589   typedef BpUGraphExtender< BpUGraphBaseExtender<
    590     SmartBpUGraphBase> > ExtendedSmartBpUGraphBase;
     597  typedef BpUGraphExtender<SmartBpUGraphBase> ExtendedSmartBpUGraphBase;
    591598
    592599  /// \ingroup graphs
Note: See TracChangeset for help on using the changeset viewer.