Percolation/Mean cluster density: Difference between revisions
Content added Content deleted
m (Final improvment to code.) |
(New post.) |
||
Line 215: | Line 215: | ||
4096 0.065836 |
4096 0.065836 |
||
16384 0.065774 |
16384 0.065774 |
||
</pre> |
|||
=={{header|C++}}== |
|||
<syntaxhighlight lang="c++"> |
|||
#include <iostream> |
|||
#include <random> |
|||
#include <string> |
|||
#include <vector> |
|||
std::random_device random; |
|||
std::mt19937 generator(random()); |
|||
std::uniform_real_distribution<double> distribution(0.0F, 1.0F); |
|||
class Grid { |
|||
public: |
|||
Grid(int32_t size, double probability) { |
|||
create_grid(size, probability); |
|||
count_clusters(); |
|||
} |
|||
int32_t cluster_count() { |
|||
return clusters; |
|||
} |
|||
double cluster_density() { |
|||
return (double) clusters / ( grid.size() * grid.size() ); |
|||
} |
|||
void display() { |
|||
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(uint64_t row, uint64_t col, 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); |
|||
printf("%s%d%s%d%s%d%s%s", "This ", size, " by ", size, " grid contains ", grid.cluster_count(), " clusters:", "\n"); |
|||
grid.display(); |
|||
printf("%s%s%d%s", "\n", " p = 0.5, iterations = ", test_count, "\n"); |
|||
std::vector<int32_t> gridSizes = { 10, 100, 1'000, 10'000 }; |
|||
for ( int32_t gridSize : gridSizes ) { |
|||
double sumDensity = 0.0; |
|||
for ( int32_t test = 0; test < test_count; test++ ) { |
|||
Grid grid(gridSize, probability); |
|||
sumDensity += grid.cluster_density(); |
|||
} |
|||
double result = sumDensity / test_count; |
|||
printf("%s%5d%s%.6f%s", " n = ", gridSize, ", simulation K = ", result, "\n"); |
|||
} |
|||
} |
|||
</syntaxhighlight> |
|||
{{ out }} |
|||
<pre> |
|||
This 15 by 15 grid contains 11 clusters: |
|||
A A . B B . B B . . . . . . . |
|||
. . B B B B . B B . B B . . . |
|||
. C . . B B . B B B B . . . . |
|||
. C C . B . B B B B B B . D D |
|||
C C . . B B B B . . B . D D . |
|||
C C . . B B B . B B B . . D D |
|||
C C . . . . B . . . B . D D D |
|||
. C . E . . . . D D . . D D . |
|||
F . . . G . H . D D D D D D D |
|||
F F . F . I . F . D D . D D . |
|||
F . F F F . . F . . D D . . D |
|||
F . F . F . . F . F . D D D D |
|||
F F . . F F F F F F . D . . D |
|||
F F F F F . . F . . . D . . D |
|||
. F F . . J J . . . . D . K . |
|||
p = 0.5, iterations = 5 |
|||
n = 10, simulation K = 0.088000 |
|||
n = 100, simulation K = 0.067260 |
|||
n = 1000, simulation K = 0.066215 |
|||
n = 10000, simulation K = 0.065777 |
|||
</pre> |
</pre> |
||