CLRS Implementation of BFS and DFS in C++

Question

I tried to implement BFS and DFS from Introduction to Algorithms by Cormen. Any suggestions on how to improve my code?

GraphStructures.h

#pragma once
#ifndef GRAPH_STRUCTURES_H
#define GRAPH_STRUCTURES_H


#include <vector>
#include <string>
#include <limits>
#include <fstream>
#include <sstream>

enum class Status { UNDISCOVERED, DISCOVERED, PROCESSED };

enum { INF = std::numeric_limits<int>::max() };

struct Vertex
{
    int id;

    Status status;
    size_t distance;
    Vertex* parent;

    size_t start;
    size_t finish;

    Vertex(int vertex) : id{ vertex } {};
};

struct Graph
{
    std::vector<Vertex*> vertex = std::vector<Vertex*>(250);
    //Adjacency List
    std::vector<std::vector<Vertex*>> adj = std::vector<std::vector<Vertex*>> (250);


    //add edges from a file
    void add_edge(std::string filename)
    {
        Vertex* obj_u = nullptr, *obj_v = nullptr;
        std::ifstream file_in(filename);
        std::string line;
        while (getline(file_in, line))
        {
            int u, v;
            std::istringstream iss(line);
            iss >> u;
            iss >> v;

            if (vertex[u] == nullptr)
            {
                obj_u = new Vertex(u);
                vertex[u] = obj_u;
            }
            if (vertex[v] == nullptr)
            {
                obj_v = new Vertex(v);
                vertex[v] = obj_v;
            }

            //undirected graph where u->v and v->u
            adj[u].push_back(vertex[v]);
            adj[v].push_back(vertex[u]);
        }
    }

    ~Graph()
    {
        for each (auto& var in vertex)
        {
            if (var)
                delete var;
        }
    }
};
#endif // !GRAPH_STRUCTURES_H

GraphAlgorithms.h

#pragma once
#ifndef GRAPH_ALGORITHMS_H
#define GRAPH_ALGORITHMS_H

#include "Graphstructures.h"
#include <string>

void BFS(const Graph&, const int);
void print_path(const Graph& G, const int, const int);
void DFS(const Graph&);
void visit(const Graph&, const int);

#endif // !GRAPH_ALGORITHMS_H

GraphAlgorithms.cpp

#include "stdafx.h"
#include "GraphAlgorithms.h"
#include <queue>
#include <iostream>
#include <memory>



void BFS(const Graph& G, const int src) 
{
    for each (auto& u in G.vertex)
    {
        if (u)
        {
            u->status = Status::UNDISCOVERED;
            u->distance = INF;
            u->parent = nullptr;
        }
    }
    const auto s = G.vertex[src];
    s->status = Status::DISCOVERED;
    s->distance = 0;
    s->parent = nullptr;

    std::queue<Vertex*> Q;
    Q.push(s);

    while (!Q.empty())
    {
        Vertex* u = Q.front();
        Q.pop();

        for each (auto& v in G.adj[u->id])
        {
            if (v->status == Status::UNDISCOVERED)
            {
                v->status = Status::DISCOVERED;
                v->distance = u->distance + 1;
                v->parent = u;
                Q.push(v);
            }
        }
        u->status = Status::PROCESSED;
        std::cout << std::endl;
    }

}

void print_path(const Graph & G, const int src, const int ver)
{
    auto s = G.vertex[src];
    auto v = G.vertex[ver];

    if (s == v)
        std::cout << s->id << " -> ";
    else
    {
        if (v->parent == nullptr)
            std::cout << "* -> ";
        else
        {
            print_path(G, s->id, v->parent->id);
            std::cout << v->parent->id << " -> ";
        }
    }
}

size_t time = 0;

void DFS(const Graph& G)
{
    for (auto& v : G.vertex) {
        if (v)
        {
            v->status = Status::UNDISCOVERED;
            v->parent = nullptr;
            v->start = 0;
            v->finish = 0;
        }
    }

    for (auto& u : G.vertex)
    {
        if (u)
        {
            if (u->status == Status::UNDISCOVERED)
            {
                visit(G, u->id);
            }
        }
    }
}

void visit(const Graph& G, const int ver)
{
    auto u = G.vertex[ver];
    u->status = Status::DISCOVERED;
    u->start = ++time;

    for (auto& v : G.adj[u->id])
    {
        if (v->status == Status::UNDISCOVERED)
        {
            visit(G, v->id);
        }
    }

    u->status = Status::PROCESSED;
    u->finish = ++time;
}

Answer 1

Rule of 0/3/5

As your Graph class possess pointers and allocate their memory you should follow the rule of 0 or 5.

Rule of three: If a class requires a user-defined destructor, a user-defined copy constructor, or a user-defined copy assignment operator, it almost certainly requires all three.

As C++11 implements the move semantics, you should also define the move constructor and move assignment constructor. (rule of 5)

You can avoid the rule of 5 by using smart pointers instead, making it the rule of 0.

SOLID Principle

You probably did this for the example only, but your Graph class breaks the first SOLID principle:

Single responsibility principle: The single responsibility principle states that every module or class should have responsibility over a single part of the functionality provided by the software.

As your Graph class is a struct that only store the vertexes data, it shouldn't handle the whole file opening thing. This part should be done by another class that could open any file for any purpose. Making your Graph opening the file makes it dependent on this storage system while it could be more generic, it is also the first step to copy-pasted code.

C++11

You are using c++11 features correctly and that's worth being noted. Besides that, you declare and define a global variable in GraphAlgorithms.cpp.

size_t time = 0;

This is probably a good sign that you need to encapsulate your functions in a class with a time attribute.

Answer 2

Thanks to @Stud 's comments, I was able to make the following changes to my earlier question:

1. Rule of 0 (used smart pointers instead of raw new and delete
2. Enforced the SOLID (Single responsibility) Principle
3. Separated the file opening from Graph class.
4. Encapsulated my functions into a class with a time attribute.

Graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include <memory>
#include <limits>
#include <string>
#include <vector>

class Graph
{
    enum class Status { UNDISCOVERED, DISCOVERED, PROCESSED };

    enum { INF = std::numeric_limits<int>::max() };

    struct Vertex
    {
        int id;

        Status status;
        size_t distance;
        std::shared_ptr<Vertex> parent;

        size_t start;
        size_t finish;

        Vertex(const int vertex) : id{ vertex } {};
    };
public:
    Graph(int size) : vertex{ size }, adj{ size }, time { 0 } {};
    ~Graph() {} ;

    void BFS(const int) const;
    void print_path(const int, const int) const;
    void DFS();
    void visit(const int);
    void add_edge(int, int);

    std::vector<std::shared_ptr<Vertex>> get_vertices() { return vertex; }

private:
    std::vector<std::shared_ptr<Vertex>> vertex;
    std::vector<std::vector<std::shared_ptr<Vertex>>> adj;

    size_t time;
};

#endif // !GRAPH_H

Graph.cpp

#include "stdafx.h"
#include "Graph.h"
#include <iostream>
#include <queue>


void Graph::BFS(const int src) const
{
    for each (auto& u in vertex)
    {
        if (u)
        {
            u->status = Status::UNDISCOVERED;
            u->distance = INF;
            u->parent = nullptr;
        }
    }
    const auto s = vertex[src];
    s->status = Status::DISCOVERED;
    s->distance = 0;
    s->parent = nullptr;

    std::queue<std::shared_ptr<Vertex>> Q;
    Q.push(s);

    while (!Q.empty())
    {
        auto u = Q.front();
        Q.pop();

        for each (auto& v in adj[u->id])
        {
            if (v->status == Status::UNDISCOVERED)
            {
                v->status = Status::DISCOVERED;
                v->distance = u->distance + 1;
                v->parent = u;
                Q.push(v);
            }
        }
        u->status = Status::PROCESSED;
        std::cout << std::endl;
    }

}

void Graph::print_path(const int src, const int ver) const
{
    auto s = vertex[src];
    auto v = vertex[ver];

    if (s == v)
        std::cout << s->id << " -> ";
    else
    {
        if (v->parent == nullptr)
            std::cout << "* -> ";
        else
        {
            print_path(s->id, v->parent->id);
            std::cout << v->parent->id << " -> ";
        }
    }
}


void Graph::DFS()
{
    for (auto& v : vertex) {
        if (v)
        {
            v->status = Status::UNDISCOVERED;
            v->parent = nullptr;
            v->start = 0;
            v->finish = 0;
        }
    }

    for (auto& u : vertex)
    {
        if (u)
        {
            if (u->status == Status::UNDISCOVERED)
            {
                visit(u->id);
            }
        }
    }
}

void Graph::visit(const int ver)
{
    auto u = vertex[ver];
    u->status = Status::DISCOVERED;
    u->start = ++time;

    for (auto& v : adj[u->id])
    {
        if (v->status == Status::UNDISCOVERED)
        {
            visit(v->id);
        }
    }

    u->status = Status::PROCESSED;
    u->finish = ++time;
}

void Graph::add_edge(int u, int v)
{   
        if (vertex[u] == nullptr)
        {
            auto obj_u = std::make_shared<Vertex>(u);
            vertex[u] = obj_u;
        }
        if (vertex[v] == nullptr)
        {
            auto obj_v = std::make_shared<Vertex>(v);
            vertex[v] = obj_v;
        }
        //undirected graph where u->v and v->u
        adj[u].push_back(vertex[v]);
        adj[v].push_back(vertex[u]);
}

file_opener.h

#ifndef FILE_OPENER_H
#define FILE_OPENER_H
#include "Graph.h"
#include <string>

void file_to_graph(Graph&, const std::string);

#endif // !FILE_OPENER_H

file_opener.cpp

#include "file_opener.h"
#include <fstream>
#include <sstream>

void file_to_graph(Graph& G, const std::string filename)
{
    std::ifstream file_in(filename);
    std::string line;
    while (getline(file_in, line))
    {
        int u, v;
        std::istringstream iss(line);
        iss >> u;
        iss >> v;

        G.add_edge(u, v);
    }
}