grPropagateDistance

GRPROPAGATEDISTANCE Propagates distances from a vertex to other vertices.

   DISTS = grPropagateDistance(V, E, V0, L)
   V0 is index of initial vertex
   E is array of source and target vertices
   L is the vector of length of each edge. If not specified, length 1 is
       assumed for all edges.
   The result DISTS is a column array with as many rows as the number of
   vertices, containing the geodesic distance of each vertex to the vertex
   of index V0.

   Example
     nodes = [20 20;20 50;20 80;50 50;80 20;80 50;80 80];
     edges = [1 2;2 3;2 4;4 6;5 6;6 7];
     figure; drawGraph(nodes, edges);
     axis([0 100 0 100]); axis equal; hold on
     DISTS = grPropagateDistance(nodes, edges, 2)
     DISTS = 
          1
          0
          1
          1
          3
          2
          3
     drawNodeLabels(nodes+1, DISTS);

   See also
   graphRadius, graphCenter, graphDiameter, graphPeripheralVertices
   grVertexEccentricity

0001 function d = grPropagateDistance(v, e, v0, l)
0002 %GRPROPAGATEDISTANCE Propagates distances from a vertex to other vertices.
0003 %
0004 %   DISTS = grPropagateDistance(V, E, V0, L)
0005 %   V0 is index of initial vertex
0006 %   E is array of source and target vertices
0007 %   L is the vector of length of each edge. If not specified, length 1 is
0008 %       assumed for all edges.
0009 %   The result DISTS is a column array with as many rows as the number of
0010 %   vertices, containing the geodesic distance of each vertex to the vertex
0011 %   of index V0.
0012 %
0013 %   Example
0014 %     nodes = [20 20;20 50;20 80;50 50;80 20;80 50;80 80];
0015 %     edges = [1 2;2 3;2 4;4 6;5 6;6 7];
0016 %     figure; drawGraph(nodes, edges);
0017 %     axis([0 100 0 100]); axis equal; hold on
0018 %     DISTS = grPropagateDistance(nodes, edges, 2)
0019 %     DISTS =
0020 %          1
0021 %          0
0022 %          1
0023 %          1
0024 %          3
0025 %          2
0026 %          3
0027 %     drawNodeLabels(nodes+1, DISTS);
0028 %
0029 %   See also
0030 %   graphRadius, graphCenter, graphDiameter, graphPeripheralVertices
0031 %   grVertexEccentricity
0032 
0033 % ------
0034 % Author: David Legland
0035 % E-mail: david.legland@inrae.fr
0036 % Created: 2010-09-07, using Matlab 7.9.0.529 (R2009b)
0037 % Copyright 2010-2024 INRA - Cepia Software Platform
0038 
0039 % initialize empty array for result
0040 Nv  = length(v);
0041 d   = ones(Nv, 1)*inf;
0042 d(v0) = 0;
0043 
0044 % ensure there is a valid length array
0045 if nargin < 4
0046     l = ones(size(e,1), 1);
0047 end
0048 
0049 % iterate from germ vertex until there are no more vertices to process
0050 verticesToProcess = v0;
0051 while ~isempty(verticesToProcess)
0052     % init new iteration
0053     newVerticesToProcess = [];
0054 
0055     % iterate over vertices that need to be updated
0056     for i = 1:length(verticesToProcess)
0057         vertex = verticesToProcess(i);
0058         
0059         % iterate over neighbor edges of current vertex
0060         vertexEdges = grAdjacentEdges(e, vertex);
0061         for j = 1:length(vertexEdges)
0062             iEdge = vertexEdges(j);
0063             
0064             % compute distance between current vertex and its neighbor
0065             vertex2 = grOppositeNode(e(iEdge,:), vertex);
0066             newDist = d(vertex) + l(iEdge);
0067             
0068             % update geodesic distance of neighbor node if needed
0069             if newDist < d(vertex2)
0070                 d(vertex2) = newDist;
0071                 newVerticesToProcess = [newVerticesToProcess ; vertex2]; %#ok<AGROW>
0072             end
0073         end
0074     end
0075     
0076     % update set of vertices for next tieration
0077     verticesToProcess = newVerticesToProcess;
0078 end
0079