The theory of percolation is used in physics, chemistry, and other fields to describe the emergence of connected structures (clusters) in random environments consisting of individual elements [1]. In order to study various effects within the framework of the percolation theory, the tools are needed that make it possible to quickly and accurately determine clusters by given characteristics. Due to the very large number of splits into clusters, speeding up the process of finding such even by a small value will give a significant increase in the calculation speed of the system as a whole. Therefore, effective tools are needed to search for clustering, the average number of nodes in a cluster, the distribution of clusters by size, the appearance of an infinite cluster and the proportion of its constituent nodes, as well as the accumulation of statistics across clusters. In this paper, the authors compare the effectiveness of two different approaches to finding clusters on the example of the two-dimensional Ising model.
A depth search version was explored in the 19th century by the French mathematician Charles Pierre Tremo as a strategy for solving labyrinths. This is called the Tremo algorithm. The Tremo algorithm is an effective method for finding a way out of a maze that requires drawing lines on the floor to mark the path, and is guaranteed to work for all mazes that have well-defined passages. In fact, this algorithm, which was discovered in the 19th century, was used about a hundred years later as the foundation for a modern depth-first search algorithm [2][3][4].
The depth search algorithm is very simple. First consider the starting node. Randomly select one of the neighbors of this node and go there. If this node has neighbors, arbitrarily choose one of them and go there if we have not visited this node yet. And we simply repeat this process until one of two conditions occurs. If we reach the end node, we complete the algorithm and report success. If we reach the site only with those neighbors which we have already visited, or there are no neighbors at all, we go back one step and visit one of the neighbors that we did not visit last time.
This algorithm is called depth search, because we always give preference to finding the deepest node we know about. If there are connections, they are broken arbitrarily, but as soon as we break our first connection (choosing which of the neighbors of the initial node to explore first), we will not try to look for other neighbors of the starting node until the first neighbor (and all of its neighbors) have been fully studied.
In the sequential case, the algorithm has algorithmic complexity O(|V| + |E|), where |V| -number of vertices in the graph, |E| -number of edges in the graph.
A breadth search was formally proposed by E. F. Moore [5] in the context of a search for a path through the labyrinth in 1959. Lee [6] independently discovered the same algorithm in the context of PCB conductor layout in 1961. A breadth-first search allows you to calculate the shortest distances (in terms of the number of edges) from a selected vertex of a directed graph to all other vertices, and/or build a root directional tree which distances coincide with the distances in the original graph. In addition, the breadth search allows us to solve the task of verifying the reachability (if there are paths between the vertex source and the rest of the vertices of the graph) [7,8,9].
The algorithm is based on traversing the vertices of the graph "by layers". At each step, there are many "advanced" vertices, for which adjacent ones are checked whether they belong to those that have not yet been visited. Still not The breadth-first search algorithm is similar to the DFS algorithm, with the only difference that nodes are placed not in the stack, but in the queue. In this case, the principle of FIFO will be applied -Fist In First Out. The algorithm can be used to find the shortest path between two nodes.
The effect of the BFS on the example of a cluster search in the lattice model is shown on Figure 3.
The fundamental difference between trees and graphs (which makes a difference in the implementation of DFS / BFS) is that there are no cycles in the trees. In graph theory, there is a cycle in any graph where you can leave a node and go through the graph back to that node. Non-directed graphs always contain loops, because you can simply move between any two neighbors. There is one exception to this rule: a graph without edges [10][11][12][13][14]. But this sort of graphs won't be discussed in this article.
Most BFS algorithms perform an abbreviated DFS before traversing each adjacency list, placing this result in a queue, which is then bypassed. For this reason, when used in trees, it is twice as slow as DFS. However, the advantage is that if you are looking for close neighbors, BFS is faster than DFS [15].
An important factor when choosing an algorithm for implementation on a high-performance hardware is the simplicity and efficiency of parallelization, to get all the benefits provided by the cluster. The implementation of the breadth-first search algorithm allows you to simply parallelize the program, with a greater effect than a parallel algorithm for depth-first search.
The difference between depth-first search and breadth-first search is that (in the case of an undirected graph) the result of the depth-first search algorithm is a certain route, following which you can go around all the graph vertices accessible from the initial vertex [16]. In this way, it is fundamentally different from the breadth-first search, where many vertices are simultaneously processed, and only one vertex is processed in the depth-first search at each moment of the algorithm execution.
On the other hand, the DFS does not find the shortest paths, but it is applicable in situations where the graph is not completely known, but is being investigated by some automated device [17].
To compare these two algorithms, the program was created on the C++. The algorithms were tested on a square lattice of the two-dimensional Ising model, where temperature is a randomizing factor, i.e., at low temperatures, the system is completely ordered. To calculate the size of the maximum cluster, the number of spins was set as N = 100x100, 300x300, 500x500, 700x700, 1000x1000, 2000x2000. The spins were clustered by orientation. Calculations were carried out for one stream in a supercomputer cluster. Several experiments were conducted. In the first experiment, a low-temperature situation was modeled, with all spins of the system entering the cluster. The second experiment was conducted near the phase transition temperature 𝑇 𝑐 = 2.269, where the maximum cluster of codirected spins begins to appear, i.e., it is large, but not all spins are included in it. In the third experiment, the lattice is completely randomized and consists of a set of small clusters of codirectional spins.
In this paper, algorithms were considered for finding clustering, the average number of nodes in a cluster, the size distribution of clusters, and the appearance of an infinite cluster. We considered breadth-first search and depth-first search traversing algorithms. A program was also written to compare two algorithms within the framework of the conditions we are interested in. On the basis of the obtained results, it can be concluded that when choosing an algorithm for searching clusters, one should use a wide search algorithm due to its advantage in execution speed on a graph and a simpler parallelization implementation, which is of great importance for supercomputer calculations. And it will help in further studies of ferromagnetic and antiferromagnetic spin models.
The research was carried out within the state assignment of FASO of Russia No. 075-00400-19-01. Computational resources provided by FEFU supercomputer cluster (cluster.dvfu.ru) and Shared Facility Center "Data Center of FEB RAS" (Khabarovsk, Russia).