Преобразование списка ребер в матрицу смежности

если у меня есть следующий код в Matlab

function adj=edgeL2adj(el)
nodes=sort(unique([el(:,1) el(:,2)])); % get all nodes, sorted
adj=zeros(numel(nodes));   % initialize adjacency matrix
% across all edges
for i=1:size(el,1);adj(find(nodes==el(i,1)),find(nodes==el(i,2)))=el(i,3);
end

которые преобразуют список ребер m x 3 в список смежности n x n, но у меня есть матрица списка ребер m x 2, так что необходимо изменить в предыдущем коде, чтобы получить истинный результат.

пример:

if edge list =[1 2;2 3;2 4] then adjacency matrix=[0 1 0 0;0 0 1 1;0 0 0 0; 0 0 0 0]

person Asmaa Daoud    schedule 29.07.2015    source источник


Ответы (2)


Я бы лично отказался от вашего кода цикла и воспользовался преимуществами sparse, а затем преобразовать обратно в матрицу full, если это необходимо. Первый столбец состоит из исходного узла, а второй столбец состоит из целевого узла. Вы просто устанавливаете для всех этих записей в разреженной матрице значение 1. Однако, судя по вашему коду, третий столбец вашего списка ребер также является соответствующим весом, поэтому я напишу код, который будет предполагать оба случая. Кроме того, убедитесь, что вы отфильтровываете повторяющиеся строки, используя unique:

Пример с весами, равными 1

edgelist = [1 2;2 3;2 4];
edgelist = unique(edgelist, 'rows');
sz = max(edgelist(:));
A = sparse(edgelist(:,1), edgelist(:,2), 1, sz, sz);

Первая строка кода обозначает ваш список ребер, где каждая пара строк состоит из двух узлов, инцидентных друг другу (т.е. они соединены ребром). Вторая строка удаляет все повторяющиеся строки из списка ребер. Третья строка определяет, насколько большой должна быть матрица смежности. Нам нужно выяснить, каков самый большой идентификатор узла, чтобы мы могли выделить разреженную матрицу N x N, где N — это наибольший идентификатор узла. Последняя строка кода просто использует первый и второй столбцы списка ребер для заполнения записей в разреженной матрице, мы устанавливаем их равными единице и гарантируем, что размер матрицы равен N x N.

Мы получаем это:

>> A

A =

   (1,2)        1
   (2,3)        1
   (2,4)        1

При желании вы можете преобразовать матрицу в полную, используя функцию full:

>> full(A)

ans =

     0     1     0     0
     0     0     1     1
     0     0     0     0
     0     0     0     0

Как видите, это соответствует желаемому результату.

Пример с весами в третьем столбце

edgelist = [1 2 0.1;2 3 0.2;2 4 0.3];
edgelist = unique(edgelist, 'rows');
sz = max(max(edgelist(:, 1:2)));
A = sparse(edgelist(:,1), edgelist(:,2), edgelist(:,3), sz, sz);

Тот же код, что и раньше, но вы меняете третий параметр на sparse с третьим столбцом edgelist.

Вот что мы получаем:

>> A

A =

   (1,2)       0.1000
   (2,3)       0.2000
   (2,4)       0.3000

>> full(A)

ans =

         0    0.1000         0         0
         0         0    0.2000    0.3000
         0         0         0         0
         0         0         0         0
person rayryeng    schedule 29.07.2015
comment
У @ChisholmKyle есть комментарий для вас под их ответом. - person beaker; 29.07.2015

Матрица смежности должна содержать только логические значения, указывающие на наличие ребра между вершинами. Я думаю, что эта функция предполагает, что третий столбец el - это все единицы. В комментариях уточняется, что, возможно, это на самом деле весы. Функцию тоже можно упростить. Вот измененный код:

function adj=edgeL2adj(el)
    nodes=unique(el(:, 1:2)); % get all nodes, sorted
    adj=zeros(numel(nodes));   % initialize adjacency matrix
    % across all edges
    for i=1:size(el,1)
        adj(nodes==el(i,1),(nodes==el(i,2)))=1;
        % if third column is weights, 
        % adj(nodes==el(i,1),(nodes==el(i,2)))=el(i, 3);
    end
person ChisholmKyle    schedule 29.07.2015
comment
Матрицы смежности часто используют это значение для указания веса ребра; третий столбец el в исходной задаче не обязательно должен был состоять из всех единиц. - person beaker; 29.07.2015
comment
Ах, хорошо знать. Я не слишком хорошо знаком с графами, вершинами и матрицами смежности. Спасибо за информацию. - person ChisholmKyle; 29.07.2015
comment
У меня недостаточно представителей, чтобы комментировать другие ответы, но @raryeng, если вы видите это, исходная функция вызывает unique(), поэтому она предназначена для игнорирования повторяющихся вершин. Возможно, вы можете изменить свой код, чтобы сохранить ту же функциональность, что и рассматриваемая функция? - person ChisholmKyle; 29.07.2015
comment
Повторяющиеся ребра между двумя вершинами не будут иметь эффекта, поскольку запись в разреженной матрице просто заменяется на 1. Однако при желании вы можете применить уникальность к строкам. С этим я скоро отредактирую свой пост. - person rayryeng; 29.07.2015
comment
Странная вещь происходит с повторяющимися значениями. Глядя в документацию для sparse, глубоко ниже скрыта эта строка: Если i и j имеют одинаковые значения для нескольких элементов в v, эти элементы складываются вместе, так что это будет не просто 1, а количество дубликатов. - person ChisholmKyle; 29.07.2015
comment
Интересный. Должно быть, он изменился в более поздних версиях. На моем он заменяет значения. Спасибо за совет. - person rayryeng; 29.07.2015