Question on reading datafile in matlab

I have a data file that looks like this:

SECTION Graph
Nodes 10
Edges 5
E 1 2 10
E 2 4 2
E 4 3 1
E 9 10 9
E 4 10 6
E 1 2 10
SECTION Terminals
Terminals 5
TP 1 3
TP 2 3
TP 3 5
TP 4 7
TP 8 9
END

EOF

means there is an edge between 1 and 2 and have a cost 10 and Terminals mean that node 13 have cost 3.I would like to read this data from my data file and create an adjacency matrix G using this data where the G(i,j) is the cost of edge(i,j) and it is -1 if there is no edge and a matrix P where P(i) is the cost of the i node and zero if no cost. Please Help example:

G = [0 10 0 0 0 0 0 0 0 0;
     10 0 0 2 0 0 0 0 0 0;
     0 0 0 1 0 0 0 0 0  0;
     0 0 1 0 0 0 0 0 0 6 ;
     0 0 0 0 0 0 0 0 0 0;
     0 0 0 0 0 0 0 0 0 0;
     0 0 0 0 0 0 0 0 0 0;
     0 0 0 0 0 0 0 0 0 0;
     0 0 0 0 0 0 0 0 0 10;
     0 0 0 0 6 0 0 0 10 0;]

P = [3 3 5 7 0 0 0 9 0 0]

[Cedric]

What have you done so far?

[jana]

I've created the matrix G, but I am having trouble with reading Terminals part:

function G = adjacencyMatrix()
      filename    = 'myFile.txt';
      delimiterIn = ' ';
      startRow    = 1;
      startCol    = 1;
      M           = dlmread(filename,delimiterIn,startRow,startCol);
      numNodes    = M(1,1); 
      G           = 0*ones(numNodes);
      node1       = M(3:end,1);
      node2       = M(3:end,2);
      cost        = M(3:end,3);
      for k = 1:numel(node1)
          G(node1(k),node2(k)) = cost(k);
          G(node2(k),node1(k)) = cost(k);
      end
end

[Cedric]

Ok, see my solution. Your file doesn't have a regular structure, so you cannot read it using DLMREAD. This leaves you basically with two approaches. The standard one based on FGETL/FSCANF, which is what you would be expected to produce for a homework I guess (which I can therefore not fully write for you), and the second based on pattern matching. I chose the latter, so you have something which works if it is not for a homework.

Let me know if you want/need to implement the standard approach and we can discuss it. Basically you would have to FOPEN the file, skip the first line with FGETL, read the second with FGETL and extract the number of nodes, same for the 3rd line (number of edges), and then read lines until it doesn't start with character 'E' (you could use the number of edges as well and implement a FOR loop, but not with the example that you provided, because there is a mismatch between Edges=5 and the six lines of edges). You would then proceed the same way for terminals, skipping a line with FGETL, reading the next and extracting the number of terminals, and then reading the block of terminals line by line.

Answer 1

[Cedric]

Here is a start assuming that it is not for a homework (in the sense that a REGEXP-based approach would probably not be accepted as a homework solution).

 % - Read file.
 content = fileread( 'myFile.txt' ) ;

 % - Extract graph information.
 pattern    = 'Nodes\s+(?<nodes>\d+)\s+Edges\s+(?<edges>\d+)\s+(?<data>.*)SEC' ;
 graph      = regexp( content, pattern, 'names' ) ;
 graph.data = textscan( graph.data, '%*s %f %f %f' ) ;

 % - Extract terminals information.
 pattern     = 'Terminals\s+(?<terminals>\d+)\s+(?<data>.*)END' ;
 terminals   = regexp( content, pattern, 'names' ) ;
 terminals.data = textscan( terminals.data, '%*s %f %f' ) ;

Once this is executed, observe the content of structs graph and terminals:

 >> graph
 graph = 
    nodes: '10'
    edges: '5'
     data: {[6x1 double]  [6x1 double]  [6x1 double]}

 >> terminals
 terminals = 
    terminals: '5'
         data: {[5x1 double]  [5x1 double]}

and see how you can exploit it to build G and P.

EDIT: you might want to convert graph.nodes, graph.edges, and terminals.terminals to double using STR2DOUBLE, e.g.

 graph.nodes = str2double( graph.nodes ) ;

[jana]

Thankyou! I figured it out myself (rewrote my code in a different way). But your method is way shorter than mine!:) PS: it is not a homework, just a part of my research. I am new to matlab.

[Cedric]

Ok, well, you didn't start with the easiest type of file to read! If you read my comment below your question, it should roughly match what you implemented afterwards (I guess).

[jana]

I was wondering how to get access to the values of graph.data. It seems like the first part of the data lie in just one cell. If I have to create a matrix G, I'll have to get access to all the values in that cell. Is there a way or a command that i should be using?

[Cedric]

You must use curly brackets to access the content of a cell (parentheses are for block-indexing, and block-indexing a cell array returns cells) . Therefore, to get the first column of node IDs:

 >> node1 = graph.data{1}
 node1 =
     1
     2
     4
     9
     4
     1

If you want to implement the loop that you defined in your function above, you can either define node1, node2, and cost, as I just did for node1 above, or index directly graph.data, first to get to cells' content, then to index relevant elements, e.g.

 for k = 1 : graph.edges
    G(graph.data{1}(k),graph.data{2}(k)) = graph.data{3}(k) ;
 end

[Cedric]

Note that you could avoid the loop using SUB2IND, but I am not sure that it is really better, so don't change for that at the moment:

 sizeG = [graph.nodes, graph.nodes] ;
 G_s2i = zeros( sizeG ) ;
 ind   = sub2ind( sizeG, graph.data{1}, graph.data{2} ) ;
 G_s2i(ind) = graph.data{3} ;
 G_s2i = G_s2i + G_s2i.' ;

Also, if you had a lot of nodes, the adjacency matrix might become larger than your RAM available and quite full of zeros. In such case, we use sparse matrices, which store only non-zero elements:

 G_sp = sparse( graph.data{1}, graph.data{2}, graph.data{3}, ...
                graph.nodes, graph.nodes ) ;
 G_sp = G_sp + G_sp.' ;

 >> G_sp 
 G_sp =
   (2,1)       20
   (1,2)       20
   (4,2)        2
   (4,3)        1
   (2,4)        2
   (3,4)        1
  (10,4)        6
  (10,9)        9
   (4,10)       6
   (9,10)       9

Displaying a sparse array shows only non=zero elements and their indices. Use FULL to convert a sparse array to its full version (you can't do this if the full array is too large for your memory)..

 >> full(G_sp)
 ans =
     0    20     0     0     0     0     0     0     0     0
    20     0     0     2     0     0     0     0     0     0
     0     0     0     1     0     0     0     0     0     0
     0     2     1     0     0     0     0     0     0     6
     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     0     9
     0     0     0     6     0     0     0     0     9     0

Finally, function SPY allows you to visualize the filling of any numric array (sparse or full). It doesn't display cost though, but having visually the location of non-zero elements is often interesting (if only for debugging):

 >> spy( G_sp ) ;

[jana]

Sorry for the late reply. I've a lot of nodes, so I'll be using the sparse function. Thank you so much for helping me out here. I learnt a lot!

[Cedric]

You're welcome!