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.

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.

See also

https://iduclub.github.io/IduEdu/examples/urban_graph_basics.html

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.

See also

https://iduclub.github.io/IduEdu/examples/urban_graph_basics.html

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.

See also

https://iduclub.github.io/IduEdu/examples/urban_graph_basics.html

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.

See also

https://iduclub.github.io/IduEdu/examples/connectivity.html

Return type:

list[set[Any]]

weakly_connected_components()[source]

Return weakly connected components, ignoring edge direction.

See also

https://iduclub.github.io/IduEdu/examples/connectivity.html

Return type:

list[set[Any]]

strongly_connected_components()[source]

Return strongly connected components.

See also

https://iduclub.github.io/IduEdu/examples/connectivity.html

Return type:

list[set[Any]]

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

Return the largest component according to the selected mode.

See also

https://iduclub.github.io/IduEdu/examples/connectivity.html

Return type:

set[Any]

Parameters:

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

subgraph_by_nodes(nodes)[source]

Return the node-induced subgraph for nodes.

See also

https://iduclub.github.io/IduEdu/examples/graph_operations.html

Return type:

UrbanGraph

Parameters:

nodes (Iterable[Any])

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

Keep only the largest graph component.

See also

https://iduclub.github.io/IduEdu/examples/connectivity.html

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.

See also

https://iduclub.github.io/IduEdu/examples/shortest_paths.html

Return type:

Series

Parameters:
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.

See also

https://iduclub.github.io/IduEdu/examples/shortest_paths.html

Return type:

Series

Parameters:
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.

See also

https://iduclub.github.io/IduEdu/examples/shortest_paths.html

Return type:

DataFrame

Parameters:
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.

See also

https://iduclub.github.io/IduEdu/examples/shortest_paths.html

Return type:

DataFrame

Parameters:
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.

See also

https://iduclub.github.io/IduEdu/examples/shortest_paths.html

Return type:

DataFrame

Parameters:
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.graph.adapters.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.graph.adapters.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.graph.transformers.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.

See also

https://iduclub.github.io/IduEdu/examples/graph_operations.html

relabel(*, inplace=False)[source]

Relabel graph nodes to a dense RangeIndex.

Functional equivalent: iduedu.graph.editors.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.

See also

https://iduclub.github.io/IduEdu/examples/graph_operations.html

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.graph.editors.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.

See also

https://iduclub.github.io/IduEdu/examples/graph_operations.html

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.

See also

https://iduclub.github.io/IduEdu/examples/graph_operations.html

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.graph.transformers.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.

See also

https://iduclub.github.io/IduEdu/examples/graph_operations.html

to_undirected(*, inplace=False)[source]

Return an undirected version of the graph.

Functional equivalent: iduedu.graph.transformers.to_undirected().

Parameters:

inplace (bool) – If True, replace this object with the undirected graph.

Return type:

UrbanGraph

Returns:

Undirected UrbanGraph.

See also

https://iduclub.github.io/IduEdu/examples/graph_operations.html

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

Return nearest graph node ids for object geometries.

Functional equivalent: iduedu.graph.graph_inputs.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.

See also

https://iduclub.github.io/IduEdu/examples/objects_and_nearest_nodes.html

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.graph.editors.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.

See also

https://iduclub.github.io/IduEdu/examples/objects_and_nearest_nodes.html