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