Graph data structure implementation

I just started using C++, and I was wondering if my code fits the standards so far. Specifically, I was wondering if I did the addEdge, isConnected, and getShortestPathForm methods correctly. For instance, are the parameters correct as Vector &v or should it be Vector *v or Vector v?

```
//Graph.h
#ifndef GRAPH_H
#define GRAPH_H

#include
#include
#include

template
class Graph;

template
class Vertex;

template
class Neighbor {
friend class Vertex;
friend class Graph;

private:
int vertexIndex;
Neighbor *next;
public:
Neighbor(int vIndex, Neighbor *n) : vertexIndex(vIndex), next(n) {}
};

template
class Vertex {
friend class Graph;

private:
T data;
int index;
Neighbor *adjLL;
public:
Vertex(const T &val, const int i) : data(val), index(i), adjLL(NULL) {}
};

typedef enum GraphType {
GraphTypeDirected,
GraphTypeUndirected
} GraphType;

template
class Graph {
private:
std::vector > vertices;
GraphType graphType;
int counter;

public:
Graph(const GraphType type) : graphType(type), counter(0) {}
Graph(const Graph &);
Vertex *addVertex(const T &);
void addEdge(Vertex &, Vertex &);
bool isConnected(const Vertex &, const Vertex &);
std::string getShortestPathFrom(Vertex &, Vertex &);
};

template
Vertex *Graph::addVertex(const T &data)
{
Vertex *v = new Vertex(data, counter++);
vertices.push_back(*v);

return v;
}

template
void Graph::addEdge(Vertex &v1, Vertex &v2)
{
Neighbor *adjLL1 = v1.adjLL;
Neighbor *adjLL2 = v2.adjLL;

v1.adjLL = new Neighbor(v2.index, v1.adjLL);
v2.adjLL = new Neighbor(v1.index, v2.adjLL);
vertices.at(v1.index) = v1;
vertices.at(v2.index) = v2;
}

template
bool Graph::isConnected(const Vertex &v1, const Vertex &v2)
{
Neighbor *curr = v1.adjLL;

while (curr != NULL) {
if (curr->vertexIndex == v2.index)

In general, your code has too much dynamic allocation going on. C++ is not garbage collected - when you call new, it must have a corresponding delete somewhere to free that memory. At the moment, your code is leaking memory all over the place.

Let's go through them and see what can be tidied up:

template 
Vertex *Graph::addVertex(const T &data)
{
    Vertex *v = new Vertex(data, counter++);
    vertices.push_back(*v);

    return v;
}

Internally, you're storing a vector of Vertex, so there is no real reason to call new here.

template 
Vertex& Graph::addVertex(const T& data)
{
    vertices.push_back(Vertex(data, counter++));
    return vertices.back();
}

In your Vertex class, you're building up a linked list of Neighbour manually by having a pointer to the start of the linked list, and then having Neighbour use a *next pointer within it. This seems to be a rather complicated way of storing adjacent vertices. Personally, I don't see much point in even having the Neighbour class: for each Vertex, you can store the set of adjacent vertices directly. Since these are presumably all unique, you can use a std::set (this will have benefits in isConnected, as we'll see soon).

template 
class Vertex {
    friend class Graph;

    private:
        T data;
        int index;
        std::set vertexIndices;
    public:
        Vertex(const T &val, const int i) : data(val), index(i) { }
        void addIndex(int vertex);
};

template 
void Vertex::addIndex(int vertex)
{
    vertexIndices.insert(vertex);
}

Your nomenclature for isConnected is non-standard. What you are actually checking is if a given vertex is directly adjacent to another vertex. In general, in a graph, two vertices are considered connected if there exists some path between them. There are two general methods of finding this: breadth first and depth first search (which appears to be sort of what your getShortestPathFrom function is doing). However, to implement your current isConnected check, we can simply do:

template 
bool Graph::isConnected(const Vertex &v1, const Vertex &v2)
{
    auto it = v1.vertexIndices.find(v2.index);
    return it != v1.vertexIndices.end();
}

I would suggest renaming this to isAdjacent or something similar.

There's another big oversight in your current code: you have an enum GraphType that you specify, however, this does not change the behaviour of your class. Even if the user specifies a directed graph, your current addEdge implementation will add edges in an undirected manner.
Generally, if you want to modify class behaviour in this way, it is better to make a separate class - so DirectedGraph and UndirectedGraph. Controlling the behaviour of a class based upon an enum is generally not good practice, as it makes the code harder to reason about, and harder to modify in the future.

That having been said, the modified addEdge function for an undirected graph could look something like:

template 
void Graph::addEdge(Vertex &v1, Vertex &v2)
{
    v1.addIndex(v2.index);
    v2.addIndex(v1.index);
}

You getShortestPathFrom function shouldn't return a string. I realise you're trying to get around the fact that it might not be there, but there are better ways of going about this. The easiest is to return some kind of value indicating "not found", like -1. This function again leaks memory with the call to new bool[...]. Further, it has some quite odd behaviour:

• It compares data for equality instead of vertex indices. What if multiple vertices have the same data? This will then give the wrong result.

• It assumes the template parameter is an, as seen by the printf("%d\n", ...) call, which somewhat defeats the purpose of using a template parameter.

• It gets the wrong answer! Your example code when run prints "10 25 20" which is v1 -> v4 -> v3, however you insert a direct link between v1 -> v3 with the call graph->addEdge(v1, v3);. This is because you're popping everything off the queue at the point where you find two matching data values, but what is left on the queue is not what your shortest path is.

Finally, you're missing some useful functions: how about removing a vertex or edge from a graph? The final bit of dynamic allocation in main is also unnecessary:

Graph *graph = new Graph(GraphTypeUndirected);

Should just be:

Graph graph(GraphTypeUndirected);

StackExchange Code Review Q#90099, answer score: 4