COIN-OR::LEMON - Graph Library

Changeset 2116:b6a68c15a6a3 in lemon-0.x for lemon/bits/graph_extender.h


Ignore:
Timestamp:
06/30/06 14:15:45 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2822
Message:

Revert splitted files

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r2115 r2116  
    2121
    2222#include <lemon/bits/invalid.h>
     23#include <lemon/error.h>
    2324
    2425#include <lemon/bits/map_extender.h>
    2526#include <lemon/bits/default_map.h>
     27
     28#include <lemon/concept_check.h>
     29#include <lemon/concept/maps.h>
    2630
    2731///\ingroup graphbits
     
    315319  };
    316320
     321  /// \ingroup graphbits
     322  ///
     323  /// \brief Extender for the UGraphs
     324  template <typename Base>
     325  class UGraphExtender : public Base {
     326  public:
     327   
     328    typedef Base Parent;
     329    typedef UGraphExtender Graph;
     330
     331    typedef typename Parent::Node Node;
     332    typedef typename Parent::Edge Edge;
     333    typedef typename Parent::UEdge UEdge;
     334
     335    // UGraph extension   
     336
     337    int maxId(Node) const {
     338      return Parent::maxNodeId();
     339    }
     340
     341    int maxId(Edge) const {
     342      return Parent::maxEdgeId();
     343    }
     344
     345    int maxId(UEdge) const {
     346      return Parent::maxUEdgeId();
     347    }
     348
     349    Node fromId(int id, Node) const {
     350      return Parent::nodeFromId(id);
     351    }
     352
     353    Edge fromId(int id, Edge) const {
     354      return Parent::edgeFromId(id);
     355    }
     356
     357    UEdge fromId(int id, UEdge) const {
     358      return Parent::uEdgeFromId(id);
     359    }
     360
     361    Node oppositeNode(const Node &n, const UEdge &e) const {
     362      if( n == Parent::source(e))
     363        return Parent::target(e);
     364      else if( n == Parent::target(e))
     365        return Parent::source(e);
     366      else
     367        return INVALID;
     368    }
     369
     370    Edge oppositeEdge(const Edge &e) const {
     371      return Parent::direct(e, !Parent::direction(e));
     372    }
     373
     374    using Parent::direct;
     375    Edge direct(const UEdge &ue, const Node &s) const {
     376      return Parent::direct(ue, Parent::source(ue) == s);
     377    }
     378
     379    // Alterable extension
     380
     381    typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;
     382    typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;
     383    typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;
     384
     385
     386  protected:
     387
     388    mutable NodeNotifier node_notifier;
     389    mutable EdgeNotifier edge_notifier;
     390    mutable UEdgeNotifier uedge_notifier;
     391
     392  public:
     393
     394    NodeNotifier& getNotifier(Node) const {
     395      return node_notifier;
     396    }
     397   
     398    EdgeNotifier& getNotifier(Edge) const {
     399      return edge_notifier;
     400    }
     401
     402    UEdgeNotifier& getNotifier(UEdge) const {
     403      return uedge_notifier;
     404    }
     405
     406
     407
     408    class NodeIt : public Node {
     409      const Graph* graph;
     410    public:
     411
     412      NodeIt() {}
     413
     414      NodeIt(Invalid i) : Node(i) { }
     415
     416      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     417        _graph.first(static_cast<Node&>(*this));
     418      }
     419
     420      NodeIt(const Graph& _graph, const Node& node)
     421        : Node(node), graph(&_graph) {}
     422
     423      NodeIt& operator++() {
     424        graph->next(*this);
     425        return *this;
     426      }
     427
     428    };
     429
     430
     431    class EdgeIt : public Edge {
     432      const Graph* graph;
     433    public:
     434
     435      EdgeIt() { }
     436
     437      EdgeIt(Invalid i) : Edge(i) { }
     438
     439      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     440        _graph.first(static_cast<Edge&>(*this));
     441      }
     442
     443      EdgeIt(const Graph& _graph, const Edge& e) :
     444        Edge(e), graph(&_graph) { }
     445
     446      EdgeIt& operator++() {
     447        graph->next(*this);
     448        return *this;
     449      }
     450
     451    };
     452
     453
     454    class OutEdgeIt : public Edge {
     455      const Graph* graph;
     456    public:
     457
     458      OutEdgeIt() { }
     459
     460      OutEdgeIt(Invalid i) : Edge(i) { }
     461
     462      OutEdgeIt(const Graph& _graph, const Node& node)
     463        : graph(&_graph) {
     464        _graph.firstOut(*this, node);
     465      }
     466
     467      OutEdgeIt(const Graph& _graph, const Edge& edge)
     468        : Edge(edge), graph(&_graph) {}
     469
     470      OutEdgeIt& operator++() {
     471        graph->nextOut(*this);
     472        return *this;
     473      }
     474
     475    };
     476
     477
     478    class InEdgeIt : public Edge {
     479      const Graph* graph;
     480    public:
     481
     482      InEdgeIt() { }
     483
     484      InEdgeIt(Invalid i) : Edge(i) { }
     485
     486      InEdgeIt(const Graph& _graph, const Node& node)
     487        : graph(&_graph) {
     488        _graph.firstIn(*this, node);
     489      }
     490
     491      InEdgeIt(const Graph& _graph, const Edge& edge) :
     492        Edge(edge), graph(&_graph) {}
     493
     494      InEdgeIt& operator++() {
     495        graph->nextIn(*this);
     496        return *this;
     497      }
     498
     499    };
     500
     501
     502    class UEdgeIt : public Parent::UEdge {
     503      const Graph* graph;
     504    public:
     505
     506      UEdgeIt() { }
     507
     508      UEdgeIt(Invalid i) : UEdge(i) { }
     509
     510      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
     511        _graph.first(static_cast<UEdge&>(*this));
     512      }
     513
     514      UEdgeIt(const Graph& _graph, const UEdge& e) :
     515        UEdge(e), graph(&_graph) { }
     516
     517      UEdgeIt& operator++() {
     518        graph->next(*this);
     519        return *this;
     520      }
     521
     522    };
     523
     524    class IncEdgeIt : public Parent::UEdge {
     525      friend class UGraphExtender;
     526      const Graph* graph;
     527      bool direction;
     528    public:
     529
     530      IncEdgeIt() { }
     531
     532      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
     533
     534      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     535        _graph.firstInc(*this, direction, n);
     536      }
     537
     538      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
     539        : graph(&_graph), UEdge(ue) {
     540        direction = (_graph.source(ue) == n);
     541      }
     542
     543      IncEdgeIt& operator++() {
     544        graph->nextInc(*this, direction);
     545        return *this;
     546      }
     547    };
     548
     549    /// \brief Base node of the iterator
     550    ///
     551    /// Returns the base node (ie. the source in this case) of the iterator
     552    Node baseNode(const OutEdgeIt &e) const {
     553      return Parent::source((Edge)e);
     554    }
     555    /// \brief Running node of the iterator
     556    ///
     557    /// Returns the running node (ie. the target in this case) of the
     558    /// iterator
     559    Node runningNode(const OutEdgeIt &e) const {
     560      return Parent::target((Edge)e);
     561    }
     562
     563    /// \brief Base node of the iterator
     564    ///
     565    /// Returns the base node (ie. the target in this case) of the iterator
     566    Node baseNode(const InEdgeIt &e) const {
     567      return Parent::target((Edge)e);
     568    }
     569    /// \brief Running node of the iterator
     570    ///
     571    /// Returns the running node (ie. the source in this case) of the
     572    /// iterator
     573    Node runningNode(const InEdgeIt &e) const {
     574      return Parent::source((Edge)e);
     575    }
     576
     577    /// Base node of the iterator
     578    ///
     579    /// Returns the base node of the iterator
     580    Node baseNode(const IncEdgeIt &e) const {
     581      return e.direction ? source(e) : target(e);
     582    }
     583    /// Running node of the iterator
     584    ///
     585    /// Returns the running node of the iterator
     586    Node runningNode(const IncEdgeIt &e) const {
     587      return e.direction ? target(e) : source(e);
     588    }
     589
     590    // Mappable extension
     591
     592    template <typename _Value>
     593    class NodeMap
     594      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
     595    public:
     596      typedef UGraphExtender Graph;
     597      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
     598
     599      NodeMap(const Graph& graph)
     600        : Parent(graph) {}
     601      NodeMap(const Graph& graph, const _Value& value)
     602        : Parent(graph, value) {}
     603
     604      NodeMap& operator=(const NodeMap& cmap) {
     605        return operator=<NodeMap>(cmap);
     606      }
     607
     608      template <typename CMap>
     609      NodeMap& operator=(const CMap& cmap) {
     610        Parent::operator=(cmap);
     611        return *this;
     612      }
     613
     614    };
     615
     616    template <typename _Value>
     617    class EdgeMap
     618      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     619    public:
     620      typedef UGraphExtender Graph;
     621      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     622
     623      EdgeMap(const Graph& graph)
     624        : Parent(graph) {}
     625      EdgeMap(const Graph& graph, const _Value& value)
     626        : Parent(graph, value) {}
     627
     628      EdgeMap& operator=(const EdgeMap& cmap) {
     629        return operator=<EdgeMap>(cmap);
     630      }
     631
     632      template <typename CMap>
     633      EdgeMap& operator=(const CMap& cmap) {
     634        Parent::operator=(cmap);
     635        return *this;
     636      }
     637    };
     638
     639
     640    template <typename _Value>
     641    class UEdgeMap
     642      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
     643    public:
     644      typedef UGraphExtender Graph;
     645      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
     646
     647      UEdgeMap(const Graph& graph)
     648        : Parent(graph) {}
     649
     650      UEdgeMap(const Graph& graph, const _Value& value)
     651        : Parent(graph, value) {}
     652
     653      UEdgeMap& operator=(const UEdgeMap& cmap) {
     654        return operator=<UEdgeMap>(cmap);
     655      }
     656
     657      template <typename CMap>
     658      UEdgeMap& operator=(const CMap& cmap) {
     659        Parent::operator=(cmap);
     660        return *this;
     661      }
     662
     663    };
     664
     665    // Alteration extension
     666
     667    Node addNode() {
     668      Node node = Parent::addNode();
     669      getNotifier(Node()).add(node);
     670      return node;
     671    }
     672
     673    UEdge addEdge(const Node& from, const Node& to) {
     674      UEdge uedge = Parent::addEdge(from, to);
     675      getNotifier(UEdge()).add(uedge);
     676      getNotifier(Edge()).add(Parent::direct(uedge, true));
     677      getNotifier(Edge()).add(Parent::direct(uedge, false));
     678      return uedge;
     679    }
     680   
     681    void clear() {
     682      getNotifier(Edge()).clear();
     683      getNotifier(UEdge()).clear();
     684      getNotifier(Node()).clear();
     685      Parent::clear();
     686    }
     687
     688    void erase(const Node& node) {
     689      Edge edge;
     690      Parent::firstOut(edge, node);
     691      while (edge != INVALID ) {
     692        erase(edge);
     693        Parent::firstOut(edge, node);
     694      }
     695
     696      Parent::firstIn(edge, node);
     697      while (edge != INVALID ) {
     698        erase(edge);
     699        Parent::firstIn(edge, node);
     700      }
     701
     702      getNotifier(Node()).erase(node);
     703      Parent::erase(node);
     704    }
     705
     706    void erase(const UEdge& uedge) {
     707      getNotifier(Edge()).erase(Parent::direct(uedge, true));
     708      getNotifier(Edge()).erase(Parent::direct(uedge, false));
     709      getNotifier(UEdge()).erase(uedge);
     710      Parent::erase(uedge);
     711    }
     712
     713    UGraphExtender() {
     714      node_notifier.setContainer(*this);
     715      edge_notifier.setContainer(*this);
     716      uedge_notifier.setContainer(*this);
     717    }
     718
     719    ~UGraphExtender() {
     720      uedge_notifier.clear();
     721      edge_notifier.clear();
     722      node_notifier.clear();
     723    }
     724
     725  };
     726
     727  /// \ingroup graphbits
     728  ///
     729  /// \brief Extender for the BpUGraphs
     730  template <typename Base>
     731  class BpUGraphExtender : public Base {
     732  public:
     733    typedef Base Parent;
     734    typedef BpUGraphExtender Graph;
     735
     736    typedef typename Parent::Node Node;
     737    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    }
     918
     919    Node oppositeNode(const UEdge& edge, const Node& node) const {
     920      return source(edge) == node ?
     921        target(edge) : source(edge);
     922    }
     923
     924    Edge direct(const UEdge& edge, const Node& node) const {
     925      return Edge(edge, node == Parent::source(edge));
     926    }
     927
     928    Edge oppositeEdge(const Edge& edge) const {
     929      return Parent::direct(edge, !Parent::direction(edge));
     930    }
     931
     932
     933    int maxId(Node) const {
     934      return Parent::maxNodeId();
     935    }
     936    int maxId(BNode) const {
     937      return Parent::maxBNodeId();
     938    }
     939    int maxId(ANode) const {
     940      return Parent::maxANodeId();
     941    }
     942    int maxId(Edge) const {
     943      return maxEdgeId();
     944    }
     945    int maxId(UEdge) const {
     946      return Parent::maxUEdgeId();
     947    }
     948
     949
     950    Node fromId(int id, Node) const {
     951      return Parent::nodeFromId(id);
     952    }
     953    ANode fromId(int id, ANode) const {
     954      return Parent::fromANodeId(id);
     955    }
     956    BNode fromId(int id, BNode) const {
     957      return Parent::fromBNodeId(id);
     958    }
     959    Edge fromId(int id, Edge) const {
     960      return Parent::edgeFromId(id);
     961    }
     962    UEdge fromId(int id, UEdge) const {
     963      return Parent::uEdgeFromId(id);
     964    } 
     965 
     966    typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;
     967    typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;
     968    typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;
     969    typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;
     970    typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;
     971
     972  protected:
     973
     974    mutable ANodeNotifier anode_notifier;
     975    mutable BNodeNotifier bnode_notifier;
     976    mutable NodeNotifier node_notifier;
     977    mutable EdgeNotifier edge_notifier;
     978    mutable UEdgeNotifier uedge_notifier;
     979
     980  public:
     981
     982    NodeNotifier& getNotifier(Node) const {
     983      return node_notifier;
     984    }
     985
     986    ANodeNotifier& getNotifier(ANode) const {
     987      return anode_notifier;
     988    }
     989
     990    BNodeNotifier& getNotifier(BNode) const {
     991      return bnode_notifier;
     992    }
     993
     994    EdgeNotifier& getNotifier(Edge) const {
     995      return edge_notifier;
     996    }
     997
     998    UEdgeNotifier& getNotifier(UEdge) const {
     999      return uedge_notifier;
     1000    }
     1001
     1002    class NodeIt : public Node {
     1003      const Graph* graph;
     1004    public:
     1005   
     1006      NodeIt() { }
     1007   
     1008      NodeIt(Invalid i) : Node(INVALID) { }
     1009   
     1010      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     1011        graph->first(static_cast<Node&>(*this));
     1012      }
     1013
     1014      NodeIt(const Graph& _graph, const Node& node)
     1015        : Node(node), graph(&_graph) { }
     1016   
     1017      NodeIt& operator++() {
     1018        graph->next(*this);
     1019        return *this;
     1020      }
     1021
     1022    };
     1023
     1024    class ANodeIt : public Node {
     1025      friend class BpUGraphExtender;
     1026      const Graph* graph;
     1027    public:
     1028   
     1029      ANodeIt() { }
     1030   
     1031      ANodeIt(Invalid i) : Node(INVALID) { }
     1032   
     1033      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
     1034        graph->firstANode(static_cast<Node&>(*this));
     1035      }
     1036
     1037      ANodeIt(const Graph& _graph, const Node& node)
     1038        : Node(node), graph(&_graph) {}
     1039   
     1040      ANodeIt& operator++() {
     1041        graph->nextANode(*this);
     1042        return *this;
     1043      }
     1044    };
     1045
     1046    class BNodeIt : public Node {
     1047      friend class BpUGraphExtender;
     1048      const Graph* graph;
     1049    public:
     1050   
     1051      BNodeIt() { }
     1052   
     1053      BNodeIt(Invalid i) : Node(INVALID) { }
     1054   
     1055      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
     1056        graph->firstBNode(static_cast<Node&>(*this));
     1057      }
     1058
     1059      BNodeIt(const Graph& _graph, const Node& node)
     1060        : Node(node), graph(&_graph) {}
     1061   
     1062      BNodeIt& operator++() {
     1063        graph->nextBNode(*this);
     1064        return *this;
     1065      }
     1066    };
     1067
     1068    class EdgeIt : public Edge {
     1069      friend class BpUGraphExtender;
     1070      const Graph* graph;
     1071    public:
     1072   
     1073      EdgeIt() { }
     1074   
     1075      EdgeIt(Invalid i) : Edge(INVALID) { }
     1076   
     1077      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     1078        graph->first(static_cast<Edge&>(*this));
     1079      }
     1080
     1081      EdgeIt(const Graph& _graph, const Edge& edge)
     1082        : Edge(edge), graph(&_graph) { }
     1083   
     1084      EdgeIt& operator++() {
     1085        graph->next(*this);
     1086        return *this;
     1087      }
     1088
     1089    };
     1090
     1091    class UEdgeIt : public UEdge {
     1092      friend class BpUGraphExtender;
     1093      const Graph* graph;
     1094    public:
     1095   
     1096      UEdgeIt() { }
     1097   
     1098      UEdgeIt(Invalid i) : UEdge(INVALID) { }
     1099   
     1100      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
     1101        graph->first(static_cast<UEdge&>(*this));
     1102      }
     1103
     1104      UEdgeIt(const Graph& _graph, const UEdge& edge)
     1105        : UEdge(edge), graph(&_graph) { }
     1106   
     1107      UEdgeIt& operator++() {
     1108        graph->next(*this);
     1109        return *this;
     1110      }
     1111    };
     1112
     1113    class OutEdgeIt : public Edge {
     1114      friend class BpUGraphExtender;
     1115      const Graph* graph;
     1116    public:
     1117   
     1118      OutEdgeIt() { }
     1119   
     1120      OutEdgeIt(Invalid i) : Edge(i) { }
     1121   
     1122      OutEdgeIt(const Graph& _graph, const Node& node)
     1123        : graph(&_graph) {
     1124        graph->firstOut(*this, node);
     1125      }
     1126   
     1127      OutEdgeIt(const Graph& _graph, const Edge& edge)
     1128        : Edge(edge), graph(&_graph) {}
     1129   
     1130      OutEdgeIt& operator++() {
     1131        graph->nextOut(*this);
     1132        return *this;
     1133      }
     1134
     1135    };
     1136
     1137
     1138    class InEdgeIt : public Edge {
     1139      friend class BpUGraphExtender;
     1140      const Graph* graph;
     1141    public:
     1142   
     1143      InEdgeIt() { }
     1144   
     1145      InEdgeIt(Invalid i) : Edge(i) { }
     1146   
     1147      InEdgeIt(const Graph& _graph, const Node& node)
     1148        : graph(&_graph) {
     1149        graph->firstIn(*this, node);
     1150      }
     1151   
     1152      InEdgeIt(const Graph& _graph, const Edge& edge) :
     1153        Edge(edge), graph(&_graph) {}
     1154   
     1155      InEdgeIt& operator++() {
     1156        graph->nextIn(*this);
     1157        return *this;
     1158      }
     1159
     1160    };
     1161 
     1162    /// \brief Base node of the iterator
     1163    ///
     1164    /// Returns the base node (ie. the source in this case) of the iterator
     1165    Node baseNode(const OutEdgeIt &e) const {
     1166      return Parent::source((Edge&)e);
     1167    }
     1168    /// \brief Running node of the iterator
     1169    ///
     1170    /// Returns the running node (ie. the target in this case) of the
     1171    /// iterator
     1172    Node runningNode(const OutEdgeIt &e) const {
     1173      return Parent::target((Edge&)e);
     1174    }
     1175 
     1176    /// \brief Base node of the iterator
     1177    ///
     1178    /// Returns the base node (ie. the target in this case) of the iterator
     1179    Node baseNode(const InEdgeIt &e) const {
     1180      return Parent::target((Edge&)e);
     1181    }
     1182    /// \brief Running node of the iterator
     1183    ///
     1184    /// Returns the running node (ie. the source in this case) of the
     1185    /// iterator
     1186    Node runningNode(const InEdgeIt &e) const {
     1187      return Parent::source((Edge&)e);
     1188    }
     1189 
     1190    class IncEdgeIt : public Parent::UEdge {
     1191      friend class BpUGraphExtender;
     1192      const Graph* graph;
     1193      bool direction;
     1194    public:
     1195   
     1196      IncEdgeIt() { }
     1197   
     1198      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
     1199   
     1200      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     1201        graph->firstInc(*this, direction, n);
     1202      }
     1203
     1204      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
     1205        : graph(&_graph), UEdge(ue) {
     1206        direction = (graph->source(ue) == n);
     1207      }
     1208
     1209      IncEdgeIt& operator++() {
     1210        graph->nextInc(*this, direction);
     1211        return *this;
     1212      }
     1213    };
     1214 
     1215
     1216    /// Base node of the iterator
     1217    ///
     1218    /// Returns the base node of the iterator
     1219    Node baseNode(const IncEdgeIt &e) const {
     1220      return e.direction ? source(e) : target(e);
     1221    }
     1222
     1223    /// Running node of the iterator
     1224    ///
     1225    /// Returns the running node of the iterator
     1226    Node runningNode(const IncEdgeIt &e) const {
     1227      return e.direction ? target(e) : source(e);
     1228    }
     1229
     1230    template <typename _Value>
     1231    class ANodeMap
     1232      : public MapExtender<DefaultMap<Graph, ANode, _Value> > {
     1233    public:
     1234      typedef BpUGraphExtender Graph;
     1235      typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;
     1236   
     1237      ANodeMap(const Graph& graph)
     1238        : Parent(graph) {}
     1239      ANodeMap(const Graph& graph, const _Value& value)
     1240        : Parent(graph, value) {}
     1241   
     1242      ANodeMap& operator=(const ANodeMap& cmap) {
     1243        return operator=<ANodeMap>(cmap);
     1244      }
     1245   
     1246      template <typename CMap>
     1247      ANodeMap& operator=(const CMap& cmap) {
     1248        Parent::operator=(cmap);
     1249        return *this;
     1250      }
     1251   
     1252    };
     1253
     1254    template <typename _Value>
     1255    class BNodeMap
     1256      : public MapExtender<DefaultMap<Graph, BNode, _Value> > {
     1257    public:
     1258      typedef BpUGraphExtender Graph;
     1259      typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;
     1260   
     1261      BNodeMap(const Graph& graph)
     1262        : Parent(graph) {}
     1263      BNodeMap(const Graph& graph, const _Value& value)
     1264        : Parent(graph, value) {}
     1265   
     1266      BNodeMap& operator=(const BNodeMap& cmap) {
     1267        return operator=<BNodeMap>(cmap);
     1268      }
     1269   
     1270      template <typename CMap>
     1271      BNodeMap& operator=(const CMap& cmap) {
     1272        Parent::operator=(cmap);
     1273        return *this;
     1274      }
     1275   
     1276    };
     1277
     1278  public:
     1279
     1280    template <typename _Value>
     1281    class NodeMap {
     1282    public:
     1283      typedef BpUGraphExtender Graph;
     1284
     1285      typedef Node Key;
     1286      typedef _Value Value;
     1287
     1288      /// The reference type of the map;
     1289      typedef typename ANodeMap<_Value>::Reference Reference;
     1290      /// The const reference type of the map;
     1291      typedef typename ANodeMap<_Value>::ConstReference ConstReference;
     1292
     1293      typedef True ReferenceMapTag;
     1294
     1295      NodeMap(const Graph& _graph)
     1296        : graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}
     1297      NodeMap(const Graph& _graph, const _Value& _value)
     1298        : graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}
     1299
     1300      NodeMap& operator=(const NodeMap& cmap) {
     1301        return operator=<NodeMap>(cmap);
     1302      }
     1303   
     1304      template <typename CMap>
     1305      NodeMap& operator=(const CMap& cmap) {
     1306        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;
     1313      }
     1314
     1315      ConstReference operator[](const Key& node) const {
     1316        if (Parent::aNode(node)) {
     1317          return aNodeMap[node];
     1318        } else {
     1319          return bNodeMap[node];
     1320        }
     1321      }
     1322
     1323      Reference operator[](const Key& node) {
     1324        if (Parent::aNode(node)) {
     1325          return aNodeMap[node];
     1326        } else {
     1327          return bNodeMap[node];
     1328        }
     1329      }
     1330
     1331      void set(const Key& node, const Value& value) {
     1332        if (Parent::aNode(node)) {
     1333          aNodeMap.set(node, value);
     1334        } else {
     1335          bNodeMap.set(node, value);
     1336        }
     1337      }
     1338
     1339      class MapIt : public NodeIt {
     1340      public:
     1341
     1342        typedef NodeIt Parent;
     1343       
     1344        explicit MapIt(NodeMap& _map)
     1345          : Parent(_map.graph), map(_map) {}
     1346       
     1347        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
     1348          return map[*this];
     1349        }
     1350       
     1351        typename MapTraits<NodeMap>::ReturnValue operator*() {
     1352          return map[*this];
     1353        }
     1354       
     1355        void set(const Value& value) {
     1356          map.set(*this, value);
     1357        }
     1358
     1359      private:
     1360        NodeMap& map;
     1361      };
     1362
     1363      class ConstMapIt : public NodeIt {
     1364      public:
     1365
     1366        typedef NodeIt Parent;
     1367       
     1368        explicit ConstMapIt(const NodeMap& _map)
     1369          : Parent(_map.graph), map(_map) {}
     1370       
     1371        typename MapTraits<NodeMap>::ConstReturnValue operator*() const {
     1372          return map[*this];
     1373        }
     1374       
     1375      private:
     1376        const NodeMap& map;
     1377      };
     1378
     1379      class ItemIt : public NodeIt {
     1380      public:
     1381
     1382        typedef NodeIt Parent;
     1383
     1384        explicit ItemIt(const NodeMap& _map)
     1385          : Parent(_map.graph) {}
     1386       
     1387      };
     1388     
     1389    private:
     1390      const Graph& graph;
     1391      ANodeMap<_Value> aNodeMap;
     1392      BNodeMap<_Value> bNodeMap;
     1393    };
     1394   
     1395
     1396    template <typename _Value>
     1397    class EdgeMap
     1398      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
     1399    public:
     1400      typedef BpUGraphExtender Graph;
     1401      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     1402   
     1403      EdgeMap(const Graph& graph)
     1404        : Parent(graph) {}
     1405      EdgeMap(const Graph& graph, const _Value& value)
     1406        : Parent(graph, value) {}
     1407   
     1408      EdgeMap& operator=(const EdgeMap& cmap) {
     1409        return operator=<EdgeMap>(cmap);
     1410      }
     1411   
     1412      template <typename CMap>
     1413      EdgeMap& operator=(const CMap& cmap) {
     1414        Parent::operator=(cmap);
     1415        return *this;
     1416      }
     1417    };
     1418
     1419    template <typename _Value>
     1420    class UEdgeMap
     1421      : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {
     1422    public:
     1423      typedef BpUGraphExtender Graph;
     1424      typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
     1425   
     1426      UEdgeMap(const Graph& graph)
     1427        : Parent(graph) {}
     1428      UEdgeMap(const Graph& graph, const _Value& value)
     1429        : Parent(graph, value) {}
     1430   
     1431      UEdgeMap& operator=(const UEdgeMap& cmap) {
     1432        return operator=<UEdgeMap>(cmap);
     1433      }
     1434   
     1435      template <typename CMap>
     1436      UEdgeMap& operator=(const CMap& cmap) {
     1437        Parent::operator=(cmap);
     1438        return *this;
     1439      }
     1440    };
     1441
     1442 
     1443    Node addANode() {
     1444      Node node = Parent::addANode();
     1445      getNotifier(ANode()).add(node);
     1446      getNotifier(Node()).add(node);
     1447      return node;
     1448    }
     1449
     1450    Node addBNode() {
     1451      Node node = Parent::addBNode();
     1452      getNotifier(BNode()).add(node);
     1453      getNotifier(Node()).add(node);
     1454      return node;
     1455    }
     1456 
     1457    UEdge addEdge(const Node& source, const Node& target) {
     1458      UEdge uedge = Parent::addEdge(source, target);
     1459      getNotifier(UEdge()).add(uedge);
     1460   
     1461      std::vector<Edge> edges;
     1462      edges.push_back(direct(uedge, true));
     1463      edges.push_back(direct(uedge, false));
     1464      getNotifier(Edge()).add(edges);
     1465   
     1466      return uedge;
     1467    }
     1468
     1469    void clear() {
     1470      getNotifier(Edge()).clear();
     1471      getNotifier(UEdge()).clear();
     1472      getNotifier(Node()).clear();
     1473      getNotifier(BNode()).clear();
     1474      getNotifier(ANode()).clear();
     1475      Parent::clear();
     1476    }
     1477
     1478    void erase(const Node& node) {
     1479      UEdge uedge;
     1480      if (Parent::aNode(node)) {
     1481        Parent::firstFromANode(uedge, node);
     1482        while (uedge != INVALID) {
     1483          erase(uedge);
     1484          Parent::firstFromANode(uedge, node);
     1485        }
     1486      } else {
     1487        Parent::firstFromBNode(uedge, node);
     1488        while (uedge != INVALID) {
     1489          erase(uedge);
     1490          Parent::firstFromBNode(uedge, node);
     1491        }
     1492      }
     1493
     1494      getNotifier(Node()).erase(node);
     1495      Parent::erase(node);
     1496    }
     1497   
     1498    void erase(const UEdge& uedge) {
     1499      std::vector<Edge> edges;
     1500      edges.push_back(direct(uedge, true));
     1501      edges.push_back(direct(uedge, false));
     1502      getNotifier(Edge()).erase(edges);
     1503      getNotifier(UEdge()).erase(uedge);
     1504      Parent::erase(uedge);
     1505    }
     1506
     1507
     1508    BpUGraphExtender() {
     1509      anode_notifier.setContainer(*this);
     1510      bnode_notifier.setContainer(*this);
     1511      node_notifier.setContainer(*this);
     1512      edge_notifier.setContainer(*this);
     1513      uedge_notifier.setContainer(*this);
     1514    }
     1515
     1516    ~BpUGraphExtender() {
     1517      uedge_notifier.clear();
     1518      edge_notifier.clear();
     1519      node_notifier.clear();
     1520      anode_notifier.clear();
     1521      bnode_notifier.clear();
     1522    }
     1523
     1524
     1525  };
     1526
    3171527}
    3181528
Note: See TracChangeset for help on using the changeset viewer.