TheAlgorithms/C++ 1.0.0
All the algorithms implemented in C++
Loading...
Searching...
No Matches
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.

for assert

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 IO operations for limits of integral types for std::vector

Graph Algorithms

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
adjadjacency list of graph.
uany node or vertex of graph.
vany node or vertex of graph.

Definition at line 46 of file connected_components.cpp.

46 {
47 (*adj)[u - 1].push_back(v - 1);
48 (*adj)[v - 1].push_back(u - 1);
49}

◆ 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
adjAdjacency list representation of graph
ufirst vertex
vsecond vertex

Definition at line 56 of file depth_first_search.cpp.

56 {
57 /*
58 *
59 * Here we are considering undirected graph that's the
60 * reason we are adding v to the adjacency list representation of u
61 * and also adding u to the adjacency list representation of v
62 *
63 */
64 (*adj)[u - 1].push_back(v - 1);
65 (*adj)[v - 1].push_back(u - 1);
66}

◆ 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
uany node or vertex of graph
vany node or vertex of graph

Definition at line 48 of file dijkstra.cpp.

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

◆ 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
graphis a 2D matrix whose rows or the first index signify the node and values in that row signify the nodes it is connected to
indexis the valus of the node currently under observation
visitedis 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

Definition at line 37 of file is_graph_bipartite2.cpp.

38 {
39 std::queue<int64_t> q;
41 q.push(index);
42 (*visited)[index] = 1;
43 while (q.size()) {
44 int64_t u = q.front();
45 q.pop();
46 for (uint64_t i = 0; i < graph[u].size(); i++) {
47 int64_t v =
48 graph[u][i];
49 if (!(*visited)[v])
51 {
52 (*visited)[v] =
53 ((*visited)[u] == 1)
54 ? -1
55 : 1;
57 q.push(v);
58 } else if ((*visited)[v] ==
59 (*visited)[u])
62 {
63 return false;
64 }
65 }
66 }
67 return true;
69}
Graph Algorithms.

◆ 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
adjadjacency list of graph
startvertex from where DFS starts traversing.

Definition at line 99 of file depth_first_search.cpp.

100 {
101 size_t vertices = adj.size();
102
103 std::vector<bool> visited(vertices, false);
104 explore(adj, start, &visited);
105}
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 in...

◆ 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
adjinput graph
ssource vertex
ttarget 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

Definition at line 66 of file dijkstra.cpp.

66 {
68 int n = adj->size();
69
71 std::vector<int64_t> dist(n, INF);
72
76 std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>,
77 std::greater<std::pair<int, int>>>
78 pq;
79
81 pq.push(std::make_pair(0, s));
82
84 dist[s] = 0;
85
86 while (!pq.empty()) {
88 int currentNode = pq.top().second;
89
91 int currentDist = pq.top().first;
92
93 pq.pop();
94
97 for (std::pair<int, int> edge : (*adj)[currentNode]) {
99 if (currentDist + edge.second < dist[edge.first]) {
100 dist[edge.first] = currentDist + edge.second;
101 pq.push(std::make_pair(dist[edge.first], edge.first));
102 }
103 }
104 }
105 if (dist[t] != INF) {
106 return dist[t];
107 }
108 return -1;
109}

◆ 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
adjadjacency list of graph.
uvertex or node to be explored.
visitedalready visited vertices.

Definition at line 59 of file connected_components.cpp.

60 {
61 (*visited)[u] = true;
62 for (auto v : (*adj)[u]) {
63 if (!(*visited)[v]) {
64 explore(adj, v, visited);
65 }
66 }
67}

◆ 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
adjgarph
vvertex to be explored
visitedalready visited vertices

Definition at line 80 of file depth_first_search.cpp.

81 {
82 std::cout << v + 1 << " ";
83 (*visited)[v] = true;
84 for (auto x : adj[v]) {
85 if (!(*visited)[x]) {
86 explore(adj, x, visited);
87 }
88 }
89}

◆ 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
adjadjacency list of graph.
Returns
connected_components number of connected components in graph.

Definition at line 77 of file connected_components.cpp.

77 {
78 int n = adj->size();
79 int connected_components = 0;
80 std::vector<bool> visited(n, false);
81
82 for (int i = 0; i < n; i++) {
83 if (!visited[i]) {
84 explore(adj, i, &visited);
85 connected_components++;
86 }
87 }
88 return connected_components;
89}

◆ isBipartite()

bool graph::isBipartite ( const std::vector< std::vector< int64_t > > & graph)

returns true if the given graph is bipartite else returns false

Parameters
graphis 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

Definition at line 76 of file is_graph_bipartite2.cpp.

76 {
77 std::vector<int64_t> visited(
78 graph.size());
81
82 for (uint64_t i = 0; i < graph.size(); i++) {
83 if (!visited[i])
86 {
87 if (!checkBipartite(graph, i, &visited)) {
88 return false;
89 }
90 }
91 }
92 return true;
93}
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

◆ 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
citiesmatrix representation of cities
srcPoint from where salesman is starting
Vnumber of vertices in the graph

Definition at line 41 of file travelling_salesman_problem.cpp.

42 {
44 std::vector<uint32_t> vtx;
45 for (uint32_t i = 0; i < V; i++) {
46 if (i != src) {
47 vtx.push_back(i);
48 }
49 }
50
52 int32_t min_path = 2147483647;
53 do {
55 int32_t curr_weight = 0;
56
58 int k = src;
59 for (int i : vtx) {
60 curr_weight += (*cities)[k][i];
61 k = i;
62 }
63 curr_weight += (*cities)[k][src];
64
66 min_path = std::min(min_path, curr_weight);
67
68 } while (next_permutation(vtx.begin(), vtx.end()));
69
70 return min_path;
71}
double k(double x)
Another test function.