First Graph Adjacency List

Question

First time implementing a adjacency list. Is the use of exceptions correct? If anyone could test/read the code and give some advice on improvments I would appreciate it.

#include <iostream>
#include <vector>
#include <exception>
#include <list>

class VertexInvalidArg : public std::invalid_argument
{
public:
    VertexInvalidArg(const std::string &msg)
        :invalid_argument(msg)
    {}
};

class VertexUnderFlow : public std::underflow_error
{
public:
    VertexUnderFlow(const std::string &msg)
        :underflow_error(msg)
    {}
};

class Graph
{
public:
    Graph(int defaultVertices = 0);

    void addEdge(int v1, int v2);
    void addVertex();
    size_t noOfVertices() const;
    bool isEdge(int v1, int v2) const;
    bool isVertex(int v1) const;
    void clear();

private:
    std::vector<std::list<int> > adjList;
    friend std::ostream& operator<<(std::ostream& os, const Graph& g);

    size_t vertexCount;
};

Graph::Graph(int defaultVertices)
{
    if (defaultVertices <= 0)
    {
        defaultVertices = 0;
    }
    vertexCount = defaultVertices;

    for (int i = 0; i < vertexCount; i++)
    {
        std::list<int> vertex;
        adjList.push_back(vertex);
    }
}

void Graph::addVertex()
{
    std::list<int> vertex;
    adjList.push_back(vertex);
    ++vertexCount;
}

size_t Graph::noOfVertices() const
{
    return vertexCount;
}

void Graph::addEdge(int v1, int v2)
{
    if (v1 == v2)
    {
        throw VertexInvalidArg("Vertex Cannot Connect To Itself");
    }
    else if (v1 > vertexCount - 1 || v2 > vertexCount - 1)
    {
        throw VertexInvalidArg("Vertex Does Not Exist");
    }
    else
    {
        std::list<int>::iterator itr = adjList[v1].begin();
        while (itr != adjList[v1].end())
        {
            if (*itr == v2)
            {
                throw VertexInvalidArg("Edge Already Exists");
            }
            ++itr;
        }

        adjList[v1].push_back(v2);
        adjList[v2].push_back(v1);
    }
}

std::ostream& operator<<(std::ostream& os, const Graph& g)
{
    if (g.vertexCount == 0)
    {
        throw VertexUnderFlow("No Vertices to Display");
    }

    std::cout << std::endl;
    for (int i = 0; i < g.vertexCount; i++)
    {
        os << "Vertex " << i << " Connects To Vertex: ";
        std::list<int>::const_iterator itr = g.adjList[i].begin();
        while (itr != g.adjList[i].end())
        {
            os << *itr << " ";
            ++itr;
        }
        os << std::endl;
    }
    return os;
}

bool Graph::isEdge(int v1, int v2) const
{
    if (vertexCount == 0)
    {
        throw VertexUnderFlow("Graph is empty");
    }
    else if (v1 == v2)
    {
        throw VertexInvalidArg("Vertex Cannot Connect To Itself");
    }
    else if (v1 > vertexCount - 1 || v2 > vertexCount - 1)
    {
        throw VertexInvalidArg("Vertex Does Not Exist");
    }

    bool found = false;
    std::list<int>::const_iterator itr = adjList[v1].begin();
    while (itr != adjList[v1].end())
    {
        if (*itr == v2)
        {
            found = true;
        }
        ++itr;
    }
    return found;
}

bool Graph::isVertex(int v1) const
{
    bool found = false;
    if (v1 < vertexCount)
    {
        found = true;
    }
    return found;
}

void Graph::clear()
{
    adjList.clear();
    vertexCount = 0;
}

int main()
{
    using std::cout;
    using std::cin;
    using std::endl;


    Graph myG;
    int loop = 0;
    int menuChoice = 0;
    int V1 = 0, V2 = 0;

    while (loop != -1)
    {
        cout << "Please select operation: " << endl << endl;
        cout << "1: Add Vertex" << endl;
        cout << "2: Add Edge" << endl;
        cout << "3: Display Graph" << endl;
        cout << "4: Number of Vertices" << endl;
        cout << "5: Is Edge" << endl;
        cout << "6: Is Vertex" << endl;
        cout << "7: Clear" << endl;
        cout << "-1: Terminate Program" << endl << endl;

        cin >> menuChoice;
        switch (menuChoice)
        {
        case 1:
            myG.addVertex();
            cout << endl << "Vertex " << myG.noOfVertices() - 1 << " Added" << endl << endl;
            break;
        case 2:
            cout << endl << "Enter First Vertex: ";
            cin >> V1;
            cout << "Enter Second Vertex: ";
            cin >> V2;
            try
            {
                myG.addEdge(V1, V2);
            }
            catch (const VertexInvalidArg& e)
            {
                std::cerr << "Error: Invalid Argument: " << e.what();
            }
            cout << endl << "Edge between " << V1 << " and " << V2 << " Added";
            cout << endl << "Edge between " << V2 << " and " << V1 << " Added" << endl << endl;
            break;
        case 3:
            cout << endl;
            try
            {
                cout << myG;
            }
            catch (const VertexUnderFlow& e)
            {
                std::cerr << "Error: Under Flow: " << e.what();
            }
            cout << endl << endl;
            break;
        case 4:
            cout << endl << "Number of Vertices: ";
            cout << myG.noOfVertices();
            cout << endl << endl;
            break;
        case 5:
            cout << endl << "Enter First Vertex: ";
            cin >> V1;
            cout << "Enter Second Vertex: ";
            cin >> V2;
            cout << endl;
            try
            {
                cout << "Is Edge: " << myG.isEdge(V1, V2);
            }
            catch (const VertexInvalidArg& e)
            {
                std::cerr << "Error: Invalid Argument: " << e.what();
            }
            catch (const VertexUnderFlow& e)
            {
                std::cerr << "Error: Under Flow: " << e.what();
            }
            cout << endl << endl;
            break;
        case 6:
            cout << endl << "Enter Vertex: ";
            cin >> V1;
            cout << endl;
            cout << "Is Vertex: " << myG.isVertex(V1);
            cout << endl << endl;
            break;
        case 7:
            cout << endl << "Graph Cleared" << endl << endl;
            myG.clear();
            break;
        case -1:
            cout << endl << "Operation Terminated";
            loop = -1;
            break;
        default: cout << endl << "Invalid Input" << endl << endl;
        }
    }

    cout << endl << endl;
    system("pause"); // TESTING
    return 0;
}

Answer 1

Data Members

You currently have two members:

std::vector<std::list<int> > adjList;
size_t vertexCount;

But vertexCount is always the size of adjList. That's just extra stuff you have to keep track of. The best thing you can say about it is that it's error prone. You can drop vertexCount and rewrite size() to simply be:

size_t Graph::noOfVertices() const
{
    return adjList.size();
}

Secondly, you implemented adjList as a vector of lists. That may be canonically correct, but list is actually not a good data structure for this since lists are very inefficient at iteration you do in several places. vector would be strictly better, due to its cache friendliness.

Constructor

The whole point of your constructor is to make defaultVertices empty lists. There is a constructor on vector which takes a size. Use it:

Graph::Graph(int defaultVertices)
: adjList(std::max(defaultVertices, 0))
{ }

Quite a bit cleaner!

addVertex()

If you can use C++11, you can rewrite this function as a one-liner as well:

adjList.emplace_back();

That will default-construct a new container in place as the new last element: exactly what you want. And note that we're not keeping track of vertexCount manually anymore - so don't have to do that either!

addEdge()

Is there a reason you're not supporting self-edges?

Your check against the max is correct, but weird. Better to do:

v1 >= adjList.size() || v2 >= adjList.size()

Any extra operations you add on your code make it harder to understand. The -1s here are just unnecessary.

Now for the main part of the function. You are looking for v2 in adjList[v1]. There's an algorithm for that, it's called std::find and it's a lot easier to use:

auto it = std::find(adjList[v1].begin(), adjList[v1].end(), v2);
if (it == adjList[v1].end()) {
    adjList[v1].push_back(v2);
    adjList[v2].push_back(v1);
}
else {
    // throw
}

isEdge()

Similarly, use find(). Here it's especially useful as it'll be much more efficient. Once you find your edge, you don't have to keep going - but you still do! The end could just be:

return std::find(adjList[v1].begin(), adjList[v1].end(), v2)
      != adjList[v1].end();

isVertex()

What you wrote is an antipattern. Anytime you want to check if an expression is true or false, you want to simply do:

return v1 < vertexCount;

Not:

return (v1 < vertexCount) ? true : false;

Not:

if (v1 < vertexCount) return true;
else return false;

Not what you did with the extra member variable. It's unnecessarily verbose and just looks funny.

Redundancy

You are keeping track of twice as much information as you need to. You have an edge from 2 to 5 and 5 to 2. If you are just keeping an adjacency list in an undirected graph, you can just keep the upper triangle. Add a helper to put the vertices in the correct order:

void sort(int& v1, int& v2) {
    if (v1 > v2) {
        std::swap(v1, v2);
    }
}

And then start each of your methods with a call to sort(), and only add and check the edges against v1.

Hope that helps!