g0([para(1,[]), para(2,[3]), para(3,[])]).
g1([para(1,[2]), para(2,[3]), para(3,[])]).
g2([para(0,[1]), para(1,[2]), para(2,[3]), para(3,[1])]).
g3([para(1,[3]), para(2,[3]), para(3,[4,5]), para(4,[]), para(5,[])]).


% rozwiazanie naiwne, ale za to czysto deklaratywne:)

bruteForceLin(G,L):- nodesPerm(L,G), \+ mismatch(G,L).

nodesPerm([], []).
nodesPerm([X|LTail], G):- memDel(para(X,_),G,H), nodesPerm(LTail,H).

memDel(X,[X|LTail],LTail).
memDel(X,[Y|L],[Y|M]):-memDel(X,L,M).

mismatch(G,L):- edge(X,Y,G), append(_, [Y|Tail], L), member(X,Tail).

edge(X,Y,G):- member(para(X,L),G), member(Y,L).

% sprytniejsze rozwiazanie, ale generuje tylko jedna odpowiedz. 

lin([], []).
lin(G,Lin):- leaves(G, L), L=[_|_], delNodes(L,G,H), lin(H,M), append(M, L, Lin).

leaves([],[]).
leaves([para(X,[])|GTail], [X|LTail]):- leaves(GTail, LTail).
leaves([para(_,[_|_])|GTail],L):-leaves(GTail, L).

delNodes([],G,G).
delNodes([X|LTail],G,H):-delNode(X,G,I), delNodes(LTail,I,H).

delNode(_, [], []).
delNode(X, [para(X,_)|GTail], H):- delNode(X, GTail, H).
delNode(X, [para(Y,L)|GTail], [para(Y,M)|HTail]):- \+ X = Y, del(X,L,M), delNode(X,GTail,HTail).

del(_,[],[]).
del(X,[X|LTail],LTail).
del(X,[Y|LTail],[Y|MTail]):- \+ X = Y, del(X,LTail,MTail).