lemon-0.x: lemon/ugraph_adaptor.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_UGRAPH_ADAPTOR_H

    20 #define LEMON_UGRAPH_ADAPTOR_H

    22 ///\ingroup graph_adaptors

    23 ///\file

    24 ///\brief Several graph adaptors.

    25 ///

    26 ///This file contains several useful ugraph adaptor functions.

    27 ///

    28 ///\author Balazs Dezso

    30 #include <lemon/bits/invalid.h>

    31 #include <lemon/maps.h>

    33 #include <lemon/bits/graph_adaptor_extender.h>

    35 #include <lemon/bits/traits.h>

    37 #include <iostream>

    39 namespace lemon {

    41   /// \ingroup graph_adaptors

    42   ///

    43   /// \brief Base type for the Graph Adaptors

    44   ///

    45   /// This is the base type for most of LEMON graph adaptors.

    46   /// This class implements a trivial graph adaptor i.e. it only wraps the

    47   /// functions and types of the graph. The purpose of this class is to

    48   /// make easier implementing graph adaptors. E.g. if an adaptor is

    49   /// considered which differs from the wrapped graph only in some of its

    50   /// functions or types, then it can be derived from GraphAdaptor, and only

    51   /// the differences should be implemented.

    52   ///

    53   /// \author Balazs Dezso

    54   template<typename _UGraph>

    55   class UGraphAdaptorBase {

    56   public:

    57     typedef _UGraph Graph;

    58     typedef Graph ParentGraph;

    60   protected:

    61     Graph* graph;

    63     UGraphAdaptorBase() : graph(0) {}

    65     void setGraph(Graph& _graph) { graph=&_graph; }

    67     Graph& getGraph() { return *graph; }

    68     const Graph& getGraph() const { return *graph; }

    70   public:

    71     UGraphAdaptorBase(Graph& _graph) : graph(&_graph) {}

    73     typedef typename Graph::Node Node;

    74     typedef typename Graph::Edge Edge;

    75     typedef typename Graph::UEdge UEdge;

    77     void first(Node& i) const { graph->first(i); }

    78     void first(Edge& i) const { graph->first(i); }

    79     void first(UEdge& i) const { graph->first(i); }

    80     void firstIn(Edge& i, const Node& n) const { graph->firstIn(i, n); }

    81     void firstOut(Edge& i, const Node& n ) const { graph->firstOut(i, n); }

    82     void firstInc(UEdge &i, bool &d, const Node &n) const {

    83       graph->firstInc(i, d, n);

    84     }

    86     void next(Node& i) const { graph->next(i); }

    87     void next(Edge& i) const { graph->next(i); }

    88     void next(UEdge& i) const { graph->next(i); }

    89     void nextIn(Edge& i) const { graph->nextIn(i); }

    90     void nextOut(Edge& i) const { graph->nextOut(i); }

    91     void nextInc(UEdge &i, bool &d) const { graph->nextInc(i, d); }

    93     Node source(const UEdge& e) const { return graph->source(e); }

    94     Node target(const UEdge& e) const { return graph->target(e); }

    96     Node source(const Edge& e) const { return graph->source(e); }

    97     Node target(const Edge& e) const { return graph->target(e); }

    99     typedef NodeNumTagIndicator<Graph> NodeNumTag;

   100     int nodeNum() const { return graph->nodeNum(); }

   102     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

   103     int edgeNum() const { return graph->edgeNum(); }

   104     int uEdgeNum() const { return graph->uEdgeNum(); }

   106     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

   107     Edge findEdge(const Node& source, const Node& target,

   108 		  const Edge& prev = INVALID) {

   109       return graph->findEdge(source, target, prev);

   110     }

   111     UEdge findUEdge(const Node& source, const Node& target,

   112                     const UEdge& prev = INVALID) {

   113       return graph->findUEdge(source, target, prev);

   114     }

   116     Node addNode() const { return graph->addNode(); }

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

   118       return graph->addEdge(source, target);

   119     }

   121     void erase(const Node& i) const { graph->erase(i); }

   122     void erase(const UEdge& i) const { graph->erase(i); }

   124     void clear() const { graph->clear(); }

   126     bool direction(const Edge& e) const { return graph->direction(e); }

   127     Edge direct(const UEdge& e, bool d) const { return graph->direct(e, d); }

   129     int id(const Node& v) const { return graph->id(v); }

   130     int id(const Edge& e) const { return graph->id(e); }

   131     int id(const UEdge& e) const { return graph->id(e); }

   133     Node fromNodeId(int id) const {

   134       return graph->fromNodeId(id);

   135     }

   137     Edge fromEdgeId(int id) const {

   138       return graph->fromEdgeId(id);

   139     }

   141     UEdge fromUEdgeId(int id) const {

   142       return graph->fromUEdgeId(id);

   143     }

   145     int maxNodeId() const {

   146       return graph->maxNodeId();

   147     }

   149     int maxEdgeId() const {

   150       return graph->maxEdgeId();

   151     }

   153     int maxUEdgeId() const {

   154       return graph->maxEdgeId();

   155     }

   157     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

   159     NodeNotifier& getNotifier(Node) const {

   160       return graph->getNotifier(Node());

   161     }

   163     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;

   165     EdgeNotifier& getNotifier(Edge) const {

   166       return graph->getNotifier(Edge());

   167     }

   169     typedef typename ItemSetTraits<Graph, UEdge>::ItemNotifier UEdgeNotifier;

   171     UEdgeNotifier& getNotifier(UEdge) const {

   172       return graph->getNotifier(UEdge());

   173     }

   175     template <typename _Value>

   176     class NodeMap : public Graph::template NodeMap<_Value> {

   177     public:

   178       typedef typename Graph::template NodeMap<_Value> Parent;

   179       explicit NodeMap(const UGraphAdaptorBase<Graph>& ga)

   180 	: Parent(*ga.graph) {}

   181       NodeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)

   182 	: Parent(*ga.graph, value) {}

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

   185 	return operator=<NodeMap>(cmap);

   186       }

   188       template <typename CMap>

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

   190         Parent::operator=(cmap);

   191         return *this;

   192       }

   194     };

   196     template <typename _Value>

   197     class EdgeMap : public Graph::template EdgeMap<_Value> {

   198     public:

   199       typedef typename Graph::template EdgeMap<_Value> Parent;

   200       explicit EdgeMap(const UGraphAdaptorBase<Graph>& ga)

   201 	: Parent(*ga.graph) {}

   202       EdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)

   203 	: Parent(*ga.graph, value) {}

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

   206 	return operator=<EdgeMap>(cmap);

   207       }

   209       template <typename CMap>

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

   211         Parent::operator=(cmap);

   212 	return *this;

   213       }

   214     };

   216     template <typename _Value>

   217     class UEdgeMap : public Graph::template UEdgeMap<_Value> {

   218     public:

   219       typedef typename Graph::template UEdgeMap<_Value> Parent;

   220       explicit UEdgeMap(const UGraphAdaptorBase<Graph>& ga)

   221 	: Parent(*ga.graph) {}

   222       UEdgeMap(const UGraphAdaptorBase<Graph>& ga, const _Value& value)

   223 	: Parent(*ga.graph, value) {}

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

   226 	return operator=<UEdgeMap>(cmap);

   227       }

   229       template <typename CMap>

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

   231         Parent::operator=(cmap);

   232         return *this;

   233       }

   234     };

   236   };

   238   /// \ingroup graph_adaptors

   239   template <typename _UGraph>

   240   class UGraphAdaptor

   241     : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {

   242   public:

   243     typedef _UGraph Graph;

   244     typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;

   245   protected:

   246     UGraphAdaptor() : Parent() {}

   248   public:

   249     explicit UGraphAdaptor(Graph& _graph) { setGraph(_graph); }

   250   };

   252   template <typename _UGraph, typename NodeFilterMap,

   253 	    typename UEdgeFilterMap, bool checked = true>

   254   class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {

   255   public:

   256     typedef _UGraph Graph;

   257     typedef SubUGraphAdaptorBase Adaptor;

   258     typedef UGraphAdaptorBase<_UGraph> Parent;

   259   protected:

   261     NodeFilterMap* node_filter_map;

   262     UEdgeFilterMap* uedge_filter_map;

   264     SubUGraphAdaptorBase()

   265       : Parent(), node_filter_map(0), uedge_filter_map(0) { }

   267     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   268       node_filter_map=&_node_filter_map;

   269     }

   270     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {

   271       uedge_filter_map=&_uedge_filter_map;

   272     }

   274   public:

   276     typedef typename Parent::Node Node;

   277     typedef typename Parent::Edge Edge;

   278     typedef typename Parent::UEdge UEdge;

   280     void first(Node& i) const {

   281       Parent::first(i);

   282       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);

   283     }

   285     void first(Edge& i) const {

   286       Parent::first(i);

   287       while (i!=INVALID && (!(*uedge_filter_map)[i]

   288 	     || !(*node_filter_map)[Parent::source(i)]

   289 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);

   290     }

   292     void first(UEdge& i) const {

   293       Parent::first(i);

   294       while (i!=INVALID && (!(*uedge_filter_map)[i]

   295 	     || !(*node_filter_map)[Parent::source(i)]

   296 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);

   297     }

   299     void firstIn(Edge& i, const Node& n) const {

   300       Parent::firstIn(i, n);

   301       while (i!=INVALID && (!(*uedge_filter_map)[i]

   302 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);

   303     }

   305     void firstOut(Edge& i, const Node& n) const {

   306       Parent::firstOut(i, n);

   307       while (i!=INVALID && (!(*uedge_filter_map)[i]

   308 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);

   309     }

   311     void firstInc(UEdge& i, bool& d, const Node& n) const {

   312       Parent::firstInc(i, d, n);

   313       while (i!=INVALID && (!(*uedge_filter_map)[i]

   314             || !(*node_filter_map)[Parent::target(i)])) Parent::nextInc(i, d);

   315     }

   317     void next(Node& i) const {

   318       Parent::next(i);

   319       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);

   320     }

   322     void next(Edge& i) const {

   323       Parent::next(i);

   324       while (i!=INVALID && (!(*uedge_filter_map)[i]

   325 	     || !(*node_filter_map)[Parent::source(i)]

   326 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);

   327     }

   329     void next(UEdge& i) const {

   330       Parent::next(i);

   331       while (i!=INVALID && (!(*uedge_filter_map)[i]

   332 	     || !(*node_filter_map)[Parent::source(i)]

   333 	     || !(*node_filter_map)[Parent::target(i)])) Parent::next(i);

   334     }

   336     void nextIn(Edge& i) const {

   337       Parent::nextIn(i);

   338       while (i!=INVALID && (!(*uedge_filter_map)[i]

   339 	     || !(*node_filter_map)[Parent::source(i)])) Parent::nextIn(i);

   340     }

   342     void nextOut(Edge& i) const {

   343       Parent::nextOut(i);

   344       while (i!=INVALID && (!(*uedge_filter_map)[i]

   345 	     || !(*node_filter_map)[Parent::target(i)])) Parent::nextOut(i);

   346     }

   348     void nextInc(UEdge& i, bool& d) const {

   349       Parent::nextInc(i, d);

   350       while (i!=INVALID && (!(*uedge_filter_map)[i]

   351             || !(*node_filter_map)[Parent::source(i)])) Parent::nextInc(i, d);

   352     }

   354     ///\e

   356     /// This function hides \c n in the graph, i.e. the iteration

   357     /// jumps over it. This is done by simply setting the value of \c n

   358     /// to be false in the corresponding node-map.

   359     void hide(const Node& n) const { node_filter_map->set(n, false); }

   361     ///\e

   363     /// This function hides \c e in the graph, i.e. the iteration

   364     /// jumps over it. This is done by simply setting the value of \c e

   365     /// to be false in the corresponding edge-map.

   366     void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }

   368     ///\e

   370     /// The value of \c n is set to be true in the node-map which stores

   371     /// hide information. If \c n was hidden previuosly, then it is shown

   372     /// again

   373      void unHide(const Node& n) const { node_filter_map->set(n, true); }

   375     ///\e

   377     /// The value of \c e is set to be true in the edge-map which stores

   378     /// hide information. If \c e was hidden previuosly, then it is shown

   379     /// again

   380     void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }

   382     /// Returns true if \c n is hidden.

   384     ///\e

   385     ///

   386     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }

   388     /// Returns true if \c n is hidden.

   390     ///\e

   391     ///

   392     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }

   394     typedef False NodeNumTag;

   395     typedef False EdgeNumTag;

   397     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

   398     Edge findEdge(const Node& source, const Node& target,

   399 		  const Edge& prev = INVALID) {

   400       if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {

   401         return INVALID;

   402       }

   403       Edge edge = Parent::findEdge(source, target, prev);

   404       while (edge != INVALID && !(*uedge_filter_map)[edge]) {

   405         edge = Parent::findEdge(source, target, edge);

   406       }

   407       return edge;

   408     }

   409     UEdge findUEdge(const Node& source, const Node& target,

   410 		  const UEdge& prev = INVALID) {

   411       if (!(*node_filter_map)[source] || !(*node_filter_map)[target]) {

   412         return INVALID;

   413       }

   414       UEdge uedge = Parent::findUEdge(source, target, prev);

   415       while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {

   416         uedge = Parent::findUEdge(source, target, uedge);

   417       }

   418       return uedge;

   419     }

   421     template <typename _Value>

   422     class NodeMap

   423       : public SubMapExtender<Adaptor,

   424                               typename Parent::template NodeMap<_Value> >

   425     {

   426     public:

   427       typedef Adaptor Graph;

   428       typedef SubMapExtender<Adaptor, typename Parent::

   429                              template NodeMap<_Value> > Parent;

   431       NodeMap(const Graph& graph)

   432 	: Parent(graph) {}

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

   434 	: Parent(graph, value) {}

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

   437 	return operator=<NodeMap>(cmap);

   438       }

   440       template <typename CMap>

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

   442         Parent::operator=(cmap);

   443 	return *this;

   444       }

   445     };

   447     template <typename _Value>

   448     class EdgeMap

   449       : public SubMapExtender<Adaptor,

   450                               typename Parent::template EdgeMap<_Value> >

   451     {

   452     public:

   453       typedef Adaptor Graph;

   454       typedef SubMapExtender<Adaptor, typename Parent::

   455                              template EdgeMap<_Value> > Parent;

   457       EdgeMap(const Graph& graph)

   458 	: Parent(graph) {}

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

   460 	: Parent(graph, value) {}

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

   463 	return operator=<EdgeMap>(cmap);

   464       }

   466       template <typename CMap>

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

   468         Parent::operator=(cmap);

   469 	return *this;

   470       }

   471     };

   473     template <typename _Value>

   474     class UEdgeMap

   475       : public SubMapExtender<Adaptor,

   476                               typename Parent::template UEdgeMap<_Value> >

   477     {

   478     public:

   479       typedef Adaptor Graph;

   480       typedef SubMapExtender<Adaptor, typename Parent::

   481                              template UEdgeMap<_Value> > Parent;

   483       UEdgeMap(const Graph& graph)

   484 	: Parent(graph) {}

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

   486 	: Parent(graph, value) {}

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

   489 	return operator=<UEdgeMap>(cmap);

   490       }

   492       template <typename CMap>

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

   494         Parent::operator=(cmap);

   495 	return *this;

   496       }

   497     };

   499   };

   501   template <typename _UGraph, typename NodeFilterMap, typename UEdgeFilterMap>

   502   class SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, false>

   503     : public UGraphAdaptorBase<_UGraph> {

   504   public:

   505     typedef _UGraph Graph;

   506     typedef SubUGraphAdaptorBase Adaptor;

   507     typedef UGraphAdaptorBase<_UGraph> Parent;

   508   protected:

   509     NodeFilterMap* node_filter_map;

   510     UEdgeFilterMap* uedge_filter_map;

   511     SubUGraphAdaptorBase() : Parent(),

   512 			    node_filter_map(0), uedge_filter_map(0) { }

   514     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   515       node_filter_map=&_node_filter_map;

   516     }

   517     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {

   518       uedge_filter_map=&_uedge_filter_map;

   519     }

   521   public:

   523     typedef typename Parent::Node Node;

   524     typedef typename Parent::Edge Edge;

   525     typedef typename Parent::UEdge UEdge;

   527     void first(Node& i) const {

   528       Parent::first(i);

   529       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);

   530     }

   532     void first(Edge& i) const {

   533       Parent::first(i);

   534       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);

   535     }

   537     void first(UEdge& i) const {

   538       Parent::first(i);

   539       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);

   540     }

   542     void firstIn(Edge& i, const Node& n) const {

   543       Parent::firstIn(i, n);

   544       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);

   545     }

   547     void firstOut(Edge& i, const Node& n) const {

   548       Parent::firstOut(i, n);

   549       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);

   550     }

   552     void firstInc(UEdge& i, bool& d, const Node& n) const {

   553       Parent::firstInc(i, d, n);

   554       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);

   555     }

   557     void next(Node& i) const {

   558       Parent::next(i);

   559       while (i!=INVALID && !(*node_filter_map)[i]) Parent::next(i);

   560     }

   561     void next(Edge& i) const {

   562       Parent::next(i);

   563       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);

   564     }

   565     void next(UEdge& i) const {

   566       Parent::next(i);

   567       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::next(i);

   568     }

   569     void nextIn(Edge& i) const {

   570       Parent::nextIn(i);

   571       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextIn(i);

   572     }

   574     void nextOut(Edge& i) const {

   575       Parent::nextOut(i);

   576       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextOut(i);

   577     }

   578     void nextInc(UEdge& i, bool& d) const {

   579       Parent::nextInc(i, d);

   580       while (i!=INVALID && !(*uedge_filter_map)[i]) Parent::nextInc(i, d);

   581     }

   583     ///\e

   585     /// This function hides \c n in the graph, i.e. the iteration

   586     /// jumps over it. This is done by simply setting the value of \c n

   587     /// to be false in the corresponding node-map.

   588     void hide(const Node& n) const { node_filter_map->set(n, false); }

   590     ///\e

   592     /// This function hides \c e in the graph, i.e. the iteration

   593     /// jumps over it. This is done by simply setting the value of \c e

   594     /// to be false in the corresponding edge-map.

   595     void hide(const UEdge& e) const { uedge_filter_map->set(e, false); }

   597     ///\e

   599     /// The value of \c n is set to be true in the node-map which stores

   600     /// hide information. If \c n was hidden previuosly, then it is shown

   601     /// again

   602      void unHide(const Node& n) const { node_filter_map->set(n, true); }

   604     ///\e

   606     /// The value of \c e is set to be true in the edge-map which stores

   607     /// hide information. If \c e was hidden previuosly, then it is shown

   608     /// again

   609     void unHide(const UEdge& e) const { uedge_filter_map->set(e, true); }

   611     /// Returns true if \c n is hidden.

   613     ///\e

   614     ///

   615     bool hidden(const Node& n) const { return !(*node_filter_map)[n]; }

   617     /// Returns true if \c n is hidden.

   619     ///\e

   620     ///

   621     bool hidden(const UEdge& e) const { return !(*uedge_filter_map)[e]; }

   623     typedef False NodeNumTag;

   624     typedef False EdgeNumTag;

   626     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

   627     Edge findEdge(const Node& source, const Node& target,

   628 		  const Edge& prev = INVALID) {

   629       Edge edge = Parent::findEdge(source, target, prev);

   630       while (edge != INVALID && !(*uedge_filter_map)[edge]) {

   631         edge = Parent::findEdge(source, target, edge);

   632       }

   633       return edge;

   634     }

   635     UEdge findUEdge(const Node& source, const Node& target,

   636 		  const UEdge& prev = INVALID) {

   637       UEdge uedge = Parent::findUEdge(source, target, prev);

   638       while (uedge != INVALID && !(*uedge_filter_map)[uedge]) {

   639         uedge = Parent::findUEdge(source, target, uedge);

   640       }

   641       return uedge;

   642     }

   644     template <typename _Value>

   645     class NodeMap

   646       : public SubMapExtender<Adaptor,

   647                               typename Parent::template NodeMap<_Value> >

   648     {

   649     public:

   650       typedef Adaptor Graph;

   651       typedef SubMapExtender<Adaptor, typename Parent::

   652                              template NodeMap<_Value> > Parent;

   654       NodeMap(const Graph& graph)

   655 	: Parent(graph) {}

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

   657 	: Parent(graph, value) {}

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

   660 	return operator=<NodeMap>(cmap);

   661       }

   663       template <typename CMap>

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

   665         Parent::operator=(cmap);

   666 	return *this;

   667       }

   668     };

   670     template <typename _Value>

   671     class EdgeMap

   672       : public SubMapExtender<Adaptor,

   673                               typename Parent::template EdgeMap<_Value> >

   674     {

   675     public:

   676       typedef Adaptor Graph;

   677       typedef SubMapExtender<Adaptor, typename Parent::

   678                              template EdgeMap<_Value> > Parent;

   680       EdgeMap(const Graph& graph)

   681 	: Parent(graph) {}

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

   683 	: Parent(graph, value) {}

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

   686 	return operator=<EdgeMap>(cmap);

   687       }

   689       template <typename CMap>

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

   691         Parent::operator=(cmap);

   692 	return *this;

   693       }

   694     };

   696     template <typename _Value>

   697     class UEdgeMap

   698       : public SubMapExtender<Adaptor,

   699                               typename Parent::template UEdgeMap<_Value> >

   700     {

   701     public:

   702       typedef Adaptor Graph;

   703       typedef SubMapExtender<Adaptor, typename Parent::

   704                              template UEdgeMap<_Value> > Parent;

   706       UEdgeMap(const Graph& graph)

   707 	: Parent(graph) {}

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

   709 	: Parent(graph, value) {}

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

   712 	return operator=<UEdgeMap>(cmap);

   713       }

   715       template <typename CMap>

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

   717         Parent::operator=(cmap);

   718 	return *this;

   719       }

   720     };

   721   };

   723   /// \ingroup graph_adaptors

   724   ///

   725   /// \brief A graph adaptor for hiding nodes and edges from an undirected

   726   /// graph.

   727   ///

   728   /// SubUGraphAdaptor shows the undirected graph with filtered node-set and

   729   /// edge-set. If the \c checked parameter is true then it filters the edgeset

   730   /// to do not get invalid edges without source or target.

   731   ///

   732   /// If the \c checked template parameter is false then we have to note that

   733   /// the node-iterator cares only the filter on the node-set, and the

   734   /// edge-iterator cares only the filter on the edge-set.

   735   /// This way the edge-map

   736   /// should filter all edges which's source or target is filtered by the

   737   /// node-filter.

   738   ///

   739   /// Note that \c n is of type \c SubGA::NodeIt, but it can be converted to

   740   /// \c Graph::Node that is why \c g.id(n) can be applied.

   741   ///

   742   template<typename _UGraph, typename NodeFilterMap,

   743 	   typename UEdgeFilterMap, bool checked = true>

   744   class SubUGraphAdaptor :

   745     public UGraphAdaptorExtender<

   746     SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap, checked> > {

   747   public:

   748     typedef _UGraph Graph;

   749     typedef UGraphAdaptorExtender<

   750       SubUGraphAdaptorBase<_UGraph, NodeFilterMap, UEdgeFilterMap> > Parent;

   751   protected:

   752     SubUGraphAdaptor() { }

   753   public:

   754     SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,

   755 		    UEdgeFilterMap& _uedge_filter_map) {

   756       setGraph(_graph);

   757       setNodeFilterMap(_node_filter_map);

   758       setUEdgeFilterMap(_uedge_filter_map);

   759     }

   760   };

   762   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>

   763   SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>

   764   subUGraphAdaptor(const UGraph& graph,

   765                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   766     return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>

   767       (graph, nfm, efm);

   768   }

   770   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>

   771   SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>

   772   subUGraphAdaptor(const UGraph& graph,

   773                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   774     return SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>

   775       (graph, nfm, efm);

   776   }

   778   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>

   779   SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>

   780   subUGraphAdaptor(const UGraph& graph,

   781                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   782     return SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>

   783       (graph, nfm, efm);

   784   }

   786   template<typename UGraph, typename NodeFilterMap, typename EdgeFilterMap>

   787   SubUGraphAdaptor<const UGraph, const NodeFilterMap, const EdgeFilterMap>

   788   subUGraphAdaptor(const UGraph& graph,

   789                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   790     return SubUGraphAdaptor<const UGraph, const NodeFilterMap,

   791       const EdgeFilterMap>(graph, nfm, efm);

   792   }

   794   /// \ingroup graph_adaptors

   795   ///

   796   /// \brief An adaptor for hiding nodes from an undirected graph.

   797   ///

   798   /// An adaptor for hiding nodes from an undirected graph.

   799   /// This adaptor specializes SubUGraphAdaptor in the way that only

   800   /// the node-set

   801   /// can be filtered. In usual case the checked parameter is true, we get the

   802   /// induced subgraph. But if the checked parameter is false then we can only

   803   /// filter only isolated nodes.

   804   template<typename _UGraph, typename NodeFilterMap, bool checked = true>

   805   class NodeSubUGraphAdaptor :

   806     public SubUGraphAdaptor<_UGraph, NodeFilterMap,

   807                             ConstMap<typename _UGraph::UEdge, bool>, checked> {

   808   public:

   809     typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,

   810                              ConstMap<typename _UGraph::UEdge, bool> > Parent;

   811     typedef _UGraph Graph;

   812   protected:

   813     ConstMap<typename _UGraph::UEdge, bool> const_true_map;

   815     NodeSubUGraphAdaptor() : const_true_map(true) {

   816       Parent::setUEdgeFilterMap(const_true_map);

   817     }

   819   public:

   820     NodeSubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map) :

   821       Parent(), const_true_map(true) {

   822       Parent::setGraph(_graph);

   823       Parent::setNodeFilterMap(_node_filter_map);

   824       Parent::setUEdgeFilterMap(const_true_map);

   825     }

   826   };

   828   template<typename UGraph, typename NodeFilterMap>

   829   NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>

   830   nodeSubUGraphAdaptor(const UGraph& graph, NodeFilterMap& nfm) {

   831     return NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>(graph, nfm);

   832   }

   834   template<typename UGraph, typename NodeFilterMap>

   835   NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>

   836   nodeSubUGraphAdaptor(const UGraph& graph, const NodeFilterMap& nfm) {

   837     return NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>(graph, nfm);

   838   }

   840   /// \brief An adaptor for hiding undirected edges from an undirected graph.

   841   ///

   842   /// \warning Graph adaptors are in even more experimental state

   843   /// than the other parts of the lib. Use them at you own risk.

   844   ///

   845   /// An adaptor for hiding undirected edges from an undirected graph.

   846   /// This adaptor specializes SubUGraphAdaptor in the way that

   847   /// only the edge-set

   848   /// can be filtered.

   849   template<typename _UGraph, typename UEdgeFilterMap>

   850   class EdgeSubUGraphAdaptor :

   851     public SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,

   852                             UEdgeFilterMap, false> {

   853   public:

   854     typedef SubUGraphAdaptor<_UGraph, ConstMap<typename _UGraph::Node,bool>,

   855                              UEdgeFilterMap, false> Parent;

   856     typedef _UGraph Graph;

   857   protected:

   858     ConstMap<typename Graph::Node, bool> const_true_map;

   860     EdgeSubUGraphAdaptor() : const_true_map(true) {

   861       Parent::setNodeFilterMap(const_true_map);

   862     }

   864   public:

   866     EdgeSubUGraphAdaptor(Graph& _graph, UEdgeFilterMap& _uedge_filter_map) :

   867       Parent(), const_true_map(true) {

   868       Parent::setGraph(_graph);

   869       Parent::setNodeFilterMap(const_true_map);

   870       Parent::setUEdgeFilterMap(_uedge_filter_map);

   871     }

   873   };

   875   template<typename UGraph, typename EdgeFilterMap>

   876   EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>

   877   edgeSubUGraphAdaptor(const UGraph& graph, EdgeFilterMap& efm) {

   878     return EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>(graph, efm);

   879   }

   881   template<typename UGraph, typename EdgeFilterMap>

   882   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>

   883   edgeSubUGraphAdaptor(const UGraph& graph, const EdgeFilterMap& efm) {

   884     return EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>(graph, efm);

   885   }

   887   template <typename _UGraph, typename _DirectionMap>

   888   class DirUGraphAdaptorBase {

   889   public:

   891     typedef _UGraph Graph;

   892     typedef _DirectionMap DirectionMap;

   894     typedef typename _UGraph::Node Node;

   895     typedef typename _UGraph::UEdge Edge;

   897     void reverseEdge(const Edge& edge) {

   898       direction->set(edge, !(*direction)[edge]);

   899     }

   901     void first(Node& i) const { graph->first(i); }

   902     void first(Edge& i) const { graph->first(i); }

   903     void firstIn(Edge& i, const Node& n) const {

   904       bool d;

   905       graph->firstInc(i, d, n);

   906       while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);

   907     }

   908     void firstOut(Edge& i, const Node& n ) const {

   909       bool d;

   910       graph->firstInc(i, d, n);

   911       while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);

   912     }

   914     void next(Node& i) const { graph->next(i); }

   915     void next(Edge& i) const { graph->next(i); }

   916     void nextIn(Edge& i) const {

   917       bool d = !(*direction)[i];

   918       graph->nextInc(i, d);

   919       while (i != INVALID && d == (*direction)[i]) graph->nextInc(i, d);

   920     }

   921     void nextOut(Edge& i) const {

   922       bool d = (*direction)[i];

   923       graph->nextInc(i, d);

   924       while (i != INVALID && d != (*direction)[i]) graph->nextInc(i, d);

   925     }

   927     Node source(const Edge& e) const {

   928       return (*direction)[e] ? graph->source(e) : graph->target(e);

   929     }

   930     Node target(const Edge& e) const {

   931       return (*direction)[e] ? graph->target(e) : graph->source(e);

   932     }

   934     typedef NodeNumTagIndicator<Graph> NodeNumTag;

   935     int nodeNum() const { return graph->nodeNum(); }

   937     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

   938     int edgeNum() const { return graph->uEdgeNum(); }

   940     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

   941     Edge findEdge(const Node& source, const Node& target,

   942 		  const Edge& prev = INVALID) {

   943       Edge edge = prev;

   944       bool d = edge == INVALID ? true : (*direction)[edge];

   945       if (d) {

   946         edge = graph->findUEdge(source, target, edge);

   947         while (edge != INVALID && !(*direction)[edge]) {

   948           graph->findUEdge(source, target, edge);

   949         }

   950         if (edge != INVALID) return edge;

   951       }

   952       graph->findUEdge(target, source, edge);

   953       while (edge != INVALID && (*direction)[edge]) {

   954         graph->findUEdge(source, target, edge);

   955       }

   956       return edge;

   957     }

   959     Node addNode() const {

   960       return Node(graph->addNode());

   961     }

   963     Edge addEdge(const Node& source, const Node& target) const {

   964       Edge edge = graph->addEdge(source, target);

   965       (*direction)[edge] = graph->source(edge) == source;

   966       return edge;

   967     }

   969     void erase(const Node& i) const { graph->erase(i); }

   970     void erase(const Edge& i) const { graph->erase(i); }

   972     void clear() const { graph->clear(); }

   974     int id(const Node& v) const { return graph->id(v); }

   975     int id(const Edge& e) const { return graph->id(e); }

   977     int maxNodeId() const {

   978       return graph->maxNodeId();

   979     }

   981     int maxEdgeId() const {

   982       return graph->maxEdgeId();

   983     }

   985     typedef typename ItemSetTraits<Graph, Node>::ItemNotifier NodeNotifier;

   987     NodeNotifier& getNotifier(Node) const {

   988       return graph->getNotifier(Node());

   989     }

   991     typedef typename ItemSetTraits<Graph, Edge>::ItemNotifier EdgeNotifier;

   993     EdgeNotifier& getNotifier(Edge) const {

   994       return graph->getNotifier(Edge());

   995     }

   997     template <typename _Value>

   998     class NodeMap : public _UGraph::template NodeMap<_Value> {

   999     public:

  1001       typedef typename _UGraph::template NodeMap<_Value> Parent;

  1003       explicit NodeMap(const DirUGraphAdaptorBase& ga)

  1004 	: Parent(*ga.graph) {}

  1006       NodeMap(const DirUGraphAdaptorBase& ga, const _Value& value)

  1007 	: Parent(*ga.graph, value) {}

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

  1010         return operator=<NodeMap>(cmap);

  1011       }

  1013       template <typename CMap>

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

  1015         Parent::operator=(cmap);

  1016         return *this;

  1017       }

  1019     };

  1021     template <typename _Value>

  1022     class EdgeMap : public _UGraph::template UEdgeMap<_Value> {

  1023     public:

  1025       typedef typename _UGraph::template UEdgeMap<_Value> Parent;

  1027       explicit EdgeMap(const DirUGraphAdaptorBase& ga)

  1028 	: Parent(*ga.graph) { }

  1030       EdgeMap(const DirUGraphAdaptorBase& ga, const _Value& value)

  1031 	: Parent(*ga.graph, value) { }

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

  1034         return operator=<EdgeMap>(cmap);

  1035       }

  1037       template <typename CMap>

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

  1039         Parent::operator=(cmap);

  1040         return *this;

  1041       }

  1042     };

  1046   protected:

  1047     Graph* graph;

  1048     DirectionMap* direction;

  1050     void setDirectionMap(DirectionMap& _direction) {

  1051       direction = &_direction;

  1052     }

  1054     void setGraph(Graph& _graph) {

  1055       graph = &_graph;

  1056     }

  1058   };

  1061   /// \ingroup graph_adaptors

  1062   ///

  1063   /// \brief A directed graph is made from an undirected graph by an adaptor

  1064   ///

  1065   /// This adaptor gives a direction for each uedge in the undirected graph.

  1066   /// The direction of the edges stored in the DirectionMap. This map is

  1067   /// a bool map on the undirected edges. If the uedge is mapped to true

  1068   /// then the direction of the directed edge will be the same as the

  1069   /// default direction of the uedge. The edges can be easily reverted

  1070   /// by the reverseEdge member in the adaptor.

  1071   template<typename _Graph,

  1072            typename DirectionMap = typename _Graph::template UEdgeMap<bool> >

  1073   class DirUGraphAdaptor :

  1074     public GraphAdaptorExtender<

  1075     DirUGraphAdaptorBase<_Graph, DirectionMap> > {

  1076   public:

  1077     typedef _Graph Graph;

  1078     typedef GraphAdaptorExtender<

  1079       DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;

  1080   protected:

  1081     DirUGraphAdaptor() { }

  1082   public:

  1083     DirUGraphAdaptor(_Graph& _graph, DirectionMap& _direction_map) {

  1084       setGraph(_graph);

  1085       setDirectionMap(_direction_map);

  1086     }

  1087   };

  1089   template<typename UGraph, typename DirectionMap>

  1090   DirUGraphAdaptor<const UGraph, DirectionMap>

  1091   dirUGraphAdaptor(const UGraph& graph, DirectionMap& dm) {

  1092     return DirUGraphAdaptor<const UGraph, DirectionMap>(graph, dm);

  1093   }

  1095   template<typename UGraph, typename DirectionMap>

  1096   DirUGraphAdaptor<const UGraph, const DirectionMap>

  1097   dirUGraphAdaptor(const UGraph& graph, const DirectionMap& dm) {

  1098     return DirUGraphAdaptor<const UGraph, const DirectionMap>(graph, dm);

  1099   }

  1101 }

  1103 #endif

author	deba
	Mon, 03 Apr 2006 09:45:23 +0000
changeset 2031	080d51024ac5
parent 1993	2115143eceea
child 2037	32e4bebee616
permissions	-rw-r--r--