Minimum spanning tree
« Thursday, September 12, 2013 »

Kruskal Prim Scheme

For a school project, we had to implement the kruskal and prim algorithm. Both algorithms are well explained in wikipedia and other sites. I based my kruskal implementation on the python implementation that can be found here.

http://programmingpraxis.com/2010/04/06/minimum-spanning-tree-kruskals-algorithm/

I implemented a disjoint set using hashtable in scheme like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
(define (ds-add self item)
  (hash-table-set! self item item))

; Find the real parent of an item
; by default each item is the root of its own tree
; but after doing some unions it should point to an other
; parent
(define (ds-find self item)
  (let ((parent (hash-table-ref self item)))
    (if (equal? parent item)
      (begin
        (hash-table-set! self item parent)
        parent)
      (ds-find self parent))))

; Change the parent of one of the two items passed as
; parameters
(define (ds-union self item1 item2)
  (hash-table-set! self item2 (hash-table-ref self item1)))

The kruskal algorithm look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
; Kruskal algorithm is done here
(define (kruskal nodes edges)
  ; Loop that will check each element in the graph and add them
  ; or not to the shortest path
  (define (kruskal-forest forest result edges)
    ; Get both node of the current edge
    (let* ((item (car edges))
           (t1 (ds-find forest (list-ref item 1)))
           (t2 (ds-find forest (list-ref item 2))))
      (if (null? (cdr edges))
        ; If there is no more edges we return the result set
        result
        (if (equal? t1 t2)
          ; We cannot add item to our result set if both
          ; nodes are in the same tree...
          ;
          ; skip to the next edge if both nodes are in the tree
          (kruskal-forest forest result (cdr edges))
          ; or append item to the set otherwise and move to the next
          ; edge
          (begin
            (ds-union forest t1 t2)
            (kruskal-forest forest (append result (list item)) (cdr edges)))))))

  ; Sort our edges by increasing weight
  (sort-nodes edges)
  (let ((forest (make-hash-table)) (mst (list)))
    ; Fill our DisjointSet with all nodes. Each
    ; nodes become an independent tree pointing to itself
    ; and at the end we should have only one tree
    (fill-forest forest nodes)
    ; Loop over all edges to be added to the result set and return
    ; when there is no more edges to watch
    (kruskal-forest forest mst edges)))

The comments in the code should be enough to understand how it works. Since I'm not experienced enough in scheme, i'm pretty sure that it could be optimized or rewritten simply. This code could make use of for-each loop.

The following sample is my implementation of the prim algorithm.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
; Check of tree of a contains b
; Check if both tree roots are the same
(define (contains forest a b)
  (let ((root (ds-find forest a))
        (node (ds-find forest b)))
    (equal? root node)))

; Get first edge in the list of edges that has
; at least one node in the tree but not both
; it returns the first match
(define (get-edge forest root edges)
  (find (lambda (edge)
    (let ((nodeA (list-ref edge 1))
          (nodeB (list-ref edge 2)))
      (and (not (contains forest nodeA nodeB))
           (or (contains forest root nodeA)
               (contains forest root nodeB)))))
    edges))

; Prim algorithm we have to copy
(define (prim nodes edges)
  (define (prim-forest forest result root edges)
    (let ((edge (get-edge forest root edges)))
      ; Get first possible edge in the edge list
      ; if there is no edge, it means we might have added
      ; all edges to the tree.
      ; edges aren't removed from the list might get slow with big
      ; graphs but should be good enough for small graphs since
      ; we don't allocate/deallocate memory
      (if edge
        (begin
            ; if edge is found we join it to our forest using the root
            ; as root
            (ds-union forest root (list-ref edge 1))
            (ds-union forest root (list-ref edge 2))
            ; Recurse for new edges and append the current edge to the results
            (prim-forest forest (append result (list edge)) root edges))
        ; Otherwise we return the result
        result)))

  ; Code starts here
  ; Sort our edges by increasing weights
  (sort-nodes edges)
  (let ((forest (make-hash-table)) (mst (list)) (root (car nodes)))
    ; Fill our forest
    (fill-forest forest nodes)
    ; Find our results
    (prim-forest forest mst root edges)))

The main difference between my algorithm and the original one is that I don't remove edges from the edges' set. I instead add them to the disjoint set. I check for the presence of one of the nodes in the disjoint set and that both nodes aren't present in the main tree.

I guess that it could be slightly slower for big graphs. It would walk over all (n) elements in the edges' set. That said, having to change the list might require scheme to copy or do more work editing the list than just skiping objects present in the list but not matching the predicate.

The source code is present on github here. The code in the repository could get changed if I find a better way to do it. So check it out.

https://github.com/llacroix/Scheme-Graph-Kruskal-Prim

comments powered by Disqus

Copyright © 2015 Loïc Faure-Lacroix