#include <LEDA/stream.h>
#include <LEDA/ugraph.h>
#include <LEDA/node_pq.h>
#include <LEDA/b_node_pq.h>
#include <LEDA/node_slist.h>

#include <LEDA/graph_alg.h>


int  dijkstra1(GRAPH<int,int>& g, node source, node target) 
{ node_array<int> dist(g);
  //DIJKSTRA(g,source,g.edge_data(),dist);
  edge_array<int> cost(g);
  edge e;
  forall_edges(e,g) cost[e] = g[e];
  DIJKSTRA(g,source,cost,dist);
  return dist[target];
}

int  dijkstra2(GRAPH<int,int>& g, node source, node target) 
{
  // use a node priority queue (node_pq)
  // and node_array<int> for dist values

  node_array<int> dist(g,MAXINT); // initialize labels
  dist[source] = 0;

  node_pq<int> PQ(g);             // candidate nodes
  PQ.insert(source,0);

  while (! PQ.empty())
  { 
    node v = PQ.del_min();
    int dv = dist[v];

    if (v == target) break;

    edge e;
    forall_adj_edges(e,v)
    { node w = g.opposite(v,e);
      int d = dv + g[e];
      if (d < dist[w]) 
      { if (dist[w] == MAXINT)
           PQ.insert(w,d);
        else
           PQ.decrease_inf(w,d);
        dist[w] = d;
       }
    }

  }

  return dist[target];
}




int dijkstra3(GRAPH<int,int>& g, node s, node t) 
{
  // use a bounded node priority queue (b_node_pq)
  // and a node_array<int> for dist values

  node_array<int> dist(g,MAXINT);

  b_node_pq<101> PQ(t);  // on empty queue del_min returns t 

  node v;

  dist[s] = 0;
  PQ.insert(s,0);

  while ( (v = PQ.del_min()) != t )
  { int dv = dist[v];
    edge e;
    forall_adj_edges(e,v) 
    { node w = g.opposite(v,e);
      int d = dv + g[e];
      if (d < dist[w])
      { if (dist[w] != MAXINT) PQ.del(w);
	dist[w] = d;
        PQ.insert(w,d);
       }
     }
   }

  return dist[t];
}


int dijkstra4(GRAPH<int,int>& g, node s, node t) 
{
  // use a bounded node priority queue (b_node_pq)
  // and node_array<int> for dist values

  node_array<int> dist(g,MAXINT);

  b_node_pq<101> PQ(t);  // on empty queue del_min returns t 

  node v;

  dist[s] = 0;
  PQ.insert(s,0);

  while ( (v = PQ.del_min()) != t )
  { int dv = dist[v];
    edge e;
    forall_adj_edges(e,v) 
    { node w = g.opposite(v,e);
      int d = dv + g[e];
      if (d < dist[w])
      { if (dist[w] != MAXINT) PQ.del(w);
	dist[w] = d;
        PQ.insert(w,d);
       }
     }
   }

  return dist[t];
}

int dijkstra5(GRAPH<int,int>& g, node s, node t) 
{
  // use a bounded node priority queue (b_node_pq)
  // and the node information of g for  dist values

  b_node_pq<101> PQ(t);  // on empty queue del_min returns t 

  node v;
  forall_nodes(v,g) g[v] = MAXINT;

  g[s] = 0;
  PQ.insert(s,0);

  while ( (v = PQ.del_min()) != t )
  { int dv = g[v];
    edge e;
    forall_adj_edges(e,v) 
    { node w = g.opposite(v,e);
      int d = dv + g[e];
      if (d < g[w])
      { if (g[w] != MAXINT) PQ.del(w);
	g[w] = d;
        PQ.insert(w,d);
       }
     }
   }

  return g[t];
}


int dijkstra6(GRAPH<int,int>& g, node s, node t) 
{
  // use a bounded node priority queue (b_node_pq)
  // and the node information of g for  dist values

  b_node_pq<101> PQ(t);  // on empty queue del_min returns t 

  node v;
  forall_nodes(v,g) g[v] = MAXINT;

  g[s] = 0;
  PQ.insert(s,0);

  while ( (v = PQ.del_min()) != t )
  { int dv = g[v];
    edge e;
    forall_adj_edges(e,v) 
    { node w = g.opposite(v,e);
      int d = dv + g[e];
      if (d < g[w])
      { if (g[w] != MAXINT) PQ.del(w);
	g[w] = d;
        PQ.insert(w,d);
       }
     }
   }

  return g[t];
}




int  moore1(GRAPH<int,int>& g, node source, node target)
{ node_array<int> dist(g);
  //MOORE(g,source,g.edge_data(),dist,target);
  edge_array<int> cost(g);
  edge e;
  forall_edges(e,g) cost[e] = g[e];
  MOORE(g,source,cost,dist,target);
  return dist[target];

}


int  moore2(GRAPH<int,int>& g, node source, node target) 
{
  // use a double ended queue of candidate nodes (node_list)
  // and a node_array<int> for dist values

  node_array<int> dist(g,MAXINT); // initialize labels
  dist[source] = 0;

  node_list labeled;             // deque of candidate nodes
  labeled.append(source);

  while (! labeled.empty()) 
  { 
    node v = labeled.pop();
    int dv = dist[v];

    if (dv > dist[target]) continue;

    edge e;
    forall_adj_edges(e,v)
    { node w = g.opposite(v,e);
      int  d = dv + g[e];
      if (d < dist[w]) 
      { if ( ! labeled(w) ) 
        { if (dist[w] == MAXINT)
	       labeled.append(w);
	    else
	       labeled.push(w);
	   }
	  dist[w] = d;
       }
     }

  }

  return dist[target];
}


int  moore3(GRAPH<int,int>& g, node source, node target) 
{
  // use a double ended queue of candidate nodes (node_list)
  // and the node information of g for  dist values


  node v;
  forall_nodes(v,g) g[v] = MAXINT;  // initialize labels

  g[source] = 0;

  node_list labeled;             // deque of candidate nodes
  labeled.append(source);

  while (! labeled.empty()) 
  { 
    node v = labeled.pop();
    int dv = g[v];

    if (dv > g[target]) continue;

    edge e;

    forall_adj_edges(e,v)
    { node w = g.opposite(v,e);
      int  d = dv + g[e];
      if (d < g[w]) 
      { if ( ! labeled(w) ) 
        { if (g[w] == MAXINT)
	       labeled.append(w);
	    else
	       labeled.push(w);
	   }
	  g[w] = d;
       }
     }

  }

  return g[target];
}


int  moore4(GRAPH<int,int>& g, node source, node target) 
{
  // use a double ended queue of candidate nodes (node_slist)
  // and the node information of g for  dist values


  node v;
  forall_nodes(v,g) g[v] = MAXINT;  // initialize labels

  g[source] = 0;

  node_slist labeled(g);            // deque of candidate nodes
  labeled.append(source);

  while (! labeled.empty()) 
  { 
    node v = labeled.pop();

    int dv = g[v];

    if (dv > g[target]) continue;

    edge e;
    forall_adj_edges(e,v)
    { node w = g.opposite(v,e);
      int  d = dv + g[e];
      if (d < g[w]) 
      { if (g[w] == MAXINT) 
           labeled.append(w);
	else 
           if (!labeled(w)) labeled.push(w);
	g[w] = d;
       }
     }
  }

  return g[target];
}


#if defined (UNCOMMENT)

int  moore5(GRAPH<int,int>& g, node source, node target) 
{
  // static iterations
  // single ended queue of candidate nodes (node_slist)
  // node information of g for  dist values


  node v;
  static_forall_nodes(v,g) g[v] = MAXINT;  // initialize labels

  g[source] = 0;

  node_slist labeled(g);             // deque of candidate nodes
  labeled.append(source);

  int dtarget = MAXINT;

  while (! labeled.empty()) 
  { 
    node v = labeled.pop();
    int dv = g[v];
    edge e;

    if (dv < dtarget)
      static_forall_adj_edges(e,v)
      { node w = g.target(e);
        int d = dv + g[e];
        if (d < g[w]) 
        { if (g[w] == MAXINT) labeled.append(w);
          else if (!labeled(w)) labeled.push(w);
          g[w] = d;
          if (w == target) dtarget = d;
         }
       }

  }

  return dtarget;
} 

#endif



int main (int argc, char** argv) 
{

  GRAPH<int,int> G0;

  int sourcename;
  int targetname;
  int len;

  string filename = "grid100";

  if (argc > 1) filename = argv[1];

  // read names of source and target from file <filename>

  file_istream  infile (filename);

  if ( ! (infile >> sourcename >> targetname) )
  { cerr << "Cannot read file " << filename << endl;
    exit(1);
   }

  cout << "Source node: " << sourcename << endl;
  cout << "Target node: " << targetname << endl;
  newline;

  // read graph from file <filename>.graph

  float t0 = used_time();

  if (G0.read(filename + ".graph") != 0)
  { cerr << "Cannot read graph from file " << filename << ".graph" << endl;
    exit(1);
   }

  cout << string("Time for reading:  %5.2f",used_time(t0)) << endl;
  newline;

  // search for source and target nodes

  node source = nil;
  node target = nil;

  node v;
  forall_nodes(v,G0) 
  { if (G0[v] == sourcename) source = v;
    if (G0[v] == targetname) target = v;
   }

  G0.make_undirected();

  t0 = used_time();

  len = dijkstra1(G0, source, target);
  cout <<string("Time for dijkstra1: %5.3f pathlength: %d",used_time(t0),len);
  newline;
  
  len = dijkstra2(G0, source, target);
  cout <<string("Time for dijkstra2: %5.3f pathlength: %d",used_time(t0),len);
  newline;
  
  len = dijkstra3(G0, source, target);
  cout <<string("Time for dijkstra3: %5.3f pathlength: %d",used_time(t0),len);
  newline;

  len = dijkstra4(G0, source, target);
  cout <<string("Time for dijkstra4: %5.3f pathlength: %d",used_time(t0),len);
  newline;

  len = dijkstra5(G0, source, target);
  cout <<string("Time for dijkstra5: %5.3f pathlength: %d",used_time(t0),len);
  newline;

  len = dijkstra6(G0, source, target);
  cout <<string("Time for dijkstra6: %5.3f pathlength: %d",used_time(t0),len);
  newline;


  
  len = moore1(G0, source, target);
  cout <<string("Time for moore1:    %5.3f pathlength: %d",used_time(t0),len);
  newline;
  
  len = moore2(G0, source, target);
  cout <<string("Time for moore2:    %5.3f pathlength: %d",used_time(t0),len);
  newline;

  len = moore3(G0, source, target);
  cout <<string("Time for moore3:    %5.3f pathlength: %d",used_time(t0),len);
  newline;

  len = moore4(G0, source, target);
  cout <<string("Time for moore4:    %5.3f pathlength: %d",used_time(t0),len);
  newline;

  return 0;
}
