lemon-0.x: lemon/ugraph_adaptor.h@e866e288cba6

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

     2  *

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

     4  *

     5  * Copyright (C) 2003-2008

     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   /// \brief Base type for the Graph Adaptors

    42   ///

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

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

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

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

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

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

    49   /// the differences should be implemented.

    50   ///

    51   /// \author Balazs Dezso

    52   template<typename _UGraph>

    53   class UGraphAdaptorBase {

    54   public:

    55     typedef _UGraph Graph;

    56     typedef Graph ParentGraph;

    58   protected:

    59     Graph* graph;

    61     UGraphAdaptorBase() : graph(0) {}

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

    65   public:

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

    68     typedef typename Graph::Node Node;

    69     typedef typename Graph::Edge Edge;

    70     typedef typename Graph::UEdge UEdge;

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

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

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

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

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

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

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

    79     }

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

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

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

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

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

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

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

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

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

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

    94     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

    97     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

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

   101     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

   102     Edge findEdge(const Node& u, const Node& v,

   103 		  const Edge& prev = INVALID) {

   104       return graph->findEdge(u, v, prev);

   105     }

   106     UEdge findUEdge(const Node& u, const Node& v,

   107                     const UEdge& prev = INVALID) {

   108       return graph->findUEdge(u, v, prev);

   109     }

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

   112     UEdge addEdge(const Node& u, const Node& v) const {

   113       return graph->addEdge(u, v);

   114     }

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

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

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

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

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

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

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

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

   128     Node fromNodeId(int ix) const {

   129       return graph->fromNodeId(ix);

   130     }

   132     Edge fromEdgeId(int ix) const {

   133       return graph->fromEdgeId(ix);

   134     }

   136     UEdge fromUEdgeId(int ix) const {

   137       return graph->fromUEdgeId(ix);

   138     }

   140     int maxNodeId() const {

   141       return graph->maxNodeId();

   142     }

   144     int maxEdgeId() const {

   145       return graph->maxEdgeId();

   146     }

   148     int maxUEdgeId() const {

   149       return graph->maxEdgeId();

   150     }

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

   154     NodeNotifier& notifier(Node) const {

   155       return graph->notifier(Node());

   156     }

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

   160     EdgeNotifier& notifier(Edge) const {

   161       return graph->notifier(Edge());

   162     }

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

   166     UEdgeNotifier& notifier(UEdge) const {

   167       return graph->notifier(UEdge());

   168     }

   170     template <typename _Value>

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

   172     public:

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

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

   175 	: Parent(*ga.graph) {}

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

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

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

   180 	return operator=<NodeMap>(cmap);

   181       }

   183       template <typename CMap>

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

   185         Parent::operator=(cmap);

   186         return *this;

   187       }

   189     };

   191     template <typename _Value>

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

   193     public:

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

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

   196 	: Parent(*ga.graph) {}

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

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

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

   201 	return operator=<EdgeMap>(cmap);

   202       }

   204       template <typename CMap>

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

   206         Parent::operator=(cmap);

   207 	return *this;

   208       }

   209     };

   211     template <typename _Value>

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

   213     public:

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

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

   216 	: Parent(*ga.graph) {}

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

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

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

   221 	return operator=<UEdgeMap>(cmap);

   222       }

   224       template <typename CMap>

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

   226         Parent::operator=(cmap);

   227         return *this;

   228       }

   229     };

   231   };

   233   /// \ingroup graph_adaptors

   234   ///

   235   /// \brief Trivial undirected graph adaptor

   236   ///

   237   /// This class is an adaptor which does not change the adapted undirected

   238   /// graph. It can be used only to test the undirected 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::source(i)]

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

   316     }

   318     void next(Node& i) const {

   319       Parent::next(i);

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

   321     }

   323     void next(Edge& i) const {

   324       Parent::next(i);

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

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

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

   328     }

   330     void next(UEdge& i) const {

   331       Parent::next(i);

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

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

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

   335     }

   337     void nextIn(Edge& i) const {

   338       Parent::nextIn(i);

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

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

   341     }

   343     void nextOut(Edge& i) const {

   344       Parent::nextOut(i);

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

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

   347     }

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

   350       Parent::nextInc(i, d);

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

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

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

   354     }

   356     /// \brief Hide the given node in the graph.

   357     ///

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

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

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

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

   363     /// \brief Hide the given undirected edge in the graph.

   364     ///

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

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

   367     /// to be false in the corresponding uedge-map.

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

   370     /// \brief Unhide the given node in the graph.

   371     ///

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

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

   374     /// again

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

   377     /// \brief Hide the given undirected edge in the graph.

   378     ///

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

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

   381     /// again

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

   384     /// \brief Returns true if \c n is hidden.

   385     ///

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

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

   389     /// \brief Returns true if \c e is hidden.

   390     ///

   391     /// Returns true if \c e is hidden.

   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& u, const Node& v,

   399 		  const Edge& prev = INVALID) {

   400       if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {

   401         return INVALID;

   402       }

   403       Edge edge = Parent::findEdge(u, v, prev);

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

   405         edge = Parent::findEdge(u, v, edge);

   406       }

   407       return edge;

   408     }

   409     UEdge findUEdge(const Node& u, const Node& v,

   410 		  const UEdge& prev = INVALID) {

   411       if (!(*node_filter_map)[u] || !(*node_filter_map)[v]) {

   412         return INVALID;

   413       }

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

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

   416         uedge = Parent::findUEdge(u, v, 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& g)

   432 	: Parent(g) {}

   433       NodeMap(const Graph& g, const _Value& v)

   434 	: Parent(g, v) {}

   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& g)

   458 	: Parent(g) {}

   459       EdgeMap(const Graph& g, const _Value& v)

   460 	: Parent(g, v) {}

   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& g)

   484 	: Parent(g) {}

   485       UEdgeMap(const Graph& g, const _Value& v)

   486 	: Parent(g, v) {}

   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     /// \brief Hide the given node in the graph.

   584     ///

   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     /// \brief Hide the given undirected edge in the graph.

   591     ///

   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 uedge-map.

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

   597     /// \brief Unhide the given node in the graph.

   598     ///

   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     /// \brief Hide the given undirected edge in the graph.

   605     ///

   606     /// The value of \c e is set to be true in the uedge-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     /// \brief Returns true if \c n is hidden.

   612     ///

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

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

   616     /// \brief Returns true if \c e is hidden.

   617     ///

   618     /// Returns true if \c e is hidden.

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

   621     typedef False NodeNumTag;

   622     typedef False EdgeNumTag;

   624     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

   625     Edge findEdge(const Node& u, const Node& v,

   626 		  const Edge& prev = INVALID) {

   627       Edge edge = Parent::findEdge(u, v, prev);

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

   629         edge = Parent::findEdge(u, v, edge);

   630       }

   631       return edge;

   632     }

   633     UEdge findUEdge(const Node& u, const Node& v,

   634 		  const UEdge& prev = INVALID) {

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

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

   637         uedge = Parent::findUEdge(u, v, uedge);

   638       }

   639       return uedge;

   640     }

   642     template <typename _Value>

   643     class NodeMap

   644       : public SubMapExtender<Adaptor,

   645                               typename Parent::template NodeMap<_Value> >

   646     {

   647     public:

   648       typedef Adaptor Graph;

   649       typedef SubMapExtender<Adaptor, typename Parent::

   650                              template NodeMap<_Value> > Parent;

   652       NodeMap(const Graph& g)

   653 	: Parent(g) {}

   654       NodeMap(const Graph& g, const _Value& v)

   655 	: Parent(g, v) {}

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

   658 	return operator=<NodeMap>(cmap);

   659       }

   661       template <typename CMap>

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

   663         Parent::operator=(cmap);

   664 	return *this;

   665       }

   666     };

   668     template <typename _Value>

   669     class EdgeMap

   670       : public SubMapExtender<Adaptor,

   671                               typename Parent::template EdgeMap<_Value> >

   672     {

   673     public:

   674       typedef Adaptor Graph;

   675       typedef SubMapExtender<Adaptor, typename Parent::

   676                              template EdgeMap<_Value> > Parent;

   678       EdgeMap(const Graph& g)

   679 	: Parent(g) {}

   680       EdgeMap(const Graph& g, const _Value& v)

   681 	: Parent(g, v) {}

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

   684 	return operator=<EdgeMap>(cmap);

   685       }

   687       template <typename CMap>

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

   689         Parent::operator=(cmap);

   690 	return *this;

   691       }

   692     };

   694     template <typename _Value>

   695     class UEdgeMap

   696       : public SubMapExtender<Adaptor,

   697                               typename Parent::template UEdgeMap<_Value> >

   698     {

   699     public:

   700       typedef Adaptor Graph;

   701       typedef SubMapExtender<Adaptor, typename Parent::

   702                              template UEdgeMap<_Value> > Parent;

   704       UEdgeMap(const Graph& g)

   705 	: Parent(g) {}

   706       UEdgeMap(const Graph& g, const _Value& v)

   707 	: Parent(g, v) {}

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

   710 	return operator=<UEdgeMap>(cmap);

   711       }

   713       template <typename CMap>

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

   715         Parent::operator=(cmap);

   716 	return *this;

   717       }

   718     };

   719   };

   721   /// \ingroup graph_adaptors

   722   ///

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

   724   /// graph.

   725   ///

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

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

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

   729   ///

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

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

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

   733   /// This way the edge-map

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

   735   /// node-filter.

   736   ///

   737   template<typename _UGraph, typename NodeFilterMap,

   738 	   typename UEdgeFilterMap, bool checked = true>

   739   class SubUGraphAdaptor :

   740     public UGraphAdaptorExtender<

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

   742   public:

   743     typedef _UGraph Graph;

   744     typedef UGraphAdaptorExtender<

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

   746   protected:

   747     SubUGraphAdaptor() { }

   748   public:

   749     SubUGraphAdaptor(Graph& _graph, NodeFilterMap& _node_filter_map,

   750 		    UEdgeFilterMap& _uedge_filter_map) {

   751       setGraph(_graph);

   752       setNodeFilterMap(_node_filter_map);

   753       setUEdgeFilterMap(_uedge_filter_map);

   754     }

   755   };

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

   758   SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>

   759   subUGraphAdaptor(const UGraph& graph,

   760                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   761     return SubUGraphAdaptor<const UGraph, NodeFilterMap, EdgeFilterMap>

   762       (graph, nfm, efm);

   763   }

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

   766   SubUGraphAdaptor<const UGraph, const NodeFilterMap, EdgeFilterMap>

   767   subUGraphAdaptor(const UGraph& graph,

   768                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

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

   770       (graph, nfm, efm);

   771   }

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

   774   SubUGraphAdaptor<const UGraph, NodeFilterMap, const EdgeFilterMap>

   775   subUGraphAdaptor(const UGraph& graph,

   776                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

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

   778       (graph, nfm, efm);

   779   }

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

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

   783   subUGraphAdaptor(const UGraph& graph,

   784                    NodeFilterMap& nfm, EdgeFilterMap& efm) {

   785     return SubUGraphAdaptor<const UGraph, const NodeFilterMap,

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

   787   }

   789   /// \ingroup graph_adaptors

   790   ///

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

   792   ///

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

   794   /// adaptor specializes SubUGraphAdaptor in the way that only the

   795   /// node-set can be filtered. In usual case the checked parameter is

   796   /// true, we get the induced subgraph. But if the checked parameter

   797   /// is false then we can filter only isolated nodes.

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

   799   class NodeSubUGraphAdaptor :

   800     public SubUGraphAdaptor<_UGraph, NodeFilterMap,

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

   802   public:

   803     typedef SubUGraphAdaptor<_UGraph, NodeFilterMap,

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

   805     typedef _UGraph Graph;

   806   protected:

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

   809     NodeSubUGraphAdaptor() : const_true_map(true) {

   810       Parent::setUEdgeFilterMap(const_true_map);

   811     }

   813   public:

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

   815       Parent(), const_true_map(true) {

   816       Parent::setGraph(_graph);

   817       Parent::setNodeFilterMap(_node_filter_map);

   818       Parent::setUEdgeFilterMap(const_true_map);

   819     }

   820   };

   822   template<typename UGraph, typename NodeFilterMap>

   823   NodeSubUGraphAdaptor<const UGraph, NodeFilterMap>

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

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

   826   }

   828   template<typename UGraph, typename NodeFilterMap>

   829   NodeSubUGraphAdaptor<const UGraph, const NodeFilterMap>

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

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

   832   }

   834   /// \ingroup graph_adaptors

   835   ///

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

   837   ///

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

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

   840   ///

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

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

   843   /// only the edge-set

   844   /// can be filtered.

   845   template<typename _UGraph, typename UEdgeFilterMap>

   846   class EdgeSubUGraphAdaptor :

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

   848                             UEdgeFilterMap, false> {

   849   public:

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

   851                              UEdgeFilterMap, false> Parent;

   852     typedef _UGraph Graph;

   853   protected:

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

   856     EdgeSubUGraphAdaptor() : const_true_map(true) {

   857       Parent::setNodeFilterMap(const_true_map);

   858     }

   860   public:

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

   863       Parent(), const_true_map(true) {

   864       Parent::setGraph(_graph);

   865       Parent::setNodeFilterMap(const_true_map);

   866       Parent::setUEdgeFilterMap(_uedge_filter_map);

   867     }

   869   };

   871   template<typename UGraph, typename EdgeFilterMap>

   872   EdgeSubUGraphAdaptor<const UGraph, EdgeFilterMap>

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

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

   875   }

   877   template<typename UGraph, typename EdgeFilterMap>

   878   EdgeSubUGraphAdaptor<const UGraph, const EdgeFilterMap>

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

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

   881   }

   883   /// \brief Base of direct undirected graph adaptor

   884   ///

   885   /// Base class of the direct undirected graph adaptor. All public member

   886   /// of this class can be used with the DirUGraphAdaptor too.

   887   /// \sa DirUGraphAdaptor

   888   template <typename _UGraph, typename _DirectionMap>

   889   class DirUGraphAdaptorBase {

   890   public:

   892     typedef _UGraph Graph;

   893     typedef _DirectionMap DirectionMap;

   895     typedef typename _UGraph::Node Node;

   896     typedef typename _UGraph::UEdge Edge;

   898     /// \brief Reverse edge

   899     ///

   900     /// It reverse the given edge. It simply negate the direction in the map.

   901     void reverseEdge(const Edge& edge) {

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

   903     }

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

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

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

   908       bool d;

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

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

   911     }

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

   913       bool d;

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

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

   916     }

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

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

   920     void nextIn(Edge& i) const {

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

   922       graph->nextInc(i, d);

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

   924     }

   925     void nextOut(Edge& i) const {

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

   927       graph->nextInc(i, d);

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

   929     }

   931     Node source(const Edge& e) const {

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

   933     }

   934     Node target(const Edge& e) const {

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

   936     }

   938     typedef NodeNumTagIndicator<Graph> NodeNumTag;

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

   941     typedef EdgeNumTagIndicator<Graph> EdgeNumTag;

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

   944     typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

   945     Edge findEdge(const Node& u, const Node& v,

   946 		  const Edge& prev = INVALID) {

   947       Edge edge = prev;

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

   949       if (d) {

   950         edge = graph->findUEdge(u, v, edge);

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

   952           graph->findUEdge(u, v, edge);

   953         }

   954         if (edge != INVALID) return edge;

   955       }

   956       graph->findUEdge(v, u, edge);

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

   958         graph->findUEdge(u, v, edge);

   959       }

   960       return edge;

   961     }

   963     Node addNode() const {

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

   965     }

   967     Edge addEdge(const Node& u, const Node& v) const {

   968       Edge edge = graph->addEdge(u, v);

   969       direction->set(edge, graph->source(edge) == u);

   970       return edge;

   971     }

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

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

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

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

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

   981     int maxNodeId() const {

   982       return graph->maxNodeId();

   983     }

   985     int maxEdgeId() const {

   986       return graph->maxEdgeId();

   987     }

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

   991     NodeNotifier& notifier(Node) const {

   992       return graph->notifier(Node());

   993     }

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

   997     EdgeNotifier& notifier(Edge) const {

   998       return graph->notifier(Edge());

   999     }

  1001     template <typename _Value>

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

  1003     public:

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

  1007       explicit NodeMap(const DirUGraphAdaptorBase& ga)

  1008 	: Parent(*ga.graph) {}

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

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

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

  1014         return operator=<NodeMap>(cmap);

  1015       }

  1017       template <typename CMap>

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

  1019         Parent::operator=(cmap);

  1020         return *this;

  1021       }

  1023     };

  1025     template <typename _Value>

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

  1027     public:

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

  1031       explicit EdgeMap(const DirUGraphAdaptorBase& ga)

  1032 	: Parent(*ga.graph) { }

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

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

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

  1038         return operator=<EdgeMap>(cmap);

  1039       }

  1041       template <typename CMap>

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

  1043         Parent::operator=(cmap);

  1044         return *this;

  1045       }

  1046     };

  1050   protected:

  1051     Graph* graph;

  1052     DirectionMap* direction;

  1054     void setDirectionMap(DirectionMap& _direction) {

  1055       direction = &_direction;

  1056     }

  1058     void setGraph(Graph& _graph) {

  1059       graph = &_graph;

  1060     }

  1062   };

  1065   /// \ingroup graph_adaptors

  1066   ///

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

  1068   ///

  1069   /// This adaptor gives a direction for each uedge in the undirected

  1070   /// graph. The direction of the edges stored in the

  1071   /// DirectionMap. This map is a bool map on the undirected edges. If

  1072   /// the uedge is mapped to true then the direction of the directed

  1073   /// edge will be the same as the default direction of the uedge. The

  1074   /// edges can be easily reverted by the \ref

  1075   /// DirUGraphAdaptorBase::reverseEdge "reverseEdge()" member in the

  1076   /// adaptor.

  1077   ///

  1078   /// It can be used to solve orientation problems on directed graphs.

  1079   /// By example how can we orient an undirected graph to get the minimum

  1080   /// number of strongly connected components. If we orient the edges with

  1081   /// the dfs algorithm out from the source then we will get such an

  1082   /// orientation.

  1083   ///

  1084   /// We use the \ref DfsVisitor "visitor" interface of the

  1085   /// \ref DfsVisit "dfs" algorithm:

  1086   ///\code

  1087   /// template <typename DirMap>

  1088   /// class OrientVisitor : public DfsVisitor<UGraph> {

  1089   /// public:

  1090   ///

  1091   ///   OrientVisitor(const UGraph& ugraph, DirMap& dirMap)

  1092   ///     : _ugraph(ugraph), _dirMap(dirMap), _processed(ugraph, false) {}

  1093   ///

  1094   ///   void discover(const Edge& edge) {

  1095   ///     _processed.set(edge, true);

  1096   ///     _dirMap.set(edge, _ugraph.direction(edge));

  1097   ///   }

  1098   ///

  1099   ///   void examine(const Edge& edge) {

  1100   ///     if (_processed[edge]) return;

  1101   ///     _processed.set(edge, true);

  1102   ///     _dirMap.set(edge, _ugraph.direction(edge));

  1103   ///   }

  1104   ///

  1105   /// private:

  1106   ///   const UGraph& _ugraph;

  1107   ///   DirMap& _dirMap;

  1108   ///   UGraph::UEdgeMap<bool> _processed;

  1109   /// };

  1110   ///\endcode

  1111   ///

  1112   /// And now we can use the orientation:

  1113   ///\code

  1114   /// UGraph::UEdgeMap<bool> dmap(ugraph);

  1115   ///

  1116   /// typedef OrientVisitor<UGraph::UEdgeMap<bool> > Visitor;

  1117   /// Visitor visitor(ugraph, dmap);

  1118   ///

  1119   /// DfsVisit<UGraph, Visitor> dfs(ugraph, visitor);

  1120   ///

  1121   /// dfs.run();

  1122   ///

  1123   /// typedef DirUGraphAdaptor<UGraph> DGraph;

  1124   /// DGraph dgraph(ugraph, dmap);

  1125   ///

  1126   /// LEMON_ASSERT(countStronglyConnectedComponents(dgraph) ==

  1127   ///              countBiEdgeConnectedComponents(ugraph), "Wrong Orientation");

  1128   ///\endcode

  1129   ///

  1130   /// The number of the bi-connected components is a lower bound for

  1131   /// the number of the strongly connected components in the directed

  1132   /// graph because if we contract the bi-connected components to

  1133   /// nodes we will get a tree therefore we cannot orient edges in

  1134   /// both direction between bi-connected components. In the other way

  1135   /// the algorithm will orient one component to be strongly

  1136   /// connected. The two relations proof that the assertion will

  1137   /// be always true and the found solution is optimal.

  1138   ///

  1139   /// \sa DirUGraphAdaptorBase

  1140   /// \sa dirUGraphAdaptor

  1141   template<typename _Graph,

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

  1143   class DirUGraphAdaptor :

  1144     public GraphAdaptorExtender<

  1145     DirUGraphAdaptorBase<_Graph, DirectionMap> > {

  1146   public:

  1147     typedef _Graph Graph;

  1148     typedef GraphAdaptorExtender<

  1149       DirUGraphAdaptorBase<_Graph, DirectionMap> > Parent;

  1150   protected:

  1151     DirUGraphAdaptor() { }

  1152   public:

  1154     /// \brief Constructor of the adaptor

  1155     ///

  1156     /// Constructor of the adaptor

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

  1158       setGraph(_graph);

  1159       setDirectionMap(_direction_map);

  1160     }

  1161   };

  1163   /// \brief Just gives back a DirUGraphAdaptor

  1164   ///

  1165   /// Just gives back a DirUGraphAdaptor

  1166   template<typename UGraph, typename DirectionMap>

  1167   DirUGraphAdaptor<const UGraph, DirectionMap>

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

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

  1170   }

  1172   template<typename UGraph, typename DirectionMap>

  1173   DirUGraphAdaptor<const UGraph, const DirectionMap>

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

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

  1176   }

  1178 }

  1180 #endif

author	kpeter
	Mon, 18 Feb 2008 03:32:06 +0000
changeset 2575	e866e288cba6
parent 2422	77ed2b97abbd
child 2617	5222a3c470ed
permissions	-rw-r--r--