Prolog同构图 [英] Prolog isomorphic graphs

问题描述

在这里尝试解决同构图问题.

Trying to solve the isomorphic graphs problem here.

分配信息:

• 确定2个无向图是否是同构的.
• 没有孤立的顶点.
• 顶点数少于30个

• 图的边缘以谓词形式给出，即

• 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:

1. 对于每对边(即，图1和2中的每条边)
2. 尝试绑定2个边的顶点
   • 如果无法进行顶点绑定(即已经存在与一个顶点的另一种绑定)，则回溯并尝试另一对边.
   • 否则，添加绑定并继续处理其余图形(即，删除每个图形的一条边并再次应用过程).

1. For every pair of edges (i.e. for every edge from graph 1 and 2)
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 :) ).

因此，如果有人知道如何优化代码(我相信可以插入多个剪切并且可以更好的方式编写try_bind)，或者可以提前告知更好的方法.

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.对于检查非同构性，我知道我们可以检查不变量等.目前，这真的不重要.

P.s. for checking non-isomorphism I know that we can check invariants and etc. It doesn't really matter for now.

代码:

%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).

推荐答案

使用另一种方法解决.附加了代码(算法在代码中).

Solved using another approach. Code is attached (algorithm is in the code).

上一个谓词.仍然保留大小写(例如try_bind).

Some predicates from prev. case remained though (like try_bind).

代码:

% Author: Denis Korekov

% Description of algorithm:
% G1 is graph 1, G2 is graph 2
% E1 is edge of G1, E2 is edge of G2
% V1 is vertex of G1, V2 is vertex of G2

% 0) Check that graphs can be isomorphic (refer to "initial_verify" predicate)
% 1) Pick V1 and some V2 and remove them from vertices lists
% 2) Ensure that none of chosen vertices are in relative closed lists (otherwise continue but remove them)
% 3) Bind (map) V1 to V2
% 4) Expand V1 and V2
% 5) Ensure that degrees of expansions are the same
% 6) Append expansion results to the end of vertices lists and repeat

% define graph predicates here

% graph predicates end

% as we have undirected edges
way_g1(X, Y):- e(X, Y).
way_g1(X, Y):- e(Y, X).
way_g2(X, Y):- f(X, Y).
way_g2(X, Y):- f(Y, X).

% returns all vertices of graphs (non-repeating)
graph1_v(RES):-findall(X, way_g1(X, _), LS), nodes(LS, [], RES).
graph2_v(RES):-findall(X, way_g2(X, _), LS), nodes(LS, [], RES).

% returns all edges of graphs in form "e(X, Y)"
graph1_e(RES):-findall(edge(X, Y), e(X, Y), RES).
graph2_e(RES):-findall(edge(X, Y), f(X, Y), RES).

% returns a list of vertices (removes repeating vertices in a list)
% 1 - list of vertices
% 2 - closed list (discovered vertices)
% 3 - resulting list
nodes([], CL_LS, RES):-append(CL_LS, [], RES).
nodes([X|Rest], CL_LS, RES):- not(member(X, CL_LS)), nodes(Rest, .(X, CL_LS), RES).
nodes([X|Rest], CL_LS, RES):-member(X, CL_LS), nodes(Rest, CL_LS, RES).

% required predicate
iso:-graph1_v(V1), graph2_v(V2), graph1_e(E1), graph2_e(E2), initial_verify(V1, V2, E1, E2), iso_acc(V1, V2, [], [], [], _).
% same as above but outputs result (outputs resulting binding map)
iso_w:-graph1_v(V1), graph2_v(V2), graph1_e(E1), graph2_e(E2), initial_verify(V1, V2, E1, E2), iso_acc(V1, V2, [], [], [], RES_MAP), write(RES_MAP).

% initial verification that graphs at least CAN BE isomorphic
% checks the number of vertices and edges as well as degrees
% 1 - vertices of G1
% 2 - vertices of G2
% 3 - edges of G1
% 4 - edges of G2
initial_verify(X_V, Y_V, X_E, Y_E):-
    length(X_V, X_VL),
    length(Y_V, Y_VL),
    X_VL=Y_VL,
    length(X_E, X_EL),
    length(Y_E, Y_EL),
    X_EL=Y_EL,
    get_degree_sequence_g1(X_V, [], X_S),
    get_degree_sequence_g2(Y_V, [], Y_S),
    %compare degree sequences
    compare_lists(X_S, Y_S).

% main algorithm
% 1 - list of vertices of G1
% 2 - list of vertices of G2
% 3 - closed list of G1
% 4 - closed list of G2
% 5 - initial binding map
% 6 - resulting binding map

% if both vertices lists are empty -> isomorphic, backtrack and cut
iso_acc([], [], _, _, ISO_MAP, RES):-append(ISO_MAP, [], RES), !.

% otherwise for every node of G1, for every root of G2
iso_acc([X|X_Rest], Y_LS, CL_X, CL_Y, ISO_MAP, RES):-
    select(Y, Y_LS, Y_Rest),
    %if X or Y in closed -> continue (next predicate)
    not(member(X, CL_X)),
    not(member(Y, CL_Y)),
    %map X to Y
    try_bind(b(X, Y), ISO_MAP, UPD_MAP),
    %expand X and Y, use CL_X and CL_Y
    expand_g1(X, CL_X, CL_X_UPD, X_RES, X_L),
    expand_g2(Y, CL_Y, CL_Y_UPD, Y_RES, Y_L),
    %compare lengths of expansions
    X_L=Y_L,
    %if OK continue with iso_acc with new closed lists and new mapping
    append(X_Rest, X_RES, X_NEW),
    append(Y_Rest, Y_RES, Y_NEW),
    iso_acc(X_NEW, Y_NEW, CL_X_UPD, CL_Y_UPD, UPD_MAP, RES).

% executed in case X and some Y are in closed list (skips such elements)
iso_acc([X|X_Rest], Y_LS, CL_X, CL_Y, ISO_MAP, RES):-
    select(Y, Y_LS, Y_Rest),
    member(X, CL_X),
    member(Y, CL_Y),
    iso_acc(X_Rest, Y_Rest, CL_X, CL_Y, ISO_MAP, RES).

% returns sorted degree sequence
% 1 - list of vertices
% 2 - current degree sequence
% 3 - resulting degree sequence
get_degree_sequence_g1([], DEG_S, RES):-
    insert_sort(DEG_S, RES).

get_degree_sequence_g1([X|Rest], DEG_S, RES):-
    findall(X, way_g1(X, _), LS),
    length(LS, L),
    append([L], DEG_S, DEG_S_UPD),
    get_degree_sequence_g1(Rest, DEG_S_UPD, RES).

get_degree_sequence_g2([], DEG_S, RES):-
    insert_sort(DEG_S, RES).

get_degree_sequence_g2([X|Rest], DEG_S, RES):-
    findall(X, way_g2(X, _), LS),
    length(LS, L),
    append([L], DEG_S, DEG_S_UPD),
    get_degree_sequence_g2(Rest, DEG_S_UPD, RES).

% compares two lists element by element
compare_lists([], []).
compare_lists([X|X_Rest], [Y|Y_Rest]):-
    X=Y,
    compare_lists(X_Rest, Y_Rest).

% checks whether binding exist, if not adds it (binding cannot be added if some other binding referring to same
% variables exists already (i.e. (1, 2) cannot be added if (2, 2) exists)
% 1 - binding to add / check in form "b(X, Y)"
% 2 - initial binding map
% 3 - resulting binding map (may remain the same)
try_bind(b(X, Y), MAP, MAP):-
    member(b(X, Z), MAP),
    Z=Y,
    member(b(W, Y), MAP),
    W=X.

try_bind(b(X, Y), MAP, UPD_MAP):-
    not(member(b(X, _), MAP)),
    not(member(b(_, Y), MAP)),
    append([b(X, Y)], MAP, UPD_MAP).

% returns updated closed list (X goes to CL), children of X, Length of children, TODO: members of closed lists should not be repeated.
% 1 - Node to expand
% 2 - initial closed list
% 3 - updated closed list (result)
% 4 - updated binding map (result)
% 5 - quantity of children (result)
expand_g1(X, CL, CL_UPD, RES, L):-
    findall(Y, (way_g1(X, Y), (not(member(Y, CL)))), LS),
    %set results
    append(LS, [], RES),
    %update closed list
    append([X], CL, CL_UPD),
    %set length
    length(RES, L).

expand_g2(X, CL, CL_UPD, RES, L):-
    findall(Y, (way_g2(X, Y), (not(member(Y, CL)))), LS),
    %set results
    append(LS, [], RES),
    %update closed list
    append([X], CL, CL_UPD),
    %set length
    length(RES, L).


% sort algorithm, used in degree sequence verification (simple insertion sort)
% 1 - list to sort
% 2 - result
insert_sort(LS, RES):-insert_sort_acc(LS, [], RES).

insert_sort_acc([], RES, RES).
insert_sort_acc([X|Rest], LS, RES):-insert(X, LS, RES1), insert_sort_acc(Rest, RES1, RES).

% insert item at list
% 1 - item to insert
% 2 - list to insert to
% 3 - result
insert(X,[],[X]).
insert(X, [Y|Rest], [X, Y|Rest]):-X=<Y, !.
insert(X, [Y|Y_Rest], [Y|RES_Rest]):-insert(X, Y_Rest, RES_Rest).

这篇关于Prolog同构图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！