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