Блог

Рассмотрим следующий график

и что это описывается нижеприведенным термином Prolog :

graph([connected(a,[b,c]), connected(b,[a,c]), connected(c,[a,b,d]), connected(d,[c]) ]).

Я хотел бы определить предикат, который преобразует вышеупомянутые соединения в список соответствующих пар. Другими словами, предикат, который дает [[a,b],[a,c],[b,c],[c,d]] результат для вышеупомянутого термина-графа.

Не могли бы вы посоветовать, как это сделать?

Моя попытка до сих пор заключается в следующем :

сопоставление 2-соседних вершин с парами :

 map2ne(adjacent(H,[K|T]),Pair) :-
    append([H],[K],L),
    append([H],T,M),
    append([L],[M],Pair).
 

Это выполняется нормально.

сопоставление 3-соседних вершин с парами :

 map3n(adjacent(H,[K,L|T]),Pair) :-
    append([H],[K],A1),
    append([H],[L],A2),
    append([A1],[A2],Z),
    append([H],T,M),
    append(Z,[M],Pair).
 

Это также выполняется нормально.

Но когда я пытаюсь расширить его до n-соседней вершины, тогда он терпит неудачу :

 mapmany(adjacent(H, [K|_]),Pair) :-
    append([H],[K],L),
    append(L,[],Pair),
    mapmany(adjacent(H,[K|_]),M),
    append(M,Pair,Pair).
 

А также сбой ниже, который был предназначен для сопоставления многих n-соседних вершин с парами :

 mapping(Map,Pairs) :-
    select(X,Map,Y),
    mapmany(X,PairX),
    append([PairX],Pairs),
    mapping(Y,Pairs).
 

Если вы собираетесь использовать решение, основанное на setof/3 , я настоятельно рекомендую определить вспомогательный предикат. Этот предикат должен точно определять, какой набор мы хотим получить. Когда мы хотим определить «множество всех ребер в графе», математически мы могли бы сказать что-то вроде « Edges является множеством всех Edge терминов, где Edge является ребром в Graph «.

Мы можем записать это очень прямо следующим образом:

 graph_edges(Graph, Edges) :-
    setof( Edge,
           graph_edge(Graph, Edge),
           Edges ).
 

Остается определить graph_edge/2 себя. Суть этого можно извлечь из решения slago:

 graph_edge(Graph, Edge) :-
    member(connected(V, Ns), Graph),
    member(W, Ns),
    edge(V, W, Edge).
 

Преимущества использования this в качестве отдельного предиката заключаются в следующем:

• setof вызов легче читать
• сам предикат имеет хорошее описательное имя
• предикат может быть протестирован изолированно
• предикат можно использовать повторно
• ^ нигде нет знаков, которые не имеют никакого значения в Prolog, за исключением усложняющих setof вызовов, которые не используют вспомогательный предикат
• не беспокойтесь о «экзистенциальной количественной оценке», которая не имеет никакого значения в Prolog, за исключением усложняющих setof вызовов, которые не используют вспомогательный предикат

В вашем коде слишком много недостатков:

• Список смежности, определенный с помощью graph/1 , состоит из терминов формы connected(Vertex, Neighbors) ; однако ваш код имеет дело со списком смежности терминов формы adjacent(Vertex, Neighbors) .
• Предикат append/3 не должен использоваться для создания всех списков; например, вместо append([H], [K], L) , вы должны использовать L = [H, K] .
• В Prolog более идиоматично представлять пару элементов V и W как V-W , вместо [V,W] .
• Согласно ответу, который вы ожидаете для приведенного примера (т.Е. [a-b,a-c,b-c,c-d] ), Один член V-W (т. Е. {V,W} ) представляет оба ребра (V,W) и (W,V). Итак, чтобы избежать избыточности, вы должны исключительно выбрать V-W или W-V вставить свой ответ (без потери общности вы можете выбрать термин, которому V предшествует W ).

Чтобы создать ребро, вы можете выполнить следующие действия:

 edge(V, W, Edge) :-
    (   V @< W
    ->  Edge = V-W
    ;   Edge = W-V ).
 

Примеры:

 ?- edge(a, b, Edge).
Edge = a-b.

?- edge(b, a, Edge).
Edge = a-b.
 

Чтобы создать все ребра, соединяющие вершину V с ее соседями Ns , без дубликатов, просто спросите:

 ?- V=a, Ns=[b,c,d], setof(E, W^Ns^(member(W,Ns), edge(V,W,E)), Edges).
V = a,
Ns = [b, c, d],
Edges = [a-b, a-c, a-d].
 

Обратите внимание, что конструкция Var^Goal указывает setof/3 не привязывать переменную Var к Goal (другими словами, указывает, что Var она определена количественно).

Обобщая эту идею, мы имеем:

 graph_edges(Graph, Edges) :-
    setof( Edge,
           V^Ns^W^( member(connected(V, Ns), Graph),
                    member(W, Ns),
                    edge(V, W, Edge)),
           Edges ).

graph([connected(a, [b, c]),
       connected(b, [a, c]),
       connected(c, [a, b, d]),
       connected(d, [c])]).
 

Пример:

 ?- graph(G), graph_edges(G, E).
G = [connected(a, [b, c]), connected(b, [a, c]), connected(c, [a, b, d]), connected(d, [c])],
E = [a-b, a-c, b-c, c-d].
 

ГРАФЫ БИБЛИОТЕКИ

В SWI-Prolog тривиальным решением было бы использовать предикат ребер/2 из library(ugraphs) . Однако будьте осторожны, поскольку представление неориентированных графов, на которых edge/2 основан предикат, отличается от того, которое вы рассматриваете (неориентированный граф в library(ugraphs) представлен списком пар вершин, где порядок вершин в этих парах имеет значение). Например:

 ?- edges([a-[b,c], b-[a,c], c-[a,b,d], d-[c]], E).
E = [a-b, a-c, b-a, b-c, c-a, c-b, c-d, d-c].