RhodeCode

///This file contains several useful digraph adaptor functions.

  ///\brief Base type for the Digraph Adaptors

  ///

  ///Base type for the Digraph Adaptors

  ///

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

  ///class implements a trivial digraph adaptor i.e. it only wraps the

  ///functions and types of the digraph. The purpose of this class is

  ///to make easier implementing digraph adaptors. E.g. if an adaptor

  ///is considered which differs from the wrapped digraph only in some

  ///of its functions or types, then it can be derived from

  ///DigraphAdaptor, and only the differences should be implemented.

  ///\ingroup graph_adaptors

  ///

  ///\brief Trivial Digraph Adaptor

  /// 

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

  /// digraph.  It can be used only to test the digraph adaptors.

  template <typename _Digraph>

  class DigraphAdaptor :

    public DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > { 

  public:

    typedef _Digraph Digraph;

    typedef DigraphAdaptorExtender<DigraphAdaptorBase<_Digraph> > Parent;

  protected:

    DigraphAdaptor() : Parent() { }

  public:

    explicit DigraphAdaptor(Digraph& digraph) { setDigraph(digraph); }

  };

  /// \brief Just gives back a digraph adaptor

  ///

  /// Just gives back a digraph adaptor which 

  /// should be provide original digraph

  template<typename Digraph>

  DigraphAdaptor<const Digraph>

  digraphAdaptor(const Digraph& digraph) {

    return DigraphAdaptor<const Digraph>(digraph);

  }

  /// ListDigraph g;

  /// RevDigraphAdaptor<ListDigraph> ga(g);

  /// implements the digraph obtained from \c g by 

  /// A good example of using RevDigraphAdaptor is to decide that the

  /// directed graph is wheter strongly connected or not. If from one

  /// node each node is reachable and from each node is reachable this

  /// node then and just then the digraph is strongly

  /// connected. Instead of this condition we use a little bit

  /// different. From one node each node ahould be reachable in the

  /// digraph and in the reversed digraph. Now this condition can be

  /// checked with the Dfs algorithm class and the RevDigraphAdaptor

  /// algorithm class.

  /// And look at the code:

  ///

    ///\e

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

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

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

    ///\e

    /// This function hides \c a in the digraph, i.e. the iteration 

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

    /// to be false in the corresponding arc-map.

    ///\e

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

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

    /// again

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

    ///\e

    /// The value of \c a is set to be true in the arc-map which stores 

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

    /// again

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

    ///\e

    ///

    /// Returns true if \c a is hidden.

    ///\e

    ///

    ///\e

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

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

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

    ///\e

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

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

    /// to be false in the corresponding arc-map.

    ///\e

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

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

    /// again

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

    ///\e

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

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

    /// again

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

    ///\e

    ///

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

    ///\e

    ///

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

  /// to do not get invalid arcs without source or target.

  /// Let \f$ G=(V, A) \f$ be a directed digraph

  /// and suppose that the digraph instance \c g of type ListDigraph

  /// implements \f$ G \f$.

  /// Let moreover \f$ b_V \f$ and \f$ b_A \f$ be bool-valued functions resp.

  /// on the node-set and arc-set.

  /// SubDigraphAdaptor<...>::NodeIt iterates 

  /// on the node-set \f$ \{v\in V : b_V(v)=true\} \f$ and 

  /// SubDigraphAdaptor<...>::ArcIt iterates 

  /// on the arc-set \f$ \{e\in A : b_A(e)=true\} \f$. Similarly, 

  /// SubDigraphAdaptor<...>::OutArcIt and

  /// SubDigraphAdaptor<...>::InArcIt iterates 

  /// only on arcs leaving and entering a specific node which have true value.

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

  /// note that the node-iterator cares only the filter on the

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

  /// arc-set.  This way the arc-map should filter all arcs which's

  /// source or target is filtered by the node-filter.

  /// typedef SubDigraphAdaptor<Digraph, BoolNodeMap, BoolArcMap> SubGA;

  /// SubGA ga(g, nm, am);

  /// for (SubGA::NodeIt n(ga); n!=INVALID; ++n)

  /// std::cout << ":-)" << std::endl;

  /// for (SubGA::ArcIt a(ga); a!=INVALID; ++a) 

  /// :-)

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

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

  /// Just gives back a sub digraph adaptor

  /// \brief Just gives back a \c NodeSubDigraphAdaptor

  /// Just gives back a \c NodeSubDigraphAdaptor

  ///means being shortest w.r.t.  non-negative arc-lengths. Note that

  ///the comprehension of the presented solution need's some

  ///elementary knowlarc from combinatorial optimization.

  ///didigraph lemon_dot_example {

  /// \brief Just gives back an arc sub digraph adaptor

  /// Just gives back an arc sub digraph adaptor

  /// \brief An graph is made from a directed digraph by an adaptor

  /// digraph. All arc of the underlying will be showed in the adaptor

  /// as an edge. Let's see an informal example about using

  /// this adaptor:

  /// \brief Base class for split digraph adaptor

  ///

  /// Base class of split digraph adaptor. In most case you do not need to

  /// use it directly but the documented member functions of this class can 

  /// be used with the SplitDigraphAdaptor class.

  /// \sa SplitDigraphAdaptor

    /// \brief Returns true when the node is in-node.

    ///

    /// Returns true when the node is in-node.

    /// \brief Returns true when the node is out-node.

    ///

    /// Returns true when the node is out-node.

    /// \brief Returns true when the arc is arc in the original digraph.

    ///

    /// Returns true when the arc is arc in the original digraph.

    /// \brief Returns true when the arc binds an in-node and an out-node.

    ///

    /// Returns true when the arc binds an in-node and an out-node.

    /// \brief Gives back the in-node created from the \c node.

    ///

    /// Gives back the in-node created from the \c node.

    /// \brief Gives back the out-node created from the \c node.

    ///

    /// Gives back the out-node created from the \c node.

    /// \brief Gives back the arc binds the two part of the node.

    /// 

    /// Gives back the arc binds the two part of the node.

    /// \brief Gives back the arc of the original arc.

    /// 

    /// Gives back the arc of the original arc.

  /// By example a maximum flow algoritm can compute how many arc

  /// \brief Base type for the Graph Adaptors

  ///

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

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

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

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

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

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

  /// the differences should be implemented.

  /// \ingroup graph_adaptors

  ///

  /// \brief Trivial graph adaptor

  ///

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

  /// graph. It can be used only to test the graph adaptors.

  template <typename _Graph>

  class GraphAdaptor 

    : public GraphAdaptorExtender< GraphAdaptorBase<_Graph> > { 

  public:

    typedef _Graph Graph;

    typedef GraphAdaptorExtender<GraphAdaptorBase<_Graph> > Parent;

  protected:

    GraphAdaptor() : Parent() {}

  public:

    explicit GraphAdaptor(Graph& graph) { setGraph(graph); }

  };

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

    ///

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

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

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

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

    ///

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

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

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

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

    ///

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

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

    /// again

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

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

    ///

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

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

    /// again

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

    ///

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

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

    ///

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

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

    ///

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

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

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

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

    ///

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

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

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

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

    ///

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

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

    /// again

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

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

    ///

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

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

    /// again

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

    ///

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

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

    ///

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

  /// \brief A graph adaptor for hiding nodes and arcs from an

  /// \brief Base of direct graph adaptor

  ///

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

  /// of this class can be used with the DirGraphAdaptor too.

  /// \sa DirGraphAdaptor

void checkDigraphAdaptor() {

  checkConcept<concepts::Digraph, DigraphAdaptor<concepts::Digraph> >();

  typedef ListDigraph Digraph;

  typedef DigraphAdaptor<Digraph> Adaptor;

  Digraph digraph;

  Adaptor adaptor(digraph);

  Digraph::Node n1 = digraph.addNode();

  Digraph::Node n2 = digraph.addNode();

  Digraph::Node n3 = digraph.addNode();

  Digraph::Arc a1 = digraph.addArc(n1, n2);

  Digraph::Arc a2 = digraph.addArc(n1, n3);

  Digraph::Arc a3 = digraph.addArc(n2, n3);

  checkGraphNodeList(adaptor, 3);

  checkGraphArcList(adaptor, 3);

  checkGraphConArcList(adaptor, 3);

  checkGraphOutArcList(adaptor, n1, 2);

  checkGraphOutArcList(adaptor, n2, 1);

  checkGraphOutArcList(adaptor, n3, 0);

  checkGraphInArcList(adaptor, n1, 0);

  checkGraphInArcList(adaptor, n2, 1);

  checkGraphInArcList(adaptor, n3, 2);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

}

void checkGraphAdaptor() {

  checkConcept<concepts::Graph, GraphAdaptor<concepts::Graph> >();

  typedef ListGraph Graph;

  typedef GraphAdaptor<Graph> Adaptor;

  Graph graph;

  Adaptor adaptor(graph);

  Graph::Node n1 = graph.addNode();

  Graph::Node n2 = graph.addNode();

  Graph::Node n3 = graph.addNode();

  Graph::Node n4 = graph.addNode();

  Graph::Edge a1 = graph.addEdge(n1, n2);

  Graph::Edge a2 = graph.addEdge(n1, n3);

  Graph::Edge a3 = graph.addEdge(n2, n3);

  Graph::Edge a4 = graph.addEdge(n3, n4);

  checkGraphNodeList(adaptor, 4);

  checkGraphArcList(adaptor, 8);

  checkGraphEdgeList(adaptor, 4);

  checkGraphConArcList(adaptor, 8);

  checkGraphConEdgeList(adaptor, 4);

  checkGraphOutArcList(adaptor, n1, 2);

  checkGraphOutArcList(adaptor, n2, 2);

  checkGraphOutArcList(adaptor, n3, 3);

  checkGraphOutArcList(adaptor, n4, 1);

  checkGraphInArcList(adaptor, n1, 2);

  checkGraphInArcList(adaptor, n2, 2);

  checkGraphInArcList(adaptor, n3, 3);

  checkGraphInArcList(adaptor, n4, 1);

  checkGraphIncEdgeList(adaptor, n1, 2);

  checkGraphIncEdgeList(adaptor, n2, 2);

  checkGraphIncEdgeList(adaptor, n3, 3);

  checkGraphIncEdgeList(adaptor, n4, 1);

  checkNodeIds(adaptor);

  checkArcIds(adaptor);

  checkEdgeIds(adaptor);

  checkGraphNodeMap(adaptor);

  checkGraphArcMap(adaptor);

  checkGraphEdgeMap(adaptor);

}

  checkDigraphAdaptor();

  checkGraphAdaptor();