Create coordinate array from adjacency matrix - Matlab

Question

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!

Answer 1

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