% -------------------------------------------------------------------
%% * Graphs

%% ** Directed, acyclic graphs (fact representation)

% path_da(X,Y) : There is a path from X to Y.
% (transitive closure of the edge relation).

path_da(X,Y) :-
	edge_da(X,Y).
path_da(X,Y) :-
	edge_da(X,Z),
	path_da(Z,Y).

circuit_da :- path_da(A,A).

% ------------------------------------------------
% Example (directed, acyclic graph): 
%
%   a ----> b             f
%   |       |             |
%   v       v             v
%   c ----> d ----> e     g
%           |
%           v
%           h
% ------------------------------------------------

edge_da(a,b).
edge_da(a,c).
edge_da(b,d).
edge_da(c,d).
edge_da(d,e).
edge_da(d,h).
edge_da(f,g).

% Try:
% ?- path_da(a,e). % yes
% ?- path_da(a,g). % no
% ?- path_da(c,X). % Nodes that c is connected to.
% ?- path_da(X,Y). % All connected nodes.
%                  % Duplicate solutions for different paths.

% Note that more needed if graph is not directed.
% Also if it has cycles.

% -------------------------------------------------------------------
%% ** Directed, acyclic graphs (list representation)

% (Same example)
graph_da([
    edge(a,b),
    edge(a,c),
    edge(b,d),
    edge(c,d),
    edge(d,e),
    edge(d,h),
    edge(f,g) ]).

path_l(X,Y,G) :-
    member(edge(X,Y),G).
path_l(X,Y,G) :-
    member(edge(X,Z),G),
    path_l(Z,Y,G).

% Try:
% ?- graph_da(_G), path_l(a,e,_G). % yes
% ?- graph_da(_G), path_l(a,g,_G). % no
% ?- graph_da(_G), path_l(c,X,_G). % Nodes that c is connected to.
% ?- graph_da(_G), path_l(X,Y,_G). % All connected nodes.
%               % Duplicate solutions for different paths.

% -------------------------------------------------------------------
%% ** Undirected graphs

path_a(X,Y) :-
	connected_a(X,Y).
path_a(X,Y) :-
	connected_a(X,Z),
	path_a(Z,Y).

connected_a(X,Y) :- edge_da(X,Y).
connected_a(X,Y) :- edge_da(Y,X).

circuit_a :- path_a(A,A).

% Try:
% ?- path_a(a,e). % yes
% But: 
% ?- path_a(c,X). % nodes that c is conn to - but duplicates (infinite)
% ?- path_a(X,Y). % also duplicates (infinite)
% ?- path_a(a,g). % loops

% We need to deal with cycles!

% -------------------------------------------------------------------
%% ** Dealing with cycles (list representation)

% ------------------------------------------------
% Example (directed graph, with cycle): 
%
%   a <---- b             f
%   |       ^             |
%   v       |             v
%   c ----> d ----> e     g
%           |
%           v
%           h
% ------------------------------------------------

%% List representation: 
graph([
    edge(a,c),
    edge(c,d),
    edge(d,b),
    edge(b,a),
    edge(d,e),
    edge(d,h),
    edge(f,g) ]).

path(X,Y,G) :-
    member(edge(X,Y),G).
path(X,Y,G) :-
    list_select(edge(X,Z),G,GRest),
    path(Z,Y,GRest).

% list_select(X,L,NL): selects an element X out of list L
% and NL is L without X
list_select(X, [X|Xs], Xs).
list_select(X, [Y|Ys], [Y|Zs]) :-
     list_select(X, Ys, Zs).

% Try:
% ?- graph(_G), path(a,e,_G).
% ?- graph(_G), path(a,g,_G).
% ?- graph(_G), path(c,X,_G).
% ?- graph(_G), path(X,Y,_G).