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 graphself.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 the split up of peak bases into intervals.
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.
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.
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.
- 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.
Module contents#
Approaches init, subpackage for the various approaches.