Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
graph::RootedTree Class Reference
Inheritance diagram for graph::RootedTree:
[legend]
Collaboration diagram for graph::RootedTree:
[legend]

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. More...
 
- Public Member Functions inherited from graph::Graph
 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. More...
 
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
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. More...
 

Detailed Description

Representation of a rooted tree. For every vertex its parent is precalculated.

Constructor & Destructor Documentation

◆ RootedTree()

graph::RootedTree::RootedTree ( const std::vector< std::pair< int, int > > &  undirected_edges,
int  root_ 
)
inline

Constructs the tree by calculating parent for every vertex. Assumes a valid description of a tree is provided.

Parameters
undirected_edgeslist of graph's undirected edges
root_index of the root vertex
95  : Graph(undirected_edges.size() + 1, undirected_edges), root(root_) {
97  }

Member Function Documentation

◆ populate_parents()

void graph::RootedTree::populate_parents ( )
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.

Returns
none
117  {
118  // Initialize the vector with -1 which indicates the vertex
119  // wasn't yet visited.
122  parent[root] = root;
123  level[root] = 0;
124  std::queue<int> queue_of_vertices;
125  queue_of_vertices.push(root);
126  while (!queue_of_vertices.empty()) {
127  int vertex = queue_of_vertices.front();
128  queue_of_vertices.pop();
129  for (int neighbor : neighbors[vertex]) {
130  // As long as the vertex was not yet visited.
131  if (parent[neighbor] == -1) {
132  parent[neighbor] = vertex;
133  level[neighbor] = level[vertex] + 1;
134  queue_of_vertices.push(neighbor);
135  }
136  }
137  }
138  }
Here is the call graph for this function:

The documentation for this class was generated from the following file:
graph::Graph::Graph
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 v...
Definition: lowest_common_ancestor.cpp:62
graph::RootedTree::level
std::vector< int > level
Stores the distance from the root.
Definition: lowest_common_ancestor.cpp:106
std::vector< int >
std::vector::size
T size(T... args)
graph::RootedTree::populate_parents
void populate_parents()
Calculate the parents for all the vertices in the tree. Implements the breadth first search algorithm...
Definition: lowest_common_ancestor.cpp:117
std::queue
STL class.
std::queue::front
T front(T... args)
graph::RootedTree::parent
std::vector< int > parent
Stores parent of every vertex and for root its own index. The root is technically not its own parent,...
Definition: lowest_common_ancestor.cpp:104
std::queue::pop
T pop(T... args)
graph::Graph::neighbors
std::vector< std::vector< int > > neighbors
for each vertex it stores a list indicies of its neighbors
Definition: lowest_common_ancestor.cpp:77
graph::Graph::number_of_vertices
int number_of_vertices() const
Definition: lowest_common_ancestor.cpp:74
std::queue::empty
T empty(T... args)
std::queue::push
T push(T... args)
graph::RootedTree::root
int root
Index of the root vertex.
Definition: lowest_common_ancestor.cpp:108