lemon-0.x: lemon/bits/graph_extender.h@080d51024ac5

     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 (ie. 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 (ie. 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 (ie. 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 (ie. 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       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       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:

   733     typedef Base Parent;

   734     typedef BpUGraphExtender Graph;

   736     typedef typename Parent::Node Node;

   737     typedef typename Parent::BNode BNode;

   738     typedef typename Parent::ANode ANode;

   739     typedef typename Parent::Edge Edge;

   740     typedef typename Parent::UEdge UEdge;

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

   743       return source(edge) == node ?

   744 	target(edge) : source(edge);

   745     }

   747     using Parent::direct;

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

   749       return Edge(edge, node == Parent::source(edge));

   750     }

   752     Edge oppositeEdge(const Edge& edge) const {

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

   754     }

   757     int maxId(Node) const {

   758       return Parent::maxNodeId();

   759     }

   760     int maxId(BNode) const {

   761       return Parent::maxBNodeId();

   762     }

   763     int maxId(ANode) const {

   764       return Parent::maxANodeId();

   765     }

   766     int maxId(Edge) const {

   767       return Parent::maxEdgeId();

   768     }

   769     int maxId(UEdge) const {

   770       return Parent::maxUEdgeId();

   771     }

   774     Node fromId(int id, Node) const {

   775       return Parent::nodeFromId(id);

   776     }

   777     ANode fromId(int id, ANode) const {

   778       return Parent::fromANodeId(id);

   779     }

   780     BNode fromId(int id, BNode) const {

   781       return Parent::fromBNodeId(id);

   782     }

   783     Edge fromId(int id, Edge) const {

   784       return Parent::edgeFromId(id);

   785     }

   786     UEdge fromId(int id, UEdge) const {

   787       return Parent::uEdgeFromId(id);

   788     }

   790     typedef AlterationNotifier<BpUGraphExtender, ANode> ANodeNotifier;

   791     typedef AlterationNotifier<BpUGraphExtender, BNode> BNodeNotifier;

   792     typedef AlterationNotifier<BpUGraphExtender, Node> NodeNotifier;

   793     typedef AlterationNotifier<BpUGraphExtender, Edge> EdgeNotifier;

   794     typedef AlterationNotifier<BpUGraphExtender, UEdge> UEdgeNotifier;

   796   protected:

   798     mutable ANodeNotifier anode_notifier;

   799     mutable BNodeNotifier bnode_notifier;

   800     mutable NodeNotifier node_notifier;

   801     mutable EdgeNotifier edge_notifier;

   802     mutable UEdgeNotifier uedge_notifier;

   804   public:

   806     NodeNotifier& getNotifier(Node) const {

   807       return node_notifier;

   808     }

   810     ANodeNotifier& getNotifier(ANode) const {

   811       return anode_notifier;

   812     }

   814     BNodeNotifier& getNotifier(BNode) const {

   815       return bnode_notifier;

   816     }

   818     EdgeNotifier& getNotifier(Edge) const {

   819       return edge_notifier;

   820     }

   822     UEdgeNotifier& getNotifier(UEdge) const {

   823       return uedge_notifier;

   824     }

   826     class NodeIt : public Node {

   827       const Graph* graph;

   828     public:

   830       NodeIt() { }

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

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

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

   836       }

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

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

   841       NodeIt& operator++() {

   842 	graph->next(*this);

   843 	return *this;

   844       }

   846     };

   848     class ANodeIt : public Node {

   849       friend class BpUGraphExtender;

   850       const Graph* graph;

   851     public:

   853       ANodeIt() { }

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

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

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

   859       }

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

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

   864       ANodeIt& operator++() {

   865 	graph->nextANode(*this);

   866 	return *this;

   867       }

   868     };

   870     class BNodeIt : public Node {

   871       friend class BpUGraphExtender;

   872       const Graph* graph;

   873     public:

   875       BNodeIt() { }

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

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

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

   881       }

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

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

   886       BNodeIt& operator++() {

   887 	graph->nextBNode(*this);

   888 	return *this;

   889       }

   890     };

   892     class EdgeIt : public Edge {

   893       friend class BpUGraphExtender;

   894       const Graph* graph;

   895     public:

   897       EdgeIt() { }

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

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

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

   903       }

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

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

   908       EdgeIt& operator++() {

   909 	graph->next(*this);

   910 	return *this;

   911       }

   913     };

   915     class UEdgeIt : public UEdge {

   916       friend class BpUGraphExtender;

   917       const Graph* graph;

   918     public:

   920       UEdgeIt() { }

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

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

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

   926       }

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

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

   931       UEdgeIt& operator++() {

   932 	graph->next(*this);

   933 	return *this;

   934       }

   935     };

   937     class OutEdgeIt : public Edge {

   938       friend class BpUGraphExtender;

   939       const Graph* graph;

   940     public:

   942       OutEdgeIt() { }

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

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

   947 	: graph(&_graph) {

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

   949       }

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

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

   954       OutEdgeIt& operator++() {

   955 	graph->nextOut(*this);

   956 	return *this;

   957       }

   959     };

   962     class InEdgeIt : public Edge {

   963       friend class BpUGraphExtender;

   964       const Graph* graph;

   965     public:

   967       InEdgeIt() { }

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

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

   972 	: graph(&_graph) {

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

   974       }

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

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

   979       InEdgeIt& operator++() {

   980 	graph->nextIn(*this);

   981 	return *this;

   982       }

   984     };

   986     /// \brief Base node of the iterator

   987     ///

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

   989     Node baseNode(const OutEdgeIt &e) const {

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

   991     }

   992     /// \brief Running node of the iterator

   993     ///

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

   995     /// iterator

   996     Node runningNode(const OutEdgeIt &e) const {

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

   998     }

  1000     /// \brief Base node of the iterator

  1001     ///

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

  1003     Node baseNode(const InEdgeIt &e) const {

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

  1005     }

  1006     /// \brief Running node of the iterator

  1007     ///

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

  1009     /// iterator

  1010     Node runningNode(const InEdgeIt &e) const {

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

  1012     }

  1014     class IncEdgeIt : public Parent::UEdge {

  1015       friend class BpUGraphExtender;

  1016       const Graph* graph;

  1017       bool direction;

  1018     public:

  1020       IncEdgeIt() { }

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

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

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

  1026       }

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

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

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

  1031       }

  1033       IncEdgeIt& operator++() {

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

  1035 	return *this;

  1036       }

  1037     };

  1040     /// Base node of the iterator

  1041     ///

  1042     /// Returns the base node of the iterator

  1043     Node baseNode(const IncEdgeIt &e) const {

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

  1045     }

  1047     /// Running node of the iterator

  1048     ///

  1049     /// Returns the running node of the iterator

  1050     Node runningNode(const IncEdgeIt &e) const {

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

  1052     }

  1054     template <typename _Value>

  1055     class ANodeMap

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

  1057     public:

  1058       typedef BpUGraphExtender Graph;

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

  1061       ANodeMap(const Graph& graph)

  1062 	: Parent(graph) {}

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

  1064 	: Parent(graph, value) {}

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

  1067 	return operator=<ANodeMap>(cmap);

  1068       }

  1070       template <typename CMap>

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

  1072         Parent::operator=(cmap);

  1073 	return *this;

  1074       }

  1076     };

  1078     template <typename _Value>

  1079     class BNodeMap

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

  1081     public:

  1082       typedef BpUGraphExtender Graph;

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

  1085       BNodeMap(const Graph& graph)

  1086 	: Parent(graph) {}

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

  1088 	: Parent(graph, value) {}

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

  1091 	return operator=<BNodeMap>(cmap);

  1092       }

  1094       template <typename CMap>

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

  1096         Parent::operator=(cmap);

  1097 	return *this;

  1098       }

  1100     };

  1102   public:

  1104     template <typename _Value>

  1105     class NodeMap {

  1106     public:

  1107       typedef BpUGraphExtender Graph;

  1109       typedef Node Key;

  1110       typedef _Value Value;

  1112       /// The reference type of the map;

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

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

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

  1117       typedef True ReferenceMapTag;

  1119       NodeMap(const Graph& _graph)

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

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

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

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

  1125 	return operator=<NodeMap>(cmap);

  1126       }

  1128       template <typename CMap>

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

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

  1131 	const typename Parent::Notifier* notifier = Parent::getNotifier();

  1132 	Edge it;

  1133 	for (graph.first(it); it != INVALID; graph.next(it)) {

  1134 	  Parent::set(it, cmap[it]);

  1135 	}

  1136 	return *this;

  1137       }

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

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

  1141 	  return aNodeMap[node];

  1142 	} else {

  1143 	  return bNodeMap[node];

  1144 	}

  1145       }

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

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

  1149 	  return aNodeMap[node];

  1150 	} else {

  1151 	  return bNodeMap[node];

  1152 	}

  1153       }

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

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

  1157 	  aNodeMap.set(node, value);

  1158 	} else {

  1159 	  bNodeMap.set(node, value);

  1160 	}

  1161       }

  1163       class MapIt : public NodeIt {

  1164       public:

  1166         typedef NodeIt Parent;

  1168         explicit MapIt(NodeMap& _map)

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

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

  1172           return map[*this];

  1173         }

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

  1176           return map[*this];

  1177         }

  1179         void set(const Value& value) {

  1180           map.set(*this, value);

  1181         }

  1183       private:

  1184         NodeMap& map;

  1185       };

  1187       class ConstMapIt : public NodeIt {

  1188       public:

  1190         typedef NodeIt Parent;

  1192         explicit ConstMapIt(const NodeMap& _map)

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

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

  1196           return map[*this];

  1197         }

  1199       private:

  1200         const NodeMap& map;

  1201       };

  1203       class ItemIt : public NodeIt {

  1204       public:

  1206         typedef NodeIt Parent;

  1208         explicit ItemIt(const NodeMap& _map)

  1209           : Parent(_map.graph) {}

  1211       };

  1213     private:

  1214       const Graph& graph;

  1215       ANodeMap<_Value> aNodeMap;

  1216       BNodeMap<_Value> bNodeMap;

  1217     };

  1220     template <typename _Value>

  1221     class EdgeMap

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

  1223     public:

  1224       typedef BpUGraphExtender Graph;

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

  1227       EdgeMap(const Graph& graph)

  1228 	: Parent(graph) {}

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

  1230 	: Parent(graph, value) {}

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

  1233 	return operator=<EdgeMap>(cmap);

  1234       }

  1236       template <typename CMap>

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

  1238         Parent::operator=(cmap);

  1239 	return *this;

  1240       }

  1241     };

  1243     template <typename _Value>

  1244     class UEdgeMap

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

  1246     public:

  1247       typedef BpUGraphExtender Graph;

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

  1250       UEdgeMap(const Graph& graph)

  1251 	: Parent(graph) {}

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

  1253 	: Parent(graph, value) {}

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

  1256 	return operator=<UEdgeMap>(cmap);

  1257       }

  1259       template <typename CMap>

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

  1261         Parent::operator=(cmap);

  1262 	return *this;

  1263       }

  1264     };

  1267     Node addANode() {

  1268       Node node = Parent::addANode();

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

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

  1271       return node;

  1272     }

  1274     Node addBNode() {

  1275       Node node = Parent::addBNode();

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

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

  1278       return node;

  1279     }

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

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

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

  1285       std::vector<Edge> edges;

  1286       edges.push_back(direct(uedge, true));

  1287       edges.push_back(direct(uedge, false));

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

  1290       return uedge;

  1291     }

  1293     void clear() {

  1294       getNotifier(Edge()).clear();

  1295       getNotifier(UEdge()).clear();

  1296       getNotifier(Node()).clear();

  1297       getNotifier(BNode()).clear();

  1298       getNotifier(ANode()).clear();

  1299       Parent::clear();

  1300     }

  1302     void erase(const Node& node) {

  1303       UEdge uedge;

  1304       bool dir;

  1305       Parent::firstInc(uedge, dir, node);

  1306       while (uedge != INVALID ) {

  1307 	erase(uedge);

  1308 	Parent::firstInc(uedge, dir, node);

  1309       }

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

  1312       Parent::erase(node);

  1313     }

  1315     void erase(const UEdge& uedge) {

  1316       std::vector<Edge> edges;

  1317       edges.push_back(direct(uedge, true));

  1318       edges.push_back(direct(uedge, false));

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

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

  1321       Parent::erase(uedge);

  1322     }

  1325     BpUGraphExtender() {

  1326       anode_notifier.setContainer(*this);

  1327       bnode_notifier.setContainer(*this);

  1328       node_notifier.setContainer(*this);

  1329       edge_notifier.setContainer(*this);

  1330       uedge_notifier.setContainer(*this);

  1331     }

  1333     ~BpUGraphExtender() {

  1334       uedge_notifier.clear();

  1335       edge_notifier.clear();

  1336       node_notifier.clear();

  1337       anode_notifier.clear();

  1338       bnode_notifier.clear();

  1339     }

  1342   };

  1344 }

  1346 #endif

author	deba
	Mon, 03 Apr 2006 09:45:23 +0000
changeset 2031	080d51024ac5
parent 1999	2ff283124dfc
child 2046	66d160810c0a
permissions	-rw-r--r--