WordGraph helpers

This page contains the documentation for various helper functions for manipulating word graphs.

Contents

`add_cycle`(…)	Adds a cycle consisting of N new nodes.
`adjacency_matrix`(…)	Returns the adjacency matrix of a word graph.
`dot`(…)	Returns a `Dot` object representing a word graph.
`equal_to`(…)	Compares two word graphs on a range of nodes.
`follow_path`(…)	Find the node that a path starting at a given node leads to (if any).
`is_acyclic`(…)	Overloaded function.
`is_compatible`(…)	Check if a word graph is compatible with some relations at a range of nodes.
`is_complete`(…)	Overloaded function.
`is_connected`(…)	Check if a word graph is connected.
`is_reachable`(…)	Check if there is a path from one node to another.
`is_strictly_cyclic`(…)	Check if every node is reachable from some node.
`last_node_on_path`(…)	Returns the last node on the path labelled by a word and the index of the position in the word reached.
`nodes_reachable_from`(…)	Returns the set of nodes reachable from a given node in a word graph.
`number_of_nodes_reachable_from`(…)	Returns the number of nodes reachable from a given node in a word graph.
`random_acyclic`(…)	Construct a random acyclic word graph from number of nodes and out-degree.
`spanning_tree`(…)	Overloaded function.
`standardize`(…)	Overloaded function.
`topological_sort`(…)	Overloaded function.

Full API

This page contains the documentation for various helper functions for manipulating WordGraph objects. All such functions are contained in the subpackage word_graph.

word_graph.add_cycle(wg: WordGraph, n: int) → None

Adds a cycle consisting of N new nodes.

Parameters:

wg (WordGraph) – the WordGraph object to add a cycle to.
n (int) – the length of the cycle and number of new nodes to add.

Complexity:

\(O(n)\) where \(n\) is the second parameter.

word_graph.adjacency_matrix(wg: WordGraph) → numpy.ndarray[numpy.float64] | Matrix

Returns the adjacency matrix of a word graph.

This function returns the adjacency matrix of the word graph wg. The type of the returned matrix depends on whether or not libsemigroups is compiled with eigen enabled. The returned matrix has the number of edges with source s and target t in the (s, t)-entry.

Parameters:: wg (WordGraph) – the word graph.
Returns:: The adjacency matrix.
Return type:: numpy.ndarray[numpy.float64] | Matrix

word_graph.dot(wg: WordGraph) → Dot

Returns a Dot object representing a word graph.

This function returns a Dot object representing the word graph wg.

Parameters:: wg (WordGraph) – the word graph.
Returns:: A Dot object.
Return type:: Dot

word_graph.equal_to(x: WordGraph, y: WordGraph, first: int, last: int) → bool

Compares two word graphs on a range of nodes.

This function returns True if the word graphs x and y are equal on the range of nodes from first to last ; and False otherwise.

The word graphs x and y are equal at a node s if:

the out-degrees of x and y coincide;
the edges with source s and label a have equal targets in x and y for every label a.

Parameters:

x (WordGraph) – the first word graph for comparison.
y (WordGraph) – the second word graph for comparison.
first (int) – the first node in the range.
last (int) – the last node in the range plus 1.

Returns:

Whether or not the word graphs are equal at the specified range of nodes.

Return type:

bool

Raises:

LibsemigroupsError – if first is not a node in x or not a node in y ; or if last - 1 is not a node in x or not a node in y.

Note

It is also possible to compare two entire word graphs using ==.

word_graph.follow_path(wg: WordGraph, source: int, path: list[int]) → int | Undefined

Find the node that a path starting at a given node leads to (if any).

This function attempts to follow the path in the word graph wg starting at the node source labelled by the word path. If this path exists, then the last node on that path is returned. If this path does not exist, then UNDEFINED is returned.

Parameters:

wg (WordGraph) – a word graph.
source (int) – the starting node.
path (list[int]) – the path to follow.

Returns:

The last node on the path or UNDEFINED.

Return type:

int | Undefined

Raises:

LibsemigroupsError – if source is not a node in the word graph or path contains a value that is not an edge-label.

Complexity:

Linear in the length of path.

word_graph.is_acyclic(*args, **kwargs)

Overloaded function.

word_graph.is_acyclic(wg: WordGraph) → bool

Check if a word graph is acyclic.

This function returns True if the word graph wg is acyclic and False otherwise. A word graph is acyclic if every directed cycle in the word graph is trivial.

Parameters:: wg (WordGraph) – the WordGraph object to check.
Returns:: Whether or not the word graph is acyclic.
Return type:: bool
Complexity:: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph.out_degree.

>>> from libsemigroups_pybind11 import WordGraph, word_graph
>>> wg = WordGraph()
>>> wg.add_nodes(2)
<WordGraph with 2 nodes, 0 edges, & out-degree 0>
>>> wg.add_to_out_degree(1)
<WordGraph with 2 nodes, 0 edges, & out-degree 1>
>>> wg.target(0, 0, 1)
<WordGraph with 2 nodes, 1 edges, & out-degree 1>
>>> wg.target(1, 0, 0)
<WordGraph with 2 nodes, 2 edges, & out-degree 1>
>>> word_graph.is_acyclic(wg)
False

word_graph.is_acyclic(wg: WordGraph, source: int) → bool

Check if the word graph induced by the nodes reachable from a source node is acyclic.

This function returns True if the word graph consisting of the nodes reachable from source in the word graph wg is acyclic and False if not. A word graph is acyclic if every directed cycle in the word graph is trivial.

Parameters:

wg (WordGraph) – the WordGraph object to check.
source (int) – the source node.

Returns:

Whether the induced subgraph of wg consisting of those nodes reachable from source is acyclic or not.

Return type:

bool

Complexity:

\(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph.out_degree.

>>> from libsemigroups_pybind11 import WordGraph, word_graph
>>> wg = WordGraph()
>>> wg.add_nodes(4).add_to_out_degree(1)
<WordGraph with 4 nodes, 0 edges, & out-degree 1>
>>> wg.target(0, 0, 1).target(1, 0, 0).target(2, 0, 3)
<WordGraph with 4 nodes, 3 edges, & out-degree 1>
>>> word_graph.is_acyclic(wg)
True
>>> word_graph.is_acyclic(wg, 0)
True
>>> word_graph.is_acyclic(wg, 1)
True
>>> word_graph.is_acyclic(wg, 2)
True
>>> word_graph.is_acyclic(wg, 3)
True

word_graph.is_acyclic(wg: WordGraph, source: int, target: int) → bool

Check if the word graph induced by the nodes reachable from a source node and from which a target node can be reached is acyclic.

This function returns True if the word graph consisting of the nodes reachable from source and from which target is reachable, in the word graph wg, is acyclic; and False if not. A word graph is acyclic if every directed cycle of the word graph is trivial.

Parameters:

wg (WordGraph) – the WordGraph object to check.
source (int) – the source node.
target (int) – the target node.

Returns:

Whether or not the subgraph is acyclic.

Return type:

bool

Complexity:

\(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph.out_degree.

word_graph.is_compatible(wg: WordGraph, first_node: int, last_node: int, lhs: list[int], rhs: list[int]) → bool

Check if a word graph is compatible with some relations at a range of nodes.

This function returns True if the word graph wg is compatible with the word lhs and rhs with source node equal to every node in the range from first_node to last_node. This means that the paths with given sources that are labelled by lhs lead to the same nodes as the paths labelled by rhs.

Parameters:

wg (WordGraph) – the word graph.
first_node (int) – the first node.
last_node (int) – one more than the last node.
lhs (list[int]) – the first rule.
rhs (list[int]) – the second rule.

Returns:

Whether or not the word graph is compatible with the given rules at each one of the given nodes.

Return type:

bool

Raises:

LibsemigroupsError – if any of the nodes in the range between first_node and last_node does not belong to wg (i.e. is greater than or equal to WordGraph.number_of_nodes).
LibsemigroupsError – if lhs or rhs contains an invalid label (i.e. one greater than or equal to WordGraph.out_degree).

word_graph.is_complete(*args, **kwargs)

Overloaded function.

word_graph.is_complete(wg: WordGraph) → bool

Check if every node has exactly WordGraph.out_degree out-edges.

This function returns True if the word graph wg is complete, meaning that every node is the source of an edge with every possible label.

Parameters:: wg (WordGraph) – the word graph.
Returns:: Whether or not the word graph is complete.
Return type:: bool
Complexity:: \(O(mn)\) where m is WordGraph.number_of_nodes and n is WordGraph.out_degree.

word_graph.is_complete(wg: WordGraph, first_node: int, last_node: int) → bool

Check if every node in a range has exactly WordGraph.out_degree out-edges.

This function returns True if every node in the range defined by first_node and last_node is complete, meaning that every such node is the source of an edge with every possible label.

Parameters:

wg (WordGraph) – the word graph.
first_node (int) – the first node.
last_node (int) – one more than the last node.

Returns:

Whether or not the word graph is complete on the given range of nodes.

Return type:

bool

Raises:

LibsemigroupsError – if any node in the range defined by first_node and last_node is not a node of wg.

Complexity:

\(O(mn)\) where m is the number of nodes in the range and n is WordGraph.out_degree.

word_graph.is_connected(wg: WordGraph) → bool

Check if a word graph is connected.

This function returns True if the word graph wg is connected and False if it is not. A word graph is connected if for every pair of nodes s and t in the graph there exists a sequence \(u_0 = s, \ldots, u_{n}= t\) for some \(n\in \mathbb{N}\) such that for every \(i\) there exists a label a such that \((u_i, a, u_{i + 1})\) or \((u_{i + 1}, a, u_i)\) is an edge in the graph.

Parameters:: wg (WordGraph) – the word graph.
Returns:: Whether or not the word graph is connected.
Return type:: bool
Raises:: LibsemigroupsError – if any target in wg is out of bounds, i.e. if any target t is not equal to UNDEFINED and not in the nodes of wg.

word_graph.is_reachable(wg: WordGraph, source: int, target: int) → bool

Check if there is a path from one node to another.

This function returns True if there is a path from the node source to the node target in the word graph wg.

Parameters:

wg (WordGraph) – the WordGraph object to check.
source (int) – the source node.
target (int) – the source node.

Returns:

Whether or not the node target is reachable from the node source in the word graph wg.

Return type:

bool

Raises:

LibsemigroupsError – if source or target is out of bounds.
LibsemigroupsError – if any target in wg is out of bounds.

Complexity:

\(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph.out_degree.

word_graph.is_strictly_cyclic(wg: WordGraph) → bool

Check if every node is reachable from some node.

This function returns True if there exists a node in wg from which every other node is reachable; and False otherwise. A word graph is strictly cyclic if there exists a node \(v\) from which every node is reachable (including \(v\) ). There must be a path of length at least \(1\) from the original node \(v\) to itself (i.e. \(v\) is not considered to be reachable from itself by default).

Parameters:: wg (WordGraph) – the WordGraph object to check.
Returns:: Whether or not every node is reachable from one specific node.
Return type:: bool
Raises:: LibsemigroupsError – if any target in wg is out of bounds.
Complexity:: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph.out_degree.

>>> from libsemigroups_pybind11 import WordGraph, word_graph
>>> wg = WordGraph(5,  [[0,  0],  [1,  1],  [2],  [3,  3]])
>>> word_graph.is_strictly_cyclic(wg)
False

word_graph.last_node_on_path(wg: WordGraph, source: int, w: list[int]) → tuple[int, int]

Returns the last node on the path labelled by a word and the index of the position in the word reached.

Parameters:

wg (WordGraph) – a word graph.
source (int) – the source node.
w (list[int]) – the word.

Returns:

A pair consisting of the last node reached and the index of the last letter in the word labelling an edge.

Return type:

tuple[int, int]

Complexity:

At worst the length of w.

word_graph.nodes_reachable_from(wg: WordGraph, source: int) → set[int]

Returns the set of nodes reachable from a given node in a word graph.

This function returns a set consisting of all the nodes in the word graph wg that are reachable from source.

Parameters:

wg (WordGraph) – the word graph.
source (int) – the source node.

Returns:

A set consisting of all the nodes in the word graph wg that are reachable from source.

Return type:

set[int]

Raises:

LibsemigroupsError – if source is out of bounds (greater than or equal to WordGraph.number_of_nodes).

word_graph.number_of_nodes_reachable_from(wg: WordGraph, source: int) → int

Returns the number of nodes reachable from a given node in a word graph.

This function returns the number of nodes in the word graph wg that are reachable from source.

Parameters:

wg (WordGraph) – the word graph.
source (int) – the source node.

Returns:

The number of nodes in the word graph wg that are reachable from source.

Return type:

int

Raises:

LibsemigroupsError – if source is out of bounds (greater than or equal to WordGraph.number_of_nodes).

word_graph.random_acyclic(number_of_nodes: int, out_degree: int) → WordGraph

Construct a random acyclic word graph from number of nodes and out-degree.

This function constructs a random acyclic word graph with number_of_nodes nodes and out-degree out_degree. This function implements the Markov chain algorithm given in [CDF11].

Parameters:

number_of_nodes (int) – the number of nodes.
out_degree (int) – the out-degree of every node.

Returns:

A random acyclic word graph.

Return type:

WordGraph

Raises:

LibsemigroupsError – if number_of_nodes is less than 2
LibsemigroupsError – if out_degree is less than 2

Complexity:

At least \(O(mn)\) where m is the number of nodes, and n is the out-degree of the word graph.

word_graph.spanning_tree(*args, **kwargs)

Overloaded function.

word_graph.spanning_tree(wg: WordGraph, root: int) → Forest

Returns a Forest containing a spanning tree of the nodes reachable from a given node in a word graph.

This function returns a Forest containing a spanning tree of the nodes reachable from root in the word graph wg.

Parameters:

wg (WordGraph) – the word graph.
root (int) – the source node.

Returns:

A Forest object containing a spanning tree.

Return type:

Forest

Raises:

LibsemigroupsError – if root is out of bounds, i.e. greater than or equal to WordGraph.number_of_nodes.

word_graph.spanning_tree(wg: WordGraph, root: int, f: Forest) → None

Replace the contents of a Forest by a spanning tree of the nodes reachable from a given node in a word graph.

This function replaces the content of the Forest f with a spanning tree of the nodes reachable from root in the word graph wg.

Parameters:

wg (WordGraph) – the word graph.
root (int) – the source node.
f (Forest) – the Forest object to hold the result.

Raises:

LibsemigroupsError – if root is out of bounds, i.e. greater than or equal to WordGraph.number_of_nodes.

word_graph.standardize(*args, **kwargs)

Overloaded function.

word_graph.standardize(wg: WordGraph, f: Forest, val: Order) → bool

Standardizes a word graph in-place.

This function standardizes the word graph wg according to the reduction order specified by val, and replaces the contents of the Forest f with a spanning tree rooted at 0 for the node reachable from 0. The spanning tree corresponds to the order val.

Parameters:

wg (WordGraph) – the word graph.
f (Forest) – the Forest object to store the spanning tree.
val (Order) – the order to use for standardization.

Returns:

This function returns True if the word graph wg is modified by this function (i.e. it was not standardized already), and False otherwise.

Return type:

bool

word_graph.standardize(wg: WordGraph, val: Order = Order.shortlex) → tuple[bool, Forest]

Standardizes a word graph in-place.

This function standardizes the word graph wg according to the reduction order specified by val, and returns a Forest object containing a spanning tree rooted at 0 for the node reachable from 0. The spanning tree corresponds to the order val.

Parameters:

wg (WordGraph) – the word graph.
val (Order) – the order to use for standardization (default: Order.shortlex).

Returns:

A tuple whose first entry is True if the word graph wg is modified by this function (i.e. it was not standardized already), and False otherwise. The second entry is a Forest object containing a spanning tree for wg.

Return type:

tuple[bool, Forest]

word_graph.topological_sort(*args, **kwargs)

Overloaded function.

word_graph.topological_sort(wg: WordGraph) → list[int]

Returns the nodes of the word graph 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:: wg (WordGraph) – the word graph.
Returns:: A list of the nodes of wg in topological order (if possible) and is otherwise empty.
Return type:: list[int]
Complexity:: \(O(m + n)\) where \(m\) is the number of nodes in the WordGraph wg and \(n\) is the number of edges. Note that for WordGraph objects the number of edges is always at most \(mk\) where \(k\) is the WordGraph.out_degree.

word_graph.topological_sort(wg: WordGraph, source: int) → list[int]

Returns the nodes of the word graph 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:

wg (WordGraph) – the WordGraph object to check.
source (int) – the source node.

Returns:

A list of the nodes reachable from source in wg in topological order (if possible) and is otherwise empty.

Return type:

list[int]

Complexity:

At worst \(O(m + n)\) where \(m\) is the number of nodes in the subword graph of those nodes reachable from source and \(n\) is the number of edges.