Top

Computing

Published in:

02-05-2018

A parallel bio-inspried shortest path algorithm

Authors: Hilal Arslan, Murat Manguoglu

Published in: Computing | Issue 8/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Physarum polycephalum is an amoeba-like organism and is able to find the shortest path in a labyrinth. Inspired by P. polycephalum, recently, a mathematical model and an algorithm (Physarum Solver) was developed. There are, however, only sequential implementations of this algorithm. In this paper, a fast and efficient parallel Physarum Solver is proposed. The proposed algorithm requires the solution of linear systems whose coefficient matrix is a symmetric M-matrix. The solution of the linear system is the most time consuming step of the Physarum Solver which is classically handled by direct solvers without taking advantage of the fact that the coefficient matrix is an M-matrix. However, direct solvers are infeasible for solving large real-world problems. In the proposed parallel Physarum Solver, an effective parallel iterative linear solver with a parallel preconditioner for M-matrices is used. The parallel scalability, solution time, and accuracy of the proposed algorithm are presented and compared to a state-of-the-art parallel implementation of \(\varDelta \)-stepping shortest path algorithm in the Parallel Boost Graph Library. Our implementation exhibits a remarkable parallel speedup with comparable accuracy for synthetic and real world applications.

previous article Virtual network mapping considering energy consumption and availability

next article Instance launch-time analysis of OpenStack virtualization technologies with control plane network errors

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

9th DIMACS implementation challenge—shortest paths. http://www.dis.uniroma1.it/challenge9/download.shtml. Accessed Jan 2017

Boost C++ Libraries. http://www.boost.org/. Accessed Apr 2016

Erdos–Renyi graphs. http://cneurocvs.rmki.kfki.hu/igraph/doc/R/erdos.renyi.game.html. Accessed Jan 2017

Portable, Extensible Toolkit for Scientific Computing, version 3.6.3. http://www.mcs.anl.gov/petsc. Accessed Apr 2016

The Watts–Strogatz small-world model. http://cneurocvs.rmki.kfki.hu/igraph/doc/R/watts.strogatz.game.html. Accessed Jan 2017

Adamatzky A, Jones J (2010) Programmable reconfiguration of Physarum machines. Nat Comput 9(1):219–237MathSciNetMATHCrossRef

Aleksandrov L, Maheshwari A, Sack JR (2005) Determining approximate shortest paths on weighted polyhedral surfaces. J ACM 52(1):25–53MathSciNetMATHCrossRef

Awerbuch B, Berger B, Cowen L, Peleg D (2006) Near-linear time construction of sparse neighborhood covers. SIAM J Comput 28(1):263–277MathSciNetMATHCrossRef

Becchetti L, Bonifaci V, Dirnberger M, Karrenbauer A, Mehlhorn K (2013) Physarum can compute shortest paths: convergence proofs and complexity bounds. In: Fomin F, Freivalds R, Kwiatkowska M, Peleg D (eds) Automata languages and programming: 40th international colloquium and ICALP 2013 Riga and Latvia and July 8–12 and 2013 and proceedings and part II. Springer, Berlin, pp 472–483

10.

Beekman M, Latty T (2015) Brainless but multi-headed: decision making by the acellular slime mould Physarum polycephalum. J Mol Biol 427(23):3734–3743. https://doi.org/10.1016/j.jmb.2015.07.007 CrossRef

11.

Benzi M (2002) Preconditioning techniques for large linear systems: a survey. J Comput Phys 182(2):418–477MathSciNetMATHCrossRef

12.

Berman A, Plemmons RJ (1979) Nonnegative matrices in the mathematical sciences. Academic Press, New York. https://doi.org/10.1016/B978-0-12-092250-5.50002-3 MATHCrossRef

13.

Bonifaci V (2013) Physarum can compute shortest paths: a short proof. Inf Process Lett 113(1):4–7. https://doi.org/10.1016/j.ipl.2012.09.005 MathSciNetMATHCrossRef

14.

Bonifaci V, Mehlhorn K, Varma G (2012) Physarum can compute shortest paths. J Theor Biol 309:121–133MathSciNetMATHCrossRef

15.

Chaibou A, Sie O (2015) Improving global performance on GPU for algorithms with main loop containing a reduction operation: case of Dijkstra’s algorithm. J Comput Commun 3:41–54CrossRef

16.

Chakaravarthy VT, Checconi F, Petrini F, Sabharwal Y (2014) Scalable single source shortest path algorithms for massively parallel systems. In: 2014 IEEE 28th international parallel and distributed processing symposium, pp 889–901

17.

Chakrabarti D, Zhan Y, Faloutsos C (2004) R-MAT: a recursive model for graph mining. In: Proceedings of the 2004 SIAM international conference on data mining. SIAM, Philadelphia, pp 442–446

18.

Cheng Gh, Huang Tz, Cheng Xy (2006) Preconditioned Gauss–Seidel type iterative method for solving linear systems. Appl Math Mech 27(9):1275–1279MathSciNetMATHCrossRef

19.

Cherkassky B, Goldberg A, Radzik T (1996) Shortest path algorithms: theory and experimental evaluation. Math Program 73(2):129–174MathSciNetMATHCrossRef

20.

Cowen LJ, Wagner CG (2004) Compact roundtrip routing in directed networks. J Algorithms 50(1):79–95MathSciNetMATHCrossRef

21.

Crobak JR, Berry JW, Madduri K, Bader DA (2007) Advanced shortest paths algorithms on a massively-multithreaded architecture. In: 2007 IEEE international parallel and distributed processing symposium, pp 1–8

22.

Dantzig G (1963) Linear programming and extensions. Princeton University Press, PrincetonMATHCrossRef

23.

Delling D, Goldberg AV, Nowatzyk A, Werneck RF (2013) PHAST: hardware-accelerated shortest path trees. J Parallel Distrib Comput 73(7):940–952CrossRef

24.

Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1:269–271MathSciNetMATHCrossRef

25.

Dorigo M, Gambardella LM (1997) Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Trans Evol Comput 1(1):53–66CrossRef

26.

Edmonds N, Breuer A, Gregor D, Lumsdaine A (2006) Single-source shortest paths with the parallel boost graph library. In: The ninth DIMACS implementation challenge: the shortest path problem

27.

Elkin M (2001) Computing almost shortest paths. In: Proceedings of the twentieth annual ACM symposium on principles of distributed computing. ACM, New York, pp 53–62

28.

Ertl G (1998) Shortest path calculation in large road networks. Oper Res Spektrum 20(1):15–20MATHCrossRef

29.

Goldberg A, Kaplan H, Werneck R (2006) Reach for A*: efficient point-to-point shortest path algorithms. Technical report, Miami, FL. https://www.microsoft.com/en-us/research/publication/reach-for-a-efficient-point-to-point-shortest-path-algorithms/

30.

Gong M, Li G, Wang Z, Ma L, Tian D (2016) An efficient shortest path approach for social networks based on community structure. CAAI Trans Intell Technol 1(1):114–123CrossRef

31.

Gregor D, Lumsdaine A (2005) The parallel BGL: a generic library for distributed graph computations. In: Parallel object-oriented scientific computing (POOSC)

32.

Gubichev A, Bedathur S, Seufert S, Weikum G (2010) Fast and accurate estimation of shortest paths in large graphs. In: Proceedings of the 19th ACM international conference on information and knowledge management, CIKM ’10. ACM, New York, pp 499–508

33.

Hadjidimos A, Noutsos D, Tzoumas M (2003) More on modifications and improvements of classical iterative schemes for M-matrices. Linear Algebra Appl 364:253–279MathSciNetMATHCrossRef

34.

Ikeda T, Hsu MY, Imai H, Nishimura S, Shimoura H, Hashimoto T, Tenmoku K, Mitoh K (1994) A fast algorithm for finding better routes by AI search techniques. In: Vehicle navigation and information systems conference, 1994. Proceedings, pp 291–296

35.

Kepner J, Gilbert J (2011) Graph algorithms in the language of linear algebra. Society for Industrial and Applied Mathematics, Philadelphia. https://doi.org/10.1137/1.9780898719918 MATHCrossRef

36.

Khorasani F, Vora K, Gupta R (2015) PaRMAT: a parallel generator for large R-MAT graphs. https://github.com/farkhor/PaRMAT. Accessed Jan 2017

37.

Klein P (2002) Preprocessing an undirected planar network to enable fast approximate distance queries. In: Proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms, SODA ’02, pp 820–827

38.

Liang M, Gao C, Zhang Z (2017) A new genetic algorithm based on modified Physarum network model for bandwidth-delay constrained least-cost multicast routing. Nat Comput 16(1):85–98MathSciNetCrossRef

39.

Liu L, Song Y, Ma H, Zhang X (2012) Physarum optimization: a biology-inspired algorithm for minimal exposure path problem in wireless sensor networks. In: 2012 proceedings IEEE INFOCOM, pp 1296–1304

40.

Liu L, Song Y, Zhang H, Ma H (2015) Physarum optimization: a biology-inspired algorithm for the steiner tree problem in networks. IEEE Trans Comput 64:818–831MathSciNetMATHCrossRef

41.

Madduri K, Bader DA, Berry JW, Crobak J (2007) An experimental study of a parallel shortest path algorithm for solving large-scale graph instances. In: Proceedings of the meeting on algorithm engineering and experiments. Society for Industrial and Applied Mathematics, Philadelphia, pp 23–35

42.

Masi L, Vasile M (2014) A multidirectional Physarum solver for the automated design of space trajectories. In: Proceedings of the 2014 IEEE congress on evolutionary computation (CEC), pp 2992–2999. https://doi.org/10.1109/CEC.2014.6900287

43.

McSherry F, Isard M, Murray DG (2015) Scalability! But at what cost? In: Proceedings of the 15th USENIX conference on hot topics in operating systems, HOTOS 15, pp 14–14

44.

Meyer U, Sanders P (1998) \(\Delta \)-stepping: a parallel single source shortest path algorithm. In: European symposium on algorithms, pp 393–404

45.

Meyer U, Sanders P (2003) \(\Delta \)-stepping: a parallelizable shortest path algorithm. J Algorithms 49:114–152MathSciNetMATHCrossRef

46.

Miyaji T, Ohnishi I (2008) Physarum can solve the shortest path problem on Riemann surface mathematically rigorously. Int J Pure Appl Math 47:353–369MathSciNetMATH

47.

Nakagaki T, Iima M, Ueda T, Nishiura Y, Saigusa T, Tero A, Kobayashi R, Showalter K (2007) Minimum-risk path finding by an adaptive amoebal network. Phys Rev Lett 99:068,104. https://doi.org/10.1103/PhysRevLett.99.068104 CrossRef

48.

Neumann M, Plemmons RJ (1987) Convergence of parallel multisplitting iterative methods for M-matrices. Linear Algebra Appl 88:559–573MathSciNetMATHCrossRef

49.

Nguyen UT, Xu J (2007) Multicast routing in wireless mesh networks: minimum cost trees or shortest path trees? IEEE Commun Mag 45(11):72–77CrossRef

50.

Niki H, Kohno T, Morimoto M (2008) The preconditioned Gauss–Seidel method faster than the SOR method. J Comput Appl Math 219(1):59–71MathSciNetMATHCrossRef

51.

Peleg D, Ullman JD (1989) An optimal synchronizer for the hypercube. SIAM J Comput 18:740–747MathSciNetMATHCrossRef

52.

Plemmons R (1977) M-matrix characterizations. I—nonsingular M-matrices. Linear Algebra Appl 18(2):175–188MathSciNetMATHCrossRef

53.

Pohl I (1971) Bi-directional search. Mach Intell 6:124–140MATH

54.

Rheinboldt WC (1970) On M-functions and their application to nonlinear Gauss-Seidel iterations and to network flows. J Math Anal Appl 32:274–307MathSciNetMATHCrossRef

55.

Saad Y (2003) Iterative methods for sparse linear systems, 2nd edn. Society for Industrial and Applied Mathematics, PhiladelphiaMATHCrossRef

56.

Sedgewick R, Vitter J (1986) Shortest paths in Euclidean graphs. Algorithmica 1:31–48MathSciNetMATHCrossRef

57.

Sen S (2009) Approximating shortest paths in graphs. In: 3rd international workshop on algorithms and computation (WALCOM), pp 32–43

58.

Siriwardana J, Halgamuge SK (2012) Fast shortest path optimization inspired by shuttle streaming of Physarum polycephalum. In: 2012 IEEE congress on evolutionary computation, pp 1–8

59.

Tero A, Kobayashi R, Nakagaki T (2006) Physarum solver: a biologically inspired method of road-network navigation. Phys A Stat Mech Appl 363(1):115–119CrossRef

60.

Tero A, Kobayashi R, Nakagaki T (2007) A mathematical model for adaptive transport network in path finding by true slime mold. J Theor Biol 244(4):553–564MathSciNetCrossRef

61.

Thorup M (2004) Compact oracles for reachability and approximate distances in planar digraphs. J ACM 51(6):993–1024MathSciNetMATHCrossRef

62.

Tsuda S, Aono M, Gunji YP (2004) Robust and emergent Physarum logical-computing. Biosystems 73(1):45–55CrossRef

63.

Varga RS (1962) Matrix iterative analysis. Prentice-Hall, Upper Saddle RiverMATH

64.

Young DM (1971) Iterative solution of large linear systems. Academic Press, New YorkMATH

65.

Yuster R (2012) Approximate shortest paths in weighted graphs. J Comput Syst Sci 78:632–637MathSciNetMATHCrossRef

66.

Zhan FB, Noon CE (2000) A comparison between label-setting and label-correcting algorithms for computing one-to-one shortest paths. Nano communication networks 4. J Geogr Inf Decis Anal 4:1–11

67.

Zhang X, Adamatzky A, Chan FTS, Deng Y, Yang H, Yang XS, Tsompanas M, Sirakoulis G, Mahadevan S (2015) A biologically inspired network design model. Sci Rep 5:10,794CrossRef

68.

Zhang X, Adamatzky A, Yang H, Mahadaven S, Yang XS, Wang Q, Deng Y (2014) A bio-inspired algorithm for identification of critical components in the transportation networks. Appl Math Comput 248:18–27MATH

69.

Zhang X, Huang S, Hu Y, Zhang Y, Mahadevan S, Deng Y (2013) Solving 0–1 knapsack problems based on amoeboid organism algorithm. Appl Math Comput 219:9959–9970MathSciNetMATH

70.

Zhang X, Zhang X, Zhang Y, Wei D, Deng Y (2013) Route selection for emergency logistics management: a bio-inspired algorithm. Saf Sci 54:87–91CrossRef

71.

Zhang Z, Gao C, Liu Y, Qian T (2014) A universal optimization strategy for ant colony optimization algorithms based on the Physarum-inspired mathematical model. Bioinspiration Biomim 9(3):036,006CrossRef

Title: A parallel bio-inspried shortest path algorithm
Authors: Hilal Arslan
Murat Manguoglu
Publication date: 02-05-2018
Publisher: Springer Vienna
Published in: Computing / Issue 8/2019
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-018-0621-x

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 8/2019

Instance launch-time analysis of OpenStack virtualization technologies with control plane network errors

Implementation and comparison of binary thinning algorithms on GPU

Edge-based personal computing services: fall detection as a pilot study

Monitoring services in the Internet of Things: an optimization approach

Using meta-heuristics and machine learning for software optimization of parallel computing systems: a systematic literature review

Virtual network mapping considering energy consumption and availability

Premium Partner