# Converting a city street map into a graph (2D array) for graph traversal/navigation

I'm giving a lecture on graph theory (specifically graph traversals) and I'd like to display my city as a directed graph. I'd like output to be a 2D array in python so I can show how graph traversal algorithms work on it. Is there any software or simple python script that can do this? I imagine I'd be using google maps to get the input street map data, but I'm happy to use other sources.

Example:

If a section of the city roads looked like this:

Where the nodes are street intersections and the arrows show which way you can drive from node to node (i.e., a one way or two way street).

Then the output I want is the following 2D array:

``````[[0, 0, 0, 1, 0],
[0, 0, 1, 1, 0],
[0, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[1, 0, 0, 1, 0]]
``````

Where a 0 at element (A,B) indicates you can't drive directly from node A to node B, and a 1 means you can.

There are quite a few elements here you will need in your data - In short, your problem isn't going to be the writing of the python script, but getting a suitable datasource.

Road Data) Are you going to be able to get vector road data out of Google Maps? Id advise getting a road network dataset from a free online repository or maybe try open street maps. https://gisgeography.com/geometric-networks/

Directional attribution) Assuming your dataset doesn't have it, you will need to manually create directional attributes, I doubt the road data will have direction on it, but you never know you might get lucky.

Topology) To do this, you will need to create network topology - ie: tell the datasource lines that where two lines meet, they are joined. This will ensure lines 'snap' to each other. Ensure intersections are joining at the vertexes. If you get your data from OSM or online, it may already be complete here.

Node dataset) You want nodes? Your going to have to create them. At each intersection of the above linework, you will need to create a node record into a table that stores points and give the node value. (you could also potentially dynamically create the nodes on the fly as you trace the network, your nodes would have dynamic ID's though).

Network tracing) Now some software to perform the network trace - Yer you could go away and write this in Python, but the Python libraries will probably require the install of some GIS software which - low and behold - already has network trace tools. So just use them. The network trace will output onto the map and - from memory - give a list of network elements it passes through. (depending upon the software you use). (This may or may not include nodes, depending upon how you did the above).

The network trace is the main bit where you will need to customize in order to output your matrix. It might end up being recursive, so something like (psuedo_code)

``````for i over list_of_nodes
node_trace_output = perform_network_trace(i)
output_matrix.append(node_trace_output)
``````

or something similar.

May I also suggest you post this in the GIS stack exchange.