contrailopt.HorizontalDAG

class contrailopt.HorizontalDAG(*, lon: NDArray[floating], lat: NDArray[floating], adj_ptr: NDArray[int64], adj: NDArray[int64], edge_dist: NDArray[floating], h_origin: int, h_dest: int)

Directed graph on (lon, lat) nodes with CSR adjacency.

All geometry (distances, azimuths, interpolation, polygon exclusion) is computed on a sphere, not on a planar lon/lat grid.

__init__(*, lon: NDArray[floating], lat: NDArray[floating], adj_ptr: NDArray[int64], adj: NDArray[int64], edge_dist: NDArray[floating], h_origin: int, h_dest: int) → None

Methods

__init__(*, lon, lat, adj_ptr, adj, ...)
adjacency_matrix()	Return dense boolean adjacency matrix A where A[i, j] is True for i->j.
distance_matrix([missing])	Return dense distance matrix A where A[i, j] is the distance aong i->j.
edge_index(src, dst)	Return the CSR index of the directed edge (src, dst).
exclude_polygons(polygons)	Return a new DAG with edges crossing any polygon removed.
expand_neighbors(nodes)	Expand CSR adjacency for a batch of nodes into flat edge arrays.
from_network(lon, lat, tail, head[, ...])	Build a DAG from a static network graph using the dual azimuth constraint.
from_points(lon, lat[, origin_idx, ...])	Build a DAG from lon/lat arrays using the dual azimuth constraint.
from_poisson(origin_lon, origin_lat, ...)	Build a DAG from Poisson-disk sampled points along the OD great circle.
neighbors(i)	Return the neighbors of a specified node.
neighbors_batch(nodes)	Return neighbors (duplicates included with multiplicity) for a batch of nodes.
plot([ax, linewidth, show_edges])	Plot the DAG on a cartopy map.
prune_edges(degree)	Keep the best degree outgoing and incoming edges per node.
prune_unreachable()	Return a new DAG with only nodes reachable from origin that also reach dest.
reverse()	Return a new DAG with all edge directions flipped and origin/dest swapped.
sample_edges(spacing_m)	Sample points along every edge at most spacing_m meters apart.
topo_wavefronts()	Yield topological wavefronts reachable from origin.

Attributes

lon	Longitude of each node in degrees (n,).
lat	Latitude of each node in degrees (n,).
adj_ptr	CSR row pointers (n + 1,).
adj	Neighbor (destination) indices for each directed edge (m,).
edge_dist	Great-circle distance in meters for each directed edge (m,).
h_origin	Index of the distinguished origin node.
h_dest	Index of the distinguished destination node.
crosses_antimeridian	Determine if the great circle between origin and destination crosses the antimeridian.
edge_src	The source endpoint index of each directed edge.
edges	The directed edges of the graph as (src, dest) index pairs in an (m, 2) array.
n_edges	The number of directed edges in the graph.
n_nodes	The number of nodes in the graph.
out_degree	The out-degree of each node.

lon: NDArray[floating]

Longitude of each node in degrees (n,). Assumed to be in the range [-180, 180). (This assumption is used in crosses_antimeridian()).

lat: NDArray[floating]

Latitude of each node in degrees (n,). Assumed to be in the range [-90, 90].

adj_ptr: NDArray[int64]

CSR row pointers (n + 1,). Neighbors of node i are adj[adj_ptr[i]: adj_ptr[i+1]].

adj: NDArray[int64]

Neighbor (destination) indices for each directed edge (m,).

edge_dist: NDArray[floating]

Great-circle distance in meters for each directed edge (m,).

h_origin: int

Index of the distinguished origin node.

h_dest: int

Index of the distinguished destination node.

property n_nodes: int

The number of nodes in the graph.

property n_edges: int

The number of directed edges in the graph.

property out_degree: NDArray[int64]

The out-degree of each node.

property edge_src: NDArray[int64]

The source endpoint index of each directed edge.

property edges: NDArray[int64]

The directed edges of the graph as (src, dest) index pairs in an (m, 2) array.

property crosses_antimeridian: bool

Determine if the great circle between origin and destination crosses the antimeridian.

neighbors(i: int) → NDArray[int64]

Return the neighbors of a specified node.

edge_index(src: int, dst: int) → int

Return the CSR index of the directed edge (src, dst).

Performs a linear scan over the neighbors of src. This could be replaced with np.searchsorted() if needed, but that would require enforcing sorted neighbors during construction.

Raises:

ValueError – If no edge from src to dst exists.

neighbors_batch(nodes: NDArray[int64]) → NDArray[int64]

Return neighbors (duplicates included with multiplicity) for a batch of nodes.

expand_neighbors(nodes: NDArray[int64]) → tuple[NDArray[int64], NDArray[floating], NDArray[int64], NDArray[int64]]

Expand CSR adjacency for a batch of nodes into flat edge arrays.

Returns:

• flat_nbr (numpy.ndarray) – (e,) neighbor indices for all edges leaving nodes.

• flat_dist (numpy.ndarray) – (e,) edge distances in meters.

• src_idx (numpy.ndarray) – (e,) index into nodes for each flat entry, so nodes[src_idx[k]] is the source node of flat edge k.

• flat_edge_idx (numpy.ndarray) – (e,) index of each edge in the CSR arrays (adj, edge_dist).

  Here e = out_degree[nodes].sum(), the total number of outgoing edges from all nodes.

adjacency_matrix() → NDArray[bool]

Return dense boolean adjacency matrix A where A[i, j] is True for i->j.

distance_matrix(missing: float = inf) → NDArray[floating]

Return dense distance matrix A where A[i, j] is the distance aong i->j.

Distances are set to infinity by default where edges are missing.

reverse() → Self

Return a new DAG with all edge directions flipped and origin/dest swapped.

prune_unreachable() → Self

Return a new DAG with only nodes reachable from origin that also reach dest.

prune_edges(degree: int) → Self

Keep the best degree outgoing and incoming edges per node.

Each edge is scored by the sum of its azimuth deviations: how far the edge direction deviates from the azimuth toward the destination (at the tail) plus how far the reverse deviates from the azimuth toward the origin (at the head). An edge is kept if it ranks among the best degree outgoing edges of its source or among the best degree incoming edges of its destination.

Parameters:

degree (int) – Number of outgoing and incoming edges to keep per node.

Returns:

A new DAG with at most degree outgoing and incoming edges per node.

Return type:

Self

exclude_polygons(polygons: list[list[tuple[float, float]]]) → Self

Return a new DAG with edges crossing any polygon removed.

Uses spherely for geodesic intersection tests on the sphere.

Parameters:

polygons (list[list[tuple[float, float]]]) – List of polygons, where each polygon is a list of (lon, lat) vertices.

Returns:

A new DAG with offending edges removed and then pruned.

Return type:

HorizontalDAG

sample_edges(spacing_m: float) → tuple[NDArray[floating], NDArray[floating], NDArray[int64], NDArray[int64]]

Sample points along every edge at most spacing_m meters apart.

Points are uniformly spaced along each edge, and both edge endpoints (source and destination nodes) are included as samples.

Returns:

• sample_lon (numpy.ndarray) – (s,) longitude of each sample point.

• sample_lat (numpy.ndarray) – (s,) latitude of each sample point.

• edge_idx (numpy.ndarray) – (s,) edge index for each sample point.

• edge_ptr (numpy.ndarray) – (m + 1,) CSR-style pointer so edge i’s samples are at sample_lon[edge_ptr[i]: edge_ptr[i+1]].

  Here s = edge_ptr[-1], the total number of sample points across all edges.

plot(ax: GeoAxes | None = None, linewidth: float = 2.0, show_edges: bool = True) → GeoAxes

Plot the DAG on a cartopy map.

classmethod from_network(lon: NDArray[floating], lat: NDArray[floating], tail: NDArray[int64], head: NDArray[int64], origin_idx: int = 0, dest_idx: int = -1, max_angle_deg: float = 40.0) → Self

Build a DAG from a static network graph using the dual azimuth constraint.

classmethod from_points(lon: NDArray[floating], lat: NDArray[floating], origin_idx: int = 0, dest_idx: int = -1, max_angle_deg: float = 40.0, max_dist_m: float = 500000.0) → Self

Build a DAG from lon/lat arrays using the dual azimuth constraint.

classmethod from_poisson(origin_lon: float, origin_lat: float, dest_lon: float, dest_lat: float, poisson_spacing_m: float = 80000.0, max_cross_track: float | None = None, max_angle_deg: float = 40.0, max_dist_m: float = 500000.0, dtype: type[floating] = <class 'numpy.float64'>, rng: Generator | None = None) → Self

Build a DAG from Poisson-disk sampled points along the OD great circle.

topo_wavefronts() → Generator[NDArray[int64], None, None]

Yield topological wavefronts reachable from origin.

Only nodes reachable from h_origin are emitted. Unreachable nodes (those with incoming edges from outside the reachable subgraph) are excluded.

The first wavefront contains only the origin. Wavefront k contains nodes whose reachable in-degree drops to zero after removing wavefronts 0 … k-1.