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

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;

  }

} //namespace lemon

#endif //LEMON_TOPOLOGY_H