# Creating an Adjacency Matrix Using the Dijkstra Algorithm for Graph Convolutional Networks GCNs

Alright so you have a list of geocoordinates (for example maybe street sensors) and you want to create an adjacency matrix to feed into your PyTorch or Tensorflow GCN model such as the A3T-GCN. This tutorial uses OSMnx to measure the distance of optimal paths between each of the geocoordinates for each geocoordinate. The distances are saved to a CSV file as an adjacency matrix. The distance matrix in this tutorial is very basic, but you could go even further by capturing more spatial information such as capturing the shape of the paths between the geocoordinates. The adjacency matrix is used to structure the unstructured graph data.

A brief file structure overview of the repository is provided. The `adjacency_matrix.py`

is in the root directory. The `data`

folder houses a list of geocoordinates in a csv file. For this example six bicycle sensors where selected from the City of Munich’s opendata portal. For a GCN of course it is better for a graph to be larger than 50 sensors. The graph distances are saved as a matrix in the `output`

folder.

`/`

adjacency_matrix.py

- / data /

munich_bicycle_sensors.csv

- / output /

bicycle_adjacency_matrix.csv

The `munich_bicycle_sensors.csv`

includes the following target geocoordinates.

`DETEKTOR_ID, LATITUDE, LONGITUDE`

Arnulf, 48.14205, 11.55534

Kreuther, 48.12194, 11.62417

Olympia, 48.16887, 11.55005

Hirsch, 48.14438, 11.51794

Margareten, 48.12032, 11.53599

Erhardt, 48.13192, 11.58469

Before jumping into the code the following requirements and packages are needed to run the code:

`Python 3.10.6`

pip3 install osmnx==0.16.1

pip3 install geopandas==0.9.0

pip3 install scipy

pip3 install networkx

pip3 install plotly

pip3 install pandas

First the packages that were just installed are imported into our file `adjacency_matrix.py`

`import os`

import numpy as np

from itertools import islice

import pandas as pd

import osmnx as ox

import networkx as nx

Then we setup the OSMNX cache configuration is an optional method to store maps from OSM. This is especially resourceful for storing larger maps as it requires fewer requests to the api. For plotting a handful of paths this really does not impact processing time significantly.

`# Using the cache accelerates processing for a large map`

ox.config(log_console=True, use_cache=True)

Next we can set the location of our map to confine its perimeter.

`place = 'Munich, Bavaria, Germany'`

The mode of transport is set to bike. Drive captures the road network used by automobiles. Bike capture the path network used by bicycles. Walk capture the walkway network used by pedestrians. Finding an optimal walkway is usually too resource intensive when processing due to the fact that their are many more nodes on the walking graph

`# 'drive', 'bike', 'walk'`

mode = 'bike'

Finally the graph can be requested and downloaded from the OSMnx api. The graph perimeters are set in the parameters and passed to the api request. The graph `mode`

and `place`

are also passed along. ONLY DOWNLOAD THE GRAPH ONCE TO AVOID REQUEST LIMITS!!

`graph = ox.graph_from_place(place, network_type = mode)`

Next a function is created which saves our optimal path distance matrix as the CSV file in our output folder from the list of geocoordinates in our data folder. This function takes our dataframe as a parameter.

`##### Interface to OSMNX`

def generate_adjacency_matrix(df):

To save the distance between every sensor with every other sensor we create an adjacency matrix.

` # Create the adjacency matrix`

matrix = [["DETEKTOR_ID_X, DETEKTOR_ID_Y, DISTANCE"]]

We need to iterate through all the detectors for each detector in our dataframe.

` i=0;`

for detector in islice(df.iterrows(), 0, len(list(df.DETEKTOR_ID))):

j=0;

for each_detector in df.iterrows():

Now that we have requested the graph from OSMnx api we can also request or path. We need the coordinates from the current sensor and the coordinates to the destination sensor. Remember we are inside a double for loop looping through sensor by sensor for each sensor.

` # coordinates from the current sensor`

start_latlng = (float(detector["LATITUDE"]), float(detector["LONGITUDE"]))

# coordinates belonging to the destination sensor

end_latlng = (float(each_detector["LATITUDE"]), float(each_detector["LONGITUDE"]))

Then we find the nearest nodes to the coordinates on the graph we requested from OSMnx.

` # find the nearest node to the current sensor`

orig_node = ox.get_nearest_node(graph, start_latlng)

# find the nearest node to the destination sensor

dest_node = ox.get_nearest_node(graph, end_latlng)

Using the Dijkstra method we find the shortest distance between the two sensors or points. Another method is the bellman-ford algorithm.

` #find the shortest path method dijkstra or bellman-ford`

shortest_route_distance = nx.shortest_path_length(graph, orig_node,dest_node, weight="length", method="dijkstra")

Finally we then append the distance to the adjacency matrix we created outside of the for loop. This would be a good place to console log the matrix to keep track of progress.

` matrix.append([str(detector["DETEKTOR_ID"]) + "," + str(each_detector["DETEKTOR_ID"]) + "," + str(float(shortest_route_distance))])`

After the distances between all the sensors have been found and added to the adjacency matrix using the nested for loop, the matrix is then converted into a numpy array.

` matrix = np.array(matrix)`

matrix = np.asarray(matrix)

Finally the matrix is saved as a csv in the `output`

folder as `bicycle_adjacency_matrix.csv`

` # Save the dijkstra rad sensors distance matrix`

np.savetxt(OS_PATH + "output/bicycle_adjacency_matrix.csv", matrix, delimiter=",", fmt='%s')

First in the main part of the script a list of target geocoordinates are fetched from the `data`

folder in the `munich_bicycle_sensors.csv`

file and loaded into python using pandas' dataframe method. The geocoordinates are then formatted as geocoordinates using geopandas.

`# Data import path`

OS_PATH = os.path.dirname(os.path.realpath('__file__'))

SENSORS_CSV = OS_PATH + '/data/munich_bicycle_sensors.csv'

# Data Import Path

df = pd.read_csv(SENSORS_CSV)

# Keep only relevant columns

df = df.loc[:, ("DETEKTOR_ID","LATITUDE", "LONGITUDE")]

# Remove missing geocoordinates

df.dropna(subset=['LATITUDE'], how='all', inplace=True)

df.dropna(subset=['LONGITUDE'], how='all', inplace=True)

# Remove missing sensor ids

df.dropna(subset=['DETEKTOR_ID'], how='all', inplace=True)

Finally our `generate_adjacency_matrix`

function is called after getting the optimal paths.

`generate_adjacency_matrix(df)`

The result is presented below:

`DETEKTOR_ID_X, DETEKTOR_ID_Y, DISTANCE`

Arnulf, Arnulf, 0.0

Arnulf, Kreuther, 6360.067999999998

Arnulf, Olympia, 3548.8400000000006

Arnulf, Hirsch, 3364.7529999999997

Arnulf, Margareten, 3658.5860000000002

Arnulf, Erhardt, 2916.509

Kreuther, Arnulf, 6403.099000000001

Kreuther, Kreuther, 0.0

Kreuther, Olympia, 9011.475000000002

Kreuther, Hirsch, 9707.515000000003

Kreuther, Margareten, 8099.6449999999995

Kreuther, Erhardt, 3523.4769999999994

Olympia, Arnulf, 3542.883

Olympia, Kreuther, 9088.311999999993

Olympia, Olympia, 0.0

Olympia, Hirsch, 4825.775000000002

Olympia, Margareten, 7074.653000000002

Olympia, Erhardt, 5913.148000000002

Hirsch, Arnulf, 3302.0229999999992

Hirsch, Kreuther, 9655.762999999995

Hirsch, Olympia, 4833.914000000002

Hirsch, Hirsch, 0.0

Hirsch, Margareten, 4234.665

Hirsch, Erhardt, 6212.2040000000015

Margareten, Arnulf, 3646.659999999999

Margareten, Kreuther, 8178.820999999996

Margareten, Olympia, 6458.455999999998

Margareten, Hirsch, 4202.3730000000005

Margareten, Margareten, 0.0

Margareten, Erhardt, 4780.81

Erhardt, Arnulf, 2913.113999999999

Erhardt, Kreuther, 3536.422

Erhardt, Olympia, 5837.165999999999

Erhardt, Hirsch, 6217.530000000001

Erhardt, Margareten, 4748.426999999998

Erhardt, Erhardt, 0.0

*bicycle_adjacency_matrix.jpg*

A more complex adjacency may capture the entire shape of the paths between the points instead of just the distance. This would increase the accuracy of a GCN model as you capturing more spatial information. This can also be done with OSMnx. I reference how to capture an entire path in an array plotting the Dijkstra paths in my other tutorial.

The OSMnx solution is great for data science if you need static graph data to test an academic GCN model. For a dynamic graph or a software solution it would be better to use a proprietary vendor such as a Google or Apple Maps to calculate your distances with better efficiency.

The GitHub repository can be found here.

The original post can be found here.

Bicycle sensors from the City of Munich Opendata Portal: https://opendata.muenchen.de/dataset/raddauerzaehlstellen-muenchen/resource/211e882d-fadd-468a-bf8a-0014ae65a393?view_id=11a47d6c-0bc1-4bfa-93ea-126089b59c3d