Create coordinate array from adjacency matrix - Matlab

0
votes

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!

2
matlabcoordinatesgraph-theoryadjacency-matrix
Can you please reformat that matrix A? I can't make heads or tails out of it – rayryeng
Haha sure, it looked good when I was typing it--trying to figure it out now. – DanMcK
Try indenting each line by 4 spaces. This will place it in a code block. – rayryeng
Give me a quick refresher on adjacency matrices. What does the number in entry (i,j) symbolize? My understanding is that this should only have 0s and 1s in it, and it symbolizes for node i, all the other nodes j that are connected to i. – rayryeng
Beat me to it, thanks again! The entry (i,j) symbolizes that there's an edge that exists between the ith node in the first column and the jth node in the first row. So the "1" at (6,2) indicates that there's an edge between Node 2 (see first column) and Node 1 (see first row). You're correct, though, the typical adjacency matrix for undirected graphs is the 13x13 lower diagonal of 1's and 0's--I added the first row and column with the ID numbers because those are what I ultimately need to list as the coordinate pairs. – DanMcK

2 Answers

1
votes

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
1
votes

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