RhodeCode

#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/tolerance.h>

#include <algorithm>

namespace lemon {

  template<typename _Digraph>

  class DigraphAdaptorBase {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase Adaptor;

    typedef Digraph ParentDigraph;

      }

    };

  };

  template <typename _Digraph>

  class RevDigraphAdaptorBase : public DigraphAdaptorBase<_Digraph> {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase<_Digraph> Parent;

  ///\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) {

    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

    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;

    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;

  /// \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>, 

    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, const ArcFilterMap>

  subDigraphAdaptor(const Digraph& digraph, 

                   NodeFilterMap& nfm, ArcFilterMap& afm) {

    return SubDigraphAdaptor<const Digraph, const NodeFilterMap, 

      const ArcFilterMap>(digraph, nfm, afm);

  }

  ///\ingroup graph_adaptors

  ///

    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);

  }

  ///

  ///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

  ///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" ];

  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);

  }

    }

  };

  ///\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

      }

    };

  };

  template <typename _Digraph>

  class SplitDigraphAdaptorBase {

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorBase<const _Digraph> Parent;

    }

    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;

  ///

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

  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 {

#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;

        return *this;

      }

    };

  };

  template <typename _Graph, typename NodeFilterMap, 

	    typename EdgeFilterMap, bool checked = true>

  class SubGraphAdaptorBase : public GraphAdaptorBase<_Graph> {

  public:

    typedef _Graph Graph;

    typedef SubGraphAdaptorBase Adaptor;

      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); }

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

    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

    }

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

      Parent::nextInc(i, d); 

      while (i!=INVALID && !(*_edge_filter_map)[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); }

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

    bool hidden(const Edge& e) const { return !(*_edge_filter_map)[e]; }

    typedef False NodeNumTag;

    typedef False EdgeNumTag;

    typedef FindEdgeTagIndicator<Graph> FindEdgeTag;

    };

  };

  /// \ingroup graph_adaptors

  ///

  /// undirected graph.

  /// 

  /// SubGraphAdaptor shows the graph with filtered node-set and

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

  /// the edge-set to do not get invalid edges which incident node is

  /// filtered.

    public GraphAdaptorExtender<

    SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap, checked> > {

  public:

    typedef _Graph Graph;

    typedef GraphAdaptorExtender<

      SubGraphAdaptorBase<_Graph, NodeFilterMap, EdgeFilterMap> > Parent;

  protected:

    SubGraphAdaptor() { }

  public:

    SubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map, 

		    EdgeFilterMap& edge_filter_map) { 

      setGraph(_graph);

      setNodeFilterMap(node_filter_map);

      setEdgeFilterMap(edge_filter_map);

    }

  };

  template<typename Graph, typename NodeFilterMap, typename ArcFilterMap>

  SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>

  subGraphAdaptor(const Graph& graph, 

                   NodeFilterMap& nfm, ArcFilterMap& efm) {

    return SubGraphAdaptor<const Graph, NodeFilterMap, ArcFilterMap>

      (graph, nfm, efm);

			   ConstMap<typename _Graph::Edge, bool>, checked> {

  public:

    typedef _Graph Graph;

    typedef _NodeFilterMap NodeFilterMap;

    typedef SubGraphAdaptor<Graph, NodeFilterMap, 

			    ConstMap<typename Graph::Edge, bool> > Parent;

  protected:

    ConstMap<typename Graph::Edge, bool> const_true_map;

    NodeSubGraphAdaptor() : const_true_map(true) {

      Parent::setEdgeFilterMap(const_true_map);

    }

  public:

    NodeSubGraphAdaptor(Graph& _graph, NodeFilterMap& node_filter_map) : 

      Parent(), const_true_map(true) { 

      Parent::setGraph(_graph);

      Parent::setNodeFilterMap(node_filter_map);

      Parent::setEdgeFilterMap(const_true_map);

    }

  };

  template<typename Graph, typename NodeFilterMap>

  NodeSubGraphAdaptor<const Graph, NodeFilterMap>

  nodeSubGraphAdaptor(const Graph& graph, NodeFilterMap& nfm) {

    return NodeSubGraphAdaptor<const Graph, NodeFilterMap>(graph, nfm);

  }

                           _EdgeFilterMap, false> {

  public:

    typedef _Graph Graph;

    typedef _EdgeFilterMap EdgeFilterMap;

    typedef SubGraphAdaptor<Graph, ConstMap<typename Graph::Node,bool>, 

			    EdgeFilterMap, false> Parent;

  protected:

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

    EdgeSubGraphAdaptor() : const_true_map(true) {

      Parent::setNodeFilterMap(const_true_map);

    }

  public: