将边列表转换为邻接矩阵

Question

如果我在 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]

Answer 1

邻接矩阵应仅包含布尔值以指示顶点之间存在边。我认为这个函数假定 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

Answer 2

如果需要，我个人会取消您的循环代码并利用 sparse then convert back to a 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);

第一行代码表示您的边列表，其中每行对由两个相互关联的节点组成（即它们由一条边连接）。第二行从边缘列表中删除所有重复的行。第三行确定邻接矩阵应该有多大。我们需要弄清楚最大的节点 ID 是什么，以便我们可以分配一个 N x N 稀疏矩阵，其中 N 是最大的节点 ID。最后一行代码简单地使用边列表的第一列和第二列来填充稀疏矩阵中的条目，我们将它们设置为一个并确保矩阵的大小为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

将边列表转换为邻接矩阵

Convert edge list to adjacency matrix

matlab

adjacency-matrix

权重仅为 1 的示例

第三列中有权重的示例