superblockify.partitioning package

Subpackages

• superblockify.partitioning.approaches package
  • Submodules
  • superblockify.partitioning.approaches.attribute module
    • AttributePartitioner
      • AttributePartitioner.partition_graph()
      • AttributePartitioner.write_attribute()
  • superblockify.partitioning.approaches.bearing module
    • BearingPartitioner
      • BearingPartitioner.group_overlapping_intervals()
      • BearingPartitioner.merge_sets()
      • BearingPartitioner.partition_graph()
      • BearingPartitioner.plot_interval_splitting()
      • BearingPartitioner.plot_peakfinding()
  • superblockify.partitioning.approaches.betweenness module
    • BetweennessPartitioner
      • BetweennessPartitioner.write_attribute()
  • superblockify.partitioning.approaches.dummy module
    • DummyPartitioner
      • DummyPartitioner.partition_graph()
  • superblockify.partitioning.approaches.steiner_tree module
    • MinimumPartitioner
      • MinimumPartitioner.sample_nodes_low_betweenness()
      • MinimumPartitioner.sample_nodes_uniform()
      • MinimumPartitioner.write_attribute()
  • superblockify.partitioning.approaches.streettype module
    • ResidentialPartitioner
      • ResidentialPartitioner.write_attribute()
  • Module contents

Submodules

superblockify.partitioning.base module

BasePartitioner parent and dummy.

class superblockify.partitioning.base.BasePartitioner(name='unnamed', city_name=None, search_str=None, unit='time', graph=None, reload_graph=False, max_nodes=20000)

Bases: ABC

Parent class for partitioning graphs.

Methods

add_component_tessellation(**tess_kwargs)	Add cell geometry to components.
calculate_metrics([make_plots, ...])	Calculate metrics for the partitioning.
calculate_metrics_before([make_plots, ...])	Calculate metrics for the graph before partitioning.
check_has_been_run()	Check if the partitioner has ran.
get_ltns()	Get Superblock list.
get_partition_nodes()	Get the nodes of the partitioned graph.
get_sorted_node_list()	Get a sorted list of nodes.
load(name)	Load a partitioner.
load_or_find_graph(city_name, search_str[, ...])	Load or find graph if it exists.
make_subgraphs_from_attribute([...])	Make component subgraphs from attribute.
overwrite_attributes_of_ignored_components(...)	Overwrite attributes of ignored components.
partition_graph([make_plots])	Partition the graph.
run([calculate_metrics, make_plots, ...])	Run partitioning.
save([save_graph_copy, ...])	Save the partitioner.
save_key_figures([save_dir, name])	Save key figures.
set_components_from_sparsified()	Set components from sparsified graph.
set_sparsified_from_components()	Set sparsified graph from components.

Notes

This class is an abstract base class and should not be instantiated directly.

Examples

>>> from superblockify.partitioning import BasePartitioner
>>> import osmnx as ox
>>> name, search_str = "Resistencia", "Resistencia, Chaco, Argentina"
>>> graph = ox.graph_from_place(search_str, network_type="drive")
>>> part = BasePartitioner(graph=graph, name=name)
>>> part.run(make_plots=True)

>>> from superblockify.partitioning import BasePartitioner
>>> import osmnx as ox
>>> part = BasePartitioner(
...     name="Resistencia", search_str="Resistencia, Chaco, Argentina"
... )
>>> part.run(approach=True, make_plots=True, num_workers=6)

add_component_tessellation(**tess_kwargs)

Add cell geometry to components.

The population and area are determined independently. To visualize the cells anyway, this method adds a cell geometry, dissolving all edges of the component’s subgraph.

Parameters:

**tess_kwargs

Keyword arguments for the superblockify.population.tessellation.get_edge_cells() function.

calculate_metrics(make_plots=False, replace_max_speeds=True)

Calculate metrics for the partitioning.

Calculates the metrics for the partitioning and writes them to the metrics dictionary. It includes the network metrics for the partitioned graph.

There are different network measures - \(d_E(i, j)\): Euclidean - \(d_S(i, j)\): Shortest path on full graph - \(d_N(i, j)\): Shortest path with a ban through Superblocks

Parameters:

make_plotsbool, optional

If True show visualization graphs of the approach. If False, only print into console. Default is False.

replace_max_speedsbool, optional

If True and unit is “time”, replace max speeds set in superblockify.config. Default is True.

calculate_metrics_before(make_plots=False, betweenness_range=None)

Calculate metrics for the graph before partitioning.

Calculates the metrics that might be used by a partitioning approach. It includes the network shortest paths \(d_S(i, j)\) on the full graph and betweenness centralities.

Parameters:

make_plotsbool, optional

If True show visualization graphs of the approach. If False, only print into console. Default is False.

betweenness_rangeint, optional

The range to use for calculating the betweenness centrality, by default None, which uses the whole graph. Its unit is meters. If it is not None, two types of betweenness centralities are calculated. The whole one is always needed for other statistics.

check_has_been_run()

Check if the partitioner has ran.

Raises:

AssertionError

If BasePartitioner has not been run yet (the partitions are not defined).

get_ltns()

Get Superblock list.

Returns:

list

Reference to self.components, if it is used, otherwise self.partitions

get_partition_nodes()

Get the nodes of the partitioned graph.

Returns list of dict with name of partition and list of nodes in partition. If partitions were split up into components with make_subgraphs_from_attribute and split_disconnected is set to True, the nodes of the components are returned.

Per default, nodes are considered to be inside a partition if they are in the subgraph of the partition and not in the sparsified subgraph. Also, ignored components are left out.

Nodes inside the sparsified graph are never inside a partition.

Method can be overwritten by child classes to change the definition of which nodes to consider to be inside a partition.

Returns:

list of dict

List of dict with name of partition, subgraph of partition and set of nodes in partition.

Raises:

AssertionError

If BasePartitioner has not been run yet (the partitions are not defined).

get_sorted_node_list()

Get a sorted list of nodes.

Sorted after the number of nodes in the partition, followed by the unpartitioned nodes. Use get_partition_nodes to return a list of nodes.

Returns:

list of nodes

List of nodes sorted after the name of the partition, followed by the unpartitioned nodes.

classmethod load(name)

Load a partitioner.

Parameters:

namestr

Name of the partitioner. This is the name of the folder in which the partitioner is saved. Also, the name of the graph and the metrics.

Returns:

partitionerBasePartitioner

Partitioner.

Raises:

FileNotFoundError

If the partitioner cannot be found.

Notes

The directories GRAPH_DIR and RESULTS_DIR are set in the superblockify.config module.

load_or_find_graph(city_name, search_str, reload_graph=False)

Load or find graph if it exists.

If graph GRAPH_DIR/name.graphml exists, load it. Else, find it using search_str and save it to GRAPH_DIR/name.graphml.

Parameters:

city_namestr

Name of the graph. It Can be the name of the place and also be descriptive. Not to confuse with the name of a class instance.

search_strstr or list of str

String to search for in OSM. Can be a list of strings to combine multiple search terms. Use nominatim to find the right search string.

reload_graphbool, optional

If True, reload the graph even if it already exists.

Returns:

graphnetworkx.MultiDiGraph

Graph.

Notes

GRAPH_DIR is set in superblockify.config.

make_subgraphs_from_attribute(split_disconnected=False, min_edge_count=0, min_length=0)

Make component subgraphs from attribute.

Method for child classes to make subgraphs from the attribute self.attribute_label, to analyze (dis-)connected components. For each partition makes a subgraph with the edges that have the attribute value of the partition. Write them to self.component[i][“subgraph”] with the name of the partition+`_component_`+`j`. Where j is the index of the component.

Parameters:

split_disconnectedbool, optional

If True, split the disconnected components into separate subgraphs. Default is False.

min_edge_countint, optional

If split_disconnected is True, minimal size of a component to be considered as a separate subgraph. Default is 0.

min_lengthint, optional

If split_disconnected is True, minimal length (in meters) of a component to be considered as a separate subgraph. Default is 0.

Raises:

AssertionError

If BasePartitioner has not been run yet (the partitions are not defined).

overwrite_attributes_of_ignored_components(attribute_name, attribute_value=None)

Overwrite attributes of ignored components.

Method for child classes to overwrite the subgraph’s edge attributes of ignored components. Overwrites the attribute attribute_name with attribute_value for all components that have the attribute ignore set to True. This is useful, for example, to overwrite the self.attribute_label attribute with None to make the subgraph invisible in the network plot (self.plot_partition_graph()).

Also it will affect self.graph, as the component’s subgraph is a view of the original graph.

Parameters:

attribute_namestr

Name of the attribute to overwrite.

attribute_valuestr, optional

Value to overwrite the attribute with. Default is None.

Raises:

AssertionError

If BasePartitioner has not been run yet (the partitions are not defined).

AssertionError

If self.components is not defined (the subgraphs have not been split into components).

abstract partition_graph(make_plots=False, **kwargs)

Partition the graph.

Parameters:

make_plotsbool, optional

If True, make plots of the partitioning and save them to self.results_dir/figures. Default is False.

Notes

This method should be implemented by the child class, kwargs are handed down from the run method.

final run(calculate_metrics=True, make_plots=False, replace_max_speeds=False, **part_kwargs)

Run partitioning.

Parameters:

calculate_metricsstr or bool, optional

If True, calculate metrics for the partitioning. If False, don’t. Save them to self.results_dir/metrics. Default is True.

make_plotsbool, optional

If True, make plots of the partitioning and save them to self.results_dir/figures. Default is False.

replace_max_speedsbool, optional

If True and self.metric.unit is “time”, calculate the quickest paths in the restricted graph with the max speeds V_MAX_LTN and V_MAX_SPARSE set in superblockify.config. Default is False.

**part_kwargs

Passed to self.partition_graph(). Depends on the abstract method self.partition_graph() of the subclass.

Warning

If self.metric.unit is not “time”, replace_max_speeds is ignored.

save(save_graph_copy=False, dismiss_distance_matrix=False, key_figures=False)

Save the partitioner.

Pickle the partitioner and save it to file. Metric object will be saved in a separate file.

Parameters:

save_graph_copybool, optional

If True, save the graph to a file. In the case the partitioner was initialized with a name and/or search string, the underlying graph is at GRAPH_DIR/name.graphml already. Only use this if you want to save a copy of the graph that has been modified by the partitioner. This is necessary for later plotting partitions, but not for component plots.

dismiss_distance_matrixbool, optional

If True, dismiss the distance matrices in the metric object before saving. This can use a lot of memory.

key_figuresbool, optional

If True, save key figures to file.

Notes

GRAPH_DIR is set in the superblockify.config module.

save_key_figures(save_dir='/home/runner/work/superblockify/superblockify/data/results/key_figures', name=None)

Save key figures.

Only saves graph attributes, essential metrics and the basic graph stats of the partitions.

Parameters:

save_dirstr, optional

Directory in which to save the key figures. If None, use RESULTS_DIR`+/key_figures`.

namestr, optional

Name of the key figures. If None, use name. “_key_figures.yml” will be appended to the name.

Notes

RESULTS_DIR is set in the superblockify.config module.

set_components_from_sparsified()

Set components from sparsified graph.

Method for child classes to set the components from the sparsified graph. The components are the connected components of the rest graph without the sparsified subgraph. The components are set to self.components, also overwriting the self.partitions attribute.

set_sparsified_from_components()

Set sparsified graph from components.

Method for child classes to set the sparsified graph from the components. The sparsified graph is the graph with all edges that are not in the components. The sparsified graph is set to self.sparsified.

superblockify.partitioning.checks module

Checks for the partitioning module.

superblockify.partitioning.checks.components_are_connect_sparsified(partitioning)

Check if each subgraph is connected to the sparsified graph.

Parameters:

partitioningpartitioning.base.BasePartitioner

Partitioning to check.

Returns:

bool

Whether each subgraph is connected to the sparsified graph

superblockify.partitioning.checks.components_are_connected(partitioning)

Check if each component is connected to the sparsified graph.

Parameters:

partitioningpartitioning.base.BasePartitioner

Partitioning to check.

Returns:

bool

Whether each component is connected to the sparsified graph.

superblockify.partitioning.checks.is_valid_partitioning(partitioning)

Check if a partitioning is valid.

The components of a partitioning are the subgraphs, a special subgraph is the sparsified graph.

A partitioning is valid if the following conditions are met:

1. The sparsified graph is connected

2. Each subgraph is connected

3. Each node is contained in exactly one subgraph and not the sparsified graph

4. Each edge is contained in exactly one subgraph and not the sparsified graph

5. No node or edge of graph is not contained in any subgraph or the sparsified graph

6. Each subgraph is connected to the sparsified graph

7. Representative nodes are contained in their respective subgraph

Parameters:

partitioningpartitioning.base.BasePartitioner

Partitioning to check.

Returns:

bool

Whether the partitioning is valid

superblockify.partitioning.checks.nodes_and_edges_are_contained_in_exactly_one_subgraph(partitioning)

Check if each node and edge is contained in exactly one subgraph.

Edges can also be contained in the sparsified graph. Use superblockify.utils.has_pairwise_overlap() to check subgraphs overlap.

Parameters:

partitioningpartitioning.base.BasePartitioner

Partitioning to check.

Returns:

bool

Whether each node and edge is contained in exactly one subgraph.

superblockify.partitioning.checks.representative_nodes_are_contained_in_subgraph(partitioning)

Check if representative nodes are contained in their subgraph.

Parameters:

partitioningpartitioning.base.BasePartitioner

Partitioning to check.

Returns:

bool

Whether representative nodes are contained in their subgraph.

superblockify.partitioning.plot module

Plotting functions for the partitioners.

superblockify.partitioning.plot.plot_component_graph(partitioner, **pba_kwargs)

Plotting the components with color on graph.

Plots the graph with the components, just like plot.paint_streets but that the components have a uniform color.

Parameters:

partitionerBasePartitioner

The partitioner to plot.

pba_kwargs

Keyword arguments to pass to superblockify.plot_by_attribute.

Returns:

fig, axetuple

matplotlib figure, axis

Raises:

AssertionError

If BasePartitioner has not been run yet (the partitions are not defined).

AssertionError

If partitioner.components is not defined (the subgraphs have not been split into components).

superblockify.partitioning.plot.plot_component_rank_size(partitioner, measure)

Plot a rank distribution of the component sizes.

Scatter plot of the component sizes, sorted after the rank of the component.

Parameters:

partitionerBasePartitioner

The partitioner to plot.

measurestr, optional

Way to measure component size. Can be ‘edges’, ‘length’ or ‘nodes’.

xtickslist of numbers or strings, optional

List of xticks to use. If None, the xticks are seven evely spaced numbers between the partitioner.attr_value_minmax.

Returns:

fig, axetuple

matplotlib figure, axis

Raises:

AssertionError

If BasePartitioner has not been run yet (the partitions are not defined).

ValueError

If measure is not ‘edges’, ‘length’ or ‘nodes’.

superblockify.partitioning.plot.plot_partition_graph(partitioner, **pba_kwargs)

Plotting the partitions with color on graph.

Plots the partitioned graph, just like plot.paint_streets but that the partitions have a uniform color.

Parameters:

partitionerBasePartitioner

The partitioner to plot.

pba_kwargs

Keyword arguments to pass to superblockify.plot_by_attribute.

Returns:

fig, axetuple

matplotlib figure, axis

Raises:

AssertionError

If BasePartitioner has not been run yet (the partitions are not defined).

superblockify.partitioning.plot.plot_speed_un_restricted(graph, sparsified, v_s=50.0, v_ltn=15.0, cmap='viridis')

Plot the speed limit of the edges of a graph before and after restrictions.

Side-by-side plot of the speed limits of the edges of a graph, before and after restrictions. Both maps use a shared colorbar.

Parameters:

graphnetworkx.MultiDiGraph

The graph to plot the speed limits of. Needs to have speed_kph as the unrestricted speed limit.

sparsifiednetworkx.MultiDiGraph

The sparsified graph, optimally a view of the original graph.

v_sfloat

The max speed for the edges of the sparsified graph.

v_ltnfloat

The max speed for the remaining edges.

cmapstr

The colormap to use.

Returns:

figmatplotlib.figure.Figure

The figure containing the plot.

axematplotlib.axes.Axes

The axes containing the plot.

superblockify.partitioning.plot.plot_subgraph_component_size(partitioner, measure, xticks=None, **pcs_kwargs)

Plot the size of the subgraph components of the partitions.

Scatter plot of the size of the subgraph components of each partition type.

Parameters:

partitionerBasePartitioner

The partitioner to plot.

measurestr, optional

Way to measure component size. Can be ‘edges’, ‘length’ or ‘nodes’.

xtickslist of numbers or strings, optional

List of xticks to use. If None, the xticks are seven evely spaced numbers between the partitioner.attr_value_minmax.

pcs_kwargs

Keyword arguments to pass to superblockify.plot.plot_component_size.

Returns:

fig, axetuple

matplotlib figure, axis

Raises:

AssertionError

If BasePartitioner has not been run yet (the partitions are not defined).

ValueError

If measure is not ‘edges’, ‘length’ or ‘nodes’.

superblockify.partitioning.representative module

Methods for finding representative nodes in components and partitions.

superblockify.partitioning.representative.find_representative_node_id(graph)

Find representative node in a graph.

Parameters:

graphnetworkx.MultiDiGraph

The graph to find a representative node for.

Returns:

representative_node_idint

The id of the representative node.

superblockify.partitioning.representative.set_representative_nodes(components)

Find representative nodes in components.

Works on list of components or partitions dicts, and sets the ‘representative_node_id’ attribute, derived from the ‘subgraph’ attribute.

It determines the convex hull of the component and returns the node next to the representative point of the convex hull. If a component consists out of one edge connected to the sparsified graph, the representative node is the one that has the lower degree.

Parameters:

componentslist of dict

The components to find representative nodes for, needs to have a ‘subgraph’ attribute.

Notes

The method works in-place. It sets the ‘representative_node_id’ attribute of the components.

superblockify.partitioning.speed module

Speed module for superblockify, used to add speed limits to the edges of a graph.

superblockify.partitioning.speed.add_edge_travel_times_restricted(graph, sparsified, v_s=50.0, v_ltn=15.0)

Add edge travel times (in seconds) to a graph.

The max speed \(v_{\mathrm{s}}\) is used for the edges of the sparsified graph, and the max speed \(v_{\mathrm{ltn}}\) is used for the remaining edges.

\[\begin{split}v_{ij} = \begin{cases} v_{\mathrm{s}} & \text{if } (i, j) \in E_{\mathrm{sparsified}} \\ v_{\mathrm{ltn}} & \text{otherwise} \end{cases}\end{split}\]

Then the travel time \(t_{ij} = \frac{l_{ij}}{v_{ij}}\) is calculated for each edge where \(l_{ij}\) is the length of the edge.

Parameters:

graphnetworkx.Graph

The graph to add the travel times to.

sparsifiednetworkx.Graph

The sparsified graph, optimally a view of the original graph.

v_sfloat

The max speed for the edges of the sparsified graph.

v_ltnfloat

The max speed for the remaining edges.

Notes

The travel times are added as an edge attribute travel_time_restricted.

This function modifies the graph in-place, no value is returned.

\(v_{\mathrm{s}}\) and \(v_{\mathrm{ltn}}\) are read from the superblockify.config module and are handled as km/h.

superblockify.partitioning.utils module

Utility functions for Partitioners.

superblockify.partitioning.utils.get_key_figures(partitioner)

Get key figures of the partitioner.

Contains the name, city_name, graph_stats, metrics, component stats, attribute_label, and attribute_dtype.

Parameters:

partitionerBasePartitioner

Partitioner to get the key figures for.

Returns:

dict

Key figures of the partitioner. See code for structure.

superblockify.partitioning.utils.get_new_node_id(graph)

Get a new node id that is not yet in the graph.

Parameters:

graphnetworkx.classes.multidigraph.MultiDiGraph

Graph to get the new node id for.

Returns:

int

New node id.

Notes

The node id is generated by the function uuid4().int.

We only accept ids > int64.max because the node ids should be differentiable from the osm node ids.

superblockify.partitioning.utils.reduce_graph(graph, max_nodes)

Reduce the graph to have at most max_nodes nodes.

Done by taking the ego graph with not more than max_nodes nodes, starting from a representative central node. As in superblockify.partitioning.representative.set_representative_nodes().

superblockify.partitioning.utils.remove_dead_ends_directed(graph)

Remove all dead ends from the directed graph.

Comes down to removing all nodes that are not in the largest strongly connected component.

Parameters:

graphnetworkx.classes.multidigraph.MultiDiGraph

Graph to remove dead ends from.

Raises:

ValueError

If the graph is not directed.

Notes

The graph is modified in place.

superblockify.partitioning.utils.save_to_gpkg(partitioner, save_path=None, ltn_boundary=False)

Save the partitioner’s graph and Superblocks to a geodatapackage.

The name of the components (/partitions) is saved into a “classification” edge attribute. The sparse graph is saved with the value “SPARSE” into the “classification” edge attribute.

Parameters:

partitionersuperblockify.partitioning.BasePartitioner

The partitioner to save.

save_pathstr, optional

The path to save the geodatapackage to. If None, it will be saved to the partitioners folder at (part.results_dir, part.name + “.gpkg”)

ltn_boundarybool, optional

If True, the boundary of the Superblocks will be saved as a polygon into the cell attribute of the Superblocks layer. For this, the tessellation needs to be calculated.

Raises:

ValueError

If the partitioner has no components or partitions attribute.

ValueError

If the partitioner has no sparsified subgraph.

Notes

The geopackage will contain the following layers: - nodes

• representative_node_name

• missing_nodes: if node is not in any component/partition or sparsified graph

• y, x, lat, lon, geometry

• edges

  • classification

  • osmid, highway, length, geometry

  • (bearing: the bearing of the edge, bearing_90: mod(bearing, 90))

  • (residential: 1 if edge[‘highway’] is or contains ‘residential’, None otherwise)

• ltns

  • classification

  • cell: if ltn_boundary is True

  • else representative_node_point

  • population_density (in people/m^2)

  • area (in m^2)

  • population (in people)

  • see osmnx.stats.basic_stats() for more

• graph_meta

  • boundary (by OSM relation)

  • boundary_crs

  • area (in m^2)

  • street_orientation_order

  • circuity_avg

  • see osmnx.stats.basic_stats() for more

superblockify.partitioning.utils.show_graph_stats(graph)

Show selected graph statistics.

Parameters:

graphnetworkx.classes.multidigraph.MultiDiGraph

Graph to show statistics for.

Notes

Graph must have basic graph stats added by means of superblockify.graph_stats.basic_graph_stats().

superblockify.partitioning.utils.show_highway_stats(graph)

Show the number of edges for each highway type in the graph.

Also show the type proportions of the highway attributes.

Parameters:

graphnetworkx.classes.multidigraph.MultiDiGraph

Graph, where the edges have a “highway” attribute.

Notes

The highway is usually a string, but can also be a list of strings. If the proportion of edges with a highway attribute of type ‘str’ is below 98%, a warning is logged.

superblockify.partitioning.utils.split_up_isolated_edges_directed(graph, sparsified)

Split up all edges in the directed graph that are isolated disregarding the sparsified subgraph.

Isolated edges are edges that are not connected to any other edge in the graph. Also, two parallel edges are considered isolated together if their geometries equal.

These nodes are inserted at a middle point of the edge(s) geometry, the geometry split up. Attributes population and area split, but the further attributes are kept the same.

Parameters:

graphnetworkx.classes.multidigraph.MultiDiGraph

Graph to split up edges in.

sparsifiednetworkx.classes.multidigraph.MultiDiGraph

View of graph, edges taken away from graph to expose isolated edges.

Raises:

ValueError

If the graphs are not directed.

NotImplementedError

Parallel edges of a degree higher than 2 are not supported.

Notes

The graph is modified in place. The function generates the new node ids get_new_node_id.

Module contents

Partitioning init, subpackage for the base partitioner and all approaches.