ActionDigraph

This page contains the documentation for the class ActionDigraph.

ActionDigraph(*args, **kwargs)

Overloaded function.

ActionDigraph.add_edge(self, i, j, lbl)

Add an edge from i to j labelled lbl.

ActionDigraph.add_nodes(self, nr)

Adds nr nodes to this.

ActionDigraph.add_to_out_degree(self, nr)

Adds nr to the out-degree of this.

ActionDigraph.algorithm(self, value)

Members:

ActionDigraph.edges_iterator(self, i)

Returns an iterator to the edges of a node in the digraph.

ActionDigraph.neighbor(self, v, lbl)

Get the range of the edge with source node v and edge-label lbl.

ActionDigraph.next_neighbor(self, v, i)

Get the next neighbor of a node that doesn't equal UNDEFINED.

ActionDigraph.nodes_iterator(self)

Returns an iterator to the nodes of the digraph.

ActionDigraph.number_of_edges(*args, **kwargs)

Overloaded function.

ActionDigraph.number_of_nodes(self)

Returns the number of nodes of this.

ActionDigraph.number_of_paths(*args, **kwargs)

Overloaded function.

ActionDigraph.number_of_paths_algorithm(...)

Overloaded function.

ActionDigraph.number_of_scc(self)

Returns the number of strongly connected components.

ActionDigraph.out_degree(self)

Returns the maximum out-degree of any node.

ActionDigraph.panilo_iterator(*args, **kwargs)

Overloaded function.

ActionDigraph.panislo_iterator(*args, **kwargs)

Overloaded function.

ActionDigraph.pilo_iterator(*args, **kwargs)

Overloaded function.

ActionDigraph.pislo_iterator(*args, **kwargs)

Overloaded function.

ActionDigraph.pstislo_iterator(*args, **kwargs)

Overloaded function.

ActionDigraph.pstilo_iterator(*args, **kwargs)

Overloaded function.

ActionDigraph.reserve(self, m, n)

Ensures that this has capacity for m nodes each with n out-edges, but does not modify number_of_nodes() or out_degree().

ActionDigraph.reverse_nodes_iterator(self)

Returns a reversed iterator to the nodes of the digraph.

ActionDigraph.reverse_spanning_forest(self)

Returns a Forest comprised of spanning trees for each scc of this, rooted at the minimum node of that component, with edges oriented towards the root.

ActionDigraph.root_of_scc(self, nd)

Returns the root of a strongly connected components containing a given node.

ActionDigraph.scc_id(self, nd)

Returns the id-number of the strongly connected component of a node.

ActionDigraph.scc_iterator(self, arg0)

Returns an iterator pointing to the first node in the scc with the specified id-number.

ActionDigraph.scc_roots_iterator(self)

Returns an iterator pointing to the root of the first scc.

ActionDigraph.sccs_iterator(self)

Returns an iterator for the nodes in the scc.

ActionDigraph.spanning_forest(self)

Returns a Forest comprised of spanning trees for each scc of this, rooted at the minimum node of that component, with edges oriented away from the root.

ActionDigraph.unsafe_neighbor(self, v, lbl)

Get the range of the edge with source node v and edge-label lbl.

ActionDigraph.unsafe_next_neighbor(self, v, i)

Get the next neighbor of a node that doesn't equal UNDEFINED.

ActionDigraph.validate(self)

Check every node has exactly out_degree() out-edges.
class ActionDigraph(*args, **kwargs)

Overloaded function.

  1. __init__(self: _libsemigroups_pybind11.ActionDigraph) -> None

  2. __init__(self: _libsemigroups_pybind11.ActionDigraph, arg0: int) -> None

  3. __init__(self: _libsemigroups_pybind11.ActionDigraph, m: int, n: int) -> None

    Construct from number of nodes and out degree.

    Parameters

    • m (int) the number of nodes in the digraph (default: 0).

    • n (int) the out-degree of every node (default: 0).

  4. __init__(self: _libsemigroups_pybind11.ActionDigraph, arg0: _libsemigroups_pybind11.ActionDigraph) -> None

    Construct a copy.

add_edge(self: _libsemigroups_pybind11.ActionDigraph, i: int, j: int, lbl: int) → None

Add an edge from i to j labelled lbl.

Parameters

  • i (int) -- the source node

  • j (int) -- the target node

  • lbl (int) -- the label of the edge from i to j

Returns

(None)

add_nodes(self: _libsemigroups_pybind11.ActionDigraph, nr: int) → None

Adds nr nodes to this.

Parameters

nr (int) -- the number of nodes to add.

Returns

(None)

add_to_out_degree(self: _libsemigroups_pybind11.ActionDigraph, nr: int) → None

Adds nr to the out-degree of this.

Parameters

nr (int) -- the number of new out-edges for every node.

Returns

(None)

class algorithm(self: _libsemigroups_pybind11.ActionDigraph.algorithm, value: int)

Members:

dfs : Use a depth-first-search.

matrix : Use the adjacency matrix and matrix multiplication.

acyclic :

Use a dynamic programming approach for acyclic digraphs.

trivial : Try to utilise some corner cases.

automatic :

The function number_of_paths() tries to decide which algorithm is best.

property name
edges_iterator(self: _libsemigroups_pybind11.ActionDigraph, i: int) → Iterator

Returns an iterator to the edges of a node in the digraph.

Parameters

i (int) -- the node.

Returns

An iterator.

neighbor(self: _libsemigroups_pybind11.ActionDigraph, v: int, lbl: int) → int

Get the range of the edge with source node v and edge-label lbl.

Parameters

  • v (int) -- the node

  • lbl (int) -- the label

Returns

An int or UNDEFINED.

next_neighbor(self: _libsemigroups_pybind11.ActionDigraph, v: int, i: int) → Tuple[int, int]

Get the next neighbor of a node that doesn't equal UNDEFINED.

Parameters

  • v (int) -- the node

  • i (int) -- the label

Returns

A tuple.

Specifically, a tuple x is returned where

  • x[0] is adjacent to v via an edge labelled x[1];

  • x[1] is the minimum value in the range \([i, N)\) where N is degree() such that neighbor(v, x[1]) is not equal to UNDEFINED.

If neighbor(v, i) is undefined for every value of i, then x[0] and x[1] equal UNDEFINED.

nodes_iterator(self: _libsemigroups_pybind11.ActionDigraph) → Iterator

Returns an iterator to the nodes of the digraph.

number_of_edges(*args, **kwargs)

Overloaded function.

  1. number_of_edges(self: _libsemigroups_pybind11.ActionDigraph) -> int

    Returns the total number of edges.

    Parameters

    None

    Returns

    An int.

  2. number_of_edges(self: _libsemigroups_pybind11.ActionDigraph, n: int) -> int

    Returns the number of edges incident to a node.

    Parameters

    • n the node.

    Returns

    An int.

number_of_nodes(self: _libsemigroups_pybind11.ActionDigraph) → int

Returns the number of nodes of this.

Parameters

None

Returns

An int.

number_of_paths(*args, **kwargs)

Overloaded function.

  1. number_of_paths(self: _libsemigroups_pybind11.ActionDigraph, source: int) -> int

    Returns the number of paths originating at the given source node.

    Parameters

    • source (int) the source node.

    return

    An int.

  2. number_of_paths(self: _libsemigroups_pybind11.ActionDigraph, source: int, min: int, max: int, lgrthm: _libsemigroups_pybind11.ActionDigraph.algorithm) -> int

    Returns the number of paths starting at a given node with length in a given range.

    Parameters

    • source (int) the source node

    • min (int) the minimum length of paths to count

    • max (int) the maximum length of paths to count

    • lgrthm (ActionDigraph.algorithm) the algorithm to use (defaults to: ActionDigraph.algorithm.automatic).

    Returns

    An int.

  3. number_of_paths(self: _libsemigroups_pybind11.ActionDigraph, source: int, target: int, min: int, max: int, lgrthm: _libsemigroups_pybind11.ActionDigraph.algorithm) -> int

    Returns the number of paths between a pair of nodes with length in a given range.

    Parameters

    • source (int) the source node

    • target (int) the target node

    • min (int) the minimum length of paths to count

    • max (int) the maximum length of paths to count

    • lgrthm (ActionDigraph.algorithm) the algorithm to use (defaults to: ActionDigraph.algorithm.automatic)

    Returns

    An int.

  4. number_of_paths(self: _libsemigroups_pybind11.ActionDigraph, source: int, target: int, min: int, max: int) -> int

    Returns the number of paths between a pair of nodes with length in a given range.

    Parameters

    • source (int) the source node

    • target (int) the target node

    • min (int) the minimum length of paths to count

    • max (int) the maximum length of paths to count

    Returns

    An int.

  5. number_of_paths(self: _libsemigroups_pybind11.ActionDigraph, source: int, min: int, max: int) -> int

    Returns the number of paths starting at a node with length in a given range.

    Parameters

    • source (int) the source node

    • min (int) the minimum length of paths to count

    • max (int) the maximum length of paths to count

    Returns

    An int.

  6. number_of_paths(self: _libsemigroups_pybind11.ActionDigraph, arg0: int, arg1: int, arg2: _libsemigroups_pybind11.PositiveInfinity) -> int

number_of_paths_algorithm(*args, **kwargs)

Overloaded function.

  1. number_of_paths_algorithm(self: _libsemigroups_pybind11.ActionDigraph, source: int) -> _libsemigroups_pybind11.ActionDigraph.algorithm

    Returns the algorithm used by number_of_paths() to compute the number of paths originating at the given source node.

    Parameters

    • source (int) the source node.

    Returns

    A value of type ActionDigraph.algorithm.

  2. number_of_paths_algorithm(self: _libsemigroups_pybind11.ActionDigraph, source: int, min: int, max: int) -> _libsemigroups_pybind11.ActionDigraph.algorithm

    Returns the algorithm used by number_of_paths to compute the number of paths originating at the given source node with length in the range $[min, max)$.

    Parameters

    • source (int) the source node

    • min (int) the minimum length of paths to count

    • max (int) the maximum length of paths to count

    Returns

    A value of type ActionDigraph.algorithm.

  3. number_of_paths_algorithm(self: _libsemigroups_pybind11.ActionDigraph, arg0: int, arg1: int, arg2: _libsemigroups_pybind11.PositiveInfinity) -> _libsemigroups_pybind11.ActionDigraph.algorithm

  4. number_of_paths_algorithm(self: _libsemigroups_pybind11.ActionDigraph, source: int, target: int, min: int, max: int) -> _libsemigroups_pybind11.ActionDigraph.algorithm

    Returns the algorithm used by number_of_paths to compute the number of paths originating at the given source node and ending at the given target node with length in the range \([min, max)\).

    Parameters

    • source (int) the source node

    • target (int) the target node

    • min (int) the minimum length of paths to count

    • max (int) the maximum length of paths to count

    Returns

    A value of type ActionDigraph.algorithm.

number_of_scc(self: _libsemigroups_pybind11.ActionDigraph) → int

Returns the number of strongly connected components.

Parameters

None

Returns

An int.

out_degree(self: _libsemigroups_pybind11.ActionDigraph) → int

Returns the maximum out-degree of any node.

Parameters

None

Returns

An int.

panilo_iterator(*args, **kwargs)

Overloaded function.

  1. panilo_iterator(self: _libsemigroups_pybind11.ActionDigraph, source: int, min: int, max: int) -> Iterator

    Returns an iterator to a pair consisting of the edge labels of the first path (in lexicographical order) starting at source with length in the range \([min, max)\) and the last node of that path.

    Parameters

    • source (int) the first node.

    • min (int) the minimum length of a path to enumerate (defaults to 0)

    • max (Union[int, PositiveInfinity]) the maximum length of a path to enumerate (defaults to POSITIVE_INFINITY).

    Returns

    An iterator.

  2. panilo_iterator(self: _libsemigroups_pybind11.ActionDigraph, arg0: int, arg1: int, arg2: _libsemigroups_pybind11.PositiveInfinity) -> Iterator

panislo_iterator(*args, **kwargs)

Overloaded function.

  1. panislo_iterator(self: _libsemigroups_pybind11.ActionDigraph, source: int, min: int, max: int) -> Iterator

    Returns an iterator to a pair consisting of the edge labels of the first path (in short-lex order) starting at source with length in the range \([min, max)\) and the last node of that path.

    Parameters

    • source (int) the first node.

    • min (int) the minimum length of a path to enumerate (defaults to 0)

    • max (Union[int, PositiveInfinity]) the maximum length of a path to enumerate (defaults to POSITIVE_INFINITY).

    Returns

    An iterator.

  2. panislo_iterator(self: _libsemigroups_pybind11.ActionDigraph, arg0: int, arg1: int, arg2: _libsemigroups_pybind11.PositiveInfinity) -> Iterator

pilo_iterator(*args, **kwargs)

Overloaded function.

  1. pilo_iterator(self: _libsemigroups_pybind11.ActionDigraph, source: int, min: int, max: int) -> Iterator

    Returns an iterator to the edge labels of the first path (in lexicographical order) starting at source with length in the range \([min, max)\).

    Parameters

    • source (int) the first node.

    • min (int) the minimum length of a path to enumerate (defaults to 0)

    • max (Union[int, PositiveInfinity]) the maximum length of a path to enumerate (defaults to POSITIVE_INFINITY).

    Returns

    An iterator.

  2. pilo_iterator(self: _libsemigroups_pybind11.ActionDigraph, arg0: int, arg1: int, arg2: _libsemigroups_pybind11.PositiveInfinity) -> Iterator

pislo_iterator(*args, **kwargs)

Overloaded function.

  1. pislo_iterator(self: _libsemigroups_pybind11.ActionDigraph, source: int, min: int, max: int) -> Iterator

    Returns an iterator pointing to the edge labels of the first path (in short-lex order) starting at source with length in the range \([min, max)\).

    Parameters

    • source (int) the first node.

    • min (int) the minimum length of a path to enumerate (defaults to 0)

    • max (Union[int, PositiveInfinity]) the maximum length of a path to enumerate (defaults to POSITIVE_INFINITY).

    Returns

    An iterator.

  2. pislo_iterator(self: _libsemigroups_pybind11.ActionDigraph, arg0: int, arg1: int, arg2: _libsemigroups_pybind11.PositiveInfinity) -> Iterator

pstilo_iterator(*args, **kwargs)

Overloaded function.

  1. pstilo_iterator(self: _libsemigroups_pybind11.ActionDigraph, source: int, target: int, min: int, max: int) -> Iterator

    Returns an iterator to the edge labels of the first path (in lex order) starting at the node source and ending at the node target with length in the range \([min, max)\).

    Parameters

    • source (int) the first node.

    • target (int) the last node.

    • min (int) the minimum length of a path to enumerate (defaults to 0)

    • max (Union[int, PositiveInfinity]) the maximum length of a path to enumerate (defaults to POSITIVE_INFINITY).

    Returns

    An iterator.

  2. pstilo_iterator(self: _libsemigroups_pybind11.ActionDigraph, arg0: int, arg1: int, arg2: int, arg3: _libsemigroups_pybind11.PositiveInfinity) -> Iterator

pstislo_iterator(*args, **kwargs)

Overloaded function.

  1. pstislo_iterator(self: _libsemigroups_pybind11.ActionDigraph, source: int, target: int, min: int, max: int) -> Iterator

    Returns an iterator to the edge labels of the first path (in short-lex order) starting at the node source and ending at the node target with length in the range \([min, max)\).

    Parameters

    • source (int) the first node.

    • min (int) the minimum length of a path to enumerate (defaults to 0)

    • max (Union[int, PositiveInfinity]) the maximum length of a path to enumerate (defaults to POSITIVE_INFINITY).

    Returns

    An iterator.

  2. pstislo_iterator(self: _libsemigroups_pybind11.ActionDigraph, arg0: int, arg1: int, arg2: int, arg3: _libsemigroups_pybind11.PositiveInfinity) -> Iterator

static random(nr_nodes: int, out_degree: int) → _libsemigroups_pybind11.ActionDigraph

Constructs a random ActionDigraph with the specified number of nodes and out-degree.

Parameters

  • nr_nodes (int) -- the number of nodes

  • out_degree (int) -- the maximum out-degree of every node

Returns

An ActionDigraph.

static random_acyclic(nr_nodes: int, out_degree: int, nr_edges: int) → _libsemigroups_pybind11.ActionDigraph

Constructs a random acyclic ActionDigraph with the specified number of nodes and edges, and out-degree.

Parameters

  • nr_nodes (int) -- the number of nodes

  • out_degree (int) -- the out-degree of every node

  • nr_edges (int) -- the out-degree of every node

Returns

An ActionDigraph.

reserve(self: _libsemigroups_pybind11.ActionDigraph, m: int, n: int) → None

Ensures that this has capacity for m nodes each with n out-edges, but does not modify number_of_nodes() or out_degree().

Parameters

  • m (int) -- the number of nodes

  • n (int) -- the out-degree

Returns

(None)

reverse_nodes_iterator(self: _libsemigroups_pybind11.ActionDigraph) → Iterator

Returns a reversed iterator to the nodes of the digraph.

reverse_spanning_forest(self: _libsemigroups_pybind11.ActionDigraph) → libsemigroups::Forest

Returns a Forest comprised of spanning trees for each scc of this, rooted at the minimum node of that component, with edges oriented towards the root.

Returns

A Forest.

root_of_scc(self: _libsemigroups_pybind11.ActionDigraph, nd: int) → int

Returns the root of a strongly connected components containing a given node.

Parameters

nd (int) -- a node.

Returns

An int.

scc_id(self: _libsemigroups_pybind11.ActionDigraph, nd: int) → int

Returns the id-number of the strongly connected component of a node.

Parameters

nd (int) -- the node.

Parameters

None

Returns

An int.

scc_iterator(self: _libsemigroups_pybind11.ActionDigraph, arg0: int) → Iterator

Returns an iterator pointing to the first node in the scc with the specified id-number.

scc_roots_iterator(self: _libsemigroups_pybind11.ActionDigraph) → Iterator

Returns an iterator pointing to the root of the first scc.

sccs_iterator(self: _libsemigroups_pybind11.ActionDigraph) → Iterator

Returns an iterator for the nodes in the scc.

spanning_forest(self: _libsemigroups_pybind11.ActionDigraph) → libsemigroups::Forest

Returns a Forest comprised of spanning trees for each scc of this, rooted at the minimum node of that component, with edges oriented away from the root.

Returns

A Forest.

unsafe_neighbor(self: _libsemigroups_pybind11.ActionDigraph, v: int, lbl: int) → int

Get the range of the edge with source node v and edge-label lbl.

Parameters

  • v (int) -- the node

  • lbl (int) -- the label

Returns

An int or UNDEFINED.

unsafe_next_neighbor(self: _libsemigroups_pybind11.ActionDigraph, v: int, i: int) → Tuple[int, int]

Get the next neighbor of a node that doesn't equal UNDEFINED.

Parameters

  • v (int) -- the node

  • i (int) -- the label

Returns

A tuple.

Specifically, a tuple x is returned where

  • x[0] is adjacent to v via an edge labelled x[1];

  • x[1] is the minimum value in the range \([i, N)\) where N is degree() such that neighbor(v, x[1]) is not equal to UNDEFINED.

If neighbor(v, i) is undefined for every value of i, then x[0] and x[1] equal UNDEFINED.

validate(self: _libsemigroups_pybind11.ActionDigraph) → bool

Check every node has exactly out_degree() out-edges.

Parameters

None

Returns

A bool.