deba@1698: /* -*- C++ -*-
deba@1698:  * lemon/topology.h - Part of LEMON, a generic C++ optimization library
deba@1698:  *
deba@1698:  * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
deba@1698:  * (Egervary Research Group on Combinatorial Optimization, EGRES).
deba@1698:  *
deba@1698:  * Permission to use, modify and distribute this software is granted
deba@1698:  * provided that this copyright notice appears in all copies. For
deba@1698:  * precise terms see the accompanying LICENSE file.
deba@1698:  *
deba@1698:  * This software is provided "AS IS" with no warranty of any kind,
deba@1698:  * express or implied, and with no claim as to its suitability for any
deba@1698:  * purpose.
deba@1698:  *
deba@1698:  */
deba@1698: 
deba@1698: #ifndef LEMON_TOPOLOGY_H
deba@1698: #define LEMON_TOPOLOGY_H
deba@1698: 
deba@1698: #include <lemon/dfs.h>
deba@1740: #include <lemon/bfs.h>
deba@1698: #include <lemon/graph_utils.h>
deba@1698: 
deba@1698: #include <lemon/concept/graph.h>
deba@1698: #include <lemon/concept/undir_graph.h>
deba@1698: #include <lemon/concept_check.h>
deba@1698: 
deba@1698: /// \ingroup flowalgs
deba@1698: /// \file
deba@1698: /// \brief Topology related algorithms
deba@1698: ///
deba@1698: /// Topology related algorithms
alpar@1739: ///\todo Place the file contents is the module tree.
deba@1698: 
deba@1698: namespace lemon {
deba@1698: 
deba@1698:   namespace _topology_bits {
deba@1698:     
deba@1698:     template <typename NodeMap>
deba@1698:     class BackCounterMap {
deba@1698:     public:
deba@1698:       BackCounterMap(NodeMap& _nodeMap, int _counter)
deba@1698: 	: nodeMap(_nodeMap), counter(_counter) {}
deba@1698: 
deba@1698:       void set(typename NodeMap::Key key, bool val) {
deba@1698: 	if (val) {
deba@1698: 	  nodeMap.set(key, --counter);
deba@1698: 	} else {
deba@1698: 	  nodeMap.set(key, -1);
deba@1698: 	}
deba@1698:       }
deba@1698: 
deba@1698:       bool operator[](typename NodeMap::Key key) const {
deba@1698: 	return nodeMap[key] != -1;
deba@1698:       }
deba@1698: 
deba@1698:     private:
deba@1698:       NodeMap& nodeMap;
deba@1698:       int counter;
deba@1698:     };
deba@1698:   }
deba@1698: 
deba@1698:   // \todo Its to special output // ReadWriteMap
deba@1698:   template <typename Graph, typename NodeMap>
deba@1698:   bool topological_sort(const Graph& graph, NodeMap& nodeMap) {
deba@1698:     using namespace _topology_bits;
deba@1698: 
deba@1698:     checkConcept<concept::StaticGraph, Graph>();
deba@1698:     checkConcept<concept::ReadWriteMap<typename Graph::Node, int>, NodeMap>();
deba@1698: 
deba@1698:     typedef typename Graph::Node Node;
deba@1698:     typedef typename Graph::NodeIt NodeIt;
deba@1698:     typedef typename Graph::Edge Edge;
deba@1698: 
deba@1698:     typedef BackCounterMap<NodeMap> ProcessedMap;
deba@1698: 
deba@1698:     typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
deba@1709:       Create dfs(graph);
deba@1698: 
deba@1698:     ProcessedMap processed(nodeMap, countNodes(graph));
deba@1698: 
deba@1698:     dfs.processedMap(processed);
deba@1698:     dfs.init();
deba@1698:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698:       if (!dfs.reached(it)) {
deba@1698: 	dfs.addSource(it);
deba@1698: 	while (!dfs.emptyQueue()) {
deba@1698: 	  Edge edge = dfs.nextEdge();
deba@1698: 	  Node target = graph.target(edge);
deba@1698: 	  if (dfs.reached(target) && !processed[target]) {
deba@1698: 	    return false;
deba@1698: 	  }
deba@1698: 	  dfs.processNextEdge();
deba@1698: 	}
deba@1698:       }
deba@1698:     }    
deba@1698:     return true;
deba@1698:   }
deba@1698: 
deba@1698:   /// \brief Check that the given graph is a DAG.
deba@1698:   ///
deba@1698:   /// Check that the given graph is a DAG. The DAG is
deba@1698:   /// an Directed Acyclic Graph.
deba@1698:   template <typename Graph>
deba@1698:   bool dag(const Graph& graph) {
deba@1698: 
deba@1698:     checkConcept<concept::StaticGraph, Graph>();
deba@1698: 
deba@1698:     typedef typename Graph::Node Node;
deba@1698:     typedef typename Graph::NodeIt NodeIt;
deba@1698:     typedef typename Graph::Edge Edge;
deba@1698: 
deba@1698:     typedef typename Graph::template NodeMap<bool> ProcessedMap;
deba@1698: 
deba@1698:     typename Dfs<Graph>::template DefProcessedMap<ProcessedMap>::
deba@1709:       Create dfs(graph);
deba@1698: 
deba@1698:     ProcessedMap processed(graph);
deba@1698:     dfs.processedMap(processed);
deba@1698: 
deba@1698:     dfs.init();
deba@1698:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698:       if (!dfs.reached(it)) {
deba@1698: 	dfs.addSource(it);
deba@1698: 	while (!dfs.emptyQueue()) {
deba@1698: 	  Edge edge = dfs.nextEdge();
deba@1698: 	  Node target = graph.target(edge);
deba@1698: 	  if (dfs.reached(target) && !processed[target]) {
deba@1698: 	    return false;
deba@1698: 	  }
deba@1698: 	  dfs.processNextEdge();
deba@1698: 	}
deba@1698:       }
deba@1698:     }    
deba@1698:     return true;
deba@1698:   }
deba@1698: 
deba@1698:   // UndirGraph algorithms
deba@1698: 
deba@1698:   /// \brief Check that the given undirected graph is connected.
deba@1698:   ///
deba@1698:   /// Check that the given undirected graph connected.
deba@1698:   template <typename UndirGraph>
deba@1698:   bool connected(const UndirGraph& graph) {
deba@1698:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1698:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1698:     if (NodeIt(graph) == INVALID) return false;
deba@1698:     Dfs<UndirGraph> dfs(graph);
deba@1698:     dfs.run(NodeIt(graph));
deba@1698:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698:       if (!dfs.reached(it)) {
deba@1698: 	return false;
deba@1698:       }
deba@1698:     }
deba@1698:     return true;
deba@1698:   }
deba@1698: 
deba@1698:   /// \brief Check that the given undirected graph is acyclic.
deba@1698:   ///
deba@1698:   /// Check that the given undirected graph acyclic.
deba@1698:   template <typename UndirGraph>
deba@1698:   bool acyclic(const UndirGraph& graph) {
deba@1698:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1698:     typedef typename UndirGraph::Node Node;
deba@1698:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1698:     typedef typename UndirGraph::Edge Edge;
deba@1698:     Dfs<UndirGraph> dfs(graph);
deba@1698:     dfs.init();
deba@1698:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698:       if (!dfs.reached(it)) {
deba@1698: 	dfs.addSource(it);
deba@1698: 	while (!dfs.emptyQueue()) {
deba@1698: 	  Edge edge = dfs.nextEdge();
deba@1698: 	  Node source = graph.source(edge);
deba@1698: 	  Node target = graph.target(edge);
deba@1698: 	  if (dfs.reached(target) && 
deba@1698: 	      dfs.pred(source) != graph.oppositeEdge(edge)) {
deba@1698: 	    return false;
deba@1698: 	  }
deba@1698: 	  dfs.processNextEdge();
deba@1698: 	}
deba@1698:       }
deba@1698:     }
deba@1698:     return true;
deba@1698:   }
deba@1698: 
deba@1698:   /// \brief Check that the given undirected graph is tree.
deba@1698:   ///
deba@1698:   /// Check that the given undirected graph is tree.
deba@1698:   template <typename UndirGraph>
deba@1698:   bool tree(const UndirGraph& graph) {
deba@1698:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1698:     typedef typename UndirGraph::Node Node;
deba@1698:     typedef typename UndirGraph::NodeIt NodeIt;
deba@1698:     typedef typename UndirGraph::Edge Edge;
deba@1698:     if (NodeIt(graph) == INVALID) return false;
deba@1698:     Dfs<UndirGraph> dfs(graph);
deba@1698:     dfs.init();
deba@1698:     dfs.addSource(NodeIt(graph));
deba@1698:     while (!dfs.emptyQueue()) {
deba@1698:       Edge edge = dfs.nextEdge();
deba@1698:       Node source = graph.source(edge);
deba@1698:       Node target = graph.target(edge);
deba@1698:       if (dfs.reached(target) && 
deba@1698: 	  dfs.pred(source) != graph.oppositeEdge(edge)) {
deba@1698: 	return false;
deba@1698:       }
deba@1698:       dfs.processNextEdge();
deba@1698:     }
deba@1698:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1698:       if (!dfs.reached(it)) {
deba@1698: 	return false;
deba@1698:       }
deba@1698:     }    
deba@1698:     return true;
deba@1698:   }
deba@1698:  
alpar@1739:   ///Count the number of connected components of an undirected graph
alpar@1739: 
alpar@1739:   ///Count the number of connected components of an undirected graph
alpar@1739:   ///
alpar@1739:   ///\param g The graph. In must be undirected.
alpar@1739:   ///\return The number of components
deba@1740:   template <class UndirGraph>
deba@1740:   int countConnectedComponents(const UndirGraph &g) {
deba@1740:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1740:     int c = 0;
deba@1740:     Bfs<UndirGraph> bfs(g);
alpar@1739:     bfs.init();
deba@1740:     for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
alpar@1739:       if(!bfs.reached(n)) {
alpar@1739: 	bfs.addSource(n);
alpar@1739: 	bfs.start();
deba@1740: 	++c;
alpar@1739:       }
deba@1740:     }
alpar@1739:     return c;
alpar@1739:   }
alpar@1739: 
alpar@1739: 
alpar@1739:   ///Find the connected components of an undirected graph
alpar@1739: 
alpar@1739:   ///Find the connected components of an undirected graph
alpar@1739:   ///
alpar@1739:   ///\param g The graph. In must be undirected.
alpar@1739:   ///\retval comp A writable node map. The values will be set from 0 to
alpar@1739:   ///the number of the connected components minus one. Each values of the map
alpar@1739:   ///will be set exactly once, the values of a certain component will be
alpar@1739:   ///set continuously.
alpar@1739:   ///\return The number of components
alpar@1739:   ///\todo Test required
deba@1740:   template <class UndirGraph, class IntNodeMap>
deba@1740:   int connectedComponents(const UndirGraph &g, IntNodeMap &comp) {
deba@1740:     checkConcept<concept::UndirGraph, UndirGraph>();
deba@1740:     checkConcept<concept::WriteMap<typename UndirGraph::Node, int>, 
deba@1740:       IntNodeMap>();
deba@1740:     int c = 0;
deba@1740:     Bfs<UndirGraph> bfs(g);
alpar@1739:     bfs.init();
deba@1740:     for(typename UndirGraph::NodeIt n(g); n != INVALID; ++n) {
alpar@1739:       if(!bfs.reached(n)) {
alpar@1739: 	bfs.addSource(n);
deba@1740: 	while (!bfs.emptyQueue()) {
deba@1740: 	  comp[bfs.nextNode()] = c;
deba@1740: 	  bfs.processNextNode();
deba@1740: 	}
deba@1740: 	++c;
alpar@1739:       }
deba@1740:     }
alpar@1739:     return c;
alpar@1739:   }
deba@1698: 
deba@1740:   namespace _components_bits {
deba@1740: 
deba@1740:     template <typename Key, typename IntMap>
deba@1740:     struct FillWriteMap : public MapBase<Key, bool> {
deba@1740:     public:
deba@1740:       FillWriteMap(IntMap& _map, int& _comp) 
deba@1740: 	: map(_map), comp(_comp) {}
deba@1740:       void set(Key key, bool value) {
deba@1740: 	if (value) { map.set(key, comp); }
deba@1740:       }
deba@1740:     private:
deba@1740:       IntMap& map;
deba@1740:       int& comp;
deba@1740:     };
deba@1740: 
deba@1740:     template <typename Key, typename Container = std::vector<Key> >
deba@1740:     struct BackInserterWriteMap : public MapBase<Key, bool> {
deba@1740:     public:
deba@1740:       BackInserterWriteMap(Container& _container) 
deba@1740: 	: container(_container) {}
deba@1740:       void set(Key key, bool value) {
deba@1740: 	if (value) { container.push_back(key); }
deba@1740:       }
deba@1740:     private:
deba@1740:       Container& container;
deba@1740:     };
deba@1740: 
deba@1740:   }
deba@1740: 
deba@1740:   /// \brief Count the strongly connected components of a directed graph
deba@1740:   ///
deba@1740:   /// Count the strongly connected components of a directed graph
deba@1740:   ///
deba@1740:   /// \param g The graph.
deba@1740:   /// \return The number of components
deba@1740:   template <typename Graph>
deba@1740:   int countStronglyConnectedComponents(const Graph& graph) {
deba@1740:     checkConcept<concept::StaticGraph, Graph>();
deba@1740: 
deba@1740:     using namespace _components_bits;
deba@1740: 
deba@1740:     typedef typename Graph::Node Node;
deba@1740:     typedef typename Graph::Edge Edge;
deba@1740:     typedef typename Graph::NodeIt NodeIt;
deba@1740:     typedef typename Graph::EdgeIt EdgeIt;
deba@1740:     
deba@1740: 
deba@1740:     typename Dfs<Graph>::
deba@1740:       template DefProcessedMap<BackInserterWriteMap<Node> >::
deba@1740:       Create dfs(graph);
deba@1740: 
deba@1740:     std::vector<Node> nodes;
deba@1740:     BackInserterWriteMap<Node> processed(nodes);
deba@1740:     dfs.processedMap(processed);
deba@1740: 
deba@1740:     dfs.init();
deba@1740:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1740:       if (!dfs.reached(it)) {
deba@1740: 	dfs.addSource(it);
deba@1740: 	dfs.start();
deba@1740:       }
deba@1740:     }
deba@1740: 
deba@1740:     typedef RevGraphAdaptor<const Graph> RGraph;
deba@1740: 
deba@1740:     RGraph rgraph(graph);
deba@1740: 
deba@1740:     Dfs<RGraph> rdfs(rgraph);
deba@1740: 
deba@1740:     int num = 0;
deba@1740: 
deba@1740:     rdfs.init();
deba@1740:     for (typename std::vector<Node>::reverse_iterator 
deba@1740: 	   it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@1740:       if (!rdfs.reached(*it)) {
deba@1740: 	rdfs.addSource(*it);
deba@1740: 	rdfs.start();
deba@1740: 	++num;
deba@1740:       }
deba@1740:     }
deba@1740:     return num;
deba@1740:   }
deba@1740: 
deba@1740:   /// \brief Find the strongly connected components of a directed graph
deba@1740:   ///
deba@1740:   /// Find the strongly connected components of a directed graph
deba@1740:   ///
deba@1740:   /// \param g The graph.
deba@1740:   /// \retval comp A writable node map. The values will be set from 0 to
deba@1740:   /// the number of the strongly connected components minus one. Each values 
deba@1740:   /// of the map will be set exactly once, the values of a certain component 
deba@1740:   /// will be set continuously.
deba@1740:   /// \return The number of components
deba@1740:   template <typename Graph, typename IntNodeMap>
deba@1740:   int stronglyConnectedComponents(const Graph& graph, IntNodeMap& comp) {
deba@1740:     checkConcept<concept::StaticGraph, Graph>();
deba@1740:     checkConcept<concept::WriteMap<typename Graph::Node, int>, IntNodeMap>();
deba@1740: 
deba@1740:     using namespace _components_bits;
deba@1740: 
deba@1740:     typedef typename Graph::Node Node;
deba@1740:     typedef typename Graph::Edge Edge;
deba@1740:     typedef typename Graph::NodeIt NodeIt;
deba@1740:     typedef typename Graph::EdgeIt EdgeIt;
deba@1740:     
deba@1740: 
deba@1740:     typename Dfs<Graph>::
deba@1740:       template DefProcessedMap<BackInserterWriteMap<Node> >::
deba@1740:       Create dfs(graph);
deba@1740: 
deba@1740:     std::vector<Node> nodes;
deba@1740:     BackInserterWriteMap<Node> processed(nodes);
deba@1740:     dfs.processedMap(processed);
deba@1740: 
deba@1740:     dfs.init();
deba@1740:     for (NodeIt it(graph); it != INVALID; ++it) {
deba@1740:       if (!dfs.reached(it)) {
deba@1740: 	dfs.addSource(it);
deba@1740: 	dfs.start();
deba@1740:       }
deba@1740:     }
deba@1740: 
deba@1740:     typedef RevGraphAdaptor<const Graph> RGraph;
deba@1740: 
deba@1740:     RGraph rgraph(graph);
deba@1740: 
deba@1740:     typename Dfs<RGraph>::
deba@1740:       template DefProcessedMap<FillWriteMap<Node, IntNodeMap> >::
deba@1740:       Create rdfs(rgraph);
deba@1740: 
deba@1740:     int num = 0;
deba@1740:     FillWriteMap<Node, IntNodeMap> rprocessed(comp, num);
deba@1740:     rdfs.processedMap(rprocessed);
deba@1740: 
deba@1740:     rdfs.init();
deba@1740:     for (typename std::vector<Node>::reverse_iterator 
deba@1740: 	   it = nodes.rbegin(); it != nodes.rend(); ++it) {
deba@1740:       if (!rdfs.reached(*it)) {
deba@1740: 	rdfs.addSource(*it);
deba@1740: 	rdfs.start();
deba@1740: 	++num;
deba@1740:       }
deba@1740:     }
deba@1740:     return num;
deba@1740:   }
deba@1740: 
deba@1698: } //namespace lemon
deba@1698: 
deba@1698: #endif //LEMON_TOPOLOGY_H