/* -*- 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