COIN-OR::LEMON - Graph Library

Changeset 2231:06faf3f06d67 in lemon-0.x for lemon/bits/graph_extender.h


Ignore:
Timestamp:
10/03/06 13:46:39 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2973
Message:

Some rearrangement of concepts and extenders
BpUGraph concepts and concept check test

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r2222 r2231  
    731731  class BpUGraphExtender : public Base {
    732732  public:
     733
    733734    typedef Base Parent;
    734735    typedef BpUGraphExtender Graph;
    735736
    736737    typedef typename Parent::Node Node;
     738    typedef typename Parent::ANode ANode;
     739    typedef typename Parent::BNode BNode;
     740    typedef typename Parent::Edge Edge;
    737741    typedef typename Parent::UEdge UEdge;
    738742
    739743
    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     }
    918 
    919     Node oppositeNode(const UEdge& edge, const Node& node) const {
    920       return source(edge) == node ?
    921         target(edge) : source(edge);
    922     }
    923 
     744    Node oppositeNode(const Node& node, const UEdge& edge) const {
     745      return Parent::aNode(edge) == node ?
     746        Parent::bNode(edge) : Parent::aNode(edge);
     747    }
     748
     749    using Parent::direct;
    924750    Edge direct(const UEdge& edge, const Node& node) const {
    925       return Edge(edge, node == Parent::source(edge));
     751      return Parent::direct(edge, node == Parent::source(edge));
    926752    }
    927753
    928754    Edge oppositeEdge(const Edge& edge) const {
    929       return Parent::direct(edge, !Parent::direction(edge));
    930     }
    931 
    932 
     755      return direct(edge, !Parent::direction(edge));
     756    }
     757   
    933758    int maxId(Node) const {
    934759      return Parent::maxNodeId();
     
    941766    }
    942767    int maxId(Edge) const {
    943       return maxEdgeId();
     768      return Parent::maxEdgeId();
    944769    }
    945770    int maxId(UEdge) const {
     
    952777    }
    953778    ANode fromId(int id, ANode) const {
    954       return Parent::fromANodeId(id);
     779      return Parent::nodeFromANodeId(id);
    955780    }
    956781    BNode fromId(int id, BNode) const {
    957       return Parent::fromBNodeId(id);
     782      return Parent::nodeFromBNodeId(id);
    958783    }
    959784    Edge fromId(int id, Edge) const {
     
    13051130      NodeMap& operator=(const CMap& cmap) {
    13061131        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
    1307         const typename Parent::Notifier* notifier = Parent::getNotifier();
    1308         Edge it;
    1309         for (graph.first(it); it != INVALID; graph.next(it)) {
    1310           Parent::set(it, cmap[it]);
    1311         }
    1312         return *this;
     1132        aNodeMap = cmap;
     1133        bNodeMap = cmap;
     1134        return *this;
    13131135      }
    13141136
     
    14601282   
    14611283      std::vector<Edge> edges;
    1462       edges.push_back(direct(uedge, true));
    1463       edges.push_back(direct(uedge, false));
     1284      edges.push_back(Parent::direct(uedge, true));
     1285      edges.push_back(Parent::direct(uedge, false));
    14641286      getNotifier(Edge()).add(edges);
    14651287   
     
    15001322    void erase(const UEdge& uedge) {
    15011323      std::vector<Edge> edges;
    1502       edges.push_back(direct(uedge, true));
    1503       edges.push_back(direct(uedge, false));
     1324      edges.push_back(Parent::direct(uedge, true));
     1325      edges.push_back(Parent::direct(uedge, false));
    15041326      getNotifier(Edge()).erase(edges);
    15051327      getNotifier(UEdge()).erase(uedge);
     
    15271349      UEdge uedge = Parent::findUEdge(u, v, prev);
    15281350      if (uedge != INVALID) {
    1529         return direct(uedge, Parent::aNode(u));
     1351        return Parent::direct(uedge, Parent::aNode(u));
    15301352      } else {
    15311353        return INVALID;
Note: See TracChangeset for help on using the changeset viewer.