graphs

Convenience functions for the preparation and conversion of networkX graphs to and from cityseer data structures. Note that the cityseer network data structures can be created and manipulated directly, if so desired.

nx_simple_geoms

nx_simple_geoms
(
nx_multigraph
)

Inferring geometries from node to node. Infers straight-lined geometries connecting the x and y coordinates of each node-pair. The resultant edge geometry will be stored to each edge’s geom attribute.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph with x and y node attributes.

Returns

MultiGraph

A networkX MultiGraph with shapely Linestring geometries assigned to the edge geom attributes.

nx_remove_filler_nodes

nx_remove_filler_nodes
(
nx_multigraph
)

Remove nodes of degree=2. Nodes of degree=2 represent no route-choice options other than traversal to the next edge. These are frequently found on network topologies as a means of describing roadway geometry, but are meaningless from a network topology point of view. This method will find and deleted these nodes, and replaces the two edges on either side with a new spliced edge. The new edge’s geom attribute will retain the geometric properties of the original edges.

Filler nodes may be prevalent in poor quality datasets, or in situations where curved roadways have been represented through the addition of nodes to describe arced geometries. cityseer uses shapely Linestrings to describe arbitrary road geometries without the need for filler nodes. Filler nodes can therefore be removed, thus reducing side-effects as a function of varied node intensities when computing network centralities.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

Returns

MultiGraph

A networkX MultiGraph with nodes of degree=2 removed. Adjacent edges will be combined into a unified new edge with associated geom attributes spliced together.

nx_remove_dangling_nodes

nx_remove_dangling_nodes
(
nx_multigraph
despine : int = 15
remove_disconnected : int = 100
)

Remove disconnected components and optionally removes short dead-end street stubs.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

despine
int

The maximum cutoff distance for removal of dead-ends. Use 0 where no despining should occur.

remove_disconnected
int

Remove disconnected components with fewer nodes than specified by this parameter. Defaults to 100. Set to 0 to keep all disconnected components.

Returns

MultiGraph

A networkX MultiGraph with disconnected components optionally removed, and dead-ends removed where less than the despine parameter distance.

nx_merge_parallel_edges

nx_merge_parallel_edges
(
nx_multigraph
merge_edges_by_midline : bool
contains_buffer_dist : int
osm_hwy_target_tags : list[str] | None = None
osm_matched_tags_only : bool = False
)

Check a MultiGraph for duplicate edges; which, if found, will be merged. The shortest of these parallel edges is selected and buffered by contains_buffer_dist. If this buffer contains an adjacent edge, then the adjacent edge is merged. Edges falling outside this buffer are retained.

When candidate edges are found for merging, they are replaced by a single new edge. The new geometry selected from either:

  • An imaginary centreline of the combined edges if merge_edges_by_midline is set to True;
  • Else, the shortest edge is retained, with longer edges discarded.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

merge_edges_by_midline
bool

Whether to merge parallel edges by an imaginary centreline. If set to False, then the shortest edge will be retained as the new geometry and the longer edges will be discarded. Defaults to True.

contains_buffer_dist
int

The buffer distance to consider when checking if parallel edges sharing the same start and end nodes are sufficiently adjacent to be merged.

osm_hwy_target_tags
list[str]

An optional list of OpenStreetMap target highway tags. If provided, only nodes with neighbouring edges containing a tag matching one of the target OSM highway tags will be consolidated. Requires graph prepared with via io.osm_graph_from_poly.

osm_matched_tags_only
bool

Whether to only merge edges with shared OSM name or ref tags. False by default. Requires graph prepared with via io.osm_graph_from_poly.

Returns

MultiGraph

A networkX MultiGraph with consolidated nodes.

nx_snap_endpoints

nx_snap_endpoints
(
nx_multigraph
)

Snaps geom endpoints to adjacent node coordinates.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

Returns

MultiGraph

A networkX MultiGraph.

nx_iron_edges

nx_iron_edges
(
nx_multigraph
simplify_by_max_angle : int = 120
min_self_loop_length : int = 100
max_foot_tunnel_length : int = 100
)

Simplifies edges.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

simplify_by_max_angle
int

The maximum angle to permit for a given edge. Angles greater than this will be reduced.

min_self_loop_length
int

Maximum self loop length to permit for a given edge.

max_foot_tunnel_length
int

Maximum tunnel length to permit for non motorised edges. Default of 100m.

Returns

MultiGraph

A networkX MultiGraph with simplified edges.

nx_deduplicate_edges

nx_deduplicate_edges
(
nx_multigraph
dissolve_distance : int = 20
max_ang_diff : int = 20
)

Deduplicates non-motorised edges where parallel to nearby motorised edges. Remove non-motorised edges where adjacent to motorised edges. This helps to simplify complex network representations for the purpose of network centralities or visualisation. Short dead-end non-motorised edges falling within the specified dissolve distance will also be removed.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

dissolve_distance
int

A distance to use when searching for adjacent edges. 20m by default.

max_ang_diff
int

Only count a nearby adjacent edge as duplicitous if the angular difference between edges is less than max_ang_diff. 20 degrees by default.

Returns

MultiGraph

A networkX graph with non-motorised edges removed if parallel to motorised edges.

nx_consolidate_nodes

nx_consolidate_nodes
(
nx_multigraph
buffer_dist : float = 12
neighbour_policy : str | None = None
crawl : bool = False
centroid_by_itx : bool = True
prioritise_by_hwy_tag : bool = False
merge_edges_by_midline : bool = True
contains_buffer_dist : int = 25
osm_hwy_target_tags : list[str] | None = None
osm_matched_tags_only : bool = False
simplify_by_max_angle : int | None = None
)

Consolidates nodes if they are within a buffer distance of each other. Several parameters provide more control over the conditions used for deciding whether or not to merge nodes. The algorithm proceeds in two steps:

Nodes within the buffer distance of each other are merged. If selecting centroid_by_itx then the new centroid will try to use intersections to determine the new centroid for the nodes. It will first attempt to find intersections with two through-routes, else will use intersections with one through-route.

The merging of nodes can create parallel edges with mutually shared nodes on either side. These edges are replaced by a single new edge, with the new geometry selected from either:

  • An imaginary centreline of the combined edges if merge_edges_by_midline is set to True;
  • Else, the shortest edge, with longer edges discarded; See nx_merge_parallel_edges for more information.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

buffer_dist
float

The buffer distance to be used for consolidating nearby nodes. Defaults to 5.

neighbour_policy
str

Whether all nodes within the buffer distance are merged, or only “direct” or “indirect” neighbours. Defaults to None which will consider all nodes.

crawl
bool

Whether the algorithm will recursively explore neighbours of neighbours if those neighbours are within the buffer distance from the prior node. Defaults to False.

centroid_by_itx
bool

Whether to favour intersections when selecting the combined centroid of merged nodes. Intersections with two straight through-routes will be favoured if found, otherwise intersections with one straight through-route are used where available. True by default.

prioritise_by_hwy_tag
bool

Whether to prioritise centroid locations by OSM highway tags. For example, trunk roads will have higher priority than residential roads. Requires graph prepared with via io.osm_graph_from_poly. Defaults to False.

merge_edges_by_midline
bool

Whether to merge parallel edges by an imaginary centreline. If set to False, then the shortest edge will be retained as the new geometry and the longer edges will be discarded. Defaults to True.

contains_buffer_dist
int

The buffer distance to consider when checking if parallel edges sharing the same start and end nodes are sufficiently adjacent to be merged. This is run after node consolidation has completed.

osm_hwy_target_tags
list[str]

An optional list of OpenStreetMap target highway tags. If provided, only nodes with neighbouring edges containing a tag matching one of the target OSM highway tags will be consolidated. Requires graph prepared with via io.osm_graph_from_poly.

osm_matched_tags_only
bool

Whether to only merge edges with shared OSM name or ref tags. False by default. Requires graph prepared with via io.osm_graph_from_poly.

simplify_by_max_angle
int

The optional maximum angle to permit for a given edge. Angles greater than this will be reduced.

Returns

nx.MultiGraph

A networkX MultiGraph with consolidated nodes.

Notes

See the guide on graph cleaning for more information.

Example raw graph from OSM The pre-consolidation OSM street network for Soho, London. © OpenStreetMap contributors.

Example cleaned graph The consolidated OSM street network for Soho, London. © OpenStreetMap contributors.

nx_snap_gapped_endings

nx_snap_gapped_endings
(
nx_multigraph : networkx.classes.multigraph.MultiGraph
buffer_dist : float = 12
osm_hwy_target_tags : list[str] | None = None
osm_matched_tags_only : bool = False
)->[ MultiGraph ]

nx_split_opposing_geoms

nx_split_opposing_geoms
(
nx_multigraph : networkx.classes.multigraph.MultiGraph
buffer_dist : float = 12
merge_edges_by_midline : bool = True
contains_buffer_dist : int = 25
prioritise_by_hwy_tag : bool = False
osm_hwy_target_tags : list[str] | None = None
osm_matched_tags_only : bool = False
min_node_degree : int = 2
max_node_degree : int | None = None
squash_nodes : bool = True
centroid_by_itx : bool = False
simplify_by_max_angle : int | None = None
)->[ MultiGraph ]

Split edges in near proximity to nodes, then weld the resultant node group together, updating edges in the process. This is primarily intended for merging parallel roadways when used with the default min_node_degree=2. When an edge geometry is within the specified buffer_dist of a node (with the specified min_node_degree) then the edge geom is split and a new node is inserted. The new node is then merged with the node which triggered the split, with edge geometries updated accordingly.

Dead-end segments can be projected to nearby edge geometries if lowering min_node_degree to 1. This is useful for connecting disjointed OSM pedestrian segments to nearby roadway geometries. Consider using with max_node_degree=1 and osm_hwy_target_tags set to ['footway'] to restrict the behaviour to dead-end pedestrian routes.

The merging of nodes can create parallel edges with mutually shared nodes on either side. These edges are replaced by a single new edge, with the new geometry selected from either:

  • An imaginary centreline of the combined edges if merge_edges_by_midline is set to True;
  • Else, the shortest edge, with longer edges discarded. See nx_merge_parallel_edges for more information.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

buffer_dist
int

The buffer distance to be used for splitting nearby nodes. Defaults to 5.

merge_edges_by_midline
bool

Whether to merge parallel edges by an imaginary centreline. If set to False, then the shortest edge will be retained as the new geometry and the longer edges will be discarded. Defaults to True.

contains_buffer_dist
int

The buffer distance to consider when checking if parallel edges sharing the same start and end nodes are sufficiently adjacent to be merged.

prioritise_by_hwy_tag
bool

Whether to prioritise centroid locations by OSM highway tags. For example, trunk roads will have higher priority than residential roads. Requires graph prepared with via io.osm_graph_from_poly. Defaults to False.

osm_hwy_target_tags
list[str]

An optional list of OpenStreetMap target highway tags. If provided, only nodes with neighbouring edges containing a tag matching one of the target OSM highway tags will be consolidated. Requires graph prepared with via io.osm_graph_from_poly.

osm_matched_tags_only
bool

Whether to only merge edges with shared OSM name or ref tags. False by default. Requires graph prepared with via io.osm_graph_from_poly.

min_node_degree
int

Only project nodes with at least node degree of min_node_degree.

max_node_degree
int

Only project nodes with at most node degree of max_node_degree.

squash_nodes
bool

Whether to automatically squash new node pairings resulting from splitting a nearby edge. If set to False then a line will be added instead. Defaults to True.

simplify_by_max_angle
int

The optional maximum angle to permit for a given edge. Angles greater than this will be reduced.

Returns

MultiGraph

A networkX MultiGraph with consolidated nodes.

nx_decompose

nx_decompose
(
nx_multigraph
decompose_max : float
osm_hwy_target_tags : list[str] | None = None
)

Decomposes a graph so that no edge is longer than a set maximum. Decomposition provides a more granular representation of potential variations along street lengths, while reducing network centrality side-effects that arise as a consequence of varied node densities.

Setting the decompose parameter too small in relation to the size of the graph may increase the computation time unnecessarily for subsequent analysis. For larger-scale urban analysis, it is generally not necessary to go smaller 20m, and 50m may already be sufficient for the majority of cases.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

decompose_max
float

The maximum length threshold for decomposed edges.

osm_hwy_target_tags
list[str]

An optional list of OpenStreetMap target highway tags. If provided, only nodes with neighbouring edges containing a tag matching one of the target OSM highway tags will be decomposed. Requires graph prepared with via io.osm_graph_from_poly.

Returns

MultiGraph

A decomposed networkX graph with no edge longer than the decompose_max parameter. If live node attributes were provided, then the live attribute for child-nodes will be set to True if either or both parent nodes were live. Otherwise, all nodes wil be set to live=True. The length and imp_factor edge attributes will be set to match the lengths of the new edges.

Notes

from cityseer.tools import mock, graphs, plot

G = mock.mock_graph()
G_simple = graphs.nx_simple_geoms(G)
G_decomposed = graphs.nx_decompose(G_simple, 100)
plot.plot_nx(G_decomposed)

Example graph Example graph prior to decomposition.

Example decomposed graph Example graph after decomposition.

nx_to_dual

nx_to_dual
(
nx_multigraph
)

Convert a primal graph representation to the dual representation. Primal graphs represent intersections as nodes and streets as edges. This method will invert this representation so that edges are converted to nodes and intersections become edges. Primal edge geom attributes will be welded to adjacent edges and split into the new dual edge geom attributes.

Note that a MultiGraph is useful for primal but not for dual, so the output MultiGraph will have single edges. e.g. a crescent street that spans the same intersections as parallel straight street requires multiple edges in primal. The same type of situation does not arise in the dual because the nodes map to distinct edges regardless.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

Returns

MultiGraph

A dual representation networkX graph. The new dual nodes will have x and y node attributes corresponding to the mid-points of the original primal edges. If live node attributes were provided, then the live attribute for the new dual nodes will be set to True if either or both of the adjacent primal nodes were set to live=True. Otherwise, all dual nodes wil be set to live=True. The primal edges will be split and welded to form the new dual geom edges. The primal LineString geom will be saved to the dual node’s primal_edge attribute. primal_edge_node_a, primal_edge_node_b, and primal_edge_idx attributes will be added to the new (dual) nodes, and a primal_node_id edge attribute will be added to the new (dual) edges.

Notes

from cityseer.tools import graphs, mock, plot

G = mock.mock_graph()
G_simple = graphs.nx_simple_geoms(G)
G_dual = graphs.nx_to_dual(G_simple)
plot.plot_nx_primal_or_dual(G_simple, G_dual, plot_geoms=False)

Example dual graph Dual graph (blue) overlaid on the source primal graph (red).

nx_weight_by_dissolved_edges

nx_weight_by_dissolved_edges
(
nx_multigraph
dissolve_distance : int = 20
max_ang_diff : int = 45
)

Generates graph node weightings based on the ratio of directly adjacent edges to total nearby edges. This is used to control for unintended amplification of centrality measures where redundant network representations (e.g. duplicitious segments such as adjacent street, sidewalk, cycleway, busway) tend to inflate centrality scores. This method is intended for ‘messier’ network representations (e.g. OSM).

This method is only recommended for primal graph representations.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

dissolve_distance
int

A distance to use when buffering edges to calculate the weighting. 20m by default.

max_ang_diff
int

Only count a nearby adjacent edge as duplicitous if the angular difference between edges is less than max_ang_diff. 45 degrees by default.

Returns

MultiGraph

A networkX graph. The nodes will have a new weight parameter indicating the node’s contribution given the locally ‘dissolved’ context.

nx_generate_vis_lines

nx_generate_vis_lines
(
nx_multigraph
)

Generates a line_geom property for nodes consisting MultiLineString geoms for visualisation purposes. This method can be used if preferring to visualise the outputs as lines instead of points. The lines are assembled from the adjacent half segments.

Parameters

nx_multigraph
MultiGraph

A networkX MultiGraph in a projected coordinate system, containing x and y node attributes, and geom edge attributes containing LineString geoms.

Returns

MultiGraph

A networkX graph. The nodes will have a new line_geom parameter containing shapely MultiLineString geoms.