lemon-main: lemon/bits/graph_extender.h@660db48f324f

     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  */

    19 #ifndef LEMON_BITS_GRAPH_EXTENDER_H

    20 #define LEMON_BITS_GRAPH_EXTENDER_H

    22 #include <lemon/core.h>

    24 #include <lemon/bits/map_extender.h>

    25 #include <lemon/bits/default_map.h>

    27 #include <lemon/concept_check.h>

    28 #include <lemon/concepts/maps.h>

    30 //\ingroup graphbits

    31 //\file

    32 //\brief Extenders for the graph types

    33 namespace lemon {

    35   // \ingroup graphbits

    36   //

    37   // \brief Extender for the digraph implementations

    38   template <typename Base>

    39   class DigraphExtender : public Base {

    40   public:

    42     typedef Base Parent;

    43     typedef DigraphExtender Digraph;

    45     // Base extensions

    47     typedef typename Parent::Node Node;

    48     typedef typename Parent::Arc Arc;

    50     int maxId(Node) const {

    51       return Parent::maxNodeId();

    52     }

    54     int maxId(Arc) const {

    55       return Parent::maxArcId();

    56     }

    58     Node fromId(int id, Node) const {

    59       return Parent::nodeFromId(id);

    60     }

    62     Arc fromId(int id, Arc) const {

    63       return Parent::arcFromId(id);

    64     }

    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     }

    75     // Alterable extension

    77     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;

    78     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;

    81   protected:

    83     mutable NodeNotifier node_notifier;

    84     mutable ArcNotifier arc_notifier;

    86   public:

    88     NodeNotifier& notifier(Node) const {

    89       return node_notifier;

    90     }

    92     ArcNotifier& notifier(Arc) const {

    93       return arc_notifier;

    94     }

    96     class NodeIt : public Node {

    97       const Digraph* _digraph;

    98     public:

   100       NodeIt() {}

   102       NodeIt(Invalid i) : Node(i) { }

   104       explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {

   105         _digraph->first(static_cast<Node&>(*this));

   106       }

   108       NodeIt(const Digraph& digraph, const Node& node)

   109         : Node(node), _digraph(&digraph) {}

   111       NodeIt& operator++() {

   112         _digraph->next(*this);

   113         return *this;

   114       }

   116     };

   119     class ArcIt : public Arc {

   120       const Digraph* _digraph;

   121     public:

   123       ArcIt() { }

   125       ArcIt(Invalid i) : Arc(i) { }

   127       explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {

   128         _digraph->first(static_cast<Arc&>(*this));

   129       }

   131       ArcIt(const Digraph& digraph, const Arc& arc) :

   132         Arc(arc), _digraph(&digraph) { }

   134       ArcIt& operator++() {

   135         _digraph->next(*this);

   136         return *this;

   137       }

   139     };

   142     class OutArcIt : public Arc {

   143       const Digraph* _digraph;

   144     public:

   146       OutArcIt() { }

   148       OutArcIt(Invalid i) : Arc(i) { }

   150       OutArcIt(const Digraph& digraph, const Node& node)

   151         : _digraph(&digraph) {

   152         _digraph->firstOut(*this, node);

   153       }

   155       OutArcIt(const Digraph& digraph, const Arc& arc)

   156         : Arc(arc), _digraph(&digraph) {}

   158       OutArcIt& operator++() {

   159         _digraph->nextOut(*this);

   160         return *this;

   161       }

   163     };

   166     class InArcIt : public Arc {

   167       const Digraph* _digraph;

   168     public:

   170       InArcIt() { }

   172       InArcIt(Invalid i) : Arc(i) { }

   174       InArcIt(const Digraph& digraph, const Node& node)

   175         : _digraph(&digraph) {

   176         _digraph->firstIn(*this, node);

   177       }

   179       InArcIt(const Digraph& digraph, const Arc& arc) :

   180         Arc(arc), _digraph(&digraph) {}

   182       InArcIt& operator++() {

   183         _digraph->nextIn(*this);

   184         return *this;

   185       }

   187     };

   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     }

   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     }

   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;

   225       explicit NodeMap(const Digraph& digraph)

   226         : Parent(digraph) {}

   227       NodeMap(const Digraph& digraph, const _Value& value)

   228         : Parent(digraph, value) {}

   230     private:

   231       NodeMap& operator=(const NodeMap& cmap) {

   232         return operator=<NodeMap>(cmap);

   233       }

   235       template <typename CMap>

   236       NodeMap& operator=(const CMap& cmap) {

   237         Parent::operator=(cmap);

   238         return *this;

   239       }

   241     };

   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;

   250       explicit ArcMap(const Digraph& digraph)

   251         : Parent(digraph) {}

   252       ArcMap(const Digraph& digraph, const _Value& value)

   253         : Parent(digraph, value) {}

   255     private:

   256       ArcMap& operator=(const ArcMap& cmap) {

   257         return operator=<ArcMap>(cmap);

   258       }

   260       template <typename CMap>

   261       ArcMap& operator=(const CMap& cmap) {

   262         Parent::operator=(cmap);

   263         return *this;

   264       }

   265     };

   268     Node addNode() {

   269       Node node = Parent::addNode();

   270       notifier(Node()).add(node);

   271       return node;

   272     }

   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     }

   280     void clear() {

   281       notifier(Arc()).clear();

   282       notifier(Node()).clear();

   283       Parent::clear();

   284     }

   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     }

   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       }

   301       Parent::firstIn(arc, node);

   302       while (arc != INVALID ) {

   303         erase(arc);

   304         Parent::firstIn(arc, node);

   305       }

   307       notifier(Node()).erase(node);

   308       Parent::erase(node);

   309     }

   311     void erase(const Arc& arc) {

   312       notifier(Arc()).erase(arc);

   313       Parent::erase(arc);

   314     }

   316     DigraphExtender() {

   317       node_notifier.setContainer(*this);

   318       arc_notifier.setContainer(*this);

   319     }

   322     ~DigraphExtender() {

   323       arc_notifier.clear();

   324       node_notifier.clear();

   325     }

   326   };

   328   // \ingroup _graphbits

   329   //

   330   // \brief Extender for the Graphs

   331   template <typename Base>

   332   class GraphExtender : public Base {

   333   public:

   335     typedef Base Parent;

   336     typedef GraphExtender Graph;

   338     typedef True UndirectedTag;

   340     typedef typename Parent::Node Node;

   341     typedef typename Parent::Arc Arc;

   342     typedef typename Parent::Edge Edge;

   344     // Graph extension

   346     int maxId(Node) const {

   347       return Parent::maxNodeId();

   348     }

   350     int maxId(Arc) const {

   351       return Parent::maxArcId();

   352     }

   354     int maxId(Edge) const {

   355       return Parent::maxEdgeId();

   356     }

   358     Node fromId(int id, Node) const {

   359       return Parent::nodeFromId(id);

   360     }

   362     Arc fromId(int id, Arc) const {

   363       return Parent::arcFromId(id);

   364     }

   366     Edge fromId(int id, Edge) const {

   367       return Parent::edgeFromId(id);

   368     }

   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     }

   379     Arc oppositeArc(const Arc &arc) const {

   380       return Parent::direct(arc, !Parent::direction(arc));

   381     }

   383     using Parent::direct;

   384     Arc direct(const Edge &edge, const Node &node) const {

   385       return Parent::direct(edge, Parent::u(edge) == node);

   386     }

   388     // Alterable extension

   390     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;

   391     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;

   392     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;

   395   protected:

   397     mutable NodeNotifier node_notifier;

   398     mutable ArcNotifier arc_notifier;

   399     mutable EdgeNotifier edge_notifier;

   401   public:

   403     NodeNotifier& notifier(Node) const {

   404       return node_notifier;

   405     }

   407     ArcNotifier& notifier(Arc) const {

   408       return arc_notifier;

   409     }

   411     EdgeNotifier& notifier(Edge) const {

   412       return edge_notifier;

   413     }

   417     class NodeIt : public Node {

   418       const Graph* _graph;

   419     public:

   421       NodeIt() {}

   423       NodeIt(Invalid i) : Node(i) { }

   425       explicit NodeIt(const Graph& graph) : _graph(&graph) {

   426         _graph->first(static_cast<Node&>(*this));

   427       }

   429       NodeIt(const Graph& graph, const Node& node)

   430         : Node(node), _graph(&graph) {}

   432       NodeIt& operator++() {

   433         _graph->next(*this);

   434         return *this;

   435       }

   437     };

   440     class ArcIt : public Arc {

   441       const Graph* _graph;

   442     public:

   444       ArcIt() { }

   446       ArcIt(Invalid i) : Arc(i) { }

   448       explicit ArcIt(const Graph& graph) : _graph(&graph) {

   449         _graph->first(static_cast<Arc&>(*this));

   450       }

   452       ArcIt(const Graph& graph, const Arc& arc) :

   453         Arc(arc), _graph(&graph) { }

   455       ArcIt& operator++() {

   456         _graph->next(*this);

   457         return *this;

   458       }

   460     };

   463     class OutArcIt : public Arc {

   464       const Graph* _graph;

   465     public:

   467       OutArcIt() { }

   469       OutArcIt(Invalid i) : Arc(i) { }

   471       OutArcIt(const Graph& graph, const Node& node)

   472         : _graph(&graph) {

   473         _graph->firstOut(*this, node);

   474       }

   476       OutArcIt(const Graph& graph, const Arc& arc)

   477         : Arc(arc), _graph(&graph) {}

   479       OutArcIt& operator++() {

   480         _graph->nextOut(*this);

   481         return *this;

   482       }

   484     };

   487     class InArcIt : public Arc {

   488       const Graph* _graph;

   489     public:

   491       InArcIt() { }

   493       InArcIt(Invalid i) : Arc(i) { }

   495       InArcIt(const Graph& graph, const Node& node)

   496         : _graph(&graph) {

   497         _graph->firstIn(*this, node);

   498       }

   500       InArcIt(const Graph& graph, const Arc& arc) :

   501         Arc(arc), _graph(&graph) {}

   503       InArcIt& operator++() {

   504         _graph->nextIn(*this);

   505         return *this;

   506       }

   508     };

   511     class EdgeIt : public Parent::Edge {

   512       const Graph* _graph;

   513     public:

   515       EdgeIt() { }

   517       EdgeIt(Invalid i) : Edge(i) { }

   519       explicit EdgeIt(const Graph& graph) : _graph(&graph) {

   520         _graph->first(static_cast<Edge&>(*this));

   521       }

   523       EdgeIt(const Graph& graph, const Edge& edge) :

   524         Edge(edge), _graph(&graph) { }

   526       EdgeIt& operator++() {

   527         _graph->next(*this);

   528         return *this;

   529       }

   531     };

   533     class IncEdgeIt : public Parent::Edge {

   534       friend class GraphExtender;

   535       const Graph* _graph;

   536       bool _direction;

   537     public:

   539       IncEdgeIt() { }

   541       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }

   543       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {

   544         _graph->firstInc(*this, _direction, node);

   545       }

   547       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)

   548         : _graph(&graph), Edge(edge) {

   549         _direction = (_graph->source(edge) == node);

   550       }

   552       IncEdgeIt& operator++() {

   553         _graph->nextInc(*this, _direction);

   554         return *this;

   555       }

   556     };

   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     }

   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     }

   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     }

   599     // Mappable extension

   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;

   608       NodeMap(const Graph& graph)

   609         : Parent(graph) {}

   610       NodeMap(const Graph& graph, const _Value& value)

   611         : Parent(graph, value) {}

   613     private:

   614       NodeMap& operator=(const NodeMap& cmap) {

   615         return operator=<NodeMap>(cmap);

   616       }

   618       template <typename CMap>

   619       NodeMap& operator=(const CMap& cmap) {

   620         Parent::operator=(cmap);

   621         return *this;

   622       }

   624     };

   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;

   633       ArcMap(const Graph& graph)

   634         : Parent(graph) {}

   635       ArcMap(const Graph& graph, const _Value& value)

   636         : Parent(graph, value) {}

   638     private:

   639       ArcMap& operator=(const ArcMap& cmap) {

   640         return operator=<ArcMap>(cmap);

   641       }

   643       template <typename CMap>

   644       ArcMap& operator=(const CMap& cmap) {

   645         Parent::operator=(cmap);

   646         return *this;

   647       }

   648     };

   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;

   658       EdgeMap(const Graph& graph)

   659         : Parent(graph) {}

   661       EdgeMap(const Graph& graph, const _Value& value)

   662         : Parent(graph, value) {}

   664     private:

   665       EdgeMap& operator=(const EdgeMap& cmap) {

   666         return operator=<EdgeMap>(cmap);

   667       }

   669       template <typename CMap>

   670       EdgeMap& operator=(const CMap& cmap) {

   671         Parent::operator=(cmap);

   672         return *this;

   673       }

   675     };

   677     // Alteration extension

   679     Node addNode() {

   680       Node node = Parent::addNode();

   681       notifier(Node()).add(node);

   682       return node;

   683     }

   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     }

   695     void clear() {

   696       notifier(Arc()).clear();

   697       notifier(Edge()).clear();

   698       notifier(Node()).clear();

   699       Parent::clear();

   700     }

   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     }

   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       }

   719       Parent::firstIn(arc, node);

   720       while (arc != INVALID ) {

   721         erase(arc);

   722         Parent::firstIn(arc, node);

   723       }

   725       notifier(Node()).erase(node);

   726       Parent::erase(node);

   727     }

   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     }

   738     GraphExtender() {

   739       node_notifier.setContainer(*this);

   740       arc_notifier.setContainer(*this);

   741       edge_notifier.setContainer(*this);

   742     }

   744     ~GraphExtender() {

   745       edge_notifier.clear();

   746       arc_notifier.clear();

   747       node_notifier.clear();

   748     }

   750   };

   752 }

   754 #endif

author	Alpar Juttner <alpar@cs.elte.hu>
	Fri, 21 Nov 2008 14:11:29 +0000
changeset 389	660db48f324f
parent 314	2cc60866a0c9
child 440	88ed40ad0d4f
permissions	-rw-r--r--