jeudi 26 octobre 2017

Vector Iterator causes Segmentation Fault 11 while attempting Depth First Search on a graph

I am attempting to use DFS based on a vector iterator to compute the largest connected cluster of a generated graph. However when the graph is a certain size (seeding probability above 0.4) a segmentation fault 11 occurs at the DFS function.

#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;
}

I based the DFS on: http://ift.tt/2zGSBvE

Aucun commentaire:

Enregistrer un commentaire