#include <hugo/dijkstra.h>

 #include <hugo/dijkstra.h>

 #include <hugo/graph_wrapper.h>

 #include <hugo/graph_wrapper.h>

 #include <hugo/maps.h>

 #include <hugo/maps.h>

 #include <vector>

 #include <vector>

 #include <list>

 #include <list>

 #include <hugo/for_each_macros.h>

 #include <hugo/for_each_macros.h>

 #include <hugo/unionfind.h>

 #include <hugo/unionfind.h>

 namespace hugo {

 namespace hugo {

 /// \addtogroup galgs

 /// \addtogroup galgs

 /// @{

 /// @{

     //auxiliary variables

     //auxiliary variables

     //To store the flow

     //To store the flow

     FlowMap flow; 

     FlowMap flow; 

     //To store excess-deficit values

     //To store excess-deficit values

     SupplyDemandMap excess_deficit;

     SupplyDemandMap excess_deficit;

     Cost total_cost;

     Cost total_cost;

   public :

   public :

     ///Runs the algorithm.

     ///Runs the algorithm.

     ///Runs the algorithm.

     ///Runs the algorithm.

       //Resetting variables from previous runs

       //Resetting variables from previous runs

       //total_cost = 0;

       //total_cost = 0;

       typedef typename Graph::template NodeMap<int> HeapMap;

       typedef typename Graph::template NodeMap<int> HeapMap;

 	std::greater<SupplyDemand> > 	HeapType;

 	std::greater<SupplyDemand> > 	HeapType;

       //A heap for the excess nodes

       //A heap for the excess nodes

       HeapMap excess_nodes_map(graph,-1);

       HeapMap excess_nodes_map(graph,-1);

       HeapType excess_nodes(excess_nodes_map);

       HeapType excess_nodes(excess_nodes_map);

       //A heap for the deficit nodes

       //A heap for the deficit nodes

       HeapMap deficit_nodes_map(graph,-1);

       HeapMap deficit_nodes_map(graph,-1);

       HeapType deficit_nodes(deficit_nodes_map);

       HeapType deficit_nodes(deficit_nodes_map);

       //A container to store nonabundant arcs

       //A container to store nonabundant arcs

       FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){

       FOR_EACH_LOC(typename Graph::EdgeIt, e, graph){

 	flow.set(e,0);

 	flow.set(e,0);

 	nonabundant_arcs.push_back(e);

 	nonabundant_arcs.push_back(e);

       SupplyDemand delta = 0;

       SupplyDemand delta = 0;

       typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;

       typedef UnionFindEnum<Node, Graph::template NodeMap> UFE;

       //A union-find structure to store the abundant components

       //A union-find structure to store the abundant components

       UFE abundant_components(abund_comp_map);

       UFE abundant_components(abund_comp_map);

       FOR_EACH_LOC(typename Graph::NodeIt, n, graph){

       FOR_EACH_LOC(typename Graph::NodeIt, n, graph){

       //It'll be allright as an initial value, though this value 

       //It'll be allright as an initial value, though this value 

       //can be the maximum deficit here

       //can be the maximum deficit here

       SupplyDemand max_excess = delta;

       SupplyDemand max_excess = delta;

       ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph

       ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph

       //We need a residual graph which is uncapacitated

       //We need a residual graph which is uncapacitated

       ResGraph res_graph(graph, const_inf_map, flow);

       ResGraph res_graph(graph, const_inf_map, flow);

       //An EdgeMap to tell which arcs are abundant

       //An EdgeMap to tell which arcs are abundant

       //Let's construct the sugraph consisting only of the abundant edges

       //Let's construct the sugraph consisting only of the abundant edges

       typedef ConstMap< typename Graph::Node, bool > ConstNodeMap;

       typedef ConstMap< typename Graph::Node, bool > ConstNodeMap;

       ConstNodeMap const_true_map(true);

       ConstNodeMap const_true_map(true);

 	AbundantGraph;

 	AbundantGraph;

       AbundantGraph abundant_graph(graph, const_true_map, abundant_arcs );

       AbundantGraph abundant_graph(graph, const_true_map, abundant_arcs );

       //Let's construct the residual graph for the abundant graph

       //Let's construct the residual graph for the abundant graph

 	ResAbGraph;

 	ResAbGraph;

       //Again uncapacitated

       //Again uncapacitated

       ResAbGraph res_ab_graph(abundant_graph, const_inf_map, flow);

       ResAbGraph res_ab_graph(abundant_graph, const_inf_map, flow);

       //We need things for the bfs

       //We need things for the bfs

 	bfs_pred(res_ab_graph); 

 	bfs_pred(res_ab_graph); 

       //We want to run bfs-es (more) on this graph 'res_ab_graph'

       //We want to run bfs-es (more) on this graph 'res_ab_graph'

       Bfs < ResAbGraph , 

       Bfs < ResAbGraph , 

 	NullMap<typename ResAbGraph::Node, int> > 

 	NullMap<typename ResAbGraph::Node, int> > 

 	bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy);

 	bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy);

       ModCostMap mod_cost(res_graph, cost, potential);

       ModCostMap mod_cost(res_graph, cost, potential);

       Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost);

       Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost);

 	 * Beginning of the delta scaling phase 

 	 * Beginning of the delta scaling phase 

 	*/

 	*/

 	//Merge and stuff

 	//Merge and stuff

 	{

 	{

 	  SupplyDemand buf=8*number_of_nodes*delta;

 	  SupplyDemand buf=8*number_of_nodes*delta;

 	  while ( i != nonabundant_arcs.end() ){

 	  while ( i != nonabundant_arcs.end() ){

 	    if (flow[i]>=buf){

 	    if (flow[i]>=buf){

 	      Node a = abundant_components.find(res_graph.head(i));

 	      Node a = abundant_components.find(res_graph.head(i));

 	      Node b = abundant_components.find(res_graph.tail(i));

 	      Node b = abundant_components.find(res_graph.tail(i));

 	      //Merge

 	      //Merge

 	if (max_excess < deficit_nodes[t]){

 	if (max_excess < deficit_nodes[t]){

 	  max_excess = deficit_nodes[t];

 	  max_excess = deficit_nodes[t];

 	}

 	}

 	  //s es t valasztasa

 	  //s es t valasztasa

 	  //Dijkstra part	

 	  //Dijkstra part	

       return total_cost;

       return total_cost;

     }

     }

     ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must

     ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must

     ///be called before using this function.

     ///be called before using this function.

   ///Returns a const reference to the NodeMap \c potential (the dual solution).

   ///Returns a const reference to the NodeMap \c potential (the dual solution).

     /// \pre \ref run() must be called before using this function.

     /// \pre \ref run() must be called before using this function.

     ///This function checks, whether the given solution is optimal

     ///This function checks, whether the given solution is optimal

     ///Running after a \c run() should return with true

     ///Running after a \c run() should return with true

     ///In this "state of the art" this only check optimality, doesn't bother with feasibility

     ///In this "state of the art" this only check optimality, doesn't bother with feasibility

     ///

     ///