Nodes, edges, neighbors

This page contains information about accessing the nodes, edges, and neighbours of the ActionDigraph class.

inline const_iterator_edges libsemigroups::ActionDigraph::cbegin_edges(node_type i) const

Returns a random access iterator pointing at the first neighbor of a node.

Complexity

Constant.

Parameters

i – a node in the digraph.

Throws

LibsemigroupsException – if i is not valid.

Returns

A const_iterator_edges.

inline const_iterator_edges libsemigroups::ActionDigraph::cbegin_edges_nc(node_type i) const noexcept

Returns a random access iterator pointing at the first neighbor of a node.

See also

cbegin_edges.

Complexity

Constant.

Warning

No checks whatsoever on the validity of the arguments are performed.

Parameters

i – a node in the digraph.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A const_iterator_edges.

inline const_iterator_nodes libsemigroups::ActionDigraph::cbegin_nodes() const noexcept

Returns a random access iterator pointing at the first node of the digraph.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

An const_iterator_nodes.

inline const_iterator_edges libsemigroups::ActionDigraph::cend_edges(node_type i) const

Returns a random access iterator pointing one-past-the-last neighbor of a node.

Complexity

Constant.

Parameters

i – a node in the digraph.

Throws

LibsemigroupsException – if i is not valid.

Returns

A const_iterator_edges.

inline const_iterator_edges libsemigroups::ActionDigraph::cend_edges_nc(node_type i) const noexcept

Returns a random access iterator pointing one-past-the-last neighbor of a node.

See also

cend_edges.

Complexity

Constant.

Warning

No checks whatsoever on the validity of the arguments are performed.

Parameters

i – a node in the digraph.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A const_iterator_edges.

inline const_iterator_nodes libsemigroups::ActionDigraph::cend_nodes() const noexcept

Returns a random access iterator pointing one-past-the-last node of the digraph.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

An const_iterator_nodes.

inline const_reverse_iterator_nodes libsemigroups::ActionDigraph::crbegin_nodes() const noexcept

Returns a random access iterator pointing at the last node of the digraph.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

An const_reverse_iterator_nodes.

inline const_reverse_iterator_nodes libsemigroups::ActionDigraph::crend_nodes() const noexcept

Returns a random access iterator pointing one-past-the-first node of the digraph.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

An const_reverse_iterator_nodes.

inline node_type libsemigroups::ActionDigraph::neighbor(node_type v, label_type lbl) const

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

Complexity

Constant.

Parameters
  • v – the node

  • lbl – the label

Throws

LibsemigroupsException – if v or lbl is not valid.

Returns

Returns the node adjacent to v via the edge labelled lbl, or libsemigroups::UNDEFINED; both are values of type node_type.

inline std::pair<node_type, label_type> libsemigroups::ActionDigraph::next_neighbor(node_type v, label_type i) const

Get the next neighbor of a node that doesn’t equal libsemigroups::UNDEFINED.

If neighbor(v, i) equals libsemigroups::UNDEFINED for every value in the range \([i, n)\), where \(n\) is the return value of out_degree() then x.first and x.second equal libsemigroups::UNDEFINED.

Complexity

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

Parameters
  • v – the node

  • i – the label

Throws

LibsemigroupsException – if v does not represent a node in this.

Returns

Returns a std::pair x where:

  1. x.first is adjacent to v via an edge labelled x.second;

  2. x.second is the minimum value in the range \([i, n)\) such that neighbor(v, x.second) is not equal to libsemigroups::UNDEFINED where \(n\) is the return value of out_degree(); and

inline size_t libsemigroups::ActionDigraph::number_of_edges() const

Returns the number of edges.

Complexity

\(O(mn)\) where m is number_of_nodes() and n is out_degree().

Parameters

(None)

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

The total number of edges, a value of type size_t.

inline size_t libsemigroups::ActionDigraph::number_of_edges(node_type n) const

Returns the number of edges with given source node.

Complexity

\(O(n)\) where n is out_degree().

Parameters

n – the node.

Throws

LibsemigroupsException – if n is not a node.

Returns

A value of type size_t.

inline T libsemigroups::ActionDigraph::number_of_nodes() const noexcept

Returns the number of nodes.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The number of nodes, a value of type T.

inline T libsemigroups::ActionDigraph::out_degree() const noexcept

Returns the out-degree.

Complexity

Constant.

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

The number of out-edges of every node, a value of type T.

inline void libsemigroups::ActionDigraph::remove_all_edges()

Remove all of the edges in the digraph.

Complexity

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

Parameters

(None)

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

(None)

inline detail::DynamicArray2<T> const &libsemigroups::ActionDigraph::table() const noexcept

Returns a const reference to the underlying array.

This function returns a const reference to the underlying container for the edges of a digraph.

Parameters (None)

Complexity

Constant.

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A const reference to a detail::DynamicArray2<node_type>.

inline node_type libsemigroups::ActionDigraph::unsafe_neighbor(node_type v, label_type lbl) const

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

Complexity

Constant.

Warning

This function is unsafe because it does not verify v or lbl is valid.

Parameters
  • v – the node

  • lbl – the label

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

Returns the node adjacent to v via the edge labelled lbl, or libsemigroups::UNDEFINED; both are values of type node_type.

inline std::pair<node_type, label_type> libsemigroups::ActionDigraph::unsafe_next_neighbor(node_type v, label_type i) const

Get the next neighbor of a node that doesn’t equal libsemigroups::UNDEFINED.

If neighbor(v, i) equals libsemigroups::UNDEFINED for every value in the range \([i, n)\), where \(n\) is the return value of out_degree() then x.first and x.second equal libsemigroups::UNDEFINED.

See also

next_neighbor.

Complexity

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

Warning

This function is unsafe because it is not verified that the parameter v represents a node of this.

Parameters
  • v – the node

  • i – the label

Throws

(None) – This function guarantees not to throw a LibsemigroupsException.

Returns

Returns a std::pair x where:

  1. x.first is adjacent to v via an edge labelled x.second;

  2. x.second is the minimum value in the range \([i, n)\) such that neighbor(v, x.second) is not equal to libsemigroups::UNDEFINED where \(n\) is the return value of out_degree(); and

inline bool libsemigroups::ActionDigraph::validate() const noexcept

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

Complexity

\(O(mn)\) where m is number_of_nodes() and n is out_degree().

Parameters

(None)

Throws

(None) – This function is noexcept and is guaranteed never to throw.

Returns

A bool.