# 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.

```/

- / data /
munich_bicycle_sensors.csv

- / output /

The `munich_bicycle_sensors.csv` includes the following target geocoordinates.

`DETEKTOR_ID,  LATITUDE,    LONGITUDEArnulf,       48.14205,    11.55534Kreuther,     48.12194,    11.62417Olympia,      48.16887,    11.55005Hirsch,       48.14438,    11.51794Margareten,   48.12032,    11.53599Erhardt,      48.13192,    11.58469`

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

`Python 3.10.6pip3 install osmnx==0.16.1 pip3 install geopandas==0.9.0pip3 install scipypip3 install networkxpip3 install plotlypip3 install pandas`

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

`import osimport numpy as npfrom itertools import isliceimport pandas as pdimport osmnx as oximport networkx as nx`

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 OSMNXdef 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():`

Inside the function a 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.

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

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 pathOS_PATH = os.path.dirname(os.path.realpath('__file__'))SENSORS_CSV   = OS_PATH + '/data/munich_bicycle_sensors.csv'# Data Import Pathdf = pd.read_csv(SENSORS_CSV)# Keep only relevant columnsdf = df.loc[:, ("DETEKTOR_ID","LATITUDE", "LONGITUDE")]# Remove missing geocoordinatesdf.dropna(subset=['LATITUDE'], how='all', inplace=True)df.dropna(subset=['LONGITUDE'], how='all', inplace=True)# Remove missing sensor idsdf.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, DISTANCEArnulf,        Arnulf,        0.0Arnulf,        Kreuther,      6360.067999999998Arnulf,        Olympia,       3548.8400000000006Arnulf,        Hirsch,        3364.7529999999997Arnulf,        Margareten,    3658.5860000000002Arnulf,        Erhardt,       2916.509Kreuther,      Arnulf,        6403.099000000001Kreuther,      Kreuther,      0.0Kreuther,      Olympia,       9011.475000000002Kreuther,      Hirsch,        9707.515000000003Kreuther,      Margareten,    8099.6449999999995Kreuther,      Erhardt,       3523.4769999999994Olympia,       Arnulf,        3542.883Olympia,       Kreuther,      9088.311999999993Olympia,       Olympia,       0.0Olympia,       Hirsch,        4825.775000000002Olympia,       Margareten,    7074.653000000002Olympia,       Erhardt,       5913.148000000002Hirsch,        Arnulf,        3302.0229999999992Hirsch,        Kreuther,      9655.762999999995Hirsch,        Olympia,       4833.914000000002Hirsch,        Hirsch,        0.0Hirsch,        Margareten,    4234.665Hirsch,        Erhardt,       6212.2040000000015Margareten,    Arnulf,        3646.659999999999Margareten,    Kreuther,      8178.820999999996Margareten,    Olympia,       6458.455999999998Margareten,    Hirsch,        4202.3730000000005Margareten,    Margareten,    0.0Margareten,    Erhardt,       4780.81Erhardt,       Arnulf,        2913.113999999999Erhardt,       Kreuther,      3536.422Erhardt,       Olympia,       5837.165999999999Erhardt,       Hirsch,        6217.530000000001Erhardt,       Margareten,    4748.426999999998Erhardt,       Erhardt,       0.0`