Transport Analytics Training Series - Last Revision: October 2022

Working with Network Datasets¶

Now that we have covered the basics of networkx, and we can start experimenting with "real" network files. In this section, we will be using the classical Sioux Falls network layout, which is very frequently used as a 'toy' network in the academic transportation literature.

In this particular notebook, we are also going to carry out a fair amount of data manipulation, and for this reason we will also need to use the pandas library. We can make sure that it has been properly installed using the below command.

In [1]:
!pip install pandas

Requirement already satisfied: pandas in /Users/pa01/opt/anaconda3/lib/python3.9/site-packages (1.4.2)
Requirement already satisfied: python-dateutil>=2.8.1 in /Users/pa01/opt/anaconda3/lib/python3.9/site-packages (from pandas) (2.8.2)
Requirement already satisfied: pytz>=2020.1 in /Users/pa01/opt/anaconda3/lib/python3.9/site-packages (from pandas) (2021.3)
Requirement already satisfied: numpy>=1.20.0 in /Users/pa01/opt/anaconda3/lib/python3.9/site-packages (from pandas) (1.21.5)
Requirement already satisfied: six>=1.5 in /Users/pa01/opt/anaconda3/lib/python3.9/site-packages (from python-dateutil>=2.8.1->pandas) (1.16.0)

pandas will only be used to import and manage the data contained in the external files. Any network manipulation activities will requirenetworkx - which we also need to import, as before.

In [2]:
import networkx as nx
import pandas as pd

A common convention when importing pandas is to use the pd acronym.

Part 1 - Loading external files¶

I have placed the relevant datasets in a separate folder. The network structure is expressed as a series of csv files, which we can easily read using the pd.read_csv() command, which returns a "dataframe" that contains the information in the file.

In [3]:
links = pd.read_csv('data-sioux-falls/siouxfalls_links.csv')
links
Out[3]:
from_node to_node length
0 1 2 6
1 1 3 4
2 2 1 6
3 2 6 5
4 3 1 4
... ... ... ...
71 23 22 4
72 23 24 2
73 24 13 4
74 24 21 3
75 24 23 2

76 rows × 3 columns

As you can notice above, pandas is able to recognise the labels in our csv file, and uses them to name the columns. Its algorithms, however, is not foolproof - occasionally you might need to intervene.

In [4]:
nodes = pd.read_csv('data-sioux-falls/siouxfalls_nodes.csv')
nodes
Out[4]:
node x y
0 1 -96.770420 43.612828
1 2 -96.711251 43.605813
2 3 -96.774303 43.572962
3 4 -96.747168 43.563654
4 5 -96.731569 43.564034
5 6 -96.711644 43.587586
6 7 -96.693423 43.563844
7 8 -96.711382 43.562324
8 9 -96.731241 43.548596
9 10 -96.731438 43.545271
10 11 -96.746841 43.544131
11 12 -96.780137 43.543941
12 13 -96.793377 43.490707
13 14 -96.751035 43.529306
14 15 -96.731504 43.529401
15 16 -96.711382 43.546744
16 17 -96.711382 43.541280
17 18 -96.694078 43.546744
18 19 -96.711316 43.529591
19 20 -96.711185 43.515333
20 21 -96.730979 43.510485
21 22 -96.731241 43.514858
22 23 -96.750904 43.514858
23 24 -96.749200 43.503164

We don't need to add all these edges to a graph one by one - we can simply create a list of edges and supply them to networkx.

To do this, we will use the zip() command which is used to take separate lists of objects (with the same number of items) and join them in a single object. The two lists that we wish to join is the sequence of origin nodes (from_node)and the sequence of destination nodes (to_node) in our pandas dataframe.

The resulting object that is returned by th zip function cannot be used directly, but must rather converted into a list using the list() command.

In [5]:
new_links = list(zip(links['from_node'], links['to_node']))
new_links
Out[5]:
[(1, 2),
 (1, 3),
 (2, 1),
 (2, 6),
 (3, 1),
 (3, 4),
 (3, 12),
 (4, 3),
 (4, 5),
 (4, 11),
 (5, 4),
 (5, 6),
 (5, 9),
 (6, 2),
 (6, 5),
 (6, 8),
 (7, 8),
 (7, 18),
 (8, 6),
 (8, 7),
 (8, 9),
 (8, 16),
 (9, 5),
 (9, 8),
 (9, 10),
 (10, 9),
 (10, 11),
 (10, 15),
 (10, 16),
 (10, 17),
 (11, 4),
 (11, 10),
 (11, 12),
 (11, 14),
 (12, 3),
 (12, 11),
 (12, 13),
 (13, 12),
 (13, 24),
 (14, 11),
 (14, 15),
 (14, 23),
 (15, 10),
 (15, 14),
 (15, 19),
 (15, 22),
 (16, 8),
 (16, 10),
 (16, 17),
 (16, 18),
 (17, 10),
 (17, 16),
 (17, 19),
 (18, 7),
 (18, 16),
 (18, 20),
 (19, 15),
 (19, 17),
 (19, 20),
 (20, 18),
 (20, 19),
 (20, 21),
 (20, 22),
 (21, 20),
 (21, 22),
 (21, 24),
 (22, 15),
 (22, 20),
 (22, 21),
 (22, 23),
 (23, 14),
 (23, 22),
 (23, 24),
 (24, 13),
 (24, 21),
 (24, 23)]

We are now ready too proceed:

In [6]:
G = nx.Graph()
G.add_nodes_from(nodes['node'])
G.add_edges_from(new_links)

This is a lot more compact than the first graph that we generated. In the first instance we passed a list of node IDs to the add_nodes_from function, that were contained in the nodes['node'] column. NetworkX used these IDs to create new node objects.

The list of links was also passed to NetworkX. The resulting network is:

In [7]:
nx.draw(G, with_labels = True, font_color = 'white')

Contrary to the abstract graphs that we experimented with earlier, this relates to a civil infrastructure network and it would be therefore quite important to represent its spatial structure accurately.

To achieve this, we need to create a list of node parameters. We can do that by zipping the relevant columns in the nodes dataframe. In contrast to the sequence of edge colors that we used before, this needs to be served to networkx as a dictionary, with the keys being the node IDs and the values being the coordinates.

In [8]:
coords = list(zip(nodes['x'], nodes['y']))
pos = dict(zip(nodes['node'], coords))
pos
Out[8]:
{1: (-96.77041974, 43.61282792),
 2: (-96.71125063, 43.60581298),
 3: (-96.77430341, 43.5729616),
 4: (-96.74716843, 43.56365362),
 5: (-96.73156909, 43.56403357),
 6: (-96.71164389, 43.58758553),
 7: (-96.69342281, 43.5638436),
 8: (-96.71138171, 43.56232379),
 9: (-96.73124137, 43.54859634),
 10: (-96.73143801, 43.54527088),
 11: (-96.74684071, 43.54413068),
 12: (-96.78013678, 43.54394065),
 13: (-96.79337655, 43.49070718),
 14: (-96.75103549, 43.52930613),
 15: (-96.73150355, 43.52940117),
 16: (-96.71138171, 43.54674361),
 17: (-96.71138171, 43.54128009),
 18: (-96.69407825, 43.54674361),
 19: (-96.71131617, 43.52959125),
 20: (-96.71118508, 43.5153335),
 21: (-96.7309792, 43.51048509),
 22: (-96.73124137, 43.51485818),
 23: (-96.75090441, 43.51485818),
 24: (-96.74920028, 43.50316422)}
In [9]:
nx.draw(G, pos, with_labels = True, font_color = 'white')

We can now start experimenting with the paths again - we pick two nodes (13 and 7), and can call the nx.dijkstra_path_length() command to get the length of the shortest path, as calculated by the Dijkstras algorithm implementation provided by networkx.

In [10]:
nx.dijkstra_path_length(G, source=13, target=7)
Out[10]:
5

The algorithm reports that the length of the shortest path is 5. Looking at the list of edges that we loaded, it is reasonable to suspect that something is not right.

Part 2 - Visualizing shortest paths¶

Let's visualize the path:

In [11]:
path = nx.dijkstra_path(G, source=13, target=7)
path
Out[11]:
[13, 24, 21, 20, 18, 7]

We can now plot it using the same approach that we followed above.

In [12]:
edges_path = list(zip(path,path[1:]))
edge_colors = ['red' if edge in edges_path else 'black' for edge in G.edges()]
nx.draw(G, pos, with_labels = True, edge_color= edge_colors, font_color = 'white')

We can only see one highlighted line in the graph, and this certainly does not suffice to connect 13 to 7. After all, the shortest path had several nodes, and we would have expected to see several edges highlighted.

Let us look at the variables one by one.

In [13]:
edges_path
Out[13]:
[(13, 24), (24, 21), (21, 20), (20, 18), (18, 7)]

Everything appears to be OK here.

In [14]:
edge_colors
Out[14]:
['black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'red',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black',
 'black']

We are getting closer - only one node is highlighted. The problem must be located at the command used to generate this list:

edge_colors = ['red' if edge in edges_path else 'black' for edge in G.edges()]

Let's look at the lists of variables that we are comparing, G.edges() and edges_path.

In [15]:
G.edges()
Out[15]:
EdgeView([(1, 2), (1, 3), (2, 6), (3, 4), (3, 12), (4, 5), (4, 11), (5, 6), (5, 9), (6, 8), (7, 8), (7, 18), (8, 9), (8, 16), (9, 10), (10, 11), (10, 15), (10, 16), (10, 17), (11, 12), (11, 14), (12, 13), (13, 24), (14, 15), (14, 23), (15, 19), (15, 22), (16, 17), (16, 18), (17, 19), (18, 20), (19, 20), (20, 21), (20, 22), (21, 22), (21, 24), (22, 23), (23, 24)])
In [16]:
edges_path
Out[16]:
[(13, 24), (24, 21), (21, 20), (20, 18), (18, 7)]

Here is the problem - the edges_path list starts with the edge (13,12). The list returned by G.edges() does not contain such an edge - it does, however have (12,13)!

We have spotted the problem. Even though our graph is bidirectional, the code that we wrote to highlight the edges does not "understand" the concepts of bi-directionality. It simply checks the edges as reported by networkx.

There are many ways to resolve this - for the time being we will use something quick and dirty: we will add to the edges_path the reversed versions of all edges. This way we will ensure that the edge will be highlighted.

We can start by creating a list of the reversed edges:

In [17]:
edges_path_reversed = [(y,x) for (x,y) in edges_path]
edges_path_reversed
Out[17]:
[(24, 13), (21, 24), (20, 21), (18, 20), (7, 18)]

We now append them to the list:

In [18]:
edges_path = edges_path + edges_path_reversed
edges_path
Out[18]:
[(13, 24),
 (24, 21),
 (21, 20),
 (20, 18),
 (18, 7),
 (24, 13),
 (21, 24),
 (20, 21),
 (18, 20),
 (7, 18)]

Let's try again!

In [19]:
edge_colors = ['red' if edge in edges_path else 'black' for edge in G.edges()]
nx.draw(G, pos, with_labels = True, edge_color= edge_colors)

Success!

But this is only one of the problems that we encountered... If you might recall, we also need to find out why the shortest path is so short.

The Dijkstra's algorithm provided by networkx calculates the paths using the weight property of each edge. We can inspect this using this following command:

In [20]:
G.edges.data("weight")
Out[20]:
EdgeDataView([(1, 2, None), (1, 3, None), (2, 6, None), (3, 4, None), (3, 12, None), (4, 5, None), (4, 11, None), (5, 6, None), (5, 9, None), (6, 8, None), (7, 8, None), (7, 18, None), (8, 9, None), (8, 16, None), (9, 10, None), (10, 11, None), (10, 15, None), (10, 16, None), (10, 17, None), (11, 12, None), (11, 14, None), (12, 13, None), (13, 24, None), (14, 15, None), (14, 23, None), (15, 19, None), (15, 22, None), (16, 17, None), (16, 18, None), (17, 19, None), (18, 20, None), (19, 20, None), (20, 21, None), (20, 22, None), (21, 22, None), (21, 24, None), (22, 23, None), (23, 24, None)])

Uh, but of course! We never added the lenghts that were included in the links dataframe to the graph.

We can provide these using a dictionary, that has the actual edges as keys and the lengths as values:

In [21]:
weights = dict(zip(G.edges,links['length']))
weights
Out[21]:
{(1, 2): 6,
 (1, 3): 4,
 (2, 6): 6,
 (3, 4): 5,
 (3, 12): 4,
 (4, 5): 4,
 (4, 11): 4,
 (5, 6): 4,
 (5, 9): 2,
 (6, 8): 6,
 (7, 8): 2,
 (7, 18): 4,
 (8, 9): 5,
 (8, 16): 5,
 (9, 10): 4,
 (10, 11): 2,
 (10, 15): 3,
 (10, 16): 2,
 (10, 17): 2,
 (11, 12): 3,
 (11, 14): 10,
 (12, 13): 5,
 (13, 24): 5,
 (14, 15): 10,
 (14, 23): 3,
 (15, 19): 3,
 (15, 22): 5,
 (16, 17): 6,
 (16, 18): 4,
 (17, 19): 8,
 (18, 20): 6,
 (19, 20): 5,
 (20, 21): 6,
 (20, 22): 4,
 (21, 22): 4,
 (21, 24): 6,
 (22, 23): 3,
 (23, 24): 3}
In [22]:
nx.set_edge_attributes(G, values = weights, name = 'weight')
G.edges.data("weight")
Out[22]:
EdgeDataView([(1, 2, 6), (1, 3, 4), (2, 6, 6), (3, 4, 5), (3, 12, 4), (4, 5, 4), (4, 11, 4), (5, 6, 4), (5, 9, 2), (6, 8, 6), (7, 8, 2), (7, 18, 4), (8, 9, 5), (8, 16, 5), (9, 10, 4), (10, 11, 2), (10, 15, 3), (10, 16, 2), (10, 17, 2), (11, 12, 3), (11, 14, 10), (12, 13, 5), (13, 24, 5), (14, 15, 10), (14, 23, 3), (15, 19, 3), (15, 22, 5), (16, 17, 6), (16, 18, 4), (17, 19, 8), (18, 20, 6), (19, 20, 5), (20, 21, 6), (20, 22, 4), (21, 22, 4), (21, 24, 6), (22, 23, 3), (23, 24, 3)])

Much better. Let's try again.

In [23]:
nx.dijkstra_path_length(G, source=13, target=7)
Out[23]:
19

This looks more like it! Let's visualise the shortest path:

In [24]:
path = nx.dijkstra_path(G, source=13, target=7)
path
Out[24]:
[13, 12, 11, 10, 16, 8, 7]
In [25]:
edges_path = list(zip(path,path[1:]))
edges_path_reversed = [(y,x) for (x,y) in edges_path]
edges_path = edges_path + edges_path_reversed
edge_colors = ['red' if edge in edges_path else 'black' for edge in G.edges()]
nx.draw(G, pos, with_labels = True, edge_color= edge_colors)

So, the path is actually different from the one that we obtained before - it turns out that when a weight is not provided, Dijkstra's uses a default weight of 1.

Part 3 - All-to-all shortest paths¶

What if we wanted to obtain all the shortest paths in our network?

In [26]:
all_paths = dict(nx.all_pairs_dijkstra_path(G))
all_paths
Out[26]:
{1: {1: [1],
  2: [1, 2],
  3: [1, 3],
  4: [1, 3, 4],
  12: [1, 3, 12],
  6: [1, 2, 6],
  11: [1, 3, 12, 11],
  13: [1, 3, 12, 13],
  5: [1, 3, 4, 5],
  10: [1, 3, 12, 11, 10],
  14: [1, 3, 12, 11, 14],
  8: [1, 2, 6, 8],
  24: [1, 3, 12, 13, 24],
  9: [1, 3, 4, 5, 9],
  15: [1, 3, 12, 11, 10, 15],
  16: [1, 3, 12, 11, 10, 16],
  17: [1, 3, 12, 11, 10, 17],
  18: [1, 3, 12, 11, 10, 16, 18],
  19: [1, 3, 12, 11, 10, 15, 19],
  22: [1, 3, 12, 11, 10, 15, 22],
  7: [1, 2, 6, 8, 7],
  21: [1, 3, 12, 13, 24, 21],
  23: [1, 3, 12, 13, 24, 23],
  20: [1, 3, 12, 11, 10, 15, 19, 20]},
 2: {2: [2],
  1: [2, 1],
  6: [2, 6],
  3: [2, 1, 3],
  5: [2, 6, 5],
  8: [2, 6, 8],
  4: [2, 6, 5, 4],
  12: [2, 1, 3, 12],
  9: [2, 6, 5, 9],
  7: [2, 6, 8, 7],
  16: [2, 6, 8, 16],
  10: [2, 6, 5, 9, 10],
  11: [2, 1, 3, 12, 11],
  13: [2, 1, 3, 12, 13],
  18: [2, 6, 8, 7, 18],
  15: [2, 6, 5, 9, 10, 15],
  17: [2, 6, 5, 9, 10, 17],
  14: [2, 1, 3, 12, 11, 14],
  20: [2, 6, 8, 7, 18, 20],
  19: [2, 6, 5, 9, 10, 15, 19],
  24: [2, 1, 3, 12, 13, 24],
  22: [2, 6, 5, 9, 10, 15, 22],
  21: [2, 6, 5, 9, 10, 15, 22, 21],
  23: [2, 1, 3, 12, 13, 24, 23]},
 3: {3: [3],
  1: [3, 1],
  4: [3, 4],
  12: [3, 12],
  2: [3, 1, 2],
  11: [3, 12, 11],
  13: [3, 12, 13],
  5: [3, 4, 5],
  10: [3, 12, 11, 10],
  14: [3, 12, 11, 14],
  24: [3, 12, 13, 24],
  6: [3, 4, 5, 6],
  9: [3, 4, 5, 9],
  15: [3, 12, 11, 10, 15],
  16: [3, 12, 11, 10, 16],
  17: [3, 12, 11, 10, 17],
  8: [3, 4, 5, 9, 8],
  18: [3, 12, 11, 10, 16, 18],
  19: [3, 12, 11, 10, 15, 19],
  22: [3, 12, 11, 10, 15, 22],
  21: [3, 12, 13, 24, 21],
  23: [3, 12, 13, 24, 23],
  7: [3, 4, 5, 9, 8, 7],
  20: [3, 12, 11, 10, 15, 19, 20]},
 4: {4: [4],
  3: [4, 3],
  5: [4, 5],
  11: [4, 11],
  6: [4, 5, 6],
  9: [4, 5, 9],
  10: [4, 11, 10],
  12: [4, 11, 12],
  14: [4, 11, 14],
  1: [4, 3, 1],
  8: [4, 5, 9, 8],
  15: [4, 11, 10, 15],
  16: [4, 11, 10, 16],
  17: [4, 11, 10, 17],
  13: [4, 11, 12, 13],
  2: [4, 5, 6, 2],
  18: [4, 11, 10, 16, 18],
  19: [4, 11, 10, 15, 19],
  22: [4, 11, 10, 15, 22],
  7: [4, 5, 9, 8, 7],
  24: [4, 11, 12, 13, 24],
  20: [4, 11, 10, 15, 19, 20],
  23: [4, 11, 14, 23],
  21: [4, 11, 10, 15, 22, 21]},
 5: {5: [5],
  4: [5, 4],
  6: [5, 6],
  9: [5, 9],
  8: [5, 9, 8],
  10: [5, 9, 10],
  3: [5, 4, 3],
  11: [5, 4, 11],
  2: [5, 6, 2],
  15: [5, 9, 10, 15],
  16: [5, 9, 10, 16],
  17: [5, 9, 10, 17],
  7: [5, 9, 8, 7],
  12: [5, 4, 11, 12],
  14: [5, 4, 11, 14],
  18: [5, 9, 10, 16, 18],
  19: [5, 9, 10, 15, 19],
  1: [5, 4, 3, 1],
  22: [5, 9, 10, 15, 22],
  13: [5, 4, 11, 12, 13],
  20: [5, 9, 10, 15, 19, 20],
  21: [5, 9, 10, 15, 22, 21],
  23: [5, 9, 10, 15, 22, 23],
  24: [5, 9, 10, 15, 22, 23, 24]},
 6: {6: [6],
  2: [6, 2],
  5: [6, 5],
  8: [6, 8],
  4: [6, 5, 4],
  9: [6, 5, 9],
  1: [6, 2, 1],
  7: [6, 8, 7],
  16: [6, 8, 16],
  10: [6, 5, 9, 10],
  3: [6, 5, 4, 3],
  11: [6, 5, 4, 11],
  18: [6, 8, 7, 18],
  15: [6, 5, 9, 10, 15],
  17: [6, 5, 9, 10, 17],
  12: [6, 5, 4, 11, 12],
  14: [6, 5, 4, 11, 14],
  20: [6, 8, 7, 18, 20],
  19: [6, 5, 9, 10, 15, 19],
  22: [6, 5, 9, 10, 15, 22],
  13: [6, 5, 4, 11, 12, 13],
  21: [6, 5, 9, 10, 15, 22, 21],
  23: [6, 5, 9, 10, 15, 22, 23],
  24: [6, 5, 9, 10, 15, 22, 23, 24]},
 7: {7: [7],
  8: [7, 8],
  18: [7, 18],
  6: [7, 8, 6],
  9: [7, 8, 9],
  16: [7, 8, 16],
  20: [7, 18, 20],
  5: [7, 8, 9, 5],
  10: [7, 8, 16, 10],
  17: [7, 8, 16, 10, 17],
  2: [7, 8, 6, 2],
  4: [7, 8, 9, 5, 4],
  11: [7, 8, 16, 10, 11],
  15: [7, 8, 16, 10, 15],
  19: [7, 18, 20, 19],
  21: [7, 18, 20, 21],
  22: [7, 18, 20, 22],
  12: [7, 8, 16, 10, 11, 12],
  14: [7, 18, 20, 22, 23, 14],
  3: [7, 8, 9, 5, 4, 3],
  1: [7, 8, 6, 2, 1],
  23: [7, 18, 20, 22, 23],
  13: [7, 8, 16, 10, 11, 12, 13],
  24: [7, 18, 20, 22, 23, 24]},
 8: {8: [8],
  6: [8, 6],
  7: [8, 7],
  9: [8, 9],
  16: [8, 16],
  18: [8, 7, 18],
  5: [8, 9, 5],
  10: [8, 16, 10],
  17: [8, 16, 10, 17],
  2: [8, 6, 2],
  20: [8, 7, 18, 20],
  4: [8, 9, 5, 4],
  11: [8, 16, 10, 11],
  15: [8, 16, 10, 15],
  12: [8, 16, 10, 11, 12],
  14: [8, 16, 10, 11, 14],
  19: [8, 16, 10, 15, 19],
  22: [8, 16, 10, 15, 22],
  3: [8, 9, 5, 4, 3],
  1: [8, 6, 2, 1],
  21: [8, 7, 18, 20, 21],
  13: [8, 16, 10, 11, 12, 13],
  23: [8, 16, 10, 15, 22, 23],
  24: [8, 16, 10, 15, 22, 23, 24]},
 9: {9: [9],
  5: [9, 5],
  8: [9, 8],
  10: [9, 10],
  4: [9, 5, 4],
  6: [9, 5, 6],
  11: [9, 10, 11],
  15: [9, 10, 15],
  16: [9, 10, 16],
  17: [9, 10, 17],
  7: [9, 8, 7],
  3: [9, 5, 4, 3],
  2: [9, 5, 6, 2],
  12: [9, 10, 11, 12],
  14: [9, 10, 11, 14],
  18: [9, 10, 16, 18],
  19: [9, 10, 15, 19],
  22: [9, 10, 15, 22],
  13: [9, 10, 11, 12, 13],
  20: [9, 10, 15, 19, 20],
  1: [9, 5, 4, 3, 1],
  21: [9, 10, 15, 22, 21],
  23: [9, 10, 15, 22, 23],
  24: [9, 10, 15, 22, 23, 24]},
 10: {10: [10],
  9: [10, 9],
  11: [10, 11],
  15: [10, 15],
  16: [10, 16],
  17: [10, 17],
  4: [10, 11, 4],
  12: [10, 11, 12],
  14: [10, 11, 14],
  8: [10, 16, 8],
  18: [10, 16, 18],
  19: [10, 15, 19],
  22: [10, 15, 22],
  5: [10, 9, 5],
  3: [10, 11, 12, 3],
  13: [10, 11, 12, 13],
  7: [10, 16, 8, 7],
  20: [10, 15, 19, 20],
  6: [10, 9, 5, 6],
  21: [10, 15, 22, 21],
  23: [10, 15, 22, 23],
  1: [10, 11, 12, 3, 1],
  24: [10, 15, 22, 23, 24],
  2: [10, 9, 5, 6, 2]},
 11: {11: [11],
  4: [11, 4],
  10: [11, 10],
  12: [11, 12],
  14: [11, 14],
  9: [11, 10, 9],
  15: [11, 10, 15],
  16: [11, 10, 16],
  17: [11, 10, 17],
  3: [11, 12, 3],
  13: [11, 12, 13],
  5: [11, 4, 5],
  8: [11, 10, 16, 8],
  18: [11, 10, 16, 18],
  19: [11, 10, 15, 19],
  22: [11, 10, 15, 22],
  1: [11, 12, 3, 1],
  24: [11, 12, 13, 24],
  6: [11, 4, 5, 6],
  7: [11, 10, 16, 8, 7],
  20: [11, 10, 15, 19, 20],
  23: [11, 14, 23],
  21: [11, 10, 15, 22, 21],
  2: [11, 12, 3, 1, 2]},
 12: {12: [12],
  3: [12, 3],
  11: [12, 11],
  13: [12, 13],
  4: [12, 11, 4],
  10: [12, 11, 10],
  14: [12, 11, 14],
  1: [12, 3, 1],
  24: [12, 13, 24],
  9: [12, 11, 10, 9],
  15: [12, 11, 10, 15],
  16: [12, 11, 10, 16],
  17: [12, 11, 10, 17],
  5: [12, 11, 4, 5],
  8: [12, 11, 10, 16, 8],
  18: [12, 11, 10, 16, 18],
  19: [12, 11, 10, 15, 19],
  2: [12, 3, 1, 2],
  22: [12, 11, 10, 15, 22],
  21: [12, 13, 24, 21],
  23: [12, 13, 24, 23],
  6: [12, 11, 4, 5, 6],
  7: [12, 11, 10, 16, 8, 7],
  20: [12, 11, 10, 15, 19, 20]},
 13: {13: [13],
  12: [13, 12],
  24: [13, 24],
  3: [13, 12, 3],
  11: [13, 12, 11],
  21: [13, 24, 21],
  23: [13, 24, 23],
  4: [13, 12, 11, 4],
  10: [13, 12, 11, 10],
  14: [13, 24, 23, 14],
  22: [13, 24, 23, 22],
  1: [13, 12, 3, 1],
  9: [13, 12, 11, 10, 9],
  15: [13, 12, 11, 10, 15],
  16: [13, 12, 11, 10, 16],
  17: [13, 12, 11, 10, 17],
  20: [13, 24, 23, 22, 20],
  5: [13, 12, 11, 4, 5],
  8: [13, 12, 11, 10, 16, 8],
  18: [13, 12, 11, 10, 16, 18],
  19: [13, 12, 11, 10, 15, 19],
  2: [13, 12, 3, 1, 2],
  6: [13, 12, 11, 4, 5, 6],
  7: [13, 12, 11, 10, 16, 8, 7]},
 14: {14: [14],
  11: [14, 11],
  15: [14, 15],
  23: [14, 23],
  22: [14, 23, 22],
  24: [14, 23, 24],
  20: [14, 23, 22, 20],
  21: [14, 23, 22, 21],
  13: [14, 23, 24, 13],
  4: [14, 11, 4],
  10: [14, 11, 10],
  12: [14, 11, 12],
  19: [14, 15, 19],
  18: [14, 23, 22, 20, 18],
  9: [14, 11, 10, 9],
  16: [14, 11, 10, 16],
  17: [14, 11, 10, 17],
  3: [14, 11, 12, 3],
  5: [14, 11, 4, 5],
  8: [14, 11, 10, 16, 8],
  7: [14, 23, 22, 20, 18, 7],
  1: [14, 11, 12, 3, 1],
  6: [14, 11, 4, 5, 6],
  2: [14, 11, 12, 3, 1, 2]},
 15: {15: [15],
  10: [15, 10],
  14: [15, 14],
  19: [15, 19],
  22: [15, 22],
  9: [15, 10, 9],
  11: [15, 10, 11],
  16: [15, 10, 16],
  17: [15, 10, 17],
  20: [15, 19, 20],
  21: [15, 22, 21],
  23: [15, 22, 23],
  4: [15, 10, 11, 4],
  12: [15, 10, 11, 12],
  8: [15, 10, 16, 8],
  18: [15, 10, 16, 18],
  5: [15, 10, 9, 5],
  24: [15, 22, 23, 24],
  3: [15, 10, 11, 12, 3],
  13: [15, 10, 11, 12, 13],
  7: [15, 10, 16, 8, 7],
  6: [15, 10, 9, 5, 6],
  1: [15, 10, 11, 12, 3, 1],
  2: [15, 10, 9, 5, 6, 2]},
 16: {16: [16],
  8: [16, 8],
  10: [16, 10],
  17: [16, 10, 17],
  18: [16, 18],
  9: [16, 10, 9],
  11: [16, 10, 11],
  15: [16, 10, 15],
  7: [16, 8, 7],
  20: [16, 18, 20],
  4: [16, 10, 11, 4],
  12: [16, 10, 11, 12],
  14: [16, 10, 11, 14],
  19: [16, 10, 15, 19],
  6: [16, 8, 6],
  22: [16, 10, 15, 22],
  5: [16, 10, 9, 5],
  3: [16, 10, 11, 12, 3],
  13: [16, 10, 11, 12, 13],
  21: [16, 10, 15, 22, 21],
  23: [16, 10, 15, 22, 23],
  2: [16, 8, 6, 2],
  1: [16, 10, 11, 12, 3, 1],
  24: [16, 10, 15, 22, 23, 24]},
 17: {17: [17],
  10: [17, 10],
  16: [17, 10, 16],
  19: [17, 19],
  9: [17, 10, 9],
  11: [17, 10, 11],
  15: [17, 10, 15],
  4: [17, 10, 11, 4],
  12: [17, 10, 11, 12],
  14: [17, 10, 11, 14],
  8: [17, 10, 16, 8],
  18: [17, 10, 16, 18],
  22: [17, 10, 15, 22],
  5: [17, 10, 9, 5],
  3: [17, 10, 11, 12, 3],
  13: [17, 10, 11, 12, 13],
  20: [17, 19, 20],
  7: [17, 10, 16, 8, 7],
  6: [17, 10, 9, 5, 6],
  21: [17, 10, 15, 22, 21],
  23: [17, 10, 15, 22, 23],
  1: [17, 10, 11, 12, 3, 1],
  24: [17, 10, 15, 22, 23, 24],
  2: [17, 10, 9, 5, 6, 2]},
 18: {18: [18],
  7: [18, 7],
  16: [18, 16],
  20: [18, 20],
  8: [18, 7, 8],
  10: [18, 16, 10],
  17: [18, 16, 10, 17],
  19: [18, 20, 19],
  21: [18, 20, 21],
  22: [18, 20, 22],
  6: [18, 7, 8, 6],
  9: [18, 16, 10, 9],
  11: [18, 16, 10, 11],
  15: [18, 16, 10, 15],
  4: [18, 16, 10, 11, 4],
  12: [18, 16, 10, 11, 12],
  14: [18, 20, 22, 23, 14],
  23: [18, 20, 22, 23],
  5: [18, 16, 10, 9, 5],
  3: [18, 16, 10, 11, 12, 3],
  13: [18, 16, 10, 11, 12, 13],
  24: [18, 20, 22, 23, 24],
  2: [18, 7, 8, 6, 2],
  1: [18, 16, 10, 11, 12, 3, 1]},
 19: {19: [19],
  15: [19, 15],
  17: [19, 17],
  20: [19, 20],
  10: [19, 15, 10],
  14: [19, 15, 14],
  22: [19, 15, 22],
  18: [19, 20, 18],
  21: [19, 20, 21],
  9: [19, 15, 10, 9],
  11: [19, 15, 10, 11],
  16: [19, 15, 10, 16],
  23: [19, 15, 22, 23],
  4: [19, 15, 10, 11, 4],
  12: [19, 15, 10, 11, 12],
  8: [19, 15, 10, 16, 8],
  5: [19, 15, 10, 9, 5],
  7: [19, 20, 18, 7],
  24: [19, 15, 22, 23, 24],
  3: [19, 15, 10, 11, 12, 3],
  13: [19, 15, 10, 11, 12, 13],
  6: [19, 15, 10, 9, 5, 6],
  1: [19, 15, 10, 11, 12, 3, 1],
  2: [19, 15, 10, 9, 5, 6, 2]},
 20: {20: [20],
  18: [20, 18],
  19: [20, 19],
  21: [20, 21],
  22: [20, 22],
  15: [20, 19, 15],
  23: [20, 22, 23],
  17: [20, 19, 17],
  7: [20, 18, 7],
  16: [20, 18, 16],
  24: [20, 22, 23, 24],
  14: [20, 22, 23, 14],
  10: [20, 19, 15, 10],
  8: [20, 18, 7, 8],
  11: [20, 19, 15, 10, 11],
  13: [20, 22, 23, 24, 13],
  9: [20, 19, 15, 10, 9],
  6: [20, 18, 7, 8, 6],
  4: [20, 19, 15, 10, 11, 4],
  12: [20, 19, 15, 10, 11, 12],
  5: [20, 19, 15, 10, 9, 5],
  3: [20, 19, 15, 10, 11, 12, 3],
  2: [20, 18, 7, 8, 6, 2],
  1: [20, 19, 15, 10, 11, 12, 3, 1]},
 21: {21: [21],
  20: [21, 20],
  22: [21, 22],
  24: [21, 24],
  15: [21, 22, 15],
  23: [21, 22, 23],
  18: [21, 20, 18],
  19: [21, 20, 19],
  13: [21, 24, 13],
  14: [21, 22, 23, 14],
  10: [21, 22, 15, 10],
  11: [21, 22, 15, 10, 11],
  17: [21, 22, 15, 10, 17],
  12: [21, 24, 13, 12],
  7: [21, 20, 18, 7],
  16: [21, 22, 15, 10, 16],
  9: [21, 22, 15, 10, 9],
  4: [21, 22, 15, 10, 11, 4],
  8: [21, 20, 18, 7, 8],
  3: [21, 24, 13, 12, 3],
  5: [21, 22, 15, 10, 9, 5],
  6: [21, 22, 15, 10, 9, 5, 6],
  1: [21, 24, 13, 12, 3, 1],
  2: [21, 22, 15, 10, 9, 5, 6, 2]},
 22: {22: [22],
  15: [22, 15],
  20: [22, 20],
  21: [22, 21],
  23: [22, 23],
  14: [22, 23, 14],
  24: [22, 23, 24],
  18: [22, 20, 18],
  19: [22, 15, 19],
  10: [22, 15, 10],
  11: [22, 15, 10, 11],
  13: [22, 23, 24, 13],
  9: [22, 15, 10, 9],
  16: [22, 15, 10, 16],
  17: [22, 15, 10, 17],
  7: [22, 20, 18, 7],
  4: [22, 15, 10, 11, 4],
  12: [22, 15, 10, 11, 12],
  8: [22, 15, 10, 16, 8],
  5: [22, 15, 10, 9, 5],
  3: [22, 15, 10, 11, 12, 3],
  6: [22, 15, 10, 9, 5, 6],
  1: [22, 15, 10, 11, 12, 3, 1],
  2: [22, 15, 10, 9, 5, 6, 2]},
 23: {23: [23],
  14: [23, 14],
  22: [23, 22],
  24: [23, 24],
  11: [23, 14, 11],
  15: [23, 22, 15],
  20: [23, 22, 20],
  21: [23, 22, 21],
  13: [23, 24, 13],
  18: [23, 22, 20, 18],
  19: [23, 22, 15, 19],
  10: [23, 22, 15, 10],
  12: [23, 24, 13, 12],
  9: [23, 22, 15, 10, 9],
  16: [23, 22, 15, 10, 16],
  17: [23, 22, 15, 10, 17],
  4: [23, 14, 11, 4],
  7: [23, 22, 20, 18, 7],
  3: [23, 24, 13, 12, 3],
  8: [23, 22, 15, 10, 16, 8],
  5: [23, 22, 15, 10, 9, 5],
  1: [23, 24, 13, 12, 3, 1],
  6: [23, 22, 15, 10, 9, 5, 6],
  2: [23, 24, 13, 12, 3, 1, 2]},
 24: {24: [24],
  13: [24, 13],
  21: [24, 21],
  23: [24, 23],
  14: [24, 23, 14],
  22: [24, 23, 22],
  12: [24, 13, 12],
  20: [24, 23, 22, 20],
  11: [24, 13, 12, 11],
  15: [24, 23, 22, 15],
  3: [24, 13, 12, 3],
  18: [24, 23, 22, 20, 18],
  19: [24, 23, 22, 15, 19],
  10: [24, 23, 22, 15, 10],
  4: [24, 13, 12, 11, 4],
  1: [24, 13, 12, 3, 1],
  9: [24, 23, 22, 15, 10, 9],
  16: [24, 23, 22, 15, 10, 16],
  17: [24, 23, 22, 15, 10, 17],
  7: [24, 23, 22, 20, 18, 7],
  8: [24, 23, 22, 15, 10, 16, 8],
  5: [24, 23, 22, 15, 10, 9, 5],
  2: [24, 13, 12, 3, 1, 2],
  6: [24, 23, 22, 15, 10, 9, 5, 6]}}

As we can see from the above, the all_pairs_dijkstra_path function returns a nested dictionary (dict-of-dicts), that contains the sequence of shortest paths between any two nodes in the network.

An important detail in the above is that we had to use the dict funtion ahead of all_pairs_dijkstra_path. This is because by default, the ltter function will return a "generator" object, which produces specific paths between node pairs only when requested. The dict ensures that all the paths are calculated and saved into a dictionary, in our case all_paths.

WARNING: The above operation is likely going to take a lot of time in a very large network.

Having calculated all paths in a single go and stored them into a nested dictionary, we can obtain our shortest paths as follows:

In [27]:
all_paths[24][10]
Out[27]:
[24, 23, 22, 15, 10]

And if we wanted to "flatten" the dictionary and obtain all individual paths, we can use the following:

In [28]:
path_list = []      #initialises empty list of paths

for i in all_paths:
    for j in all_paths[i]:
        path_list.append(all_paths[i][j])

len(path_list)
Out[28]:
576

If we look closer at a random path in that set, we can notice that it is provided to us as a sequence of nodes.

In [29]:
sample_path=path_list[10]
sample_path
Out[29]:
[1, 3, 12, 11, 14]

Using the same command that we used in our visualisation function, we can convert this into a list of links (node pairs)

In [30]:
edges_path = list(zip(sample_path,sample_path[1:]))
edges_path
Out[30]:
[(1, 3), (3, 12), (12, 11), (11, 14)]

As we saw before, for a list of all edges in the network, we can use the edges() function in our graph object:

In [31]:
all_edges = list(G.edges())
all_edges
Out[31]:
[(1, 2),
 (1, 3),
 (2, 6),
 (3, 4),
 (3, 12),
 (4, 5),
 (4, 11),
 (5, 6),
 (5, 9),
 (6, 8),
 (7, 8),
 (7, 18),
 (8, 9),
 (8, 16),
 (9, 10),
 (10, 11),
 (10, 15),
 (10, 16),
 (10, 17),
 (11, 12),
 (11, 14),
 (12, 13),
 (13, 24),
 (14, 15),
 (14, 23),
 (15, 19),
 (15, 22),
 (16, 17),
 (16, 18),
 (17, 19),
 (18, 20),
 (19, 20),
 (20, 21),
 (20, 22),
 (21, 22),
 (21, 24),
 (22, 23),
 (23, 24)]

Now, let's assume that we want to calculate the number of shortest paths that contain each link.

In the first instance, we would have to create a dictionary where we will store our path counts, agains our list of nodes, which are used as keys. The counts will be initially set to zero:

In [32]:
path_counts = {}  # Initializes an empty dictionary
In [33]:
for i in all_edges:
    path_counts[i] = 0

path_counts
Out[33]:
{(1, 2): 0,
 (1, 3): 0,
 (2, 6): 0,
 (3, 4): 0,
 (3, 12): 0,
 (4, 5): 0,
 (4, 11): 0,
 (5, 6): 0,
 (5, 9): 0,
 (6, 8): 0,
 (7, 8): 0,
 (7, 18): 0,
 (8, 9): 0,
 (8, 16): 0,
 (9, 10): 0,
 (10, 11): 0,
 (10, 15): 0,
 (10, 16): 0,
 (10, 17): 0,
 (11, 12): 0,
 (11, 14): 0,
 (12, 13): 0,
 (13, 24): 0,
 (14, 15): 0,
 (14, 23): 0,
 (15, 19): 0,
 (15, 22): 0,
 (16, 17): 0,
 (16, 18): 0,
 (17, 19): 0,
 (18, 20): 0,
 (19, 20): 0,
 (20, 21): 0,
 (20, 22): 0,
 (21, 22): 0,
 (21, 24): 0,
 (22, 23): 0,
 (23, 24): 0}

In our next step, we would go through our list of paths, convert each of them into a sequence of edges, and then keep track of how many times each of them is encountered:

In [34]:
for path in path_list:                        # go through each path in our list of paths
    edges_sequence = list(zip(path,path[1:])) # convert the sequence of nodes to a sequence of edges
    
    for edge in edges_sequence:               # now go through each edge in our sequence of edges
        path_counts[edge] += 1                # increment our edge incidence counter by one

---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
Input In [34], in <cell line: 1>()
      2 edges_sequence = list(zip(path,path[1:])) # convert the sequence of nodes to a sequence of edges
      4 for edge in edges_sequence:               # now go through each edge in our sequence of edges
----> 5     path_counts[edge] += 1

KeyError: (12, 11)

It was a good approach in theory, but we encountered the same problem as before! Because our graph is bidirectional, an edge can be traversed in either direction. We can see that the loop above wanted to increment our counter for edge (12, 11), but such an key could not be found in our dictionary.

It did however contain an edge (11, 12). We will use a work-around: before incrementing the value in the dictionary, we will be checking whether the edge exists as a key. If it does not, we will assume that the reverse edge exists, and we will be incrementing that value instead.

Note: This issue will not have occured in a directed graph.

In [35]:
for path in path_list:                        # go through each path in our list of paths
    edges_sequence = list(zip(path,path[1:])) # convert the sequence of nodes to a sequence of edges
    
    for edge in edges_sequence:               # now go through each edge in our sequence of edges
        i,j = edge
        
        if (i,j) in path_counts.keys():
            path_counts[(i,j)] += 1                # increment our edge incidence counter by one
        else:
            path_counts[(j,i)] += 1                # increment our edge incidence counter by one

path_counts
Out[35]:
{(1, 2): 24,
 (1, 3): 56,
 (2, 6): 37,
 (3, 4): 19,
 (3, 12): 74,
 (4, 5): 42,
 (4, 11): 46,
 (5, 6): 50,
 (5, 9): 74,
 (6, 8): 24,
 (7, 8): 44,
 (7, 18): 30,
 (8, 9): 16,
 (8, 16): 42,
 (9, 10): 80,
 (10, 11): 124,
 (10, 15): 146,
 (10, 16): 90,
 (10, 17): 42,
 (11, 12): 106,
 (11, 14): 30,
 (12, 13): 60,
 (13, 24): 38,
 (14, 15): 4,
 (14, 23): 20,
 (15, 19): 54,
 (15, 22): 86,
 (16, 17): 0,
 (16, 18): 26,
 (17, 19): 4,
 (18, 20): 38,
 (19, 20): 28,
 (20, 21): 10,
 (20, 22): 26,
 (21, 22): 26,
 (21, 24): 10,
 (22, 23): 68,
 (23, 24): 46}

That looks like a very interesting set of counts. If we wanted to sort the dictionary by value, we could use the following:

In [36]:
import operator


sorted_counts = dict( sorted(path_counts.items(), key=operator.itemgetter(1),reverse=True))
sorted_counts
Out[36]:
{(10, 15): 146,
 (10, 11): 124,
 (11, 12): 106,
 (10, 16): 90,
 (15, 22): 86,
 (9, 10): 80,
 (3, 12): 74,
 (5, 9): 74,
 (22, 23): 68,
 (12, 13): 60,
 (1, 3): 56,
 (15, 19): 54,
 (5, 6): 50,
 (4, 11): 46,
 (23, 24): 46,
 (7, 8): 44,
 (4, 5): 42,
 (8, 16): 42,
 (10, 17): 42,
 (13, 24): 38,
 (18, 20): 38,
 (2, 6): 37,
 (7, 18): 30,
 (11, 14): 30,
 (19, 20): 28,
 (16, 18): 26,
 (20, 22): 26,
 (21, 22): 26,
 (1, 2): 24,
 (6, 8): 24,
 (14, 23): 20,
 (3, 4): 19,
 (8, 9): 16,
 (20, 21): 10,
 (21, 24): 10,
 (14, 15): 4,
 (17, 19): 4,
 (16, 17): 0}