Graph data model¶

IduEdu represents transport networks with iduedu.UrbanGraph. An UrbanGraph stores graph topology and geometry in two pandas-compatible tables: nodes_gdf and edges_gdf.

See UrbanGraph basics for a runnable introduction to graph tables, validation, adjacency matrices, empty graphs, and .urbangraph IO.

Nodes table¶

nodes_gdf is a pandas.DataFrame or geopandas.GeoDataFrame whose index is the node identifier used by all graph algorithms.

For spatial graphs, nodes_gdf should be a GeoDataFrame with point geometries. The node index must be unique.

Edges table¶

edges_gdf is a pandas.DataFrame or geopandas.GeoDataFrame with one row per graph edge. Spatial graphs use LineString geometries.

Required columns:

u: Source node id. Must reference nodes_gdf.index.
v: Target node id. Must reference nodes_gdf.index.
geometry: Edge geometry. For geospatial graphs this is a LineString.
length_meter: Edge length in meters.
time_min: Edge traversal time in minutes.

Multigraphs¶

If UrbanGraph.is_multigraph is true, edges_gdf must also contain k. The tuple (u, v, k) uniquely identifies an edge. Non-multigraphs require (u, v) pairs to be unique.

Directed edges¶

Directed graphs are represented by UrbanGraph.is_directed. Some builders also provide an edge direction column, usually oneway.

When edge_direction_column is set:

True means movement is allowed only from u to v;
False means movement is allowed in both directions.

Coordinate reference systems¶

When nodes and edges are GeoDataFrame objects, their CRS must match the graph CRS. Builders usually estimate a local projected CRS for metric lengths and travel-time calculations.

Node and edge types¶

Builders record what a node or an edge stands for in a type column. Routing ignores it, but it tells graph layers apart after they are joined, for example to colour a route by mode or to select boarding edges.

Walk and drive graphs¶

iduedu.get_walk_graph() returns an undirected multigraph whose edges have type="walk". iduedu.get_drive_graph() returns a directed multigraph with type="drive" edges, the oneway direction column and, with add_road_category=True, a road category. Street nodes carry only their geometry. Edges also keep a configurable set of OSM tags: highway and name for walking, plus lanes for driving (see Configuration).

Public transport from OSM¶

Type	Meaning
`bus`, `trolleybus`, `tram`, `subway`, `monorail`, `taxi`, `train`	On nodes, a stop of one route, with the route name in `route`. On edges, a ride between consecutive stops of that route.
`platform`	Node where passengers wait; it is attached to the walking network in intermodal graphs. Subway platforms that are not linked to a station, or whose station has no mapped entrance and exit, are typed `platform` too.
`boarding`	Edge from a platform to a route stop, with zero length. Its `time_min` is the mode’s `avg_wait_time_min` from the transport registry.
`alighting`	Edge from a route stop back to its platform, with zero time and length.
`subway_station`	Node for a station, with OSM `name` and `depth` when mapped. As an edge type, the bidirectional link between a station and its platform.
`subway_platform`	Node for a platform reached only through its station.
`subway_entry_exit`, `subway_entry`, `subway_exit`	Nodes for station entrances, by the direction of travel they allow. They are attached to the walking network.
`subway_entrance`, `subway_exit`	Edges from an entrance into the station and from the station to an exit, timed as an escalator ride when the station depth is known.
`subway_transfer`	Bidirectional edge between the stations of one interchange.

Public transport from GTFS¶

Type	Meaning
`bus`, `subway`, `tram` and the other modes	On nodes, a stop of one route pattern, with `gtfs_stop_id`, `route_id`, `pattern_id` and `stop_position`. On edges, a ride between consecutive stops of that pattern.
`platform`	Node for a stop served by the selected trips; it is attached to the walking network in intermodal graphs.
`station_platform`	Node for a stop inside a station that the feed describes with pathways. It is reached through the station, not directly from the street.
`station`, `station_entry_exit`, `station_node`, `station_boarding_area`	Nodes for stops with `location_type` 1, 2, 3 and 4 that pathways or served stops refer to. Entrances (`station_entry_exit`) are attached to the walking network.
`boarding`, `alighting`	As in OSM graphs, except that the boarding time is the timetable wait.
`pathway`	Edge from `pathways.txt` with `pathway_id` and `pathway_mode`, timed by `traversal_time` or by its length at `walk_speed_m_per_min`.
`station_link`	Zero-cost, bidirectional edge from a stop to its `parent_station`.

Intermodal graphs¶

iduedu.get_intermodal_graph() and iduedu.join_pt_walk_graph() keep the types of both layers. Walking edges, including the connectors that attach platforms and entrances to the street, have type="walk", and walking nodes have no type. See GTFS public transport and Shortest paths and OD matrices for routes coloured by edge type.

API reference¶

class iduedu.UrbanGraph(nodes_gdf, edges_gdf, is_multigraph, is_directed, *, edge_direction_column=None, adjacency_weight='time_min', crs=None, graph_type=None)[source]¶

Tabular representation of an urban transport graph.

UrbanGraph stores nodes and edges as pandas-compatible tables and builds SciPy CSR adjacency matrices for shortest-path and OD-matrix calculations. Spatial graphs use GeoDataFrame tables: nodes are points, edges are lines, and both tables share the graph CRS.

Parameters:

nodes_gdf (GeoDataFrame | DataFrame) – Node table. Its index is the node id and must be unique. Spatial graphs should use point geometries.
edges_gdf (GeoDataFrame | DataFrame) – Edge table. Required columns are u, v, geometry, length_meter and time_min. Multigraphs also require k. Edge endpoint columns reference nodes_gdf.index.
is_multigraph (bool) – Whether multiple edges may exist between the same node pair. If true, (u, v, k) uniquely identifies an edge.
is_directed (bool) – Whether edge direction is respected by adjacency-based algorithms.
edge_direction_column (str | None) – Optional boolean edge column. True means movement is allowed only from u to v; False means both directions are allowed.
adjacency_weight (str) – Default edge column used when building weighted adjacency matrices.
crs (Any | None) – Optional graph CRS. If omitted, it is inferred from GeoDataFrames when possible.
graph_type (str | None) – Optional semantic graph type such as "drive", "walk" or "intermodal".

Raises:

TypeError – If node or edge tables use unsupported types.
ValueError – If graph table contracts are violated.

classmethod empty(*, crs=None, is_multigraph=True, is_directed=False, edge_direction_column=None, adjacency_weight='time_min', graph_type=None)[source]¶

Create an empty graph with the requested topology metadata.

Return type:

UrbanGraph

Parameters:

crs (Any | None)
is_multigraph (bool)
is_directed (bool)
edge_direction_column (str | None)
adjacency_weight (str)
graph_type (str | None)

validate()[source]¶

Validate node, edge, topology and CRS contracts of the graph.

Raises:

TypeError – If graph tables use unsupported types.
ValueError – If graph table contracts are violated.

Return type:

None

copy()[source]¶

Return an independent copy of the graph and cached adjacency state.

Return type:: UrbanGraph

write(path, *, include_adjacency=False)[source]¶

Write the graph to an .urbangraph archive.

Parameters:

path (str | Path) – Destination path with the .urbangraph suffix.
include_adjacency (bool) – Whether to persist the cached adjacency matrix.

Return type:

Path

Returns:

Path to the written archive.

classmethod read(path, *, validate=True)[source]¶

Read an UrbanGraph from an .urbangraph archive.

Parameters:

path (str | Path) – Source path with the .urbangraph suffix.
validate (bool) – Whether to validate the graph after reading.

Return type:

UrbanGraph

Returns:

Restored graph instance.

update_adjacency_matrix(*, nodelist=None, weight=None, multigraph_rule='min')[source]¶

Rebuild and store the graph adjacency matrix.

Parameters:

nodelist (Optional[Iterable[Any]]) – Node ids to include in matrix order. If omitted, all graph nodes are used.
weight (str | None) – Edge weight column. If omitted, adjacency_weight is used.
multigraph_rule (Literal['min', 'max']) – Aggregation rule for parallel edges.

Return type:

csr_matrix

Returns:

Built SciPy CSR adjacency matrix.

Raises:

KeyError – If weight is not present in edges_gdf.
ValueError – If edge weights are invalid.

to_csr(*, nodelist=None, weight=None, multigraph_rule='min')[source]¶

Build a CSR adjacency matrix without changing graph state.

Parameters:

nodelist (Optional[Iterable[Any]]) – Node ids to include in matrix order. If omitted, all graph nodes are used.
weight (str | None) – Edge weight column. If omitted, adjacency_weight is used.
multigraph_rule (Literal['min', 'max']) – Aggregation rule for parallel edges.

Return type:

csr_matrix

Returns:

Built SciPy CSR adjacency matrix.

connected_components()[source]¶

Return connected components for an undirected graph.

Return type:: list[set[Any]]

weakly_connected_components()[source]¶

Return weakly connected components, ignoring edge direction.

Return type:: list[set[Any]]

strongly_connected_components()[source]¶

Return strongly connected components.

Return type:: list[set[Any]]

largest_component(*, mode='auto')[source]¶

Return the largest component according to the selected mode.

Return type:: set[Any]
Parameters:: mode (Literal['auto', 'connected', 'weak', 'strong'])

subgraph_by_nodes(nodes)[source]¶

Return the node-induced subgraph for nodes.

Return type:: UrbanGraph
Parameters:: nodes (Iterable[Any])

keep_largest_connected_component(*, mode='auto', inplace=False)[source]¶

Keep only the largest graph component.

Return type:

UrbanGraph

Parameters:

mode (Literal['auto', 'connected', 'weak', 'strong'])
inplace (bool)

single_source_dijkstra_path_length(source_node, *, weight='time_min', cutoff=None, reverse=False, dtype=<class 'numpy.float32'>)[source]¶

Run single-source Dijkstra shortest path search on this graph.

Return type:

Series

Parameters:

source_node (Any)
weight (Literal['length_meter', 'time_min'])
cutoff (float | None)
reverse (bool)
dtype (dtype)

single_source_dijkstra_path(source_node, target_node, *, weight='time_min', cutoff=None, reverse=False)[source]¶

Return one shortest path as an ordered list of graph node ids.

Return type:

list[Any]

Parameters:

source_node (Any)
target_node (Any)
weight (Literal['length_meter', 'time_min'])
cutoff (float | None)
reverse (bool)

multi_source_dijkstra_path_length(*, source_nodes=None, gdf_sources=None, graph_node_column='graph_node_id', weight='time_min', cutoff=None, reverse=False, dtype=<class 'numpy.float32'>)[source]¶

Run multi-source Dijkstra shortest path search on this graph.

Return type:

Series

Parameters:

source_nodes (Iterable[Any] | None)
gdf_sources (DataFrame | None)
graph_node_column (str)
weight (Literal['length_meter', 'time_min'])
cutoff (float | None)
reverse (bool)
dtype (dtype)

multi_source_dijkstra_path(*, gdf_origins=None, gdf_destinations=None, origins_nodes=None, destination_nodes=None, graph_node_column='graph_node_id', weight='time_min', mode='all_to_all', threshold=None, max_workers=None)[source]¶

Return shortest node paths between origin and destination inputs.

Return type:

DataFrame

Parameters:

gdf_origins (DataFrame | None)
gdf_destinations (DataFrame | None)
origins_nodes (Iterable[Any] | None)
destination_nodes (Iterable[Any] | None)
graph_node_column (str)
weight (Literal['length_meter', 'time_min'])
mode (Literal['all_to_all', 'pairwise'])
threshold (float | None)
max_workers (int | None)

multi_source_dijkstra_nearest_source(*, source_nodes=None, gdf_sources=None, graph_node_column='graph_node_id', weight='time_min', cutoff=None, reverse=False, dtype=<class 'numpy.float32'>)[source]¶

Find the nearest source node and distance for each reachable graph node.

Return type:

DataFrame

Parameters:

source_nodes (Iterable[Any] | None)
gdf_sources (DataFrame | None)
graph_node_column (str)
weight (Literal['length_meter', 'time_min'])
cutoff (float | None)
reverse (bool)
dtype (dtype)

dijkstra_path_length_parallel(*, source_nodes=None, gdf_sources=None, graph_node_column='graph_node_id', weight='time_min', cutoff=None, reverse=False, dtype=<class 'numpy.float32'>, max_workers=None)[source]¶

Run independent Dijkstra searches for multiple source nodes.

Return type:

DataFrame

Parameters:

source_nodes (Iterable[Any] | None)
gdf_sources (DataFrame | None)
graph_node_column (str)
weight (Literal['length_meter', 'time_min'])
cutoff (float | None)
reverse (bool)
dtype (dtype)
max_workers (int | None)

od_matrix(*, gdf_origins=None, gdf_destinations=None, origins_nodes=None, destination_nodes=None, graph_node_column='graph_node_id', weight='time_min', dtype=<class 'numpy.float32'>, threshold=None, max_workers=None)[source]¶

Calculate an OD matrix of shortest paths on this graph.

Return type:

DataFrame

Parameters:

gdf_origins (DataFrame | None)
gdf_destinations (DataFrame | None)
origins_nodes (Iterable[Any] | None)
destination_nodes (Iterable[Any] | None)
graph_node_column (str)
weight (Literal['length_meter', 'time_min'])
dtype (dtype)
threshold (float | None)
max_workers (int | None)

path_to_edges(path, *, weight='time_min')[source]¶

Convert an ordered node path to ordered graph edges.

Return type:

GeoDataFrame

Parameters:

path (Iterable[Any])
weight (Literal['length_meter', 'time_min'])

classmethod from_nx_graph(nx_graph, restore_edge_geom=False, *, check_oneway=True, oneway_column='oneway')[source]¶

Create an UrbanGraph from a NetworkX graph.

This constructor is useful for graphs received from external libraries when they already contain node coordinates, CRS metadata and edge attributes such as length_meter and time_min. The conversion itself is performed by iduedu.nx_graph2urban_graph().

Parameters:

nx_graph – NetworkX graph, directed graph, multigraph or multidigraph.
restore_edge_geom (bool) – If True, empty edge geometries are restored as straight segments between endpoint nodes.
check_oneway (bool) – If True and oneway_column exists on edges, that column is used as the edge direction column.
oneway_column (str) – Boolean edge attribute that marks one-way movement.

Return type:

UrbanGraph

Returns:

Converted UrbanGraph instance.

to_nx_graph()[source]¶

Convert this graph to a NetworkX graph.

The method delegates to iduedu.urban_graph2nx_graph() and preserves node and edge attributes where possible.

Returns:: NetworkX graph type matching this graph topology.

simplify_multiedges(*, weight='time_min', rule='min', inplace=False)[source]¶

Collapse a multigraph to a simple graph.

For each node pair, one edge is selected by the weight column. rule="min" keeps the smallest weight and rule="max" keeps the largest weight. Functional equivalent: iduedu.simplify_multiedges().

Parameters:

weight (str) – Edge column used to choose the representative edge.
rule (Literal['min', 'max']) – Selection rule, either "min" or "max".
inplace (bool) – If True, replace this object with the simplified graph.

Return type:

UrbanGraph

Returns:

Simplified UrbanGraph.

relabel(*, inplace=False)[source]¶

Relabel graph nodes to a dense RangeIndex.

Functional equivalent: iduedu.relabel_urban_graph().

Parameters:: inplace (bool) – If True, replace this object with the relabeled graph.
Return type:: UrbanGraph
Returns:: UrbanGraph with updated node indexes and edge endpoints.

clip(polygon, *, inplace=False)[source]¶

Clip the graph by geometry and keep only nodes inside it.

Edges are retained only when both endpoints remain in the graph. Node ids are preserved; call relabel() if dense labels are needed. Functional equivalent: iduedu.clip_urban_graph().

Parameters:

polygon – Shapely geometry in the graph CRS.
inplace (bool) – If True, replace this object with the clipped graph.

Return type:

UrbanGraph

Returns:

Clipped UrbanGraph.

join(other, *, graph_type=None, node_conflict='left', inplace=False)[source]¶

Join this graph with another compatible UrbanGraph.

Shared node indexes are allowed and resolved with node_conflict. Duplicate edge keys are treated as conflicts.

Parameters:

other (UrbanGraph) – Graph to append.
graph_type (str | None) – Optional graph type for the result. If None, keep this graph type.
node_conflict (str) – Which side wins when node indexes overlap: "left" or "right".
inplace (bool) – If True, replace this object with the joined graph.

Return type:

UrbanGraph

Returns:

Joined UrbanGraph.

to_directed(*, edge_direction_column='oneway', default_direction_value=False, inplace=False)[source]¶

Return a directed version of the graph with an edge direction column.

Functional equivalent: iduedu.to_directed().

Parameters:

edge_direction_column (str) – Name of the boolean one-way edge column.
default_direction_value (bool) – Value used for edges where the column is missing or null.
inplace (bool) – If True, replace this object with the directed graph.

Return type:

UrbanGraph

Returns:

Directed UrbanGraph.

to_undirected(*, inplace=False)[source]¶

Return an undirected version of the graph.

Functional equivalent: iduedu.to_undirected().

Parameters:: inplace (bool) – If True, replace this object with the undirected graph.
Return type:: UrbanGraph
Returns:: Undirected UrbanGraph.

nearest_nodes(objects_gdf, *, graph_node_column='graph_node_id')[source]¶

Return nearest graph node ids for object geometries.

Functional equivalent: iduedu.nearest_nodes().

Parameters:

objects_gdf (GeoDataFrame) – GeoDataFrame with geometries to match to graph nodes.
graph_node_column (str) – Name assigned to the returned Series.

Return type:

Series

Returns:

Series indexed like objects_gdf with nearest node ids as values.

project_objects(objects_gdf, speed_m_per_min, *, max_dist=None, add_link_edge=True, inplace=False)[source]¶

Project objects onto nearest graph edges and add them to the graph.

The method creates graph nodes for objects, projects their representative points onto nearest edges, splits those edges when needed and adds connector edges. It is convenient for in-memory preparation of buildings, services or other objects before OD-matrix calculations. For backend workflows where graph changes should be persisted separately, use iduedu.project_objects2urban_graph().

Parameters:

objects_gdf (GeoDataFrame) – Objects with a unique index and geometry. The index becomes the object2node_map index.
speed_m_per_min (float) – Movement speed on connector edges, in meters per minute. For 5 km/h use 5 * 1000 / 60.
max_dist (float | None) – Optional maximum distance to the nearest edge. If None, no distance limit is applied.
add_link_edge (bool) – If True, create a dedicated object node and connector edge. If False, map objects to projection nodes on the graph.
inplace (bool) – If True, apply changes to this graph.

Return type:

tuple[UrbanGraph, Series]

Returns:

Pair (graph, object2node_map). object2node_map is indexed by the original object index and contains graph node ids.