Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Create an adjacency matrix matlab

Tags:

matrix

matlab

I apologize for the formatting and what seems like a very easy question. I am new to matlab and this stack exchange. I am attempting to create an adjacency matrix from a few column vectors in matlab. The information was imported from a text file. The information looks like this.

 X   Y  Z   W  

aa  bb  1   aa
bb  cc  2   bb
cc  dd  3   cc

Where columns X and Y are the names of the vertex columns. Z is the weight. Columns X and Y have about 30000 entries, with repetition. Column W is all of the vertices in my graph sorted alphabetically without repetition. The output should look like this for the sample data.

   aa  bb  cc  dd 

aa  0   1   0   0 
bb  1   0   2   0
cc  0   2   0   3
dd  0   0   3   0

I know how to create the matrix if the vertices are numerical. But I can't figure out how to assign numeric values to the vertices in column W and make everything still match up.

This code will work if the values in all the columns are numerical.

A = sparse([X; Y],[Y; X],[Z; Z]);

Where X, Y and Z are the columns above. When I try this with I get the following error

'Undefined function 'sparse' for input arguments of type 'cell'
like image 344
TheNumber23 Avatar asked May 26 '15 17:05

TheNumber23


1 Answers

You can still use sparse but you're going to have to do a bit more work. For one thing, we need to transform the labels in X and Y into unique integer IDs. Try using unique on the combined X and Y inputs so that you can get unique integer IDs shared between both.

Specifically, unique will give you a list of all unique entries of the input (so X and Y combined). The reason why we combine both X and Y is because there are certain tokens in X that may not be present in Y and vice-versa. Doing this ID assigning on the combined input will ensure consistency. The 'stable' flag is there because unique actually sorts all of the unique entries by default. If the input is a cell array of strings, the cell array is sorted in lexicographical order. If you want to maintain the order in which unique entries are encountered starting from the beginning to the end of the cell array, you use the 'stable' flag.

Next, what I would use is an associative array via a containers.Map that maps a string to a unique integer. Think of an associative array as a dictionary where the input is a key and the output is a value that is associated with this key. The best example of an associative array in this context would be the English dictionary. The key in this case is the word you want to look up, and the value is the definition of this word. The key is a character string, and the output is another character string.

Here, what we'll do is make the input a string and the output a single number. For each unique string we encountered with the combination of X and Y, we'll assign a unique ID to it. After that, we can use X and Y as inputs into the containers.Map to get our IDs which can then be used as input into sparse.

Without further ado, here's the code:

%// Your example
X = {'aa', 'bb', 'cc'};
Y = {'bb', 'cc', 'dd'};
Z = [1 2 3];

%// Call unique and get the unique entries
chars = unique([X Y], 'stable');

%// Create containers.Map
map = containers.Map(chars, 1:numel(chars));

%// Find the IDs for each of X and Y
idX = cell2mat(values(map, X)).';
idY = cell2mat(values(map, Y)).';

%// Create sparse matrix
A = sparse([idX; idY], [idY; idX], [Z; Z]);

The third and second last lines of code are a bit peculiar. You need to use the values function to retrieve the values given a cell array of keys. We have X and Y as both cell arrays, and so the output is also a cell array of values. We don't want this to be a cell array but to be a numerical vector instead as input into sparse, so that's why we use cell2mat to convert this back for us. Once we finally retrieve the IDs for X and Y, we put this into sparse to complete the matrix.

When we display the full version of A, we get:

>> full(A)

ans =

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

Minor Note

I see that W is the cell array of the vertex names sorted and in alphabetical order. If that's the case, then you don't need to do any unique calling, and you can just use W as the input into the containers.Map. As such, do this:

%// Create containers.Map
map = containers.Map(W, 1:numel(W));

%// Find the IDs for each of X and Y
idX = cell2mat(values(map, X)).';
idY = cell2mat(values(map, Y)).';

%// Create sparse matrix
A = sparse([idX; idY], [idY; idX], [Z; Z]);
like image 163
rayryeng Avatar answered Sep 18 '22 14:09

rayryeng