The Comparison of DFS and BFS Methods on 2D Ising Model

Abstract

We consider Deep-First Search and Breadth-First Search graph traversal algorithms for finding clusters boundaries on 2D Ising model. We implement and compare these algorithms at different cluster density on lattice. It is shown that Breadth-First Search method has a huge advantage at clusters search on the lattice.

Introduction

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. visited vertices are added to the new set of "advanced" vertices processed in the next step. Initially, only the source node enters the set of “advanced” vertices, from which the traversal begins.

This algorithm has similar complexity to DFS - O(|V| + |E|).

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.

Comparison

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-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.

Conclusion

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.

Acknowledgements

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).

References

1. Tarasevich , Yu.Yu.: Percolation: Theory, Applications, Algorithms // Moscow, URSS Publisher. 64 p. ( 2002 )

2. Tiwari , P.: An efficient parallel algorithm for shifting the root of a depth first spanning tree . // Journal of Algorithms - Volume 7 , Issue 1 - Pp. 105 - 119 . ( 1986 )

3. Awerbuch , B. : A new distributed Depth-First-Search algorithm // Information Processing Letters. - Volume 20 , Issue 3 - Pages 147- 150 ( 1985 )

4. Mohan , B. Sharma; Sitharama S. Iyengar; Narasimha K. Mandyam , An efficient distributed depth-first-search algorithm // Information Processing Letters 32 . - Pages 183- 186 ( 1989 )

5. Moore , E. F. : The shortest path through a maze // Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2-5 April 1957 ) - Harvard University Press. - Vol. 2 . - P. 285 - 292 . - 345 p. (Annals of the Computation Laboratory of Harvard University; Vol. 30 ) ( 1959 )

6. Lee , C. Y. : An algorithm for path connection and its applications . IRE Transactions on Electronic Computers, EC10(3) , pp. 346 - 365 ( 1961 )

7. Makki , S.A.M.: Efficient distributed breadth-first search algorithm // Computer Communications ( 1996 )

8. Yunzhou , Zhu; To-Yat, Cheung: A new distributed breadth-first-search algorithm // Elsevier B.V. ( 1987 )

9. Awerbuch , B. , Gallager , R.: Distributed BFS algorithms // Foundations of Computer Science // 26th Annual Symposium on Foundations of Computer Science ( 1985 )

10. Shimon , E.: Graph Algorithms. // W. H. Freeman & Co. New York, NY, USA ( 1979 )

11. Levitin , A. : Introduction to the Design and Analysis of Algorithms // Addison Wesley, 592 pages. ( 2011 )

12. Kocay , W. , Kreher , D.L. : Graphs , Algorithms, and Optimization // CRC Press. ( 2004 )

13. Richard , J. Trudeau: Introduction to Graph Theory // Dover Publications Inc., NY ( 1993 )

14. Khee Meng Koh , F. M. , Dong , Dong Fengming, Tay, Eng Guan: Introduction to Graph Theory: Solutions Manual// World Scientific. ( 2006 )

15. Cui , Zehan, Chen, Licheng, Chen, Mingyu, Bao, Yungang, Huang, Yongbing, Lv, Huiwei: Evaluation and Optimization of Breadth-First Search on NUMA Cluster. // IEEE International Conference on Cluster Computing - CLUSTER 2012 - Pages 438-448 . ( 2012 )

16. Youzou Miyadera , Koushi Anzai, Hiroshi Unno, Takeo Yaku: Depth-first layout algorithm for trees // Springer Science & Business Media, ( 2013 .)

17. Cidon , I. : Yet another distributed depth-first-search algorithm // Inf . Process. Lett. 26 , 6 (January) - Pages 301 - 305 . ( 1988 )