lemon-0.x: lemon/ugraph_adaptor.h@9b56cca61e2e

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

    31 #include <lemon/maps.h>

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

    35 #include <lemon/traits.h>

    37 #include <iostream>

    39 namespace lemon {

    41   /// \ingroup graph_adaptors

    42   ///

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

    44   ///

    45   /// \warning Graph adaptors are in even more experimental state than the

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

    47   ///

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

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

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

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

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

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

    54   /// the differences should be implemented.

    55   ///

    56   /// \author Balazs Dezso

    57   template<typename _UGraph>

    58   class UGraphAdaptorBase {

    59   public:

    60     typedef _UGraph Graph;

    61     typedef Graph ParentGraph;

    63   protected:

    64     Graph* graph;

    66     UGraphAdaptorBase() : graph(0) {}

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

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

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

    73   public:

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

    76     typedef typename Graph::Node Node;

    77     typedef typename Graph::Edge Edge;

    78     typedef typename Graph::UEdge UEdge;

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

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

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

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

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

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

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

    87     }

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

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

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

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

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

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

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

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

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

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

   103     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

   106     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

   109     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

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

   111 		  const Edge& prev = INVALID) {

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

   113     }

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

   116                     const UEdge& prev = INVALID) {

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

   118     }

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

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

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

   123     }

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

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

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

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

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

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

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

   135     Edge direct(const UEdge& e, const Node& n) const {

   136       return graph->direct(e, n);

   137     }

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

   140       return graph->oppositeNode(n, e);

   141     }

   143     Edge oppositeEdge(const Edge& e) const {

   144       return graph->oppositeEdge(e);

   145     }

   148     template <typename _Value>

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

   150     public:

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

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

   153 	: Parent(*ga.graph) {}

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

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

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

   158 	return operator=<NodeMap>(cmap);

   159       }

   161       template <typename CMap>

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

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

   164 	const typename Parent::Graph* graph = Parent::getGraph();

   165 	Node it;

   166 	for (graph->first(it); it != INVALID; graph->next(it)) {

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

   168 	}

   169 	return *this;

   170       }

   171     };

   173     template <typename _Value>

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

   175     public:

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

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

   178 	: Parent(*ga.graph) {}

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

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

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

   183 	return operator=<EdgeMap>(cmap);

   184       }

   186       template <typename CMap>

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

   188 	checkConcept<concept::ReadMap<Edge, _Value>, CMap>();

   189 	const typename Parent::Graph* graph = Parent::getGraph();

   190 	Edge it;

   191 	for (graph->first(it); it != INVALID; graph->next(it)) {

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

   193 	}

   194 	return *this;

   195       }

   196     };

   198     template <typename _Value>

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

   200     public:

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

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

   203 	: Parent(*ga.graph) {}

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

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

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

   208 	return operator=<UEdgeMap>(cmap);

   209       }

   211       template <typename CMap>

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

   213 	checkConcept<concept::ReadMap<UEdge, _Value>, CMap>();

   214 	const typename Parent::Graph* graph = Parent::getGraph();

   215 	UEdge it;

   216 	for (graph->first(it); it != INVALID; graph->next(it)) {

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

   218 	}

   219 	return *this;

   220       }

   221     };

   223   };

   225   /// \ingroup graph_adaptors

   226   template <typename _UGraph>

   227   class UGraphAdaptor

   228     : public UGraphAdaptorExtender< UGraphAdaptorBase<_UGraph> > {

   229   public:

   230     typedef _UGraph Graph;

   231     typedef UGraphAdaptorExtender<UGraphAdaptorBase<_UGraph> > Parent;

   232   protected:

   233     UGraphAdaptor() : Parent() {}

   235   public:

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

   237   };

   239   template <typename _UGraph, typename NodeFilterMap,

   240 	    typename UEdgeFilterMap, bool checked = true>

   241   class SubUGraphAdaptorBase : public UGraphAdaptorBase<_UGraph> {

   242   public:

   243     typedef _UGraph Graph;

   244     typedef UGraphAdaptorBase<_UGraph> Parent;

   245   protected:

   247     NodeFilterMap* node_filter_map;

   248     UEdgeFilterMap* uedge_filter_map;

   250     SubUGraphAdaptorBase()

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

   253     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   254       node_filter_map=&_node_filter_map;

   255     }

   256     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {

   257       uedge_filter_map=&_uedge_filter_map;

   258     }

   260   public:

   262     typedef typename Parent::Node Node;

   263     typedef typename Parent::Edge Edge;

   264     typedef typename Parent::UEdge UEdge;

   266     void first(Node& i) const {

   267       Parent::first(i);

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

   269     }

   271     void first(Edge& i) const {

   272       Parent::first(i);

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

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

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

   276     }

   278     void first(UEdge& i) const {

   279       Parent::first(i);

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

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

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

   283     }

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

   286       Parent::firstIn(i, n);

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

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

   289     }

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

   292       Parent::firstOut(i, n);

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

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

   295     }

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

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

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

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

   301     }

   303     void next(Node& i) const {

   304       Parent::next(i);

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

   306     }

   308     void next(Edge& i) const {

   309       Parent::next(i);

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

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

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

   313     }

   315     void next(UEdge& i) const {

   316       Parent::next(i);

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

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

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

   320     }

   322     void nextIn(Edge& i) const {

   323       Parent::nextIn(i);

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

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

   326     }

   328     void nextOut(Edge& i) const {

   329       Parent::nextOut(i);

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

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

   332     }

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

   335       Parent::nextInc(i, d);

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

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

   338     }

   340     ///\e

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

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

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

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

   347     ///\e

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

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

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

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

   354     ///\e

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

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

   358     /// again

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

   361     ///\e

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

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

   365     /// again

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

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

   370     ///\e

   371     ///

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

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

   376     ///\e

   377     ///

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

   380     typedef False NodeNumTag;

   381     typedef False EdgeNumTag;

   382   };

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

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

   386     : public UGraphAdaptorBase<_UGraph> {

   387   public:

   388     typedef _UGraph Graph;

   389     typedef UGraphAdaptorBase<_UGraph> Parent;

   390   protected:

   391     NodeFilterMap* node_filter_map;

   392     UEdgeFilterMap* uedge_filter_map;

   393     SubUGraphAdaptorBase() : Parent(),

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

   396     void setNodeFilterMap(NodeFilterMap& _node_filter_map) {

   397       node_filter_map=&_node_filter_map;

   398     }

   399     void setUEdgeFilterMap(UEdgeFilterMap& _uedge_filter_map) {

   400       uedge_filter_map=&_uedge_filter_map;

   401     }

   403   public:

   405     typedef typename Parent::Node Node;

   406     typedef typename Parent::Edge Edge;

   407     typedef typename Parent::UEdge UEdge;

   409     void first(Node& i) const {

   410       Parent::first(i);

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

   412     }

   414     void first(Edge& i) const {

   415       Parent::first(i);

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

   417     }

   419     void first(UEdge& i) const {

   420       Parent::first(i);

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

   422     }

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

   425       Parent::firstIn(i, n);

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

   427     }

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

   430       Parent::firstOut(i, n);

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

   432     }

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

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

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

   437     }

   439     void next(Node& i) const {

   440       Parent::next(i);

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

   442     }

   443     void next(Edge& i) const {

   444       Parent::next(i);

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

   446     }

   447     void next(UEdge& i) const {

   448       Parent::next(i);

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

   450     }

   451     void nextIn(Edge& i) const {

   452       Parent::nextIn(i);

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

   454     }

   456     void nextOut(Edge& i) const {

   457       Parent::nextOut(i);

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

   459     }

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

   461       Parent::nextInc(i, d);

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

   463     }

   465     ///\e

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

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

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

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

   472     ///\e

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

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

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

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

   479     ///\e

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

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

   483     /// again

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

   486     ///\e

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

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

   490     /// again

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

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

   495     ///\e

   496     ///

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

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

   501     ///\e

   502     ///

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

   505     typedef False NodeNumTag;

   506     typedef False EdgeNumTag;

   507   };

   509   /// \ingroup graph_adaptors

   510   ///

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

   512   /// graph.

   513   ///

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

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

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

   517   ///

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

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

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

   521   /// This way the edge-map

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

   523   /// node-filter.

   524   ///

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

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

   527   ///

   528   template<typename _UGraph, typename NodeFilterMap,

   529 	   typename UEdgeFilterMap, bool checked = true>

   530   class SubUGraphAdaptor :

   531     public UGraphAdaptorExtender<

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

   533   public:

   534     typedef _UGraph Graph;

   535     typedef UGraphAdaptorExtender<

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

   537   protected:

   538     SubUGraphAdaptor() { }

   539   public:

   540     SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,

   541 		    UEdgeFilterMap& _uedge_filter_map) {

   542       setGraph(_graph);

   543       setNodeFilterMap(_node_filter_map);

   544       setUEdgeFilterMap(_uedge_filter_map);

   545     }

   546   };

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

   549   SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>

   550   subUGraphAdaptor(const UGraph& graph,

   551                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   552     return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>

   553       (graph, nfm, efm);

   554   }

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

   557   SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>

   558   subUGraphAdaptor(const UGraph& graph,

   559                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

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

   561       (graph, nfm, efm);

   562   }

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

   565   SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>

   566   subUGraphAdaptor(const UGraph& graph,

   567                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

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

   569       (graph, nfm, efm);

   570   }

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

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

   574   subUGraphAdaptor(const UGraph& graph,

   575                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   576     return SubUGraphAdaptor<const UGraph, const NodeFilterMap,

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

   578   }

   580   /// \ingroup graph_adaptors

   581   ///

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

   583   ///

   584   ///

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

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

   587   /// the node-set

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

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

   590   /// filter only isolated nodes.

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

   592   class NodeSubUGraphAdaptor :

   593     public SubUGraphAdaptor<_UGraph, NodeFilterMap,

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

   595   public:

   596     typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,

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

   598     typedef _UGraph Graph;

   599   protected:

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

   601   public:

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

   603       Parent(), const_true_map(true) {

   604       Parent::setGraph(_graph);

   605       Parent::setNodeFilterMap(_node_filter_map);

   606       Parent::setUEdgeFilterMap(const_true_map);

   607     }

   608   };

   610   template<typename UGraph, typename NodeFilterMap>

   611   NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>

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

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

   614   }

   616   template<typename UGraph, typename NodeFilterMap>

   617   NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>

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

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

   620   }

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

   624   ///

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

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

   627   ///

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

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

   630   /// only the edge-set

   631   /// can be filtered.

   632   template<typename _UGraph, typename UEdgeFilterMap>

   633   class EdgeSubUGraphAdaptor :

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

   635                             UEdgeFilterMap, false> {

   636   public:

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

   638                              UEdgeFilterMap, false> Parent;

   639     typedef _UGraph Graph;

   640   protected:

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

   642   public:

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

   644       Parent(), const_true_map(true) {

   645       Parent::setGraph(_graph);

   646       Parent::setNodeFilterMap(const_true_map);

   647       Parent::setUEdgeFilterMap(_uedge_filter_map);

   648     }

   649   };

   651   template<typename UGraph, typename EdgeFilterMap>

   652   EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>

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

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

   655   }

   657   template<typename UGraph, typename EdgeFilterMap>

   658   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>

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

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

   661   }

   663   template <typename _UGraph, typename _DirectionMap>

   664   class DirUGraphAdaptorBase {

   665   public:

   667     typedef _UGraph Graph;

   668     typedef _DirectionMap DirectionMap;

   670     typedef typename _UGraph::Node Node;

   671     typedef typename _UGraph::UEdge Edge;

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

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

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

   676       bool d;

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

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

   679     }

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

   681       bool d;

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

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

   684     }

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

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

   688     void nextIn(Edge& i) const {

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

   690       graph->nextInc(i, d);

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

   692     }

   693     void nextOut(Edge& i) const {

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

   695       graph->nextInc(i, d);

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

   697     }

   699     Node source(const Edge& e) const {

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

   701     }

   702     Node target(const Edge& e) const {

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

   704     }

   706     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

   709     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

   712     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

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

   714 		  const Edge& prev = INVALID) {

   715       Edge edge = prev;

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

   717       if (d) {

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

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

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

   721         }

   722         if (edge != INVALID) return edge;

   723       }

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

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

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

   727       }

   728       return edge;

   729     }

   731     Node addNode() const {

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

   733     }

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

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

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

   738       return edge;

   739     }

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

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

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

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

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

   749     void reverseEdge(const Edge& edge) {

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

   751     }

   753     template <typename _Value>

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

   755     public:

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

   757       explicit NodeMap(const DirUGraphAdaptorBase& ga)

   758 	: Parent(*ga.graph) { }

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

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

   761     };

   763     template <typename _Value>

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

   765     public:

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

   767       explicit EdgeMap(const DirUGraphAdaptorBase& ga)

   768 	: Parent(*ga.graph) { }

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

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

   771     };

   775   protected:

   776     Graph* graph;

   777     DirectionMap* direction;

   779     void setDirectionMap(DirectionMap& _direction) {

   780       direction = &_direction;

   781     }

   783     void setGraph(Graph& _graph) {

   784       graph = &_graph;

   785     }

   787   };

   790   /// \ingroup graph_adaptors

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

   792   ///

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

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

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

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

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

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

   799   template<typename _Graph,

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

   801   class DirUGraphAdaptor :

   802     public GraphAdaptorExtender<

   803     DirUGraphAdaptorBase<_Graph, DirectionMap> > {

   804   public:

   805     typedef _Graph Graph;

   806     typedef GraphAdaptorExtender<

   807       DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;

   808   protected:

   809     DirUGraphAdaptor() { }

   810   public:

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

   812       setGraph(_graph);

   813       setDirectionMap(_direction_map);

   814     }

   815   };

   817   template<typename UGraph, typename DirectionMap>

   818   DirUGraphAdaptor<const UGraph, DirectionMap>

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

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

   821   }

   823   template<typename UGraph, typename DirectionMap>

   824   DirUGraphAdaptor<const UGraph, const DirectionMap>

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

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

   827   }

   829 }

   831 #endif

author	deba
	Mon, 27 Feb 2006 10:36:01 +0000
changeset 1986	9b56cca61e2e
parent 1980	a954b780e3ab
child 1991	d7442141d9ef
permissions	-rw-r--r--