API reference - NoGraphs

Type variables for graph adaptation

The algorithms, data structures and extension features of NoGraphs are able to handle vertices, vertex ids, weights and edge labels of different data types. In order to specify their capabilities and typing relationships optimally, the respective classes of NoGraphs are generic, and parameterized by the following type variables.

Example: When you choose bookkeeping collections for a specific use case (gears) that are limited to specific data types, plugging them into some graph analysis strategy will transfer these restrictions to the input and output types of the analysis. The type variables used in the API of NoGraphs document this relationship, and, optionally, you can use a type checker to check if your application correctly handles them.

nographs.T_vertex = TypeVar("T_vertex")

You can use anything as vertex, with the exception of None. (This exception cannot be expressed as type bound of a TypeVar. The requirement is checked at runtime.)

Please note: The generic classes of NoGraphs, that have T_vertex as parameter, might impose further restrictions on the possible types of vertices, by using T_vertex as argument for a type parameter of a superclass where this parameter has a type bound. See the documentation of the classes you use.

Examples: See section vertices of the tutorial.

nographs.T_vertex_id = TypeVar("T_vertex_id", bound=Hashable)

A vertex id is a hashable object that identifies a vertex (see VertexToID function).

Examples: See the section about vertex identity in the tutorial.

nographs.T_weight = TypeVar("T_weight", bound=Weight)

As type of weights of edges, you can choose any subtype of protocol Weight. For the current version of NoGraphs, it is defined as follows:

T = TypeVar("T")

class Weight(Protocol):
    @abstractmethod
    def __add__(self: T, value: T) -> T: ... # self + value
    @abstractmethod
    def __sub__(self: T, value: T) -> T: ... # self - value
    @abstractmethod
    def __lt__(self: T, value: T) -> bool: ...  #  self<value
    @abstractmethod
    def __le__(self: T, value: T) -> bool: ...  #  self<=value

Please note, that the gear (combination of bookkeeping collections) you use might have additional requirements w.r.t. edge weights. If you manually set a gear, see its documentation for this aspect. Traversal or search strategy classes, that do not allow to change the gear, use GearDefault. If you use one of them, see the documentation of this gear for its restrictions and for examples of typical weight types for it.

Examples: See section edge weights in the tutorial.

nographs.T_labels = TypeVar("T_labels"): Labels of edges can be provided as any kind of object, e.g., as a dictionary holding key/value pairs, as just a number for numbering edges, or as a string for naming an edge.

Tip

Tutorial section Usage in typed code gives a first idea of how NoGraphs can be used in typed code.

Function signatures for graph adaptation

Based on the type variables for graph adaptation, NoGraphs defines some signatures for callback functions that application code can provide to NoGraphs for graph adaptation.

Vertex identity

nographs.VertexToID

alias of Callable[[T_vertex], T_vertex_id]

For a given vertex, return a hashable object that identifies the vertex.

A function with this signature can be used by application code as parameter vertex_to_id when creating a Traversal of one of the “Flex” classes (see tutorial section vertex identity).

A VertexToID function defines the identity of vertices (or of equivalence classes of vertices) in your graph as follows: NoGraphs regards two vertices as the same vertex (“the same”, or “equivalent”) if and only if the objects returned by the used VertexToID function (the identifiers) for the vertices are equal (in the sense of Python’s equality comparison).

Typical use cases:

a) You want to use objects, that are not hashable, as you vertices. The identifiers will stand in for the vertices when hashes are needed.

b) You group vertices into equivalence classes and for each class of vertices, the Traversal algorithm should treat the vertices in the class as being the same vertex. Here, you define the function such that it calculates a hashable identifier of the equivalence class of the vertex given as parameter.

The identifiers will not only be used internally by a Traversal, but they will also replace your vertices as keys in sets or mappings used as externally accessible traversal attributes. In this case, this effect is documented for the traversal class.

Example: See tutorial.

NoGraphs provides the following default implementation of a VertexToID function:

nographs.vertex_as_id(vertex)

Return the vertex unchanged as vertex id.

In practice, this function is used as default VertexToID function to signal that a vertex can be directly used as its vertex id (semantically and w.r.t. typing) in the given use case.

At runtime, the library skips calling the function and replaces the call by a type cast from T_vertex to T_vertex_id.

Parameters:: vertex (T_vertex_id) – Is returned as vertex id.
Return type:: T_vertex_id

Outgoing edges

For a given vertex, the edges that start at this vertex can be described as tuples. The building rules of NoGraphs for such outedge tuple structures are:

The first element is always the vertex the edge leads to.
Then, in some cases, a weight value follows.
Then, in some cases, an object that represents edge labels follows.
The vertex is not the only element of the edge (because otherwise, we just use the vertex itself instead of a tuple).

This leads to the following structures that are used in the signatures of NoGraphs:

nographs.UnweightedLabeledOutEdge: alias of tuple[T_vertex, T_labels]

nographs.WeightedUnlabeledOutEdge: alias of tuple[T_vertex, T_weight]

nographs.WeightedLabeledOutEdge: alias of tuple[T_vertex, T_weight, T_labels]

Next vertices and next edges functions

Application code can use a function (“adjacency function”) to inform NoGraphs about the outgoing edges that start at some vertex. The signature of such a function needs to have a special structure:

The first argument is always the current vertex (outgoing edges from this vertex will be reported to NoGraphs)
The second argument is always the current strategy object (see tutorial section about search-aware graphs)

In the following, type variable T_strategy is used as placeholder for the type of the strategy object (traversal strategy, resp. search strategy).

nographs.T_strategy = TypeVar("T_strategy", bound=Strategy)
The result needs to be iterable.
- Either it iterates just the vertices the edges lead to.
- Or it iterates the edges described by tuples (see section outgoing edges).
  
  Application code might need to provide a weight (because the used traversal or search strategy requires it) or an edge label object (because it guarantees this to the strategy so that this data is included in results of the traversal or search). In these cases, the weight, resp. the edge label object, needs to be of the proper types (as needed by the strategy or as declared in typed code).
  
  If such data is provided without such need, it can be of arbitrary types.

These building rules lead to the following combinations of signature elements:

Adjacency functions for strategies that accept edges with and without weights:

nographs.NextVertices

alias of Callable[[T_vertex, T_strategy], Iterable[T_vertex]]

For a given vertex and a Traversal, report (positively) connected neighbor vertices.

nographs.NextEdges: alias of Callable[[T_vertex, T_strategy], Iterable[Union[

WeightedUnlabeledOutEdge [T_vertex, Any],

UnweightedLabeledOutEdge [T_vertex, Any],

WeightedLabeledOutEdge [T_vertex, Any, Any]]]]

Like NextVertices, but instead of connected vertices, return outgoing edges with or without weights and with or without labels, and the weight and labels can be of arbitrary type (not need to match the types used to instantiate the strategy), because the strategy will ignore weights and labels.

nographs.NextLabeledEdges: alias of Callable[[T_vertex, T_strategy], Iterable[Union[

WeightedLabeledOutEdge [T_vertex, Any, T_labels],

UnweightedLabeledOutEdge [T_vertex, T_labels]]

Here, a labels object must be given, and it needs to match the edge data type used to instantiate the strategy in order to ensure correct functioning of NoGraphs.

Adjacency functions for strategies that accept only edges with weights:

nographs.NextWeightedEdges: alias of Callable[[T_vertex, T_strategy], Iterable[Union[

WeightedUnlabeledOutEdge [T_vertex, T_weight],

WeightedLabeledOutEdge [T_vertex, T_weight, Any]]]]

Here, a weight must be given, and it needs to match the weight type used to instantiate the strategy in order to ensure correct functioning of NoGraphs. Labels are not necessary, and if given, can have arbitrary type.

nographs.NextWeightedLabeledEdges: alias of callable[[T_vertex, T_strategy], Iterable[

WeightedLabeledOutEdge [T_vertex, T_weight, T_labels]]]

Here, both a weight and labels must be given, and they need to match the weight and labels types used to instantiate the strategy in order to ensure correct functioning of NoGraphs.

Adjacency functions for bidirectional search strategies:

Here, two adjacency functions of the same type are needed, one for reporting outedges from a given vertex, and one for reporting inedges leading to a given vertex.

nographs.BNextVertices: alias of tuple[

NextVertices [T_vertex, T_strategy],

NextVertices [T_vertex, T_strategy],

]

nographs.BNextEdges: alias of tuple[

NextEdges [T_vertex, T_strategy],

NextEdges [T_vertex, T_strategy],

]

nographs.BNextLabeledEdges: alias of tuple[

NextLabeledEdges [T_vertex, T_strategy, T_labels],

NextLabeledEdges [T_vertex, T_strategy, T_labels],

]

nographs.BNextWeightedEdges: alias of tuple[

NextWeightedEdges [T_vertex, T_strategy, T_weight],

NextWeightedEdges [T_vertex, T_strategy, T_weight],

]

nographs.BNextWeightedLabeledEdges: alias of tuple[

NextWeightedLabeledEdges [T_vertex, T_strategy, T_weight, T_labels],

NextWeightedLabeledEdges [T_vertex, T_strategy, T_weight, T_labels],

]

Edges as part of trees or paths

NoGraphs computes trees and paths consisting of edges and returns them with the data you request. Accordingly, such edges can have weights, labels, both, or none of these:

nographs.UnweightedUnlabeledFullEdge: alias of tuple[T_vertex, T_vertex]

nographs.UnweightedLabeledFullEdge: alias of tuple[T_vertex, T_vertex, T_labels]

nographs.WeightedUnlabeledFullEdge: alias of tuple[T_vertex, T_vertex, T_weight]

nographs.WeightedLabeledFullEdge: alias of tuple[T_vertex, T_vertex, T_weight, T_labels]

Sometimes, it is optional whether you provide labels for an edges or not, and NoGraphs returns the edges as part of computed results with our without labels:

nographs.WeightedFullEdge: alias of Union[

WeightedUnlabeledFullEdge [T_vertex, T_weight],

WeightedLabeledFullEdge [T_vertex, T_weight, T_labels]]

nographs.WeightedOrLabeledFullEdge: alias of Union[

UnweightedLabeledFullEdge [T_vertex, T_labels],

WeightedUnlabeledFullEdge [T_vertex, T_weight],

WeightedLabeledFullEdge [T_vertex, T_weight, T_labels]]

nographs.AnyFullEdge: alias of Union[

UnweightedUnlabeledFullEdge [T_vertex],

WeightedUnlabeledFullEdge [T_vertex, T_weight],

UnweightedLabeledFullEdge [T_vertex, T_labels],

WeightedLabeledFullEdge [T_vertex, T_weight, T_labels],

Traversal and search strategies

class nographs.Strategy

Base class of the traversal strategies and search strategies of NoGraphs.

state_to_str(vertices=None)

Return a human-readable description of the public state of the strategy as a string.

If an attribute of the traversal is a containers that cannot iterate its content, or a collection that guarantees for the validity of stored results only for keys that are already visited vertices (see the API reference of the traversal classes), its content is only described for vertices given as parameter vertices.

Implementation details, not covered by the semantic versioning:

Currently, the method aims at providing a uniform behaviour over different platforms (CPython, PyPy, and MyPyC) and collection types (Gears with different MutableSet and MutableMapping implementations). It behaves roughly as follows:

A MutableSet, e.g. attribute visited, is described similar to a set, but items are sorted lexicographically in their string representations (this bridges differences between CPython and PyPy).
Attribute Paths is described similar to a dict (although keys can contain unhashable values, and only paths for the given vertices are described).
A MutableMapping, e.g. attribute distance, is described similarly to a dict, also in cases, where it is not a dict, and although the items for only the given vertices are described.

Parameters:: vertices (Iterable[T_vertex] | None) – If the strategy can provide additional state data w.r.t. these vertices, it will do so.
Return type:: str

See traversal strategies and search strategies.

Traversal strategies

Common methods

class nographs.Traversal

Abstract Class. Its subclasses provide methods to iterate through vertices and edges using some specific traversal strategies.

Bases: Strategy [T_vertex, T_vertex_id, T_labels]

__iter__()

Return the iterator of a started traversal. This allows for using a Traversal in for loops or as parameter to a call of function next().

Subsequent calls return the same iterator again. This allows for using the same Traversal in subsequent for loops or next() calls, as long as the iterator is not exhausted.

The iterator yields vertices reported by the traversal algorithm. When a vertex is reported, specific attributes of the traversal object contain additional data about the state of the traversal (see the API documentation of the respective subclass of Traversal).

Return type:: Iterator[T_vertex]

__next__()

Returns the next vertex reported by the (started) traversal. This allows for calls like next(traversal).

Delegates to the iterator of the traversal.

Return type:: T_vertex

go_for_vertices_in(vertices, fail_silently=False)

For a started traversal, return an iterator that fetches vertices from the traversal, reports a vertex if it is in vertices, and stops when all the vertices have been found and reported.

If the iterator has no more vertices to report (graph is exhausted) without having found all the vertices, KeyError is raised, or the traversal just terminates, if a silent fail is demanded.

If vertices does not provide any vertices, an empty iterator is returned.

If a VertexToID function is used, the method searches for vertices that have the same id as one of the vertices.

Whenever a vertex is reported, specific attributes of the traversal object contain additional data about the state of the traversal (see the API documentation of the respective subclass of Traversal).

Parameters:

vertices (Iterable[T_vertex]) – Vertices to find
fail_silently (bool) – Terminate, but do not raise KeyError, when graph is exhausted.

Return type:

Iterator[T_vertex]

go_to(vertex: T_vertex, fail_silently: Literal[False] = False) → T_vertex

go_to(vertex: T_vertex, fail_silently: Literal[True]) → T_vertex | None

For a started traversal, walk through the graph, stop at vertex and return it. If the traversal ends (traversal iterator is exhausted) without having found vertex, raise KeyError, or return None, if a silent fail is demanded.

If a VertexToID function is used, the method searches for a vertex that has the same id as the given vertex.

When vertex is reported, specific attributes of the traversal object contain additional data about the state of the traversal (see the API documentation of the respective subclass of Traversal).

Parameters:

vertex – Stop search at this vertex.
fail_silently – Terminate and return None, but do not raise KeyError, when graph is exhausted.

Traversal classes for all graphs

TraversalBreadthFirst

Examples: See Breadth First Search in a maze, Breadth First Search for the Towers of Hanoi, the comparing examples here, and an example for method go_for_depth_range.

class nographs.TraversalBreadthFirstFlex(vertex_to_id, gear, next_vertices=None, *, next_edges=None, next_labeled_edges=None, is_tree=False)

Bases: Traversal [T_vertex, T_vertex_id, T_labels]

Parameters:

vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.
gear (GearWithoutDistances[T_vertex, T_vertex_id, T_labels]) – See gears API and class GearWithoutDistances.
next_vertices (Callable[[T_vertex, TraversalBreadthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[T_vertex]] | None) – See NextVertices function. If None, provide next_edges or next_labeled_edges.
next_edges (Callable[[T_vertex, TraversalBreadthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) – See NextEdges function. Only allowed if next_vertices equals None. If both are None, provide next_labeled_edges.
next_labeled_edges (Callable[[T_vertex, TraversalBreadthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) – See NextLabeledEdges function. Only allowed if next_vertices and next_edges equal None. If given, paths will record the given labels.
is_tree (bool) – bool: If it is certain, that during each traversal run, each vertex can be reached only once, is_tree can be set to True. This improves performance, but attribute visited of the traversal will not be updated during and after the traversal.

Algorithm: Breadth First Search (“BFS”), non-recursive implementation. Vertices are reported when they are “seen” (read from the graph) for the first time.

Properties: Reports vertices in Breadth First order, i.e., with ascending depth (edge count of the path with the fewest edges from a start vertex). All computed paths are shortest paths , i.e., paths with minimal number of edges from a start vertex to their end vertex.

A vertex is considered visited when it has been reported or if it is a start vertex.

Input: Directed graph. Unlabeled or labeled edges. One or more start vertices. Optional calculation limit.

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

Parameters:

edges_with_data – Edges tuples, not just successor vertices
gear (GearWithoutDistances[T_vertex, T_vertex_id, T_labels]) – The traversal will use this gear
vertex_to_id (Callable[[T_vertex], T_vertex_id]) –
next_vertices (Callable[[T_vertex, TraversalBreadthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[T_vertex]] | None) –
next_edges (Callable[[T_vertex, TraversalBreadthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalBreadthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) –
is_tree (bool) –

For the other parameters, see super class.

depth: int

At this search depth, the reported (resp. the expanded) vertex has been found. It equals the length (number of edges) of the created path to the vertex, if path creation is demanded.

For the special case of this traversal, it equals the depth of the vertex (minimal number of edges needed to come to it from a start vertex). When a traversal has been started, but no vertex has been reported or expanded so far, the depth is 0 (depth of the start vertices).

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.

visited: VertexIdSet[T_vertex_id]: A collection that contains the visited vertices (resp. their hashable ids from vertex_to_id). After an exhaustive search, it contains the vertices (resp. vertex ids) reachable from the start vertices.

start_from(start_vertex=None, *, start_vertices=None, build_paths=False, calculation_limit=None, already_visited=None, _report_depth_increase=False)

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

Parameters:

start_vertex (T_vertex | None) – The vertex the search should start at. If None, provide start_vertices.
start_vertices (Iterable[T_vertex] | None) – The vertices the search should start at. Only allowed if start_vertex equals None.
build_paths (bool) – If true, build paths from some start vertex to each visited vertex. Paths of start vertices are empty paths.
calculation_limit (int | None) – If provided, maximal number of vertices to process (read in) from your graph. If it is exceeded, a RuntimeError will be raised.
already_visited (MutableSet[T_vertex_id] | None) – If provided, this set is used instead of an internal one to keep vertices (resp. their hashable ids from vertex_to_id), that have already been visited. This parameter can be used to get online access to the internal bookkeeping of visited vertices, or to preload vertices that should never be visited, or to provide your own way for storing the information that a vertex has already been visited.
_report_depth_increase (bool) –

Returns:

Traversal, that has been started, e.g., statements like iter(), next(), for and the methods “go*” of the Traversal can now be used.

Return type:

TraversalBreadthFirstFlex[T_vertex, T_vertex_id, T_labels]

go_for_depth_range(start, stop)

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

Note: The first vertex with a depth 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 (int) – Vertices lower than this are skipped.
stop (int) – Reporting stops when reached depth is equal or higher than this.

Return type:

Iterator[T_vertex]

class nographs.TraversalBreadthFirst(next_vertices=None, *, next_edges=None, next_labeled_edges=None, is_tree=False)

Bases: Generic[T_vertex, T_labels], TraversalBreadthFirstFlex[T_vertex, T_vertex, T_labels]

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

Uses the following standard arguments for the respective parameters of the parent class:

vertex_to_id = vertex_as_id
gear = GearDefault
T_vertex_id = T_vertex

Implications:

GearDefault is used, see there how it and its superclass work
T_vertex is bound to Hashable (T_vertex is used as T_vertex_id, see there)

Parameters:

edges_with_data – Edges tuples, not just successor vertices
gear – The traversal will use this gear
next_vertices (Callable[[T_vertex, TraversalBreadthFirstFlex[T_vertex, T_vertex, T_labels]], Iterable[T_vertex]] | None) –
next_edges (Callable[[T_vertex, TraversalBreadthFirstFlex[T_vertex, T_vertex, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalBreadthFirstFlex[T_vertex, T_vertex, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) –
is_tree (bool) –

For the other parameters, see super class.

TraversalDepthFirst

Enumerations used in the definition of parameters:

class nographs.DFSEvent(value)

An enumeration of the events that can trigger the report of a vertex / edge by TraversalDepthFirst.

Events reporting that a vertex is entered or left:

ENTERING_START: A start vertex has been entered and the traversal starts there.
LEAVING_START: A start vertex has been left (the traversal may continue with the next one).
ENTERING_SUCCESSOR: A vertex is entered, when an edge that leads to it is followed. In mode DFS_TREE, only DFS-tree edges are followed.
LEAVING_SUCCESSOR: A vertex is left, when an edge that leads to it and has been followed, is now followed in reversed direction, during backtracking from the edge. In mode DFS_TREE, only DFS-tree edges are followed.

Events reporting that a vertex (or an edge) has been detected but will not be entered (resp. followed):

SKIPPING_START: A start vertex was about to be entered, as start of a traversal from there, but it has already been visited as descendant of another start vertex, and thus, it is skipped.
BACK_EDGE: An edge (u, v) is found, where v has already been entered, but not left so far. In other words, v is on the trace (path that leads to u within the tree).
FORWARD_EDGE: An edge (u, v) is found, where v has already been left, and it had been entered after u. (u, v) is a shortcut forwards in the tree branch from u to v, so to speak.
CROSS_EDGE: An edge (u, v) is found, where v has already been left, and it had been entered before u. This means, in the DFS tree, u and v do not have any ancestor or descendant relationship between them.

Events that combine other events as a group (group-events):

SOME_NON_TREE_EDGE: One of the events FORWARD_EDGE, BACK_EDGE, or CROSS_EDGE occurred, but it has not been determined which of these events.
FORWARD_OR_CROSS_EDGE: One of the events FORWARD_EDGE or CROSS_EDGE occurred, but it has not been determined which of these events.

Aliases for sets of events:

NONE = 0
ENTERING = ENTERING_START | ENTERING_SUCCESSOR
LEAVING = LEAVING_START | LEAVING_SUCCESSOR
IN_OUT_START = ENTERING_START | LEAVING_START
IN_OUT_SUCCESSOR = ENTERING_SUCCESSOR | LEAVING_SUCCESSOR
IN_OUT = IN_OUT_START | IN_OUT_SUCCESSOR
NON_TREE_EDGES = FORWARD_EDGE | BACK_EDGE | CROSS_EDGE
EDGES = ENTERING_SUCCESSOR | NON_TREE_EDGES
ALL = IN_OUT | SKIPPING_START | NON_TREE_EDGES

class nographs.DFSMode(value)

An enumeration of the traversing mode to be used by TraversalDepthFirst.

The modes are:

DFS_TREE: The traversal follows the edges of the DFS tree. If demanded, non-tree edges are reported, but not followed. Vertices are only visited once.
ALL_PATHS: A simple path is a path that does not contain a vertex twice. In this mode, the traversal follows all edges, also edges leading to vertices that have already been visited. But edges to vertices, that are already on the trace (current path from a start vertex to the current vertex) are ignored. For example, this can be used to search in the set of all possible simple paths from some edges to some others.
ALL_WALKS: A walk is a sequence of nodes in which each adjacent pair of nodes in the sequence is adjacent in the graph. A walk can contain the same vertex or edge more than once. In this more, the traversal follows all edges, also edges leading to vertices that have already been followed as part of the trace (the current walk from a start vertex to the current vertex).

About the class:

Examples: See Depths first search in the integers and the comparing examples here.

class nographs.TraversalDepthFirstFlex(vertex_to_id, gear, next_vertices=None, *, next_edges=None, next_labeled_edges=None, is_tree=False)

Bases: Traversal [T_vertex, T_vertex_id, T_labels]

Parameters:

vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.
gear (GearWithoutDistances[T_vertex, T_vertex_id, T_labels]) – See gears API and class GearWithoutDistances.
next_vertices (Callable[[T_vertex, TraversalDepthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[T_vertex]] | None) – See NextVertices function. If None, provide next_edges or next_labeled_edges.
next_edges (Callable[[T_vertex, TraversalDepthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) – See NextEdges function. Only allowed if next_vertices equals None. If both are None, provide next_labeled_edges.
next_labeled_edges (Callable[[T_vertex, TraversalDepthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) – See NextLabeledEdges function. Only allowed if next_vertices and next_edges equal None. If given, paths will record the given labels.
is_tree (bool) – bool: If it is certain, that during each traversal run, each vertex can be reached only once, is_tree can be set to True. This improves performance, but attribute visited of the traversal will not be updated during and after the traversal.

Algorithm: Depth First Search (“DFS”), non-recursive implementation. By default, a vertex is reported when its expansion starts (its successors are about to be read from the graph).

Properties: Visits and expands unvisited vertices in depth first order, i.e., the graphs is explored as far as possible along each branch before backtracking. Starts at some unvisited start vertex, and after an exhaustive traversal from there, continues with another start vertex that has not been visited so far.

By default, it reports a vertex when it visits it.

Input: Directed graph. Unlabeled or labeled edges. One or more start vertices. Optional calculation limit.

Search state: When a vertex is expanded (traversal calls next_vertices, next_edges or next_labeled_edges) or reported (an iterator of the traversal returns it), the traversal provides updated values for the attributes depth, paths, visited, event, trace, trace_labels, on_trace, and index.

Parameters:

edges_with_data – Edges tuples, not just successor vertices
gear (GearWithoutDistances[T_vertex, T_vertex_id, T_labels]) – The traversal will use this gear
vertex_to_id (Callable[[T_vertex], T_vertex_id]) –
next_vertices (Callable[[T_vertex, TraversalDepthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[T_vertex]] | None) –
next_edges (Callable[[T_vertex, TraversalDepthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalDepthFirstFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) –
is_tree (bool) –

For the other parameters, see super class.

depth: int: If depth computation has been demanded (see option compute_depth): At this search depth, the reported (resp. the expanded) vertex has been found. It equals the length (number of edges) of the created path to the vertex, if path creation is demanded. Note: The search depth does not need to be the depth of the vertex (see TraversalBreadthFirstFlex). When a traversal has been started, but no vertex has been reported or expanded so far, the depth is 0 (depth of the start vertices).

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.

visited: VertexIdSet[T_vertex_id]: A collection that contains the visited vertices (resp. their hashable ids from vertex_to_id). After an exhaustive search, it contains the vertices (resp. vertex ids) reachable from the start vertices.

event: Event that happened when a vertex is reported

trace: Sequence of the vertices on the current path from a start vertex to the current vertex. See option compute_trace. When a back edge, cross edge, or a forward edge is reported, the edge is temporarily appended to the trace to make it visible there, although such an edge is ignored otherwise (e.g., the traversal does not follow the edge, traversal.depth is not updated, and the vertex it leads to is not taken to on_trace).

trace_labels: Sequence of the edge attributes of the edges on the current path (the first edge goes from a start vertex to a successor). See attribute trace and option compute_trace.

on_trace: Set of the vertices on the current path from a start vertex to the current vertex. See option compute_on_trace. When a cross edge or a forward edge is reported, the vertex it leads to will not be added to on_trace, unlike trace (see there).

index: Mapping that numbers vertices in pre-order, i.e., the vertex gets its number when it is entered. The vertices are numbered starting with 1. See option compute_index.

start_from(start_vertex=None, *, start_vertices=None, build_paths=False, calculation_limit=None, already_visited=None, report=DFSEvent.ENTERING_SUCCESSOR, mode=DFSMode.DFS_TREE, compute_depth=False, compute_trace=False, compute_on_trace=False, compute_index=False)

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

Parameters:

start_vertex (T_vertex | None) – The vertex the search should start at. If None, provide start_vertices.
start_vertices (Iterable[T_vertex] | None) – The vertices the search should start at. Only allowed if start_vertex equals None.
build_paths (bool) – If true, build paths from some start vertex to each visited vertex. Paths of start vertices are empty paths.
calculation_limit (int | None) – If provided, maximal number of vertices to process (read in) from your graph. If it is exceeded, a RuntimeError will be raised.
already_visited (MutableSet[T_vertex_id] | None) – If provided, this set is used instead of an internal one to keep vertices (resp. their hashable ids from vertex_to_id), that have already been visited. This parameter can be used to get online access to the internal bookkeeping of visited vertices, or to preload vertices that should never be visited, or to provide your own way for storing the information that a vertex has already been visited.
report (DFSEvent) –
See DFSEvent. When one of the chosen events occurs, the vertex is reported.

The group-events cannot be combined with the events contained in the group (see DFSEvent).

If events other than ENTERING_SUCCESSOR and ENTERING_START are required, option compute_trace (see below) will automatically be used.

If group-event FORWARD_OR_CROSS_EDGE is required, and the graph is no tree (is_tree == False), option compute_on_trace (see below) will automatically be set.

If events from NON_TREE_EDGES are required, and the graph is no tree (is_tree == False), the options compute_on_trace and compute_index (see below) will automatically be set.
mode (DFSMode) –
See DFSMode. The mode the search operates in.

Mode ALL_PATHS cannot be combined with the reporting of events FORWARD_EDGE and CROSS_EDGE, and event-groups containing them, since these events are only defined for DFS-trees. In mode ALL_PATHS, option compute_on_trace (see below) will automatically be set.

Mode ALL_WALKS cannot be combined with reporting non-tree edges, neither alone (events from NON_TREE_EDGES) nor in group-events (events SOME_NON_TREE_EDGE or FORWARD_OR_CROSS_EDGE), since forward and cross edges are only defined for DFS-trees, and back edges only for DFS-trees and for paths. The mode cannot be used for trees (parameter is_tree when creating the traversal), and visited is not computed.
compute_depth (bool) – For each reported vertex, provide the search depth is has been found at (Note: Often, this information is not helpful, and the computation increases memory consumption and runtime).
compute_index (bool) – If True, the attribute index is updated during the traversal, and option compute_trace (see below) will automatically be used. compute_index is not compatible with parameter already_visited.
compute_on_trace (bool) – If True, attribute on_trace is updated during the traversal, and option compute_trace will automatically be set. The computation of set on_trace cannot be combined with mode ALL_WALKS.
compute_trace (bool) – If True, attribute trace is updated during the traversal.

Returns:

Traversal, that has been started, e.g., statements like iter(), next(), for and the methods “go*” of the Traversal can now be used.

Return type:

TraversalDepthFirstFlex[T_vertex, T_vertex_id, T_labels]

Changed in version 3.4: Start vertices are evaluated successively. Parameters report, mode, compute_trace, compute_on_trace, and compute_index added.

__iter__()

Like nographs.Traversal.__iter__, but return a generator instead of an interator.

If StopIteration() is thrown into the generator:

When a vertex has been entered (events DFSEvent.ENTERING_START or DFSEvent.ENTERING_SUCCESSOR is reported), do not expand the vertex and reported it again as a confirmation.
In any other situation, raise a RuntimeError (according to PEP 497, see https://peps.python.org/pep-0479).

Changed in version 3.4: Now returns a generator instead of just an iterator, and a thrown StopIteration is handled, see above.

Return type:: Generator[T_vertex, None, None]

skip_expanding_entered_vertex()

If called when a vertex has been entered (events DFSEvent.ENTERING_START or DFSEvent.ENTERING_SUCCESSOR), skip the expansion of this vertex.

If called when another event happened, raise a RuntimeError.

(The method simply throws a StopIteration at traversal.__iter__().)

Changed in version 3.4: Method added.

Return type:: None

class nographs.TraversalDepthFirst(next_vertices=None, *, next_edges=None, next_labeled_edges=None, is_tree=False)

Bases: Generic[T_vertex, T_labels], TraversalDepthFirstFlex[T_vertex, T_vertex, T_labels]

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

Uses the following standard arguments for the respective parameters of the parent class:

vertex_to_id = vertex_as_id
gear = GearDefault
T_vertex_id = T_vertex

Implications:

GearDefault is used, see there how it and its superclass work
T_vertex is bound to Hashable (T_vertex is used as T_vertex_id, see there)

Parameters:

edges_with_data – Edges tuples, not just successor vertices
gear – The traversal will use this gear
next_vertices (Callable[[T_vertex, TraversalDepthFirstFlex[T_vertex, T_vertex, T_labels]], Iterable[T_vertex]] | None) –
next_edges (Callable[[T_vertex, TraversalDepthFirstFlex[T_vertex, T_vertex, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalDepthFirstFlex[T_vertex, T_vertex, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) –
is_tree (bool) –

For the other parameters, see super class.

TraversalNeighborsThenDepthFlex

Examples: See Depths first search in the integers and the comparing examples here.

class nographs.TraversalNeighborsThenDepthFlex(vertex_to_id, gear, next_vertices=None, *, next_edges=None, next_labeled_edges=None, is_tree=False)

Bases: Traversal [T_vertex, T_vertex_id, T_labels]

Parameters:

vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.
gear (GearWithoutDistances[T_vertex, T_vertex_id, T_labels]) – See gears API and class GearWithoutDistances.
next_vertices (Callable[[T_vertex, TraversalNeighborsThenDepthFlex[T_vertex, T_vertex_id, T_labels]], Iterable[T_vertex]] | None) – See NextVertices function. If None, provide next_edges or next_labeled_edges.
next_edges (Callable[[T_vertex, TraversalNeighborsThenDepthFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) – See NextEdges function. Only allowed if next_vertices equals None. If both are None, provide next_labeled_edges.
next_labeled_edges (Callable[[T_vertex, TraversalNeighborsThenDepthFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) – See NextLabeledEdges function. Only allowed if next_vertices and next_edges equal None. If given, paths will record the given labels.
is_tree (bool) – bool: If it is certain, that during each traversal run, each vertex can be reached only once, is_tree can be set to True. This improves performance, but attribute visited of the traversal will not be updated during and after the traversal.

Algorithm: Variant of the Depth First Search (“DFS”), non-recursive implementation. Vertices are reported when they are “seen” (read from the graph) for the first time - thus not in DFS order!

Properties: The graphs is explored as far as possible along each branch before backtracking, but in contrast to a Depth First Search, the algorithm first reports all successors of the current vertex and then goes deeper. A vertex is considered visited when it has been reported or if it is a start vertex.

Input: Directed graph. Unlabeled or labeled edges. One or more start vertices. Optional calculation limit.

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

Parameters:

edges_with_data – Edges tuples, not just successor vertices
gear (GearWithoutDistances[T_vertex, T_vertex_id, T_labels]) – The traversal will use this gear
vertex_to_id (Callable[[T_vertex], T_vertex_id]) –
next_vertices (Callable[[T_vertex, TraversalNeighborsThenDepthFlex[T_vertex, T_vertex_id, T_labels]], Iterable[T_vertex]] | None) –
next_edges (Callable[[T_vertex, TraversalNeighborsThenDepthFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalNeighborsThenDepthFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) –
is_tree (bool) –

For the other parameters, see super class.

depth: int: If depth computation has been demanded (see option compute_depth): At this search depth, the reported (resp. the expanded) vertex has been found. It equals the length (number of edges) of the created path to the vertex, if path creation is demanded. Note: The search depth does not need to be the depth of the vertex (see TraversalBreadthFirstFlex). When a traversal has been started, but no vertex has been reported or expanded so far, the depth is 0 (depth of the start vertices).

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.

visited: VertexIdSet[T_vertex_id]: A collection that contains the visited vertices (resp. their hashable ids from vertex_to_id). After an exhaustive search, it contains the vertices (resp. vertex ids) reachable from the start vertices.

start_from(start_vertex=None, *, start_vertices=None, build_paths=False, calculation_limit=None, already_visited=None, compute_depth=False)

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

Parameters:

start_vertex (T_vertex | None) – The vertex the search should start at. If None, provide start_vertices.
start_vertices (Iterable[T_vertex] | None) – The vertices the search should start at. Only allowed if start_vertex equals None.
build_paths (bool) – If true, build paths from some start vertex to each visited vertex. Paths of start vertices are empty paths.
calculation_limit (int | None) – If provided, maximal number of vertices to process (read in) from your graph. If it is exceeded, a RuntimeError will be raised.
already_visited (MutableSet[T_vertex_id] | None) – If provided, this set is used instead of an internal one to keep vertices (resp. their hashable ids from vertex_to_id), that have already been visited. This parameter can be used to get online access to the internal bookkeeping of visited vertices, or to preload vertices that should never be visited, or to provide your own way for storing the information that a vertex has already been visited.
compute_depth (bool) – For each reported vertex, provide the search depth is has been found at (Note: Often, this information is not helpful, and the computation increases memory consumption and runtime).

Returns:

Traversal, that has been started, e.g., statements like iter(), next(), for and the methods “go*” of the Traversal can now be used.

Return type:

TraversalNeighborsThenDepthFlex[T_vertex, T_vertex_id, T_labels]

class nographs.TraversalNeighborsThenDepth(next_vertices=None, *, next_edges=None, next_labeled_edges=None, is_tree=False)

Bases: Generic[T_vertex, T_labels], TraversalNeighborsThenDepthFlex[T_vertex, T_vertex, T_labels]

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

Uses the following standard arguments for the respective parameters of the parent class:

vertex_to_id = vertex_as_id
gear = GearDefault
T_vertex_id = T_vertex

Implications:

GearDefault is used, see there how it and its superclass work
T_vertex is bound to Hashable (T_vertex is used as T_vertex_id, see there)

Parameters:

edges_with_data – Edges tuples, not just successor vertices
gear – The traversal will use this gear
next_vertices (Callable[[T_vertex, TraversalNeighborsThenDepthFlex[T_vertex, T_vertex, T_labels]], Iterable[T_vertex]] | None) –
next_edges (Callable[[T_vertex, TraversalNeighborsThenDepthFlex[T_vertex, T_vertex, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalNeighborsThenDepthFlex[T_vertex, T_vertex, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) –
is_tree (bool) –

For the other parameters, see super class.

TraversalTopologicalSort

Examples: See Topological sorting of process steps and the comparing examples here.

class nographs.TraversalTopologicalSortFlex(vertex_to_id, gear, next_vertices=None, *, next_edges=None, next_labeled_edges=None, is_tree=False)

Bases: Traversal [T_vertex, T_vertex_id, T_labels]

Parameters:

vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.
gear (GearWithoutDistances[T_vertex, T_vertex_id, T_labels]) – See gears API and class GearWithoutDistances.
next_vertices (Callable[[T_vertex, TraversalTopologicalSortFlex[T_vertex, T_vertex_id, T_labels]], Iterable[T_vertex]] | None) – See NextVertices function. If None, provide next_edges or next_labeled_edges.
next_edges (Callable[[T_vertex, TraversalTopologicalSortFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) – See NextEdges function. Only allowed if next_vertices equals None. If both are None, provide next_labeled_edges.
next_labeled_edges (Callable[[T_vertex, TraversalTopologicalSortFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) – See NextLabeledEdges function. Only allowed if next_vertices and next_edges equal None. If given, paths will record the given labels.
is_tree (bool) – bool: If it is certain, that during each traversal run, each vertex can be reached only once, is_tree can be set to True. This improves performance, but attribute visited of the traversal will not be updated during and after the traversal.

Algorithm: Topological Search, non-recursive implementation. Vertices are reported when they “are left” for backtracking.

Properties: Vertices are reported in topological ordering, i.e. a linear ordering of the vertices such that for every directed edge uv from vertex u to vertex v (”u depends on v”), v comes before u in the ordering. If the graph contains a cycle that can be reached within the sorting process, a RuntimeError exception is raised and a cyclic path from a start vertex is provided.

Vertices are expanded following the strategy nographs.TraversalDepthFirst.

A vertex is considered visited from the moment its expansion begins. Start vertices are considered visited directly from the start of the traversal.

Input: Directed graph. Unlabeled or labeled edges. One or more start vertices. Optional calculation limit.

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

Parameters:

edges_with_data – Edges tuples, not just successor vertices
gear (GearWithoutDistances[T_vertex, T_vertex_id, T_labels]) – The traversal will use this gear
vertex_to_id (Callable[[T_vertex], T_vertex_id]) –
next_vertices (Callable[[T_vertex, TraversalTopologicalSortFlex[T_vertex, T_vertex_id, T_labels]], Iterable[T_vertex]] | None) –
next_edges (Callable[[T_vertex, TraversalTopologicalSortFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalTopologicalSortFlex[T_vertex, T_vertex_id, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) –
is_tree (bool) –

For the other parameters, see super class.

depth: int: At this search depth, the reported (resp. the expanded) vertex has been found. It equals the length (number of edges) of the created path to the vertex, if path creation is demanded. Note: The search depth does not need to be the depth of the vertex (see TraversalBreadthFirstFlex). When a traversal has been started, but no vertex has been reported or expanded so far, the depth is 0 (depth of the start vertices).

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.

visited: VertexIdSet[T_vertex_id]: A collection that contains the visited vertices (resp. their hashable ids from vertex_to_id). After an exhaustive search, it contains the vertices (resp. vertex ids) reachable from the start vertices.

cycle_from_start: list[T_vertex]: If the graph contains a cycle that can be reached within the sorting process, a RuntimeError exception is raised, and the traversal provides a cyclic path from a start vertex in attribute cycle_from_start.

start_from(start_vertex=None, *, start_vertices=None, build_paths=False, calculation_limit=None, already_visited=None)

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

Parameters:

start_vertex (T_vertex | None) – The vertex the search should start at. If None, provide start_vertices.
start_vertices (Iterable[T_vertex] | None) – The vertices the search should start at. Only allowed if start_vertex equals None.
build_paths (bool) – If true, build paths from some start vertex to each visited vertex. Paths of start vertices are empty paths.
calculation_limit (int | None) – If provided, maximal number of vertices to process (read in) from your graph. If it is exceeded, a RuntimeError will be raised.
already_visited (MutableSet[T_vertex_id] | None) –
If provided, this set is used instead of an internal one to keep vertices (resp. their hashable ids from vertex_to_id), that have already been visited. This parameter can be used to get online access to the internal bookkeeping of visited vertices, or to preload vertices that should never be visited.

Attention: TraversalTopologicalSortFlex requires, that the collection given as argument for parameter already_visited is compatible (in any sense) with the collection that gear.vertex_id_set() returns. If you have chosen GearDefault, you can just use a dict. Otherwise, create the collection by calling gear.vertex_id_set() or use the collection that another traversal with the same gear gives as attribute visited.

Returns:

Traversal, that has been started, e.g., statements like iter(), next(), for and the methods “go*” of the Traversal can now be used.

Return type:

TraversalTopologicalSortFlex[T_vertex, T_vertex_id, T_labels]

class nographs.TraversalTopologicalSort(next_vertices=None, *, next_edges=None, next_labeled_edges=None, is_tree=False)

Bases: Generic[T_vertex, T_labels], TraversalTopologicalSortFlex[T_vertex, T_vertex, T_labels]

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

Uses the following standard arguments for the respective parameters of the parent class:

vertex_to_id = vertex_as_id
gear = GearDefault
T_vertex_id = T_vertex

Implications:

GearDefault is used, see there how it and its superclass work
T_vertex is bound to Hashable (T_vertex is used as T_vertex_id, see there)

Parameters:

edges_with_data – Edges tuples, not just successor vertices
gear – The traversal will use this gear
next_vertices (Callable[[T_vertex, TraversalTopologicalSortFlex[T_vertex, T_vertex, T_labels]], Iterable[T_vertex]] | None) –
next_edges (Callable[[T_vertex, TraversalTopologicalSortFlex[T_vertex, T_vertex, T_labels]], Iterable[tuple[~T_vertex, Any] | tuple[~T_vertex, Any, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalTopologicalSortFlex[T_vertex, T_vertex, T_labels]], Iterable[tuple[~T_vertex, Any, ~T_labels] | tuple[~T_vertex, ~T_labels]]] | None) –
is_tree (bool) –

For the other parameters, see super class.

Traversal classes for weighted graphs

TraversalShortestPaths

Examples: See Shortest paths in a maze with weights, the comparing examples here and an example for method go_for_distance_range.

class nographs.TraversalShortestPathsFlex(vertex_to_id, gear, next_edges=None, *, next_labeled_edges=None, is_tree=False)

Bases: Generic[T_vertex, T_vertex_id, T_weight, T_labels],

Traversal [T_vertex, T_vertex_id, T_labels]

Parameters:

vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.
gear (Gear[T_vertex, T_vertex_id, T_weight, T_labels]) – See gears API and class Gear.
next_edges (Callable[[T_vertex, TraversalShortestPathsFlex[ T_vertex, T_vertex_id, T_weight, T_labels ]], Iterable[tuple[~T_vertex, ~T_weight] | tuple[~T_vertex, ~T_weight, Any]]] | None) – See NextWeightedEdges function. If None, provide next_labeled_edges.
next_labeled_edges (Callable[[T_vertex, TraversalShortestPathsFlex[ T_vertex, T_vertex_id, T_weight, T_labels ]], Iterable[tuple[~T_vertex, ~T_weight, ~T_labels]]] | None) – See NextWeightedLabeledEdges function. Only allowed if next_edges equals None. If given, paths will record the given labels.
is_tree (bool) – bool: If it is certain, that during each traversal run, each vertex can be reached only once, is_tree can be set to True. This improves performance, but attribute distances of the traversal will not be updated during and after the traversal.

Algorithm: Shortest paths algorithm of Dijkstra, non-recursive, based on heap.

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. One or more start vertices. Optional calculation limit.

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, depth, paths, and distances.

Parameters:

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

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

depth: int: At this search depth, the reported (resp. the expanded) vertex has been found. It equals the length (number of edges) of the created path to the vertex, if path creation is demanded. Note: The search depth does not need to be the depth of the vertex (see TraversalBreadthFirstFlex). When a traversal has been started, but no vertex has been reported or expanded so far, the depth is 0 (depth of the start vertices).

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]: Provisional or final distance values of some vertices (distance from a start vertex). Without option keep_distances, the value for a vertex is removed once the vertex has been reported. With option keep_distances, values are never removed, and that means: During a traversal, the distance values for already reported vertices can be found in the collection. 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, calculation_limit=None, keep_distances=False, known_distances=None)

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

Parameters:

start_vertex (T_vertex | None) – The vertex the search should start at. If None, provide start_vertices.
start_vertices (Iterable[T_vertex] | 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.
calculation_limit (int | None) – If provided, maximal number of vertices to process (read in) from your graph. If it is exceeded, a RuntimeError will be raised.
keep_distances (bool) – If True, the found distances of vertices are collected in traversal attribute distances, and not deleted after having reported the vertex. See attribute distances.
known_distances (MutableMapping[T_vertex_id, T_weight] | None) –
If provided, this mapping is used instead of an internal one to keep distance candidates and final distances values of reported vertices (resp. their hashable ids from vertex_to_id is used as key) from some start vertex.

For vertices without known distance, it must yield float(‘infinity’). The internal default implementation uses a collections.defaultdict. Typical use cases are: 1) preloading known distances of vertices, and the vertices should not be visited if no smaller distance is found during the traversal, and 2) providing your own way for storing the distances.

Returns:

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

Return type:

TraversalShortestPathsFlex[T_vertex, T_vertex_id, T_weight, T_labels]

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.TraversalShortestPaths(next_edges=None, *, next_labeled_edges=None, is_tree=False)

Bases: Generic[T_vertex, T_weight, T_labels], TraversalShortestPathsFlex[T_vertex, T_vertex, Union[T_weight, float], T_labels]

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

TraversalShortestPaths[T_vertex, T_weight, T_labels](*args, **keywords)

is a short form for

TraversalShortestPathsFlex[
    T_vertex, T_vertex, Union[T_weight, float], T_labels],
](nog.vertex_as_id, 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
T_vertex is bound to Hashable (T_vertex is used as T_vertex_id, see there)

Parameters:

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

TraversalAStar

Examples: See Shortest path search with distance heuristic (A* search) and the comparing examples here.

class nographs.TraversalAStarFlex(vertex_to_id, gear, next_edges=None, *, next_labeled_edges=None, is_tree=False)

Bases: Generic[T_vertex, T_vertex_id, T_weight, T_labels],

Traversal [T_vertex, T_vertex_id, T_labels]

Parameters:

vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.
gear (Gear[T_vertex, T_vertex_id, T_weight, T_labels]) – See gears API and class Gear.
next_edges (Callable[[T_vertex, TraversalAStarFlex[ T_vertex, T_vertex_id, T_weight, T_labels ]], Iterable[tuple[~T_vertex, ~T_weight] | tuple[~T_vertex, ~T_weight, Any]]] | None) – See NextWeightedEdges function. If None, provide next_labeled_edges.
next_labeled_edges (Callable[[T_vertex, TraversalAStarFlex[ T_vertex, T_vertex_id, T_weight, T_labels ]], Iterable[tuple[~T_vertex, ~T_weight, ~T_labels]]] | None) – See NextWeightedLabeledEdges function. Only allowed if next_edges equals None. If given, paths will record the given labels.
is_tree (bool) – bool: If it is certain, that during each traversal run, each vertex can be reached only once, is_tree can be set to True. This improves performance, but if start_from has been called with parameter known_path_length_guesses given, this collection will not be updated during the traversal.

Algorithm: The search algorithm A*, non-recursive, based on heap.

Input: Weighted directed graph. Weights need to be non-negative. One or more start vertices. Optional calculation limit. A heuristic function that estimates the cost of the cheapest path from a given vertex to the goal (resp. to any of your goal vertices, if you have more than one), and never overestimates the actual needed costs (“admissible heuristic function”).

Properties: Vertices are reported and expanded ordered by increasing path length (sum of edge weights) of the shortest paths from a start vertex to the respective vertex that have been found so far.

When the goal is reported, the path stored for it in paths is a shortest path from start to goal and the path_length of the search state is the distance of the goal from start.

In case the used heuristic function is consistent (i.e., following an edge from one vertex to another never reduces the estimated costs to get to the goal by more than the weight of the edge), further guarantees hold: Each vertex is only visited once. And for each visited vertex, the respective path_length and depth (and optionally, the path) are the data of the shortest existing path from start (not only from the shortest path found so far).

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 path_length, depth, paths.

Parameters:

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

path_length: T_weight: Length (sum of edge weights) of the found path to the vertex (for the goal vertex: a shortest path)

depth: int: At this search depth, the reported (resp. the expanded) vertex has been found. It equals the length (number of edges) of the created path to the vertex, if path creation is demanded. Note: The search depth does not need to be the depth of the vertex (see TraversalBreadthFirstFlex).

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.

start_from(heuristic, start_vertex=None, *, start_vertices=None, build_paths=False, calculation_limit=None, known_distances=None, known_path_length_guesses=None)

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

Parameters:

heuristic (Callable[[T_vertex], T_weight]) – The admissible and consistent heuristic function that estimates the cost of the cheapest path from a given vertex to the goal (resp. one of the goals).
start_vertex (T_vertex | None) – The vertex the search should start at. If None, provide start_vertices.
start_vertices (Iterable[T_vertex] | 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.
calculation_limit (int | None) – If provided, maximal number of vertices to process (read in) from your graph. If it is exceeded, a RuntimeError will be raised.
known_distances (MutableMapping[T_vertex_id, T_weight] | None) –
If provided, this mapping is used instead of an internal one to keep the distances of vertices that have already been visited (resp. their hashable ids from vertex_to_id is used as key) from some start vertex. For vertices without known distance, it must yield float( ‘infinity’). The internal default implementation uses a collections.defaultdict.

Typical use cases are: 1) preloading known distances of vertices, and the vertices should not be visited if no smaller distance is found during the traversal, or 2) getting online access to the internal bookkeeping of visited vertices and their distances, or 3) providing your own way for storing the distance of a vertex that has already been visited.
known_path_length_guesses (MutableMapping[T_vertex_id, T_weight] | None) – Like known_distances, but for keeping the sum distance+heuristic for vertices.

Returns:

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

Return type:

TraversalAStarFlex[T_vertex, T_vertex_id, T_weight, T_labels]

class nographs.TraversalAStar(next_edges=None, *, next_labeled_edges=None, is_tree=False)

Bases: Generic[T_vertex, T_weight, T_labels], TraversalAStarFlex[T_vertex, T_vertex, Union[T_weight, float], T_labels]

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

TraversalAStar[T_vertex, T_weight, T_labels](*args, **keywords)

is a short form for

TraversalAStarFlex[
    T_vertex, T_vertex, Union[T_weight, float], T_labels],
](nog.vertex_as_id, 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
T_vertex is bound to Hashable (T_vertex is used as T_vertex_id, see there)

Parameters:

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

TraversalMinimumSpanningTree

Examples: See the comparing examples here.

class nographs.TraversalMinimumSpanningTreeFlex(vertex_to_id, gear, next_edges=None, *, next_labeled_edges=None)

Bases: Generic[T_vertex, T_vertex_id, T_weight, T_labels],

Traversal [T_vertex, T_vertex_id, T_labels]

Parameters:

vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.
gear (Gear[T_vertex, T_vertex_id, T_weight, T_labels]) – See gears API and class Gear.
next_edges (Callable[[T_vertex, TraversalMinimumSpanningTreeFlex[ T_vertex, T_vertex_id, T_weight, T_labels ]], Iterable[tuple[~T_vertex, ~T_weight] | tuple[~T_vertex, ~T_weight, Any]]] | None) – See NextWeightedEdges function. If None, provide next_labeled_edges.
next_labeled_edges (Callable[[T_vertex, TraversalMinimumSpanningTreeFlex[ T_vertex, T_vertex_id, T_weight, T_labels ]], Iterable[tuple[~T_vertex, ~T_weight, ~T_labels]]] | None) – See NextWeightedLabeledEdges function. Only allowed if next_edges equals None. If given, paths will record the given labels.

Algorithm: Minimum spanning tree (“MST”) algorithm of Jarnik, Prim, Dijkstra. Non-recursive, based on heap. A so-called tie breaker is implemented, that prioritizes edges that have been found more recently about edges that have been found earlier. This is a typical choice that often improves search performance.

Properties: Only edges of the MST from start vertices are reported. Each vertex is reported (as end vertex of an edge) and expanded only once. Computed paths only use MST edges.

Input: Weighted undirected graph, given as directed edges with the same weight in both directions. One or more start vertices (e.g. for components in unconnected graphs). Optional calculation limit.

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

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 (Callable[[T_vertex], T_vertex_id]) – See VertexToID
gear (Gear[T_vertex, T_vertex_id, T_weight, T_labels]) –
next_edges (Callable[[T_vertex, TraversalMinimumSpanningTreeFlex[ T_vertex, T_vertex_id, T_weight, T_labels ]], Iterable[tuple[~T_vertex, ~T_weight] | tuple[~T_vertex, ~T_weight, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalMinimumSpanningTreeFlex[ T_vertex, T_vertex_id, T_weight, T_labels ]], Iterable[tuple[~T_vertex, ~T_weight, ~T_labels]]] | None) –

edge: WeightedFullEdge[T_vertex, T_weight, T_labels] | None: Tuple of from_vertex, to_vertex, the weight of the edge, and additional data you have provided with the edge (if so).

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.

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

Start the traversal at a vertex or a set of vertices and set parameters. If you provide more than one start vertex, the result consists of several trees that are only connected if the start vertices are connected.

Parameters:

start_vertex (T_vertex | None) – The vertex the search should start at. If None, provide start_vertices.
start_vertices (Iterable[T_vertex] | 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.
calculation_limit (int | None) – If provided, maximal number of vertices to process (read in) from your graph. If it is exceeded, a RuntimeError will be raised.

Returns:

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

Return type:

TraversalMinimumSpanningTreeFlex[T_vertex, T_vertex_id, T_weight, T_labels]

class nographs.TraversalMinimumSpanningTree(next_edges=None, *, next_labeled_edges=None)

Bases: Generic[T_vertex, T_weight, T_labels], TraversalMinimumSpanningTreeFlex[T_vertex, T_vertex, Union[T_weight, float], T_labels]

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

TraversalMinimumSpanningTree[T_vertex, T_weight, T_labels](*args, **keywords)

is a short form for

TraversalMinimumSpanningTreeFlex[
    T_vertex, T_vertex, Union[T_weight, float], T_labels],
](nog.vertex_as_id, 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
T_vertex is bound to Hashable (T_vertex is used as T_vertex_id, see there)

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, TraversalMinimumSpanningTreeFlex[T_vertex, T_vertex, T_weight | float, T_labels]], Iterable[tuple[~T_vertex, ~T_weight] | tuple[~T_vertex, ~T_weight, Any]]] | None) –
next_labeled_edges (Callable[[T_vertex, TraversalMinimumSpanningTreeFlex[T_vertex, T_vertex, T_weight | float, T_labels]], Iterable[tuple[~T_vertex, ~T_weight, ~T_labels]]] | None) –

Bidirectional search strategies

BSearchBreadthFirstFlex

Example: See here.

class nographs.BSearchBreadthFirstFlex(vertex_to_id, gear, next_vertices=None, *, next_edges=None, next_labeled_edges=None)

Bases: Strategy [T_vertex, T_vertex_id, T_labels]

Parameters:

vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.
gear (GearWithoutDistances[T_vertex, T_vertex_id, T_labels]) – See gears API and class GearWithoutDistances.
next_vertices (tuple[Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex_id, ~T_labels]], Iterable[~T_vertex]], Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex_id, ~T_labels]], Iterable[~T_vertex]]] | None) – Tuple BNextVertices of two NextVertices function. If None, provide next_edges or next_labeled_edges.
next_edges (tuple[Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex_id, ~T_labels]], Iterable[Union[tuple[~T_vertex, Any], tuple[~T_vertex, Any, Any]]]], Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex_id, ~T_labels]], Iterable[Union[tuple[~T_vertex, Any], tuple[~T_vertex, Any, Any]]]]] | None) – Tuple BNextEdges of two NextEdges functions. See paragraph input below for details. Only allowed if next_vertices equals None. If both are None, provide next_labeled_edges.
next_labeled_edges (tuple[Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex_id, ~T_labels]], Iterable[Union[tuple[~T_vertex, Any, ~T_labels], tuple[~T_vertex, ~T_labels]]]], Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex_id, ~T_labels]], Iterable[Union[tuple[~T_vertex, Any, ~T_labels], tuple[~T_vertex, ~T_labels]]]]] | None) – Tuple BNextLabeledEdges of two NextEdges functions. See paragraph input below for details. The parameter is only allowed if next_vertices and next_edges equal None. If given, paths will record the given labels.

Algorithm: Bidirectional version of the Breadth First Search algorithm, non-recursive, based on FIFO queues.

Properties: In both directions, vertices are visited by increasing depth from a start (resp. a goal) vertex (minimal number of edges), till a shortest path (minimal number of edges) from a start to a goal vertex is found. Each vertex is visited only once.

Input: Directed graph. Unlabeled or labeled edges. One or more start vertices, and one or more goal vertices. NextVertices (resp. NextEdges) functions both for the outgoing edges from a vertex and the incoming edges to a vertex have to be provided, and they need to describe the same graph. Optional calculation limit.

Note: A shortest path from a vertex v to itself always exists, has an edge count of 0, and will be found by the class, whilst TraversalBreadthFirst does not report start vertices and thus, TraversalBreadthFirst(<something>).start_at(v).go_to(v) fails.

class nographs.BSearchBreadthFirst(next_vertices=None, *, next_edges=None, next_labeled_edges=None)

Bases: Generic[T_vertex, T_labels], BSearchBreadthFirstFlex[T_vertex, T_vertex, T_labels]

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

BSearchBreadthFirst[T_vertex, T_labels](*args, **keywords)

is a short form for

 BSearchBreadthFirstFlex[
     T_vertex, T_vertex, T_labels],
](nog.vertex_as_id, nog.GearDefault(), *args, **keywords)

Implication:

GearDefault is used, see there how it and its superclass work
T_vertex is bound to Hashable (T_vertex is used as T_vertex_id, see there)

Parameters:

next_vertices (tuple[Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex, ~T_labels]], Iterable[~T_vertex]], Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex, ~T_labels]], Iterable[~T_vertex]]] | None) –
next_edges (tuple[Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex, ~T_labels]], Iterable[Union[tuple[~T_vertex, Any], tuple[~T_vertex, Any, Any]]]], Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex, ~T_labels]], Iterable[Union[tuple[~T_vertex, Any], tuple[~T_vertex, Any, Any]]]]] | None) –
next_labeled_edges (tuple[Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex, ~T_labels]], Iterable[Union[tuple[~T_vertex, Any, ~T_labels], tuple[~T_vertex, ~T_labels]]]], Callable[[~T_vertex, nographs._strategies.traversals.without_weights.breadth_first.TraversalBreadthFirstFlex[~T_vertex, ~T_vertex, ~T_labels]], Iterable[Union[tuple[~T_vertex, Any, ~T_labels], tuple[~T_vertex, ~T_labels]]]]] | None) –

BSearchShortestPathFlex

Example: See here.

class nographs.BSearchShortestPathFlex(vertex_to_id, gear, next_edges=None, *, next_labeled_edges=None)

Bases: Strategy [T_vertex, T_vertex_id, T_labels], Generic[T_vertex, T_vertex_id, T_weight, T_labels]

Parameters:

vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.
gear (Gear[T_vertex, T_vertex_id, T_weight, T_labels]) – See gears API and class Gear.
next_edges (tuple[Callable[[~T_vertex, ForwardRef('BSearchShortestPathFlex[T_vertex, T_vertex_id, T_weight, T_labels]')], Iterable[Union[tuple[~T_vertex, ~T_weight], tuple[~T_vertex, ~T_weight, Any]]]], Callable[[~T_vertex, ForwardRef('BSearchShortestPathFlex[T_vertex, T_vertex_id, T_weight, T_labels]')], Iterable[Union[tuple[~T_vertex, ~T_weight], tuple[~T_vertex, ~T_weight, Any]]]]] | None) – Tuple BNextWeightedEdges of two NextEdges functions. See paragraph input below for details. If None, provide next_labeled_edges.
next_labeled_edges (tuple[Callable[[~T_vertex, ForwardRef('BSearchShortestPathFlex[T_vertex, T_vertex_id, T_weight, T_labels]')], Iterable[tuple[~T_vertex, ~T_weight, ~T_labels]]], Callable[[~T_vertex, ForwardRef('BSearchShortestPathFlex[T_vertex, T_vertex_id, T_weight, T_labels]')], Iterable[tuple[~T_vertex, ~T_weight, ~T_labels]]]] | None) – Tuple BNextWeightedLabeledEdges of two NextEdges functions. See paragraph input below for details. The parameter is only allowed if next_edges equals None. If given, paths will record the given labels.

Algorithm: Bidirectional version of the shortest paths algorithm of Dijkstra, non-recursive, based on heap.

Properties: In both directions, vertices are visited by increasing distance (minimally necessary sum of edge weights) from a start (resp. a goal) vertex, till a shortest path (minimal sum of edge weights) from a start to a goal vertex is found. Each vertex is visited only once.

Input: Weighted directed graph. One or more start vertices, and one or more goal vertices. Weights need to be non-negative. NextWeightedEdges (resp. NextWeightedLabeledEdges) functions both for the outgoing edges from a vertex and the incoming edges to a vertex have to be provided, and they need to describe the same graph. Optional calculation limit.

Note: A shortest path from a vertex v to itself always exists, has length 0, and will be found by the class, whilst TraversalShortestPaths does not report start vertices and thus, TraversalShortestPaths(<something>).start_at(v).go_to(v) fails.

class nographs.BSearchShortestPath(next_edges=None, *, next_labeled_edges=None)

Bases: Generic[T_vertex, T_weight, T_labels], BSearchShortestPathFlex[T_vertex, T_vertex, Union[T_weight, float], T_labels]

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

BSearchShortestPath[T_vertex, T_weight, T_labels](*args, **keywords)

is a short form for

 BSearchShortestPathFlex[
     T_vertex, T_vertex, Union[T_weight, float], T_labels],
](nog.vertex_as_id, nog.GearDefault(), *args, **keywords)

Implication:

GearDefault is used, see there how it and its superclass work
The used weights are defined by Union[T_weight, float], see GearDefault
T_vertex is bound to Hashable (T_vertex is used as T_vertex_id, see there)

Parameters:

next_edges (tuple[Callable[[~T_vertex, nographs._strategies.bidirectional_search.shortest_path.BSearchShortestPathFlex[~T_vertex, ~T_vertex, Union[~T_weight, float], ~T_labels]], Iterable[Union[tuple[~T_vertex, ~T_weight], tuple[~T_vertex, ~T_weight, Any]]]], Callable[[~T_vertex, nographs._strategies.bidirectional_search.shortest_path.BSearchShortestPathFlex[~T_vertex, ~T_vertex, Union[~T_weight, float], ~T_labels]], Iterable[Union[tuple[~T_vertex, ~T_weight], tuple[~T_vertex, ~T_weight, Any]]]]] | None) –
next_labeled_edges (tuple[Callable[[~T_vertex, nographs._strategies.bidirectional_search.shortest_path.BSearchShortestPathFlex[~T_vertex, ~T_vertex, Union[~T_weight, float], ~T_labels]], Iterable[tuple[~T_vertex, ~T_weight, ~T_labels]]], Callable[[~T_vertex, nographs._strategies.bidirectional_search.shortest_path.BSearchShortestPathFlex[~T_vertex, ~T_vertex, Union[~T_weight, float], ~T_labels]], Iterable[tuple[~T_vertex, ~T_weight, ~T_labels]]]] | None) –

Paths containers and paths

class nographs.Paths(predecessor, vertex_to_id)

Bases: ABC, Generic[T_vertex, T_vertex_id, T_labels]

A Paths object is a container that stores the paths (“ways” through a graph) that have been generated by one of the traversal algorithms.

Paths provides methods to access and iterate a path.

A path is identified by its end vertex. The vertices that come before the end vertex are themselves stored as a path. The container will never store two paths that lead to the same vertex. An empty path with just one vertex can be stored, and the start of each path needs to be an empty path. A self loop can not be stored as path (since internally, a self loop is used to mark an empty path).

A path can be iterated in forward direction, i.e., from a start vertex to the given vertex, or in the backward direction. The forward iteration is implemented based on the backward iteration by creating a copy of the path. Thus, it is slower and needs additional memory.

Class Paths and its subclasses are not intended to be instantiated by application code. On demand, the traversal strategies of the library will create Paths objects.

Parameters:

predecessor (MutableMapping[T_vertex_id, T_vertex]) – The predecessor information of the paths will be stored in the given mapping.
vertex_to_id (Callable[[T_vertex], T_vertex_id]) – See VertexToID function.

__contains__(vertex)

Return whether a path to vertex exists in the Paths container. This allows for expressions like vertex in paths.

Parameters:: vertex (T_vertex) – The vertex to look for.
Return type:: bool

predecessor(vertex)

Return predecessor of vertex in path to vertex. Return None if the path is empty. Raise RuntimeError is no path to vertex is stored.

Parameters:: vertex (T_vertex) – The predecessor of this vertex will be returned.
Return type:: T_vertex | None

Changed in version 3.3: Method added.

iter_vertices_to_start(vertex)

Iterate the vertices on the path to vertex from the last to the first.

Parameters:: vertex (T_vertex) – The path ending at this vertex will be iterated.
Return type:: Iterator[T_vertex]

iter_vertices_from_start(vertex)

Iterate the vertices on the path to vertex from the first to the last. Internally, a list of all the vertices is created and then reversed and iterated.

Parameters:: vertex (T_vertex) – The path ending at this vertex will be iterated.
Return type:: Iterator[T_vertex]

iter_edges_to_start(vertex)

Iterate the edges of the path to vertex from the last to the first.

Parameters:: vertex (T_vertex) – The path ending at this vertex will be iterated.
Return type:: Iterator[tuple[~T_vertex, ~T_vertex]]

iter_edges_from_start(vertex)

Iterate the edges of the path to vertex from the first to the last. Internally, a list of all the edges is created and then reversed and iterated.

Parameters:: vertex (T_vertex) – The path ending at this vertex will be iterated.
Return type:: Iterator[tuple[~T_vertex, ~T_vertex]]

iter_labeled_edges_to_start(vertex)

Iterate the edges of the path to vertex from the last to the first. Raise RuntimeError if the stored edges are not labeled.

To be overridden in subclasses that support labeled edges.

Parameters:: vertex (T_vertex) – The path ending at this vertex will be iterated.
Return type:: Iterator[tuple[~T_vertex, ~T_vertex, ~T_labels]]

iter_labeled_edges_from_start(vertex)

Iterate the edges of the path to vertex from the first to the last. Internally, a list of all the edges is created and then reversed and iterated. Raise RuntimeError if the stored edges are not labeled.

To be overridden in subclasses that support labeled edges.

Parameters:: vertex (T_vertex) – The path ending at this vertex will be iterated.
Return type:: Iterator[tuple[~T_vertex, ~T_vertex, ~T_labels]]

abstract __getitem__(vertex)

Return the path that ends at vertex as a sequence. The orientation of the path is from first to last vertex / edge. In case of a labeled path, the edges are returned, for an unlabeled path the vertices.

The method allows for expressions like paths[vertex].

In fully typed code, you can use the following alternative:

# If the paths are not labeled, the following is equivalent to paths[vertex]:
tuple(paths.iter_vertices_from_start(vertex))

# If the paths are labeled, the following is equivalent to paths[vertex]:
tuple(paths.iter_labeled_edges_from_start(vertex))

Internally, the path from the given vertex back to the first vertex in the path is computed, and then reversed and stored as sequence.

Parameters:: vertex (T_vertex) – The path ending at this vertex will be returned.
Return type:: Sequence[T_vertex] | Sequence[tuple[~T_vertex, ~T_vertex, ~T_labels]]

class nographs.Path(get_vertex_forwards_iter, get_vertex_backwards_iter, get_edge_forwards_iter, get_edge_backwards_iter)

Bases: ABC, Generic[T_vertex, T_vertex_id, T_labels]

A Path object stores a path (“way” through a graph) that has been generated by one of the search algorithms.

Path provides methods to access and iterate the stored path.

A path can be iterated in forward direction, i.e., from a start vertex to the given vertex, or in the backward direction.

Implementation detail: In fact, Path does not store the path itself, but only functions that, when one of the offered kind of iteration of the path is demanded, can create the necessary iterator.

Class Path and its subclasses are not intended to be instantiated by application code. On demand, the search algorithms of the library will create Path objects.

Parameters:

get_vertex_forwards_iter (Callable[[], Iterator[T_vertex]]) – Return an iterator that iterates the vertices of the paths in forwards direction.
get_vertex_backwards_iter (Callable[[], Iterator[T_vertex]]) – Return an iterator that iterates the vertices of the paths in backwards direction.
get_edge_forwards_iter (Callable[[], Iterator[tuple[~T_vertex, ~T_vertex, ~T_labels]]]) – Return an iterator that iterates the labeled edges of the paths in forwards direction, or raise RuntimeError if the path does not contain labeled edges.
get_edge_backwards_iter (Callable[[], Iterator[tuple[~T_vertex, ~T_vertex, ~T_labels]]]) – Return an iterator that iterates the labeled edges of the paths in backwards direction, or raise RuntimeError if the path does not contain labeled edges.

iter_vertices_from_start()

Iterate the vertices on the path from the first to the last.

Return type:: Iterator[T_vertex]

iter_vertices_to_start()

Iterate the vertices on the path from the last to the first.

Return type:: Iterator[T_vertex]

iter_edges_from_start()

Iterate the edges of the path from the first to the last.

Return type:: Iterator[tuple[~T_vertex, ~T_vertex]]

iter_edges_to_start()

Iterate the edges of the path from the last to the first.

Return type:: Iterator[tuple[~T_vertex, ~T_vertex]]

iter_labeled_edges_to_start()

Iterate the edges of the path from the last to the first. Raise RuntimeError if the stored edges are not labeled.

Return type:: Iterator[tuple[~T_vertex, ~T_vertex, ~T_labels]]

iter_labeled_edges_from_start()

Iterate the edges of the path from the first to the last. Raise RuntimeError if the stored edges are not labeled.

Return type:: Iterator[tuple[~T_vertex, ~T_vertex, ~T_labels]]

Gears

In NoGraphs, a gear provides a complete set of bookkeeping data structures, that are optimized for a specific usage scenario of NoGraphs. Application code can:

choose the optimal gear for a given situation,
and define new gears that are derived from existing ones and that replace some collections by other set- oder mapping-like collections (e.g., collections from external libraries) that better suite the use case.

Side note: If you like to define a new gear based on a new list- or array-like collection (e.g., one of an external library) and you also aim at high runtime efficiency (comparable to the predefined gears for integer vertex ids, that use lists and arrays of the standard library in a special and fast way), please inform the author, that the documentation should also cover this aspect.

The protocols

Syntactically, a gear is an implementation of one of the protocols nographs.GearWithoutDistances and nographs.Gear. Each of its methods is a factory that creates one of the kinds of data structures that NoGraphs needs for its algorithms.

class nographs.GearWithoutDistances

Bases: Protocol[T_vertex, T_vertex_id, T_labels]

Protocol for a feature-limited kind of gear that offers collections that can store vertices, vertex_ids and edge data, but no edge weights / distances.

abstract vertex_id_set(initial_content)

Factory for a set of vertices.

Parameters:: initial_content (Iterable[T_vertex_id]) – The collection is created with this initial content.
Return type:: MutableSet[T_vertex_id]

abstract vertex_id_to_vertex_mapping(initial_content)

Factory for a mapping from a vertex id to a vertex.

Parameters:: initial_content (Iterable[Tuple[T_vertex_id, T_vertex]]) – The collection is created with this initial content.
Return type:: MutableMapping[T_vertex_id, T_vertex]

abstract vertex_id_to_edge_labels_mapping(initial_content)

Factory for a mapping from a vertex id to edge data.

Parameters:: initial_content (Iterable[Tuple[T_vertex_id, T_labels]]) – The collection is created with this initial content.
Return type:: MutableMapping[T_vertex_id, T_labels]

abstract sequence_of_vertices(initial_content)

Factory for a sequence of vertices.

Parameters:: initial_content (Iterable[T_vertex]) –
Return type:: MutableSequence[T_vertex]

abstract sequence_of_edge_labels(initial_content)

Factory for a sequence of edge attributes.

Parameters:: initial_content (Iterable[T_labels]) –
Return type:: MutableSequence[T_labels]

abstract vertex_id_to_number_mapping(initial_content)

Factory for a mapping from a vertex id to non-negative integers starting at zero, that represent a numbering of some vertices.

If the returned mapping does not contain a value for some key, its method __getitem__ needs to return 0.

Parameters:: initial_content (Iterable[Tuple[T_vertex_id, int]]) – The collection is created with this initial content.
Return type:: MutableMapping[T_vertex_id, int]

class nographs.Gear

Bases: Generic[T_vertex, T_vertex_id, T_weight, T_labels], GearWithoutDistances[T_vertex, T_vertex_id, T_labels], Protocol

Protocol for gears with collections that can store vertices, vertex_ids, and edge data (like a GearWithoutDistances), and additionally, edge weights / distances. It also provides suitable distance values for zero and positive infinity.

In case you use a gear that allows for manually choosing a zero and/or infinity value, or when you define your own gear, please note:

The zero value must be a neutral element of addition and subtraction in T_weight, i.e., for any value v in T_weight, v + zero == v and v - zero == v need to hold.

The infinity value must be larger (w.r.t. to the comparison operators of weights) than all T_weight values that can occur as edge weight or as distance of vertices (sum of a set of edge weights) in the use cases of the gear.

Note: The infinity value does not need to be a special, build-in infinity value of the type used for weights and distances, with the usual guarantees made for arithmetic operations and comparisons in such cases. And it does not even need to be the largest value in T_weight. As example, consider a collection that operates on int distances, stores them in an array of C-native unsigned short integers, is restricted to distances from 0 up to 65534 (and this is enough for the use cases), and uses 65535 as positive infinity value.

(In such scenarios, a special kind of error can occur: An arithmetic operation might return a result that reaches or exceeds the infinity value, but stays within the limits of the distances type, so that the operation does not raise an overflow exception. In order to avoid wrong analysis results, NoGraphs detects this kind of error in its calculations and raises an exception itself, whilst it fully relies on the arithmetic operations for the handling of any other kind of overflow, underflow and accuracy problems.)

abstract zero()

Return the zero value of T_weight, e.g., 0.0 for float.

Return type:: T_weight

abstract infinity()

Return the positive infinity value of T_weight for the gear, e.g., float(“infinity”) for float.

Return type:: T_weight

abstract vertex_id_to_distance_mapping(initial_content)

Factory for a mapping from a vertex id to a distance value.

If the returned mapping does not contain a value for some key, its method __getitem__ needs to return the positive infinity value.

Parameters:: initial_content (Iterable[Tuple[T_vertex_id, T_weight]]) – The collection is created with this initial content.
Return type:: MutableMapping[T_vertex_id, T_weight]

Gears for hashable vertex ids

class nographs.GearForHashableVertexIDs(zero, inf)

Bases: Gear[T_vertex, T_vertex_id, T_weight, T_labels]

Factory methods for bookkeeping collections. For graphs with hashable vertices (or vertices made hashable by providing a VertexToID function to the traversal).

It uses hash-based collections (e.g., set and dict) for storing data.

Parameters:

zero (T_weight) – Value of type T_weight that is used to represent zero distance.
inf (T_weight) – Value of type T_weight that is used to represent infinite distance (larger than any finite distance that might occur)

Subclasses:

class nographs.GearDefault

Bases: Generic[T_vertex, T_vertex_id, T_weight, T_labels], GearForHashableVertexIDs[T_vertex, T_vertex_id, Union[T_weight, float], T_labels]

A GearForHashableVertexIDs (see there).

For functionality of NoGraphs that deals with edge weights and distances:

It uses the integer 0 for zero distance, and float(“infinity”) for infinite distance and thus, Union[T_weight, float] as type of distances.

The choice of these two numbers has the following consequences:

Additional requirement for T_weight: Additionally to the usual requirements for edge weights in NoGraphs (see T_weight), it needs to be possible to add the integer 0 to a weight, and a weight needs to be comparable to float(“infinity”).
Distances calculated and returned by NoGraphs can not only be values of the chosen type T_weight for edge weights, but also the integer 0 and float(“infinity”).
In typed code, a traversal object that uses GearDefault must be declared with Union[T_weight, float] for the weight type because it might return a float generated by GearDefault as distance (otherwise, your typing is inconsistent, and a static type checker will report an error).

Examples for typical T_weight number types that can be used with GearDefault, because they fulfil the requirements described above:

float, int, Decimal and class mpf of library mpmath.

Due to this wide range of supported scenarios, GearDefault is the gear that is used most often in NoGraphs.

class nographs.GearForHashableVertexIDsAndIntsMaybeFloats

Bases: GearForHashableVertexIDs[T_vertex, T_vertex_id, float, T_labels]

A GearForHashableVertexIDs for weights that are of type float or integer.

It uses the integer 0 for zero distance. If all occurring edge weights are also integers, all reported distances of reached vertices will also be integers. So, this gear can also be used for calculations within the integers.

It uses float(“infinity”) for infinite distance. So, infinite distance will always be reported as float.

class nographs.GearForHashableVertexIDsAndDecimals

Bases: GearForHashableVertexIDs[T_vertex, T_vertex_id, Decimal, T_labels]

A GearForHashableVertexIDs for weights that are of type Decimal.

class nographs.GearForHashableVertexIDsAndFloats

Bases: GearForHashableVertexIDs[T_vertex, T_vertex_id, float, T_labels]

A GearForHashableVertexIDs for weights that are of type float.

Gears for integer vertex ids

class nographs.GearForIntVertexIDs(zero, inf, no_arrays=False, no_bit_packing=False, pre_allocate=0)

Bases: Gear[T_vertex, int, T_weight, T_labels], Generic[T_vertex, T_weight, T_labels]

Factory methods for bookkeeping collections. For graphs with vertex IDs that are non-negative integers (to be exact: they should be a dense subset of the natural numbers starting at 0). (Either, your vertices are such numbers, or you assign such numbers as IDs to them, see tutorial section about vertex identity).

Trades type flexibility and runtime for an (often large) reduction of the memory consumption: Uses sequence-based collections (instead of hash-based collections like dict and set) for bookkeeping. Arrays are preferred over lists, since there, data can be stored as C-native values. Boolean values are packed into integers.

Notes:

If you are on a 32-bit system, lists and arrays can not be larger than sys.maxsize/4 = 536,870,912 entries, what limits your vertex ids (and vertices, if you do not use a VertexToID function).
NoGraphs does not access the lists or arrays via an emulation of the mappings that are demanded by protocol Gear, but is able to directly access them, and the code for this is inlined, for better performance.

Parameters:

zero (T_weight) – Value used to represent zero distance.
inf (T_weight) – Value used to represent infinite distance.
no_arrays (bool) – Use only lists, no arrays. (Depending on the used traversal and the graph, arrays can reduce the memory consumption by up to 88% in comparison to lists, but runtime can increase by up to 10%.)
no_bit_packing (bool) – Store boolean values of vertex ID sets as integers instead of bits. (Depending on the used traversal and the graph, bit packing can reduce the memory consumption by up to 85%, but runtime can increase by up to 30%. By default, bit packing is used where possible.)
pre_allocate (int) – Space for this number of vertices is pre-allocated when a collection is requested by NoGraphs. Default: 0.

Subclasses:

class nographs.GearForIntVertexIDsAndIntsMaybeFloats(no_arrays=False, no_bit_packing=False, pre_allocate=0)

Bases: GearForIntVertexIDs[T_vertex, float, T_labels]

A GearForIntVertexIDs for weights that are of type float or integer.

It uses the integer 0 for zero distances. If all occurring edge weights are also integers, all reported distances of reached vertices will also be integers. So, this gear can also be used for calculations within the integers.

It uses float(“infinity”) for infinite distance. So, infinite distance will always be reported as float.

Parameters:

no_arrays (bool) – Use only lists, no arrays. See GearForIntVertexIDs.
no_bit_packing (bool) – Store boolean values in vertex sets as integers instead of bits. See GearForIntVertexIDs.
pre_allocate (int) – Space for this number of vertices is pre-allocated when a collection is requested by NoGraphs. Default: 0.

class nographs.GearForIntVertexIDsAndDecimals(no_arrays=False, no_bit_packing=False, pre_allocate=0)

Bases: GearForIntVertexIDs[T_vertex, Decimal, T_labels]

A GearForIntVertexIDs for weights that are of type Decimal.

Parameters:

no_arrays (bool) – Use lists instead of arrays. See GearForIntVertexIDs.
no_bit_packing (bool) – Store boolean values in vertex sets as integers instead of bits. See GearForIntVertexIDs.
pre_allocate (int) – Space for this number of vertices is pre-allocated when a collection is requested by NoGraphs. Default: 0.

class nographs.GearForIntVertexIDsAndCFloats(no_bit_packing=False, distance_type_code='f', pre_allocate=0)

Bases: GearForIntVertexIDs[T_vertex, float, T_labels]

A GearForIntVertexIDs for weights that are floats in the limits of some C-native float type.

Here, arrays and C-native storage of data are also used for distances.

Parameters:

no_bit_packing (bool) – Store boolean values in vertex sets as integers instead of bits. See GearForIntVertexIDs.
distance_type_code (Literal['f', 'd']) –
Number of bytes used to store distances float values, as type_code (see class array.array of the Python standard library):
- ”f” (default): 4 bytes float.
- ”d”: 8 bytes float.
pre_allocate (int) – Space for this number of vertices is pre-allocated when a collection is requested by NoGraphs. Default: 0.

class nographs.GearForIntVertexIDsAndCInts(no_bit_packing=False, distance_type_code='l', pre_allocate=0)

Bases: GearForIntVertexIDs[T_vertex, int, T_labels]

A GearForIntVertexIDs for weights that are integers in the limits of some C-native integer type.

Here, arrays and C-native storage of data are also used for distances.

Parameters:

no_bit_packing (bool) – Store boolean values in vertex sets as integers instead of bits. See GearForIntVertexIDs.
distance_type_code (Literal['b', 'B', 'h', 'H', 'i', 'I', 'l', 'L', 'q', 'Q']) –
Number of bytes used to store distances integer values, as type_code (see class array.array of the Python standard library):
- ”l” (default): 4 bytes signed long.
- ”b”, “B”, “h”, “H”, “i”, “I”, “L”, “q”, “Q”: See class array.array
pre_allocate (int) – Space for this number of vertices is pre-allocated when a collection is requested by NoGraphs. Default: 0.

Gears for integer vertices and ids

class nographs.GearForIntVerticesAndIDs(zero, inf, no_bit_packing=False, vertex_type_code='L', pre_allocate=0)

Bases: GearForIntVertexIDs[int, T_weight, T_labels]

A GearForIntVertexIDs (see there for constraints on vertex ids) for graphs with vertices, that are non-negative integers and fulfil one of the offered size constraints.

Here, arrays and C-native storage of data are also used for vertices.

Parameters:

zero (T_weight) – Value used to represent zero distance.
inf (T_weight) – Value used to represent infinite distance.
no_bit_packing (bool) – Store boolean values of vertex ID sets as integers instead of bits. (Depending on the used traversal and the graph, bit packing can reduce the memory consumption by up to 85%, but runtime can increase by up to 30%. By default, bit packing is used where possible.)
vertex_type_code (Literal['L', 'Q', 'I']) –
Number of bytes used to store one of your integer vertices, as type_code.
- ”L” (default): 4 bytes. Allows for integers in range(4.294.967.296).
- ”Q”: 8 bytes. In case you really need more than “L”…
- ”I”: 2 bytes. If range(65536) is enough.
Note: The highest respective value cannot be used as vertex, since it is used for internal purposes (flag for keys without values).
pre_allocate (int) – If you provide a value for parameter pre_allocate, space for this number of vertices is pre-allocated when a collection is requested by NoGraphs.

Subclasses:

class nographs.GearForIntVerticesAndIDsAndIntsMaybeFloats(no_bit_packing=False, vertex_type_code='L', pre_allocate=0)

Bases: GearForIntVerticesAndIDs[float, T_labels]

A GearForIntVerticesAndIDs for weights that are of type float or integer.

It uses the integer 0 for zero distances. If all occurring edge weights are also integers, all reported distances of reached vertices will also be integers. So, this gear can also be used for calculations within the integers.

It uses float(“infinity”) for infinite distance. So, infinite distance will always be reported as float.

Parameters:

no_bit_packing (bool) – Store boolean values in vertex sets as integers instead of bits. See GearForIntVerticesAndIDs.
vertex_type_code (Literal['L', 'Q', 'I']) – Number of bytes used to store one of your integer vertices, as type_code. See GearForIntVerticesAndIDs.
pre_allocate (int) – Space for this number of vertices is pre-allocated when a collection is requested by NoGraphs. Default: 0.

class nographs.GearForIntVerticesAndIDsAndDecimals(no_bit_packing=False, vertex_type_code='L', pre_allocate=0)

Bases: GearForIntVerticesAndIDs[Decimal, T_labels]

A GearForIntVerticesAndIDs for weights that are of type Decimal.

Parameters:

no_bit_packing (bool) – Store boolean values of vertex id sets as integers instead of bits. See GearForIntVerticesAndIDs.
vertex_type_code (Literal['L', 'Q', 'I']) – Number of bytes used to store one of your integer vertices, as type_code. See GearForIntVerticesAndIDs.
pre_allocate (int) – Space for this number of vertices is pre-allocated when a collection is requested by NoGraphs. Default: 0.

class nographs.GearForIntVerticesAndIDsAndCFloats(no_bit_packing=False, vertex_type_code='L', distance_type_code='f', pre_allocate=0)

Bases: GearForIntVerticesAndIDs[float, T_labels]

A GearForIntVerticesAndIDs for weights that are floats in the limits of some C-native float type.

Here, arrays and C-native storage of data are also used for weights.

Parameters:

no_bit_packing (bool) – Store boolean values of vertex id sets as integers instead of bits. See GearForIntVerticesAndIDs.
vertex_type_code (Literal['L', 'Q', 'I']) – Number of bytes used to store one of your integer vertices, as type_code. See GearForIntVerticesAndIDs.
distance_type_code (Literal['f', 'd']) –
Number of bytes used to store distances float values, as type_code (see class array.array of the Python standard library):
- ”f” (default): 4 bytes float.
- ”d”: 8 bytes float.
pre_allocate (int) – If you provide a value for parameter pre_allocate, space for this number of vertices is pre-allocated when a collection is requested by NoGraphs.

class nographs.GearForIntVerticesAndIDsAndCInts(no_bit_packing=False, vertex_type_code='L', distance_type_code='l', pre_allocate=0)

Bases: GearForIntVerticesAndIDs[int, T_labels]

A GearForIntVerticesAndIDs for weights that are integers in the limits of some C-native integer type.

Here, arrays and C-native storage of data are also used for weights.

Parameters:

no_bit_packing (bool) – Store boolean values of vertex id sets as integers instead of bits. See GearForIntVerticesAndIDs.
vertex_type_code (Literal['L', 'Q', 'I']) – Number of bytes used to store one of your integer vertices, as type_code. See GearForIntVerticesAndIDs.
distance_type_code (Literal['b', 'B', 'h', 'H', 'i', 'I', 'l', 'L', 'q', 'Q']) –
Number of bytes used to store distances integer values, as type_code (see class array.array of the Python standard library):
- ”l” (default): 4 bytes signed long.
- ”b”, “B”, “h”, “H”, “i”, “I”, “L”, “q”, “Q”: See class array.array
pre_allocate (int) – If you provide a value for parameter pre_allocate, space for this number of vertices is pre-allocated when a collection is requested by NoGraphs.