COIN-OR::LEMON - Graph Library

Changeset 1979:c2992fd74dad in lemon-0.x for lemon/bits/graph_extender.h


Ignore:
Timestamp:
02/22/06 19:26:56 (13 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2569
Message:

Mergeing extendermerge branch
Changes:

the extender system
resize for static size graph
UGraphExtender => UndirectGraphExtender?

UGraphExtenders with changed meaning

Some UGraphExtender /SubUGraphExtenders, DirectUGraphExtender/
GridGraph? => GridUGraph
radix sort to ansi compatible

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/bits/graph_extender.h

    r1956 r1979  
    2323#include <lemon/error.h>
    2424
     25#include <lemon/bits/default_map.h>
     26
    2527namespace lemon {
    2628
    27   template <typename _Base>
    28   class GraphExtender : public _Base {
     29  template <typename Base>
     30  class GraphExtender : public Base {
    2931  public:
    3032
    31     typedef _Base Parent;
     33    typedef Base Parent;
    3234    typedef GraphExtender Graph;
     35
     36    // Base extensions
    3337
    3438    typedef typename Parent::Node Node;
     
    6064    }
    6165
     66    // Alterable extension
     67
     68    typedef AlterationNotifier<Node> NodeNotifier;
     69    typedef AlterationNotifier<Edge> EdgeNotifier;
     70
     71
     72  protected:
     73
     74    mutable NodeNotifier node_notifier;
     75    mutable EdgeNotifier edge_notifier;
     76
     77  public:
     78
     79    NodeNotifier& getNotifier(Node) const {
     80      return node_notifier;
     81    }
     82   
     83    EdgeNotifier& getNotifier(Edge) const {
     84      return edge_notifier;
     85    }
     86
     87    class NodeIt : public Node {
     88      const Graph* graph;
     89    public:
     90
     91      NodeIt() {}
     92
     93      NodeIt(Invalid i) : Node(i) { }
     94
     95      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     96        _graph.first(*static_cast<Node*>(this));
     97      }
     98
     99      NodeIt(const Graph& _graph, const Node& node)
     100        : Node(node), graph(&_graph) {}
     101
     102      NodeIt& operator++() {
     103        graph->next(*this);
     104        return *this;
     105      }
     106
     107    };
     108
     109
     110    class EdgeIt : public Edge {
     111      const Graph* graph;
     112    public:
     113
     114      EdgeIt() { }
     115
     116      EdgeIt(Invalid i) : Edge(i) { }
     117
     118      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     119        _graph.first(*static_cast<Edge*>(this));
     120      }
     121
     122      EdgeIt(const Graph& _graph, const Edge& e) :
     123        Edge(e), graph(&_graph) { }
     124
     125      EdgeIt& operator++() {
     126        graph->next(*this);
     127        return *this;
     128      }
     129
     130    };
     131
     132
     133    class OutEdgeIt : public Edge {
     134      const Graph* graph;
     135    public:
     136
     137      OutEdgeIt() { }
     138
     139      OutEdgeIt(Invalid i) : Edge(i) { }
     140
     141      OutEdgeIt(const Graph& _graph, const Node& node)
     142        : graph(&_graph) {
     143        _graph.firstOut(*this, node);
     144      }
     145
     146      OutEdgeIt(const Graph& _graph, const Edge& edge)
     147        : Edge(edge), graph(&_graph) {}
     148
     149      OutEdgeIt& operator++() {
     150        graph->nextOut(*this);
     151        return *this;
     152      }
     153
     154    };
     155
     156
     157    class InEdgeIt : public Edge {
     158      const Graph* graph;
     159    public:
     160
     161      InEdgeIt() { }
     162
     163      InEdgeIt(Invalid i) : Edge(i) { }
     164
     165      InEdgeIt(const Graph& _graph, const Node& node)
     166        : graph(&_graph) {
     167        _graph.firstIn(*this, node);
     168      }
     169
     170      InEdgeIt(const Graph& _graph, const Edge& edge) :
     171        Edge(edge), graph(&_graph) {}
     172
     173      InEdgeIt& operator++() {
     174        graph->nextIn(*this);
     175        return *this;
     176      }
     177
     178    };
     179
     180    /// \brief Base node of the iterator
     181    ///
     182    /// Returns the base node (ie. the source in this case) of the iterator
     183    Node baseNode(const OutEdgeIt &e) const {
     184      return Parent::source(e);
     185    }
     186    /// \brief Running node of the iterator
     187    ///
     188    /// Returns the running node (ie. the target in this case) of the
     189    /// iterator
     190    Node runningNode(const OutEdgeIt &e) const {
     191      return Parent::target(e);
     192    }
     193
     194    /// \brief Base node of the iterator
     195    ///
     196    /// Returns the base node (ie. the target in this case) of the iterator
     197    Node baseNode(const InEdgeIt &e) const {
     198      return Parent::target(e);
     199    }
     200    /// \brief Running node of the iterator
     201    ///
     202    /// Returns the running node (ie. the source in this case) of the
     203    /// iterator
     204    Node runningNode(const InEdgeIt &e) const {
     205      return Parent::source(e);
     206    }
     207
     208   
     209    template <typename _Value>
     210    class NodeMap
     211      : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
     212    public:
     213      typedef GraphExtender Graph;
     214      typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
     215
     216      NodeMap(const Graph& _g)
     217        : Parent(_g) {}
     218      NodeMap(const Graph& _g, const _Value& _v)
     219        : Parent(_g, _v) {}
     220
     221      NodeMap& operator=(const NodeMap& cmap) {
     222        return operator=<NodeMap>(cmap);
     223      }
     224
     225
     226      /// \brief Template assign operator.
     227      ///
     228      /// The given parameter should be conform to the ReadMap
     229      /// concecpt and could be indiced by the current item set of
     230      /// the NodeMap. In this case the value for each item
     231      /// is assigned by the value of the given ReadMap.
     232      template <typename CMap>
     233      NodeMap& operator=(const CMap& cmap) {
     234        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
     235        const typename Parent::Graph* graph = Parent::getGraph();
     236        Node it;
     237        for (graph->first(it); it != INVALID; graph->next(it)) {
     238          Parent::set(it, cmap[it]);
     239        }
     240        return *this;
     241      }
     242
     243    };
     244
     245    template <typename _Value>
     246    class EdgeMap
     247      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     248    public:
     249      typedef GraphExtender Graph;
     250      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     251
     252      EdgeMap(const Graph& _g)
     253        : Parent(_g) {}
     254      EdgeMap(const Graph& _g, const _Value& _v)
     255        : Parent(_g, _v) {}
     256
     257      EdgeMap& operator=(const EdgeMap& cmap) {
     258        return operator=<EdgeMap>(cmap);
     259      }
     260
     261      template <typename CMap>
     262      EdgeMap& operator=(const CMap& cmap) {
     263        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
     264        const typename Parent::Graph* graph = Parent::getGraph();
     265        Edge it;
     266        for (graph->first(it); it != INVALID; graph->next(it)) {
     267          Parent::set(it, cmap[it]);
     268        }
     269        return *this;
     270      }
     271    };
     272
     273
     274    Node addNode() {
     275      Node node = Parent::addNode();
     276      getNotifier(Node()).add(node);
     277      return node;
     278    }
     279   
     280    Edge addEdge(const Node& from, const Node& to) {
     281      Edge edge = Parent::addEdge(from, to);
     282      getNotifier(Edge()).add(edge);
     283      return edge;
     284    }
     285
     286    void clear() {
     287      getNotifier(Edge()).clear();
     288      getNotifier(Node()).clear();
     289      Parent::clear();
     290    }
     291
     292
     293    void erase(const Node& node) {
     294      Edge edge;
     295      Parent::firstOut(edge, node);
     296      while (edge != INVALID ) {
     297        erase(edge);
     298        Parent::firstOut(edge, node);
     299      }
     300
     301      Parent::firstIn(edge, node);
     302      while (edge != INVALID ) {
     303        erase(edge);
     304        Parent::firstIn(edge, node);
     305      }
     306
     307      getNotifier(Node()).erase(node);
     308      Parent::erase(node);
     309    }
     310   
     311    void erase(const Edge& edge) {
     312      getNotifier(Edge()).erase(edge);
     313      Parent::erase(edge);
     314    }
     315
     316
     317    ~GraphExtender() {
     318      getNotifier(Edge()).clear();
     319      getNotifier(Node()).clear();
     320    }
    62321  };
    63322
    64   template <typename _Base>
    65   class UGraphExtender : public _Base {
    66     typedef _Base Parent;
    67     typedef UGraphExtender Graph;
     323  template <typename Base>
     324  class UGraphBaseExtender : public Base {
    68325
    69326  public:
    70327
     328    typedef Base Parent;
    71329    typedef typename Parent::Edge UEdge;
    72330    typedef typename Parent::Node Node;
    73331
     332    typedef True UndirectedTag;
     333
    74334    class Edge : public UEdge {
    75       friend class UGraphExtender;
     335      friend class UGraphBaseExtender;
    76336
    77337    protected:
    78       // FIXME: Marci use opposite logic in his graph adaptors. It would
    79       // be reasonable to syncronize...
    80338      bool forward;
    81339
     
    102360
    103361
    104     /// \brief Edge of opposite direction.
    105     ///
    106     /// Returns the Edge of opposite direction.
    107     Edge oppositeEdge(const Edge &e) const {
    108       return Edge(e,!e.forward);
    109     }
    110 
    111   public:
    112     /// \todo Shouldn't the "source" of an undirected edge be called "aNode"
    113     /// or something???
     362
    114363    using Parent::source;
    115364
     
    119368    }
    120369
    121     /// \todo Shouldn't the "target" of an undirected edge be called "bNode"
    122     /// or something???
    123370    using Parent::target;
    124371
     
    126373    Node target(const Edge &e) const {
    127374      return e.forward ? Parent::target(e) : Parent::source(e);
    128     }
    129 
    130     Node oppositeNode(const Node &n, const UEdge &e) const {
    131       if( n == Parent::source(e))
    132         return Parent::target(e);
    133       else if( n == Parent::target(e))
    134         return Parent::source(e);
    135       else
    136         return INVALID;
    137     }
    138 
    139     /// \brief Directed edge from an undirected edge and a source node.
    140     ///
    141     /// Returns a (directed) Edge corresponding to the specified UEdge
    142     /// and source Node.
    143     ///
    144     Edge direct(const UEdge &ue, const Node &s) const {
    145       return Edge(ue, s == source(ue));
    146375    }
    147376
     
    164393
    165394    using Parent::first;
     395    using Parent::next;
     396
    166397    void first(Edge &e) const {
    167398      Parent::first(e);
     
    169400    }
    170401
    171     using Parent::next;
    172402    void next(Edge &e) const {
    173403      if( e.forward ) {
     
    179409      }
    180410    }
    181 
    182   public:
    183411
    184412    void firstOut(Edge &e, const Node &n) const {
     
    230458    }
    231459
    232     void firstInc(UEdge &e, const Node &n) const {
    233       Parent::firstOut(e, n);
    234       if (e != INVALID) return;
    235       Parent::firstIn(e, n);
    236     }
    237     void nextInc(UEdge &e, const Node &n) const {
    238       if (Parent::source(e) == n) {
    239         Parent::nextOut(e);
    240         if (e != INVALID) return;
    241         Parent::firstIn(e, n);
    242       } else {
    243         Parent::nextIn(e);
    244       }
    245     }
    246 
    247460    void firstInc(UEdge &e, bool &d, const Node &n) const {
    248461      d = true;
     
    252465      Parent::firstIn(e, n);
    253466    }
     467
    254468    void nextInc(UEdge &e, bool &d) const {
    255469      if (d) {
     
    264478    }
    265479
    266     // Miscellaneous stuff:
    267 
    268     /// \todo these methods (id, maxEdgeId) should be moved into separate
    269     /// Extender
    270 
    271     // using Parent::id;
    272     // Using "using" is not a good idea, cause it could be that there is
    273     // no "id" in Parent...
     480    Node nodeFromId(int id) const {
     481      return Parent::nodeFromId(id);
     482    }
     483
     484    Edge edgeFromId(int id) const {
     485      return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
     486    }
     487
     488    UEdge uEdgeFromId(int id) const {
     489      return Parent::edgeFromId(id >> 1);
     490    }
    274491
    275492    int id(const Node &n) const {
     
    297514    }
    298515
    299     int maxId(Node) const {
    300       return maxNodeId();
    301     }
    302 
    303     int maxId(Edge) const {
    304       return maxEdgeId();
    305     }
    306     int maxId(UEdge) const {
    307       return maxUEdgeId();
    308     }
    309516
    310517    int edgeNum() const {
     
    315522      return Parent::edgeNum();
    316523    }
    317 
    318     Node nodeFromId(int id) const {
    319       return Parent::nodeFromId(id);
    320     }
    321 
    322     Edge edgeFromId(int id) const {
    323       return direct(Parent::edgeFromId(id >> 1), bool(id & 1));
    324     }
    325 
    326     UEdge uEdgeFromId(int id) const {
    327       return Parent::edgeFromId(id >> 1);
    328     }
    329 
    330     Node fromId(int id, Node) const {
    331       return nodeFromId(id);
    332     }
    333 
    334     Edge fromId(int id, Edge) const {
    335       return edgeFromId(id);
    336     }
    337 
    338     UEdge fromId(int id, UEdge) const {
    339       return uEdgeFromId(id);
    340     }
    341 
    342524
    343525    Edge findEdge(Node source, Node target, Edge prev) const {
     
    376558      return INVALID;
    377559    }
    378 
    379560  };
    380561
    381562
    382   template <typename _Base>
    383   class BpUGraphExtender : public _Base {
     563  template <typename Base>
     564  class UGraphExtender : public Base {
    384565  public:
    385     typedef _Base Parent;
    386     typedef BpUGraphExtender Graph;
     566   
     567    typedef Base Parent;
     568    typedef UGraphExtender Graph;
     569
     570    typedef typename Parent::Node Node;
     571    typedef typename Parent::Edge Edge;
     572    typedef typename Parent::UEdge UEdge;
     573
     574    // UGraph extension   
     575
     576    int maxId(Node) const {
     577      return Parent::maxNodeId();
     578    }
     579
     580    int maxId(Edge) const {
     581      return Parent::maxEdgeId();
     582    }
     583
     584    int maxId(UEdge) const {
     585      return Parent::maxUEdgeId();
     586    }
     587
     588    Node fromId(int id, Node) const {
     589      return Parent::nodeFromId(id);
     590    }
     591
     592    Edge fromId(int id, Edge) const {
     593      return Parent::edgeFromId(id);
     594    }
     595
     596    UEdge fromId(int id, UEdge) const {
     597      return Parent::uEdgeFromId(id);
     598    }
     599
     600    Node oppositeNode(const Node &n, const UEdge &e) const {
     601      if( n == Parent::source(e))
     602        return Parent::target(e);
     603      else if( n == Parent::target(e))
     604        return Parent::source(e);
     605      else
     606        return INVALID;
     607    }
     608
     609    Edge oppositeEdge(const Edge &e) const {
     610      return Parent::direct(e, !Parent::direction(e));
     611    }
     612
     613    using Parent::direct;
     614    Edge direct(const UEdge &ue, const Node &s) const {
     615      return Parent::direct(ue, Parent::source(ue) == s);
     616    }
     617
     618    // Alterable extension
     619
     620    typedef AlterationNotifier<Node> NodeNotifier;
     621    typedef AlterationNotifier<Edge> EdgeNotifier;
     622    typedef AlterationNotifier<UEdge> UEdgeNotifier;
     623
     624
     625  protected:
     626
     627    mutable NodeNotifier node_notifier;
     628    mutable EdgeNotifier edge_notifier;
     629    mutable UEdgeNotifier uedge_notifier;
     630
     631  public:
     632
     633    NodeNotifier& getNotifier(Node) const {
     634      return node_notifier;
     635    }
     636   
     637    EdgeNotifier& getNotifier(Edge) const {
     638      return edge_notifier;
     639    }
     640
     641    UEdgeNotifier& getNotifier(UEdge) const {
     642      return uedge_notifier;
     643    }
     644
     645
     646
     647    class NodeIt : public Node {
     648      const Graph* graph;
     649    public:
     650
     651      NodeIt() {}
     652
     653      NodeIt(Invalid i) : Node(i) { }
     654
     655      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     656        _graph.first(*static_cast<Node*>(this));
     657      }
     658
     659      NodeIt(const Graph& _graph, const Node& node)
     660        : Node(node), graph(&_graph) {}
     661
     662      NodeIt& operator++() {
     663        graph->next(*this);
     664        return *this;
     665      }
     666
     667    };
     668
     669
     670    class EdgeIt : public Edge {
     671      const Graph* graph;
     672    public:
     673
     674      EdgeIt() { }
     675
     676      EdgeIt(Invalid i) : Edge(i) { }
     677
     678      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     679        _graph.first(*static_cast<Edge*>(this));
     680      }
     681
     682      EdgeIt(const Graph& _graph, const Edge& e) :
     683        Edge(e), graph(&_graph) { }
     684
     685      EdgeIt& operator++() {
     686        graph->next(*this);
     687        return *this;
     688      }
     689
     690    };
     691
     692
     693    class OutEdgeIt : public Edge {
     694      const Graph* graph;
     695    public:
     696
     697      OutEdgeIt() { }
     698
     699      OutEdgeIt(Invalid i) : Edge(i) { }
     700
     701      OutEdgeIt(const Graph& _graph, const Node& node)
     702        : graph(&_graph) {
     703        _graph.firstOut(*this, node);
     704      }
     705
     706      OutEdgeIt(const Graph& _graph, const Edge& edge)
     707        : Edge(edge), graph(&_graph) {}
     708
     709      OutEdgeIt& operator++() {
     710        graph->nextOut(*this);
     711        return *this;
     712      }
     713
     714    };
     715
     716
     717    class InEdgeIt : public Edge {
     718      const Graph* graph;
     719    public:
     720
     721      InEdgeIt() { }
     722
     723      InEdgeIt(Invalid i) : Edge(i) { }
     724
     725      InEdgeIt(const Graph& _graph, const Node& node)
     726        : graph(&_graph) {
     727        _graph.firstIn(*this, node);
     728      }
     729
     730      InEdgeIt(const Graph& _graph, const Edge& edge) :
     731        Edge(edge), graph(&_graph) {}
     732
     733      InEdgeIt& operator++() {
     734        graph->nextIn(*this);
     735        return *this;
     736      }
     737
     738    };
     739
     740
     741    class UEdgeIt : public Parent::UEdge {
     742      const Graph* graph;
     743    public:
     744
     745      UEdgeIt() { }
     746
     747      UEdgeIt(Invalid i) : UEdge(i) { }
     748
     749      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
     750        _graph.first(*static_cast<UEdge*>(this));
     751      }
     752
     753      UEdgeIt(const Graph& _graph, const UEdge& e) :
     754        UEdge(e), graph(&_graph) { }
     755
     756      UEdgeIt& operator++() {
     757        graph->next(*this);
     758        return *this;
     759      }
     760
     761    };
     762
     763    class IncEdgeIt : public Parent::UEdge {
     764      friend class UGraphExtender;
     765      const Graph* graph;
     766      bool direction;
     767    public:
     768
     769      IncEdgeIt() { }
     770
     771      IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }
     772
     773      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     774        _graph.firstInc(*this, direction, n);
     775      }
     776
     777      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
     778        : graph(&_graph), UEdge(ue) {
     779        direction = (_graph.source(ue) == n);
     780      }
     781
     782      IncEdgeIt& operator++() {
     783        graph->nextInc(*this, direction);
     784        return *this;
     785      }
     786    };
     787
     788    /// \brief Base node of the iterator
     789    ///
     790    /// Returns the base node (ie. the source in this case) of the iterator
     791    Node baseNode(const OutEdgeIt &e) const {
     792      return Parent::source((Edge)e);
     793    }
     794    /// \brief Running node of the iterator
     795    ///
     796    /// Returns the running node (ie. the target in this case) of the
     797    /// iterator
     798    Node runningNode(const OutEdgeIt &e) const {
     799      return Parent::target((Edge)e);
     800    }
     801
     802    /// \brief Base node of the iterator
     803    ///
     804    /// Returns the base node (ie. the target in this case) of the iterator
     805    Node baseNode(const InEdgeIt &e) const {
     806      return Parent::target((Edge)e);
     807    }
     808    /// \brief Running node of the iterator
     809    ///
     810    /// Returns the running node (ie. the source in this case) of the
     811    /// iterator
     812    Node runningNode(const InEdgeIt &e) const {
     813      return Parent::source((Edge)e);
     814    }
     815
     816    /// Base node of the iterator
     817    ///
     818    /// Returns the base node of the iterator
     819    Node baseNode(const IncEdgeIt &e) const {
     820      return e.direction ? source(e) : target(e);
     821    }
     822    /// Running node of the iterator
     823    ///
     824    /// Returns the running node of the iterator
     825    Node runningNode(const IncEdgeIt &e) const {
     826      return e.direction ? target(e) : source(e);
     827    }
     828
     829    // Mappable extension
     830
     831    template <typename _Value>
     832    class NodeMap
     833      : public IterableMapExtender<DefaultMap<Graph, Node, _Value> > {
     834    public:
     835      typedef UGraphExtender Graph;
     836      typedef IterableMapExtender<DefaultMap<Graph, Node, _Value> > Parent;
     837
     838      NodeMap(const Graph& _g)
     839        : Parent(_g) {}
     840      NodeMap(const Graph& _g, const _Value& _v)
     841        : Parent(_g, _v) {}
     842
     843      NodeMap& operator=(const NodeMap& cmap) {
     844        return operator=<NodeMap>(cmap);
     845      }
     846
     847
     848      /// \brief Template assign operator.
     849      ///
     850      /// The given parameter should be conform to the ReadMap
     851      /// concecpt and could be indiced by the current item set of
     852      /// the NodeMap. In this case the value for each item
     853      /// is assigned by the value of the given ReadMap.
     854      template <typename CMap>
     855      NodeMap& operator=(const CMap& cmap) {
     856        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
     857        const typename Parent::Graph* graph = Parent::getGraph();
     858        Node it;
     859        for (graph->first(it); it != INVALID; graph->next(it)) {
     860          Parent::set(it, cmap[it]);
     861        }
     862        return *this;
     863      }
     864
     865    };
     866
     867    template <typename _Value>
     868    class EdgeMap
     869      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     870    public:
     871      typedef UGraphExtender Graph;
     872      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     873
     874      EdgeMap(const Graph& _g)
     875        : Parent(_g) {}
     876      EdgeMap(const Graph& _g, const _Value& _v)
     877        : Parent(_g, _v) {}
     878
     879      EdgeMap& operator=(const EdgeMap& cmap) {
     880        return operator=<EdgeMap>(cmap);
     881      }
     882
     883      template <typename CMap>
     884      EdgeMap& operator=(const CMap& cmap) {
     885        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
     886        const typename Parent::Graph* graph = Parent::getGraph();
     887        Edge it;
     888        for (graph->first(it); it != INVALID; graph->next(it)) {
     889          Parent::set(it, cmap[it]);
     890        }
     891        return *this;
     892      }
     893    };
     894
     895
     896    template <typename _Value>
     897    class UEdgeMap
     898      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
     899    public:
     900      typedef UGraphExtender Graph;
     901      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;
     902
     903      UEdgeMap(const Graph& _g)
     904        : Parent(_g) {}
     905      UEdgeMap(const Graph& _g, const _Value& _v)
     906        : Parent(_g, _v) {}
     907
     908      UEdgeMap& operator=(const UEdgeMap& cmap) {
     909        return operator=<UEdgeMap>(cmap);
     910      }
     911
     912      template <typename CMap>
     913      UEdgeMap& operator=(const CMap& cmap) {
     914        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
     915        const typename Parent::Graph* graph = Parent::getGraph();
     916        UEdge it;
     917        for (graph->first(it); it != INVALID; graph->next(it)) {
     918          Parent::set(it, cmap[it]);
     919        }
     920        return *this;
     921      }
     922    };
     923
     924    // Alteration extension
     925
     926    Node addNode() {
     927      Node node = Parent::addNode();
     928      getNotifier(Node()).add(node);
     929      return node;
     930    }
     931
     932    UEdge addEdge(const Node& from, const Node& to) {
     933      UEdge uedge = Parent::addEdge(from, to);
     934      getNotifier(UEdge()).add(uedge);
     935      getNotifier(Edge()).add(Parent::direct(uedge, true));
     936      getNotifier(Edge()).add(Parent::direct(uedge, false));
     937      return uedge;
     938    }
     939   
     940    void clear() {
     941      getNotifier(Edge()).clear();
     942      getNotifier(UEdge()).clear();
     943      getNotifier(Node()).clear();
     944      Parent::clear();
     945    }
     946
     947    void erase(const Node& node) {
     948      Edge edge;
     949      Parent::firstOut(edge, node);
     950      while (edge != INVALID ) {
     951        erase(edge);
     952        Parent::firstOut(edge, node);
     953      }
     954
     955      Parent::firstIn(edge, node);
     956      while (edge != INVALID ) {
     957        erase(edge);
     958        Parent::firstIn(edge, node);
     959      }
     960
     961      getNotifier(Node()).erase(node);
     962      Parent::erase(node);
     963    }
     964
     965    void erase(const UEdge& uedge) {
     966      getNotifier(Edge()).erase(Parent::direct(uedge, true));
     967      getNotifier(Edge()).erase(Parent::direct(uedge, false));
     968      getNotifier(UEdge()).erase(uedge);
     969      Parent::erase(uedge);
     970    }
     971
     972    ~UGraphExtender() {
     973      getNotifier(Edge()).clear();
     974      getNotifier(UEdge()).clear();
     975      getNotifier(Node()).clear();
     976    }
     977
     978  };
     979
     980
     981  template <typename Base>
     982  class BpUGraphBaseExtender : public Base {
     983  public:
     984    typedef Base Parent;
     985    typedef BpUGraphBaseExtender Graph;
    387986
    388987    typedef typename Parent::Node Node;
    389988    typedef typename Parent::Edge UEdge;
    390989
     990
    391991    using Parent::first;
    392992    using Parent::next;
    393993
    394994    using Parent::id;
     995
     996    class ANode : public Node {
     997      friend class BpUGraphBaseExtender;
     998    public:
     999      ANode() {}
     1000      ANode(const Node& node) : Node(node) {
     1001        LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
     1002                     typename Parent::NodeSetError());
     1003      }
     1004      ANode(Invalid) : Node(INVALID) {}
     1005    };
     1006
     1007    void first(ANode& node) const {
     1008      Parent::firstANode(static_cast<Node&>(node));
     1009    }
     1010    void next(ANode& node) const {
     1011      Parent::nextANode(static_cast<Node&>(node));
     1012    }
     1013
     1014    int id(const ANode& node) const {
     1015      return Parent::aNodeId(node);
     1016    }
     1017
     1018    class BNode : public Node {
     1019      friend class BpUGraphBaseExtender;
     1020    public:
     1021      BNode() {}
     1022      BNode(const Node& node) : Node(node) {
     1023        LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
     1024                     typename Parent::NodeSetError());
     1025      }
     1026      BNode(Invalid) : Node(INVALID) {}
     1027    };
     1028
     1029    void first(BNode& node) const {
     1030      Parent::firstBNode(static_cast<Node&>(node));
     1031    }
     1032    void next(BNode& node) const {
     1033      Parent::nextBNode(static_cast<Node&>(node));
     1034    }
     1035 
     1036    int id(const BNode& node) const {
     1037      return Parent::aNodeId(node);
     1038    }
    3951039
    3961040    Node source(const UEdge& edge) const {
     
    4281072
    4291073    class Edge : public UEdge {
    430       friend class BpUGraphExtender;
     1074      friend class BpUGraphBaseExtender;
    4311075    protected:
    4321076      bool forward;
     
    5051149    }
    5061150
     1151    int id(const Edge& edge) const {
     1152      return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
     1153    }
     1154    Edge edgeFromId(int id) const {
     1155      return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
     1156    }
     1157    int maxEdgeId() const {
     1158      return (Parent::maxId(UEdge()) << 1) + 1;
     1159    }
     1160
    5071161    bool direction(const Edge& edge) const {
    5081162      return edge.forward;
    5091163    }
    5101164
    511     Edge direct(const UEdge& edge, const Node& node) const {
    512       return Edge(edge, node == Parent::source(edge));
    513     }
    514 
    5151165    Edge direct(const UEdge& edge, bool direction) const {
    5161166      return Edge(edge, direction);
    5171167    }
     1168  };
     1169
     1170  template <typename Base>
     1171  class BpUGraphExtender : public Base {
     1172  public:
     1173    typedef Base Parent;
     1174    typedef BpUGraphExtender Graph;
     1175
     1176    typedef typename Parent::Node Node;
     1177    typedef typename Parent::BNode BNode;
     1178    typedef typename Parent::ANode ANode;
     1179    typedef typename Parent::Edge Edge;
     1180    typedef typename Parent::UEdge UEdge;
    5181181
    5191182    Node oppositeNode(const UEdge& edge, const Node& node) const {
     
    5221185    }
    5231186
     1187    using Parent::direct;
     1188    Edge direct(const UEdge& edge, const Node& node) const {
     1189      return Edge(edge, node == Parent::source(edge));
     1190    }
     1191
    5241192    Edge oppositeEdge(const Edge& edge) const {
    525       return Edge(edge, !edge.forward);
    526     }
    527 
    528     int id(const Edge& edge) const {
    529       return (Parent::id(edge) << 1) + (edge.forward ? 0 : 1);
    530     }
    531     Edge edgeFromId(int id) const {
    532       return Edge(Parent::fromId(id >> 1, UEdge()), (id & 1) == 0);
    533     }
    534     int maxEdgeId() const {
    535       return (Parent::maxId(UEdge()) << 1) + 1;
    536     }
    537 
    538     class ANode : public Node {
    539       friend class BpUGraphExtender;
    540     public:
    541       ANode() {}
    542       ANode(const Node& node) : Node(node) {
    543         LEMON_ASSERT(Parent::aNode(node) || node == INVALID,
    544                      typename Parent::NodeSetError());
    545       }
    546       ANode(Invalid) : Node(INVALID) {}
    547     };
    548 
    549     void first(ANode& node) const {
    550       Parent::firstANode(static_cast<Node&>(node));
    551     }
    552     void next(ANode& node) const {
    553       Parent::nextANode(static_cast<Node&>(node));
    554     }
    555 
    556     int id(const ANode& node) const {
    557       return Parent::aNodeId(node);
    558     }
    559 
    560     class BNode : public Node {
    561       friend class BpUGraphExtender;
    562     public:
    563       BNode() {}
    564       BNode(const Node& node) : Node(node) {
    565         LEMON_ASSERT(Parent::bNode(node) || node == INVALID,
    566                      typename Parent::NodeSetError());
    567       }
    568       BNode(Invalid) : Node(INVALID) {}
    569     };
    570 
    571     void first(BNode& node) const {
    572       Parent::firstBNode(static_cast<Node&>(node));
    573     }
    574     void next(BNode& node) const {
    575       Parent::nextBNode(static_cast<Node&>(node));
    576     }
    577  
    578     int id(const BNode& node) const {
    579       return Parent::aNodeId(node);
    580     }
    581 
     1193      return Parent::direct(edge, !Parent::direction(edge));
     1194    }
    5821195
    5831196
     
    5921205    }
    5931206    int maxId(Edge) const {
    594       return maxEdgeId();
     1207      return Parent::maxEdgeId();
    5951208    }
    5961209    int maxId(UEdge) const {
    597       return maxUEdgeId();
     1210      return Parent::maxUEdgeId();
    5981211    }
    5991212
     
    6091222    }
    6101223    Edge fromId(int id, Edge) const {
    611       return edgeFromId(id);
     1224      return Parent::edgeFromId(id);
    6121225    }
    6131226    UEdge fromId(int id, UEdge) const {
    614       return uEdgeFromId(id);
    615     }
     1227      return Parent::uEdgeFromId(id);
     1228    } 
     1229 
     1230    typedef AlterationNotifier<Node> NodeNotifier;
     1231    typedef AlterationNotifier<BNode> BNodeNotifier;
     1232    typedef AlterationNotifier<ANode> ANodeNotifier;
     1233    typedef AlterationNotifier<Edge> EdgeNotifier;
     1234    typedef AlterationNotifier<UEdge> UEdgeNotifier;
     1235
     1236  protected:
     1237
     1238    mutable NodeNotifier nodeNotifier;
     1239    mutable BNodeNotifier bNodeNotifier;
     1240    mutable ANodeNotifier aNodeNotifier;
     1241    mutable EdgeNotifier edgeNotifier;
     1242    mutable UEdgeNotifier uEdgeNotifier;
     1243
     1244  public:
     1245
     1246    NodeNotifier& getNotifier(Node) const {
     1247      return nodeNotifier;
     1248    }
     1249
     1250    BNodeNotifier& getNotifier(BNode) const {
     1251      return bNodeNotifier;
     1252    }
     1253
     1254    ANodeNotifier& getNotifier(ANode) const {
     1255      return aNodeNotifier;
     1256    }
     1257
     1258    EdgeNotifier& getNotifier(Edge) const {
     1259      return edgeNotifier;
     1260    }
     1261
     1262    UEdgeNotifier& getNotifier(UEdge) const {
     1263      return uEdgeNotifier;
     1264    }
     1265
     1266    ~BpUGraphExtender() {
     1267      getNotifier(UEdge()).clear();
     1268      getNotifier(Edge()).clear();
     1269      getNotifier(ANode()).clear();
     1270      getNotifier(BNode()).clear();
     1271      getNotifier(Node()).clear();
     1272    }
     1273
     1274 
     1275    class NodeIt : public Node {
     1276      const Graph* graph;
     1277    public:
     1278   
     1279      NodeIt() { }
     1280   
     1281      NodeIt(Invalid i) : Node(INVALID) { }
     1282   
     1283      explicit NodeIt(const Graph& _graph) : graph(&_graph) {
     1284        graph->first(static_cast<Node&>(*this));
     1285      }
     1286
     1287      NodeIt(const Graph& _graph, const Node& node)
     1288        : Node(node), graph(&_graph) { }
     1289   
     1290      NodeIt& operator++() {
     1291        graph->next(*this);
     1292        return *this;
     1293      }
     1294
     1295    };
     1296
     1297    class ANodeIt : public Node {
     1298      friend class BpUGraphExtender;
     1299      const Graph* graph;
     1300    public:
     1301   
     1302      ANodeIt() { }
     1303   
     1304      ANodeIt(Invalid i) : Node(INVALID) { }
     1305   
     1306      explicit ANodeIt(const Graph& _graph) : graph(&_graph) {
     1307        graph->firstANode(static_cast<Node&>(*this));
     1308      }
     1309
     1310      ANodeIt(const Graph& _graph, const Node& node)
     1311        : Node(node), graph(&_graph) {}
     1312   
     1313      ANodeIt& operator++() {
     1314        graph->nextANode(*this);
     1315        return *this;
     1316      }
     1317    };
     1318
     1319    class BNodeIt : public Node {
     1320      friend class BpUGraphExtender;
     1321      const Graph* graph;
     1322    public:
     1323   
     1324      BNodeIt() { }
     1325   
     1326      BNodeIt(Invalid i) : Node(INVALID) { }
     1327   
     1328      explicit BNodeIt(const Graph& _graph) : graph(&_graph) {
     1329        graph->firstBNode(static_cast<Node&>(*this));
     1330      }
     1331
     1332      BNodeIt(const Graph& _graph, const Node& node)
     1333        : Node(node), graph(&_graph) {}
     1334   
     1335      BNodeIt& operator++() {
     1336        graph->nextBNode(*this);
     1337        return *this;
     1338      }
     1339    };
     1340
     1341    class EdgeIt : public Edge {
     1342      friend class BpUGraphExtender;
     1343      const Graph* graph;
     1344    public:
     1345   
     1346      EdgeIt() { }
     1347   
     1348      EdgeIt(Invalid i) : Edge(INVALID) { }
     1349   
     1350      explicit EdgeIt(const Graph& _graph) : graph(&_graph) {
     1351        graph->first(static_cast<Edge&>(*this));
     1352      }
     1353
     1354      EdgeIt(const Graph& _graph, const Edge& edge)
     1355        : Edge(edge), graph(&_graph) { }
     1356   
     1357      EdgeIt& operator++() {
     1358        graph->next(*this);
     1359        return *this;
     1360      }
     1361
     1362    };
     1363
     1364    class UEdgeIt : public UEdge {
     1365      friend class BpUGraphExtender;
     1366      const Graph* graph;
     1367    public:
     1368   
     1369      UEdgeIt() { }
     1370   
     1371      UEdgeIt(Invalid i) : UEdge(INVALID) { }
     1372   
     1373      explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {
     1374        graph->first(static_cast<UEdge&>(*this));
     1375      }
     1376
     1377      UEdgeIt(const Graph& _graph, const UEdge& edge)
     1378        : UEdge(edge), graph(&_graph) { }
     1379   
     1380      UEdgeIt& operator++() {
     1381        graph->next(*this);
     1382        return *this;
     1383      }
     1384    };
     1385
     1386    class OutEdgeIt : public Edge {
     1387      friend class BpUGraphExtender;
     1388      const Graph* graph;
     1389    public:
     1390   
     1391      OutEdgeIt() { }
     1392   
     1393      OutEdgeIt(Invalid i) : Edge(i) { }
     1394   
     1395      OutEdgeIt(const Graph& _graph, const Node& node)
     1396        : graph(&_graph) {
     1397        graph->firstOut(*this, node);
     1398      }
     1399   
     1400      OutEdgeIt(const Graph& _graph, const Edge& edge)
     1401        : Edge(edge), graph(&_graph) {}
     1402   
     1403      OutEdgeIt& operator++() {
     1404        graph->nextOut(*this);
     1405        return *this;
     1406      }
     1407
     1408    };
     1409
     1410
     1411    class InEdgeIt : public Edge {
     1412      friend class BpUGraphExtender;
     1413      const Graph* graph;
     1414    public:
     1415   
     1416      InEdgeIt() { }
     1417   
     1418      InEdgeIt(Invalid i) : Edge(i) { }
     1419   
     1420      InEdgeIt(const Graph& _graph, const Node& node)
     1421        : graph(&_graph) {
     1422        graph->firstIn(*this, node);
     1423      }
     1424   
     1425      InEdgeIt(const Graph& _graph, const Edge& edge) :
     1426        Edge(edge), graph(&_graph) {}
     1427   
     1428      InEdgeIt& operator++() {
     1429        graph->nextIn(*this);
     1430        return *this;
     1431      }
     1432
     1433    };
     1434 
     1435    /// \brief Base node of the iterator
     1436    ///
     1437    /// Returns the base node (ie. the source in this case) of the iterator
     1438    Node baseNode(const OutEdgeIt &e) const {
     1439      return Parent::source((Edge&)e);
     1440    }
     1441    /// \brief Running node of the iterator
     1442    ///
     1443    /// Returns the running node (ie. the target in this case) of the
     1444    /// iterator
     1445    Node runningNode(const OutEdgeIt &e) const {
     1446      return Parent::target((Edge&)e);
     1447    }
     1448 
     1449    /// \brief Base node of the iterator
     1450    ///
     1451    /// Returns the base node (ie. the target in this case) of the iterator
     1452    Node baseNode(const InEdgeIt &e) const {
     1453      return Parent::target((Edge&)e);
     1454    }
     1455    /// \brief Running node of the iterator
     1456    ///
     1457    /// Returns the running node (ie. the source in this case) of the
     1458    /// iterator
     1459    Node runningNode(const InEdgeIt &e) const {
     1460      return Parent::source((Edge&)e);
     1461    }
     1462 
     1463    class IncEdgeIt : public Parent::UEdge {
     1464      friend class BpUGraphExtender;
     1465      const Graph* graph;
     1466      bool direction;
     1467    public:
     1468   
     1469      IncEdgeIt() { }
     1470   
     1471      IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }
     1472   
     1473      IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {
     1474        graph->firstInc(*this, direction, n);
     1475      }
     1476
     1477      IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)
     1478        : graph(&_graph), UEdge(ue) {
     1479        direction = (graph->source(ue) == n);
     1480      }
     1481
     1482      IncEdgeIt& operator++() {
     1483        graph->nextInc(*this, direction);
     1484        return *this;
     1485      }
     1486    };
     1487 
     1488
     1489    /// Base node of the iterator
     1490    ///
     1491    /// Returns the base node of the iterator
     1492    Node baseNode(const IncEdgeIt &e) const {
     1493      return e.direction ? source(e) : target(e);
     1494    }
     1495
     1496    /// Running node of the iterator
     1497    ///
     1498    /// Returns the running node of the iterator
     1499    Node runningNode(const IncEdgeIt &e) const {
     1500      return e.direction ? target(e) : source(e);
     1501    }
     1502
     1503    template <typename _Value>
     1504    class ANodeMap
     1505      : public IterableMapExtender<DefaultMap<Graph, ANode, _Value> > {
     1506    public:
     1507      typedef BpUGraphExtender Graph;
     1508      typedef IterableMapExtender<DefaultMap<Graph, ANode, _Value> >
     1509      Parent;
     1510   
     1511      ANodeMap(const Graph& _g)
     1512        : Parent(_g) {}
     1513      ANodeMap(const Graph& _g, const _Value& _v)
     1514        : Parent(_g, _v) {}
     1515   
     1516      ANodeMap& operator=(const ANodeMap& cmap) {
     1517        return operator=<ANodeMap>(cmap);
     1518      }
     1519   
     1520
     1521      /// \brief Template assign operator.
     1522      ///
     1523      /// The given parameter should be conform to the ReadMap
     1524      /// concept and could be indiced by the current item set of
     1525      /// the ANodeMap. In this case the value for each item
     1526      /// is assigned by the value of the given ReadMap.
     1527      template <typename CMap>
     1528      ANodeMap& operator=(const CMap& cmap) {
     1529        checkConcept<concept::ReadMap<ANode, _Value>, CMap>();
     1530        const typename Parent::Graph* graph = Parent::getGraph();
     1531        ANode it;
     1532        for (graph->first(it); it != INVALID; graph->next(it)) {
     1533          Parent::set(it, cmap[it]);
     1534        }
     1535        return *this;
     1536      }
     1537   
     1538    };
     1539
     1540    template <typename _Value>
     1541    class BNodeMap
     1542      : public IterableMapExtender<DefaultMap<Graph, BNode, _Value> > {
     1543    public:
     1544      typedef BpUGraphExtender Graph;
     1545      typedef IterableMapExtender<DefaultMap<Graph, BNode, _Value> >
     1546      Parent;
     1547   
     1548      BNodeMap(const Graph& _g)
     1549        : Parent(_g) {}
     1550      BNodeMap(const Graph& _g, const _Value& _v)
     1551        : Parent(_g, _v) {}
     1552   
     1553      BNodeMap& operator=(const BNodeMap& cmap) {
     1554        return operator=<BNodeMap>(cmap);
     1555      }
     1556   
     1557
     1558      /// \brief Template assign operator.
     1559      ///
     1560      /// The given parameter should be conform to the ReadMap
     1561      /// concept and could be indiced by the current item set of
     1562      /// the BNodeMap. In this case the value for each item
     1563      /// is assigned by the value of the given ReadMap.
     1564      template <typename CMap>
     1565      BNodeMap& operator=(const CMap& cmap) {
     1566        checkConcept<concept::ReadMap<BNode, _Value>, CMap>();
     1567        const typename Parent::Graph* graph = Parent::getGraph();
     1568        BNode it;
     1569        for (graph->first(it); it != INVALID; graph->next(it)) {
     1570          Parent::set(it, cmap[it]);
     1571        }
     1572        return *this;
     1573      }
     1574   
     1575    };
     1576
     1577  protected:
     1578
     1579    template <typename _Value>
     1580    class NodeMapBase : public NodeNotifier::ObserverBase {
     1581    public:
     1582      typedef BpUGraphExtender Graph;
     1583
     1584      typedef Node Key;
     1585      typedef _Value Value;
     1586
     1587      /// The reference type of the map;
     1588      typedef typename BNodeMap<_Value>::Reference Reference;
     1589      /// The pointer type of the map;
     1590      typedef typename BNodeMap<_Value>::Pointer Pointer;
     1591     
     1592      /// The const value type of the map.
     1593      typedef const Value ConstValue;
     1594      /// The const reference type of the map;
     1595      typedef typename BNodeMap<_Value>::ConstReference ConstReference;
     1596      /// The pointer type of the map;
     1597      typedef typename BNodeMap<_Value>::ConstPointer ConstPointer;
     1598
     1599      typedef True ReferenceMapTag;
     1600
     1601      NodeMapBase(const Graph& _g)
     1602        : graph(&_g), bNodeMap(_g), aNodeMap(_g) {
     1603        NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
     1604      }
     1605      NodeMapBase(const Graph& _g, const _Value& _v)
     1606        : graph(&_g), bNodeMap(_g, _v),
     1607          aNodeMap(_g, _v) {
     1608        NodeNotifier::ObserverBase::attach(_g.getNotifier(Node()));
     1609      }
     1610
     1611      virtual ~NodeMapBase() {     
     1612        if (NodeNotifier::ObserverBase::attached()) {
     1613          NodeNotifier::ObserverBase::detach();
     1614        }
     1615      }
     1616   
     1617      ConstReference operator[](const Key& node) const {
     1618        if (Parent::aNode(node)) {
     1619          return aNodeMap[node];
     1620        } else {
     1621          return bNodeMap[node];
     1622        }
     1623      }
     1624
     1625      Reference operator[](const Key& node) {
     1626        if (Parent::aNode(node)) {
     1627          return aNodeMap[node];
     1628        } else {
     1629          return bNodeMap[node];
     1630        }
     1631      }
     1632
     1633      void set(const Key& node, const Value& value) {
     1634        if (Parent::aNode(node)) {
     1635          aNodeMap.set(node, value);
     1636        } else {
     1637          bNodeMap.set(node, value);
     1638        }
     1639      }
     1640
     1641    protected:
     1642     
     1643      virtual void add(const Node&) {}
     1644      virtual void add(const std::vector<Node>&) {}
     1645      virtual void erase(const Node&) {}
     1646      virtual void erase(const std::vector<Node>&) {}
     1647      virtual void clear() {}
     1648      virtual void build() {}
     1649
     1650      const Graph* getGraph() const { return graph; }
     1651     
     1652    private:
     1653      const Graph* graph;
     1654      BNodeMap<_Value> bNodeMap;
     1655      ANodeMap<_Value> aNodeMap;
     1656    };
     1657   
     1658  public:
     1659
     1660    template <typename _Value>
     1661    class NodeMap
     1662      : public IterableMapExtender<NodeMapBase<_Value> > {
     1663    public:
     1664      typedef BpUGraphExtender Graph;
     1665      typedef IterableMapExtender< NodeMapBase<_Value> > Parent;
     1666   
     1667      NodeMap(const Graph& _g)
     1668        : Parent(_g) {}
     1669      NodeMap(const Graph& _g, const _Value& _v)
     1670        : Parent(_g, _v) {}
     1671   
     1672      NodeMap& operator=(const NodeMap& cmap) {
     1673        return operator=<NodeMap>(cmap);
     1674      }
     1675   
     1676
     1677      /// \brief Template assign operator.
     1678      ///
     1679      /// The given parameter should be conform to the ReadMap
     1680      /// concept and could be indiced by the current item set of
     1681      /// the NodeMap. In this case the value for each item
     1682      /// is assigned by the value of the given ReadMap.
     1683      template <typename CMap>
     1684      NodeMap& operator=(const CMap& cmap) {
     1685        checkConcept<concept::ReadMap<Node, _Value>, CMap>();
     1686        const typename Parent::Graph* graph = Parent::getGraph();
     1687        Node it;
     1688        for (graph->first(it); it != INVALID; graph->next(it)) {
     1689          Parent::set(it, cmap[it]);
     1690        }
     1691        return *this;
     1692      }
     1693   
     1694    };
     1695
     1696
     1697
     1698    template <typename _Value>
     1699    class EdgeMap
     1700      : public IterableMapExtender<DefaultMap<Graph, Edge, _Value> > {
     1701    public:
     1702      typedef BpUGraphExtender Graph;
     1703      typedef IterableMapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
     1704   
     1705      EdgeMap(const Graph& _g)
     1706        : Parent(_g) {}
     1707      EdgeMap(const Graph& _g, const _Value& _v)
     1708        : Parent(_g, _v) {}
     1709   
     1710      EdgeMap& operator=(const EdgeMap& cmap) {
     1711        return operator=<EdgeMap>(cmap);
     1712      }
     1713   
     1714      template <typename CMap>
     1715      EdgeMap& operator=(const CMap& cmap) {
     1716        checkConcept<concept::ReadMap<Edge, _Value>, CMap>();
     1717        const typename Parent::Graph* graph = Parent::getGraph();
     1718        Edge it;
     1719        for (graph->first(it); it != INVALID; graph->next(it)) {
     1720          Parent::set(it, cmap[it]);
     1721        }
     1722        return *this;
     1723      }
     1724    };
     1725
     1726    template <typename _Value>
     1727    class UEdgeMap
     1728      : public IterableMapExtender<DefaultMap<Graph, UEdge, _Value> > {
     1729    public:
     1730      typedef BpUGraphExtender Graph;
     1731      typedef IterableMapExtender<DefaultMap<Graph, UEdge, _Value> >
     1732      Parent;
     1733   
     1734      UEdgeMap(const Graph& _g)
     1735        : Parent(_g) {}
     1736      UEdgeMap(const Graph& _g, const _Value& _v)
     1737        : Parent(_g, _v) {}
     1738   
     1739      UEdgeMap& operator=(const UEdgeMap& cmap) {
     1740        return operator=<UEdgeMap>(cmap);
     1741      }
     1742   
     1743      template <typename CMap>
     1744      UEdgeMap& operator=(const CMap& cmap) {
     1745        checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();
     1746        const typename Parent::Graph* graph = Parent::getGraph();
     1747        UEdge it;
     1748        for (graph->first(it); it != INVALID; graph->next(it)) {
     1749          Parent::set(it, cmap[it]);
     1750        }
     1751        return *this;
     1752      }
     1753    };
     1754
     1755 
     1756    Node addANode() {
     1757      Node node = Parent::addANode();
     1758      getNotifier(ANode()).add(node);
     1759      getNotifier(Node()).add(node);
     1760      return node;
     1761    }
     1762
     1763    Node addBNode() {
     1764      Node node = Parent::addBNode();
     1765      getNotifier(BNode()).add(node);
     1766      getNotifier(Node()).add(node);
     1767      return node;
     1768    }
     1769 
     1770    UEdge addEdge(const Node& source, const Node& target) {
     1771      UEdge uedge = Parent::addEdge(source, target);
     1772      getNotifier(UEdge()).add(uedge);
     1773   
     1774      std::vector<Edge> edges;
     1775      edges.push_back(direct(uedge, true));
     1776      edges.push_back(direct(uedge, false));
     1777      getNotifier(Edge()).add(edges);
     1778   
     1779      return uedge;
     1780    }
     1781
     1782    void clear() {
     1783      getNotifier(Edge()).clear();
     1784      getNotifier(UEdge()).clear();
     1785      getNotifier(Node()).clear();
     1786      getNotifier(BNode()).clear();
     1787      getNotifier(ANode()).clear();
     1788      Parent::clear();
     1789    }
     1790
     1791    void erase(const Node& node) {
     1792      UEdge uedge;
     1793      bool dir;
     1794      Parent::firstInc(uedge, dir, node);
     1795      while (uedge != INVALID ) {
     1796        erase(uedge);
     1797        Parent::firstInc(uedge, dir, node);
     1798      }
     1799
     1800      getNotifier(Node()).erase(node);
     1801      Parent::erase(node);
     1802    }
     1803   
     1804    void erase(const UEdge& uedge) {
     1805      std::vector<Edge> edges;
     1806      edges.push_back(direct(uedge, true));
     1807      edges.push_back(direct(uedge, false));
     1808      getNotifier(Edge()).erase(edges);
     1809      getNotifier(UEdge()).erase(uedge);
     1810      Parent::erase(uedge);
     1811    }
     1812
     1813
     1814    ~BpUGraphExtender() {
     1815      getNotifier(Edge()).clear();
     1816      getNotifier(UEdge()).clear();
     1817      getNotifier(Node()).clear();
     1818      getNotifier(BNode()).clear();
     1819      getNotifier(ANode()).clear();
     1820    }
     1821
    6161822
    6171823  };
Note: See TracChangeset for help on using the changeset viewer.