CODEWITHSUNDEEP
matlabcoordinatesgraph-theoryadjacency-matrix
DanMcK
DanMcK

Reputation: 37

Create coordinate array from adjacency matrix - Matlab

I have a quick graph theory question.

I have a 13 x 13 adjacency matrix in Matlab. I've already taken just the lower diagonal (this is an undirected graph) and subtracted off the identity matrix (so there aren't edges joining a node to itself). I then added a column on the left and a row on the top with the ID numbers of the four nodes. The resulting 14 x 14 adjacency matrix looks like this: 

A = 

    0   1   1   1   1   2   2   2   3   3   3   4   4   4
    1   0   0   0   0   0   0   0   0   0   0   0   0   0
    1   0   0   0   0   0   0   0   0   0   0   0   0   0
    1   0   0   0   0   0   0   0   0   0   0   0   0   0
    1   0   0   0   0   0   0   0   0   0   0   0   0   0
    2   1   0   0   0   0   0   0   0   0   0   0   0   0
    2   0   0   0   0   0   0   0   0   0   0   0   0   0
    2   0   0   0   0   0   0   0   0   0   0   0   0   0
    3   0   0   1   0   0   0   0   0   0   0   0   0   0
    3   0   0   0   0   0   0   0   0   0   0   0   0   0
    3   0   1   0   0   0   0   0   0   0   0   0   0   0
    4   1   0   0   0   1   0   0   0   0   0   0   0   0
    4   0   0   0   1   0   0   0   0   0   0   0   0   0
    4   0   0   0   0   0   0   1   0   0   0   0   0   0

How can I create the coordinate array from this? I know the result should have 7 rows (one for each unique node pair).

Please let me know if you can help. Thanks in advance!

Upvotes: 0

Views: 1541

Answers (2)

Luis Mendo
Luis Mendo

Reputation: 112769

It appears that what you want is:

[ii, jj] = find(A(2:end,2:end)); %// row and col indices of ones in inner matrix
result = [ A(ii+1,1) A(1,jj+1).' ]; %'// node numbers corresponding to ii and jj

In your example, this gives

result =
     2     1
     4     1
     3     1
     3     1
     4     1
     4     2
     4     2

If you need unique rows:

result = unique(result, 'rows');

which gives

result =

     2     1
     3     1
     4     1
     4     2

Upvotes: 1

rayryeng
rayryeng

Reputation: 104565

We can use the node IDs that are provided at the first row and first column to help us create a node adjacency list. What we need to do is split up the variables so that we separate out the first row, called rowList and the first column colList. We will denote these the row and column lists respectively. We will also extract the adjacency matrix which is the rest of the matrix. The basic algorithm is the following:

  1. Find those rows and columns that are non-zero in the adjacency matrix.
  2. Use these rows and columns to index the corresponding rows and columns lists and spit out a co-ordinate array.

Without further ado:

rowList = A(2:end,1);
colList = A(1,2:end).';
AdjMatr = A(2:end,2:end);
[nonZeroRows, nonZeroCols] = find(AdjMatr);
nodeList = [rowList(nonZeroRows) colList(nonZeroCols)];

The output thus gives:

nodeList =

 2     1
 4     1
 3     1
 3     1
 4     1
 4     2
 4     2

This answer does not give unique rows of course, and produces duplicates. If you wish to have unique rows, consider doing:

nodeListUnique = unique(nodeList, 'rows');

The output is:

nodeListUnique =

 2     1
 3     1
 4     1
 4     2

Upvotes: 1

Related Questions