graph::RootedTree Class Reference

Inheritance diagram for graph::RootedTree:

Collaboration diagram for graph::RootedTree:

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.

Detailed Description

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

Definition at line 84 of file lowest_common_ancestor.cpp.

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_edges	list of graph's undirected edges
root_	index of the root vertex

Definition at line 93 of file lowest_common_ancestor.cpp.

        : Graph(undirected_edges.size() + 1, undirected_edges), root(root_) {
        populate_parents();
    }

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

Definition at line 117 of file lowest_common_ancestor.cpp.

                            {
        // Initialize the vector with -1 which indicates the vertex
        // wasn't yet visited.
        parent = std::vector<int>(number_of_vertices(), -1);
        level = std::vector<int>(number_of_vertices());
        parent[root] = root;
        level[root] = 0;
        std::queue<int> queue_of_vertices;
        queue_of_vertices.push(root);
        while (!queue_of_vertices.empty()) {
            int vertex = queue_of_vertices.front();
            queue_of_vertices.pop();
            for (int neighbor : neighbors[vertex]) {
                // As long as the vertex was not yet visited.
                if (parent[neighbor] == -1) {
                    parent[neighbor] = vertex;
                    level[neighbor] = level[vertex] + 1;
                    queue_of_vertices.push(neighbor);
                }
            }
        }
    }

Member Data Documentation

level

std::vector<int> graph::RootedTree::level

Stores the distance from the root.

Definition at line 106 of file lowest_common_ancestor.cpp.

parent

std::vector<int> graph::RootedTree::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.

Definition at line 104 of file lowest_common_ancestor.cpp.

root

int graph::RootedTree::root

Index of the root vertex.

Definition at line 108 of file lowest_common_ancestor.cpp.

---

The documentation for this class was generated from the following file:

• graph/lowest_common_ancestor.cpp