2) Creating a Network, Diagnosis, understanding network structure

Quick Summary

For using the UNA tools, you don’t need to be familiar with how the network is represented in Madina, all you need to know is that you can create a network from geometries, then insert origins and destinations. This code snippet shows all the neccessary steps needed before using any UNA tool:

• Create a Zonal object

• Load your network geometry layer (strewts, sidewlaks, ..) and load your origin and destination layers.

• create topological network from geometry

• insert origins and destinations to topological nework.

• create the graph object.

This section proivdes knowledge about how the network, origins and destinations are handled and represented internally. This knowledge is helpful for advance uses, but not necessary for being able to write analysis workflow. The code snippet below provide all needed kmowledge to run analysis tools.

import madina as md
cambridge = md.Zonal()

#Loading sidewalks, buildings and subway geometries.
cambridge.load_layer('sidewalks', 'Cities/Cambridge/Data/sidewalks.geojson')
cambridge.load_layer('buildings', 'Cities/Cambridge/Data/building_entrances.geojson')
cambridge.load_layer('subway', 'Cities/Cambridge/Data/subway.geojson')

# Creating a network, and adding origins and destinations
cambridge.create_street_network(source_layer="sidewalks", node_snapping_tolerance=0.1)
cambridge.insert_node(label='origin', layer_name="subway")
cambridge.insert_node(label='destination', layer_name="buildings")

# Creating graphs
cambridge.create_graph()

Overview of Network representation in Madina.

Madina provide functionality to convert a geometric representation of a network into a topographical networks that enables network operations like route finding. This is useful when an analysis requires doing network operation on a veriety of urban networks like streets, sidewalks or bike paths.

Once a network is created, Madina allows the insertion of two types of purpose speciic nodes: origins and destinations. In the four step transportation model, origin nodes are used for trip generation, while destination nodes are used during trip distribution. We will discuss this in more details when we introduce the Urban Network Analysis (UNA) Tools.

In practice, it is fairly common to enounter cases where the geometric representation of a nework is not suitable for network analysis. This could be a result of how the geometric network is represented. A list of common issues with networks:

• Segments aren’t touching at the end points

• An intersection is improperly represented. for a routable network, an intersection should be represented as meeting of multipe lines to form an intersection. Some data sources might represent an intersection as lines crossing one another, which would visually look like a true intersection, but topologically, it would not enable routing between segments of that intersection.

Let’s start by loading the sidewalks.geojson geometry file:

import madina as md
cambridge = md.Zonal()
cambridge.load_layer('sidewalks', 'Cities/Cambridge/Data/sidewalks.geojson')

To create a topological network of nodes and edges:

cambridge.create_street_network(source_layer="sidewalks")

This would create a network object inside the cambridge Zonal object. This network object would be used to keep track of various data structures needed to represent different parts of the network that would later be used during analysis. Calling cambridge.create_street_network() creates two dataframes inside the network object.

• cambridge.network.nodes: This is a table that contains all network nodes. In Madina, there are currently three types of nodes in a network: street_node, origin and destination. calling cambridge.create_street_network() creates nodes that represent the end points of network geometries. These nodes represent wherer connections could be made in the network.

• cambridge.network.edges: This is a table containing network edges. An edge in graph theory, is a connection between two nodes. Each line in the geometric representation of the network, would correspod to an edge

Take a look at the node table, it contains these columns:

• source_layer: the layer source where this node came from.

• source_id: the source layer id of the geometry this node represent. A street/network node is not uniquly related to a distingt geometry, but origin and destination nodes come from distingt geometries and this column keeps track of the source geometry id.

• type: As of now, there are three types of nodes: street_node, origin, and destination.

• weight: The weigt attribute is more relevant to origin and destination nodes. a reflection of node importnace.

• degree: the degree is calculated for street_nodes and represent the number of street edges that share the same node: the streets or network elements that intersect at this node. The node degree is a very important network diagnistic tool to ensure connectivity as we will see later.

• geometry: the Shapely geometry object. a geometry representation for the node that is used to create visual maps.

cambridge.network.nodes.head(5)

	source_layer	source_id	type	weight	degree	geometry	color
id
0	sidewalks	0	street_node	0.0	1	POINT (-1803.650 258.946)	[125, 125, 125]
1	sidewalks	0	street_node	0.0	1	POINT (-1803.650 161.837)	[125, 125, 125]
2	sidewalks	0	street_node	0.0	1	POINT (-1803.650 178.154)	[125, 125, 125]
3	sidewalks	0	street_node	0.0	1	POINT (-1803.650 237.220)	[125, 125, 125]
4	sidewalks	0	street_node	0.0	1	POINT (-1791.927 111.205)	[125, 125, 125]

Looking inside the netwok edge, it contains the following columns:

• length: The length of the edge geometry.

• weight: The network weight of the edge. This is used to hold the segment weight when using percievedd network distance. The function create_street_network() takes an attribute weight_attribute, a column in the source geometry layer that holds a numerical value of the segment cost (segment weight, segment percieved distance). By default, the geometric length is used as weight.

• parent_street_id: The id in the souce layer of the street segment.

• start: The node id in cambridge.network.nodes where this edge starts.

• end: The node id in cambridge.network.nodes where this edge ends.

• geometry: the Shapely geometry object. a geometry representation for the edge that is used to create visual maps.

cambridge.network.edges.head(5)

	length	weight	parent_street_id	start	end	geometry	color
id
0	53.328770	53.328770	0	31	36	LINESTRING (-1719.114 147.249, -1718.693 124.0...	[125, 125, 125]
1	33.137771	33.137771	1	35	31	LINESTRING (-1705.465 177.057, -1714.466 163.1...	[125, 125, 125]
2	82.471466	82.471466	2	64	88	LINESTRING (-1635.552 240.490, -1555.262 259.331)	[125, 125, 125]
3	20.707448	20.707448	3	60	64	LINESTRING (-1648.164 226.821, -1647.328 234.0...	[125, 125, 125]
4	60.851523	60.851523	4	52	38	LINESTRING (-1662.239 245.651, -1696.978 295.612)	[125, 125, 125]

Visualizing the network would look very similar to visualizing the geometry layer. A major difference is now you can see points for nodes where network elements meet.

cambridge.create_map(
    [
        {'gdf': cambridge.network.edges},
        {'gdf': cambridge.network.nodes},
    ]
)

Network DIagnosis

As mentioned before, many geometric networks might look visually connected, but stil have topological connection issues. One of the best indicator of network connectivity is node degree: how many edges are connected to this node. Visualizing node degrees is helpful in checking connectivity, and ensuring that a visually connected network is actually connected topologically by making sure that the node degree at points of intersection, is equal to the number of edges that are expected to connect at this point.

cambridge.create_map(
    [
        {'gdf': cambridge.network.edges, 'color': [125, 125, 125]},
        {'gdf': cambridge.network.nodes, 'color_by_attribute': 'degree', 'color_method': 'categorical', 'text': 'degree', 'opacity': 0.5},
    ]
)

In particular, it is always useful to inspect degree-1 and degree 2 nodes and make sure they only occure when they are expected:

• Degree 1 nodes: These are nodes in the network that only have one connected edges. This should only happen at real-life dead ends, or at the boundaries of the analysis area where lines tend to be artificially cus-off

• Degree 2 nodes: these represaent a node that connects only two edges. Ideally, if only two edges share a node, these two edges are probably represent a single edge without the need for a node to connect them. Having these 2-degee node increases the number of nodes and edges in the network, without providing any meaningful topological information. There are cases where degree two nodes are needed to represent sharp turns within an edge if the analysis is sensitive to the number of turns, and a turn/curvature of an edge is represented by splitting that edge where the turn occurs. The only disadvantage to having degree-2 node is they reduce the performance of many complex network analysis tools. In smaller applications, these performance issues are negligable and having degree two nodes is not an issue. More importantly, just like degree-1 nodes, degree 2 nodes could show us areas in the network where there should have been a topological connection in an intersection, but geometries of the network were not perfectly touching, or did not have an end point at that intersection for instance.

node_gdf = cambridge.network.nodes
degree_1_nodes = node_gdf[node_gdf['degree'] == 1]
degree_2_nodes = node_gdf[node_gdf['degree'] == 2]

cambridge.create_map(
    [
        {'gdf': cambridge.network.edges, 'color': [125, 125, 125]},
        {'gdf': degree_1_nodes, 'color': [255, 0, 0], 'text': 'degree'},
        {'gdf': degree_2_nodes, 'color': [0, 255, 00], 'text': 'degree'}
    ]
)

We notice in the visualization above that there is many degree-2 nodes that are clearly in three-way and four-way intersections that should have been represented by degree 2, and degree-3 nodes instead. this is a serious issue as trips cannot be routed correctly through these intersections, and the topology needs to be fixed before proceeding with any network analysis. There are multiple ways of fixing these topological issues:

• Manual work: In a GIS or CAD software, make sure that the network geometries touch one another perfectly, and lines are perfectly ‘snapped’ at intercection points. Most of GIS and CAD software packages provide functionalities to ensure that geometries are snapped.

• Automated fixes: There is no perfect automatic fix to topological issues, and manual inspection would likely be needed to ensure network quality. Madina provides some automated basic network fixes that might (or might not) be useful to solve connectivity issues.

The create_street_network function that is used to create the topological network from geometry, proivde a parameter called node_snapping_tolerance. This allows nodes to be formed, even of the geometries were not perfectly touching, by snapping together edges with a node snapping tolerance: A distance (in the same unit as the geometry CRS) where edges are allowed to snap, even if they didn’t perfectly touch, up to that tolerance distance. Settting this parameter is fairly arbitrary depends on the scope. 0.1 meters might be a safe setting for most applications where lines are disconnected for numerical issues (geometries are supposed to touch but the numerical representation of their end points is not perfectly identical due to rounding, transformations, or other numerical issues). Always check the results.

cambridge.create_street_network(source_layer="sidewalks", node_snapping_tolerance=0.1)


## Diagnostics
node_gdf = cambridge.network.nodes
degree_1_nodes = node_gdf[node_gdf['degree'] == 1]
degree_2_nodes = node_gdf[node_gdf['degree'] == 2]

cambridge.create_map(
    [
        {'gdf': cambridge.network.edges, 'color': [125, 125, 125]},
        {'gdf': degree_1_nodes, 'color': [255, 0, 0], 'text': 'degree'},
        {'gdf': degree_2_nodes, 'color': [0, 255, 00], 'text': 'degree'}
    ]
)

In this case, the node_snapping_tolerance, seems to have solved the issue. Degree-1 nodes only happen at the boundaries where lines are artificuially cut off, and there are no degree-2 nodes. Let’s check the degrees for all intersections to ensure everything looks okay:

cambridge.create_map(
    [
        {'gdf': cambridge.network.edges, 'color': [125, 125, 125]},
        {'gdf': cambridge.network.nodes, 'color_by_attribute': 'degree', 'color_method': 'categorical', 'text': 'degree', 'opacity': 0.5},
    ]
)

This looks much better and the topology now seems correct. ## Origins and destinations We now converted the geometric representation of the network, into a routable topological network. For most Urban Network Analysis tools, we need to incorporate origins and destinations. Let’s load two more layers: building entrances and subway station entrances:

cambridge.load_layer('buildings', 'Cities/Cambridge/Data/building_entrances.geojson')
cambridge.load_layer('subway', 'Cities/Cambridge/Data/subway.geojson')

cambridge.create_map(
    [
        {'layer': 'sidewalks', 'color': [125, 125, 125]},
        {'layer': 'subway', 'color': [0, 0, 255]},
        {'layer': 'buildings', 'color': [255, 0, 0]}
    ]
)

Again, these building entrances and subway station entrances are only geometric representations on the map and not part of the network yet. For any analysis that include these origins and destinations, they need to be nodes in the network:

cambridge.insert_node(layer_name="subway", label='origin')
cambridge.insert_node(layer_name="buildings", label='destination')

now subway entrances are added as origin nodes, and building entrances are added as a destination node. This can be seen in the cambridge.network.nodes geodataframe. By defauly, the cambridge.network.nodes are colored blue for origins, and red for destination, grey for network nodes. You could always override there styling options whenever you want.

cambridge.create_map(
    layer_list=[
        {'gdf': cambridge.network.edges},
        {'gdf': cambridge.network.nodes},
    ]
)

Notice how these origins and destinations are snapped to the closest network edge. This snapping is needed to give an origin point or a destination point access to the network. Be aware of this when dealing with spatial data that might be sensitive this behaviour. A centroid of a block polygons for instance might arbitrarly snap to any edge that is closest, which might be less reflective of how this block is usually reached. Be aware of this snapping behaviour when working with data that originates from census blocks for instance.

cambridge.create_map(
    layer_list=[
        {'gdf': cambridge.network.edges},
        {'gdf': cambridge.network.nodes},
        {'layer': 'subway', 'color': [0, 0, 255]},
        {'layer': 'buildings', 'color': [255, 0, 0]},
    ]
)

When origins and destinations are inserted, additional information about how they connect to other network nodes is added. nearest_edge_id is the network id of the edge this node is snapped to and is supposed to split when the network graph is created. edge_start_node, weight_to_start, edge_end_node, weight_to_end are information about the closest street nodes and their network distance. These information are needed for building an effecient graph representation of a network with origins and destinations as we will see later.

cambridge.network.nodes[cambridge.network.nodes['type'].isin(['origin', 'destination'])]

	source_layer	source_id	type	weight	degree	geometry	color	nearest_edge_id	edge_start_node	weight_to_start	edge_end_node	weight_to_end
id
119	subway	0	origin	1.0	0	POINT (-1505.907 257.088)	[86, 5, 255]	146	37	18.602976	2	21.157556
120	subway	1	origin	1.0	0	POINT (-1638.009 133.245)	[86, 5, 255]	131	68	11.284895	67	13.534535
121	buildings	0	destination	1.0	0	POINT (-1796.795 255.409)	[239, 89, 128]	157	78	7.713946	88	10.664130
122	buildings	1	destination	1.0	0	POINT (-1761.756 237.331)	[239, 89, 128]	12	9	18.599356	80	59.176549
123	buildings	2	destination	1.0	0	POINT (-1691.228 227.370)	[239, 89, 128]	5	43	0.886665	20	34.272370
...	...	...	...	...	...	...	...	...	...	...	...	...
234	buildings	113	destination	1.0	0	POINT (-1408.691 239.768)	[239, 89, 128]	96	31	34.598274	91	11.329964
235	buildings	114	destination	1.0	0	POINT (-1437.637 260.648)	[239, 89, 128]	36	31	8.763640	41	26.502313
236	buildings	115	destination	1.0	0	POINT (-1438.507 297.564)	[239, 89, 128]	35	41	16.231263	110	0.000000
237	buildings	116	destination	1.0	0	POINT (-1565.224 270.957)	[239, 89, 128]	155	53	11.075909	66	10.125012
238	buildings	117	destination	1.0	0	POINT (-1528.294 283.475)	[239, 89, 128]	161	35	4.990609	90	36.087832

120 rows × 12 columns

The cambridge.network.nodes, and cambridge.network.edges are still just geodataframes: Tables containing information that represent the nodes and edges of the network, the origins and the destioantion. Before starting any analysis usning UNA, a few NetworkX graphs are created for different representations of the network. There are multiple representations of the network for use in multiple network operations where some representations have performance advantages over others. To finally create these NetworkX graphs:

cambridge.create_graph(light_graph=True, d_graph=True, od_graph=True)

This creates three distingt graphs:

• light_graph: this is a NetworkX object that only contains the street nodes and edges. This is used as a badeline graph in which origins and destinations are added. This graph could be used to access all networkX’s functionalities and algorithms, for instance, the shortest path betweenness centrality for nodes or for edges of the network (streets, sidewalks, etc.)

• d_graph: is a networkX object that contains the network nodes and edges, together with all the destinations inserted at the appropriate network locations. This graph is used internally in many UNA algorithms since the behaviour of each origin is independent of all other origins. By adding one single origin at a time. this graph provide performance enhancemet by providing the minimal information needed for a single origin.

• od_graph: This is a networkX graph that contains all network nodes, origin nodes and destination nodes all placed in their appropriate location oin the network. This graph is not generated by default when calling cambridge.create_graph() without specifying the parameter (od_graph=True). This networkX object enables access to networkX’s algorithms where all oriigns and destinations are part of the network. For instance, in measuring shortest path betweenness in a network, accounting for the presence and locations of origins and destinations.

print("light_graph:\t", cambridge.network.light_graph)
print("d_graph:\t", cambridge.network.d_graph)
print("od_graph:\t", cambridge.network.od_graph)

light_graph:     Graph with 119 nodes and 170 edges
d_graph:         Graph with 237 nodes and 288 edges
od_graph:        Graph with 239 nodes and 290 edges

By now, A network, with origins and destinations is ready to be used for UNA tools and for networkX algorithms. We will learn about both in the next few sections.