en‎ > ‎home‎ > ‎apps‎ > ‎Ekillion‎ > ‎

Ekillion Experimental Results

The summary of experimental results of Ekillion will be illustrated as follows.

Table 1 displays all JR train paths for four key regions of metropolis suburbs in Japan represented in a graph data structure, and the corresponding graph structure information on number of nodes (number of stations), edges (number of station spacing) and total distance. 
In this report, the results of the graph are shown in two formats, namely "All Stations in the Rail Network" which refers to the actual train route map in graph structure, and "Transfer Stations Network" which excludes 2nd degree node (intermediate stations that do not have connections between trains).
Table 2 shows the degree distribution of nodes (station). 1st degree refers to the last station (It does not necessarily correspond to the so-called terminal station, but instead refers to the termination of segment between metropolis suburbs.)

Table 1 Railroad network data
Region Railroad Network
(all stations)
Railroad Network
(interchange stations only)
Nodes Edges Total Distance Nodes Edges Total Distance
Osaka 355 364 941.0 km 26 34 924.3 km
Tokyo 623 653 2,055.6 km 72 101 2,037.9 km
Fukuoka 128 131 323.0 km 19 22 323.0 km
Niigata 58 59 174.2 km 7 7 159.0 km

Table 2 Degree distribution of nodes (stations)
Region number of n-th degree stations 1st Degree Stations Max Degree Stations
1 2 3 4 5
Osaka 7 329 13 6 0 JR-Namba, Wadamisaki, Sonobe, Sakurajima, Higashi-Hagoromo, Kansai-Kuko(Kansai Airport), Banshu-Ako Kyoto, Osaka, Amagasaki, Kizu, Tennoji, Kyobashi (4th degree)
Tokyo 18 551 34 16 4 Iwaki, Kuroiso, Umi-Shibaura, Okawa, Ogimachi, Kurihama, Nirasaki, Choshi, Narita-Kuko(Narita Airport) and others Nishi-funabashi, Haijima, Akabane, Omiya (5th degree)
Fukuoka 8 109 8 3 0 Hakata-minami, Mojiko, Tosu, Yukuhashi, Wakamatsu, Imayama, Saitozaki, Umi Orio, Kashii, Chojabaru (4th degree)
Niigata 3 51 3 1 0 Gosen, Nagaoka, Yahiko Niitsu (4th degree)

Maximum possible routes between two stations (search for adjacent stations)

Taking into consideration roundtrip routes from one station to another, let's explore the maximum possible routes between two stations.
Table 3 shows the result of "Transfer Stations Network", and Table 4 shows "All Stations in Railroad network".
The intermediate stations are excluded from the "Transfer Stations Network". For instance, Osaka Station and Kyoto Station are treated as neighbor stations.

Table 3 Search for maximum number of routes between two stations (adjacent station + "Transfer stations route network")
Name of s-t stations Number of Routes Longest Distance (km) Stations Search for number of s-t stations Processing Time (sec) Time/pair
Osaka Kyoto - Osaka 103 514.8 16 34 1.49 0.043
Tokyo Abiko - Narita 9,427,117 976.4 52 101 15.07 0.149
Fukuoka Keisen - Shin-Iizuka 9 157.5 11 22 0.94 0.043
Niigata Higashi-Sanjo - Yoshida 3 108.5 5 7 0.37 0.053

Table 4 Search for maximum number of routes between two stations (adjacent station + "All stations in Rail Network")
Name of s-t stations Number of Routes Longest Distance (km) Stations Search for number of s-t stations Processing Time (sec) Time/pair
Osaka Higashi-Yodogawa - Shin-Osaka 103 556.9 208 364 23.55 0.065
Tokyo Fusa - Kinoshita 9,427,117 1,007.4 331 653 2715 4.16
Fukuoka Fukkodai-mae - Kyusandai-mae 9 163.4 66 131 6.45 0.049
Niigata Tagami - Yashiroda 3 121.0 41 59 2.57 0.043
* If the number of routes is equal, the route with maximum distance between the two stations is displayed.
* Execution environment: amazon AWS m3.2xlarge (8 cores, 26 ECUs, 30 GB memory)

Maximum number of possible routes between two stations (search for all possible combinations of starting and ending stations)

Taking into consideration roundtrip routes from one station to another station, let's explore the maximum number of possible routes between two stations.
In the previous session, "Search for Adjacent Stations" is restricted to adjacent stations. However this section search for all possible combinations of starting and ending stations, and explores all possible routes between stations in the metroplis suburbs without the previous restriction.
Table 5 shows the result of "Transfer stations network", and Table 6 shows the results of "All Stations in the Railroad Network".

Table 5 Search for maxium possible number of routes between two stations (Transfer Stations Network)
Name of s-t stations Number of Routes Longest Distance (km) Stations Search for number of s-t stations Processing Time (sec) Time/pair
Osaka Banshu-Ako - Ohmi-Shiotsu 392 653.4 20 325 5.73 0.018
Tokyo Isogo - Kazusa-Kameyama 26,440,720 1,121.1 52 2,556 143.8 0.0056
Fukuoka Imayama - Hakata-Minami 14 200.0 11 171 2.82 0.016
Niigata Higashi-Sanjo - Shibata 4 87.7 5 21 0.32 0.015

Table 6 Search for maximum possible number of routes between two stations (All Stations in the Rail Network)
Name of s-t stations Number of Routes Longest Distance (km) Stations Search for number of s-t stations Processing Time Time/pair
Osaka Ritto - Tsukaguchi 392 743.1 283 62,790 29.6 min 0.028
Tokyo Hongodai - Higashi-Jujo 28,328,716 1,078.0 360 339,076 - -
Fukuoka Harumachi - Higashi-Mizumaki 16 200.3 81 8,125 2.5 min 0.019
Niigata Echigo-Ishiyama - Nagaoka 4 134.1 46 1,653 0.5 min 0.018
* If the number of routes is equal, the route with maximum distance between the two stations is displayed.
* Execution environment: amazon AWS m3.2xlarge (8 cores, 26 ECUs, 30 GB memory)
* The processing time results are not available for Tokyo in Table 6 as the experiments are executed in a different environment.

Longest possible route between two stations

Taking into consideration roundtrip routes from one station to another station, let's explore the longest possible route between two stations.
Table 7 shows the results restricted to adjacent stations. Table 8 shows the results of including all stations in the search.

Table 7 Search for longest routes between two stations (adjacent station search)
Name of s-t Stations Routes Longest Distance (km) Stations
Osaka JR-Kawachi-Eiwa - JR-Shuntokumichi 71 557.0 208
Tokyo Nishi-Nippori - Nippori 4,789,007 1,016.8 340
Fukuoka Hakata - Yoshizuka 7 163.4 66
Niigata Tagami - Yashiroda 3 121.0 41

Table 8 Search for longest routes between two stations (all stations search)
Name of s-t Stations Routes Longest Distance (km) Stations
Osaka JR-Namba - Tsukaguchi 210 743.5 286
Tokyo Iwaki - Nirasaki 6,632,867 1,201.3 379
Fukuoka Imayama - Mizumaki 10 210.2 85
Niigata Kita-Sanjo - Nagaoka 3 142.2 48


Program codes used for experiments

Refer to the attached program codes of Ekillion (Python) and its search for combination of stations (Ruby) on the sample usage of Graphillion.
Please note that data files needed to run the above experiments are not distributed to the public.

ċ
allPairs.rb
(5k)
nysol info,
2013/12/12 7:07
ċ
ekillion.py
(10k)
nysol info,
2013/12/12 7:07
Comments