CODEWITHSUNDEEP
c++vectorsegmentation-fault
user1134632
user1134632

Reputation: 11

std::vector::push_back throws segmentation fault

I've got problem with my program. For small number of edges it works perfectly, but when it gets 15000 edges of oriented graph, i get segmentation fault after one minute runtime. Debugger says that it is thrown by vector push_back method. Do somebody of you know what is wrong with the code and how to avoid it?

Error is thrown in dfs procedure at line result.push_back(tmpResult);

#include <cstdlib>
#include <iostream>
#include <vector>

using namespace std;

typedef struct {
    unsigned int endNode;      // Number of dest node
    bool used;                 // true, if edge was used in dfs
} EdgeType;

typedef struct {
    unsigned int startNode;     // Number of source node
    vector<EdgeType> edge;      // Outgoing edges from node
} NodeType;

typedef struct {
    unsigned int startNode;
    unsigned int endNode;
} ResultType;


bool loadInput(vector<NodeType>& graph, unsigned int& numEdges);
void dfs(vector<NodeType>& graph, unsigned int i, unsigned int numEdges, vector<ResultType>& result);

int main(int argc, char** argv) {
    vector<NodeType> graph;
    vector<ResultType> result;
    unsigned int numEdges;

    result.reserve(300000);

    // Generate oriented multigraph (3 nodes, 150000 edges)
    numEdges = 150000;
    NodeType tmpNode;
    EdgeType tmpEdge;

    for (unsigned int i = 0; i < 50000; i++) {
        tmpEdge.used = false;
        tmpEdge.endNode = 1;
        tmpNode.edge.push_back(tmpEdge);     
    }
    tmpNode.startNode = 0;
    graph.push_back(tmpNode);
    tmpNode.edge.clear();

    for (unsigned int i = 0; i < 50000; i++) {
        tmpEdge.used = false;
        tmpEdge.endNode = 2;
        tmpNode.edge.push_back(tmpEdge);     
    }
    tmpNode.startNode = 1;
    graph.push_back(tmpNode);
    tmpNode.edge.clear();

    for (unsigned int i = 0; i < 50000; i++) {
        tmpEdge.used = false;
        tmpEdge.endNode = 0;
        tmpNode.edge.push_back(tmpEdge);     
    }
    tmpNode.startNode = 2;
    graph.push_back(tmpNode);
    tmpNode.edge.clear();

    cout << "numEdges: " << numEdges << endl;

    // Find way
    for (unsigned int i = 0; i < graph.size(); i++) {
        dfs(graph, i, numEdges, result);
    }

    // No way found
    cout << "-1" << endl;

    return 0;
}

void dfs(vector<NodeType>& graph, unsigned int i, unsigned int numEdges, vector<ResultType>& result) {
    // Way was found, print it and exit program (bad style, only for testing)
    if (numEdges == result.size()) {
        cout << graph.size() << endl;
        vector<ResultType>::iterator it;
        for (it = result.begin(); it != result.end(); it++) {
            cout << (*it).startNode << " " << (*it).endNode << endl;
        }
        cout << "0 0" << endl;
        exit(0);
    }
    // For each outgoing edge do recursion 
    for (unsigned int j = 0; j < graph[i].edge.size(); j++) {
        if (i >= graph.size()) return;
        if (!graph[i].edge[j].used) {
            graph[i].edge[j].used = true;
            ResultType tmpResult;
            tmpResult.startNode = graph[i].startNode;
            tmpResult.endNode = graph[i].edge[j].endNode;
            result.push_back(tmpResult);
            dfs(graph, graph[i].edge[j].endNode, numEdges, result);
            result.pop_back();
            graph[i].edge[j].used = false;
        }
    }
}

The goal for me with my program is to find a way in oriented graph, where each edge is used just once.

Upvotes: 1

Views: 7364

Answers (3)

Mike Seymour
Mike Seymour

Reputation: 254461

It's most likely that you're recursing too deeply, causing a stack overflow. On most platforms, the stack has a fixed size; you may be able to make it bigger, but you probably still won't be able to support arbitrarily large graphs.

Perhaps you could replace the recursion with an iterative algorithm, maintaining your own stack (e.g. a std::stack) of the state you need to restore when you backtrack. Then the only limit on graph size is the available memory.

Upvotes: 1

user405725
user405725

Reputation:

If push_back throws, it is most likely because your program is running out of memory. Since you do not catch any exceptions, the default exception handler is getting invoked and application is terminated. In gdb, you can use catch throw command to stop on every "throw" statement.

Upvotes: 0

ildjarn
ildjarn

Reputation: 62975

dfs calls itself recursively; increasing numEdges increases the recursion depth so, consequently, increasing numEdges sufficiently causes a stack overflow (which manifests as a segfault on your platform).

Either build your program with a larger stack size (compiler-specific) or don't use recursion in this scenario.

Upvotes: 6

Related Questions