Home > matgraph > @graph > has_path.m

has_path

PURPOSE ^

has_path(g,u,v) --- determine if there is a path from u to v in g

SYNOPSIS ^

function yn = has_path(g,u,v)

DESCRIPTION ^

 has_path(g,u,v) --- determine if there is a path from u to v in g
 this is implemented a bit differently from find_path

CROSS-REFERENCE INFORMATION ^

This function calls: This function is called by:

SOURCE CODE ^

0001 function yn = has_path(g,u,v)
0002 % has_path(g,u,v) --- determine if there is a path from u to v in g
0003 % this is implemented a bit differently from find_path
0004 
0005 global GRAPH_MAGIC
0006 
0007 n = nv(g);
0008 
0009 if (u<1) | (u>n) | (v<1) | (v>n)
0010     yn = 0;
0011     return
0012 end
0013 
0014 if u==v
0015     yn = 1;
0016     return
0017 end
0018 
0019 x = zeros(n,1);
0020 x(u) = 1;
0021 
0022 last_sum = 0;
0023 
0024 while last_sum < sum(x)
0025     last_sum = sum(x);
0026     x = GRAPH_MAGIC.graphs{g.idx}.array * x + x;
0027     x = double(x>0);
0028     if (x(v))
0029         yn = 1;
0030         return
0031     end
0032 end
0033 
0034 yn = 0;

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003