superblockify.partitioning.approaches package

superblockify.partitioning.approaches package#

Submodules#

superblockify.partitioning.approaches.attribute module#

Approaches based on node and edge attributes of the graph.

For example using the betweenness centrality of nodes and edges to partition the graph.

class superblockify.partitioning.approaches.attribute.AttributePartitioner(name='unnamed', city_name=None, search_str=None, unit='time', graph=None, reload_graph=False, max_nodes=20000)[source]#

Bases: BasePartitioner, ABC

Parent class for all partitioners that use node and/or edge attributes.

A child class needs to write boolean edge attribute (True/1 or False/0) to the attribute_label of the graph self.graph. All edges with the True belong to the sparsified graph, as well as all touching nodes. The rest of the graph falls apart into Superblocks.

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])	Group by boolean attribute and remove small components.
`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.
`write_attribute`(**kwargs)	Write boolean edge attribute `attribute_label` to the graph.

partition_graph(make_plots=False, **kwargs)[source]#

Group by boolean attribute and remove small components.

Construct sparsified graph from boolean attribute and Superblock subgraphs for the components that fall apart.

Parameters:

make_plotsbool, optional: Whether to show and save plots of the partitioning analysis, by default False

abstract write_attribute(**kwargs)[source]#: Write boolean edge attribute attribute_label to the graph. Abstract method, needs to be implemented by child class. There need to be both edges with the attribute value True and False. The case of all edges being True or False is equivalent to having no restrictions.

superblockify.partitioning.approaches.bearing module#

Approach relating using edge bearings.

class superblockify.partitioning.approaches.bearing.BearingPartitioner(**kwargs)[source]#

Bases: BasePartitioner

Bearing partitioner.

Partitions based on the edge bearings.

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.
`group_overlapping_intervals`(left_bases, ...)	Find groups of overlapping intervals.
`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.
`merge_sets`(sets)	Merge sets that share at least one element.
`overwrite_attributes_of_ignored_components`(...)	Overwrite attributes of ignored components.
`partition_graph`([make_plots, min_length, ...])	Group by prominent bearing directions.
`plot_interval_splitting`()	Plot the split up of peak bases into intervals.
`plot_peakfinding`()	Show the histogram and found peaks.
`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.

static group_overlapping_intervals(left_bases, right_bases)[source]#

Find groups of overlapping intervals.

Unused at the moment.

Parameters:

left_basesnumpy.array: List of left bases of intervals.
right_basesnumpy.array: List of right bases of intervals.

Returns:

list: List of sets of overlapping intervals.

Raises:

TypeError: If left_bases or right_bases1 are not numpy arrays of 1d shape.
ValueError: If left_bases and right_bases are not of the same length.

Examples

>>> left_bases = [0, 0, 1, 3, 4, 9]
>>> right_bases1 = [1, 2, 3, 4, 10, 10]
>>> group_overlapping_intervals(left_bases, right_bases)
[{0, 1, 2}, {4, 5}]

static merge_sets(sets: List[Set]) → List[Set][source]#

Merge sets that share at least one element.

Parameters:

setslist of sets: List of sets to merge.

Returns:

list of sets: List of merged sets.

Raises:

TypeError: If sets is not a list of sets.

Examples

>>> sets = [{1, 2}, {2, 3}, {4, 5}]
>>> merge_sets(sets)
[{1, 2, 3}, {4, 5}]

>>> sets = [{'a', 'b'}, {'m', 3.4}, {'b', 'c'}]
>>> merge_sets(sets)
[{'a', 'b', 'c'}, {'m', 3.4}]

partition_graph(make_plots=False, min_length=500, min_edge_count=5, **kwargs)[source]#

Group by prominent bearing directions.

Procedure to determine the graphs partitions based on the edges bearings.

Bin bearings. Only on residential edges.
Find peaks.
Determine boundaries/intervals corresponding to a partition.
(optional) Plot found peaks and interval splits.
Write partition attribute edges.

The number of bins is fixed to 360°, as rules for numbers of bins [1] ask for much lower numbers of bins, for common number of edges in a street network (approx. 300 to 60.000 edges), which would produce a too small resolution (Sturges’ formula: 10 to 17 bins; Square-root choice: 18 to 245 bins).

Parameters:

make_plotsbool, optional: If True show visualization graphs of the approach.
min_lengthfloat, optional: Minimum component length in meters to be considered for partitioning.
min_edge_countint, optional: Minimum component edge count to be considered for partitioning.

Raises:

ArithmeticError: If no peaks are being found.

References

[1]

Wikipedia contributors, “Histogram,” Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/w/index.php?title=Histogram&oldid=1113935482 (accessed December 14, 2022).

plot_interval_splitting()[source]#

Plot the split up of peak bases into intervals.

Show how the peaks with their overlapping left and right bases are being split up into non overlapping intervals.

Returns:

fig, axetuple: matplotlib figure, axis

Raises:

AssertionError: If boundaries have not been partitioned yet.

plot_peakfinding()[source]#

Show the histogram and found peaks.

Execute run before or plot during running (run(show_plots=True)).

Returns:

fig, axetuple: matplotlib figure, axis

Raises:

AssertionError: If peakfinding has not been done yet.

superblockify.partitioning.approaches.betweenness module#

Approach based on high betweenness centrality of nodes and edges.

class superblockify.partitioning.approaches.betweenness.BetweennessPartitioner(name='unnamed', city_name=None, search_str=None, unit='time', graph=None, reload_graph=False, max_nodes=20000)[source]#

Bases: AttributePartitioner

Partitioner using betweenness centrality of nodes and edges.

Set sparsified graph from edges or nodes with high betweenness centrality.

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])	Group by boolean attribute and remove small components.
`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.
`write_attribute`([percentile, scaling, max_range])	Determine edges with high betweenness centrality for sparsified graph.

write_attribute(percentile=85.0, scaling='normal', max_range=None, **kwargs)[source]#

Determine edges with high betweenness centrality for sparsified graph.

Edges with high betweenness centrality are used to construct the sparsified graph.

The high percentile is determined through ranking all edges by their betweenness centrality and taking the top percentile. The percentile is determined by the percentile parameter.

Parameters:

percentilefloat, optional: The percentile to use for determining the high betweenness centrality edges, by default 90.0
scalingstr, optional: The type of betweenness to use, can be normal, length, or linear, by default normal
max_rangeint, optional: The range to use for calculating the betweenness centrality, by default None, which uses the whole graph. Its unit is meters.
**kwargs: Additional keyword arguments. calculate_metrics_before takes the make_plots parameter.

Raises:

ValueError: If scaling is not normal, length, or linear.
ValueError: If percentile is not between, 0.0 and 100.0.

superblockify.partitioning.approaches.dummy module#

Dummy partitioner.

class superblockify.partitioning.approaches.dummy.DummyPartitioner(**kwargs)[source]#

Bases: BasePartitioner

Dummy partitioner.

Using the inner fifth in terms of x coordinates of the graph as LCC, and the rest as partitions.

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])	Run method.
`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.

partition_graph(make_plots=False, **kwargs)[source]#

Run method. Must be overridden.

Idea: Take sparsified graph as edges connected by nodes with x coordinates: in the middle fifth of the graph, then the LCC. Partitions are then the WCCs of the rest.

superblockify.partitioning.approaches.steiner_tree module#

A approximation of the minimum Steiner tree.

class superblockify.partitioning.approaches.steiner_tree.MinimumPartitioner(name='unnamed', city_name=None, search_str=None, unit='time', graph=None, reload_graph=False, max_nodes=20000)[source]#

Bases: AttributePartitioner

Partitioner that sets the sparsified network to the steiner tree. Can be in terms of distance or travel time.

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])	Group by boolean attribute and remove small components.
`run`([calculate_metrics, make_plots, ...])	Run partitioning.
`sample_nodes_low_betweenness`(graph, ...[, ...])	Sample nodes with low betweenness centrality.
`sample_nodes_uniform`(graph, fraction, rng)	Sample nodes uniformly.
`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.
`write_attribute`([weight, fraction, seed, ...])	Set the sparsified graph to the Steiner tree.

sample_nodes_low_betweenness(graph, fraction, rng, betweenness_type='normal', make_plots=False)[source]#

Sample nodes with low betweenness centrality.

Parameters:

graphnetworkx.Graph: Graph to sample nodes from.
fractionfloat: Fraction of nodes to sample.
rngnumpy.random.Generator: Random number generator.
betweenness_typestr, optional: Can be ‘normal’, ‘length’, or ‘linear’, by default ‘normal’.
make_plotsbool, optional: Whether to make distance matrix plots, by default False.

Returns:

list of int: List of sampled nodes.

sample_nodes_uniform(graph, fraction, rng)[source]#: Sample nodes uniformly.

write_attribute(weight='travel_time', fraction=0.4, seed=None, low_betweenness_mode=None, num_subtrees=1, remove_oneway_edges=False, **kwargs)[source]#

Set the sparsified graph to the Steiner tree.

Sample random nodes with fixed seed and find the minimum spanning tree of the subgraph induced by these nodes. The partitions are then the related components into which the residual graph decomposes.

Edges that are oneway can be excluded with remove_oneway_edges. The idea is so this approach can produce Superblocks that are reachable from every other Superblock, as Steiner trees are calculated on undirected graphs. But this highly depends on how the place was mapped. If arterial roads in two directions are mapped as two separate ways, this is not the way out.

Normally, the sampling probability is uniform, but if low_betweenness_mode is set, the sampling probability is inversely proportional to the betweenness centrality of the nodes, in the respective betweenness type. This way, the rest graph should fall into more components.

This approach violates the requirement that every Superblock is reachable from every other Superblock.

Parameters:

weightstr, optional: Edge attribute to use as weight for the minimum spanning tree, by default ‘length’, can also be ‘travel_time’ or None for hop count
fractionfloat, optional: Fraction of nodes to sample, by default 0.5
seedint, optional: Seed for the random number generator, by default None.
low_betweenness_modestr, optional: Can be ‘normal’, ‘length’, ‘linear’, or None, by default None. Read more about the centrality types in the resources of superblockify.metrics.measures.betweenness_centrality().
num_subtreesint, optional: Number of subtrees to find, by default 1. Sampled nodes are divided into subtrees subsets, and a steiner tree is found for each subset. The sparsified graph is then the union of these steiner trees. This way, the sparsified graph can be a forest and

Notes

The runtime of this approach is not optimized and can be improved by using the shortest paths calculation of superblockify.metrics.distances.

superblockify.partitioning.approaches.streettype module#

Approach only based on street type.

class superblockify.partitioning.approaches.streettype.ResidentialPartitioner(name='unnamed', city_name=None, search_str=None, unit='time', graph=None, reload_graph=False, max_nodes=20000)[source]#

Bases: AttributePartitioner

Partitioner that only uses street type to partition the graph.

This partitioner groups edges by their street type. Nodes that only connect to residential edges are then grouped into subgraphs. The resulting subgraphs are then partitioned into components based on their size and length.

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])	Group by boolean attribute and remove small components.
`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.
`write_attribute`(**kwargs)	Group by street type.

Notes

The effectiveness of this partitioner is highly dependent on the quality of the OSM data. If the data is not complete, this partitioner will not be able to partition the graph into meaningful subgraphs.

write_attribute(**kwargs)[source]#

Group by street type.

Write 0 to attribute_label if the edge is or contains a residential street, 1 otherwise.

Module contents#

Approaches init, subpackage for the various approaches.

superblockify.partitioning.approaches package

Contents

superblockify.partitioning.approaches package#

Submodules#

superblockify.partitioning.approaches.attribute module#

superblockify.partitioning.approaches.bearing module#

superblockify.partitioning.approaches.betweenness module#

superblockify.partitioning.approaches.dummy module#

superblockify.partitioning.approaches.steiner_tree module#

superblockify.partitioning.approaches.streettype module#

Module contents#