graph Namespace Reference

Graph Algorithms. More...

Classes
class	Graph
class	HKGraph
	Represents Bipartite graph for Hopcroft Karp implementation. More...
class	LowestCommonAncestor
class	RootedTree

Functions
void	addEdge (std::vector< std::vector< int > > *adj, int u, int v)
	Function that add edge between two nodes or vertices of graph.
void	explore (const std::vector< std::vector< int > > *adj, int u, std::vector< bool > *visited)
	Utility function for depth first seach algorithm this function explores the vertex which is passed into.
int	getConnectedComponents (const std::vector< std::vector< int > > *adj)
	Function that perfoms depth first search algorithm on graph and calculated the number of connected components.
void	addEdge (std::vector< std::vector< size_t > > *adj, size_t u, size_t v)
	Adds and edge between two vertices of graph say u and v in this case.
void	explore (const std::vector< std::vector< size_t > > &adj, size_t v, std::vector< bool > *visited)
	Explores the given vertex, exploring a vertex means traversing over all the vertices which are connected to the vertex that is currently being explored.
void	depth_first_search (const std::vector< std::vector< size_t > > &adj, size_t start)
	initiates depth first search algorithm.
void	addEdge (std::vector< std::vector< std::pair< int, int > > > *adj, int u, int v, int w)
	Function that add edge between two nodes or vertices of graph.
int	dijkstra (std::vector< std::vector< std::pair< int, int > > > *adj, int s, int t)
	Function runs the dijkstra algorithm for some source vertex and target vertex in the graph and returns the shortest distance of target from the source.
bool	checkBipartite (const std::vector< std::vector< int64_t > > &graph, int64_t index, std::vector< int64_t > *visited)
	function to check whether the passed graph is bipartite or not
bool	isBipartite (const std::vector< std::vector< int64_t > > &graph)
	returns true if the given graph is bipartite else returns false
int	TravellingSalesmanProblem (std::vector< std::vector< uint32_t > > *cities, int32_t src, uint32_t V)
	Function calculates the minimum path distance that will cover all the cities starting from the source.

Detailed Description

Graph Algorithms.

Check whether a given graph is bipartite or not.

for std::vector

Graph algorithms.

for IO operations for std::set

Graph Algorithms

A bipartite graph is the one whose nodes can be divided into two disjoint sets in such a way that the nodes in a set are not connected to each other at all, i.e. no intra-set connections. The only connections that exist are that of inter-set, i.e. the nodes from one set are connected to a subset of nodes in the other set. In this implementation, using a graph in the form of adjacency list, check whether the given graph is a bipartite or not.

References used: GeeksForGeeks

Author

tushar2407 for assert for IO operations for queue data structure for vector data structure

Graphical algorithms

for std::min for assert for IO operations for limits of integral types for std::vector

Function Documentation

addEdge() [1/3]

void graph::addEdge	(	std::vector< std::vector< int > > *	adj,
		int	u,
		int	v )

Function that add edge between two nodes or vertices of graph.

Parameters

adj	adjacency list of graph.
u	any node or vertex of graph.
v	any node or vertex of graph.

                                                           {
    (*adj)[u - 1].push_back(v - 1);
    (*adj)[v - 1].push_back(u - 1);
}

addEdge() [2/3]

void graph::addEdge	(	std::vector< std::vector< size_t > > *	adj,
		size_t	u,
		size_t	v )

Adds and edge between two vertices of graph say u and v in this case.

Parameters

adj	Adjacency list representation of graph
u	first vertex
v	second vertex

                                                                    {
    /*
     *
     * Here we are considering undirected graph that's the
     * reason we are adding v to the adjacency list representation of u
     * and also adding u to the adjacency list representation of v
     *
     */
    (*adj)[u - 1].push_back(v - 1);
    (*adj)[v - 1].push_back(u - 1);
}

addEdge() [3/3]

void graph::addEdge	(	std::vector< std::vector< std::pair< int, int > > > *	adj,
		int	u,
		int	v,
		int	w )

Function that add edge between two nodes or vertices of graph.

Parameters

u	any node or vertex of graph
v	any node or vertex of graph

                    {
    (*adj)[u - 1].push_back(std::make_pair(v - 1, w));
    // (*adj)[v - 1].push_back(std::make_pair(u - 1, w));
}

Here is the call graph for this function:

checkBipartite()

bool graph::checkBipartite	(	const std::vector< std::vector< int64_t > > &	graph,
		int64_t	index,
		std::vector< int64_t > *	visited )

function to check whether the passed graph is bipartite or not

Parameters

graph	is a 2D matrix whose rows or the first index signify the node and values in that row signify the nodes it is connected to
index	is the valus of the node currently under observation
visited	is the vector which stores whether a given node has been traversed or not yet

Returns

boolean

< stores the neighbouring node indexes in squence of being reached

insert the current node into the queue

mark the current node as travelled

< stores the neighbour of the current node

check whether the neighbour node is travelled already or not

colour the neighbouring node with different colour than the current node

insert the neighbouring node into the queue

if both the current node and its neighbour has the same state then it is not a bipartite graph

return true when all the connected nodes of the current nodes are travelled and satisify all the above conditions

                                                                {
    std::queue<int64_t> q;  ///< stores the neighbouring node indexes in squence
                            /// of being reached
    q.push(index);          /// insert the current node into the queue
    (*visited)[index] = 1;  /// mark the current node as travelled
    while (q.size()) {
        int64_t u = q.front();
        q.pop();
        for (uint64_t i = 0; i < graph[u].size(); i++) {
            int64_t v =
                graph[u][i];     ///< stores the neighbour of the current node
            if (!(*visited)[v])  /// check whether the neighbour node is
                                 /// travelled already or not
            {
                (*visited)[v] =
                    ((*visited)[u] == 1)
                        ? -1
                        : 1;  /// colour the neighbouring node with
                              /// different colour than the current node
                q.push(v);    /// insert the neighbouring node into the queue
            } else if ((*visited)[v] ==
                       (*visited)[u])  /// if both the current node and its
                                       /// neighbour has the same state then it
                                       /// is not a bipartite graph
            {
                return false;
            }
        }
    }
    return true;  /// return true when all the connected nodes of the current
                  /// nodes are travelled and satisify all the above conditions
}

depth_first_search()

void graph::depth_first_search	(	const std::vector< std::vector< size_t > > &	adj,
		size_t	start )

initiates depth first search algorithm.

Parameters

adj	adjacency list of graph
start	vertex from where DFS starts traversing.

                                      {
    size_t vertices = adj.size();
 
    std::vector<bool> visited(vertices, false);
    explore(adj, start, &visited);
}

Here is the call graph for this function:

dijkstra()

int graph::dijkstra	(	std::vector< std::vector< std::pair< int, int > > > *	adj,
		int	s,
		int	t )

Function runs the dijkstra algorithm for some source vertex and target vertex in the graph and returns the shortest distance of target from the source.

Parameters

adj	input graph
s	source vertex
t	target vertex

Returns

shortest distance if target is reachable from source else -1 in case if target is not reachable from source.

n denotes the number of vertices in graph

setting all the distances initially to INF

creating a min heap using priority queue first element of pair contains the distance second element of pair contains the vertex

pushing the source vertex 's' with 0 distance in min heap

marking the distance of source as 0

second element of pair denotes the node / vertex

first element of pair denotes the distance

for all the reachable vertex from the currently exploring vertex we will try to minimize the distance

minimizing distances

                                                                         {
    /// n denotes the number of vertices in graph
    int n = adj->size();
 
    /// setting all the distances initially to INF
    std::vector<int64_t> dist(n, INF);
 
    /// creating a min heap using priority queue
    /// first element of pair contains the distance
    /// second element of pair contains the vertex
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
                        std::greater<std::pair<int, int>>>
        pq;
 
    /// pushing the source vertex 's' with 0 distance in min heap
    pq.push(std::make_pair(0, s));
 
    /// marking the distance of source as 0
    dist[s] = 0;
 
    while (!pq.empty()) {
        /// second element of pair denotes the node / vertex
        int currentNode = pq.top().second;
 
        /// first element of pair denotes the distance
        int currentDist = pq.top().first;
 
        pq.pop();
 
        /// for all the reachable vertex from the currently exploring vertex
        /// we will try to minimize the distance
        for (std::pair<int, int> edge : (*adj)[currentNode]) {
            /// minimizing distances
            if (currentDist + edge.second < dist[edge.first]) {
                dist[edge.first] = currentDist + edge.second;
                pq.push(std::make_pair(dist[edge.first], edge.first));
            }
        }
    }
    if (dist[t] != INF) {
        return dist[t];
    }
    return -1;
}

Here is the call graph for this function:

explore() [1/2]

void graph::explore	(	const std::vector< std::vector< int > > *	adj,
		int	u,
		std::vector< bool > *	visited )

Utility function for depth first seach algorithm this function explores the vertex which is passed into.

Parameters

adj	adjacency list of graph.
u	vertex or node to be explored.
visited	already visited vertices.

                                       {
    (*visited)[u] = true;
    for (auto v : (*adj)[u]) {
        if (!(*visited)[v]) {
            explore(adj, v, visited);
        }
    }
}

Here is the call graph for this function:

explore() [2/2]

void graph::explore	(	const std::vector< std::vector< size_t > > &	adj,
		size_t	v,
		std::vector< bool > *	visited )

Explores the given vertex, exploring a vertex means traversing over all the vertices which are connected to the vertex that is currently being explored.

Parameters

adj	garph
v	vertex to be explored
visited	already visited vertices

                                       {
    std::cout << v + 1 << " ";
    (*visited)[v] = true;
    for (auto x : adj[v]) {
        if (!(*visited)[x]) {
            explore(adj, x, visited);
        }
    }
}

Here is the call graph for this function:

getConnectedComponents()

int graph::getConnectedComponents

(

const std::vector< std::vector< int > > *

adj

)

Function that perfoms depth first search algorithm on graph and calculated the number of connected components.

Parameters

adj	adjacency list of graph.

Returns

connected_components number of connected components in graph.

                                                                 {
    int n = adj->size();
    int connected_components = 0;
    std::vector<bool> visited(n, false);
 
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            explore(adj, i, &visited);
            connected_components++;
        }
    }
    return connected_components;
}

Here is the call graph for this function:

isBipartite()

bool graph::isBipartite

(

const std::vector< std::vector< int64_t > > &

graph

)

returns true if the given graph is bipartite else returns false

Parameters

graph

is a 2D matrix whose rows or the first index signify the node and values in that row signify the nodes it is connected to

Returns

booleans

< stores boolean values which signify whether that node had been visited or not

if the current node is not visited then check whether the sub-graph of that node is a bipartite or not

                                                             {
    std::vector<int64_t> visited(
        graph.size());  ///< stores boolean values
                        /// which signify whether that node had been visited or
                        /// not
 
    for (uint64_t i = 0; i < graph.size(); i++) {
        if (!visited[i])  /// if the current node is not visited then check
                          /// whether the sub-graph of that node is a bipartite
                          /// or not
        {
            if (!checkBipartite(graph, i, &visited)) {
                return false;
            }
        }
    }
    return true;
}

Here is the call graph for this function:

TravellingSalesmanProblem()

int graph::TravellingSalesmanProblem	(	std::vector< std::vector< uint32_t > > *	cities,
		int32_t	src,
		uint32_t	V )

Function calculates the minimum path distance that will cover all the cities starting from the source.

Parameters

cities	matrix representation of cities
src	Point from where salesman is starting
V	number of vertices in the graph

                                                       {
    //// vtx stores the vertexs of the graph
    std::vector<uint32_t> vtx;
    for (uint32_t i = 0; i < V; i++) {
        if (i != src) {
            vtx.push_back(i);
        }
    }
 
    //// store minimum weight Hamiltonian Cycle.
    int32_t min_path = 2147483647;
    do {
        //// store current Path weight(cost)
        int32_t curr_weight = 0;
 
        //// compute current path weight
        int k = src;
        for (int i : vtx) {
            curr_weight += (*cities)[k][i];
            k = i;
        }
        curr_weight += (*cities)[k][src];
 
        //// update minimum
        min_path = std::min(min_path, curr_weight);
 
    } while (next_permutation(vtx.begin(), vtx.end()));
 
    return min_path;
}

Here is the call graph for this function: