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