Trying to solve the isomorphic graphs problem here.
Assignment info:
- Determine whether 2 undirected graphs are isomorphic.
- No isolated vertices.
- Number of vertices is less than 30
Edges of graphs are given as predicates, i.e.
e(1, 2). f(1, 2).
I'm trying to use the following approach:
- For every pair of edges (i.e. for every edge from graph 1 and 2)
- Try to bind the vertices of 2 edges
- If binding of vertices is impossible (i.e. another binding with one of the vertex already exists), then backtrack and try another pair of edges.
- Otherwise add binding and continue with the rest of graphs (i.e. one edge from each graph is removed and procedure is applied again).
Procedure recurs unless both graphs are empty (meaning that all vertices were bound from one graph to the other one) meaning a success. Otherwise procedure should always fail (i.e. no other binding combinations available, etc.)
My code seems to be working but for small graphs only (guess because it tries all the pairs :) ).
So if anyone knows how it's possible to optimize the code (I believe that several cuts can be inserted and that try_bind
can be written in better way) or can tell a better approach thanks in advance.
P.s. for checking non-isomorphism I know that we can check invariants and etc. It doesn't really matter for now.
Code:
%define graph, i.e. graph is a list of edges
graph1(RES):-findall(edge(X,Y), e(X, Y), RES).
graph2(RES):-findall(edge(X,Y), f(X, Y), RES).
%define required predicate
iso:-graph1(G1), graph2(G2), iso_acc(G1, G2, [], _).
%same as above but outputs result
iso_w:-graph1(G1), graph2(G2), iso_acc(G1, G2, [], RES_MAP), write(RES_MAP).
iso_acc([], [], MAP, RES):-append(MAP, [], RES), !.
iso_acc([X|X_Rest], Y_LS, MAP, RES_MAP):-
select(Y, Y_LS, Y_Rest),
bind(X, Y, MAP, UPD_MAP),
iso_acc(X_Rest, Y_Rest, UPD_MAP, RES_MAP).
% if edges bind is successful then in RES or UPD_MAP updated binding map is returned (may return the same map
% if bindings are already defined), otherwise fails
bind([], [], MAP, RES):-append(MAP, [], RES), !.
bind(edge(X1, Y1), edge(X2, Y2), MAP, UPD_MAP):-
try_bind(b(X1, X2), MAP, RES),
try_bind(b(Y1, Y2), RES, UPD_MAP).
bind(edge(X1, Y1), edge(X2, Y2), MAP, UPD_MAP):-
try_bind(b(X1, Y2), MAP, RES),
try_bind(b(Y1, X2), RES, UPD_MAP).
%if an absolute member, we're OK (absolute member means b(X,Y) is already defined
try_bind(b(X, Y), MAP, UPD_MAP):-
member(b(X, Y), MAP),
append(MAP, [], UPD_MAP), !.
%otherwise check that we don't have other binding to X or to Y
try_bind(b(X, Y), MAP, UPD_MAP):-
member(b(X, Z), MAP),
%check if Z != Y
Z=Y,
append(MAP, [], UPD_MAP).
try_bind(b(X, Y), MAP, UPD_MAP):-
member(b(W, Y), MAP),
%check if W == X
W=X,
append(MAP, [], UPD_MAP).
%finally if we not an absolute member and if no other bindings to X and Y we add new binding
try_bind(b(X, Y), MAP, UPD_MAP):-
not(member(b(X, Z), MAP)),
not(member(b(W, Y), MAP)),
append([b(X, Y)], MAP, UPD_MAP).
First, my congratulation for a good presentation of the problem and an elaborate solution proposal.
In the next paragraph I will talk about implementation details of your solution.
Unfortunately, I must say that I do not see this approach to the solution scalable to bigger sizes. Assume graphs of 10 edges.
iso_acc/4
tries to assign first edge to any of one of the edges in second one (10 possibilities), second edge is also bind to any one (10 possibilities for each previous: 10*10), ... . If not a few of luck, that goes to 10^10 possibilities, 10! ones taken into account most of them are pruned faster.Minor comments are:
You can skip usage of
append(X,[],Y)
, socan be:
Second and third rules in
try_bind/3
seems unnecessary, in previous one you have already verified nob(X,Y)
belongs toMAP
. In other words,member(b(X,Y),MAP)
is equivalent tomember(b(X,Z),MAP), Z=Y
.Addendum
Let's try the following method. Let the example graph
e
be:and graph
f
be:The basic algorithm could be:
From this starting point, optimizations can be done.
This algorithm needs some initial data converters, to convert each graph to a list of items in the form
node-[peer1,peer2,...]
. The rules for this conversion are:Addendum 2
Initial data for this example is:
Addendum 3
When the full algorithm is now queried with the sample graphs
e
andf
, the result is:That means these graphs are isomorphic, with the possible node mappings
e:[5,1,3,4,2] => f:[1,2,3,4,5]
ande:[5,1,4,3,2] => f:[1,2,3,4,5]
.Addendum 4
Basic benchmark. Single solution:
all solutions:
Solved using another approach. Code is attached (algorithm is in the code).
Some predicates from prev. case remained though (like
try_bind
).Code: