Матрица смежности из списка ребер (предпочтительно в Matlab) - PullRequest
Новая
       2

Матрица смежности из списка ребер (предпочтительно в Matlab)

3 голосов
/ 22 марта 2012

У меня есть список триад (vertex1, vertex2, weight), представляющих ребра взвешенного ориентированного графа.Поскольку реализация прототипа происходит в Matlab, они импортируются как матрица Nx3, где N - число ребер.Таким образом, наивная реализация этого 

id1 = L(:,1);
id2 = L(:,2);
weight = L(:,3);
m = max(max(id1, id2)) % to find the necessary size
V = zeros(m,m)
for i=1:m
   V(id1(i),id2(i)) = weight(i)
end

Проблема с трибулой заключается в том, что «id1» и «id2» не являются последовательными;это коды.Это дает мне три проблемы.(1) Огромные матрицы со слишком большим количеством «фантомных», ложных вершин, которые искажают результаты алгоритмов, которые будут использоваться с этой матрицей, и (2) мне нужно восстановить коды в результатах этих алгоритмов (достаточно сказать, что этобыть тривиальным, если идентификационные коды последовательны 1: m).

Ответы в Matlab предпочтительнее, но я думаю, что могу вернуться к ответам на других языках (если они не являются предварительно упакованными решениямивроде "R имеет библиотеку, которая делает это").

Я новичок в StackOverflow и надеюсь, что скоро внесу весомый вклад в сообщество.В настоящее время, спасибо заранее!

Редактировать: Это было бы решением, если бы у нас не было вершин в начале нескольких вершин.(Это подразумевает совпадение 1: 1 между списком происхождения ребер и списком идентичностей) 

for i=1:n
   for j=1:n
   if id1(i) >0 & i2(j) > 0
       V(i,j) = weight(i);
   end
   end
   end

Ответы [ 5 ]

2 голосов
/ 22 марта 2012

Вы можете использовать функцию sparse: 

sparse(id1,id2,weight,m,m)
1 голос
/ 22 марта 2012

Вы можете использовать функцию GRP2IDX , чтобы преобразовать ваши идентификаторы в последовательные числа, и идентификаторы могут быть как числовыми, так и нет, не имеет значения. Просто сохраняйте картографическую информацию. 

[idx1, gname1, gmap1] = grp2idx(id1);
[idx2, gname2, gmap2] = grp2idx(id2);

Вы можете восстановить исходные идентификаторы с помощью gmap1(idx1).

Если ваши id1 и id2 относятся к одному и тому же набору, вы можете применить grp2idx к их объединению: 

[idx, gname,gmap] = grp2idx([id1; id2]);
idx1 = idx(1:numel(id1));
idx2 = idx(numel(id1)+1:end);

Для переупорядочения см. Недавний вопрос - как назначить набор координат в Matlab?

Вы можете использовать ACCUMARRAY или SUB2IND для решения этой проблемы. 

V = accumarray([idx1 idx2], weight);

или 

V = zeros(max(idx1),max(idx2)); %# or V = zeros(max(idx));
V(sub2ind(size(V),idx1,idx2)) = weight;

Подтвердите, если у вас есть неуникальные комбинации id1 и id2. Вам придется позаботиться об этом.

1 голос
/ 22 марта 2012

Если ваша проблема в том, что идентификационные номера узлов не являются последовательными, то почему бы не переназначить их на последовательные целые числа?Все, что вам нужно сделать, это создать словарь всех уникальных идентификаторов узлов и их соответствия новым идентификаторам.

Это на самом деле не отличается от случая, когда вас просят работать с именованными узлами (Australia,Britain, Canada, Denmark ...) - сначала вы должны отобразить их на последовательные целые числа.

0 голосов
/ 23 марта 2012

Вот еще одно решение:

Сначала соберите все ваши идентификаторы вершин, так как в вашем графе может быть вершина стока: 

v_id_from = edge_list(:,1);
v_id_to = edge_list(:,2);
v_id_all = [v_id_from; v_id_to];

Затем найдите уникальные идентификаторы вершин: 

v_id_unique = unique(v_id_all);

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

[~,from] = ismember(v_id_from, v_id_unique);
[~,to] = ismember(v_id_to, v_id_unique);

Теперь вы можете использовать sub2ind для заполнения вашей матрицы смежности: 

adjacency_matrix = zeros(length(from), length(to));
linear_ind = sub2ind(size(adjacency_matrix), from, to);
adjacency_matrix(linear_ind) = edge_list(:,3);

Вы всегда можете вернуться от сопоставленного последовательного идентификатора к исходному идентификатору вершины: 

original_vertex_id = v_id_unique(mapped_consecutive_id);

Надеюсь, это поможет.

0 голосов
/ 22 марта 2012

Ваше первое решение близко к тому, что вы хотите. Однако, вероятно, лучше всего перебирать свой список ребер вместо матрицы смежности. 

edge_indexes = edge_list(:, 1:2);
n_edges = max(edge_indexes(:));
adj_matrix = zeros(n_edges);
for local_edge = edge_list' %transpose in order to iterate by edge
    adj_matrix(local_edge(1), local_edge(2)) = local_edge(3);
end
...