Description of has_path

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:

• nv nv(g) --- number of vertices in g

This function is called by:

• euler_trail euler_trail(g) --- find an euler trail in g (if one exists)

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