Prolog - извлекать края из матрицы смежности

Question

У меня есть список списков, который представляет матрицу смежности графа.
Im ищет способ извлечения графики кромками из него:

?- getEdges([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],Edges). 
Edges = [[1,2],[2,4],[2,3]] 

ТНХ

Answer 1

раствор (при условии, ориентированный граф) будет несколько, как в следующем:

Предположим, что вы изучая матрицу смежности, и вы находитесь в определенном ряду. Вы должны были бы предикат, который анализирует список смежности эту строку и отфильтровывает все 0 -элементов, производя список с элементами вида:

(From, To) 

где From соответствует индексу строки и To соответствует ненулевым колонны. простой предикат, который делает это будет называться как

?- rowEdges(Row, AdjList, Result). 

Таким образом, вы можете попробовать сделать это:

rowEdges(Row, AdjList, Result) :- edges(AdjList, 1, Row, [], Result). 

edges([H|T], Column, Row, Acc, Res) :- 
    NewColumn is Column + 1, 
    (H =:= 1 -> edges(T, NewColumn, Row, [(Row, Column)|Acc], Res); 
     edges(T, NewColumn, Row, Acc, Res)). 
edges([], _, _, Res, Res). 

Предикат edges/5 рассматривает каждый элемент списка смежности в строке и, в то время как отслеживание индекс столбца элемента. Если необходимо добавить ребро, оно будет в форме (Row, Column), поэтому в качестве аргумента мы должны предоставить .

rowEdges/3 просто обеспечивает правильную инициализацию, которая должна быть пустым списком для аккумулятора (Acc) и 1 для индекса столбца. Теперь вы можете просто взять rowEdges/3 и применить его к каждой строке, в которой вы должны найти все ребра с помощью аналогичного процесса.

Пример:

?- rowEdges(2, [1,0,1,1,0,1], Result). 
Result = [(2, 6), (2, 4), (2, 3), (2, 1)]. 

Если вы хотите, чтобы ваши края будут производиться в порядке возрастания столбца, вы бы просто изменить rowEdges/3 производить обращенный выход, так как edges/5 использует аккумулятор.

rowEdges(Row, AdjList, Result) :- edges(AdjList, 1, Row, Acc, Res), reverse(Res, Result). 

Answer 2

Другим подходом является, во-первых, создание предиката, который идентифицирует допустимый край. Вот простой предикат сделать так, для неориентированных графов:

edge(M, [R,C]) :- 
    nth1(R, M, Row), 
    nth1(C, Row, 1), 
    R =< C.    % Remove this for directed graphs 

Вот пример запроса:

| ?- edge([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],Edge). 

Edge = [1,2] ? a 

Edge = [2,3] 

Edge = [2,4] 

(1 ms) no 
| ?- 

Он идентифицирует каждый край с каждым BackTrack. Он использует nth1/3 предиката, который является отношением nth1(N, List, Element), что говорит, Element находится на месте N в List, где первый элемент является элемент номер 1.

Для ориентированных графов, просто удалите условие R =< C, то вы получите:

| ?- edge([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],Edge). 

Edge = [1,2] ? a 

Edge = [2,1] 

Edge = [2,3] 

Edge = [2,4] 

Edge = [3,2] 

Edge = [4,2] 

(1 ms) no 
| ?- 

Если вы хотите другой способ, чтобы представить край, а не список [R,C] в 2-элементный, вам нужно только изменить руководитель пункта от edge(M, [R,C]) к, например, edge(M, R-C):

| ?- edge([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],Edge). 

Edge = 1-2 ? a 

Edge = 2-3 

Edge = 2-4 

(1 ms) no 
| ?- 

Если вы хотите, чтобы собрать все края в один список, вы можете использовать setof/3:

all_edges(M, Edges) :- 
    setof(E, edge(M, E), Edges). 

| ?- all_edges([[0,1,0,0],[1,0,1,1],[0,1,0,0],[0,1,0,0]],E), Edges). 

Edges = [1-2,2-3,2-4] 

yes 
| ?-