social.all.paths {social}

All paths between two nodes

Description

Estimate all the possible paths between two nodes in a simple graph using the stochastic method described by Roberts & Kroese (2007).

Usage

social.all.paths(A, start.node, end.node, max.depth = nrow(A), 
  n.pilot = 5000, n.estimate = 10000)

Arguments

A

a (possibly weighted) adjacency matrix.

start.node

the index of the vertex from which the paths will be calculated.

end.node

the index of the vertex to which the paths will be calculated.

max.depth

the maximum length of the paths to the returned.

n.pilot

the number of naive paths to generate (see Roberts & Kroese, 2007).

n.estimate

the number of paths to generate (see Roberts & Kroese, 2007).

Value

An estimate of all the unique paths between start.node and end.node as an nrow(A)xN matrix, padded with zeros.

References

Roberts, B. & Kroese, D.P. (2007) Estimating the number of s-t paths in a graph. Journal of Graph Algorithms and Applications 11(1), 195-214.

Examples

# Using the data from Figure 1 in Roberts & Kroese (2007)
A = matrix(c(0,1,0,1,0,
             1,0,0,1,1,
             0,0,0,1,1,
             1,1,1,0,0,
             0,1,1,0,0), nrow=5)
paths = social.all.paths(A, 1, 5)