CODEWITHSUNDEEP
matlabadjacency-matrix
syntaxfree
syntaxfree

Reputation: 237

Adjacency matrix from edge list (preferrably in Matlab)

I have a list of triads (vertex1, vertex2, weight) representing the edges of a weighted directed graph. Since prototype implementation is going on in Matlab, these are imported as a Nx3 matrix, where N is the number of edges. So the naive implementation of this is

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

The trouble with tribbles is that "id1" and "id2" are nonconsecutive; they're codes. This gives me three problems. (1) Huge matrices with way too many "phantom", spurious vertices, which distorts the results of algorithms to be used with that matrix and (2) I need to recover the codes in the results of said algorithms (suffice to say this would be trivial if id codes where consecutive 1:m).

Answers in Matlab are preferrable, but I think I can hack back from answers in other languages (as long as they're not pre-packaged solutions of the kind "R has a library that does this").

I'm new to StackOverflow, and I hope to be contributing meaningfully to the community soon. For the time being, thanks in advance!

Edit: This would be a solution, if we didn't have vertices at the origin of multiple vertices. (This implies a 1:1 match between the list of edge origins and the list of identities)

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

Upvotes: 3

Views: 6320

Answers (5)

upperBound
upperBound

Reputation: 700

Here is another solution:

First put together all your vertex ids since there might a sink vertex in your graph:

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

Then find the unique vertex ids:

v_id_unique = unique(v_id_all);

Now you can use the ismember function to get the mapping between your vertex ids and their consecutive index mappings:

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

Now you can use sub2ind to populate your adjacency matrix:

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

You can always go back from the mapped consecutive id to the original vertex id:

original_vertex_id = v_id_unique(mapped_consecutive_id);

Hope this helps.

Upvotes: 0

yuk
yuk

Reputation: 19880

You can use GRP2IDX function to convert your id codes to consecutive numbers, and ids can be either numerical or not, does not matter. Just keep the mapping information.

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

You can recover the original ids with gmap1(idx1).

If your id1 and id2 are from the same set you can apply grp2idx to their union:

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

For the reordering see a recent question - how to assign a set of coordinates in Matlab?

You can use ACCUMARRAY or SUB2IND to solve this problem.

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

or

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

Confirm if you have non-unique combinations of id1 and id2. You will have to take care of that.

Upvotes: 1

Oli
Oli

Reputation: 16065

You can use the function sparse:

sparse(id1,id2,weight,m,m)

Upvotes: 2

Li-aung Yip
Li-aung Yip

Reputation: 12486

If your problem is that the node ID numbers are nonconsecutive, why not re-map them onto consecutive integers? All you need to do is create a dictionary of all unique node ID's and their correspondence to new IDs.

This is really no different to the case where you're asked to work with named nodes (Australia, Britain, Canada, Denmark...) - you would map these onto consecutive integers first.

Upvotes: 1

AE426082
AE426082

Reputation: 633

Your first solution is close to what you want. However it is probably best to iterate over your edge list instead of the adjacency matrix. 

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

Upvotes: 0

Related Questions