Spatial networks¶

Any networkx graph.

Default edge column for algorithms.

The network.

A GeoDataFrame of points, a DataFrame with latitude and longitude columns, or a list of (lat, lon) tuples or Points.

"knn" joins each point to its k nearest neighbours; "distance" joins every pair within max_distance meters.

Number of neighbours for "knn".

Longest edge in meters. Required for "distance"; with "knn" it drops longer neighbour links.

Column holding node IDs. The frame's index otherwise.

Default weight column. Anything but "length" needs weight_func.

Computes the weight column as weight_func(nodes_u, nodes_v, length), where nodes_u and nodes_v are the node rows at each end and length is in meters.

The network. Nodes have kind "point" and edges "point_link".

Folder the network was saved to.

Data store to read from. The local file system otherwise.

Edge attribute columns to read, in addition to u, v, key, length, kind, and the weight column. Include "geometry" to keep edge geometry. All columns otherwise.

If there is no saved network at path.

If the folder was saved by a newer format version, or columns names a column that was not saved.

Folder to write.

Data store to write to. The local file system otherwise.

If node IDs are neither integers nor text, or a column cannot be stored.

If the metadata is not JSON serializable.

True gives a MultiDiGraph; from an undirected network, every edge is added in both directions, with its geometry reversed for the reverse direction. False gives a MultiGraph; from a directed network, a reverse edge with the same key replaces the forward one, as networkx's to_undirected does. Defaults to how the network is directed.

nx.MultiDiGraph or nx.MultiGraph.

If node IDs mix integers and text, which pandana cannot index.

Node IDs, in the order wanted. All nodes otherwise.

CRS to project to.

If an ID is not in the network.

With True, every edge row counts at both of its ends, as networkx counts a multigraph's degree. With False, reverse and parallel edges between the same two nodes count once, so the degree is the number of roads meeting at a node. Defaults to how the network is directed.

Degrees indexed by node ID. A self-loop counts twice.

A GeoDataFrame of points, a DataFrame with latitude and longitude columns, or a list of (lat, lon) tuples or Points.

Meters. Points with no node this close get a missing ID.

Also return the distance in meters.

A Series of node IDs indexed like the points, or with

return_distance a DataFrame with node_id and distance.

Node IDs to keep.

Booleans in node order, or a boolean Series indexed by node ID.

Area in EPSG:4326, a shapely geometry or a GeoDataFrame or GeoSeries in any CRS.

"intersects" or "within", for geometry.

Node IDs to remove.

Remove the node nearest each point, within max_distance meters.

Remove the nodes in this area (see :meth:filter_nodes).

Meters, for points.

"intersects" or "within", for geometry.

Column to set or create. x and y cannot be set.

A single value for every node, values in node order, or a Series or dict keyed by node ID. With a Series or dict, other nodes keep their value, or get a missing value in a new column.

If a key is not a node ID.

With by="id", a table indexed by node ID (or with a node_id column). With by="coordinates", a points input whose rows are matched to their nearest node; when two rows match the same node, the later row wins.

"id" or "coordinates".

Meters, for by="coordinates". Rows with no node this close are skipped, with a warning.

If by="id" and a row is not a node ID.

A GeoDataFrame of points, a DataFrame with latitude and longitude columns, or a list of (lat, lon) tuples.

Column holding the node IDs. The frame's index otherwise.

Kind of the new nodes.

If an ID is already a node of the network.

Booleans in edge order.

Area in EPSG:4326, a shapely geometry or a GeoDataFrame or GeoSeries in any CRS. Straight edges are tested as lines between their nodes.

The edge's relation to the area: "intersects", "within", "crosses", or "touches".

(u, v, key) or (u, v) tuples, or a table with u, v, and optionally key columns. Without a key, every edge between the two nodes is removed. In an undirected network, (v, u) matches (u, v).

Booleans in edge order.

If an edge is not in the network.

Column to set or create. u, v, and key cannot be set.

A single value for every edge, values in edge order, or a Series indexed by (u, v, key) or a dict keyed by (u, v, key) tuples. With a Series or dict, other edges keep their value, or get a missing value in a new column.

If a key is not an edge of the network.

If a row is not an edge of the network.

Start node IDs.

End node IDs.

The weight of each edge, stored in the weight column.

Column for weights.

Kind of the new edges.

More columns, each a single value or one value per edge.

If an endpoint is not a node of the network.

Area in EPSG:4326, a shapely geometry or a GeoDataFrame or GeoSeries in any CRS.

"intersects", "within", "crosses", or "touches".

Edge column to compare. The network's weight otherwise.

If the networks are not all directed or all undirected.

A GeoDataFrame of points, a DataFrame with latitude and longitude columns, or a list of (lat, lon) tuples. Their other columns become node attributes.

Column holding the point IDs. The frame's index otherwise.

Meters. Points farther from any road are skipped, with a warning.

Meters. Connect to the edge's end node when the foot is this close to it.

Handle points nearest to the road first, and join a point to an already inserted point (a point_link edge) when that point is closer than any road.

Also return the points that were skipped.

The new network, or (network, skipped_points). Split nodes get

negative integer IDs, continuing below the lowest existing one.

When the network's weight is not length, new connection edges

get that weight equal to their length, and road pieces get their

share of the road's weight.

If point IDs repeat or are already node IDs, or a point column is named x, y, or kind.

Edge column. The network's weight otherwise.

False ignores one-way restrictions of a directed network.

If the weight is missing or negative on some edge.

Origin node IDs.

Destination node IDs. All nodes otherwise.

Pair origins[i] with destinations[i] instead of building the full matrix.

Edge column to add up. The network's weight otherwise.

"scipy", or "pandana" for very many pairs once its contraction hierarchy is built. pandana stores weights with limited precision, so its lengths can differ by a fraction of a meter.

False ignores one-way restrictions.

With pairwise, an array with one length per pair. Otherwise a

DataFrame indexed by origin with one column per destination.

Unreachable pairs are inf.

If the matrix would exceed MAX_MATRIX_BYTES; split the origins into batches.

If a node ID is not in the network.

Origin node IDs.

Destination node IDs. With pairwise, origins[i] goes to destinations[i]; otherwise every origin goes to every destination, origin by origin.

Pair origins and destinations by position.

Edge column to minimise. The network's weight otherwise.

Return routes as lines with their lengths.

False ignores one-way restrictions.

A list of node ID lists, empty where there is no path. With

geometry, a GeoDataFrame with origin, destination,

length, nodes, and a LineString geometry (missing when

there is no path or the origin is the destination).

A long table with origin, node_id, and distance, sorted

by origin and distance; each distinct origin appears once, reaching

itself at distance 0.

Origin node IDs.

Target node IDs.

Number of targets per origin. k=1 is a single multi-source search from all targets.

Ignore targets farther than this.

A table with origin, target, and distance: one row per

origin for k=1 (target missing and distance inf when

none is reachable), and up to k rows per origin otherwise,

nearest first.

Counts indexed by origin ID, in the order given.

In a directed network, components in which every node can reach every other along one-way roads. Weak components ignore direction. The same for undirected networks.

Meters. Parts farther apart than this stay apart.

The network with the links added, or the same network when it is

already connected.

Node IDs to keep.

Edge columns to add up.

The simplified network, or the same network when no node can be removed.

Node IDs to join, such as schools.

Node IDs already connected to each other, such as fibre nodes. Reaching any root is enough.

"shortest_path" (the default): terminals connected one at a time, nearest first, to everything connected so far (Takahashi and Matsuyama). "steiner": Mehlhorn's approximation, faster and on roads a few percent longer. Both are Steiner tree approximations: with roots, a forest whose every tree reaches a root, so a terminal may connect through other terminals. "nearest_root": each terminal's shortest path to its nearest root. "all_pairs": the shortest paths between every terminal and every terminal and root; their number grows with the square of the terminals.

Edge column to minimise. The network's weight otherwise.

An undirected network. Terminals that cannot be connected are kept

without edges.

"shortest_path" (the default): Takahashi and Matsuyama's 2-approximation of the Steiner tree, and a model of a phased rollout: starting from the roots (or the first terminal), repeatedly connect the terminal nearest to anything connected so far, along its shortest path. Gives each terminal's order and marginal cost; ties go to the terminal listed first. On Kigali's roads it came within 0.7 to 6% of the optimum. "steiner": Mehlhorn's 2-approximation, with roots the rooted tree, without them the tree joining the terminals; 5 to 20 times faster, and 3 to 9% above the optimum on Kigali. :meth:improve brings either within about 1% of it. "nearest_root": each terminal's shortest path to its nearest root, and the union of those paths; needs roots, and never lets a terminal connect through another one. "all_pairs": the shortest paths between every terminal and every terminal or root; their number grows with the square of the terminals.

The plan. With roots, terminals that cannot reach any root, even

through bridges, are unreachable. Without roots, the plan joins the

terminals of the network's part that holds the most of them, and

the others are unreachable.

If the method is unknown, or is "nearest_root" without roots.