std :: vector :: push_back throws segmentation fault

Question

У меня проблема с моей программой. Для небольшого числа ребер он работает отлично, но когда он получает 15000 ребер ориентированного графика, я получаю ошибку сегментации после одной минуты выполнения. Отладчик говорит, что он вызывается векторным методом push_back. Кто-нибудь из вас знает, что не так с кодом и как его избежать?

Ошибка в процедуре dfs в строке 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; 
     } 
    } 
} 

Цель для меня с моей программой, чтобы найти путь в ориентированном графе, где каждое ребро используется только один раз.

Answer 1

dfs называет себя рекурсивно; увеличение numEdges увеличивает глубину рекурсии, поэтому увеличение numEdges в достаточной степени вызывает переполнение стека (которое проявляется как segfault на вашей платформе).

Либо создайте свою программу с большим размером стека (специфичным для компилятора), либо не используйте рекурсию в этом сценарии.

Answer 2

Если вы выбрали push_back, это скорее всего из-за нехватки памяти в вашей программе. Поскольку вы не поймаете никаких исключений, обработчик исключений по умолчанию получает вызов и приложение прекращается. В gdb вы можете использовать команду catch throw для остановки в каждом заявлении «throw».

Answer 3

Скорее всего, вы слишком глубоко пересматриваете, вызывая переполнение стека. На большинстве платформ стек имеет фиксированный размер; вы можете сделать его больше, но вы, вероятно, все равно не сможете поддерживать сколь угодно большие графики.

Возможно, вы можете заменить рекурсию на итеративный алгоритм, поддерживая свой собственный стек (например, std::stack) состояния, которое необходимо восстановить, когда вы возвращаетесь назад. Тогда единственным ограничением размера графика является доступная память.