pyorps.graph.api.graph_library_api

PYORPS: An Open-Source Tool for Automated Power Line Routing

Reference: [1] Hofmann, M., Stetz, T., Kammer, F., Repo, S.: ‘PYORPS: An Open-Source Tool for

Automated Power Line Routing’, CIRED 2025 - 28th Conference and Exhibition on Electricity Distribution, 16 - 19 June 2025, Geneva, Switzerland

This file contains the abstract base class for the interface to the graph libraries. All specific graph library interfaces should inherit from this class. The workflow of the specific interfaces are determined by the respective graph library. The workflow of the graph libraries can vary!

  • For rustworkx and igraph the nodes need to be created before the edges can be added

  • For networkit and networkx the edges can be added on the fly when adding the nodes

  • For rustworkx and igraph the edges can only be added as a list of tuples. This means

that the edge information as retrieved by numpy arrays, need to be converted into a list, which leads to a much higher (more than double) memory usage! - For networkit and networkx edges can be added as a sparse matrix or as numpy arrays

Please see the specific interfaces to the specific graph libraries for more details!

Classes

GraphLibraryAPI(raster_data, steps[, ...])

Base class for all graph library-based APIs.
class pyorps.graph.api.graph_library_api.GraphLibraryAPI(raster_data, steps, ignore_max=True, from_nodes=None, to_nodes=None, cost=None, **kwargs)[source]

Bases: GraphAPI

Base class for all graph library-based APIs.

This class extends GraphAPI with common functionality needed by standard graph libraries that require edge data to be explicitly provided and a graph to be constructed.

Initialize the graph library API.

Parameters:

  • raster_data (ndarray[int]) – 2D numpy array representing the raster

  • steps (ndarray[int]) – Array defining the neighborhood connections

  • ignore_max (bool | None) – Ignore edges whose weights are greater or equal to the maximum

  • data (value in the raster)

  • from_nodes (ndarray | None) – Source node indices for edges

  • to_nodes (ndarray | None) – Target node indices for edges

  • cost (ndarray | None) – Edge weights

__init__(raster_data, steps, ignore_max=True, from_nodes=None, to_nodes=None, cost=None, **kwargs)[source]

Initialize the graph library API.

Parameters:

  • raster_data (ndarray[int]) – 2D numpy array representing the raster

  • steps (ndarray[int]) – Array defining the neighborhood connections

  • ignore_max (bool | None) – Ignore edges whose weights are greater or equal to the maximum

  • data (value in the raster)

  • from_nodes (ndarray | None) – Source node indices for edges

  • to_nodes (ndarray | None) – Target node indices for edges

  • cost (ndarray | None) – Edge weights

abstractmethod create_graph(from_nodes, to_nodes, cost=None, **kwargs)[source]

Creates a graph object with the graph library specified in the selected interface.

Parameters:

  • from_nodes (ndarray[int]) – The starting node indices from the edge data

  • to_nodes (ndarray[int]) – The ending node indices from the edge data

  • cost (ndarray[int] | None) – The weight of the edge data

  • kwargs – Additional parameters for the underlying graph library

Returns:

The graph object

Return type:

Any

abstractmethod get_number_of_nodes()[source]

Returns the number of nodes in the graph.

Returns:

The number of nodes

Return type:

int

abstractmethod get_number_of_edges()[source]

Returns the number of edges in the graph.

Returns:

The number of edges

Return type:

int

abstractmethod remove_isolates()[source]

If the graph object was initialized with the maximum number of nodes, this function helps to reduce the occupied memory by removing nodes without any edge (degree == 0).

Returns:

None

Return type:

None

abstractmethod get_nodes()[source]

This method returns the nodes in the graph as a list or numpy array of node indices.

Returns:

List or array of node indices of the nodes in the graph

Return type:

List[int] | ndarray

shortest_path(source_indices, target_indices, algorithm='dijkstra', **kwargs)[source]

This method applies the specified shortest path algorithm on the created graph object and finds the shortest path between source(s) and target(s) as a list of node indices.

Parameters:

  • source_indices (int | int32 | int64 | uint32 | uint64 | list[int | int32 | int64 | uint32 | uint64] | ndarray[int] | None) – Index or indices of source node(s) (int or list[int])

  • target_indices (int | int32 | int64 | uint32 | uint64 | list[int | int32 | int64 | uint32 | uint64] | ndarray[int] | None) – Index or indices of target node(s) (int or list[int])

  • algorithm (str) – Algorithm to use for shortest path computation. Options depend on the specific library implementation.

  • kwargs – Additional parameters for specific algorithms library including

  • and (specific keywords) – “pairwise”: If True, compute pairwise shortest paths between source_indices and target_indices. Only allowed if len(source_indices) == len(target_indices)

Returns:

List of node indices representing the shortest path(s)

Return type:

list[int | int32 | int64 | uint32 | uint64] | ndarray[int] | list[list[int | int32 | int64 | uint32 | uint64] | ndarray[int]]

get_a_star_heuristic(target, source=None, **kwargs)[source]

Calculate the A* heuristic based on the Euclidean distance from the target node.

Parameters:

  • target (int | int32 | int64 | uint32 | uint64) – The index of the target node in the raster data

  • source (int | int32 | int64 | uint32 | uint64 | None) – Optional source node for calculating area-specific minimum values

  • kwargs – Additional parameters, including optional heu_weight for scaling

Returns:

  • An array of node indices in the graph

  • An array of heuristic values corresponding to each node

Return type:

tuple containing

get_advanced_a_star_heuristic(target, source=None, **kwargs)[source]

Calculate the A* heuristic based on the Euclidean distance from the target node.

Parameters:

  • target (int | int32 | int64 | uint32 | uint64) – The index of the target node in the raster data

  • source (int | int32 | int64 | uint32 | uint64 | None) – Optional source node for calculating area-specific minimum values

  • kwargs – Additional parameters, including optional heu_weight for scaling

Returns:

  • An array of node indices in the graph

  • An array of heuristic values corresponding to each node

Return type:

tuple containing