Target audience: Intermediate

Estimated reading time: 6'

Determining the best way to link nodes is frequently encountered in network design, transport ventures, and electrical circuitry. This piece explores and showcases an efficient computation for the minimum spanning tree (MST) through the use of Prim's algorithm, which is built on tail recursion.

This article assumes a very minimal understanding of undirected graphs.

Table of contents

Note: Implementation relies on Scala 2.11.8

Overview

Each connectivity in a graph is usually defined as a weight (cost, length, time...). The purpose is to compute the schema that connects all the nodes that minimize the total weight. This problem is known as the minimum spanning tree or MST related to the nodes connected through an un-directed graph [ref 1].

Several algorithms have been developed over the last 70 years to extract the MST from a graph. This post focuses on the implementation of the Prim's algorithm in Scala.

There are many excellent tutorials on graph algorithm and more specifically on the Prim's algorithm. I recommend Lecture 7: Minimum Spanning Trees and Prim’s Algorithm [ref 2].

Let's PQ is a priority queue, a Graph G(V, E) with n vertices V and E edges w(u,v). A Vertex v is defined by

An identifier

A load factor, load(v)

A parent tree(v)

The adjacent vertices adj(v)

The Prim's algorithm can be easily expressed as a simple iterative process. It consists of using a priority queue of all the vertices in the graph and update their load to select the next node in the spanning tree. Each node is popped up (and removed) from the priority queue before being inserted in the tree.

PQ <- V(G)
foreach u in PQ
   load(u) <- INFINITY
 
while PQ nonEmpty
   do u <- v in adj(u)
      if v in PQ && load(v) < w(u,v)
      then
         tree(v) <- u
         load(v) <- w(u,v)

The Scala implementation relies on a tail recursion to transfer vertices from the priority queue to the spanning tree.

Graph definition

The first step is to define a graph structure with edges and vertices [ref 3]. The graph takes two arguments:

numVertices number of vertices

start index of the root of the minimum spanning tree

The vertex class has three attributes

id identifier (arbitrary an integer)

load dynamic load (or key) on the vertex

tree reference to the minimum spanning tree

final class Graph(numVertices: Int, start: Int = 0) {
 
  class Vertex(val id: Int, 
     var load: Int = Int.MaxValue, 
     var tree: Int = -1) 

  val vertices = List.tabulate(numVertices)(new Vertex(_))
  vertices.head.load = 0
  val edges = new HashMap[Vertex, HashMap[Vertex, Int]]

  def += (from: Int, to: Int, weight: Int): Unit = {
    val fromV = vertices(from)
    val toV = vertices(to)
    connect(fromV, toV, weight)
    connect(toV, fromV, weight)
  }


  def connect(from: Vertex, to: Vertex, weight: Int): Unit = {
    if( !edges.contains(from))
      edges.put(from, new HashMap[Vertex, Int])    
    edges.get(from).get.put(to, weight)
  }   
  // ...
}

The vertices are initialized by with a unique identifier id, and a default load Int.MaxValue and a default depth tree (lines 3-5). The Vertex class resides within the scope of the outer class Graph to avoid naming conflict. The vertices are managed through a linked list (line 7) while the edges are defined as hash maps with a map of other edges as value (line 9). The operator += add a new edge between two existing vertices with a specified load (line 11)

In most case, the identifier is a character string or a data structure. As described in the pseudo-code, the load for the root of the spanning tree is defined a 0.

The load is defined as an integer for performance's sake. It is recommended to convert (quantization) a floating-point value to an integer for the processing of very large graph, then convert back to a original format on the resulting minimum spanning tree.

The edges are defined as hash table with the source vertex as key and the hash table of destination vertex and edge weight as value.

The graph is un-directed therefore the connection initialized in the method += are bi-directional.

Priority queue

The priority queue is used to re-order the vertices and select the next vertex to be added to the spanning tree.

Note: There are many different implementation of priority queues in Scala and Java. You need to keep in mind that the Prim's algorithm requires the queue to be re-ordered after its load is updated (see pseudo-code). The PriorityQueue classes in the Scala and Java libraries do not allow elements to be removed or to be explicitly re-ordered. An alternative is to use a binary tree, red-black tree for which elements can be removed and the tree re-balanced.

The implementation of the priority has an impact on the time complexity of the algorithm. The following implementation of the priority queue is provided only to illustrate the Prim's algorithm.

class PQueue(vertices: List[Vertex]) {
   var queue = vertices./:(new PriorityQueue[Vertex])((pq, v) => pq += v)
    
   def += (vertex: Vertex): Unit = queue += vertex
   def pop: Vertex = queue.dequeue
   def sort: Unit = {}
   def push(vertex: Vertex): Unit = queue.enqueue(vertex)
   def nonEmpty: Boolean = queue.nonEmpty
}
  
type MST = ListBuffer[Int]
implicit def orderingByLoad[T <: Vertex]: Ordering[T] = Ordering.by( - _.load)

The Scala PriorityQueue class required the implicit ordering of vertices using their load (line 2). This accomplished by defining an implicit conversion of a type T with upper-bound type Vertex to Ordering[T] (line 12).

Notes:

The type T has to be a sub-class of Vertex. A direct conversion from Vertex type to Ordering[Vertex] is not allowed in Scala.
We use the PriorityQueue from the Java library as it provides more flexibility than the Scala TreeSet.

Prim's algorithm

This implementation is the direct translation of the pseudo-code presented in the second paragraph. It relies on the efficient Scala tail recursion (line 5).

def prim: List[Int] = {
  val queue = new PQueue(vertices)
   
  @scala.annotation.tailrec
  def prim(parents: MST): Unit = {
    if( queue.nonEmpty ) {
      val head = queue.pop
      val candidates = edges.get(head).get
          .filter{ 
            case(vt,w) => vt.tree == -1 && w <= vt.load
          }
 
      if( candidates.nonEmpty ) {
        candidates.foreach {case (vt, w) => vt.load = w }
        queue.sort
      }
      parents.append(head.id)
      head.tree = 1
      prim(parents)
    }
  }
  val parents = new MST
  prim(parents)
  parents.toList
}

As long as the priority queue is not empty (line 6), the next element is the priority queue is retrieved (line 7) for which is select the most appropriate candidate for the next vertex (line 8 - 11). The load of each candidate is updated (line 14) and the priority queue is re-sorted (line 15).

Although a tree set is a more efficient data structure for managing the set of vertices waiting to be weighted, it does not allow the existing priority queue to be resorted because of its immutability.

Time complexity

As mentioned earlier, the time complexity depends on the implementation of the priority queue. If E is the number of edges, and V the number of vertices:

Minimum spanning tree with linear queue: V²
Minimum spanning tree with binary heap: (E + V).LogV
Minimum spanning tree with Fibonacci heap: V.LogV

Note: See Summary of time complexity of algorithms for details.

References

[1] Introduction to Algorithms Chapter 24 Minimum Spanning Trees - T. Cormen, C. Leiserson, R. Rivest - MIT Press 1989
[2] Lecture 7: Minimum Spanning Trees and Prim’s Algorithm Dekai Wu, Department of Computer Science and Engineering - The Hong Kong University of Science & Technology
[3] Graph Theory Chapter 4 Optimization Involving Tree - V.K. Balakrishnan - Schaum's Outlines Series, McGraw Hill, 1997

Sunday, April 2, 2017

Recursive Minimum Spanning Tree in Scala

Overview

Graph definition

Priority queue

Prim's algorithm

Time complexity

References

No comments:

Post a Comment

Contact Form

Equation Editor

Popular Posts