graph::Graph< T > Class Template Reference

Inheritance diagram for graph::Graph< T >:

Collaboration diagram for graph::Graph< T >:

Public Member Functions
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< std::vector< int > >	neighbors
	for each vertex it stores a list indicies of its neighbors

Private Attributes
std::map< T, std::list< T > >	adjacency_list

Detailed Description

template<typename T>
class graph::Graph< T >

Class for representing a graph as an adjacency list. Its vertices are indexed 0, 1, ..., N - 1.

Definition at line 53 of file lowest_common_ancestor.cpp.

Constructor & Destructor Documentation

Graph()

template<typename T >

graph::Graph< T >::Graph ( size_t N, const std::vector< std::pair< int, int > > & undirected_edges )

inline

Populate the adjacency list for each vertex in the graph. Assumes that evey edge is a pair of valid vertex indices.

Parameters

N	number of vertices in the graph
undirected_edges	list of graph's undirected edges

Definition at line 62 of file lowest_common_ancestor.cpp.

                                                                           {
        neighbors.resize(N);
        for (auto &edge : undirected_edges) {
            neighbors[edge.first].push_back(edge.second);
            neighbors[edge.second].push_back(edge.first);
        }
    }

Member Function Documentation

add_edge()

template<typename T >

void graph::Graph< T >::add_edge ( T u, T v, bool bidir = true )

inline

add_edge(u,v,bidir) is used to add an edge between node u and node v by default , bidir is made true , i.e graph is bidirectional . It means if edge(u,v) is added then u-->v and v-->u both edges exist.

to make the graph unidirectional pass the third parameter of add_edge as false which will

Definition at line 74 of file breadth_first_search.cpp.

                                               {
        adjacency_list[u].push_back(v);  // u-->v edge added
        if (bidir == true) {
            // if graph is bidirectional
            adjacency_list[v].push_back(u);  // v-->u edge added
        }
    }

breadth_first_search()

template<typename T >

std::map< T, bool > graph::Graph< T >::breadth_first_search ( T src )

inline

this function performs the breadth first search on graph and return a mapping which maps the nodes to a boolean value representing whether the node was traversed or not.

mapping to keep track of all visited nodes

initialise every possible vertex to map to false initially none of the vertices are unvisited

queue to store the nodes which are yet to be traversed

push the source vertex to queue to begin traversing

mark the source vertex as visited

traverse the graph till no connected vertex are left extract a node from queue for further traversal

remove the node from the queue

check every vertex connected to the node which are still unvisited

if the neighbour is unvisited , push it into the queue

mark the neighbour as visited

Definition at line 96 of file breadth_first_search.cpp.

                                                {
        std::map<T, bool> visited;
        for (auto const &adjlist : adjacency_list) {
            visited[adjlist.first] = false;
            for (auto const &node : adjacency_list[adjlist.first]) {
                visited[node] = false;
            }
        }
 
        std::queue<T> tracker;
 
        tracker.push(src);
        visited[src] = true;
        while (!tracker.empty()) {
            T node = tracker.front();
            tracker.pop();
            for (T const &neighbour : adjacency_list[node]) {
                if (!visited[neighbour]) {
                    tracker.push(neighbour);
                    visited[neighbour] = true;
                }
            }
        }
        return visited;
    }

number_of_vertices()

template<typename T >

int graph::Graph< T >::number_of_vertices ( ) const

inline

Function to get the number of vertices in the graph

Returns

the number of vertices in the graph.

Definition at line 74 of file lowest_common_ancestor.cpp.

{ return neighbors.size(); }

Member Data Documentation

adjacency_list

template<typename T >

std::map<T, std::list<T> > graph::Graph< T >::adjacency_list

private

adjacency_list maps every vertex to the list of its neighbours in the order in which they are added.

Definition at line 69 of file breadth_first_search.cpp.

neighbors

template<typename T >

std::vector<std::vector<int> > graph::Graph< T >::neighbors

for each vertex it stores a list indicies of its neighbors

Definition at line 77 of file lowest_common_ancestor.cpp.

---

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

• graph/breadth_first_search.cpp
• graph/lowest_common_ancestor.cpp