lemon/bits/graph_extender.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 16 Sep 2008 16:07:35 +0100
changeset 262 0181b7f12a2a
parent 209 765619b7cbb2
child 263 be8a861d3bb7
permissions -rw-r--r--
Update NEWS file (ticket #121)
     1 /* -*- mode: C++; indent-tabs-mode: nil; -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library.
     4  *
     5  * Copyright (C) 2003-2008
     6  * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     7  * (Egervary Research Group on Combinatorial Optimization, EGRES).
     8  *
     9  * Permission to use, modify and distribute this software is granted
    10  * provided that this copyright notice appears in all copies. For
    11  * precise terms see the accompanying LICENSE file.
    12  *
    13  * This software is provided "AS IS" with no warranty of any kind,
    14  * express or implied, and with no claim as to its suitability for any
    15  * purpose.
    16  *
    17  */
    18 
    19 #ifndef LEMON_BITS_GRAPH_EXTENDER_H
    20 #define LEMON_BITS_GRAPH_EXTENDER_H
    21 
    22 #include <lemon/core.h>
    23 
    24 #include <lemon/bits/map_extender.h>
    25 #include <lemon/bits/default_map.h>
    26 
    27 #include <lemon/concept_check.h>
    28 #include <lemon/concepts/maps.h>
    29 
    30 ///\ingroup graphbits
    31 ///\file
    32 ///\brief Extenders for the digraph types
    33 namespace lemon {
    34 
    35   /// \ingroup graphbits
    36   ///
    37   /// \brief Extender for the Digraphs
    38   template <typename Base>
    39   class DigraphExtender : public Base {
    40   public:
    41 
    42     typedef Base Parent;
    43     typedef DigraphExtender Digraph;
    44 
    45     // Base extensions
    46 
    47     typedef typename Parent::Node Node;
    48     typedef typename Parent::Arc Arc;
    49 
    50     int maxId(Node) const {
    51       return Parent::maxNodeId();
    52     }
    53 
    54     int maxId(Arc) const {
    55       return Parent::maxArcId();
    56     }
    57 
    58     Node fromId(int id, Node) const {
    59       return Parent::nodeFromId(id);
    60     }
    61 
    62     Arc fromId(int id, Arc) const {
    63       return Parent::arcFromId(id);
    64     }
    65 
    66     Node oppositeNode(const Node &node, const Arc &arc) const {
    67       if (node == Parent::source(arc))
    68         return Parent::target(arc);
    69       else if(node == Parent::target(arc))
    70         return Parent::source(arc);
    71       else
    72         return INVALID;
    73     }
    74 
    75     // Alterable extension
    76 
    77     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
    78     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
    79 
    80 
    81   protected:
    82 
    83     mutable NodeNotifier node_notifier;
    84     mutable ArcNotifier arc_notifier;
    85 
    86   public:
    87 
    88     NodeNotifier& notifier(Node) const {
    89       return node_notifier;
    90     }
    91 
    92     ArcNotifier& notifier(Arc) const {
    93       return arc_notifier;
    94     }
    95 
    96     class NodeIt : public Node {
    97       const Digraph* _digraph;
    98     public:
    99 
   100       NodeIt() {}
   101 
   102       NodeIt(Invalid i) : Node(i) { }
   103 
   104       explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
   105         _digraph->first(static_cast<Node&>(*this));
   106       }
   107 
   108       NodeIt(const Digraph& digraph, const Node& node)
   109         : Node(node), _digraph(&digraph) {}
   110 
   111       NodeIt& operator++() {
   112         _digraph->next(*this);
   113         return *this;
   114       }
   115 
   116     };
   117 
   118 
   119     class ArcIt : public Arc {
   120       const Digraph* _digraph;
   121     public:
   122 
   123       ArcIt() { }
   124 
   125       ArcIt(Invalid i) : Arc(i) { }
   126 
   127       explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
   128         _digraph->first(static_cast<Arc&>(*this));
   129       }
   130 
   131       ArcIt(const Digraph& digraph, const Arc& arc) :
   132         Arc(arc), _digraph(&digraph) { }
   133 
   134       ArcIt& operator++() {
   135         _digraph->next(*this);
   136         return *this;
   137       }
   138 
   139     };
   140 
   141 
   142     class OutArcIt : public Arc {
   143       const Digraph* _digraph;
   144     public:
   145 
   146       OutArcIt() { }
   147 
   148       OutArcIt(Invalid i) : Arc(i) { }
   149 
   150       OutArcIt(const Digraph& digraph, const Node& node)
   151         : _digraph(&digraph) {
   152         _digraph->firstOut(*this, node);
   153       }
   154 
   155       OutArcIt(const Digraph& digraph, const Arc& arc)
   156         : Arc(arc), _digraph(&digraph) {}
   157 
   158       OutArcIt& operator++() {
   159         _digraph->nextOut(*this);
   160         return *this;
   161       }
   162 
   163     };
   164 
   165 
   166     class InArcIt : public Arc {
   167       const Digraph* _digraph;
   168     public:
   169 
   170       InArcIt() { }
   171 
   172       InArcIt(Invalid i) : Arc(i) { }
   173 
   174       InArcIt(const Digraph& digraph, const Node& node)
   175         : _digraph(&digraph) {
   176         _digraph->firstIn(*this, node);
   177       }
   178 
   179       InArcIt(const Digraph& digraph, const Arc& arc) :
   180         Arc(arc), _digraph(&digraph) {}
   181 
   182       InArcIt& operator++() {
   183         _digraph->nextIn(*this);
   184         return *this;
   185       }
   186 
   187     };
   188 
   189     /// \brief Base node of the iterator
   190     ///
   191     /// Returns the base node (i.e. the source in this case) of the iterator
   192     Node baseNode(const OutArcIt &arc) const {
   193       return Parent::source(arc);
   194     }
   195     /// \brief Running node of the iterator
   196     ///
   197     /// Returns the running node (i.e. the target in this case) of the
   198     /// iterator
   199     Node runningNode(const OutArcIt &arc) const {
   200       return Parent::target(arc);
   201     }
   202 
   203     /// \brief Base node of the iterator
   204     ///
   205     /// Returns the base node (i.e. the target in this case) of the iterator
   206     Node baseNode(const InArcIt &arc) const {
   207       return Parent::target(arc);
   208     }
   209     /// \brief Running node of the iterator
   210     ///
   211     /// Returns the running node (i.e. the source in this case) of the
   212     /// iterator
   213     Node runningNode(const InArcIt &arc) const {
   214       return Parent::source(arc);
   215     }
   216 
   217 
   218     template <typename _Value>
   219     class NodeMap
   220       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
   221     public:
   222       typedef DigraphExtender Digraph;
   223       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
   224 
   225       explicit NodeMap(const Digraph& digraph)
   226         : Parent(digraph) {}
   227       NodeMap(const Digraph& digraph, const _Value& value)
   228         : Parent(digraph, value) {}
   229 
   230       NodeMap& operator=(const NodeMap& cmap) {
   231         return operator=<NodeMap>(cmap);
   232       }
   233 
   234       template <typename CMap>
   235       NodeMap& operator=(const CMap& cmap) {
   236         Parent::operator=(cmap);
   237         return *this;
   238       }
   239 
   240     };
   241 
   242     template <typename _Value>
   243     class ArcMap
   244       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   245     public:
   246       typedef DigraphExtender Digraph;
   247       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   248 
   249       explicit ArcMap(const Digraph& digraph)
   250         : Parent(digraph) {}
   251       ArcMap(const Digraph& digraph, const _Value& value)
   252         : Parent(digraph, value) {}
   253 
   254       ArcMap& operator=(const ArcMap& cmap) {
   255         return operator=<ArcMap>(cmap);
   256       }
   257 
   258       template <typename CMap>
   259       ArcMap& operator=(const CMap& cmap) {
   260         Parent::operator=(cmap);
   261         return *this;
   262       }
   263     };
   264 
   265 
   266     Node addNode() {
   267       Node node = Parent::addNode();
   268       notifier(Node()).add(node);
   269       return node;
   270     }
   271 
   272     Arc addArc(const Node& from, const Node& to) {
   273       Arc arc = Parent::addArc(from, to);
   274       notifier(Arc()).add(arc);
   275       return arc;
   276     }
   277 
   278     void clear() {
   279       notifier(Arc()).clear();
   280       notifier(Node()).clear();
   281       Parent::clear();
   282     }
   283 
   284     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
   285     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
   286       Parent::build(digraph, nodeRef, arcRef);
   287       notifier(Node()).build();
   288       notifier(Arc()).build();
   289     }
   290 
   291     void erase(const Node& node) {
   292       Arc arc;
   293       Parent::firstOut(arc, node);
   294       while (arc != INVALID ) {
   295         erase(arc);
   296         Parent::firstOut(arc, node);
   297       }
   298 
   299       Parent::firstIn(arc, node);
   300       while (arc != INVALID ) {
   301         erase(arc);
   302         Parent::firstIn(arc, node);
   303       }
   304 
   305       notifier(Node()).erase(node);
   306       Parent::erase(node);
   307     }
   308 
   309     void erase(const Arc& arc) {
   310       notifier(Arc()).erase(arc);
   311       Parent::erase(arc);
   312     }
   313 
   314     DigraphExtender() {
   315       node_notifier.setContainer(*this);
   316       arc_notifier.setContainer(*this);
   317     }
   318 
   319 
   320     ~DigraphExtender() {
   321       arc_notifier.clear();
   322       node_notifier.clear();
   323     }
   324   };
   325 
   326   /// \ingroup _graphbits
   327   ///
   328   /// \brief Extender for the Graphs
   329   template <typename Base>
   330   class GraphExtender : public Base {
   331   public:
   332 
   333     typedef Base Parent;
   334     typedef GraphExtender Graph;
   335 
   336     typedef True UndirectedTag;
   337 
   338     typedef typename Parent::Node Node;
   339     typedef typename Parent::Arc Arc;
   340     typedef typename Parent::Edge Edge;
   341 
   342     // Graph extension
   343 
   344     int maxId(Node) const {
   345       return Parent::maxNodeId();
   346     }
   347 
   348     int maxId(Arc) const {
   349       return Parent::maxArcId();
   350     }
   351 
   352     int maxId(Edge) const {
   353       return Parent::maxEdgeId();
   354     }
   355 
   356     Node fromId(int id, Node) const {
   357       return Parent::nodeFromId(id);
   358     }
   359 
   360     Arc fromId(int id, Arc) const {
   361       return Parent::arcFromId(id);
   362     }
   363 
   364     Edge fromId(int id, Edge) const {
   365       return Parent::edgeFromId(id);
   366     }
   367 
   368     Node oppositeNode(const Node &n, const Edge &e) const {
   369       if( n == Parent::u(e))
   370         return Parent::v(e);
   371       else if( n == Parent::v(e))
   372         return Parent::u(e);
   373       else
   374         return INVALID;
   375     }
   376 
   377     Arc oppositeArc(const Arc &arc) const {
   378       return Parent::direct(arc, !Parent::direction(arc));
   379     }
   380 
   381     using Parent::direct;
   382     Arc direct(const Edge &edge, const Node &node) const {
   383       return Parent::direct(edge, Parent::u(edge) == node);
   384     }
   385 
   386     // Alterable extension
   387 
   388     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
   389     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
   390     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
   391 
   392 
   393   protected:
   394 
   395     mutable NodeNotifier node_notifier;
   396     mutable ArcNotifier arc_notifier;
   397     mutable EdgeNotifier edge_notifier;
   398 
   399   public:
   400 
   401     NodeNotifier& notifier(Node) const {
   402       return node_notifier;
   403     }
   404 
   405     ArcNotifier& notifier(Arc) const {
   406       return arc_notifier;
   407     }
   408 
   409     EdgeNotifier& notifier(Edge) const {
   410       return edge_notifier;
   411     }
   412 
   413 
   414 
   415     class NodeIt : public Node {
   416       const Graph* _graph;
   417     public:
   418 
   419       NodeIt() {}
   420 
   421       NodeIt(Invalid i) : Node(i) { }
   422 
   423       explicit NodeIt(const Graph& graph) : _graph(&graph) {
   424         _graph->first(static_cast<Node&>(*this));
   425       }
   426 
   427       NodeIt(const Graph& graph, const Node& node)
   428         : Node(node), _graph(&graph) {}
   429 
   430       NodeIt& operator++() {
   431         _graph->next(*this);
   432         return *this;
   433       }
   434 
   435     };
   436 
   437 
   438     class ArcIt : public Arc {
   439       const Graph* _graph;
   440     public:
   441 
   442       ArcIt() { }
   443 
   444       ArcIt(Invalid i) : Arc(i) { }
   445 
   446       explicit ArcIt(const Graph& graph) : _graph(&graph) {
   447         _graph->first(static_cast<Arc&>(*this));
   448       }
   449 
   450       ArcIt(const Graph& graph, const Arc& arc) :
   451         Arc(arc), _graph(&graph) { }
   452 
   453       ArcIt& operator++() {
   454         _graph->next(*this);
   455         return *this;
   456       }
   457 
   458     };
   459 
   460 
   461     class OutArcIt : public Arc {
   462       const Graph* _graph;
   463     public:
   464 
   465       OutArcIt() { }
   466 
   467       OutArcIt(Invalid i) : Arc(i) { }
   468 
   469       OutArcIt(const Graph& graph, const Node& node)
   470         : _graph(&graph) {
   471         _graph->firstOut(*this, node);
   472       }
   473 
   474       OutArcIt(const Graph& graph, const Arc& arc)
   475         : Arc(arc), _graph(&graph) {}
   476 
   477       OutArcIt& operator++() {
   478         _graph->nextOut(*this);
   479         return *this;
   480       }
   481 
   482     };
   483 
   484 
   485     class InArcIt : public Arc {
   486       const Graph* _graph;
   487     public:
   488 
   489       InArcIt() { }
   490 
   491       InArcIt(Invalid i) : Arc(i) { }
   492 
   493       InArcIt(const Graph& graph, const Node& node)
   494         : _graph(&graph) {
   495         _graph->firstIn(*this, node);
   496       }
   497 
   498       InArcIt(const Graph& graph, const Arc& arc) :
   499         Arc(arc), _graph(&graph) {}
   500 
   501       InArcIt& operator++() {
   502         _graph->nextIn(*this);
   503         return *this;
   504       }
   505 
   506     };
   507 
   508 
   509     class EdgeIt : public Parent::Edge {
   510       const Graph* _graph;
   511     public:
   512 
   513       EdgeIt() { }
   514 
   515       EdgeIt(Invalid i) : Edge(i) { }
   516 
   517       explicit EdgeIt(const Graph& graph) : _graph(&graph) {
   518         _graph->first(static_cast<Edge&>(*this));
   519       }
   520 
   521       EdgeIt(const Graph& graph, const Edge& edge) :
   522         Edge(edge), _graph(&graph) { }
   523 
   524       EdgeIt& operator++() {
   525         _graph->next(*this);
   526         return *this;
   527       }
   528 
   529     };
   530 
   531     class IncEdgeIt : public Parent::Edge {
   532       friend class GraphExtender;
   533       const Graph* _graph;
   534       bool _direction;
   535     public:
   536 
   537       IncEdgeIt() { }
   538 
   539       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
   540 
   541       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
   542         _graph->firstInc(*this, _direction, node);
   543       }
   544 
   545       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
   546         : _graph(&graph), Edge(edge) {
   547         _direction = (_graph->source(edge) == node);
   548       }
   549 
   550       IncEdgeIt& operator++() {
   551         _graph->nextInc(*this, _direction);
   552         return *this;
   553       }
   554     };
   555 
   556     /// \brief Base node of the iterator
   557     ///
   558     /// Returns the base node (ie. the source in this case) of the iterator
   559     Node baseNode(const OutArcIt &arc) const {
   560       return Parent::source(static_cast<const Arc&>(arc));
   561     }
   562     /// \brief Running node of the iterator
   563     ///
   564     /// Returns the running node (ie. the target in this case) of the
   565     /// iterator
   566     Node runningNode(const OutArcIt &arc) const {
   567       return Parent::target(static_cast<const Arc&>(arc));
   568     }
   569 
   570     /// \brief Base node of the iterator
   571     ///
   572     /// Returns the base node (ie. the target in this case) of the iterator
   573     Node baseNode(const InArcIt &arc) const {
   574       return Parent::target(static_cast<const Arc&>(arc));
   575     }
   576     /// \brief Running node of the iterator
   577     ///
   578     /// Returns the running node (ie. the source in this case) of the
   579     /// iterator
   580     Node runningNode(const InArcIt &arc) const {
   581       return Parent::source(static_cast<const Arc&>(arc));
   582     }
   583 
   584     /// Base node of the iterator
   585     ///
   586     /// Returns the base node of the iterator
   587     Node baseNode(const IncEdgeIt &edge) const {
   588       return edge._direction ? u(edge) : v(edge);
   589     }
   590     /// Running node of the iterator
   591     ///
   592     /// Returns the running node of the iterator
   593     Node runningNode(const IncEdgeIt &edge) const {
   594       return edge._direction ? v(edge) : u(edge);
   595     }
   596 
   597     // Mappable extension
   598 
   599     template <typename _Value>
   600     class NodeMap
   601       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   602     public:
   603       typedef GraphExtender Graph;
   604       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   605 
   606       NodeMap(const Graph& graph)
   607         : Parent(graph) {}
   608       NodeMap(const Graph& graph, const _Value& value)
   609         : Parent(graph, value) {}
   610 
   611       NodeMap& operator=(const NodeMap& cmap) {
   612         return operator=<NodeMap>(cmap);
   613       }
   614 
   615       template <typename CMap>
   616       NodeMap& operator=(const CMap& cmap) {
   617         Parent::operator=(cmap);
   618         return *this;
   619       }
   620 
   621     };
   622 
   623     template <typename _Value>
   624     class ArcMap
   625       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   626     public:
   627       typedef GraphExtender Graph;
   628       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   629 
   630       ArcMap(const Graph& graph)
   631         : Parent(graph) {}
   632       ArcMap(const Graph& graph, const _Value& value)
   633         : Parent(graph, value) {}
   634 
   635       ArcMap& operator=(const ArcMap& cmap) {
   636         return operator=<ArcMap>(cmap);
   637       }
   638 
   639       template <typename CMap>
   640       ArcMap& operator=(const CMap& cmap) {
   641         Parent::operator=(cmap);
   642         return *this;
   643       }
   644     };
   645 
   646 
   647     template <typename _Value>
   648     class EdgeMap
   649       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   650     public:
   651       typedef GraphExtender Graph;
   652       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   653 
   654       EdgeMap(const Graph& graph)
   655         : Parent(graph) {}
   656 
   657       EdgeMap(const Graph& graph, const _Value& value)
   658         : Parent(graph, value) {}
   659 
   660       EdgeMap& operator=(const EdgeMap& cmap) {
   661         return operator=<EdgeMap>(cmap);
   662       }
   663 
   664       template <typename CMap>
   665       EdgeMap& operator=(const CMap& cmap) {
   666         Parent::operator=(cmap);
   667         return *this;
   668       }
   669 
   670     };
   671 
   672     // Alteration extension
   673 
   674     Node addNode() {
   675       Node node = Parent::addNode();
   676       notifier(Node()).add(node);
   677       return node;
   678     }
   679 
   680     Edge addEdge(const Node& from, const Node& to) {
   681       Edge edge = Parent::addEdge(from, to);
   682       notifier(Edge()).add(edge);
   683       std::vector<Arc> ev;
   684       ev.push_back(Parent::direct(edge, true));
   685       ev.push_back(Parent::direct(edge, false));
   686       notifier(Arc()).add(ev);
   687       return edge;
   688     }
   689 
   690     void clear() {
   691       notifier(Arc()).clear();
   692       notifier(Edge()).clear();
   693       notifier(Node()).clear();
   694       Parent::clear();
   695     }
   696 
   697     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
   698     void build(const Graph& graph, NodeRefMap& nodeRef,
   699                EdgeRefMap& edgeRef) {
   700       Parent::build(graph, nodeRef, edgeRef);
   701       notifier(Node()).build();
   702       notifier(Edge()).build();
   703       notifier(Arc()).build();
   704     }
   705 
   706     void erase(const Node& node) {
   707       Arc arc;
   708       Parent::firstOut(arc, node);
   709       while (arc != INVALID ) {
   710         erase(arc);
   711         Parent::firstOut(arc, node);
   712       }
   713 
   714       Parent::firstIn(arc, node);
   715       while (arc != INVALID ) {
   716         erase(arc);
   717         Parent::firstIn(arc, node);
   718       }
   719 
   720       notifier(Node()).erase(node);
   721       Parent::erase(node);
   722     }
   723 
   724     void erase(const Edge& edge) {
   725       std::vector<Arc> av;
   726       av.push_back(Parent::direct(edge, true));
   727       av.push_back(Parent::direct(edge, false));
   728       notifier(Arc()).erase(av);
   729       notifier(Edge()).erase(edge);
   730       Parent::erase(edge);
   731     }
   732 
   733     GraphExtender() {
   734       node_notifier.setContainer(*this);
   735       arc_notifier.setContainer(*this);
   736       edge_notifier.setContainer(*this);
   737     }
   738 
   739     ~GraphExtender() {
   740       edge_notifier.clear();
   741       arc_notifier.clear();
   742       node_notifier.clear();
   743     }
   744 
   745   };
   746 
   747 }
   748 
   749 #endif