Создайте матрицу смежности из графического файла входного набора данных с помощью редактора Matlab.

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

Первая строка файла набора данных представляет количество узлов и ребер соответственно. Следующие строки представляют node1 и node2, обозначая ребро, существующее между ними. Например: файл набора данных amazon.graph содержит следующее

Ниже приведен файл amazon.graph
4 6 // количество узлов и ребер
0 1 // ребро между узлами 0 и 1
1 3
2 3
1 2
0 2
0 3

Эти данные содержатся в файле с именем «amazon.graph». Мне нужна помощь с функцией Matlab, которая может читать файл и строить матрицу смежности из файла набора данных.


person Nikhil Katre    schedule 06.10.2014    source источник


Ответы (1)


Используйте sparse для построения матрицы:

x = [4 6
     0 1
     1 3
     2 3
     1 2
     0 2
     0 3]; %// data

adjMatrix = sparse(x(2:end,1)+1, x(2:end,2)+1, 1, x(1,1), x(1,2));

Получается разреженная матрица. При необходимости вы можете преобразовать в полную форму:

adjMatrix = full(adjMatrix);

В вашем примере это дает

adjMatrix =

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

Чтобы сделать граф симметричным (неориентированным):

s = max(x(1,1), x(1,2)); %// take largest dimemsion
adjMatrix = sparse(x(2:end,1)+1, x(2:end,2)+1, 1, s, s); %// now matrix is square
adjMatrix = adjMatrix | adjMatrix.'; %'// apply "or" with transpose to make symmetric
adjMatrix = full(adjMatrix); %// convert to full if needed

Если у вас есть данные в файле, вы можете считать их в переменную x, используя textread. Например, если файл data.txt содержит текст

4     6
0     1
1     3
2     3
1     2
0     2
0     3

просто используйте

x = textread('data.txt');

Затем вы можете применить вышеизложенное для создания adjMatrix из x.

person Luis Mendo    schedule 06.10.2014
comment
Будет ли этот метод работать, если файл набора данных графа содержит порядка тысяч узлов и ребер? - person Nikhil Katre; 06.10.2014
comment
Также не могли бы вы рассказать, как прочитать данные из файла для построения матрицы adj - person Nikhil Katre; 06.10.2014
comment
Да, этот метод эффективно использует память, поэтому он работает для любого разумного размера. Тысячи не должны быть проблемой. Что касается того, как читать данные из файла, см. обновленный ответ. - person Luis Mendo; 06.10.2014
comment
Последний вопрос, Луис, я хотел спросить, предположим, что граф неориентирован и ребро, представленное в графе, таково, что 0 3 присутствует, а 3 0 отсутствует. Итак, как справиться с этим при создании рекламной матрицы. Я знаю, что ты ответил на этот вопрос, но почему-то он потерялся. Я извиняюсь, что спрашиваю это снова. :) - person Nikhil Katre; 06.10.2014
comment
Я ответил в комментарии, но это было неправильно, поэтому я удалил его. Я отредактировал ответ с правильным способом: вы строите квадратную матрицу с наибольшим из двух измерений, а затем применяете или с ее транспонированием - person Luis Mendo; 06.10.2014
comment
Вы молодец, Луис, большое спасибо... просто чтобы подтвердить, что третья строка кода adjMatrix = adjMatrix l adjMatrix ' ; я прав ? - person Nikhil Katre; 06.10.2014
comment
В этом случае ' и .' дают одинаковый результат. Но я предпочитаю использовать .' для транспонирования. См., например, здесь - person Luis Mendo; 06.10.2014