0001 function subgraphs = kernel3 (G, pathlen, starts)
0002 % KERNEL3 : SSCA#2 Kernel 3 -- Graph Extraction
0003 %
0004 % subgraphs = kernel3 (G, pathlen, starts)
0005 % Input:  G - directed, weighted multigraph (see kernel1 for details)
0006 %         pathlen - integer
0007 %         starts - vector of vertex numbers
0008 % Output: subgraphs - cell array of structs representing subgraphs.
0009 %           For each vertex starts(i), subgraphs{i} is a directed
0010 %           graph representing those vertices and edges in the
0011 %           subgraph of G induced by vertices reachable from the 
0012 %           start vertex by paths of at most "pathlen" edges.
0013 %         subgraphs{i}.edgeWeights{} are the weighted edges,
0014 %         subgraphs.vtxmap is the map from subgraph vertex #s
0015 %           to vertex numbers of G.
0016 %
0017 % This is a concise sequential Matlab code by John R. Gilbert, 
0018 % based loosely on findSubgraphs in V0.9 of the executable spec 
0019 % by Bill Mann and Theresa Meuse.
0020 % Version of 20 Feb 2005
0021 % Viral Shah, May 23, 2006
0022 
0023 A = spones(G.edgeWeights{1});
0024 nv = length (A);
0025 npar = length(G.edgeWeights);
0026 nstarts = length(starts);
0027 
0028 % Use sparse matrix multiplication to do several BFS searches at once.
0029 s = sparse (starts, 1:nstarts, 1, nv, nstarts);
0030 for k=1:pathlen
0031     s = A * s;
0032     s = (s ~= 0);
0033 end
0034 
0035 for i = 1:nstarts
0036     x = s(:,i);
0037     vtxmap = find(x);
0038     S.edgeWeights{1} = G.edgeWeights{1}(vtxmap,vtxmap);
0039     for j = 2:npar
0040         sg = G.edgeWeights{j}(vtxmap,vtxmap);
0041         if nnz(sg) == 0
0042             break;
0043         end;
0044         S.edgeWeights{j} = sg;
0045     end;
0046     S.vtxmap = vtxmap;
0047     subgraphs{i} = S;
0048 end