COIN-OR::LEMON - Graph Library

Changeset 2076:10681ee9d8ae in lemon-0.x for lemon/bits


Ignore:
Timestamp:
05/12/06 11:51:45 (14 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/bits
Files:
3 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 {
Note: See TracChangeset for help on using the changeset viewer.