Adjacency matrix from edge list (preferably in Matlab)
I have a list of triads (vertex1, vertex2, weight) representing the edges of a weighted directed graph. Since the prototype implementation happens in Matlab, they are imported as an Nx3 matrix, where N is the number of edges. So the naive implementation of this
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 problem with tributaries is that "id1" and "id2" are inconsistencies; these are codes. This gives me three problems. (1) Huge matrices with too many "phantoms", false vertices that distort the results of the algorithms that will be used with this matrix, and (2) I need to recover the codes in the results of the specified algorithms (suffice it to say it would be trivial if id -codes, where consecutive 1: m).
Answers in Matlab are preferred, but I think I can opt out of answers in other languages (unless they are prepackaged solutions like "R has a library that does this").I'm new to StackOverflow and hopefully he contributes to the community soon. Currently, thanks in advance!
Edit: This would be a solution if we didn't have vertices at the beginning of the vertex set. (This means a 1: 1 match between the list of root edges 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
source to share
Here's another solution:
Collect all the vertex ids first, as there might be a shell top 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 we find the only vertices ids:
v_id_unique = unique(v_id_all);
You can now use the ismember function to get a mapping between vertex ids and their sequential 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 the 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 matched sequential id to the original vertex id:
original_vertex_id = v_id_unique(mapped_consecutive_id);
Hope it helps.
source to share
If your problem is that node IDs don't match, why not rearrange them into sequential integers? All you have to do is create a dictionary of all unique node IDs and match them with the new IDs.
It's really no different from the case when you are asked to work with named nodes ( Australia
, Britain
, Canada
, Denmark
...) - you must first compare them with whole integers.
source to share
You can use GRP2IDX to convert your code codes to sequential numbers, and identifiers can be either numeric or not. a business. Just save your card information.
[idx1, gname1, gmap1] = grp2idx(id1);
[idx2, gname2, gmap2] = grp2idx(id2);
You can restore the original IDs with gmap1(idx1)
.
If yours id1
and id2
belong to the same set, you can apply grp2idx
to the union of them:
[idx, gname,gmap] = grp2idx([id1; id2]); idx1 = idx(1:numel(id1)); idx2 = idx(numel(id1)+1:end);
For reordering see the 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 any unique combinations id1
and id2
. You will have to take care of this.
source to share
Your first solution is close to what you want. However, it is probably best to iterate over the 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
source to share