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_nodes libsemigroups::ActionDigraph::cbegin_nodes() const noexcept

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

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

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_nodes libsemigroups::ActionDigraph::cend_nodes() const noexcept

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

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

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.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

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.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

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().

See

unsafe_next_neighbor.

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.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Complexity

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

Parameters

(None)

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.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

Returns

The number of nodes, a value of type T.

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

Returns the out-degree.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

Constant.

Parameters

(None)

Returns

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

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.

Exceptions

This function guarantees not to throw a LibsemigroupsException.

Warning

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

Parameters
  • v – the node

  • lbl – the label

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.

Complexity

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

Exceptions

This function guarantees not to throw a LibsemigroupsException.

See

next_neighbor.

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

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.

Exceptions

This function is noexcept and is guaranteed never to throw.

Complexity

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

Parameters

(None)

Returns

A bool.