Parallel algorithms for minimum spanning trees: Difference between revisions

Revision as of 03:13, 26 May 2019

Latest revision as of 05:49, 3 August 2025

(21 intermediate revisions by 18 users not shown)

Line 6:

If <math>G</math> is [[Glossary_of_graph_theory_terms#unweighted_graph|edge-unweighted]] every spanning tree possesses the same number of edges and thus the same weight. In the [[Glossary_of_graph_theory_terms#weighted_graph|edge-weighted]] case, the spanning tree, the sum of the weights of the edges of which is lowest among all spanning trees of <math>G</math>, is called a [[minimum spanning tree]] (MST). It is not necessarily unique. More generally, graphs that are not necessarily [[Glossary_of_graph_theory_terms#connected|connected]] have minimum spanning [[Tree_(graph_theory)#Forest|forests]], which consist of a [[Union_(set_theory)|union]] of MSTs for each [[Connected_component_(graph_theory)|connected component]].

As finding MSTs is a widespread problem in graph theory, there exist many [[Sequential_algorithm|sequential algorithms]] for solving it. Among them are [[Prim's algorithm|Prim's]], [[Kruskal's algorithm|Kruskal's]] and [[Borůvka's algorithm|Borůvka's]] algorithms, each utilising different properties of MSTs. They all operate in a similar fashion - a subset of <math>E</math> is iteratively grown until a valid MST has been discovered. However, as practical problems are often quite large (road networks sometimes have billions of edges), [[Time_complexity|performance]] is a key factor. One option of improving it is by [[Parallel algorithm|parallelising]] known [[Minimum_spanning_tree#Algorithms|MST algorithms]].<ref>{{cite book |last1=Sanders |last2=Dietzfelbinger |last3=Martin |last4=Mehlhorn |last5=Kurt |last6=Peter |title=Algorithmen und Datenstrukturen Die Grundwerkzeuge |publisher=Springer Vieweg |isbn=978-3-642-05472-3|date=2014-06-10 }}</ref>.

== Prim's algorithm ==

This algorithm utilises the [[Minimum_spanning_tree#Cut_property|cut-property]] of MSTs. A simple high-level pseudocode implementation is provided bellowbelow:

<math>T \gets \emptyset</math>

<math>S \gets \{s\}</math> where <math>s</math> is a random vertex in <math>V</math>

'''repeat''' <math>|V| - 1</math> times

find lightest edge <math>(u,v)</math> s.t. <math>u \in S</math> but <math>v \in (V \setminus S)</math>

<math>S \gets S \cup \{v\}</math>

<math>T \gets T \cup \{(u,v)\}</math>

'''return''' T

Each edge is observed exactly twice - namely when examining each of its endpoints. Each vertex is examined exactly once for a total of <math>O(n + m)</math> operations aside from the selection of the lightest edge at each loop iteration. This selection is often performed using a [[priority queue]] (PQ). For each edge at most one decreaseKey operation ([[Amortized_analysis|amortised]] in <math>O(1)</math>) is performed and each loop iteration performs one deleteMin operation (<math>O(\log n)</math>). Thus using [[Fibonacci heap|Fibonacci heaps]] the total runtime of Prim's algorithm is [[Asymptotic_computational_complexity|asymptotically]] in <math>O(m + n \log n)</math>.

Line 24:

It is important to note that the loop is inherently sequential and can not be properly parallelised. This is the case, since the lightest edge with one endpoint in <math>S</math> and on in <math>V \setminus S</math> might change with the addition of edges to <math>T</math>. Thus no two selections of a lightest edge can be performed at the same time. However, there do exist some attempts at [[Prim%27s algorithm#Parallel Algorithm|parallelisation]].

One possible idea is to use <math>O(n)</math> processors to support PQ access in <math>O(1)</math> on an [[Parallel random-access machine|EREW-PRAM]] machine,<ref>{{citation

| last1 = Brodal

| firstfirst1 = Gerth Stølting

| last2 = Träff

| first2 = Jesper Larsson

Line 38:

| pages = 4–21| doi = 10.1006/jpdc.1998.1425

| citeseerx = 10.1.1.48.3272

}}</ref>, thus lowering the total runtime to <math>O(n + m)</math>.

== Kruskal's algorithm ==

Line 44:

Kruskal's MST algorithm utilises the [[Minimum_spanning_tree#Cycle_property|cycle property]] of MSTs. A high-level pseudocode representation is provided below.

<math>T \gets</math> forest with every vertex in its own subtree

'''foreach''' <math>(u, v) \in E</math> in ascending order of weight

'''if''' <math>u</math> and <math>v</math> in different subtrees of <math>T</math>

<math>T \gets T \cup \{(u,v)\}</math>

'''return''' T

The subtrees of <math>T</math> are stored in [[Disjoint-set data structure|union-find]] data structures, which is why checking whether or not two vertices are in the same subtree is possible in amortised <math>O(\alpha(m, n))</math> where <math>\alpha(m, n)</math> is the inverse [[Ackermann|Ackermann function]]. Thus the total runtime of the algorithm is in <math>O(sort(n) + \alpha(n))</math>. Here <math>\alpha(n)</math> denotes the single-valued inverse Ackermann function, for which any realistic input yields an integer less than five.

=== Approach 1: Parallelising the sorting step ===

Line 68:

| title = The filter-kruskal minimum spanning tree algorithm

| journal = Proceedings of the Eleventh Workshop on Algorithm Engineering and Experiments (ALENEX). Society for Industrial and Applied Mathematics

| pages = 52–61| citeseerx = 10.1.1.218.2574

| pages = 52–61}}</ref><ref>{{cite web |last1=Sanders |first1=Peter |title=Algorithm Engineering script |url=http://algo2.iti.kit.edu/sanders/courses/algen17/skript.pdf |website=Algorithm Engineering KIT Homepage |accessdateaccess-date=25 February 2019}}</ref>. The basic idea behind Filter-Kruskal is to partition the edges in a similar way to [[quicksort]] and filter out edges that connect vertices that belong to the same tree in order to reduce the cost of sorting. A high-level pseudocode representation is provided below.

filterKruskal(<math>G</math>):

'''if''' <math>m <</math> KruskalThreshholdKruskalThreshold:

'''return''' kruskal(<math>G</math>)

pivot = chooseRandom(<math>E</math>)

<math>(E_{\leq}</math>, <math>E_{>}) \gets </math>partition(<math>E</math>, pivot)

<math>A \gets</math> filterKruskal(<math>E_{\leq}</math>)

<math>E_{>} \gets</math> filter(<math>E_{>}</math>)

<math>A \gets A</math> <math>\cup</math> filterKruskal(<math>E_{>}</math>)

'''return''' <math>A</math>

partition(<math>E</math>, pivot):

<math>E_{\leq} \gets \emptyset </math>

<math>E_{>} \gets \emptyset</math>

'''foreach''' <math>(u, v) \in E</math>:

'''if''' weight(<math>u, v</math>) <math>\leq</math> pivot:

<math>E_{\leq} \gets E_{\leq} \cup {(u, v)}</math>

'''else'''

<math>E_{>} \gets E_{>} \cup {(u, v)} </math>

'''return''' (<math>E_{\leq}</math>, <math>E_{>}</math>)

filter(<math>E</math>):

<math>E_{filtered} \gets \emptyset </math>

'''foreach''' <math>(u, v) \in E</math>:

'''if''' find-set(u) <math>\neq</math> find-set(v):

<math>E_{filtered} \gets E_{filtered} \cup {(u, v)}</math>

'''return''' <math>E_{filtered}</math>

Filter-Kruskal is better suited for parallelisation, since sorting, partitioning and filtering have intuitively easy parallelisations where the edges are simply divided between the cores.

Line 103 ⟶ 104:

The main idea behind Borůvka's algorithm is [[edge contraction]]. An edge <math>\{u, v\}</math> is contracted by first removing <math>v</math> from the graph and then redirecting every edge <math>\{w, v\} \in E</math> to <math>\{w, u\}</math>. These new edges retain their old edge weights. If the goal is not just to determine the weight of an MST but also which edges it comprises, it must be noted between which pairs of vertices an edge was contracted. A high-level pseudocode representation is presented below.

<math>T \gets \emptyset</math>

'''while''' <math>|V| > 01</math>

<math>S \gets \emptyset</math>

'''for''' <math>v \in V</math>

<math>S \gets S</math> <math>\cup</math> lightest <math>\{u, v\} \in E</math>

'''for''' <math>\{u, v\} \in S</math>

contract <math>\{u, v\}</math>

<math>T \gets T \cup S</math>

'''return''' T

It is possible that contractions lead to multiple edges between a pair of vertices. The intuitive way of choosing the lightest of them is not possible in <math>O(m)</math>. However, if all contractions that share a vertex are performed in parallel this is doable. The recursion stops when there is only a single vertex remaining, which means the algorithm needs at most <math>\log n</math> iterations, leading to a total runtime in <math>O(m \log n)</math>.

Line 117 ⟶ 118:

=== Parallelisation ===

One possible parallelisation of this algorithm<ref>{{cite web |last1=Sanders |first1=Peter |title=Parallel Algorithms script |url=https://algo2.iti.kit.edu/sanders/courses/paralg18/skript.pdf |website=Parallel Algorithms KIT Homepage |accessdateaccess-date=25 February 2019}}</ref><ref>{{cite web |last1=Zadeh |first1=Reza |title=Distributed Algorithms and Optimization |url=https://stanford.edu/~rezab/dao/notes/lecture06/cme323_lec6.pdf |website=Distributed Algorithms and Optimization Stanford University Homepage |accessdateaccess-date=25 February 2019}}</ref><ref>{{cite journalbook |last1=Chun |first1=Sun |last2=Condon |first2=Anne |title=Proceedings of International Conference on Parallel Processing |chapter=Parallel implementation of Bouvka's minimum spanning tree algorithm |journal=Proceedings of International Conference on Parallel Processing |date=1996 |pages=302–308 |doi=10.1109/IPPS.1996.508073 |urlisbn=https://ieeexplore.ieee.org/document/5080730-8186-7255-2 |accessdates2cid=2512710022 February 2019}}</ref> yields a [[Polylogarithmic_function|polylogarithmic]] time complexity, i.e. <math>T(m, n, p) \cdot p \in O(m \log n)</math> and there exists a constant <math>c</math> so that <math>T(m, n, p) \in O(\log^c m)</math>. Here <math>T(m, n, p)</math> denotes the runtime for a graph with <math>m</math> edges, <math>n</math> vertices on a machine with <math>p</math> processors. The basic idea is the following:

'''while''' <math>|V| > 1</math>

find lightest incident edges // <math>O(\frac{m}{p} + \log n + \log p)</math>

assign the corresponding subgraph to each vertex // <math>O(\frac{n}{p} + \log n)</math>

contract each subgraph // <math>O(\frac{m}{p} + \log n)</math>

The MST then consists of all the found lightest edges.

Line 134 ⟶ 135:

Now each processor determines the lightest edge incident to each of its vertices.

<math>v \gets</math> find(<math>\frac{i m}{p}</math>, <math>\Gamma</math>)

'''for''' <math>e \gets \frac{i m}{p}; e < \frac{(i+1) m}{p} - 1; e++</math>

'''if''' <math>\Gamma[v+1] = e </math>

<math>v++</math>

'''if'''<math>c[e] < c[pred[v]]</math>

<math>pred[v] \gets e</math>

Here the issue arises some vertices are handled by more than one processor. A possible solution to this is that every processor has its own <math>prev</math> array which is later combined with those of the others using a reduction. Each processor has at most two vertices that are also handled by other processors and each reduction is in <math>O(\log p)</math>. Thus the total runtime of this step is in <math>O(\frac{m}{p} + \log n + \log p)</math>.

Line 147 ⟶ 148:

Observe the graph that consists solely of edges collected in the previous step. These edges are directed away from the vertex to which they are the lightest incident edge. The resulting graph decomposes into multiple weakly connected components. The goal of this step is to assign to each vertex the component of which it is a part. Note that every vertex has exactly one outgoing edge and therefore each component is a pseudotree - a tree with a single extra edge that runs in parallel to the lightest edge in the component but in the opposite direction. The following code mutates this extra edge into a loop:

'''parallel forAll''' <math>v \in V</math>

<math>w \gets pred[v]</math>

'''if''' <math>pred[w] = v \land v < w</math>

<math>pred[v] \gets v</math>

Now every [[Glossary_of_graph_theory_terms#weakly_connected|weakly connected]] component is a directed tree where the root has a [[Glossary_of_graph_theory_terms#loop|loop]]. This root is chosen as the representative of each component. The following code uses doubling to assign each vertex its representative:

'''while''' <math>\exists v \in V: pred[v] \neq pred[pred[v]]</math>

'''forAll''' <math>v \in V</math>

<math>pred[v] \gets pred[pred[v]]</math>

Now every subgraph is a [[Glossary_of_graph_theory_terms#star|star]]. With some advanced techniques this step needs <math>O(\frac{n}{p} + \log n)</math> time.

Line 164 ⟶ 165:

In this step each subgraph is contracted to a single vertex.

<math>k \gets</math> number of subgraphs

<math>V' \gets \{0, \dots , k-1\}</math>

find a bijective function <math>f:</math> star root <math>\rightarrow \{0, \dots, k-1\}</math>

<math>E' \gets \{(f(pred[v]), f(pred[w]), c, e_{old}): (v, w) \in E \land pred[v] \neq pred[w]\}</math>

Finding the bijective function is possible in <math>O(\frac{n}{p} + \log p)</math> using a prefix sum. As we now have a new set of vertices and edges the adjacency array must be rebuildrebuilt, which can be done using Integersort on <math>E'</math> in <math>O(\frac{m}{p} + \log p)</math> time.

=== Complexity ===

Each iteration now needs <math>O(\frac{m}{p} + \log n)</math> time and just like in the sequential case there are <math>\log n</math> interationsiterations, resulting in a total runtime of <math>O(\log n(\frac{m}{p} + \log n))</math>. If <math>m \in \Omega(p \log^2 p)</math> the efficiency of the algorithm is in <math>\Theta(1)</math> and it is relatively efficient. If <math>m \in O(n)</math> then it is absolutely efficient.

== Further algorithms ==

Line 192 ⟶ 193:

| volume = 48

| year = 2001| citeseerx = 10.1.1.32.1554

| s2cid = 1778676

}}</ref><ref>{{citation

| last1 = Pettie | first1 = Seth

Line 203 ⟶ 205:

| volume = 31

| year = 2002| url = http://www.eecs.umich.edu/~pettie/papers/sicomp-randmst.pdf

}}</ref>. Bader undand Cong presented an MST-algorithm, that was five times quicker on eight cores than an optimal sequential algorithm.<ref>{{citation

| last1 = Bader

| first1 = David A.

| author1-link = David A. Bader (computer scientist)

| last2 = Cong

| first2 = Guojing

Line 215 ⟶ 217:

| title = Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs

| volume = 66

| year = 2006}}</ref>.

Another challenge is the External Memory model - there is a proposed algorithm due to Dementiev et al. that is claimed to be only two to five times slower than an algorithm that only makes use of internal memory<ref>{{citation

| last1 = Dementiev
| first1 = Roman

| last2 = Sanders
| first2 = Peter

| last3 = Schultes
| first3 = Dominik

| last4 = Sibeyn
| first4 = Jop F.

| contribution = Engineering an external memory minimum spanning tree algorithm

| pages = 195–208

| title = Proc. IFIP 18th World Computer Congress, TC1 3rd International Conference on Theoretical Computer Science (TCS2004)

| url = http://algo2.iti.kit.edu/dementiev/files/emst.pdf

| year = 2004}}.</ref>

| access-date = 2019-05-24

| archive-date = 2011-08-09

| archive-url = https://web.archive.org/web/20110809075049/http://algo2.iti.kit.edu/dementiev/files/emst.pdf

| url-status = dead

}}.</ref>

== References ==