% P85 (**) Graph isomorphism :- ensure_loaded(p80). % conversions % This is a solution for graphs only. It is not difficult to write the % corresponding predicates for digraphs. % isomorphic(G1,G2) :- the graphs G1 and G2 are isomorphic. isomorphic(G1,G2) :- isomorphic(G1,G2,_). % isomorphic(G1,G2,Iso) :- the graphs G1 and G2 are isomorphic. % Iso is a list representing the bijection between the node % sets of the graphs. It is an open-ended list and contains % a term i(X,Y) for each pair of corresponding nodes isomorphic(graph(Ns1,Es1),graph(Ns2,Es2),Iso) :- append(Es1,Ns1,List1), append(Es2,Ns2,List2), isomo(List1,List2,Iso). % isomo(List1,List2,Iso) :- the graphs represented by List1 and % List2 are isomorphic. isomo([],[],_) :- !. isomo([X|Xrest],Ys,Iso) :- select(Ys,Y,Yrest), iso(X,Y,Iso), isomo(Xrest,Yrest,Iso). % iso(E1,E2,Iso) :- the edge E1 in one graph corresponds % to the edge E2 in the other. Note that edges are undirected. % iso(N1,N2,Iso) :- matches isolated vertices. iso(E1,E2,Iso) :- edge(E1,X1,Y1), edge(E2,X2,Y2), bind(X1,X2,Iso), bind(Y1,Y2,Iso). iso(E1,E2,Iso) :- edge(E1,X1,Y1), edge(E2,X2,Y2), bind(X1,Y2,Iso), bind(Y1,X2,Iso). iso(N1,N2,Iso) :- \+ edge(N1,_,_),\+ edge(N2,_,_), % isolated vertices bind(N1,N2,Iso). edge(e(X,Y),X,Y). edge(e(X,Y,_),X,Y). % bind(X,Y,Iso) :- it is possible to "bind X to Y" as part of the % bijection Iso; i.e. a term i(X,Y) is already in the list Iso, % or it can be added to it without violating the rules. Note that % bind(X,Y,Iso) makes sure that both X and Y are really "new" % if i(X,Y) is added to Iso. bind(X,Y,Iso) :- memberchk(i(X,Y0),Iso), nonvar(Y0), !, Y = Y0. bind(X,Y,Iso) :- memberchk(i(X0,Y),Iso), X = X0. % ---------------------------------------------------------------------- test(1) :- human_gterm([f-e,e-d,e-g,c-e,c-b,a-b,c-d,beta],G1), human_gterm([6-3,6-4,3-4,alfa,4-5,7-4,6-2,1-2],G2), isomorphic(G1,G2,Iso), write(Iso). test(2) :- human_gterm([f-e,e-d,e-g,c-e,c-b,a-b,c-d,beta],G1), human_gterm([6-3,6-4,3-4,4-5,7-4,6-2,1],G2), isomorphic(G1,G2,Iso), write(Iso). test(3) :- human_gterm([a-b,c-d,e,d-f],G1), human_gterm([1-2,1-3,5,4-6],G2), isomorphic(G1,G2,Iso), write(Iso).