/*******************************************************************************
+
+  LEDA 4.4.1  
+
+
+  shortest_path_via_assignment_time.c
+
+
+  Copyright (c) 1995-2003
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/

// $Revision: 1.1.1.1 $  $Date: 2005/09/12 10:00:26 $


#include <LEDA/graph/templates/shortest_path.h>
#include <LEDA/graph/graph_alg.h>
#include <LEDA/core/random.h>
#include <assert.h>
#include <LEDA/graph/templates/mwb_matching.h>
#include <LEDA/core/stack.h>
#include <LEDA/core/IO_interface.h>

using namespace leda;



template <class NT>
bool shortest_path_via_assignment(const graph& G, node s,
                                  const edge_array<NT>& c, 
                                  node_array<NT>& dist, 
                                  node_array<edge>& pred)
{ node v,w; edge e;
  GRAPH<NT,NT> G1;
  list<node> A,B;
  
  node_array<node> left_copy(G), right_copy(G);
  forall_nodes(v,G) 
  { A.append(left_copy[v]  = G1.new_node());
    B.append(right_copy[v] = G1.new_node());
    G1.new_edge(left_copy[v],right_copy[v],0);
  }
  forall_edges(e,G)
  { v = G.source(e); w = G.target(e);
    G1.new_edge(left_copy[v],right_copy[w],c[e]);
  }
  list<edge> M = 
     MIN_WEIGHT_ASSIGNMENT_T(G1,A,B,G1.edge_data(),G1.node_data());

  NT sum = 0;
  forall_nodes(v,G1) sum += G1[v];
  if (sum < 0) return false;
  
  node_array<NT> pot(G);
  forall_nodes(v,G) pot[v] = G1[right_copy[v]];
  
  edge_array<NT> red_cost(G);
  forall_edges(e,G) 
    red_cost[e] = pot[G.source(e)] + c[e] - pot[G.target(e)];
  
  DIJKSTRA_T(G,s,red_cost,dist,pred); 

  forall_nodes(v,G) dist[v] += pot[v] - pot[s];

  return true;
}


int main(){

IO_interface I("Shortest Path Via the Assignment Problem");

I.write_demo("This demo illustrates a strange way to solve the shortest-path \
path problem for arbitrary edge weights. A bipartite graph is set up and the \
assignment problem is solved for this graph. The solution of the assignment \
problem yields node potentials with respect to which the edge weights become \
non-negative.");

I.write_demo("You should really read the corresponding section of the LEDA book \
to understand this demo.");


GRAPH<int,int>  G;
int n = I.read_int("n = ",5000);
int m = I.read_int("m = ",50000);

I.write_table(n);
I.write_table(" & ",m);

//while (true)
{ random_graph(G,n,m);

  edge_array<int> c(G);
  edge_array<int> c_arb(G);
  edge e;

  forall_edges(e,G) c[e] = rand_int(1,1000);


  node_array<int> pot(G);

  node v;
  forall_nodes(v,G) pot[v] = rand_int(1,10000);
  forall_edges(e,G) G[e] = pot[G.source(e)] + c[e] - pot[G.target(e)];

  node_array<edge> pred(G);
  node_array<int> dist(G);

  node s = G.first_node();

  G.write("test_graph");

  float T = used_time(); float UT;

I.write_demo("\n\nNon-negative edge weights in input graph.");

DIJKSTRA(G,s,c,dist,pred);
assert(pred[s]==nil);
CHECK_SP(G,s,c,dist,pred);
UT = used_time(T);
I.write_demo("time required for Dijkstra",UT);
I.write_table(" & ",UT);


shortest_path_via_assignment(G,s,c,dist,pred);
assert(pred[s]==nil);
CHECK_SP(G,s,c,dist,pred);
UT = used_time(T);
I.write_demo("time required for shortest path via assignment",UT);
I.write_table(" & ",UT);

I.write_demo("\n\nnegative costs, but no negative cycle");

BELLMAN_FORD(G,s,G.edge_data(),dist,pred);
CHECK_SP(G,s,G.edge_data(),dist,pred);
I.write_demo("time required for Bellman Ford",UT);
I.write_table(" & ",UT);


shortest_path_via_assignment(G,s,G.edge_data(),dist,pred);
CHECK_SP(G,s,G.edge_data(),dist,pred);
UT = used_time(T);
I.write_demo("time required for shortest path via assignment",UT);
I.write_table(" & ",UT);

I.write_demo("\n\ngraph generated by BF_GEN");
BF_GEN(G,n,m,false);
BELLMAN_FORD(G,s,G.edge_data(),dist,pred);
CHECK_SP(G,s,G.edge_data(),dist,pred);
UT = used_time(T);
I.write_demo("time required for Bellman Ford",UT);
I.write_table(" & ",UT);

shortest_path_via_assignment(G,s,G.edge_data(),dist,pred);
CHECK_SP(G,s,G.edge_data(),dist,pred);
UT = used_time(T);
I.write_demo("time required for shortest path via assignment",UT);
I.write_table(" & ",UT);

}

return 0;
}

