% IB015: 12th homework

% c(X, Y) holds, if there is a connexion (by tram, by (trolley-) bus or afoot)
% from X to Y
% See assignment's appendix for visual representation of the network.
c(hlavni_nadrazi, malinovskeho_namesti).
c(hlavni_nadrazi, namesti_svobody).
c(hlavni_nadrazi, nove_sady).
c(ceska, moravske_namesti).
c(ceska, grohova).
c(moravske_namesti, malinovskeho_namesti).
c(namesti_svobody, ceska).
c(namesti_svobody, silingrovo_namesti). % No tram here, we must walk :/ (but there are pubs!)
c(silingrovo_namesti, ceska).
c(silingrovo_namesti, nove_sady).
c(nove_sady, mendlovo_namesti).
c(mendlovo_namesti, silingrovo_namesti).
c(ceska, malinovskeho_namesti).
c(mendlovo_namesti, uvoz).
c(uvoz, ceska).
c(uvoz, konecneho_namesti).
c(konecneho_namesti, grohova).
c(konecneho_namesti, pionyrska).
c(konecneho_namesti, klusackova).
c(klusackova, skacelova).
c(skacelova, husitska).
c(husitska, hrncirska).
c(hrncirska, pionyrska).
c(pionyrska, moravske_namesti).
c(klusackova, namesti_miru).
c(namesti_miru, uvoz).
c(moravske_namesti, namesti_28_rijna).
c(namesti_28_rijna, zimni_stadion).
c(zimni_stadion, pionyrska).
c(malinovskeho_namesti, jugoslavska).
c(jugoslavska, namesti_28_rijna).
c(jugoslavska, zemedelska).
c(zemedelska, lesnicka).
c(lesnicka, zimni_stadion).

% connexion/2 allows as to view each c/2-defined connexion as bidirectional
connexion(X, Y) :- c(X, Y).
connexion(X, Y) :- c(Y, X).

% trip_start/1 denotes the stop from which the trip starts (and where it ends)
trip_start(hlavni_nadrazi).

% which stops are there in the transport network?
% we use the findall standard predicate to find all solutions to
% ?- connexion(X, _Y)
% we use list_to_set to remove duplicates from the output
stops(Stops) :-
    findall(X, connexion(X, _Y), Xs),
    list_to_set(Xs, Stops).

% similarly, we can get a list of all connexions (as a list of 2-element lists)
connexions(Conns) :- findall([X, Y], c(X, Y), Conns).

% Now we want to write our map to the file in the 'dot' format
% <https://en.wikipedia.org/wiki/DOT_(graph_description_language)>
% which can then be processed with the dot or prefferably sfdp programms (from
% the graphviz package): sfdp -Tsvg file.dot > file.svg
%
% The FilePrefix gives the prefix of the file name, this will be appended with
% number (one for each result, starting from 0), and with .dot extension.
dump_dot(FilePrefix) :-
    connexions(Conns),
    findall(C, tour(C), Cs),
    dump_dot(Cs, FilePrefix, Conns, 0).

% recursively dumps all results to files
dump_dot([], _, _, _) :- !.
dump_dot([C|Cs], FilePrefix, Conns, FileIdx) :-
    % compute file name
    term_string(FileIdx, FI),
    string_concat(FilePrefix, FI, Fpi),
    string_concat(Fpi, ".dot", FileName),
    % open the file, creating it if necessary
    open(FileName, write, Fd, [create([all])]),
    % file header
    write(Fd, "graph brno {\n"),
    % edges
    dump_edges(Conns, C, Fd),
    % file foother and closing
    write(Fd, "}\n"),
    close(Fd),
    % continue with next result
    Nxt is FileIdx + 1,
    dump_dot(Cs, FilePrefix, Conns, Nxt).

% check if given edge occurs in a cycle
in_cycle([F, T], [F|HC]) :- last(HC, T), !.
in_cycle([T, F], [F|HC]) :- last(HC, T), !.
in_cycle([F, T], HC) :- append([F, T], _, Suf), append(_, Suf, HC), !.
in_cycle([T, F], HC) :- append([F, T], _, Suf), append(_, Suf, HC), !.

% write one edge in dot format
dump_edge([F, T], Fd) :-
    write(Fd, "    "),
    write(Fd, F),
    write(Fd, " -- "),
    write(Fd, T).

% dump edges, showing the ones in the cycle in red
dump_edges([], _, _) :- !.
dump_edges([E|Es], HC, Fd) :-
    in_cycle(E, HC),
    !, % avoid having to use \+ in_cycle in the other alternative
    dump_edge(E, Fd),
    write(Fd, "[color = red]\n"), % highlight edge
    dump_edges(Es, HC, Fd).
dump_edges([E|Es], HC, Fd) :-
    dump_edge(E, Fd),
    write(Fd, "\n"),
    dump_edges(Es, HC, Fd).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% Implement tour(?ZS):
tour([]).