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.
!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.
import networkx as nx
import pandas as pd
A common convention when importing pandas
is to use the pd
acronym.
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.
links = pd.read_csv('data-sioux-falls/siouxfalls_links.csv')
links
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.
nodes = pd.read_csv('data-sioux-falls/siouxfalls_nodes.csv')
nodes
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.
new_links = list(zip(links['from_node'], links['to_node']))
new_links
[(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:
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:
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.
coords = list(zip(nodes['x'], nodes['y']))
pos = dict(zip(nodes['node'], coords))
pos
{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)}
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
.
nx.dijkstra_path_length(G, source=13, target=7)
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.
Let's visualize the path:
path = nx.dijkstra_path(G, source=13, target=7)
path
[13, 24, 21, 20, 18, 7]
We can now plot it using the same approach that we followed above.
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.
edges_path
[(13, 24), (24, 21), (21, 20), (20, 18), (18, 7)]
Everything appears to be OK here.
edge_colors
['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
.
G.edges()
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)])
edges_path
[(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:
edges_path_reversed = [(y,x) for (x,y) in edges_path]
edges_path_reversed
[(24, 13), (21, 24), (20, 21), (18, 20), (7, 18)]
We now append them to the list:
edges_path = edges_path + edges_path_reversed
edges_path
[(13, 24), (24, 21), (21, 20), (20, 18), (18, 7), (24, 13), (21, 24), (20, 21), (18, 20), (7, 18)]
Let's try again!
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:
G.edges.data("weight")
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:
weights = dict(zip(G.edges,links['length']))
weights
{(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}
nx.set_edge_attributes(G, values = weights, name = 'weight')
G.edges.data("weight")
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.
nx.dijkstra_path_length(G, source=13, target=7)
19
This looks more like it! Let's visualise the shortest path:
path = nx.dijkstra_path(G, source=13, target=7)
path
[13, 12, 11, 10, 16, 8, 7]
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.
What if we wanted to obtain all the shortest paths in our network?
all_paths = dict(nx.all_pairs_dijkstra_path(G))
all_paths
{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:
all_paths[24][10]
[24, 23, 22, 15, 10]
And if we wanted to "flatten" the dictionary and obtain all individual paths, we can use the following:
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)
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.
sample_path=path_list[10]
sample_path
[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)
edges_path = list(zip(sample_path,sample_path[1:]))
edges_path
[(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:
all_edges = list(G.edges())
all_edges
[(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:
path_counts = {} # Initializes an empty dictionary
for i in all_edges:
path_counts[i] = 0
path_counts
{(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:
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.
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
{(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:
import operator
sorted_counts = dict( sorted(path_counts.items(), key=operator.itemgetter(1),reverse=True))
sorted_counts
{(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}