6
\$\begingroup\$

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->
\$\endgroup\$
2
\$\begingroup\$

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());}
\$\endgroup\$
  • \$\begingroup\$ I don't have much experience with iterators. It seems the simplest way to add them here would be to return the iterators from the 'vertices' vector. However, the Vertex class is a private member of the Graph class so I can't refer to it in the public section. I could re-organize the header code but having the public class declarations first seems to be a common rule of thumb and makes sense to me. \$\endgroup\$ – ruslank May 26 '16 at 0:29
  • \$\begingroup\$ @ruslank: Here is an iterator that returns the indexes just like your current call to GetAllVertexIDs() It just doe's not calculate all the values up front. \$\endgroup\$ – Martin York May 26 '16 at 14:53
  • \$\begingroup\$ Thanks, this makes sense. The only part I'm unclear about is why you compare the private data member 'current' for the operator == and the actual object for operator != ? \$\endgroup\$ – ruslank May 26 '16 at 18:13
  • 1
    \$\begingroup\$ @ruslank: Basically I am defining != in terms of ==. So that if I change how the == operator works then I don't need to change the code for != it will just automatically work. \$\endgroup\$ – Martin York May 26 '16 at 20:15
2
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ It seems a little confusing to change every Vertex ID to a 'size_t' since the ID's have nothing to do with a container size (other than how they originally get their value). Is there a standard alternative? Maybe change Vertex ID to uint_64? Or static_cast to an int to be explicit that we never expect overflow to occur? Or check if (size_t > INT_MAX) and throw an exception (seems like a bit of overkill)? \$\endgroup\$ – ruslank May 25 '16 at 23:28
  • 1
    \$\begingroup\$ @ruslank The ID's are directly related to the container size, since a container's size_type alias represents the number of elements that a container supports; in your case, since every element must have a unique ID, then, in order to ensure that every element has a unique ID, the numerical ID type must be large enough to represent any number in that container. Therefore, int is clearly not enough to give out an unique ID to every element of a container that can contain a maximum of std::size_t elements. \$\endgroup\$ – user2296177 May 26 '16 at 2:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.