RhodeCode

 * express or implied, and with no claim as to its suitability for any

 * purpose.

 *

 */

#ifndef LEMON_DIGRAPH_ADAPTOR_H

#define LEMON_DIGRAPH_ADAPTOR_H

///\ingroup graph_adaptors

///\file

///\brief Several digraph adaptors.

///

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/bits/variant.h>

#include <lemon/bits/base_extender.h>

#include <lemon/bits/graph_adaptor_extender.h>

#include <lemon/bits/graph_extender.h>

#include <lemon/tolerance.h>

#include <algorithm>

namespace lemon {

  template<typename _Digraph>

  class DigraphAdaptorBase {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase Adaptor;

    typedef Digraph ParentDigraph;

  protected:

    Digraph* _digraph;

    DigraphAdaptorBase() : _digraph(0) { }

    void setDigraph(Digraph& digraph) { _digraph = &digraph; }

      }

      template <typename CMap>

      ArcMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  template <typename _Digraph>

  class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase<_Digraph> Parent;

  protected:

    RevDigraphAdaptorBase() : Parent() { }

  public:

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

      return Parent::findArc(v, u, prev);

    }

  };

  ///\ingroup graph_adaptors

  ///

  ///\brief A digraph adaptor which reverses the orientation of the arcs.

  ///

  /// If \c g is defined as

  ///\code

  ///\endcode

  /// then

  ///\code

  ///\endcode

  /// reversing the orientation of its arcs.

  ///

  ///

  ///\code

  /// bool stronglyConnected(const Digraph& digraph) {

  ///   if (NodeIt(digraph) == INVALID) return true;

  ///   Dfs<Digraph> dfs(digraph);

  ///   dfs.run(NodeIt(digraph));

  ///   for (NodeIt it(digraph); it != INVALID; ++it) {

  ///     if (!dfs.reached(it)) {

  ///       return false;

  ///     }

  ///   }

  ///   typedef RevDigraphAdaptor<const Digraph> RDigraph;

  ///   RDigraph rdigraph(digraph);

  /// }

  ///\endcode

  template<typename _Digraph>

  class RevDigraphAdaptor : 

    public DigraphAdaptorExtender<RevDigraphAdaptorBase<_Digraph> > {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorExtender<

      RevDigraphAdaptorBase<_Digraph> > Parent;

  protected:

    RevDigraphAdaptor() { }

  public:

    explicit RevDigraphAdaptor(Digraph& digraph) { 

      Parent::setDigraph(digraph); 

    }

  };

  /// \brief Just gives back a reverse digraph adaptor

  ///

  /// Just gives back a reverse digraph adaptor

  template<typename Digraph>

  RevDigraphAdaptor<const Digraph>

  revDigraphAdaptor(const Digraph& digraph) {

    return RevDigraphAdaptor<const Digraph>(digraph);

    void nextIn(Arc& i) const { 

      Parent::nextIn(i); 

      while (i != INVALID && (!(*_arc_filter)[i] 

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

    }

    void nextOut(Arc& i) const { 

      Parent::nextOut(i); 

      while (i != INVALID && (!(*_arc_filter)[i] 

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

    }

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

    void hide(const Arc& a) const { _arc_filter->set(a, false); }

    void unHide(const Arc& a) const { _arc_filter->set(a, true); }

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

    bool hidden(const Arc& a) const { return !(*_arc_filter)[a]; }

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;

    Arc findArc(const Node& source, const Node& target, 

		const Arc& prev = INVALID) {

      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

        return INVALID;

      }

      Arc arc = Parent::findArc(source, target, prev);

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

    }

    void nextIn(Arc& i) const { 

      Parent::nextIn(i); 

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

    }

    void nextOut(Arc& i) const { 

      Parent::nextOut(i); 

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

    }

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

    void hide(const Arc& e) const { _arc_filter->set(e, false); }

    void unHide(const Arc& e) const { _arc_filter->set(e, true); }

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

    bool hidden(const Arc& e) const { return !(*_arc_filter)[e]; }

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

    typedef FindEdgeTagIndicator<Digraph> FindEdgeTag;

    Arc findArc(const Node& source, const Node& target, 

		  const Arc& prev = INVALID) {

      if (!(*_node_filter)[source] || !(*_node_filter)[target]) {

        return INVALID;

      }

      Arc arc = Parent::findArc(source, target, prev);

        MapParent::operator=(cmap);

	return *this;

      }

    };

  };

  /// \ingroup graph_adaptors

  ///

  /// \brief A digraph adaptor for hiding nodes and arcs from a digraph.

  /// 

  /// SubDigraphAdaptor shows the digraph with filtered node-set and 

  /// 

  ///\code

  /// typedef ListDigraph Digraph;

  /// DIGRAPH_TYPEDEFS(Digraph);

  /// Digraph g;

  /// Node u=g.addNode(); //node of id 0

  /// Node v=g.addNode(); //node of id 1

  /// Arc a=g.addArc(u, v); //arc of id 0

  /// Arc f=g.addArc(v, u); //arc of id 1

  /// BoolNodeMap nm(g, true);

  /// nm.set(u, false);

  /// BoolArcMap am(g, true);

  /// am.set(a, false);

  ///   std::cout << g.id(n) << std::endl;

  ///   std::cout << g.id(a) << std::endl;

  ///\endcode

  /// The output of the above code is the following.

  ///\code

  /// 1

  /// 1

  ///\endcode

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

  /// 

  /// For other examples see also the documentation of

  /// NodeSubDigraphAdaptor and ArcSubDigraphAdaptor.

  template<typename _Digraph, 

	   typename _NodeFilterMap = typename _Digraph::template NodeMap<bool>, 

	   typename _ArcFilterMap = typename _Digraph::template ArcMap<bool>, 

	   bool checked = true>

  class SubDigraphAdaptor : 

    public DigraphAdaptorExtender<

    SubDigraphAdaptorBase<_Digraph, _NodeFilterMap, _ArcFilterMap, checked> > {

  public:

    typedef _Digraph Digraph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef _ArcFilterMap ArcFilterMap;

    typedef DigraphAdaptorExtender<

      SubDigraphAdaptorBase<Digraph, NodeFilterMap, ArcFilterMap, checked> >

    Parent;

  protected:

    SubDigraphAdaptor() { }

  public:

    SubDigraphAdaptor(Digraph& digraph, NodeFilterMap& node_filter, 

		      ArcFilterMap& arc_filter) { 

      setDigraph(digraph);

      setNodeFilterMap(node_filter);

      setArcFilterMap(arc_filter);

    }

  };

  ///

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>

  subDigraphAdaptor(const Digraph& digraph, 

		    NodeFilterMap& nfm, ArcFilterMap& afm) {

    return SubDigraphAdaptor<const Digraph, NodeFilterMap, ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraphAdaptor<const Digraph, const NodeFilterMap, ArcFilterMap>

  subDigraphAdaptor(const Digraph& digraph, 

                   NodeFilterMap& nfm, ArcFilterMap& afm) {

  subDigraphAdaptor(const Digraph& digraph, 

                   NodeFilterMap& nfm, ArcFilterMap& afm) {

    return SubDigraphAdaptor<const Digraph, NodeFilterMap, const ArcFilterMap>

      (digraph, nfm, afm);

  }

  template<typename Digraph, typename NodeFilterMap, typename ArcFilterMap>

  SubDigraphAdaptor<const Digraph, const NodeFilterMap, const ArcFilterMap>

  subDigraphAdaptor(const Digraph& digraph, 

                   NodeFilterMap& nfm, ArcFilterMap& afm) {

    return SubDigraphAdaptor<const Digraph, const NodeFilterMap, 

      const ArcFilterMap>(digraph, nfm, afm);

  }

  ///\ingroup graph_adaptors

  ///

  ///\brief An adaptor for hiding nodes from a digraph.

  ///

  ///An adaptor for hiding nodes from a digraph.  This adaptor

  ///specializes SubDigraphAdaptor in the way that only the node-set

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

  ///get the induced subgraph. But if the checked parameter is false

  class NodeSubDigraphAdaptor : 

    public SubDigraphAdaptor<_Digraph, _NodeFilterMap, 

			     ConstMap<typename _Digraph::Arc, bool>, checked> {

  public:

    typedef _Digraph Digraph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef SubDigraphAdaptor<Digraph, NodeFilterMap, 

			      ConstMap<typename Digraph::Arc, bool>, checked> 

    Parent;

  protected:

    ConstMap<typename Digraph::Arc, bool> const_true_map;

    NodeSubDigraphAdaptor() : const_true_map(true) {

      Parent::setArcFilterMap(const_true_map);

    }

  public:

    NodeSubDigraphAdaptor(Digraph& _digraph, NodeFilterMap& node_filter) : 

      Parent(), const_true_map(true) { 

      Parent::setDigraph(_digraph);

      Parent::setNodeFilterMap(node_filter);

      Parent::setArcFilterMap(const_true_map);

    }

  };

  ///

  template<typename Digraph, typename NodeFilterMap>

  NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>

  nodeSubDigraphAdaptor(const Digraph& digraph, NodeFilterMap& nfm) {

    return NodeSubDigraphAdaptor<const Digraph, NodeFilterMap>(digraph, nfm);

  }

  template<typename Digraph, typename NodeFilterMap>

  NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>

  nodeSubDigraphAdaptor(const Digraph& digraph, const NodeFilterMap& nfm) {

    return NodeSubDigraphAdaptor<const Digraph, const NodeFilterMap>

      (digraph, nfm);

  }

  ///\ingroup graph_adaptors

  ///

  ///\brief An adaptor for hiding arcs from a digraph.

  ///

  ///An adaptor for hiding arcs from a digraph. This adaptor

  ///specializes SubDigraphAdaptor in the way that only the arc-set

  ///can be filtered. The usefulness of this adaptor is demonstrated

  ///in the problem of searching a maximum number of arc-disjoint

  ///shortest paths between two nodes \c s and \c t. Shortest here

  ///

  ///If a single shortest path is to be searched between \c s and \c

  ///t, then this can be done easily by applying the Dijkstra

  ///algorithm. What happens, if a maximum number of arc-disjoint

  ///shortest paths is to be computed. It can be proved that an arc

  ///can be in a shortest path if and only if it is tight with respect

  ///to the potential function computed by Dijkstra.  Moreover, any

  ///path containing only such arcs is a shortest one.  Thus we have

  ///to compute a maximum number of arc-disjoint paths between \c s

  ///and \c t in the digraph which has arc-set all the tight arcs. The

  ///computation will be demonstrated on the following digraph, which

  ///is read from the dimacs file \c sub_digraph_adaptor_demo.dim.

  ///The full source code is available in \ref

  ///sub_digraph_adaptor_demo.cc.  If you are interested in more demo

  ///programs, you can use \ref dim_to_dot.cc to generate .dot files

  ///from dimacs files.  The .dot file of the following figure was

  ///generated by the demo program \ref dim_to_dot.cc.

  ///

  ///\dot

  ///node [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

  ///n0 [ label="0 (s)" ];

  ///n1 [ label="1" ];

  ///n2 [ label="2" ];

  ///n3 [ label="3" ];

  ///n4 [ label="4" ];

  ///n5 [ label="5" ];

  ///n6 [ label="6 (t)" ];

  ///arc [ shape=ellipse, fontname=Helvetica, fontsize=10 ];

  ///n5 ->  n6 [ label="9, length:4" ];

  ///n4 ->  n6 [ label="8, length:2" ];

  ///n3 ->  n5 [ label="7, length:1" ];

  /// 1, 0--2->2

  ///\endcode

  template<typename _Digraph, typename _ArcFilterMap>

  class ArcSubDigraphAdaptor : 

    public SubDigraphAdaptor<_Digraph, ConstMap<typename _Digraph::Node, bool>, 

			     _ArcFilterMap, false> {

  public:

    typedef _Digraph Digraph;

    typedef _ArcFilterMap ArcFilterMap;

    typedef SubDigraphAdaptor<Digraph, ConstMap<typename Digraph::Node, bool>, 

			      ArcFilterMap, false> Parent;

  protected:

    ConstMap<typename Digraph::Node, bool> const_true_map;

    ArcSubDigraphAdaptor() : const_true_map(true) {

      Parent::setNodeFilterMap(const_true_map);

    }

  public:

    ArcSubDigraphAdaptor(Digraph& digraph, ArcFilterMap& arc_filter) 

      : Parent(), const_true_map(true) { 

      Parent::setDigraph(digraph);

      Parent::setNodeFilterMap(const_true_map);

      Parent::setArcFilterMap(arc_filter);

    }

  };

  ///

  template<typename Digraph, typename ArcFilterMap>

  ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>

  arcSubDigraphAdaptor(const Digraph& digraph, ArcFilterMap& afm) {

    return ArcSubDigraphAdaptor<const Digraph, ArcFilterMap>(digraph, afm);

  }

  template<typename Digraph, typename ArcFilterMap>

  ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>

  arcSubDigraphAdaptor(const Digraph& digraph, const ArcFilterMap& afm) {

    return ArcSubDigraphAdaptor<const Digraph, const ArcFilterMap>

      (digraph, afm);

  }

    UndirDigraphAdaptorBase() : _digraph(0) {}

    Digraph* _digraph;

    void setDigraph(Digraph& digraph) {

      _digraph = &digraph;

    }

  };

  ///\ingroup graph_adaptors

  ///

  ///

  /// This adaptor makes an undirected graph from a directed

  ///

  /// There is a network of the streets of a town. Of course there are

  /// some one-way street in the town hence the network is a directed

  /// one. There is a crazy driver who go oppositely in the one-way

  /// street without moral sense. Of course he can pass this streets

  /// slower than the regular way, in fact his speed is half of the

  /// normal speed. How long should he drive to get from a source

  /// point to the target? Let see the example code which calculate it:

  ///

  /// \todo BadCode, SimpleMap does no exists

  ///\code

  /// typedef UndirDigraphAdaptor<Digraph> Graph;

      typedef typename _CapacityMap::Value Value;

      ResCap(const Adaptor& adaptor) : _adaptor(&adaptor) {}

      Value operator[](const Arc& e) const {

        return _adaptor->rescap(e);

      }

    };

  };

  template <typename _Digraph>

  class SplitDigraphAdaptorBase {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase<const _Digraph> Parent;

    typedef SplitDigraphAdaptorBase Adaptor;

    typedef typename Digraph::Node DigraphNode;

    typedef typename Digraph::Arc DigraphArc;

    class Node;

    Arc arcFromId(int ix) const {

      if ((ix & 1) == 0) {

        return Arc(_digraph->arcFromId(ix >> 1));

      } else {

        return Arc(_digraph->nodeFromId(ix >> 1));

      }

    }

    int maxArcId() const {

      return std::max(_digraph->maxNodeId() << 1, 

                      (_digraph->maxArcId() << 1) | 1);

    }

    static bool inNode(const Node& n) {

      return n._in;

    }

    static bool outNode(const Node& n) {

      return !n._in;

    }

    static bool origArc(const Arc& e) {

      return e._item.firstState();

    }

    static bool bindArc(const Arc& e) {

      return e._item.secondState();

    }

    static Node inNode(const DigraphNode& n) {

      return Node(n, true);

    }

    static Node outNode(const DigraphNode& n) {

      return Node(n, false);

    }

    static Arc arc(const DigraphNode& n) {

      return Arc(n);

    }

    static Arc arc(const DigraphArc& e) {

      return Arc(e);

    }

    typedef True NodeNumTag;

    int nodeNum() const {

      return  2 * countNodes(*_digraph);

    }

    typedef True EdgeNumTag;

    int arcNum() const {

  /// \f$ u_{out} \f$ node. If there is an \f$ (v, u) \f$ arc in the 

  /// original digraph the new target of the arc will be \f$ u_{in} \f$ and

  /// similarly the source of the original \f$ (u, v) \f$ arc will be

  /// \f$ u_{out} \f$.  The adaptor will add for each node in the 

  /// original digraph an additional arc which will connect 

  /// \f$ (u_{in}, u_{out}) \f$.

  ///

  /// The aim of this class is to run algorithm with node costs if the 

  /// algorithm can use directly just arc costs. In this case we should use

  /// a \c SplitDigraphAdaptor and set the node cost of the digraph to the

  /// bind arc in the adapted digraph.

  /// 

  /// disjoint paths are in the digraph. But we would like to know how

  /// many node disjoint paths are in the digraph. First we have to

  /// adapt the digraph with the \c SplitDigraphAdaptor. Then run the flow

  /// algorithm on the adapted digraph. The bottleneck of the flow will

  /// be the bind arcs which bounds the flow with the count of the

  /// node disjoint paths.

  ///

  ///\code

  ///

  /// typedef SplitDigraphAdaptor<SmartDigraph> SDigraph;

  ///

  /// SDigraph sdigraph(digraph);

  /// contains some additional member functions and types. The 

  /// documentation of some member functions may be found just in the

  /// SplitDigraphAdaptorBase class.

  ///

  /// \sa SplitDigraphAdaptorBase

  template <typename _Digraph>

  class SplitDigraphAdaptor 

    : public DigraphAdaptorExtender<SplitDigraphAdaptorBase<_Digraph> > {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorExtender<SplitDigraphAdaptorBase<Digraph> > Parent;

    typedef typename Parent::Node Node;

    typedef typename Parent::Arc Arc;

    /// \brief Constructor of the adaptor.

    ///

    /// Constructor of the adaptor.

    SplitDigraphAdaptor(Digraph& g) {

      Parent::setDigraph(g);

    }

    /// \brief NodeMap combined from two original NodeMap

    ///

    /// This class adapt two of the original digraph NodeMap to

    /// get a node map on the adapted digraph.

    template <typename InNodeMap, typename OutNodeMap>

    class CombinedNodeMap {

    public:

      typedef Node Key;

      typedef typename InNodeMap::Value Value;

      /// \brief Constructor

///\ingroup graph_adaptors

///\file

///\brief Several graph adaptors.

///

///This file contains several useful undirected graph adaptor classes.

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/bits/graph_adaptor_extender.h>

namespace lemon {

  template<typename _Graph>

  class GraphAdaptorBase {

  public:

    typedef _Graph Graph;

    typedef Graph ParentGraph;

  protected:

    Graph* _graph;

    GraphAdaptorBase() : _graph(0) {}

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

	return operator=<EdgeMap>(cmap);

      }

      template <typename CMap>

      EdgeMap& operator=(const CMap& cmap) {

        Parent::operator=(cmap);

        return *this;

      }

    };

  };

  template <typename _Graph, typename NodeFilterMap, 

	    typename EdgeFilterMap, bool checked = true>

  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef SubGraphAdaptorBase Adaptor;

    typedef GraphAdaptorBase<_Graph> Parent;

  protected:

    NodeFilterMap* _node_filter_map;

    EdgeFilterMap* _edge_filter_map;

      Parent::nextOut(i); 

      while (i!=INVALID && (!(*_edge_filter_map)[i] 

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

    }

    void nextInc(Edge& i, bool& d) const { 

      Parent::nextInc(i, d); 

      while (i!=INVALID && (!(*_edge_filter_map)[i]

            || !(*_node_filter_map)[Parent::u(i)]

            || !(*_node_filter_map)[Parent::v(i)])) Parent::nextInc(i, d); 

    }

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

    void hide(const Edge& e) const { _edge_filter_map->set(e, false); }

    void unHide(const Edge& e) const { _edge_filter_map->set(e, true); }