API reference - extras

The functions and classes documented in this section provide extra functionality that does not belong to the core of NoGraphs. NoGraphs can be fully used without them.

Gadgets for adapting edge data

Examples: See tutorial.

nographs.adapt_edge_index(index: Mapping[T_vertex, Iterable[T_vertex]], *, add_inverted: bool, attributes: Literal[False]) → Callable[[T_vertex, Any], Iterable[T_vertex]]

nographs.adapt_edge_index(index: Mapping[T_vertex, Iterable[OutEdge[T_vertex, T_weight, T_labels]]], *, add_inverted: bool, attributes: Literal[True]) → Callable[[T_vertex, Any], Iterable[OutEdge[T_vertex, T_weight, T_labels]]]

nographs.adapt_edge_index(index: Sequence[Iterable[T_vertex]], *, add_inverted: bool, attributes: Literal[False]) → Callable[[int, Any], Iterable[T_vertex]]

nographs.adapt_edge_index(index: Sequence[Iterable[OutEdge[int, T_weight, T_labels]]], *, add_inverted: bool, attributes: Literal[True]) → Callable[[int, Any], Iterable[OutEdge[int, T_weight, T_labels]]]

Read a graph from a Mapping (e.g. a Dict) or from a Sequence (e.g. a tuple or list, if integers are used as the vertices) and provide a neighbor function (NextVertices or NextEdges) from that data. Typically only used for test purposes.

Parameters:

index –
Mapping or Sequence with vertices as key, resp. as index. For each vertex, you provide:
- either an Iterable of adjacent vertices (this defines edges without edge attributes)
- or an Iterable of edges (with edge attributes) that start at this vertex. An edge to some neighbor (see outgoing edge) needs to be a Sequence of the form (neighbor, labels) or (neighbor, weight) or (neighbor, weight, labels).
attributes –
Give True, if index provides labeled or weighted edges. In this case, you can use the resulting neighbor function as NextEdges function.

Give False, if index provides neighbor vertices for a given vertex. In this case, you can use the resulting neighbor function as NextVertices function.
add_inverted –
If False, the resulting neighbor function will yield only the edges of index. If True, the function will also provide the same edges inverted (start and end vertex exchanged).

Note: when this option is used, a copy of your graph will be held by the returned neighbor function.

Returns:

Neighbor function that can be used as parameter for one of the traversal algorithms.

nographs.adapt_edge_iterable(edges: Iterable[AnyFullEdge[T_vertex, T_weight, T_labels]], *, add_inverted: bool, attributes: Literal[False]) → Callable[[T_vertex, Any], Iterable[T_vertex]]

nographs.adapt_edge_iterable(edges: Iterable[WeightedOrLabeledFullEdge[T_vertex, T_weight, T_labels]], *, add_inverted: bool, attributes: Literal[True]) → Callable[[T_vertex, Any], Iterable[OutEdge[T_vertex, T_weight, T_labels]]]

Read a graph from an Iterable of edges and provide a neighbor function (NextVertices or NextEdges) from that data. Typically only used for test purposes.

Parameters:

edges – The edges of your graph, each as Sequence (start_vertex, end_vertex, optional_attributes…), where edge data can be either a weight, or labels, or both (see WeightedOrLabeledFullEdge) or none (see AnyFullEdge).
attributes –
If set to True, the resulting neighbor function will yield edges with edge attributes for a given vertex and can be used as NextEdges function, but the edges of the given graph need to have attributes (WeightedOrLabeledFullEdge, not AnyFullEdge).

If set to False, it will yield neighbor vertices, and can be used as NextVertices function, and edge data that your edges may contain will be ignored.
add_inverted – If False, the resulting neighbor function will only yield for edges. If True, the function will also provide the same edges inverted (start and end vertex exchanged). Note: when this option is used, a copy of your graph will be held by the returned neighbor function.

Returns:

Neighbor function that can be used as parameter for one of the traversal algorithms. See OutEdge for the case of attributes.

Gadgets for adapting array data and positions

Examples: See tutorial.

Common types

nographs.Vector

alias of Sequence[int]

A vector can be used as parameter to methods of class Position and Array. In fact, a Position is itself a Vector, but with further functionality.

nographs.Limits

alias of Sequence[tuple[int, int]]

The lower (inclusive) and upper (exclusive) boundaries of the indices of an Array, given per dimension.

Position

Examples: See tutorial.

class nographs.Position(my_vector: Vector)

A position in an n-dimensional array. It is initialized by a Vector.

It is quite slow, due to its n-dimensional character.

classmethod at(*coordinates)

Factory method, that creates a position from coordinates given as separated parameters.

Parameters:: coordinates (int) –
Return type:: Position

__add__(other)

Add the other Vector to the position

Parameters:: other (Sequence[int]) –
Return type:: Position

__sub__(other)

Subtract the other Vector from the position.

Parameters:: other (Sequence[int]) –
Return type:: Position

__mul__(multiple)

Multiply each coordinate by the multiple, typically an integer.

Attention: 3*p means something else, see __rmul__.

Parameters:: multiple (SupportsIndex) –
Return type:: Position

manhattan_distance(other)

Manhattan distance of the other Vector from the given position vector.

Parameters:: other (Sequence[int]) –
Return type:: int

is_in_cuboid(limits)

Return true if each coordinate of the position is inside the respective range defined by the limits sequence (see Limits).

Parameters:: limits (Sequence[tuple[int, int]]) –
Return type:: bool

wrap_to_cuboid(limits)

If a coordinate of the position is outside its respective limit range (from, to) of the limits sequence (see Limits), add or subtract the size (to - from + 1) of the limit range as often as necessary to correct this.

Parameters:: limits (Sequence[tuple[int, int]]) –
Return type:: Position

static moves(dimensions=2, diagonals=False, zero_move=False, non_zero_counts=None)

Generate vectors of moves to neighbor positions in an n-dimensional Array, i.e., vectors with combinations of -1, 0 and 1 as coordinates, and return them in ascending order.

The number of occurring non-zero coordinates per move can be configured. Default: Only moves with exactly one non-zero coordinate are generated.

Parameters:

dimensions (int) – Number of dimensions of the generated move vectors.
diagonals (bool) – Add diagonal moves (moves with more than one non-zero coordinate).
zero_move (bool) – Add the zero move (0, …).
non_zero_counts (Container[int] | None) – All moves are allowed that have a number of non-zero coordinates as specified by non_zero_counts, e.g., non_zero_counts = {0, 1} equals zero_move = True. This option can not be combined with the options diagonals and zero_move.

Return type:

Sequence[Sequence[int]]

neighbors(moves, limits=None, wrap=False)

Iterate the positions that are reached by performing the given moves. Can limit or wrap moves at a cuboid.

Parameters:

moves (Iterable[Sequence[int]]) – They define what moves lead to neighbors (irrespective the optionally given limits).
limits (Sequence[tuple[int, int]] | None) – If given, they define the cuboid the generated positions have to stay in.
wrap (bool) – If True, moves to positions outside the limits cuboid are wrapped at this boundary. If False, such moves are ignored.

Return type:

Iterator[Position]

Array

Examples: See tutorial.

class nographs.Array(nested_sequences, dimensions=2)

An n-dimensional array.

Based on nested sequences that, up to a given number of dimensions, define its content. Data in nestings deeper than that is interpreted as part of the content of an array cell.

Coordinates of a position in the array are meant in the order from “outer” to “inner” sequences along the nesting. Coordinates used as arguments for Array methods can be given as Vector, especially as Position.

Parameters:

nested_sequences (Sequence[Any]) – Content of the array to be created.
dimensions (int) – Number of dimensions the array should have.

size()

Calculate the size of the array per dimension.

Return type:: Sequence[int]

limits()

Calculate coordinate limits (see Limits) per dimension as tuples (from, to). Since the array consists of nested sequences, from is always zero and to equals the size of the array in this dimension.

Return type:: Sequence[tuple[int, int]]

mutable_copy()

Create a mutable copy of the array.

Return type:: Array

__getitem__(position)

Get the content at the given position. This allows for using the expression syntax array[…].

Parameters:: position (Sequence[int]) – The content at this position Vector is returned.
Return type:: Any

__setitem__(position, content)

Set the content at the given position. Assumption: The nested sequence the array is build upon is mutable in its last dimension (i.e., a list). Allows for using the assignment syntax array[…] = … .

Parameters:

position (Sequence[int]) – The content at this position Vector is replaced.
content (Any) – This content is stored at the position.

Return type:

None

items()

Iterate positions and content.

Return type:: Iterator[tuple[Position, Any]]

findall(content)

Find content in array and return found positions.

Parameters:: content (Iterable[Any]) – Content to be searched.
Return type:: tuple[Position, …]

next_vertices_from_forbidden(forbidden, wrap=False, diagonals=False)

Return a NextVertices function for traversal strategies, based on given choice of when positions qualify as neighbors (goals of a move) of a given position (options wrap and diagonals) and whether such a move is allowed w.r.t. the content of the array at this position (parameter forbidden).

Parameters:

forbidden (Iterable[Hashable]) – A move to a position with this content is not allowed.
wrap (bool) – Positions are wrapped at the array limits.
diagonals (bool) – Diagonal moves are allowed.

Return type:

Callable[[Any, Any], Any]

next_edges_from_cell_weights(content_to_weight, wrap=False, diagonals=False)

Return a NextEdges function for traversal strategies, based on given choice of when positions qualify as neighbors (goals of a move) of a given position (options wrap and diagonals) and what weight such a move has w.r.t. the content of the matrix at this position (parameter content_to_weight, and no assigned weight means the move is impossible).

Parameters:

content_to_weight (Mapping[Any, T_weight]) – Returns the weight of a move to a given position.
wrap (bool) – Positions are wrapped at the array limits.
diagonals (bool) – Diagonal moves are allowed.

Return type:

Callable[[Position, Any], Iterable[tuple[Position, T_weight]]]

Traveling Salesman

The algorithm behind the functions described below is used in the tutorial for demonstration purposes.

Examples: See tutorial.

nographs.traveling_salesman_flex(vertices, weights, gear, find_longest=False)

Solve the traveling salesmen problem in directed graphs, in a slightly more general and flexible form than that of typical implementations. Performance has been a design goal.

Find the path with the shortest, resp. the longest, length (sum of edge weights) through the relevant vertices (at least two), where each of these vertices is visited exactly once, in the form of a loop.

If no solution can be found, raise a KeyError. If the problem is not well-defined, raise a RuntimeError.

Flexibility:

Vertices can be any object except for None.
Edge weights can be positive, negative or zero.
The graph does not need to be symmetric (symmetric means: for each edge (i, j, weight), an edge (j, i, weight) exists).
The graph does not need to be complete (complete means: from each vertex there is an edge to all other vertices) and the algorithms profits if the graph is not complete.
Self-loops (i.e., an edge from a vertex to itself) are allowed (and will be ignored)
Optionally, a longest path is searched, instead of a shortest.
Edges from and to irrelevant vertices are allowed (and will be ignored)

The function is an implementation of the algorithm shown in the tutorial, but it is based on the bidirectional search BSearchShortestPathFlex instead of the unidirectional traversal TraversalShortestPaths. And internally, it works with bit arrays instead of vertex sets.

Recipes for solving other, but similar problems:

Your graph has multi-edges (i.e., from two vertices v and w, there are several edges from v to w): Give only the edge with the lowest edge weight between such vertices v and w.
Your graph is undirected: Give each edge in both directions.
Vertices can be visited multiple times: Build the distance graph and give it as input instead of your original graph. The distance graph can be computed by applying the traversal strategy TraversalShortestPaths for each of the vertices. Then, each tuple (start_vertex, reached_vertex, distance) is an edge of the distance graph. Save these edges, and the respective paths. When the TSP is solved on the distance graph, replace each edge in the result by the respective path of the original graph.

Parameters:

vertices (Iterable[T_vertex]) – The computed circle need to go through each of them exactly once. See T_vertex.
weights (GettableProto[T_vertex, GettableProto[T_vertex, T_weight]]) – For each pair of vertices v and w, weights [v][w] is the weight of the edge from v to w, if the edge exists. Otherwise, a KeyError or an IndexError is raised, or None is returned. This allows for providing weights in nested tuples, lists or Mappings.
gear (Gear[int, int, T_weight, Any]) – The Gear to be used internally (where vertices and vertex ids are represented by integers).
find_longest (bool) – True means, find path with the longest instead of the shortest total distance

Returns:

Length of the found travel, and an iterator for the path of vertices.

Return type:

tuple[T_weight, Iterator[T_vertex]]

nographs.traveling_salesman(vertices, weights, find_longest=False)

Like traveling_salesman_flex, see there, but the gear is GearDefault, see also there.

Note: As usual with GearDefault, the type for weight results (here: the path length) is extended by float. In case of traveling_salesman, a float will never be returned, if your graph does not contain float edge weights and the arithmetic operations on edge weights that are used (see T_weight) do not return floats. The reason is, that unsolvable TSP problems raise a KeyError, instead of returning a infinite path length. Use traveling_salesman_flex and choose another Gear if you like to have a stricter type specification (see also tutorial section Usage in typed code).

Parameters:

vertices (Iterable[T_vertex]) – The computed circle need to go through each of them exactly once. See T_vertex.
weights (GettableProto[T_vertex, GettableProto[T_vertex, T_weight]]) – For each pair of vertices v and w, weights [v][w] is the weight of the edge from v to w, if the edge exists. Otherwise, a KeyError or an IndexError is raised, or None is returned. This allows for providing weights in nested tuples, lists or Mappings.
find_longest (bool) – True means, find path with the longest instead of the shortest total distance

Returns:

Length of the found travel, and an iterator for the path of vertices.

Return type:

tuple[Union[T_weight, float], Iterator[T_vertex]]

class nographs.GettableProto(Protocol[T_key_contra, T_value_co]))

Protocol for a subscriptable readable container.

Examples:

A dict[str, float] is a GettableProto[str, float]
A tuple[str, …] is a GettableProto[int, str]

abstract __getitem__(item)

Get the value that is stored for key item. If the Gettable does not contain item, a KeyError or an IndexError might be raised, or None is returned.

Parameters:: item (T_key_contra) –
Return type:: T_value_co | None

Shortest paths in infinitely branching graphs

The algorithm behind the classes described below is used in the tutorial for demonstration purposes.

Examples: See tutorial.

nographs.State: alias of tuple[T_vertex_id, int]

class nographs.TraversalShortestPathsInfBranchingSortedFlex(gear, internal_gear, next_edges)

Bases: Generic[T_vertex_id, T_weight],

Traversal [T_vertex_id, T_vertex_id, Any]

Parameters:

gear (Gear[T_vertex_id, T_vertex_id, T_weight, Any]) – See gears API and class Gear. Used for storing and returning results (graph data in the domain of the given problem).
internal_gear (Gear[tuple[~T_vertex_id, int], tuple[~T_vertex_id, int], T_weight, Any]) – See gears API and class Gear. Used for storing internal results (graph data in the domain of the problem, that the given problem is reduced to).
next_edges (Callable[[T_vertex_id, TraversalShortestPathsInfBranchingSortedFlex[T_vertex_id, T_weight]], Iterable[tuple[~T_vertex_id, ~T_weight] | tuple[~T_vertex_id, ~T_weight, Any]]]) – See NextWeightedEdges function. If None, provide next_labeled_edges.

Algorithm: Weighted shortest paths in infinitely branching graphs with sorted edges, implemented by problem reduction to a Dijkstra shortest paths problem.

Properties: Vertices are reported (and expanded) ordered by increasing distance (minimally necessary sum of edge weights) from a start vertex.

Input: Weighted directed graph. Weights need to be non-negative.

Infinite branching is allowed. The (possibly infinitely many) edges per vertex need to be given sorted by ascending length. The algorithm can only be used if for computing the next shortest path to be reported, in all cases, only a finite incremental search is necessary.

One or more start vertices. Vertices need to be hashable (a vertex is directly used as vertex id).

Labels of edges are allowed, but will be ignored. If path generation is demanded, labels and weights are not taken into the paths.

Search state: When a vertex is expanded (traversal calls next_edges or next_labeled_edges) or reported (an iterator of the traversal returns it), the traversal provides updated values for the attributes distance, paths, and distances.

Parameters:

labeled_edges – The element label of an edge is set for edges
is_tree – The traversal does not need to prevent re-visits
vertex_to_id – See VertexToID
gear (Gear[T_vertex_id, T_vertex_id, T_weight, Any]) –
internal_gear (Gear[tuple[~T_vertex_id, int], tuple[~T_vertex_id, int], T_weight, Any]) –
next_edges (Callable[[T_vertex_id, TraversalShortestPathsInfBranchingSortedFlex[T_vertex_id, T_weight]], Iterable[tuple[~T_vertex_id, ~T_weight] | tuple[~T_vertex_id, ~T_weight, Any]]]) –

distance: T_weight: The length of the shortest path (sum of edge weights) from a start vertex to the visited vertex

paths: Paths[T_vertex, T_vertex_id, T_labels]: The container paths holds the created paths, if path creation has been demanded. If labeled edges were provided (parameter next_labeled_edges), the paths contain them instead of just vertices.

distances: VertexIdToDistanceMapping[T_vertex_id, T_weight]: Final distance values of some vertices (distance from a start vertex). It is only filled if option store_distances is used. After an exhaustive search, the collection contains exactly and only the distances of all vertices that are reachable from the start vertices and of the start vertices themselves.

start_from(start_vertex=None, *, start_vertices=None, build_paths=False, combined_calculation_limit=None, store_distances=False)

Start the traversal at a vertex or a set of vertices and set parameters.

Parameters:

start_vertex (T_vertex_id | None) – The vertex the search should start at. If None, provide start_vertices.
start_vertices (Iterable[T_vertex_id] | None) – The set of vertices the search should start at. Only allowed if start_vertex equals None.
build_paths (bool) – If true, build paths from start vertices for each reported vertex, and an empty path for each start vertex. The class can only generate paths of unweighted and unlabeled paths.
combined_calculation_limit (int | None) – If provided, maximal number of vertices and edges in sum (note the difference here to the meaning of the option for other strategies!) to process (read in) from your graph. If it is exceeded, a RuntimeError will be raised.
store_distances (bool) – If True, the found distances of vertices are stored in traversal attribute distances. See attribute distances.

Returns:

Traversal, that has been started, e.g., the methods go* can now be used.

Return type:

TraversalShortestPathsInfBranchingSortedFlex[T_vertex_id, T_weight]

go_for_distance_range(start, stop)

For a started traversal, return an iterator. During the traversal, the iterator skips vertices as long as their distance is lower than start. From then on, is reports the found vertices. It stops when the reached distance is equal to or higher than stop.

Note: The first vertex with a distance equal or higher than stop will be consumed from the traversal, but will not be reported, so it is lost (compare itertools.takewhile).

Parameters:

start (T_weight) –
stop (T_weight) –

Return type:

Iterator[T_vertex]

class nographs.TraversalShortestPathsInfBranchingSorted(next_edges)

Bases: TraversalShortestPathsInfBranchingSortedFlex[T_vertex_id, Union[T_weight, float]]

Eases the use of TraversalShortestPathsInfBranchingSortedFlex for typical cases. For documentation of functionality and parameters, see there.

TraversalShortestPathsInfBranchingSorted[T_vertex_id, T_weight](
    *args, **keywords
)

is a short form for

 TraversalShortestPathsInfBranchingSortedFlex[
     T_vertex_id, Union[T_weight, float]],
](nog.vertex_as_id, nog.GearDefault(), nog.GearDefault(), *args, **keywords)

Implications:

GearDefault is used, see there how it and its superclass work
The used weights are defined by Union[T_weight, float], see GearDefault

Parameters:

labeled_edges – The element label of an edge is set for edges
is_tree – The traversal does not need to prevent re-visits
vertex_to_id – See VertexToID
next_edges (Callable[[T_vertex_id, TraversalShortestPathsInfBranchingSortedFlex[T_vertex_id, T_weight | float]], Iterable[tuple[~T_vertex_id, ~T_weight] | tuple[~T_vertex_id, ~T_weight, Any]]]) –