3

重み付き有向グラフのエッジを表すトライアド（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」が連続していないことです。それらはコードです。これは私に3つの問題を与えます。（1）「ファントム」のスプリアス頂点が多すぎる巨大な行列。これにより、その行列で使用するアルゴリズムの結果が歪められます。（2）上記のアルゴリズムの結果でコードを復元する必要があります（これは、連続する1：mのIDコードの場合は些細なことです）。

Matlabでの回答が望ましいですが、他の言語での回答からハックバックできると思います（「Rにはこれを行うライブラリがあります」という種類の事前にパッケージ化されたソリューションでない限り）。

StackOverflowは初めてですが、コミュニティに有意義な貢献をしたいと思っています。とりあえず、よろしくお願いします！

編集：複数の頂点の原点に頂点がない場合、これは解決策になります。（これは、エッジの原点のリストとIDのリストが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

ノードID番号が連続していないことが問題である場合は、それらを連続する整数に再マップしてみませんか？あなたがする必要があるのは、すべての一意のノードIDとそれらの新しいIDへの対応の辞書を作成することです。

これは、名前付きノード（ Australia、、、、 ...）を操作するように求められた場合と実際には違いはありません。最初に、これらを連続する整数にマップします。BritainCanadaDenmark

于 2012-03-22T19:07:08.013 に答える
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 に答える
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 に答える
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 に答える