next | previous | forward | backward | up | top | index | toc | Macaulay2 website
Graphs :: findPaths

findPaths -- finds all the paths in a digraph of a given length starting at a given vertex

Synopsis

Description

The method will return a list of all the paths of length l starting at a vertex v in the digraph D. The method is compatible for graphs with loops or cycles, as variables can be repeatedly visited in paths.

i1 : D = digraph(toList(1..5), {{1,2},{1,3},{2,5},{2,4}})

o1 = Digraph{1 => {2, 3}}
             2 => {4, 5}
             3 => {}
             4 => {}
             5 => {}

o1 : Digraph
i2 : F = findPaths(D,1,2)

o2 = {{1, 2, 4}, {1, 2, 5}}

o2 : List
i3 : D = digraph(toList(a..d), {{a,c},{a,b},{b,b},{b,d}})

o3 = Digraph{a => {b, c}}
             b => {b, d}
             c => {}
             d => {}

o3 : Digraph
i4 : F = findPaths(D,a,100)

o4 = {{a, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,
     ------------------------------------------------------------------------
     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,
     ------------------------------------------------------------------------
     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,
     ------------------------------------------------------------------------
     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,
     ------------------------------------------------------------------------
     b, b, b, b, b, d}, {a, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,
     ------------------------------------------------------------------------
     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,
     ------------------------------------------------------------------------
     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,
     ------------------------------------------------------------------------
     b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b, b,
     ------------------------------------------------------------------------
     b, b, b, b, b, b, b, b, b, b, b, b}}

o4 : List

See also

Ways to use findPaths :

For the programmer

The object findPaths is a method function.