lemon-0.x: lemon/bits/graph_extender.h@269a0dcee70b

     1 /* -*- C++ -*-

     2  *

     3  * This file is a part of LEMON, a generic C++ optimization library

     4  *

     5  * Copyright (C) 2003-2006

     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/bits/invalid.h>

    23 #include <lemon/error.h>

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

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

    28 #include <lemon/concept_check.h>

    29 #include <lemon/concept/maps.h>

    31 ///\ingroup graphbits

    32 ///\file

    33 ///\brief Extenders for the graph types

    34 namespace lemon {

    36   /// \ingroup graphbits

    37   ///

    38   /// \brief Extender for the Graphs

    39   template <typename Base>

    40   class GraphExtender : public Base {

    41   public:

    43     typedef Base Parent;

    44     typedef GraphExtender Graph;

    46     // Base extensions

    48     typedef typename Parent::Node Node;

    49     typedef typename Parent::Edge Edge;

    51     int maxId(Node) const {

    52       return Parent::maxNodeId();

    53     }

    55     int maxId(Edge) const {

    56       return Parent::maxEdgeId();

    57     }

    59     Node fromId(int id, Node) const {

    60       return Parent::nodeFromId(id);

    61     }

    63     Edge fromId(int id, Edge) const {

    64       return Parent::edgeFromId(id);

    65     }

    67     Node oppositeNode(const Node &n, const Edge &e) const {

    68       if (n == Parent::source(e))

    69 	return Parent::target(e);

    70       else if(n==Parent::target(e))

    71 	return Parent::source(e);

    72       else

    73 	return INVALID;

    74     }

    76     // Alterable extension

    78     typedef AlterationNotifier<GraphExtender, Node> NodeNotifier;

    79     typedef AlterationNotifier<GraphExtender, Edge> EdgeNotifier;

    82   protected:

    84     mutable NodeNotifier node_notifier;

    85     mutable EdgeNotifier edge_notifier;

    87   public:

    89     NodeNotifier& getNotifier(Node) const {

    90       return node_notifier;

    91     }

    93     EdgeNotifier& getNotifier(Edge) const {

    94       return edge_notifier;

    95     }

    97     class NodeIt : public Node {

    98       const Graph* graph;

    99     public:

   101       NodeIt() {}

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

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

   106 	_graph.first(static_cast<Node&>(*this));

   107       }

   109       NodeIt(const Graph& _graph, const Node& node)

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

   112       NodeIt& operator++() {

   113 	graph->next(*this);

   114 	return *this;

   115       }

   117     };

   120     class EdgeIt : public Edge {

   121       const Graph* graph;

   122     public:

   124       EdgeIt() { }

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

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

   129 	_graph.first(static_cast<Edge&>(*this));

   130       }

   132       EdgeIt(const Graph& _graph, const Edge& e) :

   133 	Edge(e), graph(&_graph) { }

   135       EdgeIt& operator++() {

   136 	graph->next(*this);

   137 	return *this;

   138       }

   140     };

   143     class OutEdgeIt : public Edge {

   144       const Graph* graph;

   145     public:

   147       OutEdgeIt() { }

   149       OutEdgeIt(Invalid i) : Edge(i) { }

   151       OutEdgeIt(const Graph& _graph, const Node& node)

   152 	: graph(&_graph) {

   153 	_graph.firstOut(*this, node);

   154       }

   156       OutEdgeIt(const Graph& _graph, const Edge& edge)

   157 	: Edge(edge), graph(&_graph) {}

   159       OutEdgeIt& operator++() {

   160 	graph->nextOut(*this);

   161 	return *this;

   162       }

   164     };

   167     class InEdgeIt : public Edge {

   168       const Graph* graph;

   169     public:

   171       InEdgeIt() { }

   173       InEdgeIt(Invalid i) : Edge(i) { }

   175       InEdgeIt(const Graph& _graph, const Node& node)

   176 	: graph(&_graph) {

   177 	_graph.firstIn(*this, node);

   178       }

   180       InEdgeIt(const Graph& _graph, const Edge& edge) :

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

   183       InEdgeIt& operator++() {

   184 	graph->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 OutEdgeIt &e) const {

   194       return Parent::source(e);

   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 OutEdgeIt &e) const {

   201       return Parent::target(e);

   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 InEdgeIt &e) const {

   208       return Parent::target(e);

   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 InEdgeIt &e) const {

   215       return Parent::source(e);

   216     }

   219     template <typename _Value>

   220     class NodeMap

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

   222     public:

   223       typedef GraphExtender Graph;

   224       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;

   226       explicit NodeMap(const Graph& graph)

   227 	: Parent(graph) {}

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

   229 	: Parent(graph, value) {}

   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 EdgeMap

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

   246     public:

   247       typedef GraphExtender Graph;

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

   250       explicit EdgeMap(const Graph& graph)

   251 	: Parent(graph) {}

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

   253 	: Parent(graph, value) {}

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

   256 	return operator=<EdgeMap>(cmap);

   257       }

   259       template <typename CMap>

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

   261         Parent::operator=(cmap);

   262 	return *this;

   263       }

   264     };

   267     Node addNode() {

   268       Node node = Parent::addNode();

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

   270       return node;

   271     }

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

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

   275       getNotifier(Edge()).add(edge);

   276       return edge;

   277     }

   279     void clear() {

   280       getNotifier(Edge()).clear();

   281       getNotifier(Node()).clear();

   282       Parent::clear();

   283     }

   286     void erase(const Node& node) {

   287       Edge edge;

   288       Parent::firstOut(edge, node);

   289       while (edge != INVALID ) {

   290 	erase(edge);

   291 	Parent::firstOut(edge, node);

   292       }

   294       Parent::firstIn(edge, node);

   295       while (edge != INVALID ) {

   296 	erase(edge);

   297 	Parent::firstIn(edge, node);

   298       }

   300       getNotifier(Node()).erase(node);

   301       Parent::erase(node);

   302     }

   304     void erase(const Edge& edge) {

   305       getNotifier(Edge()).erase(edge);

   306       Parent::erase(edge);

   307     }

   309     GraphExtender() {

   310       node_notifier.setContainer(*this);

   311       edge_notifier.setContainer(*this);

   312     }

   315     ~GraphExtender() {

   316       edge_notifier.clear();

   317       node_notifier.clear();

   318     }

   319   };

   321   /// \ingroup graphbits

   322   ///

   323   /// \brief Extender for the UGraphs

   324   template <typename Base>

   325   class UGraphExtender : public Base {

   326   public:

   328     typedef Base Parent;

   329     typedef UGraphExtender Graph;

   331     typedef typename Parent::Node Node;

   332     typedef typename Parent::Edge Edge;

   333     typedef typename Parent::UEdge UEdge;

   335     // UGraph extension

   337     int maxId(Node) const {

   338       return Parent::maxNodeId();

   339     }

   341     int maxId(Edge) const {

   342       return Parent::maxEdgeId();

   343     }

   345     int maxId(UEdge) const {

   346       return Parent::maxUEdgeId();

   347     }

   349     Node fromId(int id, Node) const {

   350       return Parent::nodeFromId(id);

   351     }

   353     Edge fromId(int id, Edge) const {

   354       return Parent::edgeFromId(id);

   355     }

   357     UEdge fromId(int id, UEdge) const {

   358       return Parent::uEdgeFromId(id);

   359     }

   361     Node oppositeNode(const Node &n, const UEdge &e) const {

   362       if( n == Parent::source(e))

   363 	return Parent::target(e);

   364       else if( n == Parent::target(e))

   365 	return Parent::source(e);

   366       else

   367 	return INVALID;

   368     }

   370     Edge oppositeEdge(const Edge &e) const {

   371       return Parent::direct(e, !Parent::direction(e));

   372     }

   374     using Parent::direct;

   375     Edge direct(const UEdge &ue, const Node &s) const {

   376       return Parent::direct(ue, Parent::source(ue) == s);

   377     }

   379     // Alterable extension

   381     typedef AlterationNotifier<UGraphExtender, Node> NodeNotifier;

   382     typedef AlterationNotifier<UGraphExtender, Edge> EdgeNotifier;

   383     typedef AlterationNotifier<UGraphExtender, UEdge> UEdgeNotifier;

   386   protected:

   388     mutable NodeNotifier node_notifier;

   389     mutable EdgeNotifier edge_notifier;

   390     mutable UEdgeNotifier uedge_notifier;

   392   public:

   394     NodeNotifier& getNotifier(Node) const {

   395       return node_notifier;

   396     }

   398     EdgeNotifier& getNotifier(Edge) const {

   399       return edge_notifier;

   400     }

   402     UEdgeNotifier& getNotifier(UEdge) const {

   403       return uedge_notifier;

   404     }

   408     class NodeIt : public Node {

   409       const Graph* graph;

   410     public:

   412       NodeIt() {}

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

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

   417 	_graph.first(static_cast<Node&>(*this));

   418       }

   420       NodeIt(const Graph& _graph, const Node& node)

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

   423       NodeIt& operator++() {

   424 	graph->next(*this);

   425 	return *this;

   426       }

   428     };

   431     class EdgeIt : public Edge {

   432       const Graph* graph;

   433     public:

   435       EdgeIt() { }

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

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

   440 	_graph.first(static_cast<Edge&>(*this));

   441       }

   443       EdgeIt(const Graph& _graph, const Edge& e) :

   444 	Edge(e), graph(&_graph) { }

   446       EdgeIt& operator++() {

   447 	graph->next(*this);

   448 	return *this;

   449       }

   451     };

   454     class OutEdgeIt : public Edge {

   455       const Graph* graph;

   456     public:

   458       OutEdgeIt() { }

   460       OutEdgeIt(Invalid i) : Edge(i) { }

   462       OutEdgeIt(const Graph& _graph, const Node& node)

   463 	: graph(&_graph) {

   464 	_graph.firstOut(*this, node);

   465       }

   467       OutEdgeIt(const Graph& _graph, const Edge& edge)

   468 	: Edge(edge), graph(&_graph) {}

   470       OutEdgeIt& operator++() {

   471 	graph->nextOut(*this);

   472 	return *this;

   473       }

   475     };

   478     class InEdgeIt : public Edge {

   479       const Graph* graph;

   480     public:

   482       InEdgeIt() { }

   484       InEdgeIt(Invalid i) : Edge(i) { }

   486       InEdgeIt(const Graph& _graph, const Node& node)

   487 	: graph(&_graph) {

   488 	_graph.firstIn(*this, node);

   489       }

   491       InEdgeIt(const Graph& _graph, const Edge& edge) :

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

   494       InEdgeIt& operator++() {

   495 	graph->nextIn(*this);

   496 	return *this;

   497       }

   499     };

   502     class UEdgeIt : public Parent::UEdge {

   503       const Graph* graph;

   504     public:

   506       UEdgeIt() { }

   508       UEdgeIt(Invalid i) : UEdge(i) { }

   510       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {

   511 	_graph.first(static_cast<UEdge&>(*this));

   512       }

   514       UEdgeIt(const Graph& _graph, const UEdge& e) :

   515 	UEdge(e), graph(&_graph) { }

   517       UEdgeIt& operator++() {

   518 	graph->next(*this);

   519 	return *this;

   520       }

   522     };

   524     class IncEdgeIt : public Parent::UEdge {

   525       friend class UGraphExtender;

   526       const Graph* graph;

   527       bool direction;

   528     public:

   530       IncEdgeIt() { }

   532       IncEdgeIt(Invalid i) : UEdge(i), direction(false) { }

   534       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {

   535 	_graph.firstInc(*this, direction, n);

   536       }

   538       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)

   539 	: graph(&_graph), UEdge(ue) {

   540 	direction = (_graph.source(ue) == n);

   541       }

   543       IncEdgeIt& operator++() {

   544 	graph->nextInc(*this, direction);

   545 	return *this;

   546       }

   547     };

   549     /// \brief Base node of the iterator

   550     ///

   551     /// Returns the base node (ie. the source in this case) of the iterator

   552     Node baseNode(const OutEdgeIt &e) const {

   553       return Parent::source((Edge)e);

   554     }

   555     /// \brief Running node of the iterator

   556     ///

   557     /// Returns the running node (ie. the target in this case) of the

   558     /// iterator

   559     Node runningNode(const OutEdgeIt &e) const {

   560       return Parent::target((Edge)e);

   561     }

   563     /// \brief Base node of the iterator

   564     ///

   565     /// Returns the base node (ie. the target in this case) of the iterator

   566     Node baseNode(const InEdgeIt &e) const {

   567       return Parent::target((Edge)e);

   568     }

   569     /// \brief Running node of the iterator

   570     ///

   571     /// Returns the running node (ie. the source in this case) of the

   572     /// iterator

   573     Node runningNode(const InEdgeIt &e) const {

   574       return Parent::source((Edge)e);

   575     }

   577     /// Base node of the iterator

   578     ///

   579     /// Returns the base node of the iterator

   580     Node baseNode(const IncEdgeIt &e) const {

   581       return e.direction ? source(e) : target(e);

   582     }

   583     /// Running node of the iterator

   584     ///

   585     /// Returns the running node of the iterator

   586     Node runningNode(const IncEdgeIt &e) const {

   587       return e.direction ? target(e) : source(e);

   588     }

   590     // Mappable extension

   592     template <typename _Value>

   593     class NodeMap

   594       : public MapExtender<DefaultMap<Graph, Node, _Value> > {

   595     public:

   596       typedef UGraphExtender Graph;

   597       typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;

   599       NodeMap(const Graph& graph)

   600 	: Parent(graph) {}

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

   602 	: Parent(graph, value) {}

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

   605 	return operator=<NodeMap>(cmap);

   606       }

   608       template <typename CMap>

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

   610         Parent::operator=(cmap);

   611 	return *this;

   612       }

   614     };

   616     template <typename _Value>

   617     class EdgeMap

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

   619     public:

   620       typedef UGraphExtender Graph;

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

   623       EdgeMap(const Graph& graph)

   624 	: Parent(graph) {}

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

   626 	: Parent(graph, value) {}

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

   629 	return operator=<EdgeMap>(cmap);

   630       }

   632       template <typename CMap>

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

   634         Parent::operator=(cmap);

   635 	return *this;

   636       }

   637     };

   640     template <typename _Value>

   641     class UEdgeMap

   642       : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {

   643     public:

   644       typedef UGraphExtender Graph;

   645       typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;

   647       UEdgeMap(const Graph& graph)

   648 	: Parent(graph) {}

   650       UEdgeMap(const Graph& graph, const _Value& value)

   651 	: Parent(graph, value) {}

   653       UEdgeMap& operator=(const UEdgeMap& cmap) {

   654 	return operator=<UEdgeMap>(cmap);

   655       }

   657       template <typename CMap>

   658       UEdgeMap& operator=(const CMap& cmap) {

   659         Parent::operator=(cmap);

   660 	return *this;

   661       }

   663     };

   665     // Alteration extension

   667     Node addNode() {

   668       Node node = Parent::addNode();

   669       getNotifier(Node()).add(node);

   670       return node;

   671     }

   673     UEdge addEdge(const Node& from, const Node& to) {

   674       UEdge uedge = Parent::addEdge(from, to);

   675       getNotifier(UEdge()).add(uedge);

   676       getNotifier(Edge()).add(Parent::direct(uedge, true));

   677       getNotifier(Edge()).add(Parent::direct(uedge, false));

   678       return uedge;

   679     }

   681     void clear() {

   682       getNotifier(Edge()).clear();

   683       getNotifier(UEdge()).clear();

   684       getNotifier(Node()).clear();

   685       Parent::clear();

   686     }

   688     void erase(const Node& node) {

   689       Edge edge;

   690       Parent::firstOut(edge, node);

   691       while (edge != INVALID ) {

   692 	erase(edge);

   693 	Parent::firstOut(edge, node);

   694       }

   696       Parent::firstIn(edge, node);

   697       while (edge != INVALID ) {

   698 	erase(edge);

   699 	Parent::firstIn(edge, node);

   700       }

   702       getNotifier(Node()).erase(node);

   703       Parent::erase(node);

   704     }

   706     void erase(const UEdge& uedge) {

   707       getNotifier(Edge()).erase(Parent::direct(uedge, true));

   708       getNotifier(Edge()).erase(Parent::direct(uedge, false));

   709       getNotifier(UEdge()).erase(uedge);

   710       Parent::erase(uedge);

   711     }

   713     UGraphExtender() {

   714       node_notifier.setContainer(*this);

   715       edge_notifier.setContainer(*this);

   716       uedge_notifier.setContainer(*this);

   717     }

   719     ~UGraphExtender() {

   720       uedge_notifier.clear();

   721       edge_notifier.clear();

   722       node_notifier.clear();

   723     }

   725   };

   727   /// \ingroup graphbits

   728   ///

   729   /// \brief Extender for the BpUGraphs

   730   template <typename Base>

   731   class BpUGraphExtender : public Base {

   732   public:

   734     typedef Base Parent;

   735     typedef BpUGraphExtender Graph;

   737     typedef typename Parent::Node Node;

   738     typedef typename Parent::ANode ANode;

   739     typedef typename Parent::BNode BNode;

   740     typedef typename Parent::Edge Edge;

   741     typedef typename Parent::UEdge UEdge;

   744     Node oppositeNode(const Node& node, const UEdge& edge) const {

   745       return Parent::aNode(edge) == node ?

   746 	Parent::bNode(edge) : Parent::aNode(edge);

   747     }

   749     using Parent::direct;

   750     Edge direct(const UEdge& edge, const Node& node) const {

   751       return Parent::direct(edge, node == Parent::source(edge));

   752     }

   754     Edge oppositeEdge(const Edge& edge) const {

   755       return direct(edge, !Parent::direction(edge));

   756     }

   758     int maxId(Node) const {

   759       return Parent::maxNodeId();

   760     }

   761     int maxId(BNode) const {

   762       return Parent::maxBNodeId();

   763     }

   764     int maxId(ANode) const {

   765       return Parent::maxANodeId();

   766     }

   767     int maxId(Edge) const {

   768       return Parent::maxEdgeId();

   769     }

   770     int maxId(UEdge) const {

   771       return Parent::maxUEdgeId();

   772     }

   775     Node fromId(int id, Node) const {

   776       return Parent::nodeFromId(id);

   777     }

   778     ANode fromId(int id, ANode) const {

   779       return Parent::nodeFromANodeId(id);

   780     }

   781     BNode fromId(int id, BNode) const {

   782       return Parent::nodeFromBNodeId(id);

   783     }

   784     Edge fromId(int id, Edge) const {

   785       return Parent::edgeFromId(id);

   786     }

   787     UEdge fromId(int id, UEdge) const {

   788       return Parent::uEdgeFromId(id);

   789     }

   791     typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;

   792     typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;

   793     typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;

   794     typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;

   795     typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;

   797   protected:

   799     mutable ANodeNotifier anode_notifier;

   800     mutable BNodeNotifier bnode_notifier;

   801     mutable NodeNotifier node_notifier;

   802     mutable EdgeNotifier edge_notifier;

   803     mutable UEdgeNotifier uedge_notifier;

   805   public:

   807     NodeNotifier& getNotifier(Node) const {

   808       return node_notifier;

   809     }

   811     ANodeNotifier& getNotifier(ANode) const {

   812       return anode_notifier;

   813     }

   815     BNodeNotifier& getNotifier(BNode) const {

   816       return bnode_notifier;

   817     }

   819     EdgeNotifier& getNotifier(Edge) const {

   820       return edge_notifier;

   821     }

   823     UEdgeNotifier& getNotifier(UEdge) const {

   824       return uedge_notifier;

   825     }

   827     class NodeIt : public Node {

   828       const Graph* graph;

   829     public:

   831       NodeIt() { }

   833       NodeIt(Invalid i) : Node(INVALID) { }

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

   836 	graph->first(static_cast<Node&>(*this));

   837       }

   839       NodeIt(const Graph& _graph, const Node& node)

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

   842       NodeIt& operator++() {

   843 	graph->next(*this);

   844 	return *this;

   845       }

   847     };

   849     class ANodeIt : public Node {

   850       friend class BpUGraphExtender;

   851       const Graph* graph;

   852     public:

   854       ANodeIt() { }

   856       ANodeIt(Invalid i) : Node(INVALID) { }

   858       explicit ANodeIt(const Graph& _graph) : graph(&_graph) {

   859 	graph->firstANode(static_cast<Node&>(*this));

   860       }

   862       ANodeIt(const Graph& _graph, const Node& node)

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

   865       ANodeIt& operator++() {

   866 	graph->nextANode(*this);

   867 	return *this;

   868       }

   869     };

   871     class BNodeIt : public Node {

   872       friend class BpUGraphExtender;

   873       const Graph* graph;

   874     public:

   876       BNodeIt() { }

   878       BNodeIt(Invalid i) : Node(INVALID) { }

   880       explicit BNodeIt(const Graph& _graph) : graph(&_graph) {

   881 	graph->firstBNode(static_cast<Node&>(*this));

   882       }

   884       BNodeIt(const Graph& _graph, const Node& node)

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

   887       BNodeIt& operator++() {

   888 	graph->nextBNode(*this);

   889 	return *this;

   890       }

   891     };

   893     class EdgeIt : public Edge {

   894       friend class BpUGraphExtender;

   895       const Graph* graph;

   896     public:

   898       EdgeIt() { }

   900       EdgeIt(Invalid i) : Edge(INVALID) { }

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

   903 	graph->first(static_cast<Edge&>(*this));

   904       }

   906       EdgeIt(const Graph& _graph, const Edge& edge)

   907 	: Edge(edge), graph(&_graph) { }

   909       EdgeIt& operator++() {

   910 	graph->next(*this);

   911 	return *this;

   912       }

   914     };

   916     class UEdgeIt : public UEdge {

   917       friend class BpUGraphExtender;

   918       const Graph* graph;

   919     public:

   921       UEdgeIt() { }

   923       UEdgeIt(Invalid i) : UEdge(INVALID) { }

   925       explicit UEdgeIt(const Graph& _graph) : graph(&_graph) {

   926 	graph->first(static_cast<UEdge&>(*this));

   927       }

   929       UEdgeIt(const Graph& _graph, const UEdge& edge)

   930 	: UEdge(edge), graph(&_graph) { }

   932       UEdgeIt& operator++() {

   933 	graph->next(*this);

   934 	return *this;

   935       }

   936     };

   938     class OutEdgeIt : public Edge {

   939       friend class BpUGraphExtender;

   940       const Graph* graph;

   941     public:

   943       OutEdgeIt() { }

   945       OutEdgeIt(Invalid i) : Edge(i) { }

   947       OutEdgeIt(const Graph& _graph, const Node& node)

   948 	: graph(&_graph) {

   949 	graph->firstOut(*this, node);

   950       }

   952       OutEdgeIt(const Graph& _graph, const Edge& edge)

   953 	: Edge(edge), graph(&_graph) {}

   955       OutEdgeIt& operator++() {

   956 	graph->nextOut(*this);

   957 	return *this;

   958       }

   960     };

   963     class InEdgeIt : public Edge {

   964       friend class BpUGraphExtender;

   965       const Graph* graph;

   966     public:

   968       InEdgeIt() { }

   970       InEdgeIt(Invalid i) : Edge(i) { }

   972       InEdgeIt(const Graph& _graph, const Node& node)

   973 	: graph(&_graph) {

   974 	graph->firstIn(*this, node);

   975       }

   977       InEdgeIt(const Graph& _graph, const Edge& edge) :

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

   980       InEdgeIt& operator++() {

   981 	graph->nextIn(*this);

   982 	return *this;

   983       }

   985     };

   987     /// \brief Base node of the iterator

   988     ///

   989     /// Returns the base node (ie. the source in this case) of the iterator

   990     Node baseNode(const OutEdgeIt &e) const {

   991       return Parent::source((Edge&)e);

   992     }

   993     /// \brief Running node of the iterator

   994     ///

   995     /// Returns the running node (ie. the target in this case) of the

   996     /// iterator

   997     Node runningNode(const OutEdgeIt &e) const {

   998       return Parent::target((Edge&)e);

   999     }

  1001     /// \brief Base node of the iterator

  1002     ///

  1003     /// Returns the base node (ie. the target in this case) of the iterator

  1004     Node baseNode(const InEdgeIt &e) const {

  1005       return Parent::target((Edge&)e);

  1006     }

  1007     /// \brief Running node of the iterator

  1008     ///

  1009     /// Returns the running node (ie. the source in this case) of the

  1010     /// iterator

  1011     Node runningNode(const InEdgeIt &e) const {

  1012       return Parent::source((Edge&)e);

  1013     }

  1015     class IncEdgeIt : public Parent::UEdge {

  1016       friend class BpUGraphExtender;

  1017       const Graph* graph;

  1018       bool direction;

  1019     public:

  1021       IncEdgeIt() { }

  1023       IncEdgeIt(Invalid i) : UEdge(i), direction(true) { }

  1025       IncEdgeIt(const Graph& _graph, const Node &n) : graph(&_graph) {

  1026 	graph->firstInc(*this, direction, n);

  1027       }

  1029       IncEdgeIt(const Graph& _graph, const UEdge &ue, const Node &n)

  1030 	: graph(&_graph), UEdge(ue) {

  1031 	direction = (graph->source(ue) == n);

  1032       }

  1034       IncEdgeIt& operator++() {

  1035 	graph->nextInc(*this, direction);

  1036 	return *this;

  1037       }

  1038     };

  1041     /// Base node of the iterator

  1042     ///

  1043     /// Returns the base node of the iterator

  1044     Node baseNode(const IncEdgeIt &e) const {

  1045       return e.direction ? source(e) : target(e);

  1046     }

  1048     /// Running node of the iterator

  1049     ///

  1050     /// Returns the running node of the iterator

  1051     Node runningNode(const IncEdgeIt &e) const {

  1052       return e.direction ? target(e) : source(e);

  1053     }

  1055     template <typename _Value>

  1056     class ANodeMap

  1057       : public MapExtender<DefaultMap<Graph, ANode, _Value> > {

  1058     public:

  1059       typedef BpUGraphExtender Graph;

  1060       typedef MapExtender<DefaultMap<Graph, ANode, _Value> > Parent;

  1062       ANodeMap(const Graph& graph)

  1063 	: Parent(graph) {}

  1064       ANodeMap(const Graph& graph, const _Value& value)

  1065 	: Parent(graph, value) {}

  1067       ANodeMap& operator=(const ANodeMap& cmap) {

  1068 	return operator=<ANodeMap>(cmap);

  1069       }

  1071       template <typename CMap>

  1072       ANodeMap& operator=(const CMap& cmap) {

  1073         Parent::operator=(cmap);

  1074 	return *this;

  1075       }

  1077     };

  1079     template <typename _Value>

  1080     class BNodeMap

  1081       : public MapExtender<DefaultMap<Graph, BNode, _Value> > {

  1082     public:

  1083       typedef BpUGraphExtender Graph;

  1084       typedef MapExtender<DefaultMap<Graph, BNode, _Value> > Parent;

  1086       BNodeMap(const Graph& graph)

  1087 	: Parent(graph) {}

  1088       BNodeMap(const Graph& graph, const _Value& value)

  1089 	: Parent(graph, value) {}

  1091       BNodeMap& operator=(const BNodeMap& cmap) {

  1092 	return operator=<BNodeMap>(cmap);

  1093       }

  1095       template <typename CMap>

  1096       BNodeMap& operator=(const CMap& cmap) {

  1097         Parent::operator=(cmap);

  1098 	return *this;

  1099       }

  1101     };

  1103   public:

  1105     template <typename _Value>

  1106     class NodeMap {

  1107     public:

  1108       typedef BpUGraphExtender Graph;

  1110       typedef Node Key;

  1111       typedef _Value Value;

  1113       /// The reference type of the map;

  1114       typedef typename ANodeMap<_Value>::Reference Reference;

  1115       /// The const reference type of the map;

  1116       typedef typename ANodeMap<_Value>::ConstReference ConstReference;

  1118       typedef True ReferenceMapTag;

  1120       NodeMap(const Graph& _graph)

  1121 	: graph(_graph), aNodeMap(_graph), bNodeMap(_graph) {}

  1122       NodeMap(const Graph& _graph, const _Value& _value)

  1123 	: graph(_graph), aNodeMap(_graph, _value), bNodeMap(_graph, _value) {}

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

  1126 	return operator=<NodeMap>(cmap);

  1127       }

  1129       template <typename CMap>

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

  1131 	checkConcept<concept::ReadMap<Node, _Value>, CMap>();

  1132         aNodeMap = cmap;

  1133         bNodeMap = cmap;

  1134         return *this;

  1135       }

  1137       ConstReference operator[](const Key& node) const {

  1138 	if (Parent::aNode(node)) {

  1139 	  return aNodeMap[node];

  1140 	} else {

  1141 	  return bNodeMap[node];

  1142 	}

  1143       }

  1145       Reference operator[](const Key& node) {

  1146 	if (Parent::aNode(node)) {

  1147 	  return aNodeMap[node];

  1148 	} else {

  1149 	  return bNodeMap[node];

  1150 	}

  1151       }

  1153       void set(const Key& node, const Value& value) {

  1154 	if (Parent::aNode(node)) {

  1155 	  aNodeMap.set(node, value);

  1156 	} else {

  1157 	  bNodeMap.set(node, value);

  1158 	}

  1159       }

  1161       class MapIt : public NodeIt {

  1162       public:

  1164         typedef NodeIt Parent;

  1166         explicit MapIt(NodeMap& _map)

  1167           : Parent(_map.graph), map(_map) {}

  1169         typename MapTraits<NodeMap>::ConstReturnValue operator*() const {

  1170           return map[*this];

  1171         }

  1173         typename MapTraits<NodeMap>::ReturnValue operator*() {

  1174           return map[*this];

  1175         }

  1177         void set(const Value& value) {

  1178           map.set(*this, value);

  1179         }

  1181       private:

  1182         NodeMap& map;

  1183       };

  1185       class ConstMapIt : public NodeIt {

  1186       public:

  1188         typedef NodeIt Parent;

  1190         explicit ConstMapIt(const NodeMap& _map)

  1191           : Parent(_map.graph), map(_map) {}

  1193         typename MapTraits<NodeMap>::ConstReturnValue operator*() const {

  1194           return map[*this];

  1195         }

  1197       private:

  1198         const NodeMap& map;

  1199       };

  1201       class ItemIt : public NodeIt {

  1202       public:

  1204         typedef NodeIt Parent;

  1206         explicit ItemIt(const NodeMap& _map)

  1207           : Parent(_map.graph) {}

  1209       };

  1211     private:

  1212       const Graph& graph;

  1213       ANodeMap<_Value> aNodeMap;

  1214       BNodeMap<_Value> bNodeMap;

  1215     };

  1218     template <typename _Value>

  1219     class EdgeMap

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

  1221     public:

  1222       typedef BpUGraphExtender Graph;

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

  1225       EdgeMap(const Graph& graph)

  1226 	: Parent(graph) {}

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

  1228 	: Parent(graph, value) {}

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

  1231 	return operator=<EdgeMap>(cmap);

  1232       }

  1234       template <typename CMap>

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

  1236         Parent::operator=(cmap);

  1237 	return *this;

  1238       }

  1239     };

  1241     template <typename _Value>

  1242     class UEdgeMap

  1243       : public MapExtender<DefaultMap<Graph, UEdge, _Value> > {

  1244     public:

  1245       typedef BpUGraphExtender Graph;

  1246       typedef MapExtender<DefaultMap<Graph, UEdge, _Value> > Parent;

  1248       UEdgeMap(const Graph& graph)

  1249 	: Parent(graph) {}

  1250       UEdgeMap(const Graph& graph, const _Value& value)

  1251 	: Parent(graph, value) {}

  1253       UEdgeMap& operator=(const UEdgeMap& cmap) {

  1254 	return operator=<UEdgeMap>(cmap);

  1255       }

  1257       template <typename CMap>

  1258       UEdgeMap& operator=(const CMap& cmap) {

  1259         Parent::operator=(cmap);

  1260 	return *this;

  1261       }

  1262     };

  1265     Node addANode() {

  1266       Node node = Parent::addANode();

  1267       getNotifier(ANode()).add(node);

  1268       getNotifier(Node()).add(node);

  1269       return node;

  1270     }

  1272     Node addBNode() {

  1273       Node node = Parent::addBNode();

  1274       getNotifier(BNode()).add(node);

  1275       getNotifier(Node()).add(node);

  1276       return node;

  1277     }

  1279     UEdge addEdge(const Node& source, const Node& target) {

  1280       UEdge uedge = Parent::addEdge(source, target);

  1281       getNotifier(UEdge()).add(uedge);

  1283       std::vector<Edge> edges;

  1284       edges.push_back(Parent::direct(uedge, true));

  1285       edges.push_back(Parent::direct(uedge, false));

  1286       getNotifier(Edge()).add(edges);

  1288       return uedge;

  1289     }

  1291     void clear() {

  1292       getNotifier(Edge()).clear();

  1293       getNotifier(UEdge()).clear();

  1294       getNotifier(Node()).clear();

  1295       getNotifier(BNode()).clear();

  1296       getNotifier(ANode()).clear();

  1297       Parent::clear();

  1298     }

  1300     void erase(const Node& node) {

  1301       UEdge uedge;

  1302       if (Parent::aNode(node)) {

  1303         Parent::firstFromANode(uedge, node);

  1304         while (uedge != INVALID) {

  1305           erase(uedge);

  1306           Parent::firstFromANode(uedge, node);

  1307         }

  1308         getNotifier(ANode()).erase(node);

  1309       } else {

  1310         Parent::firstFromBNode(uedge, node);

  1311         while (uedge != INVALID) {

  1312           erase(uedge);

  1313           Parent::firstFromBNode(uedge, node);

  1314         }

  1315         getNotifier(BNode()).erase(node);

  1316       }

  1318       getNotifier(Node()).erase(node);

  1319       Parent::erase(node);

  1320     }

  1322     void erase(const UEdge& uedge) {

  1323       std::vector<Edge> edges;

  1324       edges.push_back(Parent::direct(uedge, true));

  1325       edges.push_back(Parent::direct(uedge, false));

  1326       getNotifier(Edge()).erase(edges);

  1327       getNotifier(UEdge()).erase(uedge);

  1328       Parent::erase(uedge);

  1329     }

  1332     BpUGraphExtender() {

  1333       anode_notifier.setContainer(*this);

  1334       bnode_notifier.setContainer(*this);

  1335       node_notifier.setContainer(*this);

  1336       edge_notifier.setContainer(*this);

  1337       uedge_notifier.setContainer(*this);

  1338     }

  1340     ~BpUGraphExtender() {

  1341       uedge_notifier.clear();

  1342       edge_notifier.clear();

  1343       node_notifier.clear();

  1344       anode_notifier.clear();

  1345       bnode_notifier.clear();

  1346     }

  1348     Edge findEdge(Node u, Node v, Edge prev = INVALID) const {

  1349       UEdge uedge = Parent::findUEdge(u, v, prev);

  1350       if (uedge != INVALID) {

  1351         return Parent::direct(uedge, Parent::aNode(u));

  1352       } else {

  1353         return INVALID;

  1354       }

  1355     }

  1357   };

  1359 }

  1361 #endif

author	deba
	Tue, 17 Oct 2006 10:50:57 +0000
changeset 2247	269a0dcee70b
parent 2222	a24939ee343c
child 2260	4274224f8a7d
permissions	-rw-r--r--