lemon-0.x: lemon/ugraph_adaptor.h@33db14058543

     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   public:

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

    70     typedef typename Graph::Node Node;

    71     typedef typename Graph::Edge Edge;

    72     typedef typename Graph::UEdge UEdge;

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

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

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

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

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

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

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

    81     }

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

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

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

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

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

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

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

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

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

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

    96     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

    99     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

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

   103     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

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

   105 		  const Edge& prev = INVALID) {

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

   107     }

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

   109                     const UEdge& prev = INVALID) {

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

   111     }

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

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

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

   116     }

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

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

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

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

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

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

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

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

   130     Node fromNodeId(int id) const {

   131       return graph->fromNodeId(id);

   132     }

   134     Edge fromEdgeId(int id) const {

   135       return graph->fromEdgeId(id);

   136     }

   138     UEdge fromUEdgeId(int id) const {

   139       return graph->fromUEdgeId(id);

   140     }

   142     int maxNodeId() const {

   143       return graph->maxNodeId();

   144     }

   146     int maxEdgeId() const {

   147       return graph->maxEdgeId();

   148     }

   150     int maxUEdgeId() const {

   151       return graph->maxEdgeId();

   152     }

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

   156     NodeNotifier& getNotifier(Node) const {

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

   158     }

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

   162     EdgeNotifier& getNotifier(Edge) const {

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

   164     }

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

   168     UEdgeNotifier& getNotifier(UEdge) const {

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

   170     }

   172     template <typename _Value>

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

   174     public:

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

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

   177 	: Parent(*ga.graph) {}

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

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

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

   182 	return operator=<NodeMap>(cmap);

   183       }

   185       template <typename CMap>

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

   187         Parent::operator=(cmap);

   188         return *this;

   189       }

   191     };

   193     template <typename _Value>

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

   195     public:

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

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

   198 	: Parent(*ga.graph) {}

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

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

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

   203 	return operator=<EdgeMap>(cmap);

   204       }

   206       template <typename CMap>

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

   208         Parent::operator=(cmap);

   209 	return *this;

   210       }

   211     };

   213     template <typename _Value>

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

   215     public:

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

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

   218 	: Parent(*ga.graph) {}

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

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

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

   223 	return operator=<UEdgeMap>(cmap);

   224       }

   226       template <typename CMap>

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

   228         Parent::operator=(cmap);

   229         return *this;

   230       }

   231     };

   233   };

   235   /// \ingroup graph_adaptors

   236   template <typename _UGraph>

   237   class UGraphAdaptor

   238     : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {

   239   public:

   240     typedef _UGraph Graph;

   241     typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;

   242   protected:

   243     UGraphAdaptor() : Parent() {}

   245   public:

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

   247   };

   249   template <typename _UGraph, typename NodeFilterMap,

   250 	    typename UEdgeFilterMap, bool checked = true>

   251   class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {

   252   public:

   253     typedef _UGraph Graph;

   254     typedef SubUGraphAdaptorBase Adaptor;

   255     typedef UGraphAdaptorBase<_UGraph> Parent;

   256   protected:

   258     NodeFilterMap* node_filter_map;

   259     UEdgeFilterMap* uedge_filter_map;

   261     SubUGraphAdaptorBase()

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

   264     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   265       node_filter_map=&_node_filter_map;

   266     }

   267     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {

   268       uedge_filter_map=&_uedge_filter_map;

   269     }

   271   public:

   273     typedef typename Parent::Node Node;

   274     typedef typename Parent::Edge Edge;

   275     typedef typename Parent::UEdge UEdge;

   277     void first(Node& i) const {

   278       Parent::first(i);

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

   280     }

   282     void first(Edge& i) const {

   283       Parent::first(i);

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

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

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

   287     }

   289     void first(UEdge& i) const {

   290       Parent::first(i);

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

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

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

   294     }

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

   297       Parent::firstIn(i, n);

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

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

   300     }

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

   303       Parent::firstOut(i, n);

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

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

   306     }

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

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

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

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

   312     }

   314     void next(Node& i) const {

   315       Parent::next(i);

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

   317     }

   319     void next(Edge& i) const {

   320       Parent::next(i);

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

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

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

   324     }

   326     void next(UEdge& i) const {

   327       Parent::next(i);

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

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

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

   331     }

   333     void nextIn(Edge& i) const {

   334       Parent::nextIn(i);

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

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

   337     }

   339     void nextOut(Edge& i) const {

   340       Parent::nextOut(i);

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

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

   343     }

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

   346       Parent::nextInc(i, d);

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

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

   349     }

   351     ///\e

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

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

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

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

   358     ///\e

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

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

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

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

   365     ///\e

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

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

   369     /// again

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

   372     ///\e

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

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

   376     /// again

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

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

   381     ///\e

   382     ///

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

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

   387     ///\e

   388     ///

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

   391     typedef False NodeNumTag;

   392     typedef False EdgeNumTag;

   394     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

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

   396 		  const Edge& prev = INVALID) {

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

   398         return INVALID;

   399       }

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

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

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

   403       }

   404       return edge;

   405     }

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

   407 		  const UEdge& prev = INVALID) {

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

   409         return INVALID;

   410       }

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

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

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

   414       }

   415       return uedge;

   416     }

   418     template <typename _Value>

   419     class NodeMap

   420       : public SubMapExtender<Adaptor,

   421                               typename Parent::template NodeMap<_Value> >

   422     {

   423     public:

   424       typedef Adaptor Graph;

   425       typedef SubMapExtender<Adaptor, typename Parent::

   426                              template NodeMap<_Value> > Parent;

   428       NodeMap(const Graph& graph)

   429 	: Parent(graph) {}

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

   431 	: Parent(graph, value) {}

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

   434 	return operator=<NodeMap>(cmap);

   435       }

   437       template <typename CMap>

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

   439         Parent::operator=(cmap);

   440 	return *this;

   441       }

   442     };

   444     template <typename _Value>

   445     class EdgeMap

   446       : public SubMapExtender<Adaptor,

   447                               typename Parent::template EdgeMap<_Value> >

   448     {

   449     public:

   450       typedef Adaptor Graph;

   451       typedef SubMapExtender<Adaptor, typename Parent::

   452                              template EdgeMap<_Value> > Parent;

   454       EdgeMap(const Graph& graph)

   455 	: Parent(graph) {}

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

   457 	: Parent(graph, value) {}

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

   460 	return operator=<EdgeMap>(cmap);

   461       }

   463       template <typename CMap>

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

   465         Parent::operator=(cmap);

   466 	return *this;

   467       }

   468     };

   470     template <typename _Value>

   471     class UEdgeMap

   472       : public SubMapExtender<Adaptor,

   473                               typename Parent::template UEdgeMap<_Value> >

   474     {

   475     public:

   476       typedef Adaptor Graph;

   477       typedef SubMapExtender<Adaptor, typename Parent::

   478                              template UEdgeMap<_Value> > Parent;

   480       UEdgeMap(const Graph& graph)

   481 	: Parent(graph) {}

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

   483 	: Parent(graph, value) {}

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

   486 	return operator=<UEdgeMap>(cmap);

   487       }

   489       template <typename CMap>

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

   491         Parent::operator=(cmap);

   492 	return *this;

   493       }

   494     };

   496   };

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

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

   500     : public UGraphAdaptorBase<_UGraph> {

   501   public:

   502     typedef _UGraph Graph;

   503     typedef SubUGraphAdaptorBase Adaptor;

   504     typedef UGraphAdaptorBase<_UGraph> Parent;

   505   protected:

   506     NodeFilterMap* node_filter_map;

   507     UEdgeFilterMap* uedge_filter_map;

   508     SubUGraphAdaptorBase() : Parent(),

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

   511     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   512       node_filter_map=&_node_filter_map;

   513     }

   514     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {

   515       uedge_filter_map=&_uedge_filter_map;

   516     }

   518   public:

   520     typedef typename Parent::Node Node;

   521     typedef typename Parent::Edge Edge;

   522     typedef typename Parent::UEdge UEdge;

   524     void first(Node& i) const {

   525       Parent::first(i);

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

   527     }

   529     void first(Edge& i) const {

   530       Parent::first(i);

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

   532     }

   534     void first(UEdge& i) const {

   535       Parent::first(i);

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

   537     }

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

   540       Parent::firstIn(i, n);

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

   542     }

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

   545       Parent::firstOut(i, n);

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

   547     }

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

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

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

   552     }

   554     void next(Node& i) const {

   555       Parent::next(i);

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

   557     }

   558     void next(Edge& i) const {

   559       Parent::next(i);

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

   561     }

   562     void next(UEdge& i) const {

   563       Parent::next(i);

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

   565     }

   566     void nextIn(Edge& i) const {

   567       Parent::nextIn(i);

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

   569     }

   571     void nextOut(Edge& i) const {

   572       Parent::nextOut(i);

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

   574     }

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

   576       Parent::nextInc(i, d);

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

   578     }

   580     ///\e

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

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

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

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

   587     ///\e

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

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

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

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

   594     ///\e

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

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

   598     /// again

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

   601     ///\e

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

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

   605     /// again

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

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

   610     ///\e

   611     ///

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

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

   616     ///\e

   617     ///

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

   620     typedef False NodeNumTag;

   621     typedef False EdgeNumTag;

   623     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

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

   625 		  const Edge& prev = INVALID) {

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

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

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

   629       }

   630       return edge;

   631     }

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

   633 		  const UEdge& prev = INVALID) {

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

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

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

   637       }

   638       return uedge;

   639     }

   641     template <typename _Value>

   642     class NodeMap

   643       : public SubMapExtender<Adaptor,

   644                               typename Parent::template NodeMap<_Value> >

   645     {

   646     public:

   647       typedef Adaptor Graph;

   648       typedef SubMapExtender<Adaptor, typename Parent::

   649                              template NodeMap<_Value> > Parent;

   651       NodeMap(const Graph& graph)

   652 	: Parent(graph) {}

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

   654 	: Parent(graph, value) {}

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

   657 	return operator=<NodeMap>(cmap);

   658       }

   660       template <typename CMap>

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

   662         Parent::operator=(cmap);

   663 	return *this;

   664       }

   665     };

   667     template <typename _Value>

   668     class EdgeMap

   669       : public SubMapExtender<Adaptor,

   670                               typename Parent::template EdgeMap<_Value> >

   671     {

   672     public:

   673       typedef Adaptor Graph;

   674       typedef SubMapExtender<Adaptor, typename Parent::

   675                              template EdgeMap<_Value> > Parent;

   677       EdgeMap(const Graph& graph)

   678 	: Parent(graph) {}

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

   680 	: Parent(graph, value) {}

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

   683 	return operator=<EdgeMap>(cmap);

   684       }

   686       template <typename CMap>

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

   688         Parent::operator=(cmap);

   689 	return *this;

   690       }

   691     };

   693     template <typename _Value>

   694     class UEdgeMap

   695       : public SubMapExtender<Adaptor,

   696                               typename Parent::template UEdgeMap<_Value> >

   697     {

   698     public:

   699       typedef Adaptor Graph;

   700       typedef SubMapExtender<Adaptor, typename Parent::

   701                              template UEdgeMap<_Value> > Parent;

   703       UEdgeMap(const Graph& graph)

   704 	: Parent(graph) {}

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

   706 	: Parent(graph, value) {}

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

   709 	return operator=<UEdgeMap>(cmap);

   710       }

   712       template <typename CMap>

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

   714         Parent::operator=(cmap);

   715 	return *this;

   716       }

   717     };

   718   };

   720   /// \ingroup graph_adaptors

   721   ///

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

   723   /// graph.

   724   ///

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

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

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

   728   ///

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

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

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

   732   /// This way the edge-map

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

   734   /// node-filter.

   735   ///

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

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

   738   ///

   739   template<typename _UGraph, typename NodeFilterMap,

   740 	   typename UEdgeFilterMap, bool checked = true>

   741   class SubUGraphAdaptor :

   742     public UGraphAdaptorExtender<

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

   744   public:

   745     typedef _UGraph Graph;

   746     typedef UGraphAdaptorExtender<

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

   748   protected:

   749     SubUGraphAdaptor() { }

   750   public:

   751     SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,

   752 		    UEdgeFilterMap& _uedge_filter_map) {

   753       setGraph(_graph);

   754       setNodeFilterMap(_node_filter_map);

   755       setUEdgeFilterMap(_uedge_filter_map);

   756     }

   757   };

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

   760   SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>

   761   subUGraphAdaptor(const UGraph& graph,

   762                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   763     return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>

   764       (graph, nfm, efm);

   765   }

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

   768   SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>

   769   subUGraphAdaptor(const UGraph& graph,

   770                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

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

   772       (graph, nfm, efm);

   773   }

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

   776   SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>

   777   subUGraphAdaptor(const UGraph& graph,

   778                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

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

   780       (graph, nfm, efm);

   781   }

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

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

   785   subUGraphAdaptor(const UGraph& graph,

   786                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   787     return SubUGraphAdaptor<const UGraph, const NodeFilterMap,

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

   789   }

   791   /// \ingroup graph_adaptors

   792   ///

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

   794   ///

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

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

   797   /// the node-set

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

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

   800   /// filter only isolated nodes.

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

   802   class NodeSubUGraphAdaptor :

   803     public SubUGraphAdaptor<_UGraph, NodeFilterMap,

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

   805   public:

   806     typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,

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

   808     typedef _UGraph Graph;

   809   protected:

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

   812     NodeSubUGraphAdaptor() : const_true_map(true) {

   813       Parent::setUEdgeFilterMap(const_true_map);

   814     }

   816   public:

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

   818       Parent(), const_true_map(true) {

   819       Parent::setGraph(_graph);

   820       Parent::setNodeFilterMap(_node_filter_map);

   821       Parent::setUEdgeFilterMap(const_true_map);

   822     }

   823   };

   825   template<typename UGraph, typename NodeFilterMap>

   826   NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>

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

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

   829   }

   831   template<typename UGraph, typename NodeFilterMap>

   832   NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>

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

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

   835   }

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

   838   ///

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

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

   841   ///

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

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

   844   /// only the edge-set

   845   /// can be filtered.

   846   template<typename _UGraph, typename UEdgeFilterMap>

   847   class EdgeSubUGraphAdaptor :

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

   849                             UEdgeFilterMap, false> {

   850   public:

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

   852                              UEdgeFilterMap, false> Parent;

   853     typedef _UGraph Graph;

   854   protected:

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

   857     EdgeSubUGraphAdaptor() : const_true_map(true) {

   858       Parent::setNodeFilterMap(const_true_map);

   859     }

   861   public:

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

   864       Parent(), const_true_map(true) {

   865       Parent::setGraph(_graph);

   866       Parent::setNodeFilterMap(const_true_map);

   867       Parent::setUEdgeFilterMap(_uedge_filter_map);

   868     }

   870   };

   872   template<typename UGraph, typename EdgeFilterMap>

   873   EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>

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

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

   876   }

   878   template<typename UGraph, typename EdgeFilterMap>

   879   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>

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

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

   882   }

   884   template <typename _UGraph, typename _DirectionMap>

   885   class DirUGraphAdaptorBase {

   886   public:

   888     typedef _UGraph Graph;

   889     typedef _DirectionMap DirectionMap;

   891     typedef typename _UGraph::Node Node;

   892     typedef typename _UGraph::UEdge Edge;

   894     void reverseEdge(const Edge& edge) {

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

   896     }

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

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

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

   901       bool d;

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

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

   904     }

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

   906       bool d;

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

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

   909     }

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

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

   913     void nextIn(Edge& i) const {

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

   915       graph->nextInc(i, d);

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

   917     }

   918     void nextOut(Edge& i) const {

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

   920       graph->nextInc(i, d);

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

   922     }

   924     Node source(const Edge& e) const {

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

   926     }

   927     Node target(const Edge& e) const {

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

   929     }

   931     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

   934     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

   937     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

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

   939 		  const Edge& prev = INVALID) {

   940       Edge edge = prev;

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

   942       if (d) {

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

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

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

   946         }

   947         if (edge != INVALID) return edge;

   948       }

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

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

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

   952       }

   953       return edge;

   954     }

   956     Node addNode() const {

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

   958     }

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

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

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

   963       return edge;

   964     }

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

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

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

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

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

   974     int maxNodeId() const {

   975       return graph->maxNodeId();

   976     }

   978     int maxEdgeId() const {

   979       return graph->maxEdgeId();

   980     }

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

   984     NodeNotifier& getNotifier(Node) const {

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

   986     }

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

   990     EdgeNotifier& getNotifier(Edge) const {

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

   992     }

   994     template <typename _Value>

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

   996     public:

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

  1000       explicit NodeMap(const DirUGraphAdaptorBase& ga)

  1001 	: Parent(*ga.graph) {}

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

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

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

  1007         return operator=<NodeMap>(cmap);

  1008       }

  1010       template <typename CMap>

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

  1012         Parent::operator=(cmap);

  1013         return *this;

  1014       }

  1016     };

  1018     template <typename _Value>

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

  1020     public:

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

  1024       explicit EdgeMap(const DirUGraphAdaptorBase& ga)

  1025 	: Parent(*ga.graph) { }

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

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

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

  1031         return operator=<EdgeMap>(cmap);

  1032       }

  1034       template <typename CMap>

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

  1036         Parent::operator=(cmap);

  1037         return *this;

  1038       }

  1039     };

  1043   protected:

  1044     Graph* graph;

  1045     DirectionMap* direction;

  1047     void setDirectionMap(DirectionMap& _direction) {

  1048       direction = &_direction;

  1049     }

  1051     void setGraph(Graph& _graph) {

  1052       graph = &_graph;

  1053     }

  1055   };

  1058   /// \ingroup graph_adaptors

  1059   ///

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

  1061   ///

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

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

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

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

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

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

  1068   template<typename _Graph,

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

  1070   class DirUGraphAdaptor :

  1071     public GraphAdaptorExtender<

  1072     DirUGraphAdaptorBase<_Graph, DirectionMap> > {

  1073   public:

  1074     typedef _Graph Graph;

  1075     typedef GraphAdaptorExtender<

  1076       DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;

  1077   protected:

  1078     DirUGraphAdaptor() { }

  1079   public:

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

  1081       setGraph(_graph);

  1082       setDirectionMap(_direction_map);

  1083     }

  1084   };

  1086   template<typename UGraph, typename DirectionMap>

  1087   DirUGraphAdaptor<const UGraph, DirectionMap>

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

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

  1090   }

  1092   template<typename UGraph, typename DirectionMap>

  1093   DirUGraphAdaptor<const UGraph, const DirectionMap>

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

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

  1096   }

  1098 }

  1100 #endif

author	deba
	Tue, 04 Apr 2006 17:45:35 +0000
changeset 2038	33db14058543
parent 2031	080d51024ac5
child 2042	bdc953f2a449
permissions	-rw-r--r--