Object Oriented Graph Hierarchy with Depth First Search revisited

Question

This question is follow up to Object Oriented Graph Hierarchy with Depth First Search. I tried to fulfill every point which @LokiAstari mentioned. I think I succeeded in everything except Visitor Pattern.

I came to implementation of a function void BiGraph::addAdjacentImpl(int fVertex, int sVertex) in different way. Now it will do very heavy checks. Hope I didn't miss something. Also, I implemented check for keeping being a tree with ad-hoc approach (not sure about it). Every time edge is to be added, it is added only one way, and then traverse is called to check if cycle will be created or not, so it is kind of online check. Could you please pay extra attention to this function and criticize it as much as possible, because it is very essential part.

Graph.cpp is the outcome of complains of linker. Seems like inlining of print function call made the complains. The file implements only operator<<s, so if clients write their own non-virtual functions I think it doesn't violate ODR which is ok, I hope I'm not missing anything. Also I made heavy unit test, but it is just a bunch of try catch statements, everything was executed in a way it was waited to.

Graph.h

#ifndef GRAPH_H
#define GRAPH_H
#include <memory>
#include <vector>
#include <iostream>

class Graph
{
public:
    void addAdjacent(int fVertex, int sVertex) { addAdjacentImpl(fVertex, sVertex); }
    const std::vector<char>  areConnected(int sourceVertex) const { return areConnectedImpl(sourceVertex); }
    void print(std::ostream& os) const { printImpl(os); }
private:
    virtual void printImpl(std::ostream& os) const = 0;
    virtual void addAdjacentImpl(int fvertex, int svertex) = 0;
    virtual const std::vector<char> areConnectedImpl(int sourcevertex) const = 0;
    virtual void traverse(int sourcevVertex, std::vector<char>& areVisited) const = 0;
};

std::ostream& operator<<(std::ostream& os, Graph* g);

std::ostream& operator<<(std::ostream& os, const std::unique_ptr<Graph>& g);

std::ostream& operator<<(std::ostream& os, const std::shared_ptr<Graph>& g);
#endif 

Graph.cpp

#include "graph.h"

std::ostream& operator<<(std::ostream& os, Graph* g)
{
    g->print(os);
    return os;
}

std::ostream& operator<<(std::ostream& os, const std::unique_ptr<Graph>& g)
{
    g->print(os);
    return os;
}

std::ostream& operator<<(std::ostream& os, const std::shared_ptr<Graph>& g)
{
    g->print(os);
    return os;
}

BiGraph.h

#ifndef BIGRAPH_H
#define BIGRAPH_H

#include "graph.h"
#include <map>
#include <vector>
#include <string>
#include <iostream>

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

private:
    virtual void printImpl(std::ostream& os) const override;
    virtual void addAdjacentImpl(int fVertex, int sVertex) override;
    virtual const std::vector<char> areConnectedImpl(int sourcevertex) const override;
    virtual void traverse(int sourceVertex, std::vector<char>& areVisited) const override;
};

#endif

BiGraph.cpp

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

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

}

void BiGraph::addAdjacentImpl(int fVertex, int sVertex)
{
    if (fVertex == sVertex)
    {
        throw std::logic_error(name + ": Trying to add a loop");
    }

    if (fVertex <0 || fVertex > maxVertexCount)
    {
        throw std::out_of_range(name + ": trying to add non-existent vertex");
    }
    if (sVertex < 0 || sVertex > maxVertexCount)
    {
        throw std::out_of_range(name + ": trying to add non-existent vertex");
    }

    std::vector<int>::const_iterator cit;
    cit = std::find(graph[fVertex].cbegin(), graph[fVertex].cend(), sVertex);
    if (cit != graph[fVertex].cend())
    {
        throw std::logic_error(name + ": Connecting these vertices will make the graph no longer tree");
    }

    cit = std::find(graph[sVertex].cbegin(), graph[sVertex].cend(), fVertex);
    if (cit != graph[sVertex].cend())
    {
        throw std::logic_error(name + ": Connecting these vertices will make the graph no longer tree");
    }

    graph[fVertex].push_back(sVertex);

    std::vector<char> areVisited(maxVertexCount, false);

    traverse(sVertex, areVisited);

    if (areVisited[fVertex])
    {
        graph[fVertex].pop_back();
        throw std::logic_error(name + ": Connecting these vertices will cause a cycle");
    }

    graph[sVertex].push_back(fVertex);

}

void BiGraph::traverse(int sourceVertex, std::vector<char>& areVisited) const
{
    if (areVisited[sourceVertex])
        return;
    areVisited[sourceVertex] = true;
    for (auto& x:graph[sourceVertex])
    {
        traverse(x, areVisited);
    }
}

const std::vector<char> BiGraph::areConnectedImpl(int sourceVertex) const
{
    std::vector<char> areVisited(maxVertexCount, false);
    traverse(sourceVertex, areVisited);
    return areVisited;
}

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

GraphFactory.h

#ifndef GRAPHFACTORY_H
#define GRAPHFACTORY_H
#include "graph.h"
#include <memory>
#include <string>

class GraphFactory
{
public:
    GraphFactory()=default;

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

    ~GraphFactory()=default;
};

#endif

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

I will review your code independently; if you get conflicting recommendations from other reviews, use your judgement to reconcile them.

It's OK to have virtual functions in the public interface.

class Graph
{
public:
    void addAdjacent(int fVertex, int sVertex) { addAdjacentImpl(fVertex, sVertex); }
    const std::vector<char>  areConnected(int sourceVertex) const { return areConnectedImpl(sourceVertex); }
    void print(std::ostream& os) const { printImpl(os); }
};

This code has no purpose: you are not adding any context and they just add unnecessary indirection. The optimizer will probably optimize it away, but I see no sense in having this code.

Pointers in stream operators are not the best idea.

std::ostream& operator<<(std::ostream& os, Graph* g)
{
    g->print(os);
    return os;
}

std::ostream& operator<<(std::ostream& os, const std::unique_ptr<Graph>& g)
{
    g->print(os);
    return os;
}

std::ostream& operator<<(std::ostream& os, const std::shared_ptr<Graph>& g)
{
    g->print(os);
    return os;
}

You probably should just use constant references instead of pointers. This is the canonical stream operator and adding pointers is just a special case. You can always dereference the pointer in the calling code (unless you intend to print the pointer address too).

If you are passing in pointers, you should probably check whether the pointers are not null. This can either be an assert or a throw std::invalid_argument.

Override is sufficient.

class BiGraph
{
  virtual void printImpl(std::ostream& os) const override;
}

Just use override, since virtual is implied here. As a rule of thumb use virtual at the base to indicate a virtual function and use override on the derived functions.

Prefer assert to handle programming mistakes.

void BiGraph::addAdjacentImpl(int fVertex, int sVertex)
{
    if (fVertex == sVertex)
    {
        throw std::logic_error(name + ": Trying to add a loop");
    }

    if (fVertex <0 || fVertex > maxVertexCount)
    {
        throw std::out_of_range(name + ": trying to add non-existent vertex");
    }
    if (sVertex < 0 || sVertex > maxVertexCount)
    {
        throw std::out_of_range(name + ": trying to add non-existent vertex");
    }
}

All things that can be considered "programming" mistakes should be checked against with asserts. The problem is, if this is a programming mistake, what can the calling code do about it? If this is some source of input, that input should have been validated at a higher level.

If the (fVertex == sVertex) is within the realm of normal operations, it probably should a different exception than logic_error.

Use bool for boolean values.

void BiGraph::traverse(int sourceVertex, std::vector<char>& areVisited) const
{
    if (areVisited[sourceVertex])
        return;
    areVisited[sourceVertex] = true;
    for (auto& x:graph[sourceVertex])
    {
        traverse(x, areVisited);
    }
}

You are clearly using areVisited as a boolean; then the type should be std::vector<bool>.

Use a single function where possible

void BiGraph::traverse(int sourceVertex, std::vector<char>& areVisited) const
{
    if (areVisited[sourceVertex])
        return;
    areVisited[sourceVertex] = true;
    for (auto& x:graph[sourceVertex])
    {
        traverse(x, areVisited);
    }
}

const std::vector<char> BiGraph::areConnectedImpl(int sourceVertex) const
{
    std::vector<char> areVisited(maxVertexCount, false);
    traverse(sourceVertex, areVisited);
    return areVisited;
}

areConnectedImpl is implemented in terms of traverse; maybe you can reconcile the functions to only have one way to do this.

Use std::endl only if you need a flush

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

std::endl will always also call flush, which is really slow. If you are printing lots of elements, consider just using '\n' instead.

class GraphFactory
{
public:
    GraphFactory()=default;
    ~GraphFactory()=default;
};

If your class adheres to the Rule of Zero, don't add defaulted constructors and destructors. Although technically GraphFactory does, semantically I think a factory should not be copyable. In that case remove the copy constructor and assignment operator.

If the factory class does nothing, consider using a factory function.

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

This function does not do much. The calling code could probably just call make_unique on its own. If you really want to hide the BiGraph class, you can provide a simple function, without the factory.

The inheritance hierarchy does not pull its own weight.

This code looks unnecessarily "object oriented" (in the Java sense). This could be just one class and everybody, including the compiler, would be happy. C++ is good at creating small code if you let it. There may be good reasons to do what you did with the factory and implementation hiding, but unless there is more and a higher goal, this makes no sense.