The WordGraph class

Class for representing word graphs.

Instances of this class represent word graphs. If the word graph has n nodes, they are represented by the numbers \(\{0, ..., n - 1\}\), and every node has the same number m of out-edges (edges with source that node and target any other node or UNDEFINED). The number m is referred to as the out-degree of the word graph, or any of its nodes.

Contents

`WordGraph`	Class for representing word graphs.
`WordGraph.add_nodes`(…)	Add a number of new nodes.
`WordGraph.add_to_out_degree`(…)	Add to the out-degree of every node.
`WordGraph.copy`(…)	Copy a `WordGraph` object.
`WordGraph.disjoint_union_inplace`(…)	Unites a word graph in-place.
`WordGraph.induced_subgraph`(…)	Modify in-place to contain the subgraph induced by a range of nodes.
`WordGraph.init`(…)	Re-initialize the word graph to have m nodes and out-degree n.
`WordGraph.labels_and_targets`(…)	Returns an iterator yielding pairs consisting of edge labels and target nodes.
`WordGraph.next_label_and_target`(…)	Get the next target of an edge incident to a given node that doesn't equal `UNDEFINED`.
`WordGraph.nodes`(…)	Returns an iterator yielding the nodes of the word graph.
`WordGraph.number_of_edges`(…)	Overloaded function.
`WordGraph.number_of_nodes`(…)	Returns the number of nodes.
`WordGraph.out_degree`(…)	Returns the out-degree.
`WordGraph.random`(…)	Construct a random word graph from number of nodes and out-degree.
`WordGraph.remove_all_targets`(…)	Remove all of the edges in the word graph.
`WordGraph.remove_label`(…)	Removes a given label from the word graph.
`WordGraph.remove_target`(…)	Remove an edge from a node with a given label.
`WordGraph.reserve`(…)	Ensures that the word graph has capacity for a given number of nodes, and out-degree.
`WordGraph.swap_targets`(…)	Swaps the edge with specified label from one node with another.
`WordGraph.target`(…)	Overloaded function.
`WordGraph.targets`(…)	Returns an iterator yielding the targets of the edges incident to a given node.

Full API

class WordGraph

__init__(*args, **kwargs)

Overloaded function.

__init__(self: WordGraph, m: int = 0, n: int = 0) → None

Construct from number of nodes and out degree.

This function constructs a word graph with m nodes and where the maximum out-degree of any node is n. There are no edges in the defined word graph.

Parameters:

m (int) – the number of nodes in the word graph (default: 0).
n (int) – the out-degree of every node (default: 0).

Complexity:

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

__init__(self: WordGraph, num_nodes: int, targets: list[list[int | Undefined | PositiveInfinity | LimitMax]]) → None

Construct a word graph from a number of nodes and an list of targets.

This function constructs a word graph from its arguments whose out-degree is specified by the length of the first item in targets.

Parameters:

num_nodes (int) – the number of nodes in the word graph.
targets (list[list[int | Undefined | PositiveInfinity | LimitMax]]) – list of the targets.

Raises:

LibsemigroupsError – if any target is specified in targets is greater than or equal to num_nodes.

>>> from libsemigroups_pybind11 import WordGraph
>>> WordGraph(5, [[0, 0], [1, 1], [2], [3, 3]])
<WordGraph with 5 nodes, 7 edges, & out-degree 2>

add_nodes(self: WordGraph, nr: int) → WordGraph

Add a number of new nodes.

This function modifies a word graph in-place so that it has nr new nodes added.

Parameters:: nr (int) – the number of nodes to add.
Returns:: self.
Return type:: WordGraph
Complexity:: Linear in (number_of_nodes() + nr) * out_degree().

add_to_out_degree(self: WordGraph, nr: int) → WordGraph

Add to the out-degree of every node.

This function modifies a word graph in-place so that the out-degree is increased by nr.

Parameters:: nr (int) – the number of new out-edges for every node.
Returns:: self.
Return type:: WordGraph
Complexity:: \(O(mn)\) where m is the number of nodes, and n is the new out degree of the word graph.

copy(self: WordGraph) → WordGraph

Copy a WordGraph object.

Returns:: A copy.
Return type:: WordGraph

disjoint_union_inplace(self: WordGraph, that: WordGraph) → WordGraph

Unites a word graph in-place.

This function changes a WordGraph object in-place to contain the disjoint union of itself and that. The node n of that is mapped to number_of_nodes() + n.

Parameters:: that (WordGraph) – the word graph to unite.
Returns:: self.
Return type:: WordGraph
Raises:: LibsemigroupsError – if self and that do not have the same out-degree.

induced_subgraph(self: WordGraph, first: int, last: int) → WordGraph

Modify in-place to contain the subgraph induced by a range of nodes.

This function modifies a WordGraph object in-place to contain its subgraph induced by the range of nodes first to last.

Parameters:

first (int) – the first node.
last (int) – one more than the last node.

Returns:

self.

Return type:

WordGraph

Raises:

LibsemigroupsError – if first or last is out of range.
LibsemigroupsError – if any edge with source in the range first to last has target outside the range first to last.

init(self: WordGraph, m: int, n: int) → WordGraph

Re-initialize the word graph to have m nodes and out-degree n.

This function puts a word graph into the state that it would have been in if it had just been newly constructed with the same parameters m and n.

Parameters:

m (int) – the number of nodes in the word graph.
n (int) – the out-degree of every node.

Returns:

self.

Return type:

WordGraph

Complexity:

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

labels_and_targets(self: WordGraph, source: int) → collections.abc.Iterator[tuple[int, int | Undefined]]

Returns an iterator yielding pairs consisting of edge labels and target nodes.

This function returns an iterator yielding all the edge labels and targets of edges with source source.

Parameters:: source (int) – the source node.
Returns:: An iterator.
Return type:: collections.abc.Iterator[tuple[int, int | Undefined]]
Raises:: LibsemigroupsError – if source is out of bounds.

next_label_and_target(self: WordGraph, s: int, a: int) → tuple[int | Undefined, int | Undefined]

Get the next target of an edge incident to a given node that doesn’t equal UNDEFINED.

This function returns the next target of an edge with label greater than or equal to a that is incident to the node s. If target(s, b) equals UNDEFINED for every value b in the range \([a, n)\), where \(n\) is the return value of out_degree(), then x.first and x.second equal UNDEFINED.

Parameters:

s (int) – the node.
a (int) – the label (default: 0).

Returns:

Returns a pair where the first entry is the next label after a and the second is the next target of s that is not UNDEFINED.

Return type:

tuple[int | Undefined, int | Undefined]

Raises:

LibsemigroupsError – if s does not represent a node in self.

Complexity:

At worst \(O(n)\) where \(n\) equals out_degree().

nodes(self: WordGraph) → collections.abc.Iterator[int]

Returns an iterator yielding the nodes of the word graph.

This function returns an iterator yielding the nodes of the word graph.

Returns:: An iterator yielding the nodes.
Return type:: collections.abc.Iterator[int]
Complexity:: Constant.

number_of_edges(self: WordGraph, s: int) → int

Overloaded function.

number_of_edges(self: WordGraph) → int

Returns the number of edges. This function returns the total number of edges (i.e. values s and a such that target(s, a) is not UNDEFINED) in the word graph.

Returns:: The total number of edges.
Return type:: int
Complexity:: \(O(mn)\) where m is number_of_nodes() and n is out_degree().

number_of_edges(self: WordGraph, s: int) → int

Returns the number of edges with given source node.

This function returns the number of edges incident to the given source node s.

Parameters:: s (int) – the node.
Returns:: The number of edge incident to s.
Return type:: int
Raises:: LibsemigroupsError – if s is not a node.
Complexity:: \(O(n)\) where n is out_degree().

number_of_nodes(self: WordGraph) → int

Returns the number of nodes. This function returns the number of nodes in the word graph.

Returns:: The number of nodes in the word graph.
Return type:: int
Complexity:: Constant.

out_degree(self: WordGraph) → int

Returns the out-degree. This function returns the number of edge labels in the word graph.

Returns:: The number of edge labels.
Return type:: int
Complexity:: Constant.

static random(number_of_nodes: int, out_degree: int) → WordGraph

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

This function constructs a random word graph with number_of_nodes nodes and out-degree out_degree.

Parameters:

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

Returns:

A random word graph.

Return type:

WordGraph

Raises:

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

Complexity:

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

remove_all_targets(self: WordGraph) → WordGraph

Remove all of the edges in the word graph. Set every target of every source with every possible label to UNDEFINED.

Returns:: self.
Return type:: WordGraph
Complexity:: \(O(mn)\) where m is the number of nodes and n is the out-degree.

remove_label(self: WordGraph, a: int) → WordGraph

Removes a given label from the word graph.

This function removes the label a from a WordGraph object in-place. This reduces the out-degree by 1.

Parameters:: a (int) – the label to remove.
Returns:: self.
Return type:: WordGraph
Raises:: LibsemigroupsError – if a is out of range.

remove_target(self: WordGraph, s: int, a: int) → WordGraph

Remove an edge from a node with a given label.

This function removes the edge with source node s labelled by a.

Parameters:

s (int) – the source node.
a (int) – the label of the edge from s.

Returns:

self.

Return type:

WordGraph

Raises:

LibsemigroupsError – if s or a is out of range.

Complexity:

Constant.

reserve(self: WordGraph, m: int, n: int) → WordGraph

Ensures that the word graph has capacity for a given number of nodes, and out-degree.

This function ensures that the word graph has capacity for m nodes and n labels.

Parameters:

m (int) – the number of nodes.
n (int) – the out-degree.

Returns:

self.

Return type:

WordGraph

Complexity:

\(O(mn)\) where m is the number of nodes and n is the out-degree.

swap_targets(self: WordGraph, m: int, n: int, a: int) → WordGraph

Swaps the edge with specified label from one node with another.

This function swaps the target of the edge from the node m labelled a with the target of the edge from the node n labelled a.

Parameters:

m (int) – the first node.
n (int) – the second node.
a (int) – the label.

Returns:

self.

Return type:

WordGraph

Raises:

LibsemigroupsError – if any of m, n, and a is out of range.

Complexity:

Constant

target(*args, **kwargs)

Overloaded function.

target(self: WordGraph, s: int, a: int, t: int) → WordGraph

Add an edge from one node to another with a given label.

If s and t are nodes in self, and a is in the range [0, out_degree()), then this function adds an edge from a to b labelled a.

Parameters:

s (int) – the source node.
a (int) – the label of the edge.
t (int) – the range node.

Returns:

self.

Return type:

WordGraph

Raises:

LibsemigroupsError – if s, a, or t is not valid.

Complexity:

Constant.

target(self: WordGraph, source: int, a: int) → int

Get the target of the edge with given source node and label.

This function returns the target of the edge with source node source and label a.

Parameters:

source (int) – the node.
a (int) – the label.

Returns:

Returns the node adjacent to source via the edge labelled a, or UNDEFINED.

Return type:

int

Raises:

LibsemigroupsError – if source or a is not valid.

Complexity:

Constant.

targets(self: WordGraph, source: int) → collections.abc.Iterator[int | Undefined]

Returns an iterator yielding the targets of the edges incident to a given node.

This function returns an iterator yielding the targets of the edges incident to the source node source. This target might equal UNDEFINED.

Parameters:: source (int) – the source node in the word graph.
Returns:: An iterator yielding the targets.
Return type:: collections.abc.Iterator[int | Undefined]
Raises:: LibsemigroupsError – if source is out of range (i.e. greater than or equal to number_of_nodes).
Complexity:: Constant.