PathDistribution.jl

This package estimates the number of paths and the path-length distribution using a Monte-Carlo simulation as well as explicitly enumerate all paths.
Author chkwon
Popularity
5 Stars
Updated Last
1 Year Ago
Started In
October 2015

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

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:

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, 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]

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
``````