lemon-main: lemon/bits/graph_extender.h@ec0b1b423b8b

     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-2009

     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     typedef Base Parent;

    42   public:

    44     typedef DigraphExtender Digraph;

    46     // Base extensions

    48     typedef typename Parent::Node Node;

    49     typedef typename Parent::Arc Arc;

    51     int maxId(Node) const {

    52       return Parent::maxNodeId();

    53     }

    55     int maxId(Arc) const {

    56       return Parent::maxArcId();

    57     }

    59     Node fromId(int id, Node) const {

    60       return Parent::nodeFromId(id);

    61     }

    63     Arc fromId(int id, Arc) const {

    64       return Parent::arcFromId(id);

    65     }

    67     Node oppositeNode(const Node &node, const Arc &arc) const {

    68       if (node == Parent::source(arc))

    69         return Parent::target(arc);

    70       else if(node == Parent::target(arc))

    71         return Parent::source(arc);

    72       else

    73         return INVALID;

    74     }

    76     // Alterable extension

    78     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;

    79     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;

    82   protected:

    84     mutable NodeNotifier node_notifier;

    85     mutable ArcNotifier arc_notifier;

    87   public:

    89     NodeNotifier& notifier(Node) const {

    90       return node_notifier;

    91     }

    93     ArcNotifier& notifier(Arc) const {

    94       return arc_notifier;

    95     }

    97     class NodeIt : public Node {

    98       const Digraph* _digraph;

    99     public:

   101       NodeIt() {}

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

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

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

   107       }

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

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

   112       NodeIt& operator++() {

   113         _digraph->next(*this);

   114         return *this;

   115       }

   117     };

   120     class ArcIt : public Arc {

   121       const Digraph* _digraph;

   122     public:

   124       ArcIt() { }

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

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

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

   130       }

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

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

   135       ArcIt& operator++() {

   136         _digraph->next(*this);

   137         return *this;

   138       }

   140     };

   143     class OutArcIt : public Arc {

   144       const Digraph* _digraph;

   145     public:

   147       OutArcIt() { }

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

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

   152         : _digraph(&digraph) {

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

   154       }

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

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

   159       OutArcIt& operator++() {

   160         _digraph->nextOut(*this);

   161         return *this;

   162       }

   164     };

   167     class InArcIt : public Arc {

   168       const Digraph* _digraph;

   169     public:

   171       InArcIt() { }

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

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

   176         : _digraph(&digraph) {

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

   178       }

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

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

   183       InArcIt& operator++() {

   184         _digraph->nextIn(*this);

   185         return *this;

   186       }

   188     };

   190     // \brief Base node of the iterator

   191     //

   192     // Returns the base node (i.e. the source in this case) of the iterator

   193     Node baseNode(const OutArcIt &arc) const {

   194       return Parent::source(arc);

   195     }

   196     // \brief Running node of the iterator

   197     //

   198     // Returns the running node (i.e. the target in this case) of the

   199     // iterator

   200     Node runningNode(const OutArcIt &arc) const {

   201       return Parent::target(arc);

   202     }

   204     // \brief Base node of the iterator

   205     //

   206     // Returns the base node (i.e. the target in this case) of the iterator

   207     Node baseNode(const InArcIt &arc) const {

   208       return Parent::target(arc);

   209     }

   210     // \brief Running node of the iterator

   211     //

   212     // Returns the running node (i.e. the source in this case) of the

   213     // iterator

   214     Node runningNode(const InArcIt &arc) const {

   215       return Parent::source(arc);

   216     }

   219     template <typename _Value>

   220     class NodeMap

   221       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {

   222       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;

   224     public:

   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       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;

   248     public:

   249       explicit ArcMap(const Digraph& digraph)

   250         : Parent(digraph) {}

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

   252         : Parent(digraph, value) {}

   254     private:

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

   256         return operator=<ArcMap>(cmap);

   257       }

   259       template <typename CMap>

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

   261         Parent::operator=(cmap);

   262         return *this;

   263       }

   264     };

   267     Node addNode() {

   268       Node node = Parent::addNode();

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

   270       return node;

   271     }

   273     Arc addArc(const Node& from, const Node& to) {

   274       Arc arc = Parent::addArc(from, to);

   275       notifier(Arc()).add(arc);

   276       return arc;

   277     }

   279     void clear() {

   280       notifier(Arc()).clear();

   281       notifier(Node()).clear();

   282       Parent::clear();

   283     }

   285     template <typename Digraph, typename NodeRefMap, typename ArcRefMap>

   286     void build(const Digraph& digraph, NodeRefMap& nodeRef, ArcRefMap& arcRef) {

   287       Parent::build(digraph, nodeRef, arcRef);

   288       notifier(Node()).build();

   289       notifier(Arc()).build();

   290     }

   292     void erase(const Node& node) {

   293       Arc arc;

   294       Parent::firstOut(arc, node);

   295       while (arc != INVALID ) {

   296         erase(arc);

   297         Parent::firstOut(arc, node);

   298       }

   300       Parent::firstIn(arc, node);

   301       while (arc != INVALID ) {

   302         erase(arc);

   303         Parent::firstIn(arc, node);

   304       }

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

   307       Parent::erase(node);

   308     }

   310     void erase(const Arc& arc) {

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

   312       Parent::erase(arc);

   313     }

   315     DigraphExtender() {

   316       node_notifier.setContainer(*this);

   317       arc_notifier.setContainer(*this);

   318     }

   321     ~DigraphExtender() {

   322       arc_notifier.clear();

   323       node_notifier.clear();

   324     }

   325   };

   327   // \ingroup _graphbits

   328   //

   329   // \brief Extender for the Graphs

   330   template <typename Base>

   331   class GraphExtender : public Base {

   332     typedef Base Parent;

   334   public:

   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       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;

   606     public:

   607       NodeMap(const Graph& graph)

   608         : Parent(graph) {}

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

   610         : Parent(graph, value) {}

   612     private:

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

   614         return operator=<NodeMap>(cmap);

   615       }

   617       template <typename CMap>

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

   619         Parent::operator=(cmap);

   620         return *this;

   621       }

   623     };

   625     template <typename _Value>

   626     class ArcMap

   627       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {

   628       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;

   630     public:

   631       ArcMap(const Graph& graph)

   632         : Parent(graph) {}

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

   634         : Parent(graph, value) {}

   636     private:

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

   638         return operator=<ArcMap>(cmap);

   639       }

   641       template <typename CMap>

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

   643         Parent::operator=(cmap);

   644         return *this;

   645       }

   646     };

   649     template <typename _Value>

   650     class EdgeMap

   651       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {

   652       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;

   654     public:

   655       EdgeMap(const Graph& graph)

   656         : Parent(graph) {}

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

   659         : Parent(graph, value) {}

   661     private:

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

   663         return operator=<EdgeMap>(cmap);

   664       }

   666       template <typename CMap>

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

   668         Parent::operator=(cmap);

   669         return *this;

   670       }

   672     };

   674     // Alteration extension

   676     Node addNode() {

   677       Node node = Parent::addNode();

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

   679       return node;

   680     }

   682     Edge addEdge(const Node& from, const Node& to) {

   683       Edge edge = Parent::addEdge(from, to);

   684       notifier(Edge()).add(edge);

   685       std::vector<Arc> ev;

   686       ev.push_back(Parent::direct(edge, true));

   687       ev.push_back(Parent::direct(edge, false));

   688       notifier(Arc()).add(ev);

   689       return edge;

   690     }

   692     void clear() {

   693       notifier(Arc()).clear();

   694       notifier(Edge()).clear();

   695       notifier(Node()).clear();

   696       Parent::clear();

   697     }

   699     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>

   700     void build(const Graph& graph, NodeRefMap& nodeRef,

   701                EdgeRefMap& edgeRef) {

   702       Parent::build(graph, nodeRef, edgeRef);

   703       notifier(Node()).build();

   704       notifier(Edge()).build();

   705       notifier(Arc()).build();

   706     }

   708     void erase(const Node& node) {

   709       Arc arc;

   710       Parent::firstOut(arc, node);

   711       while (arc != INVALID ) {

   712         erase(arc);

   713         Parent::firstOut(arc, node);

   714       }

   716       Parent::firstIn(arc, node);

   717       while (arc != INVALID ) {

   718         erase(arc);

   719         Parent::firstIn(arc, node);

   720       }

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

   723       Parent::erase(node);

   724     }

   726     void erase(const Edge& edge) {

   727       std::vector<Arc> av;

   728       av.push_back(Parent::direct(edge, true));

   729       av.push_back(Parent::direct(edge, false));

   730       notifier(Arc()).erase(av);

   731       notifier(Edge()).erase(edge);

   732       Parent::erase(edge);

   733     }

   735     GraphExtender() {

   736       node_notifier.setContainer(*this);

   737       arc_notifier.setContainer(*this);

   738       edge_notifier.setContainer(*this);

   739     }

   741     ~GraphExtender() {

   742       edge_notifier.clear();

   743       arc_notifier.clear();

   744       node_notifier.clear();

   745     }

   747   };

   749 }

   751 #endif

author	Peter Kovacs <kpeter@inf.elte.hu>
	Fri, 16 Oct 2009 01:06:16 +0200
changeset 853	ec0b1b423b8b
parent 440	88ed40ad0d4f
child 685	a27356ceb5bd
permissions	-rw-r--r--