106 lines
2.9 KiB
C++
106 lines
2.9 KiB
C++
#include <iostream>
|
|
#include <random>
|
|
#include <string>
|
|
#include <vector>
|
|
#include <iomanip>
|
|
|
|
std::random_device random;
|
|
std::mt19937 generator(random());
|
|
std::uniform_real_distribution<double> distribution(0.0F, 1.0F);
|
|
|
|
class Grid {
|
|
public:
|
|
Grid(const int32_t size, const double probability) {
|
|
create_grid(size, probability);
|
|
count_clusters();
|
|
}
|
|
|
|
int32_t cluster_count() const {
|
|
return clusters;
|
|
}
|
|
|
|
double cluster_density() const {
|
|
return (double) clusters / ( grid.size() * grid.size() );
|
|
}
|
|
|
|
void display() const {
|
|
for ( uint64_t row = 0; row < grid.size(); ++row ) {
|
|
for ( uint64_t col = 0; col < grid.size(); ++col ) {
|
|
uint64_t value = grid[row][col];
|
|
char ch = ( value < GRID_CHARACTERS.length() ) ? GRID_CHARACTERS[value] : '?';
|
|
std::cout << " " << ch;
|
|
}
|
|
std::cout << std::endl;
|
|
}
|
|
}
|
|
private:
|
|
void count_clusters() {
|
|
clusters = 0;
|
|
for ( uint64_t row = 0; row < grid.size(); ++row ) {
|
|
for ( uint64_t col = 0; col < grid.size(); ++col ) {
|
|
if ( grid[row][col] == CLUSTERED ) {
|
|
clusters += 1;
|
|
identify_cluster(row, col, clusters);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
void identify_cluster(const uint64_t row, const uint64_t col, const uint64_t count) {
|
|
grid[row][col] = count;
|
|
if ( row < grid.size() - 1 && grid[row + 1][col] == CLUSTERED ) {
|
|
identify_cluster(row + 1, col, count);
|
|
}
|
|
if ( col < grid.size() - 1 && grid[row][col + 1] == CLUSTERED ) {
|
|
identify_cluster(row, col + 1, count);
|
|
}
|
|
if ( col > 0 && grid[row][col - 1] == CLUSTERED ) {
|
|
identify_cluster(row, col - 1, count);
|
|
}
|
|
if ( row > 0 && grid[row - 1][col] == CLUSTERED ) {
|
|
identify_cluster(row - 1, col, count);
|
|
}
|
|
}
|
|
|
|
void create_grid(int32_t grid_size, double probability) {
|
|
grid.assign(grid_size, std::vector<int32_t>(grid_size, 0));
|
|
for ( int32_t row = 0; row < grid_size; ++row ) {
|
|
for ( int32_t col = 0; col < grid_size; ++col ) {
|
|
if ( distribution(generator) < probability ) {
|
|
grid[row][col] = CLUSTERED;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
int32_t clusters;
|
|
std::vector<std::vector<int32_t>> grid;
|
|
|
|
inline static const int CLUSTERED = -1;
|
|
inline static const std::string GRID_CHARACTERS = ".ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
|
|
};
|
|
|
|
int main() {
|
|
const int32_t size = 15;
|
|
const double probability = 0.5;
|
|
const int32_t test_count = 5;
|
|
|
|
Grid grid(size, probability);
|
|
std::cout << "This " << size << " by " << size << " grid contains "
|
|
<< grid.cluster_count() << " clusters:" << std::endl;
|
|
grid.display();
|
|
|
|
std::cout << "\n p = 0.5, iterations = " << test_count << std::endl;
|
|
std::vector<int32_t> grid_sizes = { 10, 100, 1'000, 10'000 };
|
|
for ( int32_t grid_size : grid_sizes ) {
|
|
double sumDensity = 0.0;
|
|
for ( int32_t test = 0; test < test_count; test++ ) {
|
|
Grid grid(grid_size, probability);
|
|
sumDensity += grid.cluster_density();
|
|
}
|
|
double result = sumDensity / test_count;
|
|
std::cout << " n = " << std::setw(5) << grid_size
|
|
<< ", simulations K = " << std::fixed << result << std::endl;
|
|
}
|
|
}
|