dijkstra.erl

-module(dijkstra).
-export([read_graph/0, perform/3]).

% S -  wierzchołki sprawdzone
% Q - wierzchołki niesprawdzone
% tupla - {V, C, P} - Vertex, Cost, Parent

parse(0, List) ->
  List;

parse(N, List) when N > 0 ->
  {_, Line} = io:fread("input from, to, weight: ", "~d ~d ~d"),
  parse(N-1, List ++ [Line]).

read_graph() ->
  {_, [V]} = io:fread("vortex count: ", "~d"),
  {_, [N]} = io:fread("path count: ", "~d"),
  Paths = parse(N, []),
  {_, [Start]} = io:fread("Start: ", "~d"),
  [V, Start, Paths].
  
perform(N, Start, Paths) ->
  S = [],
  Q = lists:map(fun(E) -> {E, 999, 0} end, lists:seq(1, N)),
  calc_dist(S, Q, Start, Paths).
  
calc_dist(S, [], _, _) ->
  io:fwrite("~w\n", [S]),
  find_path(S);
  
calc_dist([], Q, V, Paths) ->
  calc_dist([{V, 0, 0}], Q -- [{V, 999, 0}], {V, 0, 0}, Paths);

calc_dist(S, Q, V, Paths) ->
  io:fwrite("~w\t\t~w\t\t~w\n", [S, Q, V]),
  UpdQ = update_neighbours(V, Q, Paths),
  % tutaj jak Neighbours/shortest_path jest puste to sie sypie
  [NewS, NewQ, NewV] = move_next_vertex(S, UpdQ),
  calc_dist(NewS, NewQ, NewV, Paths).
  
move_next_vertex(S, Q) ->
  io:fwrite("~w\t\t~w\n", [S, Q]),
  Next = lowest_cost(Q),
  [[Next|S], remove(Next, Q), Next].
  
update_neighbours(V, Q, Paths) -> 
  neighbours(V, Q, Paths, []).

neighbours(_, Q, [], Acc) -> 
  lists:flatten([Acc|Q]);

neighbours(V, Q, [H|Paths], Acc) ->
  [A, B, W] = H,
  {X, Cost, _} = V,
  % check if path starts in parent and target is in Q
  case A == X andalso member(B, Q) of
    % if so add to found neighbours
    true ->
      NewQ = remove({B, 0, 0}, Q),
      neighbours(V, NewQ, Paths, [{B, Cost + W, X}|Acc]);
    % else continue
    false -> neighbours(V, Q, Paths, Acc)
  end.
  
find_path(S) ->
  find_path(S, []).
  
find_path([], Acc) ->
  Acc;
  
find_path([H|S], []) ->
  {V, _, P} = H,
  find_path(S, [P, V]);
  
find_path([H|S], Acc) ->
  Parent = lists:nth(1, Acc),
  {_, _, P} = H,
  case H of
    {_, _, 0} -> find_path(S, Acc);
    {Parent, _, _} -> find_path(S, [P|Acc]);
    _ -> find_path(S, Acc)
  end.

% helper functions
% check if vertex is in list of tuples
member(_, []) ->
  false;

member(Vertex, [H|List]) ->
  case H of
    {Vertex, _, _} -> true;
    _ -> member(Vertex, List)
  end.
  
% remove vertex from list of tuples
remove(V, Q) ->
  remove(V, Q, []).

remove(_, [], Acc) ->
  Acc;
  
remove(V, [H|Q], Acc) ->
  {Vertex, _, _} = V,
  case H of
    {Vertex, _, _} ->
      remove(V, Q, Acc);
    _ ->
      remove(V, Q, [H|Acc])
  end.
  
lowest_cost(Q) ->
  lowest_cost(Q, []).
  
lowest_cost([], Result) ->
  Result;
  
lowest_cost([H|Q], []) ->
  lowest_cost(Q, H);
  
lowest_cost([H|Q], Result) ->
  {_, Cost, _} = Result,
  {_, NewCost, _} = H,
  case NewCost =< Cost of
    true -> lowest_cost(Q, H);
    false-> lowest_cost(Q, Result)
  end.