RhodeCode

/* -*- mode: C++; indent-tabs-mode: nil; -*-

 *

 * This file is a part of LEMON, a generic C++ optimization library.

 *

 * Copyright (C) 2003-2009

 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport

 * (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/connectivity.h>

#include <lemon/list_graph.h>

#include <lemon/adaptors.h>

#include "test_tools.h"

using namespace lemon;

int main()

{

  typedef ListDigraph Digraph;

  typedef Undirector<Digraph> Graph;

  {

    Digraph d;

    Digraph::NodeMap<int> order(d);

    Graph g(d);

    check(stronglyConnected(d), "The empty digraph is strongly connected");

    check(countStronglyConnectedComponents(d) == 0,

          "The empty digraph has 0 strongly connected component");

    check(connected(g), "The empty graph is connected");

    check(countConnectedComponents(g) == 0,

          "The empty graph has 0 connected component");

    check(biNodeConnected(g), "The empty graph is bi-node-connected");

    check(countBiNodeConnectedComponents(g) == 0,

          "The empty graph has 0 bi-node-connected component");

    check(biEdgeConnected(g), "The empty graph is bi-edge-connected");

    check(countBiEdgeConnectedComponents(g) == 0,

          "The empty graph has 0 bi-edge-connected component");

    check(dag(d), "The empty digraph is DAG.");

    check(checkedTopologicalSort(d, order), "The empty digraph is DAG.");

    check(loopFree(d), "The empty digraph is loop-free.");

    check(parallelFree(d), "The empty digraph is parallel-free.");

    check(simpleGraph(d), "The empty digraph is simple.");

    check(acyclic(g), "The empty graph is acyclic.");

    check(tree(g), "The empty graph is tree.");

    check(bipartite(g), "The empty graph is bipartite.");

    check(loopFree(g), "The empty graph is loop-free.");

    check(parallelFree(g), "The empty graph is parallel-free.");

    check(simpleGraph(g), "The empty graph is simple.");

  }

  {

    Digraph d;

    Digraph::NodeMap<int> order(d);

    Graph g(d);

    Digraph::Node n = d.addNode();

    check(stronglyConnected(d), "This digraph is strongly connected");

    check(countStronglyConnectedComponents(d) == 1,

          "This digraph has 1 strongly connected component");

    check(connected(g), "This graph is connected");

    check(countConnectedComponents(g) == 1,

          "This graph has 1 connected component");

    check(biNodeConnected(g), "This graph is bi-node-connected");

    check(countBiNodeConnectedComponents(g) == 0,

          "This graph has 0 bi-node-connected component");

    check(biEdgeConnected(g), "This graph is bi-edge-connected");

    check(countBiEdgeConnectedComponents(g) == 1,

          "This graph has 1 bi-edge-connected component");

    check(dag(d), "This digraph is DAG.");

    check(checkedTopologicalSort(d, order), "This digraph is DAG.");

    check(loopFree(d), "This digraph is loop-free.");

    check(parallelFree(d), "This digraph is parallel-free.");

    check(simpleGraph(d), "This digraph is simple.");

    check(acyclic(g), "This graph is acyclic.");

    check(tree(g), "This graph is tree.");

    check(bipartite(g), "This graph is bipartite.");

    check(loopFree(g), "This graph is loop-free.");

    check(parallelFree(g), "This graph is parallel-free.");

    check(simpleGraph(g), "This graph is simple.");

  }

  {

    Digraph d;

    Digraph::NodeMap<int> order(d);

    Graph g(d);

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

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

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

    Digraph::Node n4 = d.addNode();

    Digraph::Node n5 = d.addNode();

    Digraph::Node n6 = d.addNode();

    d.addArc(n1, n3);

    d.addArc(n3, n2);

    d.addArc(n2, n1);

    d.addArc(n4, n2);

    d.addArc(n4, n3);

    d.addArc(n5, n6);

    d.addArc(n6, n5);

    check(!stronglyConnected(d), "This digraph is not strongly connected");

    check(countStronglyConnectedComponents(d) == 3,

          "This digraph has 3 strongly connected components");

    check(!connected(g), "This graph is not connected");

    check(countConnectedComponents(g) == 2,

          "This graph has 2 connected components");

    check(!dag(d), "This digraph is not DAG.");

    check(!checkedTopologicalSort(d, order), "This digraph is not DAG.");

    check(loopFree(d), "This digraph is loop-free.");

    check(parallelFree(d), "This digraph is parallel-free.");

    check(simpleGraph(d), "This digraph is simple.");

    check(!acyclic(g), "This graph is not acyclic.");

    check(!tree(g), "This graph is not tree.");

    check(!bipartite(g), "This graph is not bipartite.");

    check(loopFree(g), "This graph is loop-free.");

    check(!parallelFree(g), "This graph is not parallel-free.");

    check(!simpleGraph(g), "This graph is not simple.");

    d.addArc(n3, n3);

    check(!loopFree(d), "This digraph is not loop-free.");

    check(!loopFree(g), "This graph is not loop-free.");

    check(!simpleGraph(d), "This digraph is not simple.");

    d.addArc(n3, n2);

    check(!parallelFree(d), "This digraph is not parallel-free.");

  }

  {

    Digraph d;

    Digraph::ArcMap<bool> cutarcs(d, false);

    Graph g(d);

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

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

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

    Digraph::Node n4 = d.addNode();

    Digraph::Node n5 = d.addNode();

    Digraph::Node n6 = d.addNode();

    Digraph::Node n7 = d.addNode();

    Digraph::Node n8 = d.addNode();

    d.addArc(n1, n2);

    d.addArc(n5, n1);

    d.addArc(n2, n8);

    d.addArc(n8, n5);

    d.addArc(n6, n4);

    d.addArc(n4, n6);

    d.addArc(n2, n5);

    d.addArc(n1, n8);

    d.addArc(n6, n7);

    d.addArc(n7, n6);

    check(!stronglyConnected(d), "This digraph is not strongly connected");

    check(countStronglyConnectedComponents(d) == 3,

          "This digraph has 3 strongly connected components");

    Digraph::NodeMap<int> scomp1(d);

    check(stronglyConnectedComponents(d, scomp1) == 3,

          "This digraph has 3 strongly connected components");

    check(scomp1[n1] != scomp1[n3] && scomp1[n1] != scomp1[n4] &&

          scomp1[n3] != scomp1[n4], "Wrong stronglyConnectedComponents()");

    check(scomp1[n1] == scomp1[n2] && scomp1[n1] == scomp1[n5] &&

          scomp1[n1] == scomp1[n8], "Wrong stronglyConnectedComponents()");

    check(scomp1[n4] == scomp1[n6] && scomp1[n4] == scomp1[n7],

          "Wrong stronglyConnectedComponents()");

    Digraph::ArcMap<bool> scut1(d, false);

    check(stronglyConnectedCutArcs(d, scut1) == 0,

          "This digraph has 0 strongly connected cut arc.");

    for (Digraph::ArcIt a(d); a != INVALID; ++a) {

      check(!scut1[a], "Wrong stronglyConnectedCutArcs()");

    }

    check(!connected(g), "This graph is not connected");

    check(countConnectedComponents(g) == 3,

          "This graph has 3 connected components");

    Graph::NodeMap<int> comp(g);

    check(connectedComponents(g, comp) == 3,

          "This graph has 3 connected components");

    check(comp[n1] != comp[n3] && comp[n1] != comp[n4] &&

          comp[n3] != comp[n4], "Wrong connectedComponents()");

    check(comp[n1] == comp[n2] && comp[n1] == comp[n5] &&

          comp[n1] == comp[n8], "Wrong connectedComponents()");

    check(comp[n4] == comp[n6] && comp[n4] == comp[n7],

          "Wrong connectedComponents()");

    cutarcs[d.addArc(n3, n1)] = true;

    cutarcs[d.addArc(n3, n5)] = true;

    cutarcs[d.addArc(n3, n8)] = true;

    cutarcs[d.addArc(n8, n6)] = true;

    cutarcs[d.addArc(n8, n7)] = true;

    check(!stronglyConnected(d), "This digraph is not strongly connected");

    check(countStronglyConnectedComponents(d) == 3,

          "This digraph has 3 strongly connected components");

    Digraph::NodeMap<int> scomp2(d);

    check(stronglyConnectedComponents(d, scomp2) == 3,

          "This digraph has 3 strongly connected components");

    check(scomp2[n3] == 0, "Wrong stronglyConnectedComponents()");

    check(scomp2[n1] == 1 && scomp2[n2] == 1 && scomp2[n5] == 1 &&

          scomp2[n8] == 1, "Wrong stronglyConnectedComponents()");

    check(scomp2[n4] == 2 && scomp2[n6] == 2 && scomp2[n7] == 2,

          "Wrong stronglyConnectedComponents()");

    Digraph::ArcMap<bool> scut2(d, false);

    check(stronglyConnectedCutArcs(d, scut2) == 5,

          "This digraph has 5 strongly connected cut arcs.");

    for (Digraph::ArcIt a(d); a != INVALID; ++a) {

      check(scut2[a] == cutarcs[a], "Wrong stronglyConnectedCutArcs()");

    }

  }

  {

    // DAG example for topological sort from the book New Algorithms

    // (T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein)

    Digraph d;

    Digraph::NodeMap<int> order(d);

    Digraph::Node belt = d.addNode();

    Digraph::Node trousers = d.addNode();

    Digraph::Node necktie = d.addNode();

    Digraph::Node coat = d.addNode();

    Digraph::Node socks = d.addNode();

    Digraph::Node shirt = d.addNode();

    Digraph::Node shoe = d.addNode();

    Digraph::Node watch = d.addNode();

    Digraph::Node pants = d.addNode();

    d.addArc(socks, shoe);

    d.addArc(pants, shoe);

    d.addArc(pants, trousers);

    d.addArc(trousers, shoe);

    d.addArc(trousers, belt);

    d.addArc(belt, coat);

    d.addArc(shirt, belt);

    d.addArc(shirt, necktie);

    d.addArc(necktie, coat);

    check(dag(d), "This digraph is DAG.");

    topologicalSort(d, order);

    for (Digraph::ArcIt a(d); a != INVALID; ++a) {

      check(order[d.source(a)] < order[d.target(a)],

            "Wrong topologicalSort()");

    }

  }

  {

    ListGraph g;

    ListGraph::NodeMap<bool> map(g);

    ListGraph::Node n1 = g.addNode();

    ListGraph::Node n2 = g.addNode();

    ListGraph::Node n3 = g.addNode();

    ListGraph::Node n4 = g.addNode();

    ListGraph::Node n5 = g.addNode();

    ListGraph::Node n6 = g.addNode();

    ListGraph::Node n7 = g.addNode();

    g.addEdge(n1, n3);

    g.addEdge(n1, n4);

    g.addEdge(n2, n5);

    g.addEdge(n3, n6);

    g.addEdge(n4, n6);

    g.addEdge(n4, n7);

    g.addEdge(n5, n7);

    check(bipartite(g), "This graph is bipartite");

    check(bipartitePartitions(g, map), "This graph is bipartite");

    check(map[n1] == map[n2] && map[n1] == map[n6] && map[n1] == map[n7],

          "Wrong bipartitePartitions()");

    check(map[n3] == map[n4] && map[n3] == map[n5],

          "Wrong bipartitePartitions()");

  }

  return 0;

}

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

    if (NodeIt(graph) == INVALID) return true;

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