RhodeCode

  /// \brief Check whether an undirected graph is connected.

  /// This function checks whether the given undirected graph is connected,

  /// i.e. there is a path between any two nodes in the graph.

  ///

  /// \return \c true if the graph is connected.

  ///

  /// \see countConnectedComponents(), connectedComponents()

  /// \see stronglyConnected()

  /// This function counts the number of connected components of the given

  /// undirected graph.

  /// The connected components are the classes of an equivalence relation

  /// on the nodes of an undirected graph. Two nodes are in the same class

  /// if they are connected with a path.

  ///

  /// \return The number of connected components.

  ///

  /// \see connected(), connectedComponents()

  /// This function finds the connected components of the given undirected

  /// graph.

  ///

  /// The connected components are the classes of an equivalence relation

  /// on the nodes of an undirected graph. Two nodes are in the same class

  /// if they are connected with a path.

  /// \param graph The undirected graph.

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

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

  /// \return The number of connected components.

  /// \note By definition, the empty graph consists

  /// of zero connected components.

  ///

  /// \see connected(), countConnectedComponents()

  /// \brief Check whether a directed graph is strongly connected.

  /// This function checks whether the given directed graph is strongly

  /// connected, i.e. any two nodes of the digraph are

  /// \return \c true if the digraph is strongly connected.

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

  /// 

  /// \see countStronglyConnectedComponents(), stronglyConnectedComponents()

  /// \see connected()

    typedef DfsVisitor<RDigraph> RVisitor;

  /// \brief Count the number of strongly connected components of a 

  /// directed graph

  /// This function counts the number of strongly connected components of

  /// the given directed graph.

  ///

  /// equivalence relation on the nodes of a digraph. Two nodes are in

  /// \return The number of strongly connected components.

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

  ///

  /// \see stronglyConnected(), stronglyConnectedComponents()

  /// This function finds the strongly connected components of the given

  /// directed graph. In addition, the numbering of the components will

  /// satisfy that there is no arc going from a higher numbered component

  /// to a lower one (i.e. it provides a topological order of the components).

  ///

  /// The strongly connected components are the classes of an

  /// equivalence relation on the nodes of a digraph. Two nodes are in

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

  /// direction.

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

  /// component will be set continuously.

  /// \return The number of strongly connected components.

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

  /// strongly connected components.

  ///

  /// \see stronglyConnected(), countStronglyConnectedComponents()

  /// This function finds the cut arcs of the strongly connected components

  /// of the given digraph.

  ///

  /// The strongly connected components are the classes of an

  /// equivalence relation on the nodes of a digraph. Two nodes are in

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

  /// direction.

  /// \param digraph The digraph.

  /// \retval cutMap A writable arc map. The values will be set to \c true

  /// for the cut arcs (exactly once for each cut arc), and will not be

  /// changed for other arcs.

  /// \return The number of cut arcs.

  /// \see stronglyConnected(), stronglyConnectedComponents()

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

    Container nodes(countNodes(digraph));

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

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

    RDigraph rdigraph(digraph);

    RVisitor rvisitor(rdigraph, cutMap, cutNum);

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

  /// \brief Check whether an undirected graph is bi-node-connected.

  /// This function checks whether the given undirected graph is 

  /// bi-node-connected, i.e. any two edges are on same circle.

  /// \return \c true if the graph bi-node-connected.

  /// \note By definition, the empty graph is bi-node-connected.

  ///

  /// \see countBiNodeConnectedComponents(), biNodeConnectedComponents()

  /// \brief Count the number of bi-node-connected components of an 

  /// undirected graph.

  /// This function counts the number of bi-node-connected components of

  /// the given undirected graph.

  /// The bi-node-connected components are the classes of an equivalence

  /// relation on the edges of a undirected graph. Two edges are in the

  /// same class if they are on same circle.

  ///

  /// \return The number of bi-node-connected components.

  ///

  /// \see biNodeConnected(), biNodeConnectedComponents()

  /// \brief Find the bi-node-connected components of an undirected graph.

  /// This function finds the bi-node-connected components of the given

  /// undirected graph.

  ///

  /// The bi-node-connected components are the classes of an equivalence

  /// relation on the edges of a undirected graph. Two edges are in the

  /// same class if they are on same circle.

  /// \param graph The undirected graph.

  /// \retval compMap A writable edge map. The values will be set from 0

  /// to the number of the bi-node-connected components minus one. Each

  /// value of the map will be set exactly once, and the values of a 

  /// certain component will be set continuously.

  /// \return The number of bi-node-connected components.

  ///

  /// \see biNodeConnected(), countBiNodeConnectedComponents()

  /// \brief Find the bi-node-connected cut nodes in an undirected graph.

  /// This function finds the bi-node-connected cut nodes in the given

  /// undirected graph.

  /// The bi-node-connected components are the classes of an equivalence

  /// relation on the edges of a undirected graph. Two edges are in the

  /// same class if they are on same circle.

  /// The bi-node-connected components are separted by the cut nodes of

  /// the components.

  ///

  /// \param graph The undirected graph.

  /// \retval cutMap A writable node map. The values will be set to 

  /// \c true for the nodes that separate two or more components

  /// (exactly once for each cut node), and will not be changed for

  /// other nodes.

  ///

  /// \see biNodeConnected(), biNodeConnectedComponents()

  /// \brief Check whether an undirected graph is bi-edge-connected.

  /// This function checks whether the given undirected graph is 

  /// bi-edge-connected, i.e. any two nodes are connected with at least

  /// two edge-disjoint paths.

  /// \return \c true if the graph is bi-edge-connected.

  /// \note By definition, the empty graph is bi-edge-connected.

  ///

  /// \see countBiEdgeConnectedComponents(), biEdgeConnectedComponents()

  /// \brief Count the number of bi-edge-connected components of an

  /// undirected graph.

  /// This function counts the number of bi-edge-connected components of

  /// the given undirected graph.

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

  /// relation on the nodes of an undirected graph. Two nodes are in the

  /// same class if they are connected with at least two edge-disjoint

  /// paths.

  ///

  /// \return The number of bi-edge-connected components.

  ///

  /// \see biEdgeConnected(), biEdgeConnectedComponents()

  /// \brief Find the bi-edge-connected components of an undirected graph.

  /// This function finds the bi-edge-connected components of the given

  /// undirected graph.

  ///

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

  /// relation on the nodes of an undirected graph. Two nodes are in the

  /// same class if they are connected with at least two edge-disjoint

  /// paths.

  /// \param graph The undirected graph.

  /// the number of the bi-edge-connected components minus one. Each value

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

  /// component will be set continuously.

  /// \return The number of bi-edge-connected components.

  ///

  /// \see biEdgeConnected(), countBiEdgeConnectedComponents()

  /// \brief Find the bi-edge-connected cut edges in an undirected graph.

  /// This function finds the bi-edge-connected cut edges in the given

  /// undirected graph. 

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

  /// relation on the nodes of an undirected graph. Two nodes are in the

  /// same class if they are connected with at least two edge-disjoint

  /// paths.

  /// The bi-edge-connected components are separted by the cut edges of

  /// the components.

  ///

  /// \param graph The undirected graph.

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

  /// for the cut edges (exactly once for each cut edge), and will not be

  /// changed for other edges.

  ///

  /// \see biEdgeConnected(), biEdgeConnectedComponents()

  /// \brief Check whether a digraph is DAG.

  ///

  /// This function checks whether the given digraph is DAG, i.e.

  /// \e Directed \e Acyclic \e Graph.

  /// \return \c true if there is no directed cycle in the digraph.

  /// \see acyclic()

  template <typename Digraph>

  bool dag(const Digraph& 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>::

      Create dfs(digraph);

    ProcessedMap processed(digraph);

    dfs.processedMap(processed);

    dfs.init();

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

      if (!dfs.reached(it)) {

        dfs.addSource(it);

        while (!dfs.emptyQueue()) {

          Arc arc = dfs.nextArc();

          Node target = digraph.target(arc);

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

            return false;

          }

          dfs.processNextArc();

        }

      }

    }

    return true;

  }

  /// \ingroup graph_properties

  ///

  /// This function sorts the nodes of the given acyclic digraph (DAG)

  /// into topolgical order.

  /// \param digraph The digraph, which must be DAG.

  /// the number of the nodes in the digraph minus one. Each value of the

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

  /// order.

  /// \see dag(), checkedTopologicalSort()

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

      visitor(order, countNodes(digraph));

      dfs(digraph, visitor);

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

  /// This function sorts the nodes of the given acyclic digraph (DAG)

  /// into topolgical order and also checks whether the given digraph

  /// is DAG.

  /// \param digraph The digraph.

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

  /// set from 0 to the number of the nodes in the digraph minus one. 

  /// Each value of the map will be set exactly once, and the values will

  /// be set descending order.

  /// \return \c false if the digraph is not DAG.

  /// \see dag(), topologicalSort()

  /// \brief Check whether an undirected graph is acyclic.

  /// This function checks whether the given undirected graph is acyclic.

  /// \return \c true if there is no cycle in the graph.

  /// \see dag()

          Arc arc = dfs.nextArc();

          Node source = graph.source(arc);

          Node target = graph.target(arc);

              dfs.predArc(source) != graph.oppositeArc(arc)) {

  /// \brief Check whether an undirected graph is tree.

  /// This function checks whether the given undirected graph is tree.

  /// \return \c true if the graph is acyclic and connected.

  /// \see acyclic(), connected()

      Arc arc = dfs.nextArc();

      Node source = graph.source(arc);

      Node target = graph.target(arc);

          dfs.predArc(source) != graph.oppositeArc(arc)) {

  /// \brief Check whether an undirected graph is bipartite.

  /// The function checks whether the given undirected graph is bipartite.

  /// \return \c true if the graph is bipartite.

  ///

  /// \see bipartitePartitions()

  bool bipartite(const Graph &graph){

  /// \brief Find the bipartite partitions of an undirected graph.

  /// This function checks whether the given undirected graph is bipartite

  /// and gives back the bipartite partitions.

  /// \retval partMap A writable node map of \c bool (or convertible) value

  /// type. The values will be set to \c true for one component and

  /// \c false for the other one.

  /// \return \c true if the graph is bipartite, \c false otherwise.

  ///

  /// \see bipartite()

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

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

  /// \ingroup graph_properties

  /// \brief Check whether the given graph contains no loop arcs/edges.

  ///

  /// This function returns \c true if there are no loop arcs/edges in

  /// the given graph. It works for both directed and undirected graphs.

  template <typename Graph>

  bool loopFree(const Graph& graph) {

    for (typename Graph::ArcIt it(graph); it != INVALID; ++it) {

      if (graph.source(it) == graph.target(it)) return false;

  /// \ingroup graph_properties

  /// \brief Check whether the given graph contains no parallel arcs/edges.

  ///

  /// This function returns \c true if there are no parallel arcs/edges in

  /// the given graph. It works for both directed and undirected graphs.

  /// \ingroup graph_properties

  /// \brief Check whether the given graph is simple.

  ///

  /// This function returns \c true if the given graph is simple, i.e.

  /// it contains no loop arcs/edges and no parallel arcs/edges.

  /// The function works for both directed and undirected graphs.

  /// \see loopFree(), parallelFree()

  ///Check if the given graph is Eulerian

  ///This function checks if the given graph is Eulerian.