template<typename VertexT, typename EdgeT = empty_t>
struct fennec::graph< VertexT, EdgeT >
| Property | Value |
| stable | ⛔ |
| dynamic | ✅ |
| homogenous | ✅ |
| distinct | ⛔ |
| ordered | ⛔ |
| space | \(O(N)\) |
| linear | ✅ |
| access | \(O(1)\) |
| find | \(O(1)\) |
| insertion | \(O(1)\) |
| deletion | \(O(N)\) |
Graphs contain vertices and edges. Graphs are either directed or undirected. This structure allows the creation of both directed and undirected edges. As far as what that means; a directed graph means that edges have direction, where there are edges that are "to" and "from," rather than "between" which is used in undirected graphs.
An undirected graph is connected if there is a path between every pair of vertices in the graph.
A directed graph is weakly connected if replacing all of its directed edges with undirected edges would produce a connected graph. We will call this "disjointed"
A directed graph is semi-connected if there is a directed path p for u → v or v → u for every pair of vertices u, v. We will call this "unilateral"
A directed graph is strongly-connected if there is a directed path p for u → v and v → u for every pair of vertices u, v. We will call this "connected"
- Template Parameters
-
| VertexT | The type associated with each vertex |
| EdgeT | The type associated with each edge |
|
|
|
constexpr | graph ()=default |
| | Default Constructor, initializes empty graph.
|
| |
|
constexpr | ~graph ()=default |
| | Destructor.
|
| |
|
| constexpr graph & | operator= (const graph &g)=default |
| | Copy Assignment Operator.
|
| |
| constexpr graph & | operator= (graph &&g)=default |
| | Move Assignment Operator.
|
| |
|
| constexpr size_t | num_vertices () const |
| |
| constexpr size_t | num_edges () const |
| |
| constexpr size_t | capacity () const |
| |
| constexpr bool | empty () const |
| |
| constexpr bool | exists (size_t a, size_t b) const |
| | Checks if there exists an edge e that starts from a and ends at b
|
| |
| constexpr bool | is_symmetric (size_t a, size_t b) const |
| | Checks if there exists an edge e0 that starts from a and ends at b and e1 that starts from b and ends at a
|
| |
| constexpr bool | is_undirected (size_t a, size_t b) const |
| | Checks if there exists an edge e between a and b
|
| |
|
| constexpr vertex_t & | operator[] (size_t vertex) |
| | vertex Access Operator
|
| |
| constexpr const vertex_t & | operator[] (size_t vertex) const |
| | vertex Const Access Operator
|
| |
| constexpr edge_t * | operator[] (size_t a, size_t b) |
| | edge Access Operator
|
| |
| constexpr const edge_t * | operator[] (size_t a, size_t b) const |
| | edge Const Access Operator
|
| |
| list< size_t > | outgoing (size_t vertex) |
| | Getter for a list of vertices x that vertex has an edge to x...
|
| |
| list< size_t > | incoming (size_t vertex) |
| | Getter for a list of vertices x that vertex has an edge from x...
|
| |
| list< size_t > | symmetric (size_t vertex) |
| | Getter for a list of vertices x that vertex has an edge to and from x...
|
| |
| list< size_t > | undirected (size_t vertex) |
| | Getter for a list of vertices x that vertex has an edge to and from x... and share the same value.
|
| |
| const auto * | edges (size_t vertex) |
| | Getter for the internal storage of mapped edges from this vertex. Use this when you want to iterate over edges that start from this vertex.
|
| |
|
| constexpr size_t | insert (vertex_t &&vertex) |
| | Move a new vertex into the graph.
|
| |
| constexpr size_t | insert (const vertex_t &vertex) |
| | Copy a new vertex into the graph.
|
| |
| template<typename... ArgsT> |
| constexpr size_t | emplace (ArgsT &&...args) |
| | Construct a new vertex in the graph.
|
| |
| constexpr void | erase (size_t vertex) |
| | Erase a vertex from the graph.
|
| |
| template<typename... ArgsT> |
| constexpr void | make_edge (size_t a, size_t b, ArgsT &&...args) |
| | Form an edge from vertex a to vertex b
|
| |
| template<typename... ArgsT> |
| constexpr void | make_edge2 (size_t a, size_t b, ArgsT &&...args) |
| | Form an undirected edge between vertex a and vertex b
|
| |
| constexpr void | cut_edge (size_t a, size_t b) |
| | Disconnect an edge from vertex a to vertex b
|
| |
| constexpr void | cut_edge2 (size_t a, size_t b) |
| | Disconnect both directed edges between vertices a and b
|
| |
| void | cut (size_t n) |
| | Break all edges to and from n
|
| |
|
void | clear () |
| | Clear the graph, destructing all vertices and edges.
|
| |
1.9.8