Ticket-to-ride board game is one of the good strategic games out there and it requires that players need a lot of planning and strategy building in the process. With simple application of network analysis and graph theory concepts, it is possible that we can play this game even more efficiently. In this article, I will share some of the my results from the computational analysis on Ticket-to-ride board game. Also I will discuss on how to build best strategies for this game.
Before we proceed, let me clarify that this article is not to introduce the game or its rules to you, it is expected that the audience of this article are familiar with the game. Anyways, for those of you who are unfamiliar about the game and its rules, visit this page Ticket to Ride Wiki
Building the structure
We will be using the popular python package networkx to build the graph structures. To fit in the current
context, cities are represented as nodes and segments between cities can be represented as edges.
Then we construct the network using the below code.
# construct graph
import os
import re
import networkx as nx
import pandas as pd
import json
import math
# function to calculate points from segment length
def points(distance):
x = [0, 1, 2, 4, 7, 0, 15, 0, 21]
return x[distance]
pattern = re.compile('\\w+')
# we need a multigraph as we know from the game that there are multiple edges between certain cities
Gm = nx.MultiGraph()
Gm.clear()
with open(routes_path) as f:
for line in f:
city1, city2, distance, route_type, color, is_multi = pattern.findall(line)
distance = int(distance)
if(Gm.has_edge(city1,city2)==False):
Gm.add_edge(city1, city2, key=0, distance=distance, route_type=route_type, color=color, points=points(distance),
weight=distance, importance=0)
It can be observed from the Chart-1 (below) that the cities with maximum degree are Paris, Frankfurt and Kyiv as indicated by
their corresponding node sizes.
Basic Stats
From the degree distribution as shown in Chart-2a (below), it can be observed that degree of all cities ranges between 1-7. A big chunk nearly 31.9%
of cities have a degree 4 while about 29% of cities have a degree 3. There is only one city with maximum degree of 7 while there are two cities
with degree 6. Also we can observe from Chart-2b (below) that 36% of edges have a weight 2, 28% of edges have a weight of 4 and 27% of edges have weight 3.
There is only 1 edge with weight 8 which runs between Petrograd-Stockholm. Just by claiming this route you can buckle up 21 points.
As expected, the level of difficulty of this game increases as the number of players increase.
This is evident from the below ratios. For e.g, in a 3-player game only 10% of cities
have a degree less than 3 which means blocking other players is difficult so that would be an easy game for each player involved. However blocking probabilities
are more in 4-player and 5-player games. In a 5-player game, huge number of cities nearly 72% have a degree less than 5 which means there is more
room for blocking strategies by other players hence the game becomes more difficult.
# fraction of nodes with degree < 3
len(degree_df[degree_df.degree<3])/len(degree_df)*100
10.638297872340425
# fraction of nodes with degree < 4
len(degree_df[degree_df.degree<4])/len(degree_df)*100
40.42553191489361
# fraction of nodes with degree < 5
len(degree_df[degree_df.degree<5])/len(degree_df)*100
72.3404255319149
Chart-3 (below) shows the destination card points distribution.
It can be observed that there are very few long routes about 3 cards with 20 points and
another 3 cards with 21 points. A vast number of cards are short routes with a big chunk
about 13 cards fetch 8 points each.
Let us now define some common properties of network:
- radius is the minimum number of edges needed to connect the most central node (city) to all others.
- diameter is the minimum number of edges that will connect the two nodes that are far apart.
- eccentricity is the maximum distance from a given node to all other nodes. Lower value of eccentricity means that the node is relatively closer to the center of network while the higher value of eccentricity means that the node is relatively far from the center of the network.
- center of the network is the set of nodes whose eccentricity equals the radius of the network. There are 3 cities (listed below) at the center of the network. From all of these cities it is relatively easy to reach any part of the network.
- periphery of the network is the set of nodes whose eccentricity equals the diameter of the network. There are 7 cities (listed below) at the periphery of the network. From each of these cities, it is relatively difficult to reach to the further part of the network.
All of the above properties can be deduced from the network as shown below,
nx.radius(G)
5
nx.diameter(G)
9
# ecc is the dictionary of nodes and their respective eccentricities.
ecc = nx.eccentricity(G)
nx.center(G)
['Berlin', 'Venezia', 'Munchen']
nx.periphery(G)
['Lisboa', 'Cadiz', 'Edinburgh', 'Erzurum', 'Sochi', 'Rostov', 'Moskva']
For your reference, all cities with maximum and minimum eccentricities are listed in Table-1
Based on the above properties, we can make the following inferences:
- Its a good strategy to start your game by claiming routes around the cities at the center such as
Berlin,Venezia,Munchenbecause its relatively easy to reach whatever direction you wish to continue as the game unfolds. - It is a good strategy to choose destination cards including any periphery cities such as
Lisboa,Cadiz,Edinburgh,Erzurum,Sochi,Rostov,Moskva. Having one or more of these in your control increases your chances of building the longest route. Your best bet would be to have two such cities but at the opposite ends of the network. - Listed below are all those routes from periphery cities with length equal to diameter. Considering these in your plan would be a smart strategy especially if you are on building the longest route.
Lisboa-Madrid-Barcelona-Marseille-Roma-Palermo-Smyrna-Angora-Erzurum-Sochi
Lisboa-Madrid-Barcelona-Marseille-Roma-Palermo-Smyrna-Constantinople-Sevastopol-Rostov
Lisboa-Madrid-Pamplona-Paris-Frankfurt-Essen-Kobenhavn-Stockholm-Petrograd-Moskva
Cadiz-Madrid-Barcelona-Marseille-Roma-Palermo-Smyrna-Angora-Erzurum-Sochi
Cadiz-Madrid-Barcelona-Marseille-Roma-Palermo-Smyrna-Constantinople-Sevastopol-Rostov
Cadiz-Madrid-Pamplona-Paris-Frankfurt-Essen-Kobenhavn-Stockholm-Petrograd-Moskva
Edinburgh-London-Dieppe-Paris-Marseille-Roma-Palermo-Smyrna-Angora-Erzurum
Edinburgh-London-Amsterdam-Essen-Berlin-Warszawa-Kyiv-Bucuresti-Sevastopol-Sochi
Importance of some cities
Certainly some cities are more important than others. This can be measured with variety of centrality measures, clustering coefficient, connectivity and efficiency.
These properties are defined below:
- Degree centrality for a node is the fraction of nodes connected to it.
- Betweenness centrality of a node is the sum of the fraction of all-pairs shortest paths that pass through it.
- Closeness centrality of a node is the reciprocal of the sum of the shortest path distances from the current node to all other nodes.
- Clustering coefficient of a node is the ratio of number of connections in the neighborhood of a node and the number of connections if the neighborhood was fully connected. This ratio tells how well connected the neighborhood of the node is. If the neighborhood is fully connected, the clustering coefficient is 1 and a value close to 0 means that there are hardly any connections in the neighborhood.
- connectivity of a node is the minimum number of nodes required to be removed to block out all the paths to the subject node. The higher value is better.
All the above properties can be deduced from the network as below:
# values returned are dictionary of nodes with their respective values for the speicifed property
dc = nx.degree_centrality(G)
cc = nx.closeness_centrality(G, distance='weight')
bc = nx.betweenness_centrality(G, weight='weight')
ccoef = nx.clustering(G)
The table below (Table-1) lists all of the above discussed properties for every node (city).
Table-1: All Cities (Nodes) - Degree, Centrality Measures and Clustering
NOTE: dc, bc, cc are degree centrality, betweenness centrality and closeness centrality
respectively
| city | degree | eccentricity | dc | bc | cc | clustering coeff. |
|---|---|---|---|---|---|---|
| Paris | 7 | 7 | 0.152174 | 0.137203 | 0.100656 | 0.285714 |
| Kyiv | 6 | 7 | 0.130435 | 0.127660 | 0.093496 | 0.200000 |
| Frankfurt | 6 | 6 | 0.130435 | 0.206094 | 0.113022 | 0.266667 |
| Pamplona | 5 | 7 | 0.108696 | 0.060386 | 0.081129 | 0.400000 |
| Marseille | 5 | 7 | 0.108696 | 0.118542 | 0.097665 | 0.300000 |
| Sevastopol | 5 | 8 | 0.108696 | 0.055753 | 0.078498 | 0.300000 |
| Constantinople | 5 | 8 | 0.108696 | 0.073816 | 0.087287 | 0.300000 |
| Bucuresti | 5 | 8 | 0.108696 | 0.154723 | 0.101545 | 0.300000 |
| Wilno | 5 | 7 | 0.108696 | 0.073269 | 0.091089 | 0.300000 |
| Warszawa | 5 | 6 | 0.108696 | 0.134599 | 0.101099 | 0.300000 |
| Budapest | 5 | 7 | 0.108696 | 0.176931 | 0.117048 | 0.300000 |
| Berlin | 5 | 5 | 0.108696 | 0.156821 | 0.111922 | 0.300000 |
| Wien | 5 | 6 | 0.108696 | 0.185461 | 0.120104 | 0.200000 |
| Madrid | 4 | 8 | 0.086957 | 0.085024 | 0.069277 | 0.333333 |
| Dieppe | 4 | 8 | 0.086957 | 0.047893 | 0.093117 | 0.333333 |
| Bruxelles | 4 | 7 | 0.086957 | 0.024771 | 0.100218 | 0.500000 |
| Amsterdam | 4 | 7 | 0.086957 | 0.060789 | 0.099138 | 0.333333 |
| Smyrna | 4 | 7 | 0.086957 | 0.041932 | 0.082585 | 0.166667 |
| Petrograd | 4 | 8 | 0.086957 | 0.010628 | 0.070552 | 0.166667 |
| Athina | 4 | 7 | 0.086957 | 0.057874 | 0.089669 | 0.166667 |
| Sofia | 4 | 8 | 0.086957 | 0.046377 | 0.098081 | 0.333333 |
| Essen | 4 | 6 | 0.086957 | 0.089372 | 0.106977 | 0.333333 |
| Zagrab | 4 | 6 | 0.086957 | 0.118201 | 0.116751 | 0.333333 |
| Sarajevo | 4 | 7 | 0.086957 | 0.057488 | 0.103139 | 0.333333 |
| Roma | 4 | 6 | 0.086957 | 0.101932 | 0.101996 | 0.166667 |
| Venezia | 4 | 5 | 0.086957 | 0.175206 | 0.115869 | 0.166667 |
| Munchen | 4 | 5 | 0.086957 | 0.162112 | 0.117347 | 0.166667 |
| Zurich | 4 | 6 | 0.086957 | 0.154051 | 0.109524 | 0.333333 |
| Barcelona | 3 | 8 | 0.065217 | 0.074879 | 0.077052 | 0.666667 |
| Brest | 3 | 8 | 0.065217 | 0.000000 | 0.080844 | 0.666667 |
| London | 3 | 8 | 0.065217 | 0.043478 | 0.087121 | 0.000000 |
| Erzurum | 3 | 9 | 0.065217 | 0.003382 | 0.066570 | 0.333333 |
| Angora | 3 | 8 | 0.065217 | 0.025121 | 0.077181 | 0.333333 |
| Sochi | 3 | 9 | 0.065217 | 0.024334 | 0.071875 | 0.666667 |
| Rostov | 3 | 9 | 0.065217 | 0.026248 | 0.068047 | 0.333333 |
| Kharkov | 3 | 8 | 0.065217 | 0.042958 | 0.073482 | 0.000000 |
| Moskva | 3 | 9 | 0.065217 | 0.014171 | 0.070444 | 0.000000 |
| Smolensk | 3 | 8 | 0.065217 | 0.034300 | 0.077572 | 0.333333 |
| Riga | 3 | 7 | 0.065217 | 0.007246 | 0.078767 | 0.333333 |
| Palermo | 3 | 7 | 0.065217 | 0.000000 | 0.080420 | 0.333333 |
| Danzig | 3 | 6 | 0.065217 | 0.033333 | 0.090909 | 0.333333 |
| Brindisi | 3 | 7 | 0.065217 | 0.056425 | 0.093117 | 0.333333 |
| Lisboa | 2 | 9 | 0.043478 | 0.000000 | 0.057862 | 1.000000 |
| Cadiz | 2 | 9 | 0.043478 | 0.000000 | 0.057862 | 1.000000 |
| Stockholm | 2 | 7 | 0.043478 | 0.001932 | 0.070552 | 0.000000 |
| Kobenhavn | 2 | 7 | 0.043478 | 0.033816 | 0.083333 | 0.000000 |
| Edinburgh | 1 | 9 | 0.021739 | 0.000000 | 0.064972 | 0.000000 |
Below are few observations we can make from the above table:
- Based on degree centrality, cities
Paris, Kyiv, Frankfurthave higher values where as citiesEdiburgh, Cadiz, Lisboa, Kobenhavnhave lower value. Lower value of this measure means that you need to be more cautious around those cities because there is a high probability that you may be blocked from those cities. - Based on betweenness centrality, cities
Frankfurt, Wien, Budapesthave higher values where as cities such asBrest, Palermo, Cadizhave lowest values. The higher value of this measure means that there are more shortest paths passing through those cities hence there will be more competition for routes passing through those cities. More competition again leads to blockage so you need to watch out these cities if you have any of them in your plan. - Based on closeness centrality, cities
Wien, Munchen, Budapesthave higher values so it is relatively easy from these to reach far ends of the network quite easily. where as citiesCadiz, Lisboa, Edinburghhave lower value so it is relatively difficult to reach the far ends from these cities. - Based on clustering coefficient values, it is evident that the neighborhoods of cities such as
Lisboa, Cadiz, Sochi, Barcelona, Brestare quite strong so even if your opponent tries to block you in one route, you will certainly be able to find your way out and move on. However you need to be more cautious for cities such asEdinburgh, Moskva, Stockholm, Kharkov, Kobenhavn. Londonbecause their neighborhood is not strong and you may be blocked out.
Apart from centrality measures and clustering, we can measure each city’s importance by certain attacking strategies.
Importance of anything is better known only when its gone. So, we can iteratively remove one city at a time from the network and measure the
change in certain properties such as connectivity, efficiency etc. Removing a city in this context means that your opponents have claimed all routes
around that city and you are blocked out with respect to that city. Table-2 (below) shows the details about the impact caused.
Table-2: Impact of each city
NOTE: All values shown below are the values observed in the network
when the mentioned city is removed from the network.
| city removed | network is still connected? | num of unreachable nodes | avg shortest path change % | avg connectivity change % | clustering coeff change % | efficiency change % |
|---|---|---|---|---|---|---|
| Lisboa | 1 | 0 | -2.16 | 2.81 | -11.84 | 1.43 |
| Cadiz | 1 | 0 | -2.16 | 2.81 | -11.84 | 1.43 |
| Madrid | 0 | 2 | -6.15 | -1.60 | -11.14 | -4.30 |
| Barcelona | 1 | 0 | 0.06 | 0.00 | -2.73 | 0.41 |
| Pamplona | 1 | 0 | 0.88 | -7.08 | -4.03 | -1.03 |
| Marseille | 1 | 0 | 2.77 | -10.35 | 2.97 | -2.20 |
| Paris | 1 | 0 | 2.14 | -6.97 | -9.17 | -3.16 |
| Brest | 1 | 0 | -0.28 | -4.24 | -1.93 | 0.24 |
| Dieppe | 1 | 0 | 0.69 | -6.97 | 3.21 | -0.32 |
| London | 0 | 1 | -1.51 | -1.70 | 6.84 | -2.10 |
| Bruxelles | 1 | 0 | 0.75 | -2.23 | -1.93 | -0.18 |
| Amsterdam | 1 | 0 | 1.40 | -5.81 | 0.54 | -0.58 |
| Edinburgh | 1 | 0 | -1.44 | 2.91 | 2.17 | 1.51 |
| Erzurum | 1 | 0 | -1.25 | -5.00 | 7.08 | 0.64 |
| Angora | 1 | 0 | -0.13 | -5.00 | 3.57 | 0.27 |
| Sevastopol | 1 | 0 | 0.45 | -4.50 | -8.80 | -0.80 |
| Sochi | 1 | 0 | -0.67 | -2.27 | -8.10 | 0.76 |
| Smyrna | 1 | 0 | 0.46 | -7.41 | 4.74 | -1.02 |
| Constantinople | 1 | 0 | 1.13 | -4.44 | -4.13 | -1.00 |
| Rostov | 1 | 0 | -0.53 | -7.41 | 2.41 | 0.24 |
| Bucuresti | 1 | 0 | 3.50 | -4.57 | -0.39 | -2.36 |
| Kharkov | 1 | 0 | 0.26 | -8.51 | 7.54 | -0.40 |
| Moskva | 1 | 0 | -0.81 | -3.67 | 8.01 | 0.40 |
| Kyiv | 1 | 0 | 3.22 | -3.97 | -1.80 | -3.59 |
| Smolensk | 1 | 0 | 0.35 | -1.40 | 0.07 | 0.23 |
| Petrograd | 1 | 0 | -0.69 | -7.18 | -1.10 | -0.71 |
| Wilno | 1 | 0 | 1.16 | -4.30 | -6.23 | -1.16 |
| Warszawa | 1 | 0 | 2.45 | -2.60 | -3.20 | -1.88 |
| Budapest | 1 | 0 | 3.27 | -2.83 | -2.26 | -1.65 |
| Riga | 1 | 0 | -0.39 | -2.43 | 3.57 | 0.20 |
| Stockholm | 1 | 0 | -0.92 | -2.03 | 3.34 | 0.41 |
| Palermo | 1 | 0 | -0.31 | -2.67 | -2.50 | -0.44 |
| Athina | 1 | 0 | 0.88 | -6.04 | 6.84 | -0.45 |
| Sofia | 1 | 0 | 1.08 | -3.74 | -0.86 | -0.22 |
| Danzig | 1 | 0 | 0.95 | -2.43 | 4.98 | -0.19 |
| Kobenhavn | 1 | 0 | 2.72 | -2.03 | 4.51 | 0.07 |
| Essen | 1 | 0 | 8.24 | -8.11 | -0.39 | -1.78 |
| Berlin | 1 | 0 | 3.81 | -3.50 | -3.20 | -2.67 |
| Wien | 1 | 0 | 3.66 | -3.07 | 2.64 | -1.59 |
| Zagrab | 1 | 0 | 2.17 | -2.93 | -0.16 | -0.93 |
| Sarajevo | 1 | 0 | 1.37 | -5.07 | -1.10 | -0.51 |
| Brindisi | 1 | 0 | 1.00 | -2.67 | -2.50 | 0.01 |
| Roma | 1 | 0 | 5.02 | -9.85 | -1.10 | -2.84 |
| Venezia | 1 | 0 | 3.85 | -4.14 | 3.34 | -1.04 |
| Frankfurt | 1 | 0 | 3.10 | -6.04 | -3.80 | -2.88 |
| Munchen | 1 | 0 | 2.54 | -2.63 | 1.71 | -0.87 |
| Zurich | 1 | 0 | 2.72 | -5.47 | -1.93 | -0.66 |
Below are few observations we can make from the above table:
- It can be observed that the network pretty much stays connected when you remove any city except for
LondonandMadrid.When you removeLondon,Edinburghbecomes unreachable and when you removeMadrid, bothLisboaandCadizbecomes unreachable from else where. So, if you are interested in either of these cities, you better watch outLondonorMadrid. - Its interesting to know that removing
Essenraises the overall average cost to build a route by+8.24%. If you claimed all routes leading to this city, you would significantly affect all of your opponents as their cost to build increases and consequently their game will be slightly delayed. However its not good for you if the situation is other way around. - Another interesting observation is that absence of
Marsiellereduces the average connectivity by-10.35%which again is not good for your opponents as they become more vulnerable for blockage.
Importance of some edge segments
In the context of the game, its relatively hard that anyone gets blocked out for a city but its fairly easy to get blocked out on a route segment hence knowing the importance of certain edge segments is more useful in this game. The importance of each route segment can be gauged by edge betweenness centrality, and change in factors such as average connectivity, average clustering coefficient, efficiency.
The table below lists out top 10 and bottom 10 cities by their edge betweenness values,
Table-3: Top-10 Edge segments and Bottom-10 by edge betweenness
| segment | edge_betweenness |
|---|---|
| (Budapest, Wien) | 0.142879 |
| (Zagrab, Venezia) | 0.131673 |
| (Wien, Munchen) | 0.117440 |
| (Frankfurt, Munchen) | 0.112625 |
| (Bucuresti, Budapest) | 0.110365 |
| (Venezia, Zurich) | 0.105832 |
| (Marseille, Zurich) | 0.103321 |
| (Berlin, Frankfurt) | 0.098806 |
| (Barcelona, Marseille) | 0.097595 |
| (Roma, Venezia) | 0.090287 |
| segment | edge_betweenness |
|---|---|
| (Roma, Venezia) | 0.090287 |
| (Barcelona, Marseille) | 0.097595 |
| (Berlin, Frankfurt) | 0.098806 |
| (Marseille, Zurich) | 0.103321 |
| (Venezia, Zurich) | 0.105832 |
| (Bucuresti, Budapest) | 0.110365 |
| (Frankfurt, Munchen) | 0.112625 |
| (Wien, Munchen) | 0.117440 |
| (Zagrab, Venezia) | 0.131673 |
| (Budapest, Wien) | 0.142879 |
Below are few observations we can make from the above table:
- It can be observed that
Budapest-Wien, Zagrab-Vienna, Wien-Munchenhave the high betweenness centrality. So, certainly there is a big competition for these segments, so you need to catch up on them relatively sooner if at all they are in your plan. - However, for segments such as
Rome-Venezia, Barcelona-Marsielle, you need not stress much because their lower value of betweenness score indicates lesser competition.
From the table below we can understand the impact caused by removing a particular edge segment.
Table-4: Impact of each edge segment
NOTE: All values shown below are the values observed in the network
when the mentioned edge segment is removed from the network.
| edge removed | is network still connected ? | num of unreachable nodes | avg shortest path change % | avg connectivity change % | clustering coeff. change % | global efficiency change % |
|---|---|---|---|---|---|---|
| Lisboa-Cadiz | 1 | 0 | 0.03 | -0.10 | -14.85 | -0.14 |
| Lisboa-Madrid | 1 | 0 | 0.72 | -0.10 | -13.71 | -0.57 |
| Cadiz-Madrid | 1 | 0 | 0.72 | -0.10 | -13.71 | -0.57 |
| Madrid-Barcelona | 1 | 0 | 0.62 | -1.41 | 1.60 | -0.23 |
| Madrid-Pamplona | 1 | 0 | 0.36 | -1.41 | -1.60 | -0.89 |
| Barcelona-Pamplona | 1 | 0 | 0.20 | -0.03 | -6.86 | -0.18 |
| Barcelona-Marseille | 1 | 0 | 0.95 | -2.69 | 1.83 | -0.45 |
| Pamplona-Marseille | 1 | 0 | 0.22 | -0.03 | -3.98 | -0.30 |
| Pamplona-Paris | 1 | 0 | 0.99 | -1.21 | -3.56 | -0.86 |
| Pamplona-Brest | 1 | 0 | 0.12 | -5.43 | 2.64 | -0.27 |
| Marseille-Roma | 1 | 0 | 0.57 | -4.32 | 2.51 | -1.86 |
| Marseille-Zurich | 1 | 0 | 1.40 | -1.57 | -0.10 | -0.29 |
| Marseille-Paris | 1 | 0 | 0.06 | -0.80 | -2.87 | -0.81 |
| Paris-Brest | 1 | 0 | 0.00 | -1.21 | -6.53 | -0.48 |
| Paris-Dieppe | 1 | 0 | 0.45 | -0.80 | -5.84 | -0.59 |
| Paris-Bruxelles | 1 | 0 | 0.12 | -1.53 | -2.87 | -0.42 |
| Paris-Frankfurt | 1 | 0 | 0.44 | -0.03 | -0.59 | -1.29 |
| Paris-Zurich | 1 | 0 | 0.49 | -3.48 | -0.36 | -0.48 |
| Brest-Dieppe | 1 | 0 | 0.06 | -5.43 | 1.96 | -0.21 |
| Dieppe-London | 1 | 0 | 0.35 | -2.97 | 2.29 | -0.70 |
| Dieppe-Bruxelles | 1 | 0 | 0.03 | -1.57 | 0.82 | -0.14 |
| London-Amsterdam | 1 | 0 | 0.83 | -2.97 | 2.29 | -0.83 |
| London-Edinburgh | 0 | 1 | -1.44 | -1.47 | 0.00 | -2.81 |
| Bruxelles-Amsterdam | 1 | 0 | 0.16 | -1.57 | 0.69 | -0.14 |
| Bruxelles-Frankfurt | 1 | 0 | 0.24 | -1.53 | -3.07 | -0.40 |
| Amsterdam-Essen | 1 | 0 | 0.07 | -4.25 | -0.46 | -0.38 |
| Amsterdam-Frankfurt | 1 | 0 | 0.31 | -0.80 | -5.03 | -0.31 |
| Erzurum-Angora | 1 | 0 | 0.46 | -6.17 | 9.14 | -0.40 |
| Erzurum-Sevastopol | 1 | 0 | 0.01 | -1.21 | -4.34 | -0.35 |
| Erzurum-Sochi | 1 | 0 | 0.23 | -3.55 | -0.69 | -0.18 |
| Angora-Smyrna | 1 | 0 | 0.18 | -2.75 | -4.11 | -0.55 |
| Angora-Constantinople | 1 | 0 | 0.66 | -1.25 | -3.20 | -0.38 |
| Sevastopol-Sochi | 1 | 0 | 0.74 | -1.21 | -10.06 | -0.34 |
| Sevastopol-Constantinople | 1 | 0 | 0.21 | -0.83 | -0.23 | -0.40 |
| Sevastopol-Bucuresti | 1 | 0 | 1.10 | -1.05 | -0.23 | -0.84 |
| Sevastopol-Rostov | 1 | 0 | 0.00 | -1.21 | -4.34 | -0.40 |
| Sochi-Rostov | 1 | 0 | 0.44 | -3.55 | -0.69 | -0.23 |
| Smyrna-Constantinople | 1 | 0 | 0.40 | -0.83 | -3.20 | -0.70 |
| Smyrna-Palermo | 1 | 0 | 0.21 | -3.93 | 5.71 | -1.15 |
| Smyrna-Athina | 1 | 0 | 0.64 | -1.57 | 2.29 | -0.32 |
| Constantinople-Sofia | 1 | 0 | 0.24 | -2.17 | -0.46 | -0.23 |
| Constantinople-Bucuresti | 1 | 0 | 0.62 | -0.26 | -3.66 | -0.84 |
| Rostov-Kharkov | 1 | 0 | 1.33 | -8.47 | 4.57 | -0.81 |
| Bucuresti-Sofia | 1 | 0 | 0.53 | -1.05 | -0.46 | -0.41 |
| Bucuresti-Budapest | 1 | 0 | 1.37 | -0.45 | 0.00 | -0.67 |
| Bucuresti-Kyiv | 1 | 0 | 1.57 | -0.26 | -0.46 | -1.25 |
| Kharkov-Moskva | 1 | 0 | 0.33 | -2.97 | 0.00 | -0.48 |
| Kharkov-Kyiv | 1 | 0 | 1.33 | -1.21 | 0.69 | -1.03 |
| Moskva-Smolensk | 1 | 0 | 0.92 | -2.72 | 4.57 | -0.18 |
| Moskva-Petrograd | 1 | 0 | 0.24 | -2.01 | 1.14 | -0.55 |
| Kyiv-Smolensk | 1 | 0 | 0.39 | -1.21 | -2.97 | -0.44 |
| Kyiv-Wilno | 1 | 0 | 0.80 | -0.22 | -4.57 | -0.94 |
| Kyiv-Warszawa | 1 | 0 | 0.42 | -0.22 | -0.46 | -0.94 |
| Kyiv-Budapest | 1 | 0 | 0.33 | -0.22 | -0.46 | -0.72 |
| Smolensk-Wilno | 1 | 0 | 0.26 | -1.57 | -2.51 | -0.18 |
| Petrograd-Wilno | 1 | 0 | 0.45 | -1.02 | -3.20 | -0.62 |
| Petrograd-Riga | 1 | 0 | 0.08 | -2.17 | -4.11 | -0.34 |
| Petrograd-Stockholm | 1 | 0 | 0.39 | -4.73 | 1.14 | -1.15 |
| Wilno-Warszawa | 1 | 0 | 0.80 | -0.42 | 0.00 | -0.54 |
| Wilno-Riga | 1 | 0 | 0.30 | -1.44 | -3.20 | -0.38 |
| Warszawa-Danzig | 1 | 0 | 0.45 | -1.44 | -2.74 | -0.32 |
| Warszawa-Berlin | 1 | 0 | 1.07 | -0.42 | -4.80 | -1.10 |
| Warszawa-Wien | 1 | 0 | 0.58 | -0.51 | -0.69 | -0.41 |
| Budapest-Wien | 1 | 0 | 1.47 | -0.54 | -1.14 | -0.53 |
| Budapest-Zagrab | 1 | 0 | 0.21 | -1.02 | -5.03 | -0.57 |
| Budapest-Sarajevo | 1 | 0 | 0.20 | -1.02 | -0.91 | -0.37 |
| Riga-Danzig | 1 | 0 | 0.74 | -3.71 | 9.14 | -0.48 |
| Stockholm-Kobenhavn | 1 | 0 | 2.96 | -4.73 | 0.00 | -0.95 |
| Palermo-Brindisi | 1 | 0 | 0.04 | -2.40 | -5.71 | -0.14 |
| Palermo-Roma | 1 | 0 | 0.22 | -2.01 | -5.71 | -1.14 |
| Athina-Sofia | 1 | 0 | 0.22 | -1.57 | -2.29 | -0.32 |
| Athina-Sarajevo | 1 | 0 | 0.10 | -1.57 | -2.29 | -0.44 |
| Athina-Brindisi | 1 | 0 | 0.95 | -3.93 | 5.71 | -0.67 |
| Sofia-Sarajevo | 1 | 0 | 0.72 | -1.57 | -1.14 | -0.26 |
| Danzig-Berlin | 1 | 0 | 0.51 | -1.60 | -2.74 | -0.63 |
| Kobenhavn-Essen | 1 | 0 | 7.34 | -4.73 | 2.29 | -1.71 |
| Essen-Frankfurt | 1 | 0 | 0.69 | -0.80 | -4.57 | -0.76 |
| Essen-Berlin | 1 | 0 | 1.03 | -1.02 | -0.23 | -0.69 |
| Berlin-Frankfurt | 1 | 0 | 0.62 | -0.54 | -0.69 | -1.15 |
| Berlin-Wien | 1 | 0 | 0.94 | -0.42 | -0.69 | -0.44 |
| Wien-Munchen | 1 | 0 | 0.71 | -1.21 | 2.06 | -0.57 |
| Wien-Zagrab | 1 | 0 | 0.24 | -1.02 | -0.91 | -0.29 |
| Zagrab-Sarajevo | 1 | 0 | 0.57 | -1.76 | -0.69 | -0.39 |
| Zagrab-Venezia | 1 | 0 | 1.40 | -2.05 | 3.43 | -0.82 |
| Brindisi-Roma | 1 | 0 | 1.65 | -2.01 | -5.71 | -0.71 |
| Roma-Venezia | 1 | 0 | 2.01 | -1.57 | 2.29 | -0.68 |
| Venezia-Munchen | 1 | 0 | 0.51 | -1.57 | -3.43 | -0.36 |
| Venezia-Zurich | 1 | 0 | 0.93 | -1.79 | -2.29 | -0.39 |
| Frankfurt-Munchen | 1 | 0 | 1.34 | -1.02 | 2.06 | -0.53 |
| Munchen-Zurich | 1 | 0 | 0.38 | -1.57 | -2.29 | -0.33 |
Below are few observations we can make from the above table:
- You can observe that the network is only disconnected when you remove the edge
London-Edinburghand when that happens onlyEdinburghbecomes unreachable. However the network is not impacted by any other edges. - When
Kobenhavn-Essengoes out of picture, the average shortest path cost increases by7.34%. - It can be observed that average connectivity is considerably impacted by almost every edge removal with most impact caused by removing the edge
Rostov-Kharkovwhen average connectivity drops by8.47%. - The neighborhood also is deeply affected when you remove edges such as
Lisboa-Cadiz, Cadiz-Madrid, Lisboa-Madridwhich is evident from the huge drops in the network’s average clustering coefficient values. - Also, the efficiency drop of
2.81%is caused when you remove the edgeLondon-Edinburgh.
Destination Card Profitability Analysis
What if you know the art of picking the right cards ?. Of course, that is quite possible but only if you know the underlying numbers. Listed below are all destination card routes with their shortest path characteristics.
Table-5: All Destination Cards with their Shortest Paths
| source-destination | destination | card points | shortest path length | shortest path cost | shortest path total points | shortest path | shortest path profitability | connectivity |
|---|---|---|---|---|---|---|---|---|
| Palermo | Moskva | 20 | 7 | 20 | 54 | Palermo-Smyrna-Constantinople-Bucuresti-Kyiv-Smolensk-Moskva | 2.70 | 3 |
| Kobenhavn | Erzurum | 21 | 8 | 21 | 53 | Kobenhavn-Essen-Berlin-Wien-Budapest-Bucuresti-Sevastopol-Erzurum | 2.52 | 2 |
| Cadiz | Stockholm | 21 | 8 | 21 | 50 | Cadiz-Madrid-Pamplona-Paris-Frankfurt-Essen-Kobenhavn-Stockholm | 2.38 | 2 |
| Brest | Petrograd | 20 | 7 | 20 | 50 | Brest-Paris-Frankfurt-Berlin-Warszawa-Wilno-Petrograd | 2.50 | 3 |
| Lisboa | Danzig | 20 | 7 | 20 | 50 | Lisboa-Madrid-Pamplona-Paris-Frankfurt-Berlin-Danzig | 2.50 | 2 |
| Edinburgh | Athina | 21 | 9 | 20 | 48 | Edinburgh-London-Dieppe-Paris-Zurich-Venezia-Roma-Brindisi-Athina | 2.40 | 1 |
| Frankfurt | Smolensk | 13 | 5 | 13 | 32 | Frankfurt-Berlin-Warszawa-Wilno-Smolensk | 2.46 | 3 |
| Amsterdam | Wilno | 12 | 5 | 12 | 29 | Amsterdam-Frankfurt-Berlin-Warszawa-Wilno | 2.42 | 4 |
| Berlin | Moskva | 12 | 5 | 12 | 29 | Berlin-Warszawa-Wilno-Smolensk-Moskva | 2.42 | 3 |
| Essen | Kyiv | 10 | 4 | 10 | 26 | Essen-Berlin-Warszawa-Kyiv | 2.60 | 4 |
| Riga | Bucuresti | 10 | 4 | 10 | 26 | Riga-Wilno-Kyiv-Bucuresti | 2.60 | 3 |
| Athina | Wilno | 11 | 5 | 11 | 26 | Athina-Sofia-Bucuresti-Kyiv-Wilno | 2.36 | 4 |
| Stockholm | Wien | 11 | 5 | 11 | 25 | Stockholm-Kobenhavn-Essen-Berlin-Wien | 2.27 | 2 |
| Palermo | Constantinople | 8 | 3 | 8 | 25 | Palermo-Smyrna-Constantinople | 3.12 | 3 |
| Venezia | Constantinople | 10 | 5 | 10 | 22 | Venezia-Zagrab-Sarajevo-Sofia-Constantinople | 2.20 | 4 |
| Angora | Kharkov | 10 | 5 | 10 | 22 | Angora-Erzurum-Sochi-Rostov-Kharkov | 2.20 | 3 |
| Bruxelles | Danzig | 9 | 4 | 9 | 22 | Bruxelles-Frankfurt-Berlin-Danzig | 2.44 | 3 |
| London | Wien | 10 | 5 | 9 | 20 | London-Amsterdam-Frankfurt-Munchen-Wien | 2.22 | 2 |
| Madrid | Dieppe | 8 | 4 | 8 | 20 | Madrid-Pamplona-Paris-Dieppe | 2.50 | 2 |
| Berlin | Bucuresti | 8 | 4 | 8 | 20 | Berlin-Wien-Budapest-Bucuresti | 2.50 | 5 |
| Kyiv | Sochi | 8 | 4 | 8 | 19 | Kyiv-Kharkov-Rostov-Sochi | 2.38 | 3 |
| Berlin | Roma | 9 | 5 | 9 | 19 | Berlin-Frankfurt-Munchen-Venezia-Roma | 2.11 | 4 |
| Madrid | Zurich | 8 | 4 | 8 | 19 | Madrid-Barcelona-Marseille-Zurich | 2.38 | 2 |
| Smolensk | Rostov | 8 | 4 | 8 | 19 | Smolensk-Moskva-Kharkov-Rostov | 2.38 | 3 |
| Barcelona | Munchen | 8 | 4 | 8 | 19 | Barcelona-Marseille-Zurich-Munchen | 2.38 | 3 |
| Barcelona | Bruxelles | 8 | 4 | 8 | 19 | Barcelona-Pamplona-Paris-Bruxelles | 2.38 | 3 |
| Sarajevo | Sevastopol | 8 | 4 | 8 | 19 | Sarajevo-Sofia-Bucuresti-Sevastopol | 2.38 | 4 |
| Roma | Smyrna | 8 | 4 | 8 | 19 | Roma-Brindisi-Athina-Smyrna | 2.38 | 4 |
| Brest | Marseille | 7 | 3 | 7 | 18 | Brest-Paris-Marseille | 2.57 | 3 |
| Brest | Venezia | 8 | 4 | 8 | 18 | Brest-Paris-Zurich-Venezia | 2.25 | 3 |
| Paris | Wien | 8 | 4 | 8 | 18 | Paris-Frankfurt-Munchen-Wien | 2.25 | 5 |
| Edinburgh | Paris | 7 | 4 | 7 | 17 | Edinburgh-London-Dieppe-Paris | 2.43 | 1 |
| Amsterdam | Pamplona | 7 | 4 | 7 | 17 | Amsterdam-Bruxelles-Paris-Pamplona | 2.43 | 4 |
| Marseille | Essen | 8 | 5 | 8 | 16 | Marseille-Zurich-Munchen-Frankfurt-Essen | 2.00 | 4 |
| London | Berlin | 7 | 4 | 7 | 15 | London-Amsterdam-Frankfurt-Berlin | 2.14 | 2 |
| Paris | Zagrab | 7 | 4 | 7 | 15 | Paris-Zurich-Venezia-Zagrab | 2.14 | 4 |
| Kyiv | Petrograd | 6 | 3 | 6 | 15 | Kyiv-Wilno-Petrograd | 2.50 | 4 |
| Warszawa | Smolensk | 6 | 3 | 6 | 14 | Warszawa-Wilno-Smolensk | 2.33 | 3 |
| Zurich | Budapest | 6 | 4 | 6 | 13 | Zurich-Munchen-Wien-Budapest | 2.17 | 4 |
| Zagrab | Brindisi | 6 | 4 | 6 | 12 | Zagrab-Venezia-Roma-Brindisi | 2.00 | 3 |
| Zurich | Brindisi | 6 | 4 | 6 | 12 | Zurich-Venezia-Roma-Brindisi | 2.00 | 3 |
| Budapest | Sofia | 5 | 3 | 5 | 11 | Budapest-Sarajevo-Sofia | 2.20 | 4 |
| Sofia | Smyrna | 5 | 3 | 5 | 11 | Sofia-Constantinople-Smyrna | 2.20 | 4 |
| Rostov | Erzurum | 5 | 3 | 5 | 11 | Rostov-Sochi-Erzurum | 2.20 | 3 |
| Frankfurt | Kobenhavn | 5 | 3 | 5 | 11 | Frankfurt-Essen-Kobenhavn | 2.20 | 2 |
| Athina | Angora | 5 | 3 | 5 | 11 | Athina-Smyrna-Angora | 2.20 | 3 |
Below are few observations we can make from the above table:
- It can be observed that all long routes (card points >=20) fetch you around 50-54 final points if you get to do the shortest paths. You still will be left out with nearly half of your locomotives besides doing shortest path in one of these routes because it costs you only around 20-21 locomotives at the max.
- Also its interesting to know that the route
Edinburgh-Athina (21)may seem more attractive overLisboa-Danzig (20)because of the extra card point but the shortest path ofLisboa-Danzigwill fetch you50points where asEdinburgh-Athinafetches you only48points. This is in fact more evident in theshorest path profitabilityratio which essentially explains how profitable is that route. It is simply the ratio of total final points and the cost for it which is the number of locomotives you used to build that route. Also from the table, its evident that the most profitable shortest path route isPalermo-Constantinoplewhich would cost you only8locomotives for a return of25points. That would be a good short route card to grab besides one long route. - Another interesting factor to look at is the
connectivitywhich in this case applies for all the associated route. It indicates the minimum number of edges to remove for blocking out all paths between a given source and destination nodes. The higher it is the better. It can be observed thatBerlin-Bucurestiis by far the most robust route because it takes5edges for anyone to block you out. In the longer routes,Edinburgh-Athina, Kobenhavn-Erzurum, Cadiz-Stockholmare more vulnerable for blockage because fo their lower edge connectivity values. So, you got to play with more caution if you were to do any of these routes.
Alternate Scoring Strategies
On any route, shortest path completion requires least number of locomotives but does not necessarily fetch you maximum points. During the coarse of the game, its quite common for the players to make slight detours especially for gaining few extra points.
Let us analyze the route Palermo-Moskva in more detail. From Table-5 we can see that the shortest path for the route Palermo-Moskva
fetches you a total of 54 points at the cost of 20 locomotives. However, if you have more time, you are more likely to plan a detour for gaining extra points.
So how do you do that? Well, here you need to carefully consider various features associated with every alternate path so as to make good gains.
For e.g, if there is not much time left in the game, you might want to select a path that has less path length because completing every segment of the path length costs
you a turn. Also, you should be able to cover the cost of your selected path so path cost becomes important factor in selecting an optimal path sometimes.
Sometimes, path profitability makes more sense especially when you want more return on your investment.
Deducing all the alternate routes between given source and destination requires finding all simple paths through out the network which could sometimes lead to an indefinite time especially for large networks. Hence we will only find all those alternate paths which are just 2 segments more than the shortest path which simplifies our process. Below is the code fragment which essentially does that.
# return all paths between u and v in graph g up to distance min(u,v)+2
def alternate_scoring_paths_with_cutoff(g, u, v):
sp_length = nx.shortest_path_length(g,u,v)
paths = nx.all_simple_paths(g, u, v, cutoff=sp_length+2)
return list(paths)
Using the above method, we generate all the alternate paths for the route Palermo-Moskva and the related results are listed below in
Table-6. You can carefully analyze below paths and select the most optimal path depending on your criteria.
Similarly alternate paths can be deduced for any given route.
Table-6: Alternate Scoring Paths for Route Palermo-Moskva
| alternate path | length of path | cost of path | total points | path profitability |
|---|---|---|---|---|
| [Palermo, Smyrna, Constantinople, Sevastopol, Rostov, Kharkov, Moskva] | 7 | 22 | 60 | 2.73 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Kyiv, Smolensk, Moskva] | 7 | 20 | 54 | 2.70 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Kyiv, Kharkov, Moskva] | 7 | 23 | 62 | 2.70 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Budapest, Kyiv, Kharkov, Moskva] | 8 | 29 | 77 | 2.66 |
| [Palermo, Smyrna, Athina, Sarajevo, Budapest, Kyiv, Kharkov, Moskva] | 8 | 29 | 77 | 2.66 |
| [Palermo, Smyrna, Athina, Sarajevo, Budapest, Kyiv, Smolensk, Moskva] | 8 | 26 | 69 | 2.65 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Budapest, Kyiv, Smolensk, Moskva] | 8 | 26 | 69 | 2.65 |
| [Palermo, Smyrna, Constantinople, Sevastopol, Sochi, Rostov, Kharkov, Moskva] | 8 | 22 | 57 | 2.59 |
| [Palermo, Roma, Venezia, Zagrab, Budapest, Kyiv, Kharkov, Moskva] | 8 | 24 | 62 | 2.58 |
| [Palermo, Smyrna, Constantinople, Sevastopol, Bucuresti, Kyiv, Kharkov, Moskva] | 8 | 28 | 72 | 2.57 |
| [Palermo, Roma, Venezia, Zagrab, Budapest, Kyiv, Smolensk, Moskva] | 8 | 21 | 54 | 2.57 |
| [Palermo, Smyrna, Constantinople, Sevastopol, Bucuresti, Kyiv, Smolensk, Moskva] | 8 | 25 | 64 | 2.56 |
| [Palermo, Smyrna, Constantinople, Sevastopol, Bucuresti, Budapest, Kyiv, Kharkov, Moskva] | 9 | 34 | 87 | 2.56 |
| [Palermo, Smyrna, Constantinople, Sofia, Bucuresti, Kyiv, Kharkov, Moskva] | 8 | 25 | 64 | 2.56 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Sevastopol, Rostov, Kharkov, Moskva] | 8 | 25 | 64 | 2.56 |
| [Palermo, Smyrna, Angora, Constantinople, Sevastopol, Rostov, Kharkov, Moskva] | 8 | 25 | 64 | 2.56 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Kyiv, Wilno, Petrograd, Moskva] | 8 | 25 | 64 | 2.56 |
| [Palermo, Smyrna, Athina, Sofia, Bucuresti, Kyiv, Kharkov, Moskva] | 8 | 25 | 64 | 2.56 |
| [Palermo, Smyrna, Athina, Sarajevo, Budapest, Kyiv, Wilno, Petrograd, Moskva] | 9 | 31 | 79 | 2.55 |
| [Palermo, Smyrna, Constantinople, Sofia, Bucuresti, Kyiv, Smolensk, Moskva] | 8 | 22 | 56 | 2.55 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Budapest, Kyiv, Wilno, Petrograd, Moskva] | 9 | 31 | 79 | 2.55 |
| [Palermo, Smyrna, Athina, Sarajevo, Zagrab, Budapest, Kyiv, Kharkov, Moskva] | 9 | 31 | 79 | 2.55 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Kyiv, Wilno, Smolensk, Moskva] | 8 | 22 | 56 | 2.55 |
| [Palermo, Smyrna, Constantinople, Sevastopol, Bucuresti, Budapest, Kyiv, Smolensk, Moskva] | 9 | 31 | 79 | 2.55 |
| [Palermo, Smyrna, Athina, Sofia, Bucuresti, Kyiv, Smolensk, Moskva] | 8 | 22 | 56 | 2.55 |
| [Palermo, Smyrna, Constantinople, Sofia, Bucuresti, Budapest, Kyiv, Kharkov, Moskva] | 9 | 31 | 79 | 2.55 |
| [Palermo, Smyrna, Athina, Sofia, Bucuresti, Budapest, Kyiv, Kharkov, Moskva] | 9 | 31 | 79 | 2.55 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Budapest, Kyiv, Wilno, Smolensk, Moskva] | 9 | 28 | 71 | 2.54 |
| [Palermo, Smyrna, Athina, Sarajevo, Budapest, Kyiv, Wilno, Smolensk, Moskva] | 9 | 28 | 71 | 2.54 |
| [Palermo, Smyrna, Constantinople, Sofia, Bucuresti, Budapest, Kyiv, Smolensk, Moskva] | 9 | 28 | 71 | 2.54 |
| [Palermo, Smyrna, Athina, Sofia, Bucuresti, Budapest, Kyiv, Smolensk, Moskva] | 9 | 28 | 71 | 2.54 |
| [Palermo, Smyrna, Athina, Sarajevo, Zagrab, Budapest, Kyiv, Smolensk, Moskva] | 9 | 28 | 71 | 2.54 |
| [Palermo, Brindisi, Athina, Sarajevo, Budapest, Kyiv, Kharkov, Moskva] | 8 | 28 | 71 | 2.54 |
| [Palermo, Smyrna, Angora, Erzurum, Sevastopol, Rostov, Kharkov, Moskva] | 8 | 26 | 66 | 2.54 |
| [Palermo, Smyrna, Angora, Constantinople, Bucuresti, Kyiv, Kharkov, Moskva] | 8 | 26 | 66 | 2.54 |
| [Palermo, Smyrna, Athina, Sofia, Sarajevo, Budapest, Kyiv, Kharkov, Moskva] | 9 | 30 | 76 | 2.53 |
| [Palermo, Smyrna, Constantinople, Sofia, Sarajevo, Budapest, Kyiv, Kharkov, Moskva] | 9 | 30 | 76 | 2.53 |
| [Palermo, Smyrna, Angora, Constantinople, Bucuresti, Budapest, Kyiv, Kharkov, Moskva] | 9 | 32 | 81 | 2.53 |
| [Palermo, Smyrna, Angora, Constantinople, Bucuresti, Kyiv, Smolensk, Moskva] | 8 | 23 | 58 | 2.52 |
| [Palermo, Roma, Venezia, Zagrab, Wien, Budapest, Kyiv, Kharkov, Moskva] | 9 | 25 | 63 | 2.52 |
| [Palermo, Brindisi, Athina, Sarajevo, Budapest, Kyiv, Smolensk, Moskva] | 8 | 25 | 63 | 2.52 |
| [Palermo, Smyrna, Constantinople, Sofia, Sarajevo, Budapest, Kyiv, Smolensk, Moskva] | 9 | 27 | 68 | 2.52 |
| [Palermo, Smyrna, Angora, Erzurum, Sochi, Rostov, Kharkov, Moskva] | 8 | 23 | 58 | 2.52 |
| [Palermo, Smyrna, Angora, Constantinople, Bucuresti, Budapest, Kyiv, Smolensk, Moskva] | 9 | 29 | 73 | 2.52 |
| [Palermo, Smyrna, Athina, Sofia, Sarajevo, Budapest, Kyiv, Smolensk, Moskva] | 9 | 27 | 68 | 2.52 |
| [Palermo, Roma, Venezia, Zagrab, Wien, Budapest, Kyiv, Smolensk, Moskva] | 9 | 22 | 55 | 2.50 |
| [Palermo, Roma, Venezia, Munchen, Wien, Budapest, Kyiv, Kharkov, Moskva] | 9 | 26 | 65 | 2.50 |
| [Palermo, Roma, Venezia, Munchen, Wien, Budapest, Kyiv, Smolensk, Moskva] | 9 | 23 | 57 | 2.48 |
| [Palermo, Smyrna, Constantinople, Sevastopol, Bucuresti, Kyiv, Wilno, Petrograd, Moskva] | 9 | 30 | 74 | 2.47 |
| [Palermo, Smyrna, Athina, Sarajevo, Sofia, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 28 | 69 | 2.46 |
| [Palermo, Roma, Venezia, Zagrab, Budapest, Kyiv, Wilno, Petrograd, Moskva] | 9 | 26 | 64 | 2.46 |
| [Palermo, Smyrna, Athina, Sarajevo, Budapest, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 31 | 76 | 2.45 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Kyiv, Wilno, Riga, Petrograd, Moskva] | 9 | 29 | 71 | 2.45 |
| [Palermo, Smyrna, Angora, Constantinople, Sevastopol, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 31 | 76 | 2.45 |
| [Palermo, Roma, Brindisi, Athina, Sarajevo, Budapest, Kyiv, Kharkov, Moskva] | 9 | 31 | 76 | 2.45 |
| [Palermo, Smyrna, Angora, Erzurum, Sevastopol, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 32 | 78 | 2.44 |
| [Palermo, Brindisi, Roma, Venezia, Zagrab, Budapest, Kyiv, Kharkov, Moskva] | 9 | 25 | 61 | 2.44 |
| [Palermo, Smyrna, Athina, Sarajevo, Sofia, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 25 | 61 | 2.44 |
| [Palermo, Smyrna, Athina, Sofia, Bucuresti, Kyiv, Wilno, Petrograd, Moskva] | 9 | 27 | 66 | 2.44 |
| [Palermo, Smyrna, Athina, Sofia, Bucuresti, Sevastopol, Rostov, Kharkov, Moskva] | 9 | 27 | 66 | 2.44 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Sevastopol, Sochi, Rostov, Kharkov, Moskva] | 9 | 25 | 61 | 2.44 |
| [Palermo, Smyrna, Angora, Constantinople, Sevastopol, Sochi, Rostov, Kharkov, Moskva] | 9 | 25 | 61 | 2.44 |
| [Palermo, Smyrna, Constantinople, Sevastopol, Erzurum, Sochi, Rostov, Kharkov, Moskva] | 9 | 27 | 66 | 2.44 |
| [Palermo, Smyrna, Constantinople, Sevastopol, Bucuresti, Kyiv, Wilno, Smolensk, Moskva] | 9 | 27 | 66 | 2.44 |
| [Palermo, Smyrna, Constantinople, Sevastopol, Rostov, Kharkov, Kyiv, Smolensk, Moskva] | 9 | 27 | 66 | 2.44 |
| [Palermo, Smyrna, Constantinople, Sofia, Bucuresti, Sevastopol, Rostov, Kharkov, Moskva] | 9 | 27 | 66 | 2.44 |
| [Palermo, Smyrna, Constantinople, Sofia, Bucuresti, Kyiv, Wilno, Petrograd, Moskva] | 9 | 27 | 66 | 2.44 |
| [Palermo, Smyrna, Constantinople, Angora, Erzurum, Sevastopol, Rostov, Kharkov, Moskva] | 9 | 27 | 66 | 2.44 |
| [Palermo, Smyrna, Athina, Sarajevo, Budapest, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 28 | 68 | 2.43 |
| [Palermo, Brindisi, Athina, Sofia, Bucuresti, Budapest, Kyiv, Kharkov, Moskva] | 9 | 30 | 73 | 2.43 |
| [Palermo, Roma, Venezia, Zagrab, Sarajevo, Budapest, Kyiv, Kharkov, Moskva] | 9 | 28 | 68 | 2.43 |
| [Palermo, Smyrna, Angora, Constantinople, Sevastopol, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 28 | 68 | 2.43 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Kyiv, Warszawa, Wilno, Petrograd, Moskva] | 9 | 30 | 73 | 2.43 |
| [Palermo, Smyrna, Athina, Sofia, Constantinople, Sevastopol, Rostov, Kharkov, Moskva] | 9 | 28 | 68 | 2.43 |
| [Palermo, Roma, Venezia, Zagrab, Budapest, Kyiv, Wilno, Smolensk, Moskva] | 9 | 23 | 56 | 2.43 |
| [Palermo, Smyrna, Angora, Constantinople, Sofia, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 28 | 68 | 2.43 |
| [Palermo, Roma, Brindisi, Athina, Sarajevo, Budapest, Kyiv, Smolensk, Moskva] | 9 | 28 | 68 | 2.43 |
| [Palermo, Smyrna, Angora, Constantinople, Bucuresti, Sevastopol, Rostov, Kharkov, Moskva] | 9 | 28 | 68 | 2.43 |
| [Palermo, Brindisi, Athina, Sarajevo, Zagrab, Budapest, Kyiv, Kharkov, Moskva] | 9 | 30 | 73 | 2.43 |
| [Palermo, Brindisi, Athina, Sarajevo, Budapest, Kyiv, Wilno, Petrograd, Moskva] | 9 | 30 | 73 | 2.43 |
| [Palermo, Smyrna, Angora, Constantinople, Bucuresti, Kyiv, Wilno, Petrograd, Moskva] | 9 | 28 | 68 | 2.43 |
| [Palermo, Brindisi, Athina, Sofia, Bucuresti, Kyiv, Kharkov, Moskva] | 8 | 24 | 58 | 2.42 |
| [Palermo, Smyrna, Angora, Erzurum, Sevastopol, Sochi, Rostov, Kharkov, Moskva] | 9 | 26 | 63 | 2.42 |
| [Palermo, Smyrna, Constantinople, Angora, Erzurum, Sochi, Rostov, Kharkov, Moskva] | 9 | 24 | 58 | 2.42 |
| [Palermo, Smyrna, Constantinople, Sofia, Bucuresti, Kyiv, Wilno, Smolensk, Moskva] | 9 | 24 | 58 | 2.42 |
| [Palermo, Smyrna, Athina, Sofia, Bucuresti, Kyiv, Wilno, Smolensk, Moskva] | 9 | 24 | 58 | 2.42 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Kyiv, Warszawa, Wilno, Smolensk, Moskva] | 9 | 27 | 65 | 2.41 |
| [Palermo, Brindisi, Athina, Sofia, Bucuresti, Budapest, Kyiv, Smolensk, Moskva] | 9 | 27 | 65 | 2.41 |
| [Palermo, Brindisi, Roma, Venezia, Zagrab, Budapest, Kyiv, Smolensk, Moskva] | 9 | 22 | 53 | 2.41 |
| [Palermo, Brindisi, Athina, Sarajevo, Zagrab, Budapest, Kyiv, Smolensk, Moskva] | 9 | 27 | 65 | 2.41 |
| [Palermo, Smyrna, Athina, Sofia, Constantinople, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 29 | 70 | 2.41 |
| [Palermo, Smyrna, Angora, Erzurum, Sochi, Sevastopol, Rostov, Kharkov, Moskva] | 9 | 27 | 65 | 2.41 |
| [Palermo, Brindisi, Athina, Sarajevo, Budapest, Kyiv, Wilno, Smolensk, Moskva] | 9 | 27 | 65 | 2.41 |
| [Palermo, Smyrna, Constantinople, Bucuresti, Kyiv, Smolensk, Wilno, Petrograd, Moskva] | 9 | 29 | 70 | 2.41 |
| [Palermo, Brindisi, Athina, Sofia, Sarajevo, Budapest, Kyiv, Kharkov, Moskva] | 9 | 29 | 70 | 2.41 |
| [Palermo, Smyrna, Angora, Erzurum, Sevastopol, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 29 | 70 | 2.41 |
| [Palermo, Smyrna, Angora, Constantinople, Sofia, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 25 | 60 | 2.40 |
| [Palermo, Smyrna, Angora, Constantinople, Bucuresti, Kyiv, Wilno, Smolensk, Moskva] | 9 | 25 | 60 | 2.40 |
| [Palermo, Roma, Venezia, Zagrab, Sarajevo, Budapest, Kyiv, Smolensk, Moskva] | 9 | 25 | 60 | 2.40 |
| [Palermo, Smyrna, Athina, Sofia, Constantinople, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 26 | 62 | 2.38 |
| [Palermo, Brindisi, Athina, Sofia, Sarajevo, Budapest, Kyiv, Smolensk, Moskva] | 9 | 26 | 62 | 2.38 |
| [Palermo, Brindisi, Athina, Sofia, Bucuresti, Kyiv, Smolensk, Moskva] | 8 | 21 | 50 | 2.38 |
| [Palermo, Roma, Venezia, Zagrab, Wien, Warszawa, Kyiv, Kharkov, Moskva] | 9 | 26 | 61 | 2.35 |
| [Palermo, Roma, Venezia, Zagrab, Budapest, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 26 | 61 | 2.35 |
| [Palermo, Brindisi, Athina, Sarajevo, Sofia, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 27 | 63 | 2.33 |
| [Palermo, Roma, Brindisi, Athina, Sofia, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 27 | 63 | 2.33 |
| [Palermo, Roma, Venezia, Munchen, Wien, Warszawa, Kyiv, Kharkov, Moskva] | 9 | 27 | 63 | 2.33 |
| [Palermo, Brindisi, Athina, Sarajevo, Budapest, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 30 | 70 | 2.33 |
| [Palermo, Brindisi, Athina, Smyrna, Constantinople, Sevastopol, Rostov, Kharkov, Moskva] | 9 | 25 | 58 | 2.32 |
| [Palermo, Roma, Venezia, Zagrab, Wien, Warszawa, Wilno, Petrograd, Moskva] | 9 | 25 | 58 | 2.32 |
| [Palermo, Roma, Venezia, Munchen, Wien, Warszawa, Wilno, Petrograd, Moskva] | 9 | 26 | 60 | 2.31 |
| [Palermo, Brindisi, Athina, Sofia, Bucuresti, Sevastopol, Rostov, Kharkov, Moskva] | 9 | 26 | 60 | 2.31 |
| [Palermo, Brindisi, Athina, Sofia, Bucuresti, Kyiv, Wilno, Petrograd, Moskva] | 9 | 26 | 60 | 2.31 |
| [Palermo, Brindisi, Athina, Smyrna, Constantinople, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 26 | 60 | 2.31 |
| [Palermo, Roma, Venezia, Zagrab, Budapest, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 23 | 53 | 2.30 |
| [Palermo, Roma, Venezia, Zagrab, Wien, Warszawa, Kyiv, Smolensk, Moskva] | 9 | 23 | 53 | 2.30 |
| [Palermo, Brindisi, Athina, Sofia, Constantinople, Sevastopol, Rostov, Kharkov, Moskva] | 9 | 27 | 62 | 2.30 |
| [Palermo, Brindisi, Athina, Sarajevo, Budapest, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 27 | 62 | 2.30 |
| [Palermo, Roma, Brindisi, Athina, Sofia, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 24 | 55 | 2.29 |
| [Palermo, Brindisi, Athina, Sarajevo, Sofia, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 24 | 55 | 2.29 |
| [Palermo, Brindisi, Athina, Sofia, Constantinople, Bucuresti, Kyiv, Kharkov, Moskva] | 9 | 28 | 64 | 2.29 |
| [Palermo, Roma, Venezia, Munchen, Wien, Warszawa, Kyiv, Smolensk, Moskva] | 9 | 24 | 55 | 2.29 |
| [Palermo, Roma, Venezia, Zagrab, Wien, Warszawa, Wilno, Smolensk, Moskva] | 9 | 22 | 50 | 2.27 |
| [Palermo, Brindisi, Athina, Smyrna, Constantinople, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 23 | 52 | 2.26 |
| [Palermo, Roma, Venezia, Munchen, Wien, Warszawa, Wilno, Smolensk, Moskva] | 9 | 23 | 52 | 2.26 |
| [Palermo, Brindisi, Athina, Sofia, Bucuresti, Kyiv, Wilno, Smolensk, Moskva] | 9 | 23 | 52 | 2.26 |
| [Palermo, Brindisi, Athina, Sofia, Constantinople, Bucuresti, Kyiv, Smolensk, Moskva] | 9 | 25 | 56 | 2.24 |
Blocking Strategies
In the previous section, we have seen alternate scoring strategies. However you need to be aware of what it takes for others to block you to complete your
desired route. Using Mininum edge cut for any route, we can find out the list of most critical edges if all are blocked would mean that you cannot complete that route.
For example for the same route discussed above Palermo-Moskva, it takes 3 edges for anyone to knock you down.
In other words, it essentially means that you need make smart choices to build on these edges relatively sooner and leaving less chance for others to block you.
for min_cut in list(nx.minimum_edge_cut(G,'Palermo','Moskva')):
print(min_cut)
('Petrograd', 'Moskva')
('Kharkov', 'Moskva')
('Smolensk', 'Moskva')
We have seen from Table-5 that the most robust routes are Berlin-Bucurest and Paris-Wien because it takes 5 turns for anyone to block on these.
for min_cut in list(nx.minimum_edge_cut(G,'Bucuresti','Berlin')):
print(min_cut)
('Frankfurt', 'Berlin')
('Danzig', 'Berlin')
('Essen', 'Berlin')
('Wien', 'Berlin')
('Warszawa', 'Berlin')
for min_cut in list(nx.minimum_edge_cut(G,'Paris','Wien')):
print(min_cut)
('Munchen', 'Wien')
('Berlin', 'Wien')
('Budapest', 'Wien')
('Warszawa', 'Wien')
('Zagrab', 'Wien')
Also, the most vulnerable route is Edinburgh-Athina because it takes only 1 edge for anyone to block you completely.
for min_cut in list(nx.minimum_edge_cut(G,'Edinburgh','Athina')):
print(min_cut)
('Edinburgh', 'London')
Code
All the code used in this analysis can be downloaded from this github repository
Leave a comment