C++ Graph Class Implementation (adjacency list)

Question

I've got a barebones C++ graph class implemented as an adjacency list. The graph consists of a vector of vertices. Each vertex has a vector of outgoing edges that store the destination vertex id. Vertex ids are just 'int's, incremented each time a new vertex is added to the graph.

This code is mostly for practice as I prep for interviews. I have some code for edge costs that will be used to implement Dijkstra's algorithm later but it can be ignored.

I welcome any feedback, but was hoping to hear about:

• Overall OOP design and encapsulation
• Clean/elegant way to remove vertices from the graph
• Manual memory allocation (I avoided since it didn't seem necessary)
• Splitting up the class definitions/implementations for a templated class

graph.h:

#ifndef GRAPH_H
#define GRAPH_H

#include <utility> // std::pair
#include <ostream>
#include <vector>

template <typename T>
class Graph
{
    public:
        Graph(bool directed = false) : directed(directed) {}

        int AddVertex(T value);
        std::pair<int, int> AddEdgeAndVertices(T start_value, T end_value, int cost = 0);
        void AddEdge(int start_id, int end_id, int cost = 0);
        int VertexCount() const;
        const T & GetVertexData(int vertex_id) const;
        std::vector<int> GetAllVertexIDs() const;
        // BFS returns vector pair <vertex_id, parent of this vertex>
        std::pair<std::vector<int>, std::vector<int>> BreadthFirstSearch(int start_id) const;
        std::vector<int> DepthFirstSearch(int start_id, bool recursive = false) const;

        template <typename U>
        friend std::ostream & operator<<(std::ostream & out, Graph<U> & g);

    private:
        class Vertex; // forward declare;

        std::vector<Vertex> vertices;
        const bool directed;
        void DepthFirstSearchRecursive(int vertex_id, std::vector<int> & visit_order,
                std::vector<bool> & visited) const;
        void Print(std::ostream & out) const;

        class OutEdge
        {
            public:
                OutEdge(int end_id, int cost): dest_id(end_id), cost(cost) {}
                const int GetDestID() const;
                const int GetCost() const;

            private:
                int dest_id;
                int cost;
        };

        class Vertex
        {
            public:
                Vertex(int id, T value): id(id), data(value) {}
                void AddEdge(int end_id, int cost);
                const T & GetData() const;
                const std::vector<OutEdge> & GetOutgoingEdges() const;

            private:
                int id; // unique identifier
                T data; 
                std::vector<OutEdge> outgoing_edges;
        };

};

#include "graph.cpp"

#endif

graph.cpp:

#include <cassert>
#include <queue> // for Breadth First Search
#include <stack> // for Depth First Search

template <typename T>
int Graph<T>::AddVertex(T value)
{
    int id = VertexCount(); // id is the index into vertices array
    vertices.push_back(Vertex(id, value));
    return id;
}

template <typename T>
std::pair<int, int> Graph<T>::AddEdgeAndVertices(T start_value, T end_value, int cost)
{
    int start_id = AddVertex(start_value);
    int end_id = AddVertex(end_value);
    AddEdge(start_id, end_id, cost);
    return std::pair<int, int> (start_id, end_id);
}

template <typename T>
void Graph<T>::AddEdge(int start_id, int end_id, int cost)
{
    assert(start_id >= 0 && start_id < VertexCount());
    assert(end_id >= 0 && end_id < VertexCount());
    vertices[start_id].AddEdge(end_id, cost);
    if (!directed)
        vertices[end_id].AddEdge(start_id, cost);
}

template <typename T>
int Graph<T>::VertexCount() const
{
    return vertices.size();
}

template <typename T>
const T & Graph<T>::GetVertexData(int vertex_id) const
{
    return vertices[vertex_id].GetData();
}

template <typename T>
std::vector<int> Graph<T>::GetAllVertexIDs() const
{
    std::vector<int> vertex_ids(VertexCount());
    for (size_t i = 0; i < vertex_ids.size(); ++i)
        vertex_ids[i] = i;
    return vertex_ids;
}

template <typename T>
std::pair<std::vector<int>, std::vector<int>> Graph<T>::BreadthFirstSearch(int start_id) const
{
    std::vector<int> parent(VertexCount(), -1);
    std::vector<int> vertex_ids(VertexCount(), -1);
    std::vector<bool> visited(VertexCount(), false);

    std::queue<int> q; // holds vertex ids still to be explored
    q.push(start_id);
    int index = 0;
    vertex_ids[index++] = start_id;
    parent[start_id] = -1;
    visited[start_id] = true;

    while (!q.empty())
    {
        int id = q.front();
        q.pop();
        // process vertex here if desired
        for (const OutEdge e : vertices[id].GetOutgoingEdges())
        {
            int neighbor_id = e.GetDestID();
            if (!visited[neighbor_id])
            {
                visited[neighbor_id] = true;
                vertex_ids[index++] = neighbor_id;
                parent[neighbor_id] = id;
                q.push(neighbor_id);
            }
        }
    }
    return std::make_pair(vertex_ids, parent);
}

template <typename T>
std::vector<int> Graph<T>::DepthFirstSearch(int start_id, bool recursive) const
{
    std::vector<bool> visited(VertexCount(), false);

    // Recursive implementation
    if (recursive)
    {
        std::vector<int> visit_order_recursive;
        DepthFirstSearchRecursive(start_id, visit_order_recursive, visited);
        return visit_order_recursive;
    }

    // Iterative implementation
    std::vector<int> visit_order(VertexCount(), -1);
    std::stack<int> s; // holds vertex ids still to be explored
    s.push(start_id);

    int index = 0;
    while (!s.empty())
    {
        int id = s.top();
        s.pop();
        if (!visited[id])
        {
            visited[id] = true;
            visit_order[index++] = id;
            for (const OutEdge e : vertices[id].GetOutgoingEdges())
            {
                int neighbor_id = e.GetDestID();
                s.push(neighbor_id);
            }
        }
    }
    return visit_order;
}

template <typename T>
std::ostream & operator<<(std::ostream & out, Graph<T> & g)
{
    g.Print(out);
    return out;
}

template <typename T>
void Graph<T>::DepthFirstSearchRecursive(int vertex_id, std::vector<int> & visit_order, 
        std::vector<bool> & visited) const
{
    visited[vertex_id] = true;
    visit_order.push_back(vertex_id); // pre-order
    for (const OutEdge e : vertices[vertex_id].GetOutgoingEdges())
    {
        int neighbor_id = e.GetDestID();
        if (!visited[neighbor_id])
            DepthFirstSearchRecursive(neighbor_id, visit_order, visited);
    }
    // post-order visit would go here
}


template <typename T>
void Graph<T>::Print(std::ostream & out) const
{
    out << "V = ";
    for (const Vertex v : vertices)
        out << v.GetData() << " ";
    out << "\n";
    out << "E = ";
    for (const Vertex v : vertices)
    {
        out << "[" << v.GetData() << ":";
        for (const OutEdge e : v.GetOutgoingEdges())
        {
            out << " " << vertices[e.GetDestID()].GetData();
        }
        out << "] ";
    }
    out << "\n";

}

template <typename T>
const int Graph<T>::OutEdge::GetDestID() const
{
    return dest_id;
}

template <typename T>
const int Graph<T>::OutEdge::GetCost() const
{
    return cost;
}

template <typename T>
void Graph<T>::Vertex::AddEdge(int end_id, int cost)
{
    outgoing_edges.push_back(OutEdge(end_id, cost));
}

template <typename T>
const T & Graph<T>::Vertex::GetData() const
{
    return data;
}

template <typename T>
const std::vector<typename Graph<T>::OutEdge> & Graph<T>::Vertex::GetOutgoingEdges() const
{
    return outgoing_edges;
}

Some basic testing in test_graph.cpp:

#include <utility> // std::pair
#include <iostream>
#include <string>
#include <vector>
#include "graph.h"

int main()
{
    // Using graph from Wikipedia entry on DFS: 
    // https://en.wikipedia.org/wiki/Depth-first_search
    Graph<std::string> g;

    std::pair<int, int> ids_A_B = g.AddEdgeAndVertices("A", "B");
    std::pair<int, int> ids_C_G = g.AddEdgeAndVertices("C", "G");
    std::pair<int, int> ids_E_F = g.AddEdgeAndVertices("E", "F");
    int id_D = g.AddVertex("D");

    g.AddEdge(ids_A_B.first, ids_C_G.first); // A<-->C
    g.AddEdge(ids_A_B.first, ids_E_F.first); // A<-->E
    g.AddEdge(ids_A_B.second, id_D); // B<-->D
    g.AddEdge(ids_A_B.second, ids_E_F.second); // B<-->F

    std::cout << "str graph:\n";
    std::cout << g;

    // Breadth first search
    std::pair<std::vector<int>, std::vector<int>> vertex_parents = 
        g.BreadthFirstSearch(ids_A_B.first);

    int first_vertex = vertex_parents.first[0]; // starting ID
    std::cout << "\nBFS starting at vertex " << g.GetVertexData(ids_A_B.first) << ":\n";
    for (size_t i = 0; i < vertex_parents.first.size(); ++i)
    {
        int curr_vertex = vertex_parents.first[i];
        int distance = 0;
        while (curr_vertex != first_vertex)
        {
            std::cout << g.GetVertexData(curr_vertex) << "->";
            curr_vertex = vertex_parents.second[curr_vertex];
            ++distance;
        }
        std::cout << g.GetVertexData(first_vertex) << ", distance = " << distance << "\n";
    }

    // Depth first search
    std::vector<int> visit_order = g.DepthFirstSearch(ids_A_B.first, true);
    std::cout << "\nDFS starting at vertex " << g.GetVertexData(ids_A_B.first) << ":\n";
    for (int vertex_id : visit_order)
        std::cout << g.GetVertexData(vertex_id) << "->";
    std::cout << "\n";
}

The result is:

str graph:
V = A B C G E F D 
E = [A: B C E] [B: A D F] [C: G A] [G: C] [E: F A] [F: E B] [D: B] 

BFS starting at vertex A:
A, distance = 0
B->A, distance = 1
C->A, distance = 1
E->A, distance = 1
D->B->A, distance = 2
F->B->A, distance = 2
G->C->A, distance = 2

DFS starting at vertex A:
A->B->D->F->E->C->G->

Answer 1

Interface

Your interface locks you into certain design decisions.

std::vector<int> GetAllVertexIDs() const;

Why return a verctor of all the node ID(s)? A more classic approach would be to return an iterator that allows you to iterate over all the nodes.

I am not sure what a depth or a breadth first search of a graph mean?

std::pair<std::vector<int>, std::vector<int>> BreadthFirstSearch(int start_id) const;
std::vector<int> DepthFirstSearch(int start_id, bool recursive = false) const;

Also why are they returning different things? I would expect any type of search to return the same thing. Otherwise how can I write generic code that searches for stuff and be expected to swap one search function for another?

Pass vertex data by reference (or R-Value reference) to prevent excessive copying.

int AddVertex(T value);

// I would have written three versions of this.
int addVertex(T const& value);         // Copy value into Graph
int addVertex(T&& value);              // Move value into Graph
template<typename... Args>
int emplaceVertex(Args... args);       // Construct in place in Graph

Accessing the data of a vertex via a reference. You do fine, but most containers allow you to mutate the date via the reference. So usually you see two versions of this method:

const T & GetVertexData(int vertex_id) const;

// Unless the graph data should be immutable I would have added:
T const& getVertexData(int vertex_id) const;
T&       getVertexData(int vertex_id);

A bit more white space in the class declaration to make it more readable would have been nice.

template <typename T>
class Graph
{
    public:
        using InsertPair = std::pair<int, int>;

        Graph(bool directed = false) : directed(directed) {}

        int      VertexCount() const;
        int      AddVertex(T const& value);
        T const& GetVertexData(int vertex_id) const;

        void       AddEdge(int start_id, int end_id, int cost = 0);
        InsertPair AddEdgeAndVertices(T const& start_value, T const& end_value, int cost = 0);


        std::vector<int> GetAllVertexIDs() const;

        // BFS returns vector pair <vertex_id, parent of this vertex>
        std::pair<std::vector<int>, std::vector<int>> BreadthFirstSearch(int start_id) const;
        std::vector<int> DepthFirstSearch(int start_id, bool recursive = false) const;


        template <typename U>
        friend std::ostream & operator<<(std::ostream & out, Graph<U> & g);

Naming conventions

There is no standard.
But a common convention is:

1. User defined types have an initial upper case letter.
2. Objects (variables/methods/functions) have an initial lower case letter.

File Names

You have split the declaration and definition of your template class into two files (which is fine). But the definition is in a *.cpp file.

A more common convention is to use *.tpp file for the definition. When your code gets installed on other people systems you will then not be installing *.cpp files (which would look strange).

Code Review

As mention above pass objects by const reference when possible to avoid copying.

template <typename T>
int Graph<T>::AddVertex(T value)  // Copy to here that is not needed.
{
    int id = VertexCount(); // id is the index into vertices array
    vertices.push_back(Vertex(id, value));
    return id;
}

Avoid comments that should be obvious from reading the code.

int id = VertexCount(); // id is the index into vertices array

There is already a function that does this:

    return std::pair<int, int> (start_id, end_id);

    // Easier to write:
    return std::make_pair(start_id, end_id);

Avoid this kind of assert.

template <typename T>
void Graph<T>::AddEdge(int start_id, int end_id, int cost)
{
    assert(start_id >= 0 && start_id < VertexCount());
    assert(end_id >= 0 && end_id < VertexCount());

When you compile this code for production then these assert's disappear (ie they become noops). So they provide no real protection.

The assert should be used to validate that internal state of your object is consistent. Then your test code should try and throw all sorts of data through the public API to make sure the object can not be put in an inconsistent state.

Here you are validating user input. This is not the kind of data that should be evaluated by assert. You can not test all code that uses your code in a testing environment so these assert's provide no real protection. So either do real tests that throw or do no tests and define the contract and assume the user stays within the contract.

Example:

 std::vector::at(std::size_t index); // Throws if index is out of range.
 std::vector::operator[](std::size_t index); // Does nothing.
                                             // It assumes user has already
                                             // validated the input
                                             // and obeys the contract.

This is doing a lot of work. That may just be discarded by the caller after looking at a few nodes. Also it may become invalid very quickly if the graph is mutated and need to be regenerated.

template <typename T>
std::vector<int> Graph<T>::GetAllVertexIDs() const
{
    std::vector<int> vertex_ids(VertexCount());
    for (size_t i = 0; i < vertex_ids.size(); ++i)
        vertex_ids[i] = i;
    return vertex_ids;
}

I would return an iterator (they are cheap to construct). If the graph is mutated then creating another is not an issue. Also you make it return the id or a reference to the object (whichever suits your use case best).

Visitor pattern

I would look into the visitor pattern for doing graph traversal.

A Graph Iterator

Here is an iterator to iterator across the Verticies in your graph (should be declared as a public member of Graph):

class GraphIterator
{   
    public:
        typedef std::input_iterator_tag     iterator_category;
        typedef int                         value_type;
        typedef std::size_t                 difference_type;
        typedef int*                        pointer;
        typedef int&                        reference;

        GraphIterator(int value) :current(value){}

        // Pre Increment
        GraphIterator & operator++()               {++current;return *this;}
        // Post increment
        GraphIterator operator++(int)             {return GraphIterator(current++);}

        // De-Reference
        value_type operator*() const            {return current;}

        bool operator==(GraphIterator const& rhs) {return current == rhs.current}
        bool operator!=(GraphIterator const& rhs) {return !((*this) == rhs);}
    private:
        int current;
};
GraphIterator begin() const {return GraphIterator(0);}
GraphIterator end()   const {return GraphIterator(vertices.size());}

Answer 2

Overflow/narrowing conversion bug

Your Vertex ID type is int, yet you assign from vertices.size() which returns std::vector<Vertex>::size_type; normally this is an alias for a 32-bit or a 64-bit unsigned integer for x86 and x64, respectively.

Thus, your Vertex ID type should be std::vector<Vertex>::size_type in order to prevent overflow/narrowing conversions.

Non-unique ID assignment bug

Once you add removal operations, calling vertices.size() to get an ID will lead to bugs. This pseudo-code should make it clear:

vertex a = graph.add(...); // assigned 0 as vertex id
vertex b = graph.add(...); // assigned 1 as vertex id
graph.erase( a ); // vertices.size() will now return 1
vextex c = graph.add(...); // assigned 1 as vertex id, error: b.id == c.id

As a possible solution, you can implement a small id_provider type that takes care of giving out unique id types. On destruction, id type instances can give back their id value to the id_provider that originally created them so that you can represent the whole range of values of the backing id value type (such as std::vector<Vertex>::size_type).