# Algorithms_in_C++: graph Namespace Reference

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

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

{
(*graph)[u].push_back(v);
}

## 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

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

{
add_directed_edge(graph, u, v);
add_directed_edge(graph, v, u);
}
Here is the call graph for this function:

## addEdge() [1/2]

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/2]

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:

## 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

  graph | Adjacency list representation of graph
  start | vertex 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

{
/// vector to keep track of visited vertices
std::vector<bool> visited(graph.size(), false);
/// a queue that stores vertices that need to be further explored
std::queue<int> tracker;
/// mark the starting vertex as visited
visited[start] = true;
tracker.push(start);
while (!tracker.empty()) {
size_t vertex = tracker.front();
tracker.pop();
for (auto x : graph[vertex]) {
/// if the vertex is not visited then mark it as visited
/// and push it to the queue
if (!visited[x]) {
visited[x] = true;
tracker.push(x);
}
}
}
return 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()

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);
}
}
}

## 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:
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::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)