Free tree graph class. More...
#include <free_tree.hpp>
Public Member Functions | |
| free_tree () noexcept | |
| Empty constructor. | |
| free_tree (uint64_t n) noexcept | |
| Constructor with number of vertices. More... | |
| free_tree (const free_tree &t) noexcept | |
| Copy constructor. More... | |
| free_tree (free_tree &&t) noexcept | |
| Move constructor. More... | |
| free_tree (const undirected_graph &t) noexcept | |
| Copy constructor with undirected graph. More... | |
| free_tree (undirected_graph &&t) noexcept | |
| Move constructor with undirected graph. More... | |
| virtual | ~free_tree () noexcept |
| Destructor. | |
| free_tree & | operator= (const free_tree &f) noexcept |
| Copy assignment operator. More... | |
| free_tree & | operator= (free_tree &&f) noexcept |
| Copy assignment operator. More... | |
| virtual free_tree & | remove_node (node u, bool norm=true, bool check_norm=true) noexcept |
| Remove a node from this graph. More... | |
| free_tree & | add_edge (node s, node t, bool norm=true, bool check_norm=true) noexcept |
| Adds an edge to the tree. More... | |
| free_tree & | add_edge_bulk (node s, node t) noexcept |
| Adds an edge to the graph. More... | |
| void | finish_bulk_add (bool norm=true, bool check=true) noexcept |
| Finishes adding edges in bulk. More... | |
| free_tree & | add_edges (const std::vector< edge > &edges, bool norm=true, bool check_norm=true) noexcept |
| Adds a list of edges to the graph. More... | |
| free_tree & | set_edges (const std::vector< edge > &edges, bool norm=true, bool check_norm=true) noexcept |
| Sets the edges to the graph. More... | |
| free_tree & | remove_edge (node s, node t, bool norm=false, bool check_norm=true) noexcept |
| Remove an edge from this graph. More... | |
| free_tree & | remove_edges (const std::vector< edge > &edges, bool norm=true, bool check_norm=true) noexcept |
| Remove an edge from this graph. More... | |
| virtual free_tree & | remove_edges_incident_to (node u, bool norm=true, bool check_norm=true) noexcept |
| Remove all edges incident to a given vertex. More... | |
| void | disjoint_union (const free_tree &t) noexcept |
| Disjoint union of trees. More... | |
| void | calculate_tree_type () noexcept |
| Calculates the type of tree. More... | |
| bool | is_rooted () const noexcept |
| Returns whether this tree is a rooted tree. | |
| head_vector | get_head_vector (node r=0, const linear_arrangement &arr={}) const noexcept |
| Converts a free tree into a head vector. More... | |
| std::vector< edge_pair > | get_Q () const noexcept |
| Returns all independent pairs of edges of this graph. More... | |
| std::vector< edge > | get_edges () const noexcept |
| Returns all edges of this graph. | |
| const neighbourhood & | get_neighbours (node u) const noexcept |
| Returns the neighbourhood of node u. More... | |
| uint64_t | get_degree (node u) const noexcept |
| Returns the number of neighbours of u. More... | |
| bool | has_edge (node u, node v) const noexcept |
| Returns true if the edge \(\{u,v\}\) exists in the graph. | |
| bool | is_directed () const noexcept |
| Returns whether this graph is directed or not. | |
| bool | is_undirected () const noexcept |
| Returns whether this graph is undirected or not. | |
| virtual void | init (uint64_t n) noexcept |
| Allocates the necessary memory for this class. More... | |
| virtual void | clear () noexcept |
| Frees the memory occupied by this graph. More... | |
| virtual void | normalise () noexcept |
| Normalises the graph. More... | |
| virtual bool | check_normalised () noexcept |
| Checks if the graph is normalised. More... | |
| void | set_normalised (bool v=true) noexcept |
| Sets whether this graph is normalised or not. | |
| bool | has_node (node u) const noexcept |
| Returns true if node u is in this graph. | |
| uint64_t | get_num_nodes () const noexcept |
| Returns the number of ndoes. | |
| uint64_t | get_num_edges () const noexcept |
| Returns the number of edges. | |
| bool | is_normalised () const noexcept |
| Returns whether this graph is normalised or not. More... | |
| bool | is_tree () const noexcept |
| Is this graph is an actual tree? More... | |
| virtual bool | can_add_edge (node s, node t) const noexcept |
| Can this edge be added? More... | |
| virtual bool | can_add_edges (const std::vector< edge > &edges) const noexcept |
| Can these edges be added? More... | |
| uint64_t | get_component_representative (node u) const noexcept |
| Representative node of the connected component in which u belongs. More... | |
| bool | are_nodes_in_same_component (node u, node v) const noexcept |
| Checks if two nodes are in the same connected component. More... | |
| uint64_t | get_num_nodes_component (node u) const noexcept |
| Amount of nodes in a connected component of the tree. More... | |
| bool | is_of_tree_type (const tree_type &tt) const noexcept |
| Returns whether this tree is of type tt. More... | |
| bool | is_tree_type_valid () const noexcept |
| Is the type of this tree valid? More... | |
| std::vector< std::string > | get_tree_type_list () const noexcept |
| Returns the list of types as a list of strings. More... | |
Protected Member Functions | |
| virtual void | _init (uint64_t n) noexcept |
| Initialises memory of free_tree, undirected_graph and graph classes. | |
| virtual void | _clear () noexcept |
| void | update_union_find_after_edge_add (node u, node v, uint64_t *const root_of, uint64_t *const root_size) noexcept |
| Update the union find data structure after an edge addition. More... | |
| void | update_union_find_after_edge_add (node u, node v, uint64_t *const root_of, uint64_t *const root_size) const noexcept |
| Update the union find data structure after an edge addition. More... | |
| void | update_union_find_after_edge_remove (node u, node v, uint64_t *const root_of, uint64_t *const root_size) noexcept |
| Update the union find data structure after an edge removal. More... | |
| void | update_union_find_after_edge_remove (node u, node v, uint64_t *const root_of, uint64_t *const root_size) const noexcept |
| Update the union find data structure after an edge removal. More... | |
| void | update_union_find_before_incident_edges_removed (node u, uint64_t *const root_of, uint64_t *const root_size) noexcept |
| Update the union find data structure before the removal of all edges incident to a node. More... | |
| void | update_union_find_before_incident_edges_removed (node u, uint64_t *const root_of, uint64_t *const root_size) const noexcept |
| Update the union find data structure before the removal of all edges incident to a node. More... | |
| void | copy_full_free_tree (const free_tree &f) noexcept |
| Copies all members of this class and the parent class. | |
| void | move_full_free_tree (free_tree &&f) noexcept |
| Moves all members of this class and the parent class. | |
| void | copy_full_undirected_graph (const undirected_graph &u) noexcept |
| Copies all members of this class and the parent class. | |
| void | move_full_undirected_graph (undirected_graph &&u) noexcept |
| Moves all members of this class and the parent class. | |
| void | copy_full_graph (const graph &g) noexcept |
| Copies all members of this class. | |
| void | move_full_graph (graph &&g) noexcept |
| Moves all members of this class. | |
| void | __disjoint_union (const graph &g) noexcept |
| Disjoint union of graphs. More... | |
| virtual void | actions_after_remove_node (node u) noexcept |
| Do some work before an node is removed. More... | |
| virtual void | actions_before_remove_edges_incident_to (node u) noexcept |
| Do some work before all edges incident to a node is removed. More... | |
| virtual void | actions_after_add_edge (node u, node v) noexcept |
| Do some extra work after an edge has been added. More... | |
| virtual void | actions_after_remove_edge (node u, node v) noexcept |
| Do some extra work after an edge has been removed. More... | |
| void | normalise_after_edge_addition (bool norm, bool check) noexcept |
| Normalise the graph after one (or more) edges have been added. | |
| void | normalise_after_edge_removal (bool norm, bool check) noexcept |
| Normalise the graph after one (or more) edges have been removed. | |
| void | tree_only_init (uint64_t n) noexcept |
| Initialises only the memory of class tree. More... | |
| void | tree_only_clear () noexcept |
| Clears the memory used by only class tree. | |
| void | tree_only_copy (const tree &t) noexcept |
| Copies only members of class tree. | |
| void | tree_only_move (tree &&t) noexcept |
| Moves only members of class tree. | |
| void | actions_after_remove_node (node u) noexcept |
| Do some work before an node is removed. More... | |
| void | actions_after_add_edge (node u, node v) noexcept |
| Do some work after the addition of an edge. More... | |
| void | actions_after_remove_edge (node u, node v) noexcept |
| Do some work after the removal of an edge. More... | |
| void | actions_before_remove_edges_incident_to (node u) noexcept |
| Do some work before all edges incident to a node is removed. More... | |
| void | tree_only_set_edges () noexcept |
| Updates the data structures of a tree after the graph structure has had its set of edges set. More... | |
| void | tree_only_remove_node (node u) noexcept |
| Removes a vertex from the union-find data structure. More... | |
| void | fill_union_find () noexcept |
Protected Attributes | |
| std::vector< neighbourhood > | m_adjacency_list |
| Data structure that implements the graph. | |
| uint64_t | m_num_edges = 0 |
| Amount of edges of this graph. | |
| bool | m_normalised = true |
| Is this graph normalised? More... | |
| std::vector< node > | m_root_of |
| The root of every vertex in the union-find data structure. | |
| std::vector< uint64_t > | m_root_size |
| The size of the connected component that a root belongs to. More... | |
| std::array< bool, __tree_type_size > | m_tree_type |
| The type of this tree. | |
| bool | m_is_tree_type_valid = false |
| Is the type of this tree valid? More... | |
Private Member Functions | |
| void | disjoint_union (const undirected_graph &g) noexcept |
| Disjoint union of graphs. More... | |
| void | remove_single_edge (node u, node v, neighbourhood &out_u, neighbourhood &in_v) noexcept |
| Removes a single edge. More... | |
Detailed Description
Free tree graph class.
This class constrains the addition of edges so that the resulting graphs does not contain cycles. Furthermore, the edges added are undirected.
For another type of tree-like graphs, see rooted_tree.
Constructor & Destructor Documentation
◆ free_tree() [1/5]
|
inlinenoexcept |
Constructor with number of vertices.
- Parameters
-
n Number of vertices
◆ free_tree() [2/5]
|
inlinenoexcept |
Copy constructor.
- Parameters
-
t Free tree.
◆ free_tree() [3/5]
|
inlinenoexcept |
Move constructor.
- Parameters
-
t Free tree.
◆ free_tree() [4/5]
|
noexcept |
Copy constructor with undirected graph.
- Parameters
-
t An undirected graph.
- Precondition
- Graph t is a tree.
◆ free_tree() [5/5]
|
noexcept |
Move constructor with undirected graph.
- Parameters
-
t An undirected graph.
- Precondition
- Graph t is a tree.
Member Function Documentation
◆ __disjoint_union()
|
protectednoexceptinherited |
Disjoint union of graphs.
Given a graph, append it to the current graph.
All the nodes in g are relabelled starting at n, the number of nodes of the current graph.
- Parameters
-
g Input graph.
- Precondition
- This graph and g must be of the same type (both must be either undirected, or both directed).
- Postcondition
- The graph is normalised only if it was normalised before the call and g is also normalised.
◆ _clear()
|
inlineprotectedvirtualnoexcept |
Clears the memory of free_tree, undirected_graph and graph classes.
Reimplemented from lal::graphs::undirected_graph.
◆ actions_after_add_edge() [1/2]
|
protectedvirtualnoexceptinherited |
Do some extra work after an edge has been added.
- Parameters
-
u Node of the edge v Node of the edge
Reimplemented in lal::graphs::tree.
◆ actions_after_add_edge() [2/2]
Do some work after the addition of an edge.
- Parameters
-
u First node of the edge. v Second node of the edge.
- Postcondition
- The tree type is invalidated.
- Updated union-find.
Reimplemented from lal::graphs::graph.
◆ actions_after_remove_edge() [1/2]
|
protectedvirtualnoexceptinherited |
Do some extra work after an edge has been removed.
- Parameters
-
u Node of the edge v Node of the edge
Reimplemented in lal::graphs::tree.
◆ actions_after_remove_edge() [2/2]
|
protectedvirtualnoexceptinherited |
Do some work after the removal of an edge.
- Parameters
-
u First node of the edge. v Second node of the edge.
- Postcondition
- The tree type is invalidated.
- Updated union-find.
Reimplemented from lal::graphs::graph.
◆ actions_after_remove_node() [1/2]
|
protectedvirtualnoexceptinherited |
Do some work before an node is removed.
- Parameters
-
u Node to be removed.
Reimplemented in lal::graphs::tree.
◆ actions_after_remove_node() [2/2]
|
protectedvirtualnoexceptinherited |
Do some work before an node is removed.
- Parameters
-
u Node to be removed.
- Postcondition
- The tree type is invalidated.
- Updated union-find.
Reimplemented from lal::graphs::graph.
◆ actions_before_remove_edges_incident_to() [1/2]
|
protectedvirtualnoexceptinherited |
Do some work before all edges incident to a node is removed.
- Parameters
-
u Node whose incident edges are to be removed.
Reimplemented in lal::graphs::tree.
◆ actions_before_remove_edges_incident_to() [2/2]
|
protectedvirtualnoexceptinherited |
Do some work before all edges incident to a node is removed.
- Parameters
-
u Node whose incident edges are to be removed.
- Postcondition
- The tree type is invalidated.
- Updated union-find.
Reimplemented from lal::graphs::graph.
◆ add_edge()
|
virtualnoexcept |
Adds an edge to the tree.
This operation checks that the edge added does not produce cycles only in a debug compilation of the library. For a more controlled addition of the edges, see can_add_edge.
For developers: method lal::graphs::graph::actions_after_add_edge is called after the edge has been added.
- Parameters
-
s Valid node index: \(0 \le s < n\). t Valid node index: \(0 \le t < n\). norm Should the graph be normalised? check_norm If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.
- Precondition
- \(s \neq t\)
- Edge \(\{s,t\}\) is not part of the graph.
- Postcondition
- If norm is true the graph is guaranteed to be normalised after the addition of the edge.
Reimplemented from lal::graphs::undirected_graph.
◆ add_edge_bulk()
Adds an edge to the graph.
This method only adds an edge, and does no other work: normalisation is not checked, and no extra work per edge is done.
- Parameters
-
s Valid node index: \(0 \le s < n\). t Valid node index: \(0 \le t < n\).
- Precondition
- \(u \neq v\).
- The edge \(\{s,t\}\) is not part of the graph.
- Postcondition
- If norm is true the graph is guaranteed to be normalised after the addition of the edge.
◆ add_edges()
|
virtualnoexcept |
Adds a list of edges to the graph.
This function checks that edges will not produce cycles only in a debug compilation of the library. Moreover, this operation is faster than calling add_edge since the edges are added in bulk. For a more controlled addition of the edges, see can_add_edges.
For developers: method lal::graphs::graph::actions_after_add_edge is called after each edge has been added.
- Parameters
-
edges The edges to be added. norm Normalise the graph after the insertions. check_norm If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.
- Precondition
- All the edges in edges must meet the precondition of method add_edge.
- None of the subsets of the list of edges can produce cycles when added.
- Postcondition
- If norm is true the graph is guaranteed to be normalised after the addition of the edges.
Reimplemented from lal::graphs::undirected_graph.
◆ are_nodes_in_same_component()
|
inlinenoexceptinherited |
Checks if two nodes are in the same connected component.
- Parameters
-
u First node. v Second node.
- Returns
- True or false.
◆ calculate_tree_type()
|
virtualnoexcept |
Calculates the type of tree.
See tree_type for the list of different tree types.
Implements lal::graphs::tree.
◆ can_add_edge()
Can this edge be added?
In a tree, an edge can only be added if it does not produce cycles, and it has not been added before.
In a rooted tree, an edge can only be added if the in-degree of vertex t (see lal::graphs::directed_graph::get_in_degree) is exactly 1 after adding the edge.
- Parameters
-
s First node of the edge. t Second node of the edge.
- Returns
- Whether or not this edge can be added to the tree without producing cycles.
Reimplemented in lal::graphs::rooted_tree.
◆ can_add_edges()
|
virtualnoexceptinherited |
Can these edges be added?
In a tree, a set of edges can only be added if their addition to the tree do not produce cycles and none of them have been added before.
In a rooted tree, edges \((s,t)\) can only be added if the in-degree of vertex t (see lal::graphs::directed_graph::get_in_degree) is exactly 1 after adding the edge.
- Parameters
-
edges List of edges.
- Returns
- Whether or not these edges can be added to the tree without producing cycles.
Reimplemented in lal::graphs::rooted_tree.
◆ check_normalised()
|
virtualnoexceptinherited |
Checks if the graph is normalised.
Checks, whether the graph's adjacency structure is normalised or not. In case it is, attribute m_normalised is set to true, so method is_normalised evaluates to true.
Reimplemented in lal::graphs::directed_graph.
◆ clear()
|
virtualnoexceptinherited |
Frees the memory occupied by this graph.
See _clear for details.
- Postcondition
- The graph is normalised. The number of edges is 0.
◆ disjoint_union() [1/2]
|
noexcept |
Disjoint union of trees.
Given a free tree, append it to the current tree. If the current is empty (i.e., size 0), then the new tree is simply copied into the new one.
If the current tree is not empty, all the new nodes in t (appended to the current tree) are relabelled starting at n, the number of nodes of the current tree.
- Parameters
-
t Input tree.
- Postcondition
- If the current tree is empty, the whole state of the new tree is copied into the new one.
- If the current tree is not empty, then the resulting graph is not a tree since it lacks an edge. Then method is_tree() returns false.
- The type of tree (m_is_tree_type_valid) is invalidated.
◆ disjoint_union() [2/2]
|
privatenoexcept |
Disjoint union of graphs.
Given a graph, append it to the current graph.
All the nodes in g are relabelled starting at n, the number of nodes of the current graph.
- Parameters
-
g Input graph.
- Postcondition
- The graph is normalised only if it was normalised before the call and g is also normalised.
◆ fill_union_find()
|
inlineprotectednoexceptinherited |
Fills the Union-Find data structure assuming that the graph structure has all of its edges.
◆ finish_bulk_add()
|
virtualnoexcept |
Finishes adding edges in bulk.
- Parameters
-
norm Normalise the tree. check Check whether the tree is normalised or not.
- Precondition
- All edges of the have been added with method add_edge_bulk.
Implements lal::graphs::graph.
◆ get_component_representative()
|
inlinenoexceptinherited |
Representative node of the connected component in which u belongs.
If the current graph lacks some edges then it is clearly a forest, i.e., a series of disconnected components. This function returns a representative node of the connected component to which node u belongs.
Further, let \(cc(u)\) be the connected component of vertex u, and \(rep(cc(u))\) be the representative node of \(cc(u)\). For every other node \(v\in cc(u)\), this function will return the same representative node \(rep(cc(u))\). Therefore, \(rep(cc(u))=rep(cc(v))\) for every \(v\in cc(u)\).
- Parameters
-
u Input node.
- Returns
- The representative node of node u's component.
◆ get_degree()
|
inlinenoexceptinherited |
Returns the number of neighbours of u.
- Parameters
-
u Node to be queried.
- Returns
- The number of adjacent nodes.
◆ get_head_vector()
|
noexcept |
Converts a free tree into a head vector.
See Head vector page for a definition of 'head vector'.
- Parameters
-
r A fictional root to be used to calculate the head vector. arr Linear arrangement of the tree.
- Returns
- The head vector representation of this tree.
- Precondition
- This tree is a valid free tree (see is_tree).
◆ get_neighbours()
|
inlinenoexceptinherited |
Returns the neighbourhood of node u.
- Parameters
-
u Node.
- Returns
- The list of nodes adjacent to node u.
◆ get_num_nodes_component()
|
inlinenoexceptinherited |
Amount of nodes in a connected component of the tree.
If the current graph lacks some edges then it is clearly a forest, i.e., a series of disconnected components. This function returns the size of the component node u belongs to.
In rooted trees one has to see this amount as the number of nodes of the component in the underlying undirected forest.
- Parameters
-
u Input node.
- Returns
- The size of the connected component of u.
◆ get_Q()
|
virtualnoexceptinherited |
Returns all independent pairs of edges of this graph.
The set \(Q(G)\) is defined as the pairs of edges of \(G\), \(E(G) \times E(G)\), that are independent, that is, that share no nodes.
Implements lal::graphs::graph.
◆ get_tree_type_list()
|
noexceptinherited |
Returns the list of types as a list of strings.
- Returns
- The list of types as a list of strings.
◆ init()
|
virtualnoexceptinherited |
◆ is_normalised()
|
inlinenoexceptinherited |
Returns whether this graph is normalised or not.
A graph is normalised if every node's adjacency list is sorted increasingly. For this, use method normalise().
- Returns
- The value of m_normalised.
◆ is_of_tree_type()
|
inlinenoexceptinherited |
Returns whether this tree is of type tt.
See method calculate_tree_type to know how to calculate a tree's type.
- Parameters
-
tt Type of tree (see lal::graphs::tree_type).
- Returns
- True if this tree is of type tt.
◆ is_tree()
|
inlinenoexceptinherited |
Is this graph is an actual tree?
Returns true if the number of edges is one less than the number of nodes. Note that this would not really be true if the addition of edges was not constrained. Since it is constrained in a way that no cycles can be produced (for example, see free_tree::add_edge, or free_tree::add_edges), then we only need to check for the number of edges.
For further characterisations of a tree see [23] (chapter 4, pages 32-33).
- Returns
- True or false depending on whether this graph fits the defintion of tree.
◆ is_tree_type_valid()
|
inlinenoexceptinherited |
Is the type of this tree valid?
This function enables users determine when this tree's type should be calculated.
In case this function returns false, users should call function calculate_tree_type in order to obtain a valid tree type. Note, however, that prior to calling the function the type of this tree might be lal::graphs::tree_type::unknown and that the tree type may remain lal::graphs::tree_type::unknown even after the type has been calculated. Nevertheless, users should be suspicious of a tree being of lal::graphs::tree_type::unknown (in fact, of any) type if this method returns false, yet they should be sure of it if the type was calculated via method calculate_tree_type.
- Returns
- True or false depending on whether the tree type was calculated or not.
◆ normalise()
|
virtualnoexceptinherited |
Normalises the graph.
Sorts this graph's adjacency list structure in increasing order.
Besides expensive, this method may be unnecessary. Method check_normalised() checks whether the graph is normalised or not; in case it is, using this method is completely unnecessary.
- Postcondition
- Method is_normalised evaluates to true.
Reimplemented in lal::graphs::directed_graph.
◆ operator=() [1/2]
Copy assignment operator.
- Parameters
-
f A lal::graphs::free_tree.
◆ operator=() [2/2]
Copy assignment operator.
- Parameters
-
f A lal::graphs::free_tree.
◆ remove_edge()
|
virtualnoexcept |
Remove an edge from this graph.
For developers: method lal::graphs::graph::actions_after_remove_edge is called after the edge has been removed.
- Parameters
-
s Valid node index: \(0 \le s < n\). t Valid node index: \(0 \le t < n\). norm Normalise the graph after the deletion. check_norm If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.
- Precondition
- The edge must exist.
- Postcondition
- If norm is true the tree is guaranteed to be normalised after the addition of the edge.
- The type of tree (m_is_tree_type_valid) is invalidated.
Reimplemented from lal::graphs::undirected_graph.
◆ remove_edges()
|
virtualnoexcept |
Remove an edge from this graph.
This operation is faster than removing edges one by one with remove_edge(node,node,bool,bool) since the edges are removed in bulk.
For developers: method lal::graphs::graph::actions_after_remove_edge is called after each edge has been removed.
- Parameters
-
edges The edges to be deleted. norm Normalise the graph after the deletion. check_norm If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.
- Precondition
- All the edges in edges must meet the precondition of method add_edge(node,node,bool,bool).
- Postcondition
- If norm is true the tree is guaranteed to be normalised after the addition of the edge.
- The type of tree (m_is_tree_type_valid) is invalidated.
Reimplemented from lal::graphs::undirected_graph.
◆ remove_edges_incident_to()
|
virtualnoexcept |
Remove all edges incident to a given vertex.
This operation is faster than removing edges one by one with remove_edge(node,node,bool,bool) since the edges are removed in bulk.
For developers: method lal::graphs::graph::actions_after_remove_edge is called after each edge has been removed.
- Parameters
-
u The node whose incident vertices are to be removed. norm Normalise the graph after the deletion. check_norm If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.
- Postcondition
- If norm is true the tree is guaranteed to be normalised after the addition of the edge.
- The type of tree (m_is_tree_type_valid) is invalidated.
Reimplemented from lal::graphs::undirected_graph.
◆ remove_node()
|
virtualnoexcept |
Remove a node from this graph.
- Parameters
-
u Valid node index: \(0 \le u < n\). norm Normalise the graph after the deletion. check_norm If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.
- Precondition
- The node must exist.
- Postcondition
- If norm is true the graph is guaranteed to be normalised after the addition of the edge.
Reimplemented from lal::graphs::undirected_graph.
◆ remove_single_edge()
|
privatenoexceptinherited |
Removes a single edge.
- Parameters
-
u First node of edge. v Second node of edge. out_u Out-neighbourhood of node u. in_v In-neighbourhood of node v.
◆ set_edges()
|
virtualnoexcept |
Sets the edges to the graph.
Sets the edges of this graph assuming that the nodes indexed in the list are, at most, the number of nodes of this graph.
This list of edges is assumed to be all the edges that are going to be added to this graph. This means that the internal data structures are constructed more efficiently than when adding edges one by one (see add_edge) or in several chunks (see add_edges). For a more controlled addition of the edges, see can_add_edges.
Moreover, the current structure of the graph is cleared before setting the new edges.
- Parameters
-
edges The edges to be added. norm Normalise the graph after the insertions. check_norm If norm is false then, should we check whether the result is normalised or not? This might be useful in case the resulting graph is normalised. If norm is true then check_norm is ignored.
- Precondition
- The graph has been initialized with as many nodes as vertices in the list of edges.
- There are no repeated edges in the list.
- Postcondition
- If norm is true the graph is guaranteed to be normalised after the addition of the edge.
- The type of tree (m_is_tree_type_valid) is invalidated.
Reimplemented from lal::graphs::undirected_graph.
◆ tree_only_init()
|
inlineprotectednoexceptinherited |
Initialises only the memory of class tree.
- Parameters
-
n Number of vertices.
◆ tree_only_remove_node()
|
protectednoexceptinherited |
Removes a vertex from the union-find data structure.
- Parameters
-
u Node that was removed.
- Postcondition
- The tree type is invalidated.
- Updated union-find.
◆ tree_only_set_edges()
|
protectednoexceptinherited |
Updates the data structures of a tree after the graph structure has had its set of edges set.
- Postcondition
- The tree type is invalidated.
- Updated union-find.
◆ update_union_find_after_edge_add() [1/2]
|
protectedvirtualnoexcept |
Update the union find data structure after an edge addition.
This is a helper method to be able to call a template in the lal::detail namespace which updates the union find data structure under addition of an edge.
- Parameters
-
u Node that is connected to v. v Node that is connected to u. root_of Array of n elements relating each vertex to its root in the union find data structure. root_size Array of n elements relating each vertex to the size of the connected component it belongs to.
Implements lal::graphs::tree.
◆ update_union_find_after_edge_add() [2/2]
|
protectedvirtualnoexcept |
Update the union find data structure after an edge addition.
This is a helper method to be able to call a template in the lal::detail namespace which updates the union find data structure under addition of an edge.
- Parameters
-
u Node that is connected to v. v Node that is connected to u. root_of Array of n elements relating each vertex to its root in the union find data structure. root_size Array of n elements relating each vertex to the size of the connected component it belongs to.
Implements lal::graphs::tree.
◆ update_union_find_after_edge_remove() [1/2]
|
protectedvirtualnoexcept |
Update the union find data structure after an edge removal.
This is a helper method to be able to call a template in the lal::detail namespace which updates the union find data structure under removal of an edge.
- Parameters
-
u Node that is connected to v. v Node that is connected to u. root_of Array of n elements relating each vertex to its root in the union find data structure. root_size Array of n elements relating each vertex to the size of the connected component it belongs to.
Implements lal::graphs::tree.
◆ update_union_find_after_edge_remove() [2/2]
|
protectedvirtualnoexcept |
Update the union find data structure after an edge removal.
This is a helper method to be able to call a template in the lal::detail namespace which updates the union find data structure under removal of an edge.
- Parameters
-
u Node that is connected to v. v Node that is connected to u. root_of Array of n elements relating each vertex to its root in the union find data structure. root_size Array of n elements relating each vertex to the size of the connected component it belongs to.
Implements lal::graphs::tree.
◆ update_union_find_before_incident_edges_removed() [1/2]
|
protectedvirtualnoexcept |
Update the union find data structure before the removal of all edges incident to a node.
This is a helper method to be able to call a template in the lal::detail namespace which updates the union find data structure under removal of all incident edges to a node.
- Parameters
-
u Node whose incident edges are to be removed. root_of Array of n elements relating each vertex to its root in the union find data structure. root_size Array of n elements relating each vertex to the size of the connected component it belongs to.
Implements lal::graphs::tree.
◆ update_union_find_before_incident_edges_removed() [2/2]
|
protectedvirtualnoexcept |
Update the union find data structure before the removal of all edges incident to a node.
This is a helper method to be able to call a template in the lal::detail namespace which updates the union find data structure under removal of all incident edges to a node.
- Parameters
-
u Node whose incident edges are to be removed. root_of Array of n elements relating each vertex to its root in the union find data structure. root_size Array of n elements relating each vertex to the size of the connected component it belongs to.
Implements lal::graphs::tree.
Member Data Documentation
◆ m_is_tree_type_valid
|
protectedinherited |
Is the type of this tree valid?
This attribute keeps track of whether or not the function calculate_tree_type should be called before querying the type of this tree via function is_of_tree_type.
◆ m_normalised
|
protectedinherited |
Is this graph normalised?
An undirected graph is normalised iff every node's adjacency list is sorted in increasing order.
In directed graphs, however, it is necessary that the adjacency lists of the out-neighbours and in-neighbours of nodes be sorted.
This attribute is set to 'true' in all graph's initialisation and destruction (when clear() method is called).
◆ m_root_size
|
protectedinherited |
The size of the connected component that a root belongs to.
Formally, m_size_of[v] is the size of the connected component of a root vertex v. A vertex u is a root vertex if there exists a vertex w such that m_root_of[w] = u.
In this context, root is within the union-find data structure.
The documentation for this class was generated from the following file:
- lal/graphs/free_tree.hpp
