Book Image

C++ Data Structures and Algorithm Design Principles

By : John Carey, Anil Achary, Shreyans Doshi, Payas Rajan
Book Image

C++ Data Structures and Algorithm Design Principles

By: John Carey, Anil Achary, Shreyans Doshi, Payas Rajan

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.
Table of Contents (11 chapters)

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;

        }

        void add_edge(Edge<T>&& e)

        {

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

                G.add_edge(Edge<T>{ i.first, j.first, j.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;

                }

                // Add unvisited adjacent vertices to the stack.

                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:
    Figure 6.34: Output of Activity 13
Figure 6.34: Output of Activity 13

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;

        }

        void add_edge(Edge<T>&& e)

        {

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

    auto read_graph_from_file()

    {

        std::ifstream infile("USA-road-d.NY.gr");

        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;

                G.add_edge(Edge<T>{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()

    {

        auto G = read_graph_from_file<T>();

        //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:
Figure 6.35: Output of Activity 14
Figure 6.35: Output of Activity 14