#### Overview of this book

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++. This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book. By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.
Free Chapter
1. Lists, Stacks, and Queues
2. Trees, Heaps, and Graphs
3. Hash Tables and Bloom Filters
4. Divide and Conquer
5. Greedy Algorithms
6. Graph Algorithms I
7. Graph Algorithms II
8. Dynamic Programming I
9. Dynamic Programming II

## Chapter 6: Graph Algorithms I

### Activity 13: Finding out Whether a Graph is Bipartite Using DFS

In this activity, we will check whether a graph is bipartite using depth-first search traversal. Follow these steps to complete the activity:

1. Add the required header files and declare the graph to be used:

#include <string>

#include <vector>

#include <iostream>

#include <set>

#include <map>

#include <stack>

template<typename T> class Graph;

2. Write the following struct to define an edge in our graph:

template<typename T>

struct Edge

{

size_t src;

size_t dest;

T weight;

// To compare edges, only compare their weights,

// and not the source/destination vertices

inline bool operator< (const Edge<T>& e) const

{

return this->weight < e.weight;

}

inline bool operator> (const Edge<T>& e) const

{

return this->weight > e.weight;

}

};

3. Use the following function to overload the << operator for the graph so that it can be written to standard output:

template <typename T>

std::ostream& operator<<(std::ostream& os, const Graph<T>& G)

{

for (auto i = 1; i < G.vertices(); i++)

{

os << i << ":\t";

auto edges = G.outgoing_edges(i);

for (auto& e : edges)

os << "{" << e.dest << ": " << e.weight << "}, ";

os << std::endl;

}

return os;

}

4. Implement the edge list graph as follows:

template<typename T>

class Graph

{

public:

// Initialize the graph with N vertices

Graph(size_t N) : V(N)

{}

// Return number of vertices in the graph

auto vertices() const

{

return V;

}

// Return all edges in the graph

auto& edges() const

{

return edge_list;

}

{

// Check if the source and destination vertices are within range

if (e.src >= 1 && e.src <= V &&

e.dest >= 1 && e.dest <= V)

edge_list.emplace_back(e);

else

std::cerr << "Vertex out of bounds" << std::endl;

}

// Returns all outgoing edges from vertex v

auto outgoing_edges(size_t v) const

{

std::vector<Edge<T>> edges_from_v;

for (auto& e : edge_list)

{

if (e.src == v)

edges_from_v.emplace_back(e);

}

return edges_from_v;

}

// Overloads the << operator so a graph be written directly to a stream

// Can be used as std::cout << obj << std::endl;

template <typename T>

friend std::ostream& operator<< <>(std::ostream& os, const Graph<T>& G);

private:

size_t V;        // Stores number of vertices in graph

std::vector<Edge<T>> edge_list;

};

5. Create the graph shown in figure 6.17, as shown here:

template <typename T>

auto create_bipartite_reference_graph()

{

Graph<T> G(10);

std::map<unsigned, std::vector<std::pair<size_t, T>>> edges;

edges[1] = { {2, 0} };

edges[2] = { {1, 0}, {3, 0} , {8, 0} };

edges[3] = { {2, 0}, {4, 0} };

edges[4] = { {3, 0}, {6, 0} };

edges[5] = { {7, 0}, {9, 0} };

edges[6] = { {1, 0}, {4, 0} };

edges[7] = { {5, 0} };

edges[8] = { {2,0}, {9, 0} };

edges[9] = { {5, 0} };

for (auto& i : edges)

for (auto& j : i.second)

return G;

}

6. Now, we need a function so that we can implement our algorithm and check whether the graph is bipartite. Write the function like so:

template <typename T>

auto bipartite_check(const Graph<T>& G)

{

std::stack<size_t> stack;

std::set<size_t> visited;

stack.push(1); // Assume that BFS always starts from vertex ID 1

enum class colors {NONE, RED, BLUE};

colors current_color{colors::BLUE}; // This variable tracks the color to be assigned to the next vertex that is visited.

std::vector<colors> vertex_colors(G.vertices(), colors::NONE);

while (!stack.empty())

{

auto current_vertex = stack.top();

stack.pop();

// If the current vertex hasn't been visited in the past

if (visited.find(current_vertex) == visited.end())

{

visited.insert(current_vertex);

vertex_colors[current_vertex] = current_color;

if (current_color == colors::RED)

{

std::cout << "Coloring vertex " << current_vertex << " RED" << std::endl;

current_color = colors::BLUE;

}

else

{

std::cout << "Coloring vertex "

<< current_vertex << " BLUE" << std::endl;

current_color = colors::RED;

}

for (auto e : G.outgoing_edges(current_vertex))

if (visited.find(e.dest) == visited.end())

stack.push(e.dest);

}

// If the found vertex is already colored and

// has a color same as its parent's color, the graph is not bipartite

else if (visited.find(current_vertex) != visited.end() &&

((vertex_colors[current_vertex] == colors::BLUE &&

current_color == colors::RED) ||

(vertex_colors[current_vertex] == colors::RED &&

current_color == colors::BLUE)))

return false;

}

// If all vertices have been colored, the graph is bipartite

return true;

}

7. Use the following functions to implement the test and driver code that tests our implementation of the bipartite checking algorithm:

template <typename T>

void test_bipartite()

{

// Create an instance of and print the graph

auto BG = create_bipartite_reference_graph<T>();

std::cout << BG << std::endl;

if (bipartite_check<T>(BG))

std::cout << "The graph is bipartite" << std::endl;

else

std::cout << "The graph is not bipartite" << std::endl;

}

int main()

{

using T = unsigned;

test_bipartite<T>();

return 0;

}

8. Run the program. You should see the following output:

### Activity 14: Shortest Path in New York

In this activity, we will use the graph of various locations in New York City and find the shortest distance between the two given vertices. Follow these steps to complete the activity:

1. Add the required header files and declare the graph, as shown here:

#include <string>

#include <vector>

#include <iostream>

#include <set>

#include <map>

#include <limits>

#include <queue>

#include <fstream>

#include <sstream>

template<typename T> class Graph;

2. Implement the weighted edge that will be used in the graph:

template<typename T>

struct Edge

{

size_t src;

size_t dest;

T weight;

// To compare edges, only compare their weights,

// and not the source/destination vertices

inline bool operator< (const Edge<T>& e) const

{

return this->weight < e.weight;

}

inline bool operator> (const Edge<T>& e) const

{

return this->weight > e.weight;

}

};

3. Overload the << operator for the Graph class so that it can be output to the C++ streams:

template <typename T>

std::ostream& operator<<(std::ostream& os, const Graph<T>& G)

{

for (auto i = 1; i < G.vertices(); i++)

{

os << i << ":\t";

auto edges = G.outgoing_edges(i);

for (auto& e : edges)

os << "{" << e.dest << ": " << e.weight << "}, ";

os << std::endl;

}

return os;

}

4. Implement an edge list graph, as shown here:

template<typename T>

class Graph

{

public:

// Initialize the graph with N vertices

Graph(size_t N) : V(N)

{}

// Return number of vertices in the graph

auto vertices() const

{

return V;

}

// Return all edges in the graph

auto& edges() const

{

return edge_list;

}

{

// Check if the source and destination vertices are within range

if (e.src >= 1 && e.src <= V &&

e.dest >= 1 && e.dest <= V)

edge_list.emplace_back(e);

else

std::cerr << "Vertex out of bounds" << std::endl;

}

// Returns all outgoing edges from vertex v

auto outgoing_edges(size_t v) const

{

std::vector<Edge<T>> edges_from_v;

for (auto& e : edge_list)

{

if (e.src == v)

edges_from_v.emplace_back(e);

}

return edges_from_v;

}

// Overloads the << operator so a graph be written directly to a stream

// Can be used as std::cout << obj << std::endl;

template <typename T>

friend std::ostream& operator<< <>(std::ostream& os, const Graph<T>& G);

private:

size_t V;        // Stores number of vertices in graph

std::vector<Edge<T>> edge_list;

};

5. Write the following function so that you can parse the graph file and prepare the graph:

template <typename T>

{

size_t num_vertices, num_edges;

std::string line;

// Read the problem description line that starts with 'p' and looks like:

// p <num_vertices> <num_edges>

while (std::getline(infile, line))

{

if (line[0] == 'p')

{

std::istringstream iss(line);

char p;

std::string sp;

iss >> p >>sp >> num_vertices >> num_edges;

std::cout << "Num vertices: " << num_vertices

<< " Num edges: " << num_edges <<std::endl;

break;

}

}

Graph<T> G(num_vertices + 1);

// Read the edges and edge weights, which look like:

// a <source_vertex> <destination_vertex> <weight>

while (std::getline(infile, line))

{

if (line[0] == 'a')

{

std::istringstream iss(line);

char p;

size_t source_vertex, dest_vertex;

T weight;

iss >> p >> source_vertex >> dest_vertex >> weight;

}

}

infile.close();

return G;

}

6. Now, we need a struct that implements a Label struct that will be assigned to each vertex as Dijkstra's algorithm runs. Implement it as follows:

template<typename T>

struct Label

{

size_t vertex_ID;

T distance_from_source;

Label(size_t _id, T _distance) :

vertex_ID(_id),

distance_from_source(_distance)

{}

// To compare labels, only compare their distances from source

inline bool operator< (const Label<T>& l) const

{

return this->distance_from_source < l.distance_from_source;

}

inline bool operator> (const Label<T>& l) const

{

return this->distance_from_source > l.distance_from_source;

}

inline bool operator() (const Label<T>& l) const

{

return this > l;

}

};

7. Dijkstra's algorithm can be implemented as follows:

template <typename T>

auto dijkstra_shortest_path(const Graph<T>& G, size_t src, size_t dest)

{

std::priority_queue<Label<T>, std::vector<Label<T>>, std::greater<Label<T>>> heap;

std::set<int> visited;

std::vector<size_t> parent(G.vertices());

std::vector<T> distance(G.vertices(), std::numeric_limits<T>::max());

std::vector<size_t> shortest_path;

heap.emplace(src, 0);

parent[src] = src;

// Search for the destination vertex in the graph

while (!heap.empty()) {

auto current_vertex = heap.top();

heap.pop();

// If the search has reached the destination vertex

if (current_vertex.vertex_ID == dest) {

std::cout << "Destination " <<

current_vertex.vertex_ID << " reached." << std::endl;

break;

}

if (visited.find(current_vertex.vertex_ID) == visited.end()) {

std::cout << "Settling vertex " <<

current_vertex.vertex_ID << std::endl;

// For each outgoing edge from the current vertex,

// create a label for the destination vertex and add it to the heap

for (auto e : G.outgoing_edges(current_vertex.vertex_ID)) {

auto neighbor_vertex_ID = e.dest;

auto new_distance_to_dest=current_vertex.distance_from_source

+ e.weight;

// Check if the new path to the destination vertex

// has a lower cost than any previous paths found to it, if // yes, then this path should be preferred

if (new_distance_to_dest < distance[neighbor_vertex_ID]) {

heap.emplace(neighbor_vertex_ID, new_distance_to_dest);

parent[e.dest] = current_vertex.vertex_ID;

distance[e.dest] = new_distance_to_dest;

}

}

visited.insert(current_vertex.vertex_ID);

}

}

// Construct the path from source to the destination by backtracking

// using the parent indexes

auto current_vertex = dest;

while (current_vertex != src) {

shortest_path.push_back(current_vertex);

current_vertex = parent[current_vertex];

}

shortest_path.push_back(src);

std::reverse(shortest_path.begin(), shortest_path.end());

return shortest_path;

}

8. Finally, implement the test and driver code, as shown here:

template<typename T>

void test_dijkstra()

{

//std::cout << G << std::endl;

auto shortest_path = dijkstra_shortest_path<T>(G, 913, 542);

std::cout << "The shortest path between 913 and 542 is:" << std::endl;

for (auto v : shortest_path)

std::cout << v << " ";

std::cout << std::endl;

}

int main()

{

using T = unsigned;

test_dijkstra<T>();

return 0;

}

9. Run the program. Your output should look as follows: