Итератор вектора вызывает ошибку сегментации 11 при попытке поиска в глубину на графике

Question

Я пытаюсь использовать DFS на основе векторного итератора для вычисления наибольшего связанного кластера сгенерированного графа. Однако, когда график имеет определенный размер (вероятность заполнения выше 0,4), в функции DFS возникает ошибка 11 сегментации.

#include <iostream>
#include <vector>
#include <random>

float seedingProbability = 0.6;
int latticeSize = 1024;
int graphSize;
bool *visited;
long largestClusterSize = 0;

std::vector<int> *graph;
std::vector<int> currentCluster;

std::uniform_real_distribution<float> unif(0, 1);
std::random_device rd;
std::mt19937 rand_engine(rd());

//Is a random number between 0 and 1 higher than (1-seeding probability)
bool isCriticalThreshold() {
    float r = unif(rand_engine); //a random float between 0 and 1
    bool isCritical = r > (1-seedingProbability);
    return isCritical;
}

//This helper function is used to determine the site index
int siteFor(int x, int y) {
    return (latticeSize*x)+y;
}

//Add an undirected edge to the graph between two sites
void addEdge(int site1, int site2) {
    graph[site1].push_back(site2);
    graph[site2].push_back(site1);
}

void DFS(int v) {
    visited[v] = true;
    currentCluster.push_back(v);

    for (std::vector<int>::iterator it = graph[v].begin(); it != graph[v].end(); it++) {
        if(!visited[*it]) {
            DFS(*it);
        }
    }
}

void connectedComponents() {
    for (int i=0; i < (graphSize); i++) {
        visited[i] = false;
    }

    for (int i=0; i<(graphSize); i++) {
        if (visited[i] == false) {
            currentCluster.clear();
            DFS(i);

            long clusterSize = currentCluster.size();
            if (clusterSize > largestClusterSize) {
                largestClusterSize = clusterSize;
            }
        }
    }
}

void createGraph() {
    for (int x = 0; x < latticeSize; x++) {
        for (int y = 0; y < latticeSize; y++) {
            //Down bond
            if (isCriticalThreshold()) {
                if (y == latticeSize-1) { addEdge(siteFor(x, y), siteFor(x, 0)); }
                else { addEdge(siteFor(x, y), siteFor(x, y+1)); }
            }

            //Right bond
            if (isCriticalThreshold()) {
                if (x == latticeSize-1) { addEdge(siteFor(x, y), siteFor(0, y)); }
                else { addEdge(siteFor(x, y), siteFor(x+1, y)); }
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    std::cout << "Running..." << std::endl;

    graphSize = latticeSize*latticeSize;
    graph = new std::vector<int>[graphSize];
    visited = new bool[graphSize];

    createGraph();
    connectedComponents();

    std::cout << "Largest cluster: " << largestClusterSize << std::endl;

    return 0;
}

Я основал DFS на: http://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/

Answer 1

Как указал jszpilewski, основная проблема заключается в том, что вам, вероятно, не хватает стековой памяти. Рекурсивный алгоритм, такой как DFS, может очень быстро заполнить стек. Вы можете использовать нерекурсивный алгоритм DFS с явно управляемым стеком.

Я собрал пример программы на основе вашего кода, чтобы проиллюстрировать это. Я позволил себе заменить необработанные указатели на объекты и массивы std::vectors. Я думаю, что это намного безопаснее с точки зрения управления памятью. Каждый узел простой struct с (необязательно) координатами x а также y как места на решетке. Основное изменение в DFS(), который явно управляет стеком для каждого не посещаемого узла. Пожалуйста, не стесняйтесь редактировать это в соответствии с вашими потребностями. Я проверил код с latticeSize до 4096, и это работает. Обратите внимание, что Node объекты должны хранить ребра только для всех целевых узлов, но не для исходных узлов.

#include <iostream>
#include <vector>
#include <random>
#include <functional>
#include <stack>

class Node;
typedef std::reference_wrapper<Node> NodeRef;

float seedingProbability = 0.8;
size_t latticeSize = 4096;
size_t largestClusterSize = 0;

std::vector<size_t> clusters;
std::vector<std::vector<Node>> graph;

std::uniform_real_distribution<float> unif(0.0, 1.0);
std::random_device rd;
std::mt19937 rand_engine(rd());

struct Node
{
    size_t x;
    size_t y;

    bool visited;

    std::vector<NodeRef> targets;

    // Add edges
    void addEdge(Node& _target)
    {
        targets.emplace_back(_target);
    }

    explicit Node(size_t _x, size_t _y)
        :
          x(_x),
          y(_y),
          visited(false)
    {}
};

// Is a random number between 0 and 1 lower than the seeding probability
bool isCriticalThreshold()
{
    return unif(rand_engine) < seedingProbability;
}

void DFS()
{
    for (auto& row : graph)
    {
        for (auto& node : row)
        {
            node.visited = false;
        }
    }

    for (auto& row : graph)
    {
        for (auto& node : row)
        {
            if (!node.visited)
            {
                size_t clusterSize(0);
                std::stack<NodeRef> stack;
                stack.push(node);
                while (!stack.empty())
                {
                    Node& cur_node(stack.top());
                    stack.pop();
                    if (!cur_node.visited)
                    {
                        cur_node.visited = true;
                        ++clusterSize;
                        for (auto& tgt : cur_node.targets)
                        {
                            stack.push(tgt);
                        }
                    }
                }

                clusters.push_back(clusterSize);
            }
        }
    }
}

void connectedComponents() 
{

    largestClusterSize = 0;
    for (const auto& clusterSize : clusters)
    {
        if (clusterSize > largestClusterSize)
        {
            largestClusterSize = clusterSize;
        }
    }
}

void createGraph()
{
    // Generate the lattice
    for (size_t x = 0; x < latticeSize; ++x)
    {
        graph.emplace_back(std::vector<Node>());
        for (size_t y = 0; y < latticeSize; ++y)
        {
            graph.back().emplace_back(x, y);
        }
    }

    // Add edges
    for (size_t  x = 0; x < latticeSize; ++x)
    {
        for (size_t y = 0; y < latticeSize; ++y)
        {
            // Down bond
            if (isCriticalThreshold())
            {
                graph.at(x).at(y).addEdge(graph.at(x).at((y + 1) % latticeSize));
            }

            // Right bond
            if (isCriticalThreshold())
            {
                graph.at(x).at(y).addEdge(graph.at((x + 1) % latticeSize).at(y));
            }
        }
    }
}

int main(int argc, const char * argv[]) {

    std::cout << "Running..." << std::endl;

    createGraph();
    DFS();
    connectedComponents();

    //  std::cout << "Cluster sizes:\n";
    //  for (size_t c = 0; c < clusters.size(); ++c)
    //  {
    //      std::cout << "\tCluster " << c << ": " << clusters.at(c) << "\n";
    //  }

    std::cout << "Largest cluster: " << largestClusterSize << std::endl;

    return 0;
}

Answer 2

Переполнение стека является наиболее типичной проблемой при запуске рекурсивного DPS на большом графике. В вашем случае вы также строите вспомогательный сбор данных currentCluster поэтому проверьте, не исчерпан ли вам 32-битный объем памяти для вашей программы (около 2-4 ГБ в зависимости от ОС). Следовательно, если вы действительно компилируете в 32-битном режиме, попробуйте сгенерировать и протестировать 64-битную версию вашей программы.