Object Oriented Graph Hierarchy with Depth First Search

Question

I would like to receive review on my code. It has only depth first search (DFS) and bidirected graph is the only member of the hierarchy. I added name member for the BiGraph to make it easier to debug in the future, because there might be several BiGraph instances. Also, I would like the review to primarily focus on names of the functions'. I couldn't come with better names. The last thing is performing DFS. I think there are too many indirections, so, could you please suggest some relaxations? Any other suggestions are appreciated.

The call to make DFS is achieved through calling areConnected which calls implementation. Implementation resets the history of the last DFS, and then calls traverse which actually performs DFS and fills the isvVisited bool array, which indicates all vertices which were visited.

Graph.h

#pragma once
#include <vector>

class Graph
{
public:
    Graph()=default;

    void addAdjacent(int fvertex, int svertex) { addAdjacentImpl(fvertex, svertex); }
    const std::vector<bool>&  areConnected(int sourcevertex) { return areConnectedImpl(sourcevertex); }
    void print() { printImpl(); }
    virtual ~Graph()=default;

private:
    virtual void printImpl() const = 0;
    virtual void addAdjacentImpl(int fvertex, int svertex) = 0;
    virtual const std::vector<bool>& areConnectedImpl(int sourcevertex) = 0;
    virtual void traverse(int sourcevertex) = 0;
};

BiGraph.h

#pragma once
#include "graph.h"
#include <vector>
#include <string>

class BiGraph :public Graph
{
    std::vector<std::vector<int> > graph;
    int maxVertexCount;
    std::string name;
    std::vector<bool> isVisited;
public:
    BiGraph(int maxVertexCount_, std::string name_);

    ~BiGraph();
private:
    virtual void printImpl() const override;
    virtual void addAdjacentImpl(int fVertex, int sVertex) override;
    virtual const std::vector<bool>& areConnectedImpl(int sourcevertex) override;
    virtual void traverse(int sourceVertex) override;
};

BiGraph.cpp

#include "BiGraph.h"
#include <exception>
#include <iostream>

void ZeroBoolArray(std::vector<bool>& arr)
{
    for (auto &x : arr)
    {
        x = false;
    }
}

BiGraph::BiGraph(int maxvertexcount_, std::string name_):graph(maxvertexcount_), maxVertexCount(maxvertexcount_), name(name_), isVisited(maxVertexCount)
{

}

void BiGraph::addAdjacentImpl(int fVertex, int sVertex)
{
    if (fVertex > maxVertexCount)
    {
        throw std::out_of_range(name + ": trying to add vertex which doesn't exist");
    }
    graph[fVertex].push_back(sVertex);
    graph[sVertex].push_back(fVertex);
}

void BiGraph::traverse(int sourceVertex)
{
    if (isVisited[sourceVertex])
        return;
    isVisited[sourceVertex] = true;
    for (auto& x:graph[sourceVertex])
    {
        traverse(x);
    }
}

const std::vector<bool>& BiGraph::areConnectedImpl(int sourceVertex)
{
    ZeroBoolArray(isVisited);
    traverse(sourceVertex);
    return isVisited;
}

BiGraph::~BiGraph()
{

}

void BiGraph::printImpl() const
{
    for (size_t i = 0; i < graph.size(); i++)
    {
        std::cout << i << ": ";
        for (size_t j = 0; j < graph[i].size(); j++)
        {
            std::cout << j << ' ';
        }
        std::cout << std::endl;
    }
}

GraphFactory.h

#pragma once
#include "graph.h"
#include <memory>
#include <string>

class GraphFactory
{
public:
    GraphFactory()=default;

    std::unique_ptr<Graph> getBiGraph(int size, std::string name);

    ~GraphFactory()=default;
};

GraphFactory.cpp

#include "GraphFactory.h"
#include "BiGraph.h"

std::unique_ptr<Graph> GraphFactory::getBiGraph(int size, std::string name)
{
    return std::make_unique<BiGraph>(size, name);
}

Answer 1

General

Depth first search generally applies to trees (because it has a depth, no cycles). You have implemented a general purpose graph (which can contain cycles and thus is not a tree (and does not have a depth).

Code Review

Pragmas are compiler specific. They are fine if you use them taking this into context.

#pragma once

This pragma is basically useless as it is non portable. Use the appropriate include guards unless you want to be locked into your current compiler only.

Not sure why you need to make isVisitied a member.

class BiGraph :public Graph
{
    std::vector<bool> isVisited;

The only reason you seem to need it was because areConnected() returns it by reference.

const std::vector<bool>&  areConnected(int sourcevertex)

I assume you did this to save the cost of copying the vector out. This is a false optimization. C++ is highly optimized and it is unlikely that a return by value would be copied out. The compiler has aggrissive RVO/NRVO optimization that would build the result at the destionation. In C++11 move semantics are introduced and compliment the RVO/NRVO optimization and in the few cases were they can not be built in place move semantics kick in and the content is moved optimally out of the method.

So declare this function

const std::vector<bool>  areConnected(int sourcevertex) const;

The specialization std::vector<bool> is broadly considered a mistake. It is optimized for size (unlike nearly everything else in C++ which is optimized for speed).

Because it optimized for size it has several drawbacks and does not act like a normal std::vector<> (which is why it is normally avoided). Now if you think you need to optimize for size then fair enough but normally people prefer to use std::vector<char>

Simpler Issues

Sure.

void ZeroBoolArray(std::vector<bool>& arr)

But if you fix the code as I suggeste above you don't need this function.

There is a simpler way to write this:

for (auto &x : arr)
{
    x = false;
}

// Easier to write as:
x = std::vector<bool>(x.size());   // Might be slightly more expensive.

Please one variable per line. This includes initializee list.

// This is unreadable
BiGraph::BiGraph(int maxvertexcount_, std::string name_):graph(maxvertexcount_), maxVertexCount(maxvertexcount_), name(name_), isVisited(maxVertexCount)
{

}

// Rewrite as:
BiGraph::BiGraph(int maxvertexcount_, std::string name_)
    : graph(maxvertexcount_)
    , maxVertexCount(maxvertexcount_)
    , name(name_)
    , isVisited(maxVertexCount)
{}
// PS I hate the trailing `_` there is no need to have it.
// If you re-write as:
BiGraph::BiGraph(int maxvertexcount, std::string name)
    : graph(maxvertexcount)
    , maxVertexCount(maxvertexcount)
    , name(name)
    , isVisited(maxVertexCount)
{}
// this works just as well and is unambiguous.

Why only check fVertex?

void BiGraph::addAdjacentImpl(int fVertex, int sVertex)
{
    if (fVertex > maxVertexCount)
    {
        throw std::out_of_range(name + ": trying to add vertex which doesn't exist");
    }

You should probably also check sVertex. But unless you explicitly want that error message you don't need the test; just use at() method.

void BiGraph::addAdjacentImpl(int fVertex, int sVertex)
{
    graph.at(fVertex).push_back(sVertex);
    graph.at(sVertex).push_back(fVertex);
}

Also you don't check if the vertex has already been added.

Sure this works fine. But it would be better to use the Visitor Pattern.

void BiGraph::traverse(int sourceVertex)

We covered this function above:

const std::vector<bool>& BiGraph::areConnectedImpl(int sourceVertex)

// I would write as:
const std::vector<char> BiGraph::areConnectedImpl(int sourceVertex) const
{
    std::vector<char>  isVisited.
    traverse(sourceVertex, isVisited);
    return isVisited;
}

If your destructor does nothing then don't declare it. The compiler generated version will work perfectly well.

BiGraph::~BiGraph()

Sure: This printImpl() seems easy enough. But it could be improved.

void BiGraph::printImpl() const

Rather than assume you will print to std::cout take a parameter for the output stream to be used. It can default to std::cout but this gives you the flexability to use other streams (like files/string streams etc).

Also in C++ it is standard to define an output operator to print an object.

Prefer "\n" over std::endl. The std::endl will also flush the stream which will usually make the code sub optimal. The stream is already flushed automatically if needed and if not needed will flush at optimal points so there is no need to manually force a flush.

Prefer the range based for loop if you don't need the index (currently your j loop is wrong (you should print the value at each index).

void BiGraph::printImpl(std::ostream& str = std::cout) const
{
    for (size_t i = 0; i < graph.size(); i++)
    {
        str << i << ": ";
        for (auto j: graph[i])
        {
            str << j << ' ';
        }
        str << "\n";
    }
}
std::ostream& operator<<(std::ostream^ str, Graph const& g)
{
    g.print(str);
    return str;
}

Answer 2

I really don't see what this gives you:

void addAdjacent(int fvertex, int svertex) { addAdjacentImpl(fvertex, svertex); }

Compared to just do:

virtual void addAdjacent(int f, int s) = 0;

Doing so would reduce one level of indirection, while implementing the interface would be the same amount of work.

Apart from that I think your code looks quite good.