COIN-OR::LEMON - Graph Library

Changeset 1909:2d806130e700 in lemon-0.x for lemon/bits/graph_extender.h


Ignore:
Timestamp:
01/26/06 16:42:13 (14 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2484
Message:

Undir -> U transition

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r1875 r1909  
    6262
    6363  template <typename _Base>
    64   class UndirGraphExtender : public _Base {
     64  class UGraphExtender : public _Base {
    6565    typedef _Base Parent;
    66     typedef UndirGraphExtender Graph;
     66    typedef UGraphExtender Graph;
    6767
    6868  public:
    6969
    70     typedef typename Parent::Edge UndirEdge;
     70    typedef typename Parent::Edge UEdge;
    7171    typedef typename Parent::Node Node;
    7272
    73     class Edge : public UndirEdge {
    74       friend class UndirGraphExtender;
     73    class Edge : public UEdge {
     74      friend class UGraphExtender;
    7575
    7676    protected:
     
    7979      bool forward;
    8080
    81       Edge(const UndirEdge &ue, bool _forward) :
    82         UndirEdge(ue), forward(_forward) {}
     81      Edge(const UEdge &ue, bool _forward) :
     82        UEdge(ue), forward(_forward) {}
    8383
    8484    public:
     
    8686
    8787      /// Invalid edge constructor
    88       Edge(Invalid i) : UndirEdge(i), forward(true) {}
     88      Edge(Invalid i) : UEdge(i), forward(true) {}
    8989
    9090      bool operator==(const Edge &that) const {
    91         return forward==that.forward && UndirEdge(*this)==UndirEdge(that);
     91        return forward==that.forward && UEdge(*this)==UEdge(that);
    9292      }
    9393      bool operator!=(const Edge &that) const {
    94         return forward!=that.forward || UndirEdge(*this)!=UndirEdge(that);
     94        return forward!=that.forward || UEdge(*this)!=UEdge(that);
    9595      }
    9696      bool operator<(const Edge &that) const {
    9797        return forward<that.forward ||
    98           (!(that.forward<forward) && UndirEdge(*this)<UndirEdge(that));
     98          (!(that.forward<forward) && UEdge(*this)<UEdge(that));
    9999      }
    100100    };
     
    127127    }
    128128
    129     Node oppositeNode(const Node &n, const UndirEdge &e) const {
     129    Node oppositeNode(const Node &n, const UEdge &e) const {
    130130      if( n == Parent::source(e))
    131131        return Parent::target(e);
     
    138138    /// \brief Directed edge from an undirected edge and a source node.
    139139    ///
    140     /// Returns a (directed) Edge corresponding to the specified UndirEdge
     140    /// Returns a (directed) Edge corresponding to the specified UEdge
    141141    /// and source Node.
    142142    ///
    143     Edge direct(const UndirEdge &ue, const Node &s) const {
     143    Edge direct(const UEdge &ue, const Node &s) const {
    144144      return Edge(ue, s == source(ue));
    145145    }
     
    147147    /// \brief Directed edge from an undirected edge.
    148148    ///
    149     /// Returns a directed edge corresponding to the specified UndirEdge.
     149    /// Returns a directed edge corresponding to the specified UEdge.
    150150    /// If the given bool is true the given undirected edge and the
    151151    /// returned edge have the same source node.
    152     Edge direct(const UndirEdge &ue, bool d) const {
     152    Edge direct(const UEdge &ue, bool d) const {
    153153      return Edge(ue, d);
    154154    }
     
    183183    void firstOut(Edge &e, const Node &n) const {
    184184      Parent::firstIn(e,n);
    185       if( UndirEdge(e) != INVALID ) {
     185      if( UEdge(e) != INVALID ) {
    186186        e.forward = false;
    187187      }
     
    195195        Node n = Parent::target(e);
    196196        Parent::nextIn(e);
    197         if( UndirEdge(e) == INVALID ) {
     197        if( UEdge(e) == INVALID ) {
    198198          Parent::firstOut(e, n);
    199199          e.forward = true;
     
    207207    void firstIn(Edge &e, const Node &n) const {
    208208      Parent::firstOut(e,n);
    209       if( UndirEdge(e) != INVALID ) {
     209      if( UEdge(e) != INVALID ) {
    210210        e.forward = false;
    211211      }
     
    219219        Node n = Parent::source(e);
    220220        Parent::nextOut(e);
    221         if( UndirEdge(e) == INVALID ) {
     221        if( UEdge(e) == INVALID ) {
    222222          Parent::firstIn(e, n);
    223223          e.forward = true;
     
    229229    }
    230230
    231     void firstInc(UndirEdge &e, const Node &n) const {
     231    void firstInc(UEdge &e, const Node &n) const {
    232232      Parent::firstOut(e, n);
    233233      if (e != INVALID) return;
    234234      Parent::firstIn(e, n);
    235235    }
    236     void nextInc(UndirEdge &e, const Node &n) const {
     236    void nextInc(UEdge &e, const Node &n) const {
    237237      if (Parent::source(e) == n) {
    238238        Parent::nextOut(e);
     
    244244    }
    245245
    246     void firstInc(UndirEdge &e, bool &d, const Node &n) const {
     246    void firstInc(UEdge &e, bool &d, const Node &n) const {
    247247      d = true;
    248248      Parent::firstOut(e, n);
     
    251251      Parent::firstIn(e, n);
    252252    }
    253     void nextInc(UndirEdge &e, bool &d) const {
     253    void nextInc(UEdge &e, bool &d) const {
    254254      if (d) {
    255255        Node s = Parent::source(e);
     
    276276    }
    277277
    278     int id(const UndirEdge &e) const {
     278    int id(const UEdge &e) const {
    279279      return Parent::id(e);
    280280    }
     
    292292    }
    293293
    294     int maxUndirEdgeId() const {
     294    int maxUEdgeId() const {
    295295      return Parent::maxEdgeId();
    296296    }
     
    303303      return maxEdgeId();
    304304    }
    305     int maxId(UndirEdge) const {
    306       return maxUndirEdgeId();
     305    int maxId(UEdge) const {
     306      return maxUEdgeId();
    307307    }
    308308
     
    311311    }
    312312
    313     int undirEdgeNum() const {
     313    int uEdgeNum() const {
    314314      return Parent::edgeNum();
    315315    }
     
    323323    }
    324324
    325     UndirEdge undirEdgeFromId(int id) const {
     325    UEdge uEdgeFromId(int id) const {
    326326      return Parent::edgeFromId(id >> 1);
    327327    }
     
    335335    }
    336336
    337     UndirEdge fromId(int id, UndirEdge) const {
    338       return undirEdgeFromId(id);
     337    UEdge fromId(int id, UEdge) const {
     338      return uEdgeFromId(id);
    339339    }
    340340
     
    342342    Edge findEdge(Node source, Node target, Edge prev) const {
    343343      if (prev == INVALID) {
    344         UndirEdge edge = Parent::findEdge(source, target);
     344        UEdge edge = Parent::findEdge(source, target);
    345345        if (edge != INVALID) return direct(edge, true);
    346346        edge = Parent::findEdge(target, source);
    347347        if (edge != INVALID) return direct(edge, false);
    348348      } else if (direction(prev)) {
    349         UndirEdge edge = Parent::findEdge(source, target, prev);
     349        UEdge edge = Parent::findEdge(source, target, prev);
    350350        if (edge != INVALID) return direct(edge, true);
    351351        edge = Parent::findEdge(target, source);
    352352        if (edge != INVALID) return direct(edge, false);       
    353353      } else {
    354         UndirEdge edge = Parent::findEdge(target, source, prev);
     354        UEdge edge = Parent::findEdge(target, source, prev);
    355355        if (edge != INVALID) return direct(edge, false);             
    356356      }
     
    358358    }
    359359
    360     UndirEdge findUndirEdge(Node source, Node target, UndirEdge prev) const {
     360    UEdge findUEdge(Node source, Node target, UEdge prev) const {
    361361      if (prev == INVALID) {
    362         UndirEdge edge = Parent::findEdge(source, target);
     362        UEdge edge = Parent::findEdge(source, target);
    363363        if (edge != INVALID) return edge;
    364364        edge = Parent::findEdge(target, source);
    365365        if (edge != INVALID) return edge;
    366366      } else if (Parent::source(prev) == source) {
    367         UndirEdge edge = Parent::findEdge(source, target, prev);
     367        UEdge edge = Parent::findEdge(source, target, prev);
    368368        if (edge != INVALID) return edge;
    369369        edge = Parent::findEdge(target, source);
    370370        if (edge != INVALID) return edge;       
    371371      } else {
    372         UndirEdge edge = Parent::findEdge(target, source, prev);
     372        UEdge edge = Parent::findEdge(target, source, prev);
    373373        if (edge != INVALID) return edge;             
    374374      }
     
    380380
    381381  template <typename _Base>
    382   class UndirBipartiteGraphExtender : public _Base {
     382  class UBipartiteGraphExtender : public _Base {
    383383  public:
    384384    typedef _Base Parent;
    385     typedef UndirBipartiteGraphExtender Graph;
     385    typedef UBipartiteGraphExtender Graph;
    386386
    387387    typedef typename Parent::Node Node;
    388     typedef typename Parent::Edge UndirEdge;
     388    typedef typename Parent::Edge UEdge;
    389389
    390390    using Parent::first;
     
    393393    using Parent::id;
    394394
    395     Node source(const UndirEdge& edge) const {
     395    Node source(const UEdge& edge) const {
    396396      return upperNode(edge);
    397397    }
    398     Node target(const UndirEdge& edge) const {
     398    Node target(const UEdge& edge) const {
    399399      return lowerNode(edge);
    400400    }
    401401
    402     void firstInc(UndirEdge& edge, bool& direction, const Node& node) const {
     402    void firstInc(UEdge& edge, bool& direction, const Node& node) const {
    403403      if (Parent::upper(node)) {
    404404        Parent::firstDown(edge, node);
     
    406406      } else {
    407407        Parent::firstUp(edge, node);
    408         direction = static_cast<UndirEdge&>(edge) == INVALID;
    409       }
    410     }
    411     void nextInc(UndirEdge& edge, bool& direction) const {
     408        direction = static_cast<UEdge&>(edge) == INVALID;
     409      }
     410    }
     411    void nextInc(UEdge& edge, bool& direction) const {
    412412      if (direction) {
    413413        Parent::nextDown(edge);
     
    418418    }
    419419
    420     int maxUndirEdgeId() const {
     420    int maxUEdgeId() const {
    421421      return Parent::maxEdgeId();
    422422    }
    423423
    424     UndirEdge undirEdgeFromId(int id) const {
     424    UEdge uEdgeFromId(int id) const {
    425425      return Parent::edgeFromId(id);
    426426    }
    427427
    428     class Edge : public UndirEdge {
    429       friend class UndirBipartiteGraphExtender;
     428    class Edge : public UEdge {
     429      friend class UBipartiteGraphExtender;
    430430    protected:
    431431      bool forward;
    432432
    433       Edge(const UndirEdge& edge, bool _forward)
    434         : UndirEdge(edge), forward(_forward) {}
     433      Edge(const UEdge& edge, bool _forward)
     434        : UEdge(edge), forward(_forward) {}
    435435
    436436    public:
    437437      Edge() {}
    438       Edge (Invalid) : UndirEdge(INVALID), forward(true) {}
     438      Edge (Invalid) : UEdge(INVALID), forward(true) {}
    439439      bool operator==(const Edge& i) const {
    440         return UndirEdge::operator==(i) && forward == i.forward;
     440        return UEdge::operator==(i) && forward == i.forward;
    441441      }
    442442      bool operator!=(const Edge& i) const {
    443         return UndirEdge::operator!=(i) || forward != i.forward;
     443        return UEdge::operator!=(i) || forward != i.forward;
    444444      }
    445445      bool operator<(const Edge& i) const {
    446         return UndirEdge::operator<(i) ||
    447           (!(i.forward<forward) && UndirEdge(*this)<UndirEdge(i));
     446        return UEdge::operator<(i) ||
     447          (!(i.forward<forward) && UEdge(*this)<UEdge(i));
    448448      }
    449449    };
    450450
    451451    void first(Edge& edge) const {
    452       Parent::first(static_cast<UndirEdge&>(edge));
     452      Parent::first(static_cast<UEdge&>(edge));
    453453      edge.forward = true;
    454454    }
     
    456456    void next(Edge& edge) const {
    457457      if (!edge.forward) {
    458         Parent::next(static_cast<UndirEdge&>(edge));
     458        Parent::next(static_cast<UEdge&>(edge));
    459459      }
    460460      edge.forward = !edge.forward;
     
    467467      } else {
    468468        Parent::firstUp(edge, node);
    469         edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
     469        edge.forward = static_cast<UEdge&>(edge) == INVALID;
    470470      }
    471471    }
     
    475475      } else {
    476476        Parent::nextUp(edge);
    477         edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
     477        edge.forward = static_cast<UEdge&>(edge) == INVALID;
    478478      }
    479479    }
     
    485485      } else {
    486486        Parent::firstDown(edge, node);
    487         edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
     487        edge.forward = static_cast<UEdge&>(edge) == INVALID;
    488488      }
    489489    }
     
    493493      } else {
    494494        Parent::nextDown(edge);
    495         edge.forward = static_cast<UndirEdge&>(edge) == INVALID;
     495        edge.forward = static_cast<UEdge&>(edge) == INVALID;
    496496      }
    497497    }
     
    508508    }
    509509
    510     Edge direct(const UndirEdge& edge, const Node& node) const {
     510    Edge direct(const UEdge& edge, const Node& node) const {
    511511      return Edge(edge, node == Parent::source(edge));
    512512    }
    513513
    514     Edge direct(const UndirEdge& edge, bool direction) const {
     514    Edge direct(const UEdge& edge, bool direction) const {
    515515      return Edge(edge, direction);
    516516    }
    517517
    518     Node oppositeNode(const UndirEdge& edge, const Node& node) const {
     518    Node oppositeNode(const UEdge& edge, const Node& node) const {
    519519      return source(edge) == node ?
    520520        target(edge) : source(edge);
     
    529529    }
    530530    Edge edgeFromId(int id) const {
    531       return Edge(Parent::fromId(id >> 1, UndirEdge()), (id & 1) == 0);
     531      return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
    532532    }
    533533    int maxEdgeId() const {
    534       return (Parent::maxId(UndirEdge()) << 1) + 1;
     534      return (Parent::maxId(UEdge()) << 1) + 1;
    535535    }
    536536
    537537    class UpperNode : public Node {
    538       friend class UndirBipartiteGraphExtender;
     538      friend class UBipartiteGraphExtender;
    539539    public:
    540540      UpperNode() {}
     
    558558
    559559    class LowerNode : public Node {
    560       friend class UndirBipartiteGraphExtender;
     560      friend class UBipartiteGraphExtender;
    561561    public:
    562562      LowerNode() {}
     
    593593      return maxEdgeId();
    594594    }
    595     int maxId(UndirEdge) const {
    596       return maxUndirEdgeId();
     595    int maxId(UEdge) const {
     596      return maxUEdgeId();
    597597    }
    598598
     
    610610      return edgeFromId(id);
    611611    }
    612     UndirEdge fromId(int id, UndirEdge) const {
    613       return undirEdgeFromId(id);
     612    UEdge fromId(int id, UEdge) const {
     613      return uEdgeFromId(id);
    614614    }
    615615
Note: See TracChangeset for help on using the changeset viewer.