Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
|
Public Member Functions | |
RootedTree (const std::vector< std::pair< int, int > > &undirected_edges, int root_) | |
Constructs the tree by calculating parent for every vertex. Assumes a valid description of a tree is provided. | |
Public Member Functions inherited from graph::Graph< T > | |
void | add_edge (T u, T v, bool bidir=true) |
std::map< T, bool > | breadth_first_search (T src) |
Graph (size_t N, const std::vector< std::pair< int, int > > &undirected_edges) | |
Populate the adjacency list for each vertex in the graph. Assumes that evey edge is a pair of valid vertex indices. | |
int | number_of_vertices () const |
Public Attributes | |
std::vector< int > | parent |
Stores parent of every vertex and for root its own index. The root is technically not its own parent, but it's very practical for the lowest common ancestor algorithm. | |
std::vector< int > | level |
Stores the distance from the root. | |
int | root |
Index of the root vertex. | |
Public Attributes inherited from graph::Graph< T > | |
std::vector< std::vector< int > > | neighbors |
for each vertex it stores a list indicies of its neighbors | |
Protected Member Functions | |
void | populate_parents () |
Calculate the parents for all the vertices in the tree. Implements the breadth first search algorithm starting from the root vertex searching the entire tree and labeling parents for all vertices. | |
Representation of a rooted tree. For every vertex its parent is precalculated.
|
inline |
Constructs the tree by calculating parent for every vertex. Assumes a valid description of a tree is provided.
undirected_edges | list of graph's undirected edges |
root_ | index of the root vertex |
|
inlineprotected |
Calculate the parents for all the vertices in the tree. Implements the breadth first search algorithm starting from the root vertex searching the entire tree and labeling parents for all vertices.