Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
graph Namespace Reference

Graph algorithms. More...

Classes

class  Graph
 
class  LowestCommonAncestor
 
class  RootedTree
 

Functions

void add_directed_edge (std::vector< std::vector< int >> *graph, int u, int v)
 Adds a directed edge from vertex u to vertex v. More...
 
void add_undirected_edge (std::vector< std::vector< int >> *graph, int u, int v)
 Adds an undirected edge from vertex u to vertex v. Essentially adds too directed edges to the adjacency list reprsentation of the graph. More...
 
std::vector< bool > breadth_first_search (const std::vector< std::vector< int >> &graph, int start)
 Function performs the breadth first search algorithm over the graph. More...
 
void addEdge (std::vector< std::vector< int >> *adj, int u, int v)
 Function that add edge between two nodes or vertices of graph. More...
 
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. More...
 
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. More...
 
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. More...
 
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. More...
 
void depth_first_search (const std::vector< std::vector< size_t >> &adj, size_t start)
 initiates depth first search algorithm. More...
 
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. More...
 
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. More...
 

Detailed Description

Graph algorithms.

Graph Algorithms.

Function Documentation

◆ add_directed_edge()

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

Adds a directed edge from vertex u to vertex v.

Parameters
graphAdjacency list representation of graph
ufirst vertex
vsecond vertex
66  {
67  (*graph)[u].push_back(v);
68 }

◆ add_undirected_edge()

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

Adds an undirected edge from vertex u to vertex v. Essentially adds too directed edges to the adjacency list reprsentation of the graph.

Parameters
graphAdjacency list representation of graph
ufirst vertex
vsecond vertex
81  {
82  add_directed_edge(graph, u, v);
83  add_directed_edge(graph, v, u);
84 }
Here is the call graph for this function:

◆ 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.
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
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
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 }
Here is the call graph for this function:

◆ breadth_first_search()

std::vector<bool> graph::breadth_first_search ( const std::vector< std::vector< int >> &  graph,
int  start 
)

Function performs the breadth first search algorithm over the graph.

Parameters
graphAdjacency list representation of graph
startvertex from where traversing starts
Returns
a binary vector indicating which vertices were visited during the search.

vector to keep track of visited vertices

a queue that stores vertices that need to be further explored

mark the starting vertex as visited

if the vertex is not visited then mark it as visited and push it to the queue

97  {
98  /// vector to keep track of visited vertices
99  std::vector<bool> visited(graph.size(), false);
100  /// a queue that stores vertices that need to be further explored
101  std::queue<int> tracker;
102 
103  /// mark the starting vertex as visited
104  visited[start] = true;
105  tracker.push(start);
106  while (!tracker.empty()) {
107  size_t vertex = tracker.front();
108  tracker.pop();
109  for (auto x : graph[vertex]) {
110  /// if the vertex is not visited then mark it as visited
111  /// and push it to the queue
112  if (!visited[x]) {
113  visited[x] = true;
114  tracker.push(x);
115  }
116  }
117  }
118  return visited;
119 }
Here is the call graph for this function:

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

66  {
67  /// n denotes the number of vertices in graph
68  int n = adj->size();
69 
70  /// setting all the distances initially to INF
71  std::vector<int64_t> dist(n, INF);
72 
73  /// creating a min heap using priority queue
74  /// first element of pair contains the distance
75  /// second element of pair contains the vertex
78  pq;
79 
80  /// pushing the source vertex 's' with 0 distance in min heap
81  pq.push(std::make_pair(0, s));
82 
83  /// marking the distance of source as 0
84  dist[s] = 0;
85 
86  while (!pq.empty()) {
87  /// second element of pair denotes the node / vertex
88  int currentNode = pq.top().second;
89 
90  /// first element of pair denotes the distance
91  int currentDist = pq.top().first;
92 
93  pq.pop();
94 
95  /// for all the reachable vertex from the currently exploring vertex
96  /// we will try to minimize the distance
97  for (std::pair<int, int> edge : (*adj)[currentNode]) {
98  /// minimizing distances
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 }
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
adjadjacency list of graph.
uvertex or node to be explored.
visitedalready visited vertices.
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
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 }
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
adjadjacency list of graph.
Returns
connected_components number of connected components in graph.
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 }
Here is the call graph for this function:
std::pair
std::vector< bool >
std::vector::size
T size(T... args)
graph::add_directed_edge
void add_directed_edge(std::vector< std::vector< int >> *graph, int u, int v)
Adds a directed edge from vertex u to vertex v.
Definition: breadth_first_search.cpp:66
std::queue
STL class.
std::queue::front
T front(T... args)
std::cout
graph::explore
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 connec...
Definition: depth_first_search.cpp:80
std::queue::pop
T pop(T... args)
std::priority_queue::top
T top(T... args)
std::priority_queue
STL class.
std::greater
graph
Graph algorithms.
graph::explore
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...
Definition: connected_components.cpp:59
std::queue::empty
T empty(T... args)
std::queue::push
T push(T... args)
std::make_pair
T make_pair(T... args)