source: lemon-0.x/lemon/topology.h @ 1740:4cade8579363

/* -*- C++ -*-
 * lemon/topology.h - Part of LEMON, a generic C++ optimization library
 *
 * Copyright (C) 2005 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.
 *
 */

#ifndef LEMON_TOPOLOGY_H
#define LEMON_TOPOLOGY_H

#include <lemon/dfs.h>
#include <lemon/bfs.h>
#include <lemon/graph_utils.h>

#include <lemon/concept/graph.h>
#include <lemon/concept/undir_graph.h>
#include <lemon/concept_check.h>

/// \ingroup flowalgs
/// \file
/// \brief Topology related algorithms
///
/// Topology related algorithms
///\todo Place the file contents is the module tree.

namespace lemon {

  namespace _topology_bits {
    
    template <typename NodeMap>
    class BackCounterMap {
    public:
      BackCounterMap(NodeMap& _nodeMap, int _counter)
        : nodeMap(_nodeMap), counter(_counter) {}

      void set(typename NodeMap::Key key, bool val) {
        if (val) {
          nodeMap.set(key, --counter);
        } else {
          nodeMap.set(key, -1);
        }
      }

      bool operator[](typename NodeMap::Key key) const {
        return nodeMap[key] != -1;
      }

    private:
      NodeMap& nodeMap;
      int counter;
    };
  }

  // \todo Its to special output // ReadWriteMap
  template <typename Graph, typename NodeMap>
  bool topological_sort(const Graph& graph, NodeMap& nodeMap) {
    using namespace _topology_bits;

    checkConcept<concept::StaticGraph, Graph>();
    checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();

    typedef typename Graph::Node Node;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::Edge Edge;

    typedef BackCounterMap<NodeMap> ProcessedMap;

    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
      Create dfs(graph);

    ProcessedMap processed(nodeMap, countNodes(graph));

    dfs.processedMap(processed);
    dfs.init();
    for (NodeIt it(graph); it != INVALID; ++it) {
      if (!dfs.reached(it)) {
        dfs.addSource(it);
        while (!dfs.emptyQueue()) {
          Edge edge = dfs.nextEdge();
          Node target = graph.target(edge);
          if (dfs.reached(target) && !processed[target]) {
            return false;
          }
          dfs.processNextEdge();
        }
      }
    }    
    return true;
  }

  /// \brief Check that the given graph is a DAG.
  ///
  /// Check that the given graph is a DAG. The DAG is
  /// an Directed Acyclic Graph.
  template <typename Graph>
  bool dag(const Graph& graph) {

    checkConcept<concept::StaticGraph, Graph>();

    typedef typename Graph::Node Node;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::Edge Edge;

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

    typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
      Create dfs(graph);

    ProcessedMap processed(graph);
    dfs.processedMap(processed);

    dfs.init();
    for (NodeIt it(graph); it != INVALID; ++it) {
      if (!dfs.reached(it)) {
        dfs.addSource(it);
        while (!dfs.emptyQueue()) {
          Edge edge = dfs.nextEdge();
          Node target = graph.target(edge);
          if (dfs.reached(target) && !processed[target]) {
            return false;
          }
          dfs.processNextEdge();
        }
      }
    }    
    return true;
  }

  // UndirGraph algorithms

  /// \brief Check that the given undirected graph is connected.
  ///
  /// Check that the given undirected graph connected.
  template <typename UndirGraph>
  bool connected(const UndirGraph& graph) {
    checkConcept<concept::UndirGraph, UndirGraph>();
    typedef typename UndirGraph::NodeIt NodeIt;
    if (NodeIt(graph) == INVALID) return false;
    Dfs<UndirGraph> dfs(graph);
    dfs.run(NodeIt(graph));
    for (NodeIt it(graph); it != INVALID; ++it) {
      if (!dfs.reached(it)) {
        return false;
      }
    }
    return true;
  }

  /// \brief Check that the given undirected graph is acyclic.
  ///
  /// Check that the given undirected graph acyclic.
  template <typename UndirGraph>
  bool acyclic(const UndirGraph& graph) {
    checkConcept<concept::UndirGraph, UndirGraph>();
    typedef typename UndirGraph::Node Node;
    typedef typename UndirGraph::NodeIt NodeIt;
    typedef typename UndirGraph::Edge Edge;
    Dfs<UndirGraph> dfs(graph);
    dfs.init();
    for (NodeIt it(graph); it != INVALID; ++it) {
      if (!dfs.reached(it)) {
        dfs.addSource(it);
        while (!dfs.emptyQueue()) {
          Edge edge = dfs.nextEdge();
          Node source = graph.source(edge);
          Node target = graph.target(edge);
          if (dfs.reached(target) && 
              dfs.pred(source) != graph.oppositeEdge(edge)) {
            return false;
          }
          dfs.processNextEdge();
        }
      }
    }
    return true;
  }

  /// \brief Check that the given undirected graph is tree.
  ///
  /// Check that the given undirected graph is tree.
  template <typename UndirGraph>
  bool tree(const UndirGraph& graph) {
    checkConcept<concept::UndirGraph, UndirGraph>();
    typedef typename UndirGraph::Node Node;
    typedef typename UndirGraph::NodeIt NodeIt;
    typedef typename UndirGraph::Edge Edge;
    if (NodeIt(graph) == INVALID) return false;
    Dfs<UndirGraph> dfs(graph);
    dfs.init();
    dfs.addSource(NodeIt(graph));
    while (!dfs.emptyQueue()) {
      Edge edge = dfs.nextEdge();
      Node source = graph.source(edge);
      Node target = graph.target(edge);
      if (dfs.reached(target) && 
          dfs.pred(source) != graph.oppositeEdge(edge)) {
        return false;
      }
      dfs.processNextEdge();
    }
    for (NodeIt it(graph); it != INVALID; ++it) {
      if (!dfs.reached(it)) {
        return false;
      }
    }    
    return true;
  }
 
  ///Count the number of connected components of an undirected graph

  ///Count the number of connected components of an undirected graph
  ///
  ///\param g The graph. In must be undirected.
  ///\return The number of components
  template <class UndirGraph>
  int countConnectedComponents(const UndirGraph &g) {
    checkConcept<concept::UndirGraph, UndirGraph>();
    int c = 0;
    Bfs<UndirGraph> bfs(g);
    bfs.init();
    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
      if(!bfs.reached(n)) {
        bfs.addSource(n);
        bfs.start();
        ++c;
      }
    }
    return c;
  }


  ///Find the connected components of an undirected graph

  ///Find the connected components of an undirected graph
  ///
  ///\param g The graph. In must be undirected.
  ///\retval comp A writable node map. The values will be set from 0 to
  ///the number of the connected 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
  ///\todo Test required
  template <class UndirGraph, class IntNodeMap>
  int connectedComponents(const UndirGraph &g, IntNodeMap &comp) {
    checkConcept<concept::UndirGraph, UndirGraph>();
    checkConcept<concept::WriteMap<typename UndirGraph::Node, int>, 
      IntNodeMap>();
    int c = 0;
    Bfs<UndirGraph> bfs(g);
    bfs.init();
    for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
      if(!bfs.reached(n)) {
        bfs.addSource(n);
        while (!bfs.emptyQueue()) {
          comp[bfs.nextNode()] = c;
          bfs.processNextNode();
        }
        ++c;
      }
    }
    return c;
  }

  namespace _components_bits {

    template <typename Key, typename IntMap>
    struct FillWriteMap : public MapBase<Key, bool> {
    public:
      FillWriteMap(IntMap& _map, int& _comp) 
        : map(_map), comp(_comp) {}
      void set(Key key, bool value) {
        if (value) { map.set(key, comp); }
      }
    private:
      IntMap& map;
      int& comp;
    };

    template <typename Key, typename Container = std::vector<Key> >
    struct BackInserterWriteMap : public MapBase<Key, bool> {
    public:
      BackInserterWriteMap(Container& _container) 
        : container(_container) {}
      void set(Key key, bool value) {
        if (value) { container.push_back(key); }
      }
    private:
      Container& container;
    };

  }

  /// \brief Count the strongly connected components of a directed graph
  ///
  /// Count the strongly connected components of a directed graph
  ///
  /// \param g The graph.
  /// \return The number of components
  template <typename Graph>
  int countStronglyConnectedComponents(const Graph& graph) {
    checkConcept<concept::StaticGraph, Graph>();

    using namespace _components_bits;

    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EdgeIt EdgeIt;
    

    typename Dfs<Graph>::
      template DefProcessedMap<BackInserterWriteMap<Node> >::
      Create dfs(graph);

    std::vector<Node> nodes;
    BackInserterWriteMap<Node> processed(nodes);
    dfs.processedMap(processed);

    dfs.init();
    for (NodeIt it(graph); it != INVALID; ++it) {
      if (!dfs.reached(it)) {
        dfs.addSource(it);
        dfs.start();
      }
    }

    typedef RevGraphAdaptor<const Graph> RGraph;

    RGraph rgraph(graph);

    Dfs<RGraph> rdfs(rgraph);

    int num = 0;

    rdfs.init();
    for (typename std::vector<Node>::reverse_iterator 
           it = nodes.rbegin(); it != nodes.rend(); ++it) {
      if (!rdfs.reached(*it)) {
        rdfs.addSource(*it);
        rdfs.start();
        ++num;
      }
    }
    return num;
  }

  /// \brief Find the strongly connected components of a directed graph
  ///
  /// Find the strongly connected components of a directed graph
  ///
  /// \param g The graph.
  /// \retval comp A writable node map. The values will be set from 0 to
  /// the number of the strongly connected 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 IntNodeMap>
  int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) {
    checkConcept<concept::StaticGraph, Graph>();
    checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>();

    using namespace _components_bits;

    typedef typename Graph::Node Node;
    typedef typename Graph::Edge Edge;
    typedef typename Graph::NodeIt NodeIt;
    typedef typename Graph::EdgeIt EdgeIt;
    

    typename Dfs<Graph>::
      template DefProcessedMap<BackInserterWriteMap<Node> >::
      Create dfs(graph);

    std::vector<Node> nodes;
    BackInserterWriteMap<Node> processed(nodes);
    dfs.processedMap(processed);

    dfs.init();
    for (NodeIt it(graph); it != INVALID; ++it) {
      if (!dfs.reached(it)) {
        dfs.addSource(it);
        dfs.start();
      }
    }

    typedef RevGraphAdaptor<const Graph> RGraph;

    RGraph rgraph(graph);

    typename Dfs<RGraph>::
      template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >::
      Create rdfs(rgraph);

    int num = 0;
    FillWriteMap<Node, IntNodeMap> rprocessed(comp, num);
    rdfs.processedMap(rprocessed);

    rdfs.init();
    for (typename std::vector<Node>::reverse_iterator 
           it = nodes.rbegin(); it != nodes.rend(); ++it) {
      if (!rdfs.reached(*it)) {
        rdfs.addSource(*it);
        rdfs.start();
        ++num;
      }
    }
    return num;
  }

} //namespace lemon

#endif //LEMON_TOPOLOGY_H