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.

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

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

Here is the call graph for this function:

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

                                               {
        /**
         *  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
         */
        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

                                                {
        /// mapping to keep track of all visited nodes
        std::map<T, bool> visited;
        /// initialise every possible vertex to map to false
        /// initially none of the vertices are unvisited
        for (auto const &adjlist : adjacency_list) {
            visited[adjlist.first] = false;
            for (auto const &node : adjacency_list[adjlist.first]) {
                visited[node] = false;
            }
        }
 
        /// queue to store the nodes which are yet to be traversed
        std::queue<T> tracker;
 
        /// push the source vertex to queue to begin traversing
        tracker.push(src);
        /// mark the source vertex as visited
        visited[src] = true;
        while (!tracker.empty()) {
            /// traverse the graph till no connected vertex are left
            /// extract a node from queue for further traversal
            T node = tracker.front();
            /// remove the node from the queue
            tracker.pop();
            for (T const &neighbour : adjacency_list[node]) {
                /// check every vertex connected to the node which are still
                /// unvisited
                if (!visited[neighbour]) {
                    /// if the neighbour is unvisited , push it into the queue
                    tracker.push(neighbour);
                    /// mark the neighbour as visited
                    visited[neighbour] = true;
                }
            }
        }
        return visited;
    }

Here is the call graph for this function:

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.

{ return neighbors.size(); }

Here is the call graph for this function:

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.

---

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

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