lemon/bits/graph_extender.h
author Peter Kovacs <kpeter@inf.elte.hu>
Sun, 15 Jun 2008 22:05:23 +0200
changeset 171 02f4d5d9bfd7
parent 107 31a2e6d28f61
child 209 765619b7cbb2
permissions -rw-r--r--
Improve and redesign test programs + unify their output (ticket #25)
- Move graph related utilities form test_tools.h to graph_test.h.
- Move the contents of graph_utils_test.h to graph_utils_test.cc.
- Rename map_test.h -> graph_maps_test.h.
- Rename digraph_test.h -> graph_test.h.
- Many improvements in the following files:
* digraph_test.cc
* graph_test.cc
* graph_test.h
* graph_maps_test.h
* graph_utils_test.cc
* bfs_test.cc
* dfs_test.cc
* counter_test.cc
- Test programs print messages only if it really seems necessary.
- Remove \file commands form .cc test files.
     1 /* -*- C++ -*-
     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/bits/invalid.h>
    23 #include <lemon/bits/utility.h>
    24 
    25 #include <lemon/bits/map_extender.h>
    26 #include <lemon/bits/default_map.h>
    27 
    28 #include <lemon/concept_check.h>
    29 #include <lemon/concepts/maps.h>
    30 
    31 ///\ingroup graphbits
    32 ///\file
    33 ///\brief Extenders for the digraph types
    34 namespace lemon {
    35 
    36   /// \ingroup graphbits
    37   ///
    38   /// \brief Extender for the Digraphs
    39   template <typename Base>
    40   class DigraphExtender : public Base {
    41   public:
    42 
    43     typedef Base Parent;
    44     typedef DigraphExtender Digraph;
    45 
    46     // Base extensions
    47 
    48     typedef typename Parent::Node Node;
    49     typedef typename Parent::Arc Arc;
    50 
    51     int maxId(Node) const {
    52       return Parent::maxNodeId();
    53     }
    54 
    55     int maxId(Arc) const {
    56       return Parent::maxArcId();
    57     }
    58 
    59     Node fromId(int id, Node) const {
    60       return Parent::nodeFromId(id);
    61     }
    62 
    63     Arc fromId(int id, Arc) const {
    64       return Parent::arcFromId(id);
    65     }
    66 
    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     }
    75 
    76     // Alterable extension
    77 
    78     typedef AlterationNotifier<DigraphExtender, Node> NodeNotifier;
    79     typedef AlterationNotifier<DigraphExtender, Arc> ArcNotifier;
    80 
    81 
    82   protected:
    83 
    84     mutable NodeNotifier node_notifier;
    85     mutable ArcNotifier arc_notifier;
    86 
    87   public:
    88 
    89     NodeNotifier& notifier(Node) const {
    90       return node_notifier;
    91     }
    92     
    93     ArcNotifier& notifier(Arc) const {
    94       return arc_notifier;
    95     }
    96 
    97     class NodeIt : public Node { 
    98       const Digraph* _digraph;
    99     public:
   100 
   101       NodeIt() {}
   102 
   103       NodeIt(Invalid i) : Node(i) { }
   104 
   105       explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
   106 	_digraph->first(static_cast<Node&>(*this));
   107       }
   108 
   109       NodeIt(const Digraph& digraph, const Node& node) 
   110 	: Node(node), _digraph(&digraph) {}
   111 
   112       NodeIt& operator++() { 
   113 	_digraph->next(*this);
   114 	return *this; 
   115       }
   116 
   117     };
   118 
   119 
   120     class ArcIt : public Arc { 
   121       const Digraph* _digraph;
   122     public:
   123 
   124       ArcIt() { }
   125 
   126       ArcIt(Invalid i) : Arc(i) { }
   127 
   128       explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
   129 	_digraph->first(static_cast<Arc&>(*this));
   130       }
   131 
   132       ArcIt(const Digraph& digraph, const Arc& arc) : 
   133 	Arc(arc), _digraph(&digraph) { }
   134 
   135       ArcIt& operator++() { 
   136 	_digraph->next(*this);
   137 	return *this; 
   138       }
   139 
   140     };
   141 
   142 
   143     class OutArcIt : public Arc { 
   144       const Digraph* _digraph;
   145     public:
   146 
   147       OutArcIt() { }
   148 
   149       OutArcIt(Invalid i) : Arc(i) { }
   150 
   151       OutArcIt(const Digraph& digraph, const Node& node) 
   152 	: _digraph(&digraph) {
   153 	_digraph->firstOut(*this, node);
   154       }
   155 
   156       OutArcIt(const Digraph& digraph, const Arc& arc) 
   157 	: Arc(arc), _digraph(&digraph) {}
   158 
   159       OutArcIt& operator++() { 
   160 	_digraph->nextOut(*this);
   161 	return *this; 
   162       }
   163 
   164     };
   165 
   166 
   167     class InArcIt : public Arc { 
   168       const Digraph* _digraph;
   169     public:
   170 
   171       InArcIt() { }
   172 
   173       InArcIt(Invalid i) : Arc(i) { }
   174 
   175       InArcIt(const Digraph& digraph, const Node& node) 
   176 	: _digraph(&digraph) {
   177 	_digraph->firstIn(*this, node);
   178       }
   179 
   180       InArcIt(const Digraph& digraph, const Arc& arc) : 
   181 	Arc(arc), _digraph(&digraph) {}
   182 
   183       InArcIt& operator++() { 
   184 	_digraph->nextIn(*this);
   185 	return *this; 
   186       }
   187 
   188     };
   189 
   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     }
   203 
   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     }
   217 
   218     
   219     template <typename _Value>
   220     class NodeMap 
   221       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
   222     public:
   223       typedef DigraphExtender Digraph;
   224       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
   225 
   226       explicit NodeMap(const Digraph& digraph) 
   227 	: Parent(digraph) {}
   228       NodeMap(const Digraph& digraph, const _Value& value) 
   229 	: Parent(digraph, value) {}
   230 
   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       ArcMap& operator=(const ArcMap& cmap) {
   256 	return operator=<ArcMap>(cmap);
   257       }
   258 
   259       template <typename CMap>
   260       ArcMap& operator=(const CMap& cmap) {
   261         Parent::operator=(cmap);
   262 	return *this;
   263       }
   264     };
   265 
   266 
   267     Node addNode() {
   268       Node node = Parent::addNode();
   269       notifier(Node()).add(node);
   270       return node;
   271     }
   272     
   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     }
   278 
   279     void clear() {
   280       notifier(Arc()).clear();
   281       notifier(Node()).clear();
   282       Parent::clear();
   283     }
   284 
   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     }
   291 
   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       } 
   299 
   300       Parent::firstIn(arc, node);
   301       while (arc != INVALID ) {
   302 	erase(arc);
   303 	Parent::firstIn(arc, node);
   304       }
   305 
   306       notifier(Node()).erase(node);
   307       Parent::erase(node);
   308     }
   309     
   310     void erase(const Arc& arc) {
   311       notifier(Arc()).erase(arc);
   312       Parent::erase(arc);
   313     }
   314 
   315     DigraphExtender() {
   316       node_notifier.setContainer(*this);
   317       arc_notifier.setContainer(*this);
   318     } 
   319     
   320 
   321     ~DigraphExtender() {
   322       arc_notifier.clear();
   323       node_notifier.clear();
   324     }
   325   };
   326 
   327   /// \ingroup _graphbits
   328   ///
   329   /// \brief Extender for the Graphs
   330   template <typename Base> 
   331   class GraphExtender : public Base {
   332   public:
   333     
   334     typedef Base Parent;
   335     typedef GraphExtender Graph;
   336 
   337     typedef True UndirectedTag;
   338 
   339     typedef typename Parent::Node Node;
   340     typedef typename Parent::Arc Arc;
   341     typedef typename Parent::Edge Edge;
   342 
   343     // Graph extension    
   344 
   345     int maxId(Node) const {
   346       return Parent::maxNodeId();
   347     }
   348 
   349     int maxId(Arc) const {
   350       return Parent::maxArcId();
   351     }
   352 
   353     int maxId(Edge) const {
   354       return Parent::maxEdgeId();
   355     }
   356 
   357     Node fromId(int id, Node) const {
   358       return Parent::nodeFromId(id);
   359     }
   360 
   361     Arc fromId(int id, Arc) const {
   362       return Parent::arcFromId(id);
   363     }
   364 
   365     Edge fromId(int id, Edge) const {
   366       return Parent::edgeFromId(id);
   367     }
   368 
   369     Node oppositeNode(const Node &n, const Edge &e) const {
   370       if( n == Parent::u(e))
   371 	return Parent::v(e);
   372       else if( n == Parent::v(e))
   373 	return Parent::u(e);
   374       else
   375 	return INVALID;
   376     }
   377 
   378     Arc oppositeArc(const Arc &arc) const {
   379       return Parent::direct(arc, !Parent::direction(arc));
   380     }
   381 
   382     using Parent::direct;
   383     Arc direct(const Edge &edge, const Node &node) const {
   384       return Parent::direct(edge, Parent::u(edge) == node);
   385     }
   386 
   387     // Alterable extension
   388 
   389     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
   390     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
   391     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
   392 
   393 
   394   protected:
   395 
   396     mutable NodeNotifier node_notifier;
   397     mutable ArcNotifier arc_notifier;
   398     mutable EdgeNotifier edge_notifier;
   399 
   400   public:
   401 
   402     NodeNotifier& notifier(Node) const {
   403       return node_notifier;
   404     }
   405     
   406     ArcNotifier& notifier(Arc) const {
   407       return arc_notifier;
   408     }
   409 
   410     EdgeNotifier& notifier(Edge) const {
   411       return edge_notifier;
   412     }
   413 
   414 
   415 
   416     class NodeIt : public Node { 
   417       const Graph* _graph;
   418     public:
   419 
   420       NodeIt() {}
   421 
   422       NodeIt(Invalid i) : Node(i) { }
   423 
   424       explicit NodeIt(const Graph& graph) : _graph(&graph) {
   425 	_graph->first(static_cast<Node&>(*this));
   426       }
   427 
   428       NodeIt(const Graph& graph, const Node& node) 
   429 	: Node(node), _graph(&graph) {}
   430 
   431       NodeIt& operator++() { 
   432 	_graph->next(*this);
   433 	return *this; 
   434       }
   435 
   436     };
   437 
   438 
   439     class ArcIt : public Arc { 
   440       const Graph* _graph;
   441     public:
   442 
   443       ArcIt() { }
   444 
   445       ArcIt(Invalid i) : Arc(i) { }
   446 
   447       explicit ArcIt(const Graph& graph) : _graph(&graph) {
   448 	_graph->first(static_cast<Arc&>(*this));
   449       }
   450 
   451       ArcIt(const Graph& graph, const Arc& arc) : 
   452 	Arc(arc), _graph(&graph) { }
   453 
   454       ArcIt& operator++() { 
   455 	_graph->next(*this);
   456 	return *this; 
   457       }
   458 
   459     };
   460 
   461 
   462     class OutArcIt : public Arc { 
   463       const Graph* _graph;
   464     public:
   465 
   466       OutArcIt() { }
   467 
   468       OutArcIt(Invalid i) : Arc(i) { }
   469 
   470       OutArcIt(const Graph& graph, const Node& node) 
   471 	: _graph(&graph) {
   472 	_graph->firstOut(*this, node);
   473       }
   474 
   475       OutArcIt(const Graph& graph, const Arc& arc) 
   476 	: Arc(arc), _graph(&graph) {}
   477 
   478       OutArcIt& operator++() { 
   479 	_graph->nextOut(*this);
   480 	return *this; 
   481       }
   482 
   483     };
   484 
   485 
   486     class InArcIt : public Arc { 
   487       const Graph* _graph;
   488     public:
   489 
   490       InArcIt() { }
   491 
   492       InArcIt(Invalid i) : Arc(i) { }
   493 
   494       InArcIt(const Graph& graph, const Node& node) 
   495 	: _graph(&graph) {
   496 	_graph->firstIn(*this, node);
   497       }
   498 
   499       InArcIt(const Graph& graph, const Arc& arc) : 
   500 	Arc(arc), _graph(&graph) {}
   501 
   502       InArcIt& operator++() { 
   503 	_graph->nextIn(*this);
   504 	return *this; 
   505       }
   506 
   507     };
   508 
   509 
   510     class EdgeIt : public Parent::Edge { 
   511       const Graph* _graph;
   512     public:
   513 
   514       EdgeIt() { }
   515 
   516       EdgeIt(Invalid i) : Edge(i) { }
   517 
   518       explicit EdgeIt(const Graph& graph) : _graph(&graph) {
   519 	_graph->first(static_cast<Edge&>(*this));
   520       }
   521 
   522       EdgeIt(const Graph& graph, const Edge& edge) : 
   523 	Edge(edge), _graph(&graph) { }
   524 
   525       EdgeIt& operator++() { 
   526 	_graph->next(*this);
   527 	return *this; 
   528       }
   529 
   530     };
   531 
   532     class IncEdgeIt : public Parent::Edge {
   533       friend class GraphExtender;
   534       const Graph* _graph;
   535       bool _direction;
   536     public:
   537 
   538       IncEdgeIt() { }
   539 
   540       IncEdgeIt(Invalid i) : Edge(i), _direction(false) { }
   541 
   542       IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
   543 	_graph->firstInc(*this, _direction, node);
   544       }
   545 
   546       IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
   547 	: _graph(&graph), Edge(edge) {
   548 	_direction = (_graph->source(edge) == node);
   549       }
   550 
   551       IncEdgeIt& operator++() {
   552 	_graph->nextInc(*this, _direction);
   553 	return *this; 
   554       }
   555     };
   556 
   557     /// \brief Base node of the iterator
   558     ///
   559     /// Returns the base node (ie. the source in this case) of the iterator
   560     Node baseNode(const OutArcIt &arc) const {
   561       return Parent::source(static_cast<const Arc&>(arc));
   562     }
   563     /// \brief Running node of the iterator
   564     ///
   565     /// Returns the running node (ie. the target in this case) of the
   566     /// iterator
   567     Node runningNode(const OutArcIt &arc) const {
   568       return Parent::target(static_cast<const Arc&>(arc));
   569     }
   570 
   571     /// \brief Base node of the iterator
   572     ///
   573     /// Returns the base node (ie. the target in this case) of the iterator
   574     Node baseNode(const InArcIt &arc) const {
   575       return Parent::target(static_cast<const Arc&>(arc));
   576     }
   577     /// \brief Running node of the iterator
   578     ///
   579     /// Returns the running node (ie. the source in this case) of the
   580     /// iterator
   581     Node runningNode(const InArcIt &arc) const {
   582       return Parent::source(static_cast<const Arc&>(arc));
   583     }
   584 
   585     /// Base node of the iterator
   586     ///
   587     /// Returns the base node of the iterator
   588     Node baseNode(const IncEdgeIt &edge) const {
   589       return edge._direction ? u(edge) : v(edge);
   590     }
   591     /// Running node of the iterator
   592     ///
   593     /// Returns the running node of the iterator
   594     Node runningNode(const IncEdgeIt &edge) const {
   595       return edge._direction ? v(edge) : u(edge);
   596     }
   597 
   598     // Mappable extension
   599 
   600     template <typename _Value>
   601     class NodeMap 
   602       : public MapExtender<DefaultMap<Graph, Node, _Value> > {
   603     public:
   604       typedef GraphExtender Graph;
   605       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
   606 
   607       NodeMap(const Graph& graph) 
   608 	: Parent(graph) {}
   609       NodeMap(const Graph& graph, const _Value& value) 
   610 	: Parent(graph, value) {}
   611 
   612       NodeMap& operator=(const NodeMap& cmap) {
   613 	return operator=<NodeMap>(cmap);
   614       }
   615 
   616       template <typename CMap>
   617       NodeMap& operator=(const CMap& cmap) {
   618         Parent::operator=(cmap);
   619 	return *this;
   620       }
   621 
   622     };
   623 
   624     template <typename _Value>
   625     class ArcMap 
   626       : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
   627     public:
   628       typedef GraphExtender Graph;
   629       typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
   630 
   631       ArcMap(const Graph& graph) 
   632 	: Parent(graph) {}
   633       ArcMap(const Graph& graph, const _Value& value) 
   634 	: Parent(graph, value) {}
   635 
   636       ArcMap& operator=(const ArcMap& cmap) {
   637 	return operator=<ArcMap>(cmap);
   638       }
   639 
   640       template <typename CMap>
   641       ArcMap& operator=(const CMap& cmap) {
   642         Parent::operator=(cmap);
   643 	return *this;
   644       }
   645     };
   646 
   647 
   648     template <typename _Value>
   649     class EdgeMap 
   650       : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
   651     public:
   652       typedef GraphExtender Graph;
   653       typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
   654 
   655       EdgeMap(const Graph& graph) 
   656 	: Parent(graph) {}
   657 
   658       EdgeMap(const Graph& graph, const _Value& value) 
   659 	: Parent(graph, value) {}
   660 
   661       EdgeMap& operator=(const EdgeMap& cmap) {
   662 	return operator=<EdgeMap>(cmap);
   663       }
   664 
   665       template <typename CMap>
   666       EdgeMap& operator=(const CMap& cmap) {
   667         Parent::operator=(cmap);
   668 	return *this;
   669       }
   670 
   671     };
   672 
   673     // Alteration extension
   674 
   675     Node addNode() {
   676       Node node = Parent::addNode();
   677       notifier(Node()).add(node);
   678       return node;
   679     }
   680 
   681     Edge addEdge(const Node& from, const Node& to) {
   682       Edge edge = Parent::addEdge(from, to);
   683       notifier(Edge()).add(edge);
   684       std::vector<Arc> ev;
   685       ev.push_back(Parent::direct(edge, true));
   686       ev.push_back(Parent::direct(edge, false));      
   687       notifier(Arc()).add(ev);
   688       return edge;
   689     }
   690     
   691     void clear() {
   692       notifier(Arc()).clear();
   693       notifier(Edge()).clear();
   694       notifier(Node()).clear();
   695       Parent::clear();
   696     }
   697 
   698     template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
   699     void build(const Graph& graph, NodeRefMap& nodeRef, 
   700                EdgeRefMap& edgeRef) {
   701       Parent::build(graph, nodeRef, edgeRef);
   702       notifier(Node()).build();
   703       notifier(Edge()).build();
   704       notifier(Arc()).build();
   705     }
   706 
   707     void erase(const Node& node) {
   708       Arc arc;
   709       Parent::firstOut(arc, node);
   710       while (arc != INVALID ) {
   711 	erase(arc);
   712 	Parent::firstOut(arc, node);
   713       } 
   714 
   715       Parent::firstIn(arc, node);
   716       while (arc != INVALID ) {
   717 	erase(arc);
   718 	Parent::firstIn(arc, node);
   719       }
   720 
   721       notifier(Node()).erase(node);
   722       Parent::erase(node);
   723     }
   724 
   725     void erase(const Edge& edge) {
   726       std::vector<Arc> av;
   727       av.push_back(Parent::direct(edge, true));
   728       av.push_back(Parent::direct(edge, false));      
   729       notifier(Arc()).erase(av);
   730       notifier(Edge()).erase(edge);
   731       Parent::erase(edge);
   732     }
   733 
   734     GraphExtender() {
   735       node_notifier.setContainer(*this); 
   736       arc_notifier.setContainer(*this);
   737       edge_notifier.setContainer(*this);
   738     } 
   739 
   740     ~GraphExtender() {
   741       edge_notifier.clear();
   742       arc_notifier.clear();
   743       node_notifier.clear(); 
   744     } 
   745 
   746   };
   747 
   748 }
   749 
   750 #endif