Graph data structure implementation

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 <typename T>
Vertex<T> *Graph<T>::addVertex(const T &data)
{
    Vertex<T> *v = new Vertex<T>(data, counter++);
    vertices.push_back(*v);

    return v;
}

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

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

In your Vertex<T> class, you're building up a linked list of Neighbour<T> 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 <typename T>
class Vertex {
    friend class Graph<T>;

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

template <typename T>
void Vertex<T>::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 <typename T>
bool Graph<T>::isConnected(const Vertex<T> &v1, const Vertex<T> &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 <typename T>
void Graph<T>::addEdge(Vertex<T> &v1, Vertex<T> &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<int> *graph = new Graph<int>(GraphTypeUndirected);

Should just be:

Graph<int> graph(GraphTypeUndirected);