0001 function G = kernel1(E)
0002 % KERNEL1 : SSCA#2 Kernel 1 -- Graph Construction
0003 %
0004 % G = kernel1 (E)
0005 % Input:  E is a structure representing a list of triples <i,j,w>
0006 %         representing directed, weighted edges.  
0007 %         See genScalData for details.
0008 % Output: G is the graph, a structure containing the following:
0009 %         G.edgeWeights{1:maxParallelEdges} is a cell array of sparse
0010 %           matrices.  The first cell is a directed adjacency
0011 %           matrix for the whole graph, with the first weight as
0012 %           edge value.  Each cell is a matrix representing a
0013 %           subgraph of the previous one, with another set of
0014 %           parallel edges.  Positive values are integer weights,
0015 %           negative values are negated indices into ...
0016 %         G.strings(1:nStrings,1:maxStringLen) is the array of
0017 %           all string-valued weights.
0018 %         G.graph is the simple, undirected graph ignoring edge dirs
0019 %
0020 % This is a concise sequential Matlab code by John R. Gilbert, 
0021 % based loosely on computeGraph in V0.9 of the executable spec 
0022 % by Bill Mann and Theresa Meuse.
0023 % Version of 25 Feb 2005
0024 
0025 % Combine integer weights with string weights
0026 weight = E.intWeights;
0027 strEdges = find(weight == 0);
0028 weight(strEdges) = -(1:length(strEdges));
0029 %G.strings = E.strWeights(strEdges,:);
0030 
0031 % Sort edge pairs into row major order
0032 [col, perm] = sort(E.endVertices);
0033 row = E.startVertices(perm);
0034 weight = weight(perm);
0035 [row, perm] = sort(row);
0036 col = col(perm);
0037 weight = weight(perm);
0038 
0039 % Parameters of the graph
0040 nEdges = length(weight);
0041 nVertices = max(max(row),max(col));
0042 
0043 % Label each edge with which layer of the digraph it goes into
0044 maxParallelEdges = 1;
0045 layer = ones(nEdges,1);
0046 dups = ([0 row(1:end-1)] == row) & ([0 col(1:end-1)] == col);
0047 while any(dups)
0048     maxParallelEdges = maxParallelEdges+1;
0049     layer(find(dups)) = maxParallelEdges;
0050     pad = zeros(1, maxParallelEdges);
0051     dups = ([pad row(1:end-maxParallelEdges)] == row) & ...
0052            ([pad col(1:end-maxParallelEdges)] == col);
0053 end;
0054 
0055 % Create the digraph for each layer of duplicate edges
0056 for k = 1:maxParallelEdges
0057     layerk = layer == k;
0058     G.edgeWeights{k} = sparse( ...
0059         row(layerk), col(layerk), weight(layerk), nVertices, nVertices);
0060 end;
0061 
0062 % Create undirected graph
0063 G.graph = G.edgeWeights{1} | G.edgeWeights{1}';