PathDistribution.jl

This Julia package implements the Monte Carlo path generation method to estimate the number of simple paths between a pair of nodes in a graph, proposed by Roberts and Kroese (2007).

• 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.

Extending the same idea, this package also estimate the path-length distribution. That is, we can estimate the number of paths whose length is no greater than a certain number. This idea was used in the following paper:

• Sun, L., Karwan, M.H. and Kwon, C., 2018. Generalized bounded rationality and robust multicommodity network design. Operations Research, 66(1), pp.42-57.

This package can also be used to fully enumerate all paths.

Installation

Pkg.add("PathDistribution")

Basic Usage with an Adjacency Matrix

First import the package:

using PathDistribution

Suppose we have an adjacency matrix of the form:

adj_mtx = [ 0 1 1 1 0 1 1 1 ;
            1 0 0 0 1 1 1 0 ;
            1 0 0 1 1 1 1 1 ;
            1 0 1 0 1 1 1 1 ;
            0 1 1 1 0 1 0 0 ;
            1 1 1 1 1 0 1 1 ;
            1 1 1 1 0 1 0 1 ;
            1 0 1 1 0 1 1 0 ]

and the origin node is 1 the destination node is 8.

Monte-Carlo Simulation

To estimate the total number of paths from the origin to the destination, we can do the following:

# N1: number of samples in the first stage (default=5000)
# N2: number of samples in the second stage (default=10000)
no_path_est = monte_carlo_path_number(1, 8, adj_mtx)
no_path_est = monte_carlo_path_number(1, 8, adj_mtx, N1, N2)

To estimate the path-length distribution:

samples = monte_carlo_path_sampling(1, size(adj_mtx,1), adj_mtx)
x_data_est, y_data_est = estimate_cumulative_count(samples)

where x_data_est and y_data_est are for estimating the cumulative count of paths by path length. That is, y_data_est[i] is an estimate for the number of simple paths whose length is no greater than x_data_est[i] between the origin and destination nodes. Note that y_data_est[end] is the estimated number of total paths.

Full Enumeration

This package can also enumerate all paths explicitly. (CAUTION: It may take "forever" to enumerate all paths for a large network.)

path_enums = path_enumeration(1, size(adj_mtx,1), adj_mtx)
x_data, y_data = actual_cumulative_count(path_enums)

You can access each enumerated path as follows:

for enum in path_enums
    println("Length = $(enum.length) : $(enum.path)")
end
println("The total number of paths is $(length(path_enums))")

Results

One obtains results similar to the following:

The total number of paths:
- Full enumeration      : 397
- Monte Carlo estimation: 395.6732706634341

Another Form

When you have the following form data:

data = [
 1   4  79.0 ;
 1   2  59.0 ;
 2   4  31.0 ;
 2   3  90.0 ;
 2   5   9.0 ;
 2   6  32.0 ;
 3   9  89.0 ;
 3   8  66.0 ;
 3   6  68.0 ;
 3   7  47.0 ;
 4   3  14.0 ;
 4   9  95.0 ;
 4   8  88.0 ;
 5   3  44.0 ;
 5   6  83.0 ;
 6   7  33.0 ;
 6   8  37.0 ;
 7  11  79.0 ;
 7  12  10.0 ;
 8   7  95.0 ;
 8  10   0.0 ;
 8  12  30.0 ;
 9  10   5.0 ;
 9  11  44.0 ;
10  13  79.0 ;
10  14  91.0 ;
11  14  53.0 ;
11  15  80.0 ;
11  13  56.0 ;
12  15  75.0 ;
12  14   1.0 ;
13  14  48.0 ;
14  15  25.0 ;
]

st = round(Int, data[:,1]) #first column of data
en = round(Int, data[:,2]) #second column of data
len = data[:,3] #third

# Double them for two-ways.
start_node = [st; en]
end_node = [en; st]
link_length = [len; len]

origin = 1
destination = 15

Monte-Carlo Simulation

The similar tasks as above can be done as follows:

# Full Enumeration
path_enums = path_enumeration(origin, destination, start_node, end_node, link_length)
x_data, y_data = actual_cumulative_count(path_enums)

# Monte-Carlo estimation
N1 = 5000
N2 = 10000
samples = monte_carlo_path_sampling(origin, destination, start_node, end_node, link_length)
samples = monte_carlo_path_sampling(origin, destination, start_node, end_node, link_length, N1, N2)
x_data_est, y_data_est = estimate_cumulative_count(samples)

println("===== Another Example =====")
println("The total number of paths:")
println("- Full enumeration      : $(length(path_enums))")
println("- Monte Carlo estimation: $(y_data_est[end])")

Results

Results would look like:

===== Another Example =====
The total number of paths:
- Full enumeration      : 9851
- Monte Carlo estimation: 9742.908561771697