Graph
Interface
template<Arithmetic T> requires Referenceable<T>
class Graph;
Constraints
The given can be a fundamental type
or an arbitrary type which adhere to the arithmetic and reference constraints.
template<typename T>
using Reference = T&;
template<typename T>
using ConstReference = T const&;
template<typename T>
concept Referenceable =
requires
{
typename Reference<T>;
typename ConstReference<T>;
};
template<typename T>
concept Integral = std::is_integral_v<T>;
template<typename T>
concept Floating = std::is_floating_point_v<T>;
template<typename T>
concept Arithmetic =
Integral<T>
|| Floating<T>
|| requires(T t)
{
{ t+t } -> std::same_as<T>;
{ t-t } -> std::same_as<T>;
{ t*t } -> std::same_as<T>;
{ t/t } -> std::same_as<T>;
};
Constructors
Creates an empty graph.
template<typename T>
Graph<T>::Graph() noexcept
Creates a copy of a source graph.
template<typename T>
Graph<T>::Graph(Graph const& src) noexcept
Moves the contents of a source graph, and invalidates its contents.
Graph(Graph&& src) noexcept;
Initializes a graph with a list of edges.
Graph(std::initializer_list<std::pair<T,T>> t) noexcept;
Public aliases
value_type
Returns the type of T.
using value_type = T;
reference
Returns a reference to T.
using reference = T&;
const_reference
Returns a constant reference to T.
using const_reference = T const&;
Methods
Element Access
Successors
template<typename T>
template<typename U> requires cp::ConvertibleTo<T,U>
std::vector<T> Graph<T>::successors(U u) const noexcept;
Given a graph \(G(V,E)\), returns all the outgoing directed edges of a vertex \(v\).
The successors of vertex 2 are depicted below.
graph TD; 1 --> 5; 1 --> 4; 2 --> 5; 2 --> 4; 4 --> 7; 5 --> 7; linkStyle 2,3 stroke:#33f,color:blue;
Predecessors
template<typename T>
template<typename U> requires cp::ConvertibleTo<T,U>
std::vector<T> Graph<T>::predecessors(U u) const noexcept;
Given a graph \(G(V,E)\), returns all the incomming directed edges of a vertex \(v\).
The predecessors of vertex 7 are depicted below.
graph TD; 1 --> 5; 1 --> 4; 2 --> 5; 2 --> 4; 3 --> 5; 3 --> 6; 4 --> 7; 5 --> 7; 6 --> 8; 7 --> 9; 8 --> 9; linkStyle 6,7 stroke:#33f,color:blue;
Adjacent
template<typename T>
template<typename U> requires cp::ConvertibleTo<T,U>
bool Graph<T>::adjacent(U&& u1, U&& u2) const noexcept;
A vertex \(v\) is adjacent to \(u\) if it there is an edge from \(v\) to \(u\),
this method returns whether two vertices are adjacent.
In the example below 7 and 9 are the adjacent.
graph TD; 1 --> 5; 1 --> 4; 2 --> 5; 2 --> 4; 3 --> 5; 3 --> 6; 4 --> 7; 5 --> 7; 6 --> 8; 7 --> 9; 8 --> 9; 9 --> 10; linkStyle 9 stroke:#33f,color:blue;
Neighbors
template<typename T>
template<typename U> requires cp::ConvertibleTo<T,U>
std::vector<T> Graph<T>::neighbors(U&& u) const noexcept;
Returns all the predecessors and successors of a vertex \(v\). In the example below, the result of a function call to vertex 5 is demonstrated.
graph TD; 1 --> 5; 1 --> 4; 2 --> 5; 2 --> 4; 3 --> 5; 3 --> 6; 4 --> 7; 5 --> 7; 6 --> 8; 7 --> 9; 8 --> 9; 9 --> 10; linkStyle 0,2,4,7 stroke:#33f,color:blue;
Data
Vertices<T>& data() noexcept;
Returns the underlying data structure.
Capacity
Vertices Count
std::size_t vertices_count() const noexcept;
Returns the number of vertices of the graph.
Edges Count
std::size_t edges_count() const noexcept;
Returns the number of edges of the graph.
Modifiers
Emplace
template<typename T>
template<typename... U> requires cp::IsPairsOf<T,U...>
void Graph<T>::emplace(U&&... u) noexcept;
Inserts a number of edges \(uv\) in a graph \(G\). This method takes a variable number of arguments, those which are pairs of the base type, consider the graph:
graph TD; 1 --> 4; 2 --> 5; 2 --> 4; 3 --> 5;
A call to emplace((1,5),(4,7),(5,7)), yields a novel vertex 7, adjacent to 4 and 5,
and makes vertex 1 adjacent to 5.
graph TD; 1 --> 5; 1 --> 4; 2 --> 5; 2 --> 4; 3 --> 5; 4 --> 7; 5 --> 7; linkStyle 0,5,6 stroke:#33f,color:blue;
Erase
template<typename T>
template<typename U> requires cp::IsPairOf<T,U>
void Graph<T>::erase(U&& u) noexcept;
Removes edges from a graph \(G\) and orphan vertices, consider the graph below:
graph TD; 1 --> 4; 2 --> 5; 2 --> 4; 3 --> 5;
A call to erase(3,5) removes the edge 3->5, and removes vertex 3 since it is not adjacent
to any other vertex.
graph TD; 1 --> 4; 2 --> 5; 2 --> 4;
Operators
Operator=
Assigment copy operator, replaces the graph in the lhs with the contents of the rhs.
template<cp::Arithmetic T>
Graph<T> Graph<T>::operator=(Graph<T> const& rhs)
Example:
g1 = g2;
Assigment move operator, moves the graph from the rhs to the lhs.
template<cp::Arithmetic T>
Graph<T> Graph<T>::operator=(Graph<T>&& rhs)
Example:
g1 = std::move(g2);
Reader
This is a file reader module for the graph data structure.
Reader class
The class has the following interface:
template<Callback T>
class Reader : private lorina::verilog_reader;
Where Callback has to adhere to the following constraints:
template<typename T>
concept Callback =
requires(T t)
{
{ t(std::make_pair(int32_t{},int32_t{}) ) } -> std::same_as<std::void_t<>>;
};
The callback is a callable which receives an edge as input, and performs an insertion operation on
the graph.
Constructors
template<typename Str>
requires cp::ConvertibleTo<Str,std::string>
Reader(Str&& input, T callback);
Formats
The currently supported formats are:
- Verilog