source: lemon-0.x/lemon/topology.h @ 1739:b1385f5da81b

/* -*- 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/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
  ///\todo Test required
  template<class UGraph>
  int numberOfComponents(const UGraph &g)
  {
    int c=0;
    Bfs<Graph> bfs(g);
    bfs.init();
    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
      if(!bfs.reached(n)) {
        c++;
        bfs.addSource(n);
        bfs.start();
      }
    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 UGraph, class WMap>
  int connectedComponents(const UGraph &g, WMap &comp)
  {
    int c=0;
    Bfs<Graph> bfs(g);
    bfs.init();
    for(typename Graph::NodeIt n(g);n!=INVALID;++n)
      if(!bfs.reached(n)) {
        bfs.addSource(n);
        while ( bfs.nextNode()!=INVALID ) {
          comp[bfs.nextNode()]=c;
          processNextNode();
          c++;
      }
    return c;
  }

} //namespace lemon

#endif //LEMON_TOPOLOGY_H