3

我有一个表示加权有向图边缘的三元组（顶点1、顶点2、权重）列表。由于原型实现是在 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

tribbles 的问题是“id1”和“id2”是不连续的；它们是代码。这给了我三个问题。(1) 具有太多“幻像”、虚假顶点的巨大矩阵，这会扭曲与该矩阵一起使用的算法的结果；(2) 我需要恢复所述算法结果中的代码（可以这么说如果连续 1:m 的 id 代码是微不足道的）。

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
4

5 回答 5

2

您可以使用以下功能sparse：

sparse(id1,id2,weight,m,m)
于 2012-03-22T18:48:54.450 回答
1

您可以使用GRP2IDX函数将您的 id 代码转换为连续的数字，id 可以是数字也可以不是数字，没关系。只保留映射信息。

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

您可以使用 恢复原始 ID 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。你将不得不照顾它。

于 2012-03-22T19:23:00.643 回答
1

如果您的问题是节点 ID 号不连续，为什么不将它们重新映射到连续整数上呢？您需要做的就是创建一个包含所有唯一节点 ID 的字典以及它们与新 ID 的对应关系。

Australia这与要求您使用命名节点 ( , Britain, Canada, ...)的情况确实没有什么不同Denmark- 您首先将它们映射到连续的整数上。

于 2012-03-22T19:07:08.013 回答
0

这是另一个解决方案：

首先将所有顶点 id 放在一起，因为图中可能存在下沉顶点：

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

然后找到唯一的顶点ID：

v_id_unique = unique(v_id_all);

现在您可以使用ismember函数来获取顶点 id 与其连续索引映射之间的映射：

[~,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);

您总是可以从映射的连续 id 返回到原始顶点 id：

original_vertex_id = v_id_unique(mapped_consecutive_id);

希望这可以帮助。

于 2012-03-23T00:01:02.023 回答
0

您的第一个解决方案接近您想要的。然而，最好迭代你的边缘列表而不是邻接矩阵。 

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
于 2012-03-22T17:18:43.687 回答