Ctrl+K

differt_core.rt.graph module

differt_core.rt.graph module#

TODO.

class AllPathsFromCompleteGraphChunksIter#

Bases: object

An iterator over all paths in a complete graph, as array chunks.

class AllPathsFromCompleteGraphIter#

Bases: object

An iterator over all paths in a complete graph.

Note

Even though this iterator is generally sized, this is not true when its length is so large that overflow occurred when computing its theoretical length. For lengths close or above usize::MAX, do not rely on the provided size hint nor the length.

class AllPathsFromDiGraphChunksIter#

Bases: object

An iterator over all paths in a directed graph, as array chunks.

class AllPathsFromDiGraphIter#

Bases: object

An iterator over all paths in a directed graph.

class CompleteGraph(num_nodes)#

Bases: object

A complete graph, i.e., a simple undirected graph in which every pair of distinc nodes is connected by a unique edge.

all_paths(from_, to, depth, *, include_from_and_to=True)#

Return an iterator over all paths of length depth from node from to node to.

Note

Unlike for DiGraph’s iterators, from_ and to nodes do not need to be part of the graph (i.e., node_id >= num_nodes). This is especially useful to generate all paths from from_ to to, where from_ and to will only ever appear in the first and last position, respectively.

Therefore, those iterators are equivalents:

>>> from differt_core.rt.graph import CompleteGraph, DiGraph
>>>
>>> num_nodes, depth = 100, 5
>>> complete_graph = CompleteGraph(num_nodes)
>>> di_graph = DiGraph.from_complete_graph(complete_graph)
>>> from_, to = (
...     di_graph.insert_from_and_to_nodes(
...         direct_path=True
...     )
... )
>>>
>>> iter1 = complete_graph.all_paths(from_, to, depth)
>>> iter2 = di_graph.all_paths(from_, to, depth)
>>> assert(
...     all(
...         np.array_equal(p1, p2)
...         for p1, p2 in zip(iter1, iter2)
...     )
... )

This note also applies to all_paths_array and all_paths_array_chunks.

Parameters:

  • from_ (int) – The node index to find the paths from.

  • to (int) – The node index to find the paths to.

  • depth (int) – The number of nodes to include in each path.

  • include_from_and_to (bool) – Whether to include or not from and to nodes in the output paths. If set to False, the output paths will include depth - 2 nodes.

Returns:

An iterator over all paths.

Return type:

AllPathsFromCompleteGraphIter

all_paths_array(from_, to, depth, *, include_from_and_to=True)#

Return an array of all paths of length depth from node from to node to.

Parameters:

  • from_ (int) – The node index to find the paths from.

  • to (int) – The node index to find the paths to.

  • depth (int) – The number of nodes to include in each path.

  • include_from_and_to (bool) – Whether to include or not from and to nodes in the output paths. If set to False, the output paths will include depth - 2 nodes.

Returns:

An array of all paths.

Return type:

UInt[ndarray, "num_paths path_depth"]

all_paths_array_chunks(from_, to, depth, *, include_from_and_to=True, chunk_size=1000)#

Return an iterator over all paths of length depth from node from to node to, grouped in chunks of size of max. chunk_size.

Parameters:

  • from_ (int) – The node index to find the paths from.

  • to (int) – The node index to find the paths to.

  • depth (int) – The number of nodes to include in each path.

  • include_from_and_to (bool) – Whether to include or not from and to nodes in the output paths. If set to False, the output paths will include depth - 2 nodes.

  • chunk_size (int) – The size of each chunk.

Returns:

An iterator over all paths, as array chunks.

Return type:

AllPathsFromCompleteGraphChunksIter

class DiGraph#

Bases: object

A directed graph.

all_paths(from_, to, depth, *, include_from_and_to=True)#

Return an iterator over all paths of length depth from node from to node to.

Parameters:

  • from_ (int) – The node index to find the paths from.

  • to (int) – The node index to find the paths to.

  • depth (int) – The number of nodes to include in each path.

  • include_from_and_to (bool) – Whether to include or not from and to nodes in the output paths. If set to False, the output paths will include depth - 2 nodes.

Returns:

An iterator over all paths.

Return type:

AllPathsFromDiGraphIter

all_paths_array(from_, to, depth, *, include_from_and_to=True)#

Return an array of all paths of length depth from node from to node to.

Parameters:

  • from_ (int) – The node index to find the paths from.

  • to (int) – The node index to find the paths to.

  • depth (int) – The number of nodes to include in each path.

  • include_from_and_to (bool) – Whether to include or not from and to nodes in the output paths. If set to False, the output paths will include depth - 2 nodes.

Returns:

An array of all paths.

Return type:

UInt[ndarray, "num_paths path_depth"]

all_paths_array_chunks(from_, to, depth, *, include_from_and_to=True, chunk_size=1000)#

Return an iterator over all paths of length depth from node from to node to, grouped in chunks of size of max. chunk_size.

Parameters:

  • from_ (int) – The node index to find the paths from.

  • to (int) – The node index to find the paths to.

  • depth (int) – The number of nodes to include in each path.

  • include_from_and_to (bool) – Whether to include or not from and to nodes in the output paths. If set to False, the output paths will include depth - 2 nodes.

  • chunk_size (int) – The size of each chunk.

Returns:

An iterator over all paths, as array chunks.

Return type:

AllPathsFromDiGraphChunksIter

from_adjacency_matrix(adjacency_matrix)#

Create a directed graph from an adjacency matrix.

Each row of the adjacency matrix M contains boolean entries: if M[i, j] is True, then node i is connected to node j.

Parameters:

adjacency_matrix (Bool[ndarray, "num_nodes num_nodes"]) – The adjacency matrix.

Returns:

A directed graph.

Return type:

DiGraph

from_complete_graph(graph)#

Create a directed graph from a complete graph.

This is equivalent to creating a directed graph from an adjacency matrix will all entries equal to True, except on the main diagonal (i.e., no loop).

Parameters:

graph (CompleteGraph) – The complete graph.

Returns:

A directed graph.

Return type:

DiGraph

insert_from_and_to_nodes(*, direct_path=True)#

Insert two additional nodes in the graph:

  • a from node, that is connected to every other node in the graph;

  • and a to node, where every other node is connected to this node.

If direct_path is True, then the from node is connected to the to node.

Parameters:

direct_path (bool) – Whether to create a direction connection between from and to nodes.

Returns:

The indices of the two added nodes in the graph.

Return type:

tuple[int, int]

Contents