Usage: 5.3. Modifying Network: Simplification

Simplifying the Network object

This page goes through network simplification in GeNet. Available as a jupyter notebook or wiki page.

Using OSM data to generate a network results in a very node-dense network. GeNet has methods to simplify such networks.

from genet import read_osm
n = read_osm('../example_data/example.osm', 
             '../genet/configs/OSM/slim_config.yml',
            epsg='epsg:27700')
n.print()

2022-07-14 16:04:32,948 - Building OSM graph from file ../example_data/example.osm
2022-07-14 16:04:33,358 - Creating networkx graph from OSM data
2022-07-14 16:04:33,360 - OSM: Extract Nodes and Paths from OSM data
2022-07-14 16:04:33,653 - OSM: Add each OSM way (aka, path) to the OSM graph
2022-07-14 16:04:33,654 - Created OSM edges
2022-07-14 16:04:34,608 - Added 8695 nodes
2022-07-14 16:04:39,558 - Generated 802 link ids.
2022-07-14 16:04:39,748 - Added 802 links
2022-07-14 16:04:39,749 - Deleting isolated nodes which have no edges.
2022-07-14 16:04:39,972 - Removed 8132 nodes.


Graph info: Name: Network graph
Type: MultiDiGraph
Number of nodes: 563
Number of edges: 802
Average in degree:   1.4245
Average out degree:   1.4245 
Schedule info: Schedule:
Number of services: 0
Number of routes: 0
Number of stops: 0

You can simplify a genet.Network using the simplify method.

n.simplify(no_processes=1)

n.print()

2022-07-14 16:04:39,982 - Begin simplifying the graph
2022-07-14 16:04:39,985 - Generating paths to be simplified
2022-07-14 16:04:39,990 - Identified 114 edge endpoints
2022-07-14 16:04:39,991 - Identified 163 possible paths
2022-07-14 16:04:39,993 - Processing 163 paths
2022-07-14 16:04:39,995 - Found 110 paths to simplify.
2022-07-14 16:04:39,996 - Generated 110 link ids.
2022-07-14 16:04:40,007 - Processing links for all paths to be simplified
2022-07-14 16:04:40,032 - Adding new simplified links
2022-07-14 16:04:40,057 - Generated 0 link ids.
2022-07-14 16:04:40,078 - Added 110 links
2022-07-14 16:04:40,084 - Simplified graph: 563 to 114 nodes, 802 to 163 edges


Graph info: Name: Network graph
Type: MultiDiGraph
Number of nodes: 114
Number of edges: 163
Average in degree:   1.4298
Average out degree:   1.4298 
Schedule info: Schedule:
Number of services: 0
Number of routes: 0
Number of stops: 0

Specifying number of processes is optional but defaults to 1. It is recommended you select a number appropriate for the machine you're using to spread the computational load. Having said that, we have seen large memory spikes when using more than one process. It may take a few attempts to get this number right.

This is a complicated process and can take a long time. To that end, it may be more convenient to use a script, see an example scripts/simplify_network.py.

The process is an altered version of graph simplification available in the osmnx package. Network links will be simplified between end-point nodes which meet the following conditions:

• the number of nodes in the union of successor and predecessor nodes of that node is greater than two
  • i.e. if the node is connected to more than one node in any direction it cannot be simplified
• the node has no successor or predecessor nodes
  • i.e. the node is a sink or source
• there is a loop at the node
  • the only successor node is the node itself
• the number of successor and predecessor nodes is not equal
  • this should be thought of cases where number of successor and predecessor nodes is 0, 1 or 2 (earlier condition prohibits other cases). This condition means we end link simplification at nodes where direction of flow changes so in a situation where ... NODE_1 ---> NODE_2 <--> NODE_3 ..., NODE_2 will be be an endpoint and remain in the graph
• if the number of nodes in the union of successor and predecessor nodes is 1 and that node is both the successor and predecessor node
  • i.e. ... NODE_1 <--> NODE_2 <--> NODE_3, NODE_3 will be an endpoint to avoid cul-de-sacs being big loops at single point in the graph

Below is an example of a simplified network.

Upon simplification, the nodes which are being simplified are used for the creation of geometry for the link. This geometry is used in any geojson outputs, preserving the original look of the network. The data stored under links which are being simplified is fused handles in the following way:

• freespeed: The maximum value across links is taken
• capacity: Rounded up to integer of median across links
• permlanes: Rounded up to integer of median across links
• length: Sum across links
• modes: Union across links, i.e. {'bus'} | {'car'} = {'bus', 'car}'
• In the case of overlapping OSM attributes such as osm ids or highway types they are stored as sets under the same attributes in the graph.

>>> n.link('12')['attributes']['osm:way:osmid'] = {'123','124'}

GeNet by default supports such mixture of data types when filtering the network on conditions e.g. to get links with OSM ids 123, you need only use the familiar syntax:

osm_id_123_links = genet.graph_operations.extract_links_on_edge_attributes(
        n,
        conditions= {'attributes': {'osm:way:highway': '123'}}
    )

If you need this method to work only for non iterable values, you need to specify mixed_dtypes=False:

osm_id_123_links = genet.graph_operations.extract_links_on_edge_attributes(
        n,
        conditions= {'attributes': {'osm:way:highway': '123'}},
        mixed_dtypes=False
    )

This will result in link with id 12 not being included in the resulting osm_id_123_links.

In the output MATSim network these are saved as comma separated values under link attributes. Upon reading such a network into GeNet, the attributes become sets again. The geometry is also saved to a MATSim network under attributes and encoded as polyline. Unlike other attributes, upon reading it back with GeNet the geometry is decoded into shapely.LineString and becomes a main data key, i.e.

>>> n.link_attribute_summary()

attribute
├── id ['12']
├── geometry [LineString((x,y), (v,w)]
...
└── attributes
    ...
    └── osm:way:highway [{'residential','minor'}]

instead of

>>> n.link_attribute_summary()

attribute
├── id ['12']
...
└── attributes
    ├── geometry ['}qtqa{aBwfc`_y`@jfq|Hdzm~A...']
    ...
    └── osm:way:highway [{'residential','minor'}]

This is the same schema as for the network right after simplification, before it is saved. The output MATSim link is saved in the following way:

<link id="12" from="NODE_1" to="NODE_4" freespeed="12.5" capacity="600" permlanes="1" oneway="1" modes="car,walk,bike" length="232.733">
    <attributes>
        <attribute name="osm:way:osmid" class="java.lang.String">123,124</attribute>
        <attribute name="osm:way:highway" class="java.lang.String">residential,minor</attribute>
        <attribute name="osm:way:lanes" class="java.lang.String">1</attribute>
        <attribute name="geometry" class="java.lang.String">}qtqa{aBwfc`_y`@jfq|Hdzm~Adn~tMlnkoDlpa|OttblF</attribute>
    </attributes>
</link>

! Attention - Always make sure to validate connectivity of the simplified network

In case of Networks featuring a Schedule. After the process of simplifying the Network graph is complete all of the link references for PT stops get checked and updated by simplified links. All of the network routes also get updated by simplified links. Because our condition for simplification is in-degree = out-degree = 1, the updated do not have the potential to disrupt the PT network route. It could mean that two or more stops could now refer to the same long link. It is encouraged that you run validation on your network post simplification (included in scripts/simplify_network.py) and verify your network visually.