lemon/bits/graph_extender.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 02 Dec 2008 10:31:20 +0000
changeset 408 69f33ef03334
parent 314 2cc60866a0c9
child 440 88ed40ad0d4f
permissions -rw-r--r--
Merge
     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 graph types
    33 namespace lemon {
    34 
    35   // \ingroup graphbits
    36   //
    37   // \brief Extender for the digraph implementations
    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     private:
   231       NodeMap& operator=(const NodeMap& cmap) {
   232         return operator=<NodeMap>(cmap);
   233       }
   234 
   235       template <typename CMap>
   236       NodeMap& operator=(const CMap& cmap) {
   237         Parent::operator=(cmap);
   238         return *this;
   239       }
   240 
   241     };
   242 
   243     template <typename _Value>
   244     class ArcMap
   245       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   246     public:
   247       typedef DigraphExtender Digraph;
   248       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   249 
   250       explicit ArcMap(const Digraph& digraph)
   251         : Parent(digraph) {}
   252       ArcMap(const Digraph& digraph, const _Value& value)
   253         : Parent(digraph, value) {}
   254 
   255     private:
   256       ArcMap& operator=(const ArcMap& cmap) {
   257         return operator=<ArcMap>(cmap);
   258       }
   259 
   260       template <typename CMap>
   261       ArcMap& operator=(const CMap& cmap) {
   262         Parent::operator=(cmap);
   263         return *this;
   264       }
   265     };
   266 
   267 
   268     Node addNode() {
   269       Node node = Parent::addNode();
   270       notifier(Node()).add(node);
   271       return node;
   272     }
   273 
   274     Arc addArc(const Node& from, const Node& to) {
   275       Arc arc = Parent::addArc(from, to);
   276       notifier(Arc()).add(arc);
   277       return arc;
   278     }
   279 
   280     void clear() {
   281       notifier(Arc()).clear();
   282       notifier(Node()).clear();
   283       Parent::clear();
   284     }
   285 
   286     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>
   287     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {
   288       Parent::build(digraph, nodeRef, arcRef);
   289       notifier(Node()).build();
   290       notifier(Arc()).build();
   291     }
   292 
   293     void erase(const Node& node) {
   294       Arc arc;
   295       Parent::firstOut(arc, node);
   296       while (arc != INVALID ) {
   297         erase(arc);
   298         Parent::firstOut(arc, node);
   299       }
   300 
   301       Parent::firstIn(arc, node);
   302       while (arc != INVALID ) {
   303         erase(arc);
   304         Parent::firstIn(arc, node);
   305       }
   306 
   307       notifier(Node()).erase(node);
   308       Parent::erase(node);
   309     }
   310 
   311     void erase(const Arc& arc) {
   312       notifier(Arc()).erase(arc);
   313       Parent::erase(arc);
   314     }
   315 
   316     DigraphExtender() {
   317       node_notifier.setContainer(*this);
   318       arc_notifier.setContainer(*this);
   319     }
   320 
   321 
   322     ~DigraphExtender() {
   323       arc_notifier.clear();
   324       node_notifier.clear();
   325     }
   326   };
   327 
   328   // \ingroup _graphbits
   329   //
   330   // \brief Extender for the Graphs
   331   template <typename Base>
   332   class GraphExtender : public Base {
   333   public:
   334 
   335     typedef Base Parent;
   336     typedef GraphExtender Graph;
   337 
   338     typedef True UndirectedTag;
   339 
   340     typedef typename Parent::Node Node;
   341     typedef typename Parent::Arc Arc;
   342     typedef typename Parent::Edge Edge;
   343 
   344     // Graph extension
   345 
   346     int maxId(Node) const {
   347       return Parent::maxNodeId();
   348     }
   349 
   350     int maxId(Arc) const {
   351       return Parent::maxArcId();
   352     }
   353 
   354     int maxId(Edge) const {
   355       return Parent::maxEdgeId();
   356     }
   357 
   358     Node fromId(int id, Node) const {
   359       return Parent::nodeFromId(id);
   360     }
   361 
   362     Arc fromId(int id, Arc) const {
   363       return Parent::arcFromId(id);
   364     }
   365 
   366     Edge fromId(int id, Edge) const {
   367       return Parent::edgeFromId(id);
   368     }
   369 
   370     Node oppositeNode(const Node &n, const Edge &e) const {
   371       if( n == Parent::u(e))
   372         return Parent::v(e);
   373       else if( n == Parent::v(e))
   374         return Parent::u(e);
   375       else
   376         return INVALID;
   377     }
   378 
   379     Arc oppositeArc(const Arc &arc) const {
   380       return Parent::direct(arc, !Parent::direction(arc));
   381     }
   382 
   383     using Parent::direct;
   384     Arc direct(const Edge &edge, const Node &node) const {
   385       return Parent::direct(edge, Parent::u(edge) == node);
   386     }
   387 
   388     // Alterable extension
   389 
   390     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
   391     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
   392     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
   393 
   394 
   395   protected:
   396 
   397     mutable NodeNotifier node_notifier;
   398     mutable ArcNotifier arc_notifier;
   399     mutable EdgeNotifier edge_notifier;
   400 
   401   public:
   402 
   403     NodeNotifier& notifier(Node) const {
   404       return node_notifier;
   405     }
   406 
   407     ArcNotifier& notifier(Arc) const {
   408       return arc_notifier;
   409     }
   410 
   411     EdgeNotifier& notifier(Edge) const {
   412       return edge_notifier;
   413     }
   414 
   415 
   416 
   417     class NodeIt : public Node {
   418       const Graph* _graph;
   419     public:
   420 
   421       NodeIt() {}
   422 
   423       NodeIt(Invalid i) : Node(i) { }
   424 
   425       explicit NodeIt(const Graph& graph) : _graph(&graph) {
   426         _graph->first(static_cast<Node&>(*this));
   427       }
   428 
   429       NodeIt(const Graph& graph, const Node& node)
   430         : Node(node), _graph(&graph) {}
   431 
   432       NodeIt& operator++() {
   433         _graph->next(*this);
   434         return *this;
   435       }
   436 
   437     };
   438 
   439 
   440     class ArcIt : public Arc {
   441       const Graph* _graph;
   442     public:
   443 
   444       ArcIt() { }
   445 
   446       ArcIt(Invalid i) : Arc(i) { }
   447 
   448       explicit ArcIt(const Graph& graph) : _graph(&graph) {
   449         _graph->first(static_cast<Arc&>(*this));
   450       }
   451 
   452       ArcIt(const Graph& graph, const Arc& arc) :
   453         Arc(arc), _graph(&graph) { }
   454 
   455       ArcIt& operator++() {
   456         _graph->next(*this);
   457         return *this;
   458       }
   459 
   460     };
   461 
   462 
   463     class OutArcIt : public Arc {
   464       const Graph* _graph;
   465     public:
   466 
   467       OutArcIt() { }
   468 
   469       OutArcIt(Invalid i) : Arc(i) { }
   470 
   471       OutArcIt(const Graph& graph, const Node& node)
   472         : _graph(&graph) {
   473         _graph->firstOut(*this, node);
   474       }
   475 
   476       OutArcIt(const Graph& graph, const Arc& arc)
   477         : Arc(arc), _graph(&graph) {}
   478 
   479       OutArcIt& operator++() {
   480         _graph->nextOut(*this);
   481         return *this;
   482       }
   483 
   484     };
   485 
   486 
   487     class InArcIt : public Arc {
   488       const Graph* _graph;
   489     public:
   490 
   491       InArcIt() { }
   492 
   493       InArcIt(Invalid i) : Arc(i) { }
   494 
   495       InArcIt(const Graph& graph, const Node& node)
   496         : _graph(&graph) {
   497         _graph->firstIn(*this, node);
   498       }
   499 
   500       InArcIt(const Graph& graph, const Arc& arc) :
   501         Arc(arc), _graph(&graph) {}
   502 
   503       InArcIt& operator++() {
   504         _graph->nextIn(*this);
   505         return *this;
   506       }
   507 
   508     };
   509 
   510 
   511     class EdgeIt : public Parent::Edge {
   512       const Graph* _graph;
   513     public:
   514 
   515       EdgeIt() { }
   516 
   517       EdgeIt(Invalid i) : Edge(i) { }
   518 
   519       explicit EdgeIt(const Graph& graph) : _graph(&graph) {
   520         _graph->first(static_cast<Edge&>(*this));
   521       }
   522 
   523       EdgeIt(const Graph& graph, const Edge& edge) :
   524         Edge(edge), _graph(&graph) { }
   525 
   526       EdgeIt& operator++() {
   527         _graph->next(*this);
   528         return *this;
   529       }
   530 
   531     };
   532 
   533     class IncEdgeIt : public Parent::Edge {
   534       friend class GraphExtender;
   535       const Graph* _graph;
   536       bool _direction;
   537     public:
   538 
   539       IncEdgeIt() { }
   540 
   541       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
   542 
   543       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
   544         _graph->firstInc(*this, _direction, node);
   545       }
   546 
   547       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
   548         : _graph(&graph), Edge(edge) {
   549         _direction = (_graph->source(edge) == node);
   550       }
   551 
   552       IncEdgeIt& operator++() {
   553         _graph->nextInc(*this, _direction);
   554         return *this;
   555       }
   556     };
   557 
   558     // \brief Base node of the iterator
   559     //
   560     // Returns the base node (ie. the source in this case) of the iterator
   561     Node baseNode(const OutArcIt &arc) const {
   562       return Parent::source(static_cast<const Arc&>(arc));
   563     }
   564     // \brief Running node of the iterator
   565     //
   566     // Returns the running node (ie. the target in this case) of the
   567     // iterator
   568     Node runningNode(const OutArcIt &arc) const {
   569       return Parent::target(static_cast<const Arc&>(arc));
   570     }
   571 
   572     // \brief Base node of the iterator
   573     //
   574     // Returns the base node (ie. the target in this case) of the iterator
   575     Node baseNode(const InArcIt &arc) const {
   576       return Parent::target(static_cast<const Arc&>(arc));
   577     }
   578     // \brief Running node of the iterator
   579     //
   580     // Returns the running node (ie. the source in this case) of the
   581     // iterator
   582     Node runningNode(const InArcIt &arc) const {
   583       return Parent::source(static_cast<const Arc&>(arc));
   584     }
   585 
   586     // Base node of the iterator
   587     //
   588     // Returns the base node of the iterator
   589     Node baseNode(const IncEdgeIt &edge) const {
   590       return edge._direction ? u(edge) : v(edge);
   591     }
   592     // Running node of the iterator
   593     //
   594     // Returns the running node of the iterator
   595     Node runningNode(const IncEdgeIt &edge) const {
   596       return edge._direction ? v(edge) : u(edge);
   597     }
   598 
   599     // Mappable extension
   600 
   601     template <typename _Value>
   602     class NodeMap
   603       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   604     public:
   605       typedef GraphExtender Graph;
   606       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   607 
   608       NodeMap(const Graph& graph)
   609         : Parent(graph) {}
   610       NodeMap(const Graph& graph, const _Value& value)
   611         : Parent(graph, value) {}
   612 
   613     private:
   614       NodeMap& operator=(const NodeMap& cmap) {
   615         return operator=<NodeMap>(cmap);
   616       }
   617 
   618       template <typename CMap>
   619       NodeMap& operator=(const CMap& cmap) {
   620         Parent::operator=(cmap);
   621         return *this;
   622       }
   623 
   624     };
   625 
   626     template <typename _Value>
   627     class ArcMap
   628       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   629     public:
   630       typedef GraphExtender Graph;
   631       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   632 
   633       ArcMap(const Graph& graph)
   634         : Parent(graph) {}
   635       ArcMap(const Graph& graph, const _Value& value)
   636         : Parent(graph, value) {}
   637 
   638     private:
   639       ArcMap& operator=(const ArcMap& cmap) {
   640         return operator=<ArcMap>(cmap);
   641       }
   642 
   643       template <typename CMap>
   644       ArcMap& operator=(const CMap& cmap) {
   645         Parent::operator=(cmap);
   646         return *this;
   647       }
   648     };
   649 
   650 
   651     template <typename _Value>
   652     class EdgeMap
   653       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   654     public:
   655       typedef GraphExtender Graph;
   656       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   657 
   658       EdgeMap(const Graph& graph)
   659         : Parent(graph) {}
   660 
   661       EdgeMap(const Graph& graph, const _Value& value)
   662         : Parent(graph, value) {}
   663 
   664     private:
   665       EdgeMap& operator=(const EdgeMap& cmap) {
   666         return operator=<EdgeMap>(cmap);
   667       }
   668 
   669       template <typename CMap>
   670       EdgeMap& operator=(const CMap& cmap) {
   671         Parent::operator=(cmap);
   672         return *this;
   673       }
   674 
   675     };
   676 
   677     // Alteration extension
   678 
   679     Node addNode() {
   680       Node node = Parent::addNode();
   681       notifier(Node()).add(node);
   682       return node;
   683     }
   684 
   685     Edge addEdge(const Node& from, const Node& to) {
   686       Edge edge = Parent::addEdge(from, to);
   687       notifier(Edge()).add(edge);
   688       std::vector<Arc> ev;
   689       ev.push_back(Parent::direct(edge, true));
   690       ev.push_back(Parent::direct(edge, false));
   691       notifier(Arc()).add(ev);
   692       return edge;
   693     }
   694 
   695     void clear() {
   696       notifier(Arc()).clear();
   697       notifier(Edge()).clear();
   698       notifier(Node()).clear();
   699       Parent::clear();
   700     }
   701 
   702     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
   703     void build(const Graph& graph, NodeRefMap& nodeRef,
   704                EdgeRefMap& edgeRef) {
   705       Parent::build(graph, nodeRef, edgeRef);
   706       notifier(Node()).build();
   707       notifier(Edge()).build();
   708       notifier(Arc()).build();
   709     }
   710 
   711     void erase(const Node& node) {
   712       Arc arc;
   713       Parent::firstOut(arc, node);
   714       while (arc != INVALID ) {
   715         erase(arc);
   716         Parent::firstOut(arc, node);
   717       }
   718 
   719       Parent::firstIn(arc, node);
   720       while (arc != INVALID ) {
   721         erase(arc);
   722         Parent::firstIn(arc, node);
   723       }
   724 
   725       notifier(Node()).erase(node);
   726       Parent::erase(node);
   727     }
   728 
   729     void erase(const Edge& edge) {
   730       std::vector<Arc> av;
   731       av.push_back(Parent::direct(edge, true));
   732       av.push_back(Parent::direct(edge, false));
   733       notifier(Arc()).erase(av);
   734       notifier(Edge()).erase(edge);
   735       Parent::erase(edge);
   736     }
   737 
   738     GraphExtender() {
   739       node_notifier.setContainer(*this);
   740       arc_notifier.setContainer(*this);
   741       edge_notifier.setContainer(*this);
   742     }
   743 
   744     ~GraphExtender() {
   745       edge_notifier.clear();
   746       arc_notifier.clear();
   747       node_notifier.clear();
   748     }
   749 
   750   };
   751 
   752 }
   753 
   754 #endif