A Problem with Vectors (std::out_of_range)

Question

Here is the description of my problem:

The Program's Description:
I am implementing a program in C++ that tests Prim's algorithm for finding minimum spanning trees. The objective of the program is calculating the number of seconds it takes to find the minimum spanning tree for a selected number of random graphs.

What i have done up to now?
I finished the implementation of the functions and the header files for the whole program. Since the source code is small, i decided for clarity reasons to paste it with this mail in order to provide a better visualization of the problem.

The Problem:
For some reason, i am facing some sort of "out of range" vector problem during the run time of the application. The problem is marked in the ("Prim_and_Kruskal_Algorithms.cpp") file.

Requesting help:
I would be really grateful if anyone can help me spotting the problem. I have inlined the source code with this question.

The Source Code:

The (Undirected_Graph.h) file:

#ifndef UNDIRECTED_GRAPH_H
#define UNDIRECTED_GRAPH_H

#include <vector>
using std::vector;

#include <climits>

class Edge;

class Node
{
    public:

        Node(int);                 //The constructor.

        int id;                    //For the id of the node.
        bool visited;              //For checking visited nodes.
        int distance;

        vector <Edge*> adj;       //The adjacent nodes.
};

class Edge
{
    public:

        Edge(Node*, Node*, int);   //The constructor.

        Node* start_Node;          //The start_Node start of the edge.
        Node* end_Node;            //The end of the edge.
        int w;                     //The weight of the edge.

        bool isConnected(Node* node1, Node* node2)  //Checks if the nodes are connected.
        {
            return((node1 == this->start_Node && node2 == this->end_Node) ||
                   (node1 == this->end_Node   && node2 == this->start_Node));
        }
};

class Graph
{
    public:

        Graph(int);                    //The Constructor.

        int max_Nodes;                 //Maximum Number of allowed Nodes.

        vector <Edge*> edges_List;     //For storing the edges of the graph.
        vector <Node*> nodes_List;     //For storing the nodes of the graph.

        void insertEdge(int, int, int);

        int getNumNodes();
        int getNumEdges();
};

#endif

The (Undirected_Graph.cpp) file:

#include "Undirected_Graph.h"

Node::Node(int id_Num)
{
    id = id_Num;
    visited = 0;
    distance = INT_MAX;
}

Edge::Edge(Node* a, Node* b, int weight)
{
    start_Node = a;
    end_Node = b;
    w = weight;
}

Graph::Graph(int size)
{
    max_Nodes = size;

    for (int i = 1; i <= max_Nodes; ++i)
    {
        Node* temp = new Node(i);

        nodes_List.push_back(temp);
    }
}

void Graph::insertEdge(int x, int y, int w)
{
    Node* a = nodes_List[x-1];
    Node* b = nodes_List[y-1];

    Edge* edge1 = new Edge(a, b, w);
    Edge* edge2 = new Edge(b, a, w);

    edges_List.push_back(edge1);

    a->adj.push_back(edge1);
    b->adj.push_back(edge2);
}

int Graph::getNumNodes()
{
    return max_Nodes;
}

int Graph::getNumEdges()
{
    return edges_List.size();
}

The (Prim_and_Kruskal_Algorithms.h) File:

#ifndef PRIM_AND_KRUSKAL_ALGORITHMS_H
#define PRIM_AND_KRUSKAL_ALGORITHMS_H

class PKA
{
    private:
    //inline void generateRandomGraph();

    protected:
    //-No Protected Data Members in this Class.

    public:
        void runAlgorithms();
        void prim();
};

#endif

The (Prim_and_Kruskal_Algorithms.cpp) file *(The problem is in this file and is marked below):*

#include "Prim_and_Kruskal_Algorithms.h"
#include "Undirected_Graph.h"

#include <iostream>
using std::cout;
using std::cin;
using std::endl;

#include <cstdlib>
using std::rand;
using std::srand;

#include <ctime>
using std::time;

//=============================================================================
//============Global Variables and Settings for the program====================
//=============================================================================

const int numIterations = 1; //How many times the Prim function will run.
const int numNodes = 10;     //The number of nodes in each graph.
const int numEdges = 9;      //The number of edges for each graph.
const int sRandWeight = 1;   //The "start" range of the weight of each edge in the graph.
const int eRandWeight = 100; //The "end" range of the weight of each edge in the graph.

//=============================================================================
//=============================================================================
//=============================================================================

void PKA::runAlgorithms()   //Runs the Algorithms
{
        srand( time(0) );

    cout << "------------------------------" << endl;

        //Calling the Functions:
        cout << "\nRunning the Prim's Algorithms:\nPlease wait till the completion of the execution time" << endl;

        //===============================================

        //Start the clock for Prim's Algorithm:
        clock_t start, finish;
        start = clock();

        for(int iter1 = 1; iter1 <= numIterations; ++iter1)
        {
            prim();
        }

        //Stop the clock for Prim and print the results:
    finish = clock();
        cout << "\n\tThe execution time of Prim's Algorithm:\t" << ((double)(finish - start) / CLOCKS_PER_SEC) << " s";

    return;
}

void PKA::prim()
{
    //=============================================================================
    //=============================Generating A Random Graph=======================
    //=============================================================================

    //Randomizing Values:
    //===============================================

    int randStartNode = rand() % numNodes;     //Generation a random start node.
    int randEndNode = rand() % numNodes;       //Generating a random end node.
    int randWeight;               //Random weight for the edge.

    while(randEndNode == randStartNode)   //Checking if both randomized nodes are equal.
    {
        randEndNode = (rand() % numNodes);
    }

    //===============================================

    Graph myGraph(numNodes);

    for(int i = 0; i < numEdges; ++i)
    {
        //Generating a random weight:
        randWeight =  sRandWeight + rand() % eRandWeight;

        //Inserting a new Edge:
        myGraph.insertEdge(randStartNode, randEndNode, randWeight);
    }


    //=============================================================================
    //=============================================================================
    //=============================================================================

    int currentNode = 0;           //The current Node being under investigation.
    int adjCounter = NULL;         //How many adjacent nodes do we have for the current node.
    int minDistance = NULL;        
    int minIndex = 0;

    myGraph.nodes_List[0]->distance = 0;   //Indicate the start node.
    myGraph.nodes_List[0]->visited = 1;    //The starting node is already considered as a visited node.

    for(int i = 0; i < numNodes - 1; i++)
    {
        //Determine how many adjacent nodes there are for the current node:
        adjCounter = myGraph.nodes_List[currentNode]->adj.size();

        if(adjCounter == 0) //If there are no adjacent nodes to the current node:
        {
            myGraph.nodes_List[currentNode]->adj.at(minIndex)->end_Node->visited = 1;
                    cout << "\n*******Not all nodes are connected!*******" << endl;
            continue;
        }

        minDistance = myGraph.nodes_List[currentNode]->adj.at(0)->w;
        minIndex = 0;

        for(int counter = 0; adjCounter > 0; adjCounter--, counter++)
        {
            if(myGraph.nodes_List[currentNode]->adj[counter]->end_Node->visited == false)
            {
                if(myGraph.nodes_List[currentNode]->distance > myGraph.nodes_List[currentNode]->adj[counter]->w)
                {
                    myGraph.nodes_List[currentNode]->distance = myGraph.nodes_List[currentNode]->adj[counter]->w;
                }

                if(minDistance > myGraph.nodes_List[currentNode]->adj[counter]->w)
                {
                    minDistance = myGraph.nodes_List[currentNode]->adj[counter]->w;
                    minIndex = counter;
                }
            }
        }

                //======================================================================================
                //=========================The Problem is in the following two lines====================
        //======================================================================================

        //Mark the current node as visited:
        myGraph.nodes_List[currentNode]->adj.at(minIndex)->end_Node->visited = 1;

        //Switching to the next node that we have just visited:
        currentNode = myGraph.nodes_List[currentNode]->adj.at(minIndex)->start_Node->id;

        //======================================================================================
        //======================================================================================
        //======================================================================================
    }
}

The (Client_Code.cpp) file: For testing the program.

#include "Prim_and_Kruskal_Algorithms.h"
#include <iostream>

using std::cout;
using std::endl;

int main()
{
    cout << "\nWelcome to the Prim and Kruskal Algorithms Comparison!" << endl;
    cout << "\nPlease wait until the completion of the algorithms." << endl;

    PKA myPKA;                //Creating an object of the class.
    myPKA.runAlgorithms();    //Running the Algorithm.

    cout << "\n\nThe program terminated successfully!" << endl;

    return 0;
}

Answer 1

Look at this line:

myGraph.nodes_List[currentNode]->adj.at(minIndex)->end_Node->visited = 1;

As an experienced C++ programmer, I find that line terrifying.

The immediate cause of trouble is that adj doesn't have as many members as you think it does; you're asking for (in my test run) the 5th element of a list of size zero. That sends you off the map, where you then start manipulating memory.

More generally, you are not checking bounds.

More generally still, you should allow these classes to manage their own members. Use accessors and mutators (getX() and setX(...)) so that member access happens all in one place and you can put the bounds checking there. Reaching down myGraph's throat like that is very unsafe.

You'll notice that I haven't said where/when/how the program diverges from intention so that the list doesn't have as many elements as it should. That's because it's too much trouble for me to track it down. If you organize the classes as I suggest, the code will be a lot cleaner, you can check your assumptions in various places, and the bug should become obvious.

EDIT:
To create a random connected graph, try this:

  Graph myGraph(numNodes);              //Create a new Graph.

  // This ensures that the kth node is connected to the [1...(k-1)] subgraph.
  for(int k=2 ; k<=numNodes ; ++k)
    {
      randWeight =  rand() % eRandWeight;
      myGraph.insertEdge(k, rand()%(k-1)+1, randWeight);
    }

  // This adds as many extra links as you want.
  for(int i = 0; i < numExtraEdges; ++i)
    {
      randWeight =  rand() % eRandWeight;
      randStartNode = rand()%(numNodes-1)+1;
      randEndNode = rand()%(numNodes-1)+1;
      myGraph.insertEdge(randStartNode, randEndNode, randWeight);
    }

Answer 2

You have too much code for a casual examination to be sure of anything. But the .at() method will throw the out-of-range exception that you mentioned and that crashing line occurs right after you've updated minIndex so I would suggest reviewing the code that determines that value. Are you using a debugger? What is the value of minIndex at the point of the exception and what is the allowable range?

Also, when you have a monster line of compounded statements like that, it can help in debugging problems like this and give you clearer, simpler looking code if you break it up. Rather than repeating big chunks of code over and over, you can have something like this:

Node * node = myGraph.nodes_List[currentNode];
assert(node);
Edge * minAdjEdge = node->adj.at(minIndex);
assert(minAdjEdge);

Then use minAdjEdge to refer to that edge instead of that repeated compound statement.

It also seems odd to me that your first use of minIndex in the big loop is still using the value determined from the node in the previous iteration, but it's applying it to the new current node. Then you reset it to zero after possibly using the stale value. But that isn't near the line that you say is causing the crash, so that may not be your problem. Like I said, you have a lot of code pasted here so it's hard to follow the entire thing.

Answer 3

It is too much code, but what I can observe at the first glance is that for some reason you are mixing 0-based and 1-based iteration.

Is this intentional? Couldn't that be the cause of your problem?