COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 2115:4cd528a30ec1 in lemon-0.x for lemon/bits/graph_extender.h


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

Splitted graph files

File:
1 edited

Legend:

Unmodified
Added
Removed

  • lemon/bits/graph_extender.h

    r2102 r2115  
    2121
    2222#include <lemon/bits/invalid.h>
    23 #include <lemon/error.h>
    2423
    2524#include <lemon/bits/map_extender.h>
    2625#include <lemon/bits/default_map.h>
    27 
    28 #include <lemon/concept_check.h>
    29 #include <lemon/concept/maps.h>
    3026
    3127///\ingroup graphbits
    … …  
    319315  };
    320316
    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 
    1527317}
    1528318
Note: See TracChangeset for help on using the changeset viewer.