3
\$\begingroup\$

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<T> &v or should it be Vector<T> *v or Vector<T> v?

//Graph.h
#ifndef GRAPH_H
#define GRAPH_H

#include <vector>
#include <string>
#include <queue>

template <typename T>
class Graph;

template <typename K>
class Vertex;

template <typename T>
class Neighbor {
    friend class Vertex<T>;
    friend class Graph<T>;

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

template <typename T>
class Vertex {
    friend class Graph<T>;

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

typedef enum GraphType {
    GraphTypeDirected,
    GraphTypeUndirected
} GraphType;

template <typename T>
class Graph {
    private:
        std::vector< Vertex<T> > vertices;
        GraphType graphType;
        int counter;

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

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;
}

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

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

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

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

        curr = curr->next;
    }

    return false;
}

template <typename T>
std::string Graph<T>::getShortestPathFrom(Vertex<T> &v1, Vertex<T> &v2)
{
    std::queue<Vertex<T> > q;
    q.push(v1);

    bool *seen = new bool[vertices.size()];
    for (int i = 0; i < vertices.size(); i++)
        seen[i] = false;

    seen[v1.index] = true;

    while (!q.empty()) {
        Vertex<T> v = q.front();
        Neighbor<T> *curr = v.adjLL;

        while (curr != NULL) {
            if (!seen[curr->vertexIndex]) {
                seen[curr->vertexIndex] = true;
                q.push(vertices.at(curr->vertexIndex));

                if (vertices.at(curr->vertexIndex).data == v2.data) {
                    std::string temp;

                    while (!q.empty()) {
                        printf("%d\n", q.front().data);
                        temp += q.front().data;
                        q.pop();
                    }

                    return temp;
                }
            }

            curr = curr->next;
        }

        q.pop();
    }

    return "Path Not Found";
}

#endif

//main.cpp
#include <stdio.h>
#include <string>
#include <iostream>
#include "Graph.h"

using namespace std;

int main(int argc, const char *argv[])
{
    Graph<int> *graph = new Graph<int>(GraphTypeUndirected);
    Vertex<int> *v1 = graph->addVertex(10);
    Vertex<int> *v2 = graph->addVertex(15);
    Vertex<int> *v3 = graph->addVertex(20);
    Vertex<int> *v4 = graph->addVertex(25);
    Vertex<int> *v5 = graph->addVertex(30);

    graph->addEdge(*v1, *v2);
    graph->addEdge(*v1, *v3);
    graph->addEdge(*v1, *v4);

    bool c = graph->isConnected(*v1, *v3);
    std::string s = graph->getShortestPathFrom(*v1, *v3);

    printf("%s", s.c_str());
}
\$\endgroup\$
4
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ Also I was wondering, how would you do DFS with your implementation of a graph with an array of neighbors. \$\endgroup\$ – Aadesh May 9 '15 at 4:06
  • \$\begingroup\$ @Aadesh Basically swapping a queue for a stack will do DFS. \$\endgroup\$ – Yuushi May 9 '15 at 4:57
  • \$\begingroup\$ Btw this piece of code doesn't work: template <typename T> Vertex& Graph<T>::addVertex(const T& data) { vertices.push_back(Vertex<T>(data, counter++)); return *vertices.back(); } it says that vertices.back() isn't even a pointer so you can't dereference it \$\endgroup\$ – Aadesh May 11 '15 at 0:06
  • \$\begingroup\$ @Aadesh Yeah, back returns a reference, my mistake. I've fixed that up \$\endgroup\$ – Yuushi May 11 '15 at 2:19
  • \$\begingroup\$ A little detail: I believe that is better to use #include <cstdio> instead of #include <stdio.h>. It makes explicit that your using things from the C library. For more information, see here gcc.gnu.org/onlinedocs/gcc-4.9.0/libstdc++/api/a01092.html and here gcc.gnu.org/onlinedocs/gcc-4.9.0/libstdc++/api/…. \$\endgroup\$ – rcanepa May 11 '15 at 2:44

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.