www.pudn.com > ConstrainedEM.zip > paintedPath.m

function [path,cutArcs] = paintedPath(E,paint,fromNode,toNode,silent) 
 
% Painted path algorithm, with graphics 
% 
% Enter with E = node-arc incidence matrix, 
%            paint = vector of colours 'r' 'g' 'w' 'b' (default all 'g') 
%            fromNode = origin (default 1) 
%            toNode   = destination (default 0) 
%            silent   = 1 to turn off graphics (default 0) 
% and the algorithm paints the network according to the direction 
% vector, then either finds a path from origin to destination, 
% or finds a cut separating origin from destination. 
% 
% If a path is found, it is returned as a list of arc indices, 
% with negative indices corresponding to arcs traversed in the reverse 
% direction, and the cut is set to empty. 
% 
% If a cut is found, the path is set to empty and the set of nodes on 
% the origin side of the cut is returned, along with the arcs crossing 
% the cut (negative for reverse arcs). 
% 
% If toNode is not a node of the network, both path and cut are returned 
% empty and cutArcs contains a tree spanning all nodes reachable from fromNode. 
% 
% 
% Note that this is not an efficient implementation: I have used the 
% node-arc incidence matrix to maintain similarity with lectures. 
 
% For use in course Mathematics 2A1. 
% 
% Copyright (c) March 1997, Alistair Mees, University of Western Australia.  
% 
% This program may be freely used for education but may not be 
% sold or used for commercial purposes without my express written 
% permission. 
% 
% email: Alistair.Mees@uwa.edu.au 
 
 
 
% Set up the output arguments: 
if nargout>=2 
  cutArcs = []; 
end 
path = []; 
 
 
% Set up the input arguments: 
if nargin<5 
  silent = 0; 
end 
if nargin<4 
  toNode = 0; 
end 
if nargin<3 
  fromNode = 1; 
end 
if nargin<2 
  paint = []; 
end 
 
% Make sure the input args make sense, and if necessary paint the network: 
[nNodes,nArcs,paint] = ppSanityCheck(E,paint,fromNode,toNode); 
 
if ~silent 
  % Display the network: 
  [arcHandles,nodeHandles,nodePosns] = showNetwork(E,paint); 
  set(nodeHandles,'facecolor',[0.4 0.4 0.4]); 
end 
 
 
% Painted path algorithm: 
labelled = fromNode; 
scanned = []; 
arcUsed = zeros(1,nNodes); 
 
while ~isempty(labelled)  &  ~any(toNode==labelled) 
 
  % Scan first labelled node: 
  n = labelled(1); 
   
  % Find arcs incident on node n: 
  outArcs = find(E(n,:)==1); 
  inArcs = find(E(n,:)==-1); 
  % Keep only those that satisfy the painting: 
  if ~isempty(outArcs) 
    outArcs = outArcs(find(paint(outArcs)=='g' | paint(outArcs)=='w')); 
  end 
  if ~isempty(inArcs) 
    inArcs  = inArcs(find(paint(inArcs)=='g' | paint(inArcs)=='b')); 
  end 
   
  % Look at nodes at other ends of arcs; if not labelled or scanned, label them: 
  for a = outArcs 
    destNode = find(E(:,a)==-1); 
	if ~any(ismember(destNode,labelled)) & ~any(ismember(destNode,scanned)) 
	  labelled = [labelled,destNode]; 
	  arcUsed(destNode) = a; 
	  if ~silent 
	    % Display arc as used: 
	    set(arcHandles(a),'linewidth',4); 
        % Display node as labelled: 
        set(nodeHandles(destNode),'facecolor','c');  
	  end 
	  if destNode==toNode 
	    break; 
	  end 
	end 
  end 
  for a = inArcs 
    srcNode = find(E(:,a)==1); 
	if ~any(ismember(srcNode,labelled)) & ~any(ismember(srcNode,scanned)) 
	  labelled = [labelled,srcNode]; 
	  arcUsed(srcNode) = -a;   % negative sign flags reverse arc 
	  if ~silent 
	    % Display arc as used: 
	    set(arcHandles(a),'linewidth',4); 
        % Display node as labelled: 
        set(nodeHandles(srcNode),'facecolor','c'); 
	  end 
	  if srcNode==toNode 
	    break; 
	  end 
	end 
  end 
   
  % Shift node n from labelled set to scanned set: 
  labelled(1) = []; 
  scanned = [scanned,n]; 
   
  if ~silent 
    % Paint node n as scanned: 
    set(nodeHandles(n),'facecolor','m'); 
    drawnow 
  end 
 
end 
 
% On exit either we have a path or a cut: 
if ~isempty(labelled)  &  any(toNode==labelled) 
 
  % Find the path by walking back from the toNode: 
  path = []; 
  n = toNode; 
  while n ~= fromNode 
    path = [arcUsed(n), path]; 
	if arcUsed(n)>0 
	  m = find( E(:,abs(arcUsed(n)))==1 ); 
	else 
	  m = find( E(:,abs(arcUsed(n)))==-1 ); 
	end 
	if isempty(m) 
	  error 'Can''t find the node I came here from!' 
	elseif m==0 
	  error 'Bad arc in reverse path' 
	elseif m==n 
	  error 'Program error: failed to find other end of path' 
	end 
	n = m; 
	   
  end 
 
  if ~silent 
    set(arcHandles,'linewidth',0.5); 
    set(arcHandles(abs(path)),'linewidth',4); 
    title 'Arcs emphasized form a path' 
  end 
 
elseif toNode<1  |  toNode>nNodes 
 
  % This case deals with e.g. setting nNodes to zero to get a spanning tree. 
  % We return empty path and cut, and set cutArcs to a spanning tree. 
  cut = []; 
  path = []; 
  % Just see which arcs we've used. 
  cutArcs = arcUsed(find(arcUsed~=0)); 
  if ~silent 
    title 'Arcs emphasized form a tree' 
  end 
   
else 
 
  % Return the set of labelled and/or scanned nodes: 
  cut = [scanned, labelled]; 
  if ~silent 
    % Identify the cut arcs and make them dotted and thick: 
    set(arcHandles,'linewidth',0.5); 
  end 
 
  % Now find the cut arcs: they are the ones that go from the source nodes 
  % of the cut (those in set "cut") to the others, so they are the columns 
  % of E for which there is a single +1 or -1 in the rows belonging to the 
  % source nodes. 
  if length(cut)>1 
    outArcs = find( sum(E(cut,:)) == 1  ); 
    inArcs  = find( sum(E(cut,:)) == -1 ); 
  else 
    outArcs = find( E(cut,:) ==  1 ); 
    inArcs  = find( E(cut,:) == -1 ); 
  end 
  cutArcs = [outArcs, -inArcs]; 
 
  if ~silent 
    set(arcHandles([outArcs inArcs]),'linewidth',4);  
    title 'Arcs emphasized cross the cut' 
  end 
   
end