Helper functions for ActionDigraph¶

This page contains the documentation for helper function for the class ActionDigraph.

`add_cycle`	Adds a cycle consisting of `N` new nodes.
`dot`	Returns a `graphviz.Digraph` of an `ActionDigraph`.
`follow_path`	Find the node that a path starting at a given node leads to.
`is_acyclic`	Check if a digraph is acyclic.
`make`	Overloaded function.
`out_neighbors`	Returns the list of out-neighbor of the action digraph `d`.
`topological_sort`	Overloaded function.

add_cycle(ad: _libsemigroups_pybind11.ActionDigraph, N: int) → None¶

Adds a cycle consisting of N new nodes.

Parameters

ad (ActionDigraph) -- the action digraph.
N (int) -- the length of the cycle.

Returns

None.

dot(d: ActionDigraph) → Digraph¶

Returns a graphviz.Digraph of an ActionDigraph.

Parameters: d (ActionDigraph) -- the ActionDigraph
Returns: A graphviz representation of the input action digraph.
Return type: graphviz.Digraph

>>> from libsemigroups_pybind11 import action_digraph_helper
>>> d = action_digraph_helper.make(5, [[1, 0], [2], [3, 4]])
>>> action_digraph_helper.dot(d).view()  

follow_path(ad: _libsemigroups_pybind11.ActionDigraph, source: int, path: List[int]) → int¶

Find the node that a path starting at a given node leads to.

Parameters

ad (ActionDigraph) -- the ActionDigraph object to check.
first (int) -- the starting node.
path (List[int]) -- the path to follow.

Returns

An int corresponding to the node at the end of the path or UNDEFINED otherwise.

Raises

RuntimeError -- if source is not a node in the digraph or path contains a value that is not an edge-label.

is_acyclic(ad: _libsemigroups_pybind11.ActionDigraph) → bool¶

Check if a digraph is acyclic.

A digraph is acyclic if every directed cycle is trivial.

Parameters: ad (ActionDigraph) -- the digraph.
Returns: A bool.

make(num_nodes: int, l: List[List[int]]) → ActionDigraph¶

Constructs a digraph from number of nodes and a list.

This function constructs an ActionDigraph from its arguments whose out-degree is specified by the length of the first list in the 2nd parameter.

Parameters

num_nodes (int) -- the number of nodes in the digraph.
l (List[List[int]]) -- the out-neighbors of the digraph.

Returns

An ActionDigraph.

Raises

RuntimeError -- if ActionDigraph.add_edge() raises when adding edges from l.

Complexity

\(O(mn)\) where \(m\) is the length of l and \(n\) is the parameter num_nodes.

>>> from libsemigroups_pybind11 import action_digraph_helper
>>> # Construct an action digraph with 5 nodes and 10 edges (7
>>> # specified)
>>> action_digraph_helper.make(5, [[0, 0], [1, 1], [2], [3, 3]])
<action digraph with 5 nodes, 7 edges, 2 out-degree>

out_neighbors(d: ActionDigraph) → List[List[int]]¶

Returns the list of out-neighbor of the action digraph d.

Parameters: d (ActionDigraph) -- the ActionDigraph
Returns: A list l where l[i][j] equals ActionDigraph.neighbor() with arguments i and j.
Return type: List[List[int]]

>>> from libsemigroups_pybind11 import action_digraph_helper
>>> d = action_digraph_helper.make(5, [[1, 0], [2], [3, 4]])
>>> action_digraph_helper.out_neighbors(d)  
[[1, 0], ..., [18446744073709551615, 18446744073709551615]]

topological_sort(*args, **kwargs)¶

Overloaded function.

topological_sort(ad: _libsemigroups_pybind11.ActionDigraph) -> List[int]
Returns the nodes of the digraph in topological order (see below) if possible.

If it is not empty, the returned list has the property that if an edge from a node n points to a node m, then m occurs before n in the list.
Parameters
ad (ActionDigraph) the digraph.
Returns

A list of int.
topological_sort(ad: _libsemigroups_pybind11.ActionDigraph, source: int) -> List[int]
Returns the nodes of the digraph reachable from a given node in topological order (see below) if possible.

If it is not empty, the returned list has the property that if an edge from a node n points to a node m, then m occurs before n in the list, and the last item in the list is source.
Parameters
ad (ActionDigraph) the digraph.

source (int) the source node.
Returns

A list of int.