RhodeCode

 * (Egervary Research Group on Combinatorial Optimization, EGRES).

 *

 * Permission to use, modify and distribute this software is granted

 * provided that this copyright notice appears in all copies. For

 * precise terms see the accompanying LICENSE file.

 *

 * This software is provided "AS IS" with no warranty of any kind,

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

 * purpose.

 *

 */

#include <lemon/dfs.h>

#include <lemon/bfs.h>

#include <lemon/core.h>

#include <lemon/maps.h>

#include <lemon/adaptors.h>

#include <lemon/concepts/digraph.h>

#include <lemon/concepts/graph.h>

#include <lemon/concept_check.h>

#include <stack>

      if(!bfs.reached(n)) {

        bfs.addSource(n);

        while (!bfs.emptyQueue()) {

          compMap.set(bfs.nextNode(), compNum);

          bfs.processNextNode();

        }

        ++compNum;

      }

    }

    return compNum;

  }

    template <typename Digraph, typename Iterator >

    struct LeaveOrderVisitor : public DfsVisitor<Digraph> {

    public:

      typedef typename Digraph::Node Node;

      LeaveOrderVisitor(Iterator it) : _it(it) {}

      void leave(const Node& node) {

        *(_it++) = node;

      }

    private:

      FillMapVisitor(Map& map, Value& value)

        : _map(map), _value(value) {}

      void reach(const Node& node) {

        _map.set(node, _value);

      }

    private:

      Map& _map;

      Value& _value;

    };

    template <typename Digraph, typename ArcMap>

    public:

      typedef typename Digraph::Node Node;

      typedef typename Digraph::Arc Arc;

        : _digraph(digraph), _cutMap(cutMap), _cutNum(cutNum),

      }

        ++_num;

      }

      void reach(const Node& node) {

        _compMap.set(node, _num);

      }

      void examine(const Arc& arc) {

         if (_compMap[_digraph.source(arc)] !=

             _compMap[_digraph.target(arc)]) {

           _cutMap.set(arc, true);

           ++_cutNum;

  ///

  /// \note By definition, the empty graph is strongly connected.

  template <typename Digraph>

  bool stronglyConnected(const Digraph& digraph) {

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

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typename Digraph::Node source = NodeIt(digraph);

    if (source == INVALID) return true;

    typedef DfsVisitor<Digraph> Visitor;

    Visitor visitor;

    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);

    dfs.init();

    dfs.addSource(source);

    dfs.start();

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

      if (!dfs.reached(it)) {

        return false;

      }

    }

    typedef ReverseDigraph<const Digraph> RDigraph;

    RDigraph rdigraph(digraph);

    typedef DfsVisitor<Digraph> RVisitor;

    RVisitor rvisitor;

    DfsVisit<RDigraph, RVisitor> rdfs(rdigraph, rvisitor);

    rdfs.init();

    rdfs.addSource(source);

    rdfs.start();

      if (!rdfs.reached(it)) {

        return false;

      }

    }

    return true;

  }

  /// \ingroup connectivity

  ///

  /// \brief Count the strongly connected components of a directed graph

  ///

  /// equivalence relation on the nodes of the graph. Two nodes are in

  /// the same class if they are connected with directed paths in both

  /// direction.

  ///

  /// \param graph The graph.

  /// \return The number of components

  /// \note By definition, the empty graph has zero

  /// strongly connected components.

  template <typename Digraph>

  int countStronglyConnectedComponents(const Digraph& digraph) {

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

    typedef typename Digraph::Node Node;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::ArcIt ArcIt;

    typedef std::vector<Node> Container;

    typedef typename Container::iterator Iterator;

    Container nodes(countNodes(digraph));

    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;

    Visitor visitor(nodes.begin());

  /// the number of the strongly connected components minus one. Each value

  /// of the map will be set exactly once, the values of a certain component

  /// will be set continuously.

  /// \return The number of components

  ///

  template <typename Digraph, typename NodeMap>

  int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) {

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

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();

    typedef std::vector<Node> Container;

    typedef typename Container::iterator Iterator;

    Container nodes(countNodes(digraph));

    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;

    Visitor visitor(nodes.begin());

    DfsVisit<Digraph, Visitor> dfs(digraph, visitor);

    dfs.init();

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

      if (!dfs.reached(it)) {

  /// \retval cutMap A writable node map. The values will be set true when the

  /// arc is a cut arc.

  ///

  /// \return The number of cut arcs

  template <typename Digraph, typename ArcMap>

  int stronglyConnectedCutArcs(const Digraph& graph, ArcMap& cutMap) {

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

    typedef typename Digraph::Node Node;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::NodeIt NodeIt;

    checkConcept<concepts::WriteMap<Arc, bool>, ArcMap>();

    typedef std::vector<Node> Container;

    typedef typename Container::iterator Iterator;

    Container nodes(countNodes(graph));

    typedef LeaveOrderVisitor<Digraph, Iterator> Visitor;

    Visitor visitor(nodes.begin());

    DfsVisit<Digraph, Visitor> dfs(graph, visitor);

    dfs.init();

    for (NodeIt it(graph); it != INVALID; ++it) {

      if (!dfs.reached(it)) {

        dfs.addSource(it);

        dfs.start();

      }

    }

    typedef typename Container::reverse_iterator RIterator;

    typedef ReverseDigraph<const Digraph> RDigraph;

    RDigraph rgraph(graph);

    int cutNum = 0;

    RVisitor rvisitor(rgraph, cutMap, cutNum);

    DfsVisit<RDigraph, RVisitor> rdfs(rgraph, rvisitor);

    rdfs.init();

    for (RIterator it = nodes.rbegin(); it != nodes.rend(); ++it) {

      if (!rdfs.reached(*it)) {

        rdfs.addSource(*it);

        rdfs.start();

      }

    }

    return cutNum;

  }

    template <typename Digraph>

    class CountBiNodeConnectedComponentsVisitor : public DfsVisitor<Digraph> {

    public:

      typedef typename Digraph::Node Node;

      typedef typename Digraph::Arc Arc;

      typedef typename Digraph::Edge Edge;

      CountBiNodeConnectedComponentsVisitor(const Digraph& graph, int &compNum)

        : _graph(graph), _compNum(compNum),

          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}

  /// This function finds the bi-node-connected components in an undirected

  /// graph. The biconnected components are the classes of an equivalence

  /// relation on the undirected edges. Two undirected edge is in relationship

  /// when they are on same circle.

  ///

  /// \param graph The graph.

  /// \return The number of components.

  template <typename Graph>

  int countBiNodeConnectedComponents(const Graph& graph) {

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

    typedef typename Graph::NodeIt NodeIt;

    typedef CountBiNodeConnectedComponentsVisitor<Graph> Visitor;

    int compNum = 0;

    Visitor visitor(graph, compNum);

    DfsVisit<Graph, Visitor> dfs(graph, visitor);

    dfs.init();

    for (NodeIt it(graph); it != INVALID; ++it) {

      if (!dfs.reached(it)) {

        dfs.addSource(it);

  /// of the map will be set exactly once, the values of a certain component

  /// will be set continuously.

  /// \return The number of components.

  ///

  template <typename Graph, typename EdgeMap>

  int biNodeConnectedComponents(const Graph& graph,

                                EdgeMap& compMap) {

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

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::Edge Edge;

    checkConcept<concepts::WriteMap<Edge, int>, EdgeMap>();

    typedef BiNodeConnectedComponentsVisitor<Graph, EdgeMap> Visitor;

    int compNum = 0;

    Visitor visitor(graph, compMap, compNum);

    DfsVisit<Graph, Visitor> dfs(graph, visitor);

    dfs.init();

    for (NodeIt it(graph); it != INVALID; ++it) {

      if (!dfs.reached(it)) {

        dfs.addSource(it);

  ///

  /// \param graph The graph.

  /// \retval cutMap A writable edge map. The values will be set true when

  /// the node separate two or more components.

  /// \return The number of the cut nodes.

  template <typename Graph, typename NodeMap>

  int biNodeConnectedCutNodes(const Graph& graph, NodeMap& cutMap) {

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

    typedef typename Graph::Node Node;

    typedef typename Graph::NodeIt NodeIt;

    checkConcept<concepts::WriteMap<Node, bool>, NodeMap>();

    typedef BiNodeConnectedCutNodesVisitor<Graph, NodeMap> Visitor;

    int cutNum = 0;

    Visitor visitor(graph, cutMap, cutNum);

    DfsVisit<Graph, Visitor> dfs(graph, visitor);

    dfs.init();

    for (NodeIt it(graph); it != INVALID; ++it) {

      if (!dfs.reached(it)) {

        dfs.addSource(it);

        dfs.start();

      }

    }

    return cutNum;

  }

    template <typename Digraph>

    class CountBiEdgeConnectedComponentsVisitor : public DfsVisitor<Digraph> {

    public:

      typedef typename Digraph::Node Node;

      typedef typename Digraph::Arc Arc;

      typedef typename Digraph::Edge Edge;

      CountBiEdgeConnectedComponentsVisitor(const Digraph& graph, int &compNum)

        : _graph(graph), _compNum(compNum),

          _numMap(graph), _retMap(graph), _predMap(graph), _num(0) {}

  /// This function count the bi-edge-connected components in an undirected

  /// graph. The bi-edge-connected components are the classes of an equivalence

  /// relation on the nodes. Two nodes are in relationship when they are

  /// connected with at least two edge-disjoint paths.

  ///

  /// \param graph The undirected graph.

  /// \return The number of components.

  template <typename Graph>

  int countBiEdgeConnectedComponents(const Graph& graph) {

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

    typedef typename Graph::NodeIt NodeIt;

    typedef CountBiEdgeConnectedComponentsVisitor<Graph> Visitor;

    int compNum = 0;

    Visitor visitor(graph, compNum);

    DfsVisit<Graph, Visitor> dfs(graph, visitor);

    dfs.init();

    for (NodeIt it(graph); it != INVALID; ++it) {

      if (!dfs.reached(it)) {

        dfs.addSource(it);

  /// the number of the biconnected components minus one. Each values

  /// of the map will be set exactly once, the values of a certain component

  /// will be set continuously.

  /// \return The number of components.

  ///

  template <typename Graph, typename NodeMap>

  int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) {

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

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::Node Node;

    checkConcept<concepts::WriteMap<Node, int>, NodeMap>();

    typedef BiEdgeConnectedComponentsVisitor<Graph, NodeMap> Visitor;

    int compNum = 0;

    Visitor visitor(graph, compMap, compNum);

    DfsVisit<Graph, Visitor> dfs(graph, visitor);

    dfs.init();

    for (NodeIt it(graph); it != INVALID; ++it) {

      if (!dfs.reached(it)) {

        dfs.addSource(it);

  ///

  /// \param graph The graph.

  /// \retval cutMap A writable node map. The values will be set true when the

  /// edge is a cut edge.

  /// \return The number of cut edges.

  template <typename Graph, typename EdgeMap>

  int biEdgeConnectedCutEdges(const Graph& graph, EdgeMap& cutMap) {

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

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::Edge Edge;

    checkConcept<concepts::WriteMap<Edge, bool>, EdgeMap>();

    typedef BiEdgeConnectedCutEdgesVisitor<Graph, EdgeMap> Visitor;

    int cutNum = 0;

    Visitor visitor(graph, cutMap, cutNum);

    DfsVisit<Graph, Visitor> dfs(graph, visitor);

    dfs.init();

    for (NodeIt it(graph); it != INVALID; ++it) {

      if (!dfs.reached(it)) {

        dfs.addSource(it);

        dfs.start();

      }

    }

    return cutNum;

  }

    template <typename Digraph, typename IntNodeMap>

    class TopologicalSortVisitor : public DfsVisitor<Digraph> {

    public:

      typedef typename Digraph::Node Node;

      typedef typename Digraph::Arc edge;

      TopologicalSortVisitor(IntNodeMap& order, int num)

        : _order(order), _num(num) {}

      void leave(const Node& node) {

        _order.set(node, --_num);

  ///

  /// Sort the nodes of a DAG into topolgical order.

  ///

  /// \param graph The graph. It must be directed and acyclic.

  /// \retval order A writable node map. The values will be set from 0 to

  /// the number of the nodes in the graph minus one. Each values of the map

  /// will be set exactly once, the values  will be set descending order.

  ///

  /// \see checkedTopologicalSort

  /// \see dag

  template <typename Digraph, typename NodeMap>

  void topologicalSort(const Digraph& graph, NodeMap& order) {

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

    checkConcept<concepts::WriteMap<typename Digraph::Node, int>, NodeMap>();

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    TopologicalSortVisitor<Digraph, NodeMap>

      visitor(order, countNodes(graph));

    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >

  /// that the given graph is DAG.

  ///

  /// \param graph The graph. It must be directed and acyclic.

  /// \retval order A readable - writable node map. The values will be set

  /// from 0 to the number of the nodes in the graph minus one. Each values

  /// of the map will be set exactly once, the values will be set descending

  /// order.

  /// \return %False when the graph is not DAG.

  ///

  /// \see topologicalSort

  /// \see dag

  template <typename Digraph, typename NodeMap>

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

    checkConcept<concepts::ReadWriteMap<typename Digraph::Node, int>,

      NodeMap>();

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    TopologicalSortVisitor<Digraph, NodeMap>

    DfsVisit<Digraph, TopologicalSortVisitor<Digraph, NodeMap> >

    dfs.init();

      if (!dfs.reached(it)) {

        dfs.addSource(it);

        while (!dfs.emptyQueue()) {

           if (dfs.reached(target) && order[target] == -1) {

             return false;

           }

           dfs.processNextArc();

         }

      }

    }

    return true;

  }

  /// \ingroup connectivity

  ///

  /// \brief Check that the given directed graph is a DAG.

  ///

  /// Check that the given directed graph is a DAG. The DAG is

  /// an Directed Acyclic Digraph.

  /// \return %False when the graph is not DAG.

  /// \see acyclic

  template <typename Digraph>

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

    typedef typename Digraph::Node Node;

    typedef typename Digraph::NodeIt NodeIt;

    typedef typename Digraph::Arc Arc;

    typedef typename Digraph::template NodeMap<bool> ProcessedMap;

    typename Dfs<Digraph>::template SetProcessedMap<ProcessedMap>::

    dfs.processedMap(processed);

    dfs.init();

      if (!dfs.reached(it)) {

        dfs.addSource(it);

        while (!dfs.emptyQueue()) {

          Arc edge = dfs.nextArc();

          if (dfs.reached(target) && !processed[target]) {

            return false;

          }

          dfs.processNextArc();

        }

      }

    }

    return true;

  }

  /// \ingroup connectivity

  ///

        return false;

      }

      dfs.processNextArc();

    }

    for (NodeIt it(graph); it != INVALID; ++it) {

      if (!dfs.reached(it)) {

        return false;

      }

    }

    return true;

  }

    template <typename Digraph>

    class BipartiteVisitor : public BfsVisitor<Digraph> {

    public:

      typedef typename Digraph::Arc Arc;

      typedef typename Digraph::Node Node;

      BipartiteVisitor(const Digraph& graph, bool& bipartite)

        : _graph(graph), _part(graph), _bipartite(bipartite) {}

      void start(const Node& node) {

        _part[node] = true;

  /// \ingroup connectivity

  ///

  /// \brief Check if the given undirected graph is bipartite or not

  ///

  /// The function checks if the given undirected \c graph graph is bipartite

  /// or not. The \ref Bfs algorithm is used to calculate the result.

  /// \param graph The undirected graph.

  /// \return %True if \c graph is bipartite, %false otherwise.

  /// \sa bipartitePartitions

  template<typename Graph>

  inline bool bipartite(const Graph &graph){

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

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::ArcIt ArcIt;

    bool bipartite = true;

    BipartiteVisitor<Graph>

      visitor(graph, bipartite);

    BfsVisit<Graph, BipartiteVisitor<Graph> >

      bfs(graph, visitor);

  /// \brief Check if the given undirected graph is bipartite or not

  ///

  /// The function checks if the given undirected graph is bipartite

  /// or not. The  \ref  Bfs  algorithm  is   used  to  calculate the result.

  /// During the execution, the \c partMap will be set as the two

  /// partitions of the graph.

  /// \param graph The undirected graph.

  /// \retval partMap A writable bool map of nodes. It will be set as the

  /// two partitions of the graph.

  /// \return %True if \c graph is bipartite, %false otherwise.

  template<typename Graph, typename NodeMap>

  inline bool bipartitePartitions(const Graph &graph, NodeMap &partMap){

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

    typedef typename Graph::Node Node;

    typedef typename Graph::NodeIt NodeIt;

    typedef typename Graph::ArcIt ArcIt;

    bool bipartite = true;

    BipartitePartitionsVisitor<Graph, NodeMap>

      visitor(graph, partMap, bipartite);

    BfsVisit<Graph, BipartitePartitionsVisitor<Graph, NodeMap> >

          bfs.processNextNode();

          if (!bipartite) return false;

        }

      }

    }

    return true;

  }

  /// \brief Returns true when there are not loop edges in the graph.

  ///

  /// Returns true when there are not loop edges in the graph.

  template <typename Digraph>

    }

    return true;

  }

  /// \brief Returns true when there are not parallel edges in the graph.

  ///

  /// Returns true when there are not parallel edges in the graph.

  template <typename Digraph>

      }

      }

    }

    return true;

  }

  /// \brief Returns true when there are not loop edges and parallel

  /// edges in the graph.

  ///

  /// Returns true when there are not loop edges and parallel edges in

  /// the graph.

  template <typename Digraph>

      reached.set(n, true);

      }

      }

      reached.set(n, false);

    }

    return true;

  }

} //namespace lemon

    {

      LEMON_DEBUG(emptyQueue(), "The stack is not empty.");

      if(!(*_reached)[s]) {

          _reached->set(s,true);

          _visitor->start(s);

          _visitor->reach(s);

          Arc e;

          _digraph->firstOut(e, s);

          if (e != INVALID) {

            _stack[++_stack_head] = e;

          } else {

            _visitor->leave(s);

          }

        }

    }

    /// \brief Processes the next arc.

    ///

    /// Processes the next arc.

    ///

    /// \return The processed arc.

    ///

    /// \pre The stack must not be empty.

    Arc processNextArc() {