/* -*- C++ -*-

  *

  * This file is a part of LEMON, a generic C++ optimization library

  *

  * Copyright (C) 2003-2006

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

 #define LEMON_FREDMAN_TARJAN_H

 ///\ingroup spantree

 ///\file

 ///\brief FredmanTarjan algorithm to compute minimum spanning forest.

 #include <limits>

 #include <vector>

 #include <lemon/list_graph.h>

 #include <lemon/smart_graph.h>

 #include <lemon/fib_heap.h>

 #include <lemon/radix_sort.h>

 #include <lemon/bits/invalid.h>

 #include <lemon/error.h>

 #include <lemon/maps.h>

 #include <lemon/bits/traits.h>

 #include <lemon/graph_utils.h>

 #include <lemon/concept/ugraph.h>

 namespace lemon {

   ///Default traits class of FredmanTarjan class.

   ///Default traits class of FredmanTarjan class.

   ///\param GR Graph type.

   ///\param CM Type of cost map.

   template<class GR, class CM>

   struct FredmanTarjanDefaultTraits{

     ///The graph type the algorithm runs on. 

     typedef GR UGraph;

     ///The type of the map that stores the edge costs.

     ///The type of the map that stores the edge costs.

     ///It must meet the \ref concept::ReadMap "ReadMap" concept.

     typedef CM CostMap;

     //The type of the cost of the edges.

     typedef typename CM::Value Value;

     ///The type of the map that stores whether an edge is in the

     ///spanning tree or not.

     ///The type of the map that stores whether an edge is in the

     ///spanning tree or not.

     ///It must meet the \ref concept::ReadWriteMap "ReadWriteMap" concept.

     ///By default it is a BoolEdgeMap.

     typedef typename UGraph::template UEdgeMap<bool> TreeMap;

     ///Instantiates a TreeMap.

     ///This function instantiates a \ref TreeMap.

     ///\param _graph is the graph, to which

     ///we would like to define the \ref TreeMap

     static TreeMap *createTreeMap(const GR &_graph){

       return new TreeMap(_graph);

     }

   };

   ///%FredmanTarjan algorithm class to find a minimum spanning tree.

   /// \ingroup spantree 

   ///

   ///This class provides an efficient implementation of %FredmanTarjan

   ///algorithm whitch is sometimes a bit quicker than the Prim

   ///algorithm on larger graphs.  Due to the structure of the

   ///algorithm, it has less controll functions than Prim.

   ///

   /// The running time is \f$ O(e\beta(e,n)) \f$ where 

   /// \f$ \beta(e,n) = \min\{ i | \log^{i}(n) \le e/n\} \f$ and 

   /// \f$ \log^{i+1}(n)=\log(\log^{i}(n)) \f$

   ///

   ///The edge costs are passed to the algorithm using a \ref

   ///concept::ReadMap "ReadMap", so it is easy to change it to any

   ///kind of cost.

   ///

   ///The type of the cost is determined by the \ref

   ///concept::ReadMap::Value "Value" of the cost map.

   ///

   ///\param GR The graph type the algorithm runs on. The default value

   ///is \ref ListUGraph. The value of GR is not used directly by

   ///FredmanTarjan, it is only passed to \ref

   ///FredmanTarjanDefaultTraits.

   ///

   ///\param CM This read-only UEdgeMap determines the costs of the

   ///edges. It is read once for each edge, so the map may involve in

   ///relatively time consuming process to compute the edge cost if it

   ///is necessary. The default map type is \ref

   ///concept::UGraph::UEdgeMap "UGraph::UEdgeMap<int>". The value of

   ///CM is not used directly by FredmanTarjan, it is only passed to

   ///\ref FredmanTarjanDefaultTraits.

   ///

   ///\param TR Traits class to set various data types used by the

   ///algorithm.  The default traits class is \ref

   ///FredmanTarjanDefaultTraits "FredmanTarjanDefaultTraits<GR,CM>".

   ///See \ref FredmanTarjanDefaultTraits for the documentation of a

   ///FredmanTarjan traits class.

   ///

   ///\author Balazs Attila Mihaly

 #ifdef DOXYGEN

   template <typename GR,

 	    typename CM,

 	    typename TR>

 #else

   template <typename GR=ListUGraph,

 	    typename CM=typename GR::template UEdgeMap<int>,

 	    typename TR=FredmanTarjanDefaultTraits<GR,CM> >

 #endif

   class FredmanTarjan {

   public:

     ///\brief \ref Exception for uninitialized parameters.

     ///

     ///This error represents problems in the initialization

     ///of the parameters of the algorithms.

     class UninitializedParameter : public lemon::UninitializedParameter {

     public:

       virtual const char* exceptionName() const {

 	return "lemon::FredmanTarjan::UninitializedParameter";

       }

     };

     typedef GR Graph;

     typedef TR Traits;

     ///The type of the underlying graph.

     typedef typename TR::UGraph UGraph;

     ///\e

     typedef typename UGraph::Node Node;

     ///\e

     typedef typename UGraph::NodeIt NodeIt;

     ///\e

     typedef typename UGraph::UEdge UEdge;

     ///\e

     typedef typename UGraph::UEdgeIt UEdgeIt;

     ///\e

     typedef typename UGraph::IncEdgeIt IncEdgeIt;

     ///The type of the cost of the edges.

     typedef typename TR::CostMap::Value Value;

     ///The type of the map that stores the edge costs.

     typedef typename TR::CostMap CostMap;

     ///Edges of the spanning tree.

     typedef typename TR::TreeMap TreeMap;

   private:

     ///Pointer to the underlying graph.

     const UGraph *graph;

     ///Pointer to the cost map

     const CostMap *cost;

     ///Pointer to the map of tree edges.

     TreeMap *_tree;

     ///Indicates if \ref _tree is locally allocated (\c true) or not.

     bool local_tree;

     ///Creates the maps if necessary.

     void create_maps(){

       if(!_tree){

 	local_tree=true;

 	_tree=Traits::createTreeMap(*graph);

       }

     }

   public :

     typedef FredmanTarjan Create;

     ///\name Named template parameters

     ///@{

     template <class TM>

     struct DefTreeMapTraits : public Traits {

       typedef TM TreeMap;

       static TreeMap *createTreeMap(const UGraph &) {

 	throw UninitializedParameter();

       }

     };

     ///\ref named-templ-param "Named parameter" for setting TreeMap 

     ///\ref named-templ-param "Named parameter" for setting TreeMap

     ///

     template <class TM>

     struct DefTreeMap

       : public FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > { 

       typedef FredmanTarjan< UGraph, CostMap, DefTreeMapTraits<TM> > Create;

     };

     ///@}

   protected:

     FredmanTarjan() {}

   private:

     template<class SrcGraph,class OrigMap,class Heap,class HeapCrossRef,

              class ProcessedMap,class PredMap>

     void processNextTree(const SrcGraph& graph,const OrigMap& orig,

                          Heap &heap, HeapCrossRef& crossref,

                          ProcessedMap& processed,PredMap& pred,

                          int& tree_counter,const int limit){

       std::vector<typename SrcGraph::Node> tree_nodes;

       int tree_index=tree_counter;

       bool stop=false;

       while(!heap.empty() && !stop){

         typename SrcGraph::Node v=heap.top();

         heap.pop();

 	if(processed[v]!=-1){

 	  heap.state(v,Heap::PRE_HEAP);

 	  tree_index=processed[v];

 	  _tree->set(orig[pred[v]],true);

 	  stop=true;

 	  break;

         }

 	tree_nodes.push_back(v);

 	for(typename SrcGraph::IncEdgeIt e(graph,v);e!=INVALID;++e){

 	  typename SrcGraph::Node w=graph.oppositeNode(v,e);

 	  switch(heap.state(w)){

 	  case Heap::PRE_HEAP:

 	    if(heap.size()>=limit){

 	      stop=true;

 	    }

 	    else{

 	      heap.push(w,(*cost)[orig[e]]);

 	      pred.set(w,e);

 	    }

 	    break;

 	  case Heap::IN_HEAP:

 	    if ((*cost)[orig[e]]<heap[w]){

 	      heap.decrease(w,(*cost)[orig[e]]); 

 	      pred.set(w,e);

 	    }

 	    break;

 	  case Heap::POST_HEAP:

 	    break;

 	  }

 	}

       }

       for(int i=1;i<(int)tree_nodes.size();++i){

 	_tree->set(orig[pred[tree_nodes[i]]],true);

         processed.set(tree_nodes[i],tree_index);

         crossref[tree_nodes[i]] = Heap::PRE_HEAP;

       }

       processed.set(tree_nodes[0],tree_index);

       crossref[tree_nodes[0]] = Heap::PRE_HEAP;

       while (!heap.empty()) {

         typename SrcGraph::Node v=heap.top();

 	heap.pop();

         crossref[v] = Heap::PRE_HEAP;

       }

       heap.clear();

       if(!stop)++tree_counter;

     }

     template<class SrcGraph,class OrigMap,class ProcessedMap>

     void createTrees(const SrcGraph& graph, const OrigMap& orig, 

                      ProcessedMap& processed,

                      int edgenum,int& tree_counter){

       typedef typename SrcGraph::Node Node;

       typedef typename SrcGraph::UEdge UEdge;

       typedef typename SrcGraph::NodeIt NodeIt;

       typedef typename SrcGraph::template NodeMap<int> HeapCrossRef;

       typedef typename SrcGraph::template NodeMap<UEdge> PredMap;

       HeapCrossRef crossref(graph,-1);

       FibHeap<Node,Value,HeapCrossRef> heap(crossref);

       PredMap pred(graph,INVALID);

       int rate=2*edgenum/countNodes(graph);

       int limit=(rate>std::numeric_limits<int>::digits)?

       std::numeric_limits<int>::max() : (1<<rate);

       for(NodeIt i(graph);i!=INVALID;++i){

 	if(processed[i]==-1){

 	  heap.push(i, Value());

 	  processNextTree(graph,orig,heap,crossref,

                           processed,pred,tree_counter,limit);

 	}

       }

     }

     template<class SrcGraph,class DestGraph,class SrcOrigMap,

              class DestOrigMap,class ProcessedMap>

     void collect(const SrcGraph& srcgraph,const SrcOrigMap& srcorig,

                  DestGraph& destgraph,DestOrigMap& destorig,

                  const ProcessedMap& processed,const int tree_counter){

       typedef typename SrcGraph::Node Node;

       typedef typename DestGraph::Node DNode;

       typedef typename SrcGraph::UEdge UEdge;

       typedef typename DestGraph::UEdge DUEdge;

       typedef typename SrcGraph::Edge Edge;

       typedef typename SrcGraph::EdgeIt EdgeIt;

       std::vector<Edge> edges;

       std::vector<DNode> nodes(tree_counter, INVALID);

       for(EdgeIt i(srcgraph);i!=INVALID;++i){

 	if(processed[srcgraph.source(i)]<processed[srcgraph.target(i)]){

 	  edges.push_back(i);

           if(nodes[processed[srcgraph.source(i)]]==INVALID) {

 	    nodes[processed[srcgraph.source(i)]]=destgraph.addNode();

 	  }

           if(nodes[processed[srcgraph.target(i)]]==INVALID) {

 	    nodes[processed[srcgraph.target(i)]]=destgraph.addNode();

 	  }

 	}

       }

       radixSort(edges.begin(),edges.end(),

                 mapFunctor(composeMap(processed,sourceMap(srcgraph))));

       counterSort(edges.begin(),edges.end(),

                   mapFunctor(composeMap(processed,targetMap(srcgraph))));

       for(int i=0;i!=(int)edges.size();++i){

 	int srcproc=processed[srcgraph.source(edges[i])];

 	int trgproc=processed[srcgraph.target(edges[i])];

         Value minval=(*cost)[srcorig[edges[i]]];

         UEdge minpos=edges[i];

 	while (i+1!=(int)edges.size() && 

                srcproc==processed[srcgraph.source(edges[i+1])] &&

 	  trgproc==processed[srcgraph.target(edges[i+1])]) {

 	  if (minval>(*cost)[srcorig[edges[i+1]]]) {

             minval=(*cost)[srcorig[edges[i+1]]];

             minpos=edges[i+1];

 	  }

           ++i;

 	} 

 	destorig[destgraph.addEdge(nodes[srcproc],nodes[trgproc])]=

           srcorig[minpos];

       }

     }

     template<class SrcGraph,class OrigMap>

     void phase(const SrcGraph& graph,const OrigMap& orig,int edgenum){

       int tree_counter = 0;

       typename SrcGraph::template NodeMap<int> processed(graph,-1);

       SmartUGraph destgraph;

       SmartUGraph::UEdgeMap<typename OrigMap::Value> destorig(destgraph);

       createTrees(graph,orig,processed,edgenum,tree_counter);

       collect(graph,orig,destgraph,destorig,processed,tree_counter);

       if (countNodes(destgraph)>1) {

         phase(destgraph,destorig,edgenum);

       }

     }

   public:      

     ///Constructor.

     ///\param _graph the graph the algorithm will run on.

     ///\param _cost the cost map used by the algorithm.

     FredmanTarjan(const UGraph& _graph, const CostMap& _cost) :

       graph(&_graph), cost(&_cost),

       _tree(0), local_tree(false)

     {

       checkConcept<concept::UGraph, UGraph>();

     }

     ///Destructor.

     ~FredmanTarjan(){

       if(local_tree) delete _tree;

     }

     ///Sets the cost map.

     ///Sets the cost map.

     ///\return <tt> (*this) </tt>

     FredmanTarjan &costMap(const CostMap &m){

       cost = &m;

       return *this;

     }

     ///Sets the map storing the tree edges.

     ///Sets the map storing the tree edges.

     ///If you don't use this function before calling \ref run(),

     ///it will allocate one. The destuctor deallocates this

     ///automatically allocated map, of course.

     ///By default this is a BoolEdgeMap.

     ///\return <tt> (*this) </tt>

     FredmanTarjan &treeMap(TreeMap &m){

       if(local_tree) {

 	delete _tree;

 	local_tree=false;

       }

       _tree = &m;

       return *this;

     }

   public:

     ///\name Execution control

     ///The simplest way to execute the algorithm is to use

     ///one of the member functions called \c run(...).

     ///@{

     ///Initializes the internal data structures.

     ///Initializes the internal data structures.

     ///

     void init(){

       create_maps();

       for(typename Graph::UEdgeIt i(*graph);i!=INVALID;++i){

 	_tree->set(i,false);

       }

     }

     ///Executes the algorithm.

     ///Executes the algorithm.

     ///

     ///\pre init() must be called and at least one node should be added

     ///with addSource() before using this function.

     ///

     ///This method runs the %FredmanTarjan algorithm from the node(s)

     ///in order to compute the

     ///minimum spanning tree.

     void start(){

 	phase(*graph,identityMap<UEdge>(),countEdges(*graph));

     }

     ///Runs %FredmanTarjan algorithm.

     ///This method runs the %FredmanTarjan algorithm

     ///in order to compute the minimum spanning forest.

     ///

     ///\note ft.run() is just a shortcut of the following code.

     ///\code

     ///  ft.init();

     ///  ft.start();

     ///\endcode

     void run() {

       init();

       start();

     }

     ///@}

     ///\name Query Functions

     ///The result of the %FredmanTarjan algorithm can be obtained using these

     ///functions.\n

     ///Before the use of these functions,

     ///either run() or start() must be called.

     ///@{

     ///Returns a reference to the tree edges map.

     ///Returns a reference to the TreeEdgeMap of the edges of the

     ///minimum spanning tree. The value of the map is \c true only if the 

     ///edge is in the minimum spanning tree.

     ///

     ///\pre \ref run() or \ref start() must be called before using this 

     ///function.

     const TreeMap &treeMap() const { return *_tree;}

     ///Sets the tree edges map.

     ///Sets the TreeMap of the edges of the minimum spanning tree.

     ///The map values belonging to the edges of the minimum

     ///spanning tree are set to \c tree_edge_value or \c true by default 

     ///while the edge values not belonging to the minimum spanning tree are 

     ///set to

     ///\c tree_default_value or \c false by default.

     ///

     ///\pre \ref run() or \ref start() must be called before using this 

     ///function.

     template<class TreeMap>

     void treeEdges(

         TreeMap& tree,

         const typename TreeMap::Value& tree_edge_value=true,

         const typename TreeMap::Value& tree_default_value=false) const {

       for(typename UGraph::UEdgeIt i(*graph);i!=INVALID;++i){

 	(*_tree)[i]?tree.set(i,tree_edge_value):tree.set(i,tree_default_value);

       }

     }

     ///\brief Checks if an edge is in the spanning tree or not.

     ///Checks if an edge is in the spanning tree or not.

     ///\param e is the edge that will be checked

     ///\return \c true if e is in the spanning tree, \c false otherwise

     bool tree(UEdge e){

       return (*_tree)[e];

     }

     ///@}

   };

   /// \ingroup spantree

   ///

   /// \brief Function type interface for FredmanTarjan algorithm.

   ///

   /// Function type interface for FredmanTarjan algorithm.

   /// \param graph the UGraph that the algorithm runs on

   /// \param cost the CostMap of the edges

   /// \retval tree the EdgeMap that contains whether an edge is in the 

   /// spanning tree or not

   ///

   /// \sa Prim

   template<class Graph,class CostMap,class TreeMap>

   void fredmanTarjan(const Graph& graph, const CostMap& cost,TreeMap& tree){

     typename FredmanTarjan<Graph,CostMap>::template DefTreeMap<TreeMap>::

       Create ft(graph,cost);

     ft.treeMap(tree);

     ft.run();

   }

 } //END OF NAMESPACE LEMON

 #endif