lemon/bits/graph_extender.h
author Alpar Juttner <alpar@cs.elte.hu>
Tue, 22 Jan 2008 10:59:14 +0000
changeset 59 4ab73d92f0fb
child 77 2de55e4f57a7
permissions -rw-r--r--
Merge
     1 /* -*- C++ -*-
     2  *
     3  * This file is a part of LEMON, a generic C++ optimization library
     4  *
     5  * Copyright (C) 2003-2007
     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 
    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 &n, const Arc &e) const {
    67       if (n == Parent::source(e))
    68 	return Parent::target(e);
    69       else if(n==Parent::target(e))
    70 	return Parent::source(e);
    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& e) : 
   132 	Arc(e), 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 &e) const {
   193       return Parent::source(e);
   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 &e) const {
   200       return Parent::target(e);
   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 &e) const {
   207       return Parent::target(e);
   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 &e) const {
   214       return Parent::source(e);
   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 Digraph;
   335 
   336     typedef typename Parent::Node Node;
   337     typedef typename Parent::Arc Arc;
   338     typedef typename Parent::Edge Edge;
   339 
   340     // Graph extension    
   341 
   342     int maxId(Node) const {
   343       return Parent::maxNodeId();
   344     }
   345 
   346     int maxId(Arc) const {
   347       return Parent::maxArcId();
   348     }
   349 
   350     int maxId(Edge) const {
   351       return Parent::maxEdgeId();
   352     }
   353 
   354     Node fromId(int id, Node) const {
   355       return Parent::nodeFromId(id);
   356     }
   357 
   358     Arc fromId(int id, Arc) const {
   359       return Parent::arcFromId(id);
   360     }
   361 
   362     Edge fromId(int id, Edge) const {
   363       return Parent::edgeFromId(id);
   364     }
   365 
   366     Node oppositeNode(const Node &n, const Edge &e) const {
   367       if( n == Parent::source(e))
   368 	return Parent::target(e);
   369       else if( n == Parent::target(e))
   370 	return Parent::source(e);
   371       else
   372 	return INVALID;
   373     }
   374 
   375     Arc oppositeArc(const Arc &e) const {
   376       return Parent::direct(e, !Parent::direction(e));
   377     }
   378 
   379     using Parent::direct;
   380     Arc direct(const Edge &ue, const Node &s) const {
   381       return Parent::direct(ue, Parent::source(ue) == s);
   382     }
   383 
   384     // Alterable extension
   385 
   386     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;
   387     typedef AlterationNotifier<GraphExtender, Arc> ArcNotifier;
   388     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;
   389 
   390 
   391   protected:
   392 
   393     mutable NodeNotifier node_notifier;
   394     mutable ArcNotifier arc_notifier;
   395     mutable EdgeNotifier edge_notifier;
   396 
   397   public:
   398 
   399     NodeNotifier& notifier(Node) const {
   400       return node_notifier;
   401     }
   402     
   403     ArcNotifier& notifier(Arc) const {
   404       return arc_notifier;
   405     }
   406 
   407     EdgeNotifier& notifier(Edge) const {
   408       return edge_notifier;
   409     }
   410 
   411 
   412 
   413     class NodeIt : public Node { 
   414       const Digraph* digraph;
   415     public:
   416 
   417       NodeIt() {}
   418 
   419       NodeIt(Invalid i) : Node(i) { }
   420 
   421       explicit NodeIt(const Digraph& _digraph) : digraph(&_digraph) {
   422 	_digraph.first(static_cast<Node&>(*this));
   423       }
   424 
   425       NodeIt(const Digraph& _digraph, const Node& node) 
   426 	: Node(node), digraph(&_digraph) {}
   427 
   428       NodeIt& operator++() { 
   429 	digraph->next(*this);
   430 	return *this; 
   431       }
   432 
   433     };
   434 
   435 
   436     class ArcIt : public Arc { 
   437       const Digraph* digraph;
   438     public:
   439 
   440       ArcIt() { }
   441 
   442       ArcIt(Invalid i) : Arc(i) { }
   443 
   444       explicit ArcIt(const Digraph& _digraph) : digraph(&_digraph) {
   445 	_digraph.first(static_cast<Arc&>(*this));
   446       }
   447 
   448       ArcIt(const Digraph& _digraph, const Arc& e) : 
   449 	Arc(e), digraph(&_digraph) { }
   450 
   451       ArcIt& operator++() { 
   452 	digraph->next(*this);
   453 	return *this; 
   454       }
   455 
   456     };
   457 
   458 
   459     class OutArcIt : public Arc { 
   460       const Digraph* digraph;
   461     public:
   462 
   463       OutArcIt() { }
   464 
   465       OutArcIt(Invalid i) : Arc(i) { }
   466 
   467       OutArcIt(const Digraph& _digraph, const Node& node) 
   468 	: digraph(&_digraph) {
   469 	_digraph.firstOut(*this, node);
   470       }
   471 
   472       OutArcIt(const Digraph& _digraph, const Arc& arc) 
   473 	: Arc(arc), digraph(&_digraph) {}
   474 
   475       OutArcIt& operator++() { 
   476 	digraph->nextOut(*this);
   477 	return *this; 
   478       }
   479 
   480     };
   481 
   482 
   483     class InArcIt : public Arc { 
   484       const Digraph* digraph;
   485     public:
   486 
   487       InArcIt() { }
   488 
   489       InArcIt(Invalid i) : Arc(i) { }
   490 
   491       InArcIt(const Digraph& _digraph, const Node& node) 
   492 	: digraph(&_digraph) {
   493 	_digraph.firstIn(*this, node);
   494       }
   495 
   496       InArcIt(const Digraph& _digraph, const Arc& arc) : 
   497 	Arc(arc), digraph(&_digraph) {}
   498 
   499       InArcIt& operator++() { 
   500 	digraph->nextIn(*this);
   501 	return *this; 
   502       }
   503 
   504     };
   505 
   506 
   507     class EdgeIt : public Parent::Edge { 
   508       const Digraph* digraph;
   509     public:
   510 
   511       EdgeIt() { }
   512 
   513       EdgeIt(Invalid i) : Edge(i) { }
   514 
   515       explicit EdgeIt(const Digraph& _digraph) : digraph(&_digraph) {
   516 	_digraph.first(static_cast<Edge&>(*this));
   517       }
   518 
   519       EdgeIt(const Digraph& _digraph, const Edge& e) : 
   520 	Edge(e), digraph(&_digraph) { }
   521 
   522       EdgeIt& operator++() { 
   523 	digraph->next(*this);
   524 	return *this; 
   525       }
   526 
   527     };
   528 
   529     class IncArcIt : public Parent::Edge {
   530       friend class GraphExtender;
   531       const Digraph* digraph;
   532       bool direction;
   533     public:
   534 
   535       IncArcIt() { }
   536 
   537       IncArcIt(Invalid i) : Edge(i), direction(false) { }
   538 
   539       IncArcIt(const Digraph& _digraph, const Node &n) : digraph(&_digraph) {
   540 	_digraph.firstInc(*this, direction, n);
   541       }
   542 
   543       IncArcIt(const Digraph& _digraph, const Edge &ue, const Node &n)
   544 	: digraph(&_digraph), Edge(ue) {
   545 	direction = (_digraph.source(ue) == n);
   546       }
   547 
   548       IncArcIt& operator++() {
   549 	digraph->nextInc(*this, direction);
   550 	return *this; 
   551       }
   552     };
   553 
   554     /// \brief Base node of the iterator
   555     ///
   556     /// Returns the base node (ie. the source in this case) of the iterator
   557     Node baseNode(const OutArcIt &e) const {
   558       return Parent::source(static_cast<const Arc&>(e));
   559     }
   560     /// \brief Running node of the iterator
   561     ///
   562     /// Returns the running node (ie. the target in this case) of the
   563     /// iterator
   564     Node runningNode(const OutArcIt &e) const {
   565       return Parent::target(static_cast<const Arc&>(e));
   566     }
   567 
   568     /// \brief Base node of the iterator
   569     ///
   570     /// Returns the base node (ie. the target in this case) of the iterator
   571     Node baseNode(const InArcIt &e) const {
   572       return Parent::target(static_cast<const Arc&>(e));
   573     }
   574     /// \brief Running node of the iterator
   575     ///
   576     /// Returns the running node (ie. the source in this case) of the
   577     /// iterator
   578     Node runningNode(const InArcIt &e) const {
   579       return Parent::source(static_cast<const Arc&>(e));
   580     }
   581 
   582     /// Base node of the iterator
   583     ///
   584     /// Returns the base node of the iterator
   585     Node baseNode(const IncArcIt &e) const {
   586       return e.direction ? source(e) : target(e);
   587     }
   588     /// Running node of the iterator
   589     ///
   590     /// Returns the running node of the iterator
   591     Node runningNode(const IncArcIt &e) const {
   592       return e.direction ? target(e) : source(e);
   593     }
   594 
   595     // Mappable extension
   596 
   597     template <typename _Value>
   598     class NodeMap 
   599       : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
   600     public:
   601       typedef GraphExtender Digraph;
   602       typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
   603 
   604       NodeMap(const Digraph& digraph) 
   605 	: Parent(digraph) {}
   606       NodeMap(const Digraph& digraph, const _Value& value) 
   607 	: Parent(digraph, value) {}
   608 
   609       NodeMap& operator=(const NodeMap& cmap) {
   610 	return operator=<NodeMap>(cmap);
   611       }
   612 
   613       template <typename CMap>
   614       NodeMap& operator=(const CMap& cmap) {
   615         Parent::operator=(cmap);
   616 	return *this;
   617       }
   618 
   619     };
   620 
   621     template <typename _Value>
   622     class ArcMap 
   623       : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
   624     public:
   625       typedef GraphExtender Digraph;
   626       typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
   627 
   628       ArcMap(const Digraph& digraph) 
   629 	: Parent(digraph) {}
   630       ArcMap(const Digraph& digraph, const _Value& value) 
   631 	: Parent(digraph, value) {}
   632 
   633       ArcMap& operator=(const ArcMap& cmap) {
   634 	return operator=<ArcMap>(cmap);
   635       }
   636 
   637       template <typename CMap>
   638       ArcMap& operator=(const CMap& cmap) {
   639         Parent::operator=(cmap);
   640 	return *this;
   641       }
   642     };
   643 
   644 
   645     template <typename _Value>
   646     class EdgeMap 
   647       : public MapExtender<DefaultMap<Digraph, Edge, _Value> > {
   648     public:
   649       typedef GraphExtender Digraph;
   650       typedef MapExtender<DefaultMap<Digraph, Edge, _Value> > Parent;
   651 
   652       EdgeMap(const Digraph& digraph) 
   653 	: Parent(digraph) {}
   654 
   655       EdgeMap(const Digraph& digraph, const _Value& value) 
   656 	: Parent(digraph, value) {}
   657 
   658       EdgeMap& operator=(const EdgeMap& cmap) {
   659 	return operator=<EdgeMap>(cmap);
   660       }
   661 
   662       template <typename CMap>
   663       EdgeMap& operator=(const CMap& cmap) {
   664         Parent::operator=(cmap);
   665 	return *this;
   666       }
   667 
   668     };
   669 
   670     // Alteration extension
   671 
   672     Node addNode() {
   673       Node node = Parent::addNode();
   674       notifier(Node()).add(node);
   675       return node;
   676     }
   677 
   678     Edge addEdge(const Node& from, const Node& to) {
   679       Edge edge = Parent::addEdge(from, to);
   680       notifier(Edge()).add(edge);
   681       std::vector<Arc> ev;
   682       ev.push_back(Parent::direct(edge, true));
   683       ev.push_back(Parent::direct(edge, false));      
   684       notifier(Arc()).add(ev);
   685       return edge;
   686     }
   687     
   688     void clear() {
   689       notifier(Arc()).clear();
   690       notifier(Edge()).clear();
   691       notifier(Node()).clear();
   692       Parent::clear();
   693     }
   694 
   695     template <typename Digraph, typename NodeRefMap, typename EdgeRefMap>
   696     void build(const Digraph& digraph, NodeRefMap& nodeRef, 
   697                EdgeRefMap& edgeRef) {
   698       Parent::build(digraph, nodeRef, edgeRef);
   699       notifier(Node()).build();
   700       notifier(Edge()).build();
   701       notifier(Arc()).build();
   702     }
   703 
   704     void erase(const Node& node) {
   705       Arc arc;
   706       Parent::firstOut(arc, node);
   707       while (arc != INVALID ) {
   708 	erase(arc);
   709 	Parent::firstOut(arc, node);
   710       } 
   711 
   712       Parent::firstIn(arc, node);
   713       while (arc != INVALID ) {
   714 	erase(arc);
   715 	Parent::firstIn(arc, node);
   716       }
   717 
   718       notifier(Node()).erase(node);
   719       Parent::erase(node);
   720     }
   721 
   722     void erase(const Edge& edge) {
   723       std::vector<Arc> ev;
   724       ev.push_back(Parent::direct(edge, true));
   725       ev.push_back(Parent::direct(edge, false));      
   726       notifier(Arc()).erase(ev);
   727       notifier(Edge()).erase(edge);
   728       Parent::erase(edge);
   729     }
   730 
   731     GraphExtender() {
   732       node_notifier.setContainer(*this); 
   733       arc_notifier.setContainer(*this);
   734       edge_notifier.setContainer(*this);
   735     } 
   736 
   737     ~GraphExtender() {
   738       edge_notifier.clear();
   739       arc_notifier.clear();
   740       node_notifier.clear(); 
   741     } 
   742 
   743   };
   744 
   745 }
   746 
   747 #endif