How to populate a sparse matrix from data read from a file

I have a circuit paritioning problem. I will have a '.net' file which will have anywhere from 10-30,000 nodes. The file will have a netlist of the nodes connected. The file will be in this format:

nodes: 10
nets: 15

net 0: 0 2
net 1: 0 5 6 9 
net 2: 1 5 9 
net 3: 5 6 7 8
net 4: 2 3 6 7
net 5: 1 3 
net 6: 4 5 
net 7: 0 3
net 8: 7 9
net 9: 0 5
net 10: 2 6 7 9
net 11: 1 8
net 12: 5 8 
net 13: 7 9 
net 14: 1 4

I need to open the file and save it in a sparse matrix. Any ideas how to do this?

I have this so far:

netList = 'sample1.net'; 

fid = fopen(netList, 'r');
fgetl(fid);
rows = fgetl(fid);
numNodes = sscanf(rows,'%*s %d'); 
cols = fgetl(fid);
numNets = sscanf(cols,'%*s %d'); 
fgetl(fid);

j = zeros(1,numNets);
for var = 1:numNets
    j(1,var) = var;
end

for n = 1:numNets
    x = fgetl(fid);
    c = sscanf(x(12:end),'%d');
    for k = 1:length(c)
        i(n,k) = c(k,1)+1; 
    end
end
% Here I plan to append the next set of numbers to the i vector in preparation for the sparse but I'm not sure how to do this
fclose(fid);

Any help is appreciated, thank you.

Answer 1

[Walter Roberson]

Your line

c = sscanf(x(12:end),'%d');

is wrong unless the data is not the same as the data you showed.

Most of the input lines do not have 12 characters: only the lines that list 4 nodes have at least 12 characters. For example I will put a '|' just before the 12th character to show what part of the string would be examined by your sscanf:

net 4: 2 3 |6 7

I suggest instead

sscanf( x(find(x==':',1)+1:end), '%d')

Your "j" vector has no useful purpose unless your "net" entries are not consecutive -- and if that is the case then you need to parse the net number out of the "net" line instead of assuming it.

You cannot set your "i" array like that as it leads to trailing 0 for nets that have fewer nodes, which is a problem as node 0 is a valid node number.

I suggest you consider using cell arrays:

i = cell(numNodes,1);

then in your reading of nets, skip the c= and "for" loop and instead

i{n} = sscanf( x(find(x==':',1)+1:end), '%d');

Though how you plan to represent this all in a sparse matrix, I do not know, especially with node 0 being valid. Would anyone be heart-broken if you added 1 to all of the node numbers, thus starting the valid node numbers at 1 ?

[T.S. H]

Hi,

Thank you for your response.

The sscanf line does work, when typing the file contents out the formatting was not quite the same as what was posted. That part does work.

The original solution I had was for a small set of values around 10-50. The way I had it was in a net vs node matrix. So for the example, it would be a matrix of 15x10 and I would have the matrix all zeros except for where there are node connections. The first line of the net vs node matrix was:

[1 0 1 0 0 0 0 0 0 0]

But now I must incorporate up to tens of thousands so the net vs node matrix would be way to large and time consuming.

Yes, I did have the nets and nodes all shifted by one.

I know that the format for a sparse matrix is:

S = SPARSE(i,j,s,m,n,nzmax)

What I am unsure about is how to get my data from the file into the i and j vectors. Some kind of matrix that keeps adding the number of nodes in the net to the end of the matrix. So of size 1x2 after the first net, then 1x6, then 1x9 and so on. I simultaneously have to get the net numbers in the j matrix something like this: [1 1] then becomes [1 1 2 2 2 2] then [1 1 2 2 2 2 3 3 3] and so on. Or is there an easier way to do this?

Thanks

[Walter Roberson]

Do not build sparse matrices up incrementally if you can afford not to: instead, build up index pairs. For example, when you are reading the data in, for any fragment you could use the node numbers as one index, and use repeated copies of the net number as the other index (which should be first or second will depend on how you are going to be using the data.)

If you were to build up in cell arrays the way I show with i{n}, then the one index would be horzcat(i{:}) . The other wouldn't be too bad to create once you have the "i" cell array created:

t = arrayfun(@(IDX) repmat(IDX, 1, length(i{IDX})), 1:length(i), 'Uniform', 0);

horzcat(t{:})

[T.S. H]

I'm not totally sure what these lines do:

t = arrayfun(@(IDX) repmat(IDX, 1, length(i{IDX})), 1:length(i), 'Uniform', 0);

horzcat(t{:})

When I change the code to this:

netList = 'sample1.net';

fid = fopen(netList, 'r');

fgetl(fid);

rows = fgetl(fid);

numNodes = sscanf(rows,'%*s %d'); % Saves number of nodes

cols = fgetl(fid);

numNets = sscanf(cols,'%*s %d'); % Saves number of nets

fgetl(fid);

i = cell(1,numNodes);

for n = 1:numNets

x = fgetl(fid);

i{n} = sscanf(x(12:end),'%d')+1;

end

j = arrayfun(@(IDX) repmat(IDX, 1, length(i{IDX})), 1:length(i), 'Uniform', 0);

horzcat(j{:})

SSS = SPARSE(i,j,numNets,numNodes);

fclose(fid);

I get i and j as 1x49 cells. They store the right values for the sparse matrix, but then the sparse matrix still has an error with the types.

[T.S. H]

i and j are 1 x numNets cells