bad_alloc on vector.push_back

[PsylentKnight]

I'm getting a bad_alloc error when I attempt to push to a vector(see the line marked // ERROR HERE). What could be the problem?

/*
 * Files: bellmanFord.cpp
 *
 * Program Purpose: 
 * To implement the Bellman-Ford routing algorithm. 
 */ 
 
#include <iostream>
#include <climits>
#include <fstream>
#include <vector>
#include <sstream>
#include <ctype.h>

const int DEBUG = true;

// weighted edge in graph
struct Edge
{
    int src, dest, weight;

};

// node
struct Node
{
	std::string cityName;
};
 
// connected, directed and weighted graph
struct Graph
{
    int V; // number of vertices
	int E; // number of edges
 
    // graph is represented as an array of edges.
    std::vector<Edge> edges;
    
    std::vector<Node> nodes;
};
 
// Creates a graph with V vertices and E edges
struct Graph* createGraph(int V, int E)
{
    struct Graph* graph = 
         (struct Graph*) malloc( sizeof(struct Graph) );
    graph->V = V;
    graph->E = E;
 		
    return graph;
}
 
// prints the routing table
void printRoutingTable(std::vector<std::vector<int> > routingTable)
{
    for(int i = 0; i < routingTable.size(); i++)
    {
    	for(int j = 0; j < routingTable.size(); i++)
    	{
    		std::cout << routingTable.at(i).at(j) << " ";
		}
		std::cout << std::endl;
	}
}
 
// Given a graph, 
std::vector<int> bellmanFord(struct Graph* graph, int src)
{
	if(DEBUG) std::cout << "Bellman Ford" << std::endl;
    int V = graph->V;
    int E = graph->E;
    std::vector<int> dist(V, INT_MAX);
 	dist.at(src) = 0;
 	
    // relax all edges at most |V| - 1 times. A simple shortest 
    // path from src to any other vertex can have at-most |V| - 1 
    // edges
    for (int i = 1; i <= V-1; i++)
    {
        for (int j = 0; j < E; j++)
        {
            int u = graph->edges.at(j).src;
            int v = graph->edges.at(j).dest;
            int weight = graph->edges.at(j).weight;
            if (dist.at(u) != INT_MAX && dist.at(u) + weight < dist.at(v))
                dist.at(v) = dist.at(v) + weight;
        }
    }
 
    // check for negative-weight cycles.  The above step 
    // guarantees shortest distances if graph doesn't contain 
    // negative weight cycle.  If we get a shorter path, then there
    // is a cycle.
    for (int i = 0; i < E; i++)
    {
        int u = graph->edges.at(i).src;
        int v = graph->edges.at(i).dest;
        int weight = graph->edges.at(i).weight;
        if (dist.at(u) != INT_MAX && dist.at(u) + weight < dist.at(v))
            printf("Error: negative weight cycle");
    }
 
    return dist;
}

// split string on whitespace
std::vector<std::string> split(std::string str)
{
	if(DEBUG) std::cout << "Split" << std::endl;
    std::string buf; // buffer
    std::stringstream ss(str); // Insert the string into a stream

    std::vector<std::string> tokens; // Create vector to hold our words

    while (ss >> buf)
        tokens.push_back(buf);
		
	return tokens;	
}

struct Graph* readFile(){
	if(DEBUG) std::cout << "Read File" << std::endl;
	std::string line;
	std::ifstream myFile ("input.txt");
	int V = 0;  // Number of vertices in graph
    int E = 0;  // Number of edges in graph
    struct Graph* graph;
    
	if(myFile.is_open())
	{
		// get vectors
		std::getline(myFile, line);
		int V = stoi(line);
		
		// edges
		int E = 0;
		
    	graph = createGraph(V, E);
    	
		// get every line
		for(int i = 0; i < graph->V; i++){
			if(DEBUG) std::cout << "Getting Line" << std::endl;
			std::getline(myFile, line);
			
			struct Node newNode;
			newNode.cityName = "";
			graph->nodes.push_back(newNode);
			
			// process line
			std::vector<std::string> tokens = split(line);
			
			int edgeInd = 0;

			for(int j = 0; j < tokens.size(); j++)
			{
				std::string word = tokens.at(j);
				if(DEBUG) std::cout << "Word: " << word << std::endl;
				if(j < tokens.size() - graph->V)
				{
					graph->nodes.at(i).cityName += word;
					graph->nodes.at(i).cityName += " ";
				}
				else
				{
					if(isdigit(word.at(0)))
					{
						struct Edge newEdge;
						newEdge.src = i;
						newEdge.dest = edgeInd;
						newEdge.weight = stoi(word);
						
						graph->edges.push_back(newEdge); // ERROR HERE
						if(DEBUG) std::cout << "NewEdge. Src: " << graph->edges.at(i).src << " Dest: " << graph->edges.at(i).dest << " Weight: " << graph->edges.at(i).weight << std::endl;
						graph->E++;
					}
					edgeInd++;
				}
			}
		}
		
		myFile.close();
	}

	return graph;
}

int main()
{
	struct Graph* graph = readFile();
    
	std::vector< std::vector<int> > routingTable(graph->V, std::vector<int>(graph->V, INT_MAX));
	
	for(int i = 0; i < graph->V; i++)
	{
		routingTable.at(i) = bellmanFord(graph, i);
	}
	
	printRoutingTable(routingTable);
}

[ne555]

> std::ifstream myFile ("input.txt");
¿is too much to ask to be able to run your program the same way that you do to get the same error as you?

    struct Graph* graph = 
         (struct Graph*) malloc( sizeof(struct Graph) );

`Graph' contains two `std::vector' that need to be initialized properly. You are leaving them in a bad state.
If you are sure that you want a pointer to a dynamical allocated graph, then use new instead of `malloc()'
Else, just construct an object.

[PsylentKnight]

Sorry for not posting the input file, my bad.

 struct Graph* graph = new Graph;

This fixed it, thank you.

[ne555]

don't forget to delete it when you are done.