C++ Graph Class Implementation (adjacency list)

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 // std::pair
#include
#include

template
class Graph
{
public:
Graph(bool directed = false) : directed(directed) {}

int AddVertex(T value);
std::pair 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 GetAllVertexIDs() const;
// BFS returns vector pair
std::pair, std::vector> BreadthFirstSearch(int start_id) const;
std::vector DepthFirstSearch(int start_id, bool recursive = false) const;

template
friend std::ostream & operator & g);

private:
class Vertex; // forward declare;

std::vector vertices;
const bool directed;
void DepthFirstSearchRecursive(int vertex_id, std::vector & visit_order,
std::vector & 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 Get

Overflow/narrowing conversion bug

Your Vertex ID type is int, yet you assign from vertices.size() which returns std::vector::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::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::size_type).

StackExchange Code Review Q#129143, answer score: 2