/* 

  Shortest path in Picat.

  Some exploration of shortest path using tabled dynamic programming.


  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
% import cp.


main => go.


go =>
  N = 3000, 
  M = 10000,
  G = random_graph(N,M),
  if M < 30 then
     writeln(g=G)
  end,
  cl_facts(G, $[index(+,-,-), index(-,+,-)]),
  writeln(start),
  time(shortest_path(1,2,Path,W)),
  writeln([path=Path,w=W]),
  
  nl.

go2 =>
  foreach(N in 100..100..1000) 
     M = N*4,
     G = random_graph(N,M),
     cl_facts(G),
     (   time(shortest_path(1,2,Path,W)) ->
          writeln([path=Path,w=W]) 
       ;
          writeln(no_solution),
          true
     ),

     nl
  end,
  nl.


random_graph(N, M) = G =>
  writeln([n=N,m=M]),
  G = [],
  foreach(_I in 1..M)
     R1 = 1 + (random2() mod N),
     R2 = 1 + (random2() mod N),
     % no self loops
     while (R1 == R2) 
       R2 := 1 + (random2() mod N)
     end,
     G := G ++ [$edge(R1,R2,1)]
  end,
  G := G.remove_dups().




% From Neng-Fa's talk at IBM PL Day 2013
table(+,+,-,min)
shortest_path(X,Y,Path,W) ?=>
   Path=[(X,Y)],
   edge(X,Y,W).
shortest_path(X,Y,Path,W) =>
   Path = [(X,Z)|PathR],
   edge(X,Z,W1),
   shortest_path(Z,Y,PathR,W2),
   W = W1+W2.

% index(+,-,-) (-,+,-)
% edge(a,b,1).
% edge(a,c,2).
% edge(b,c,3).
% edge(c,b,2).
% edge(c,d,1).