% reprezentacja grafu jako listy termów kr(A,B) - krawędź z A do B
% [kr(1,3), kr(2,3), kr(3,5), kr(5,7), kr(3,6), kr(6,9)]

% 1 -> 3 -> 5 -> 7

% connect(Graf, A, B) gdy Graf jest listą krawędzi kr(A,B) i istnieje niepusta ścieżka z A do B w tym grafie (po jednym sukcesie na ścieżkę)

connect(Graf, A, B) :-
	member(kr(A, B), Graf).

connect(Graf, A, C) :-
%	connect(Graf, A, B), % jeżeli zrobimy tak, to się będzie zawieszać i odnosić wielokrotne sukcesy
	member(kr(A, B), Graf),
	connect(Graf, B, C).


% drugi wariant gdzie graf reprezentujemy jako predykaty edge(X, Y) tak jak na początku drzewa genealogiczne
% w tym wariancie mamy jeden graf do dyspozycji w całym środowisku (można by dodać trzeci argument identyfikujący o który graf chodzi).


% edge(A, B) gdy w całym środowisku istnieje krawędź z A do B

edge(1,3).
edge(2,3).
edge(3,4).
edge(4,5).
edge(5,7).
edge(3,6).
edge(6,9).
edge(9,1). % na początek grafy są acykliczne !!!
edge(2, 10).

% connect(A, B) gdy istnieje niepusta ścieżka z A do B wśród "edge" (po jednym sukcesie na ścieżkę)

connect(A, B) :-
	edge(A,B).

connect(A, C) :-
	edge(A,B),
	connect(B, C).

% path(A, B, P) gdy P = opis niepustej ścieżki z A do B, tzn. P = [A, ..., B]

path(A, B, [A, B]) :-
	edge(A,B).

path(A, C, [A | P]) :-
	edge(A, B),
	path(B, C, P).

% nonmember(X, L) gdy X nie jest elementem listy L

nonmember(_X, []).

nonmember(X, [Y | L]) :-
	X \= Y,
	nonmember(X, L).

% pathC(A,B,P) w dowolnym grafie skierowanym (potencjalnie cyklicznym), ścieżki niepuste, bez powtórzeń

pathC(A, B, P) :- pathC(A, B, P, [A]).

% pathC(A, B, P, V) gdy P to ścieżka z A do B omijająca wierzchołki z V (nie licząc pierwszego A)

pathC(A, B, [A, B], V) :-
	edge(A, B),
	nonmember(B, V).

pathC(A, C, [A | P], V) :-
	edge(A, B),
	nonmember(B, V),
	pathC(B, C, P, [B | V]).
	
	
% euler(G, P) gdy dany graf G jako lista kr(A,B) jest grafem Eulera i P to jakaś jego ścieżka Eulera

% graf G jest nieskierowany, krawędzie w nim są wymieniane raz, więc [kr(1,2), kr(3,2), kr(3,1)] to
% nieskierowany trójkąt

euler([kr(A, B)], [A, B]).  % to jest już załatwione przez weź napisane poniżej
euler([kr(B, A)], [A, B]).  % ale gdy to uprościmy jak niżej to jest problem

% euler([], [_X]).    % moĹźna tak krĂłtko, ale jest problem z pustym grafem

euler(G, [X, Y | P]) :-
	wez(G, X, Y, G1),
	euler(G1, [Y | P]).
	

% umiejętność wyjęcia (wzięcia) krawędzi z grafu G:

% wez(G, X, Y, G1) gdy G1 to graf G z wyjętą krawędzią z X do Y

wez([kr(X, Y) | G], X, Y, G).

wez([kr(Y, X) | G], X, Y, G).

wez([E | G], X, Y, [E | G1]) :-	wez(G, X, Y, G1).