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 encapsulationClean/elegant way to remove vertices from the graphManual memory allocation (I avoided since it didn't seem necessary)Splitting up the class definitions/implementations for a templated classgraph.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#endifgraph.cpp:#include <cassert>#include <queue> // for Breadth First Search#include <stack> // for Depth First Searchtemplate <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.hint 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 = 0B->A, distance = 1C->A, distance = 1E->A, distance = 1D->B->A, distance = 2F->B->A, distance = 2G->C->A, distance = 2DFS starting at vertex A:A->B->D->F->E->C->G->
C++ Graph Class Implementation (adjacency list)
c++;interview questions;graph;depth first search;breadth first search
InterfaceYour 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 Graphint addVertex(T&& value);              // Move value into Graphtemplate<typename... Args>int emplaceVertex(Args... args);       // Construct in place in GraphAccessing 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 conventionsThere is no standard.But a common convention is:User defined types have an initial upper case letter.Objects (variables/methods/functions) have an initial lower case letter.File NamesYou 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 ReviewAs 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 arrayThere 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 patternI would look into the visitor pattern for doing graph traversal.A Graph IteratorHere 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        CSVIterator& operator++()               {++current;return *this;}        // Post increment        CSVIterator operator++(int)             {return GraphIterator(current++);}        // De-Reference        value_type operator*() const            {return current;}        bool operator==(CSVIterator const& rhs) {return current == rhs.current}        bool operator!=(CSVIterator const& rhs) {return !((*this) == rhs);}    private:        int current;};GraphIterator begin() const {return GraphIterator(0);}GraphIterator end()   const {return GraphIterator(vertices.size());}