Assignment in CS312

Posted: August 7, 2012 in Assignments, Requirements, etc about my course

#1.)

Minimum Spanning Trees

This minimum spanning tree algorithm was first described by Kruskal in 1956 in the same paper where he rediscovered Jarnik’s algorithm. This algorithm was also rediscovered in 1957 by Loberman and Weinberger, but somehow avoided being renamed after them. The basic idea of the Kruskal’s algorithms is as follows: scan all edges in increasing weight order; if an edge is safe, keep it (i.e. add it to the set A).

Spanning trees

A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A graph may have many spanning trees; for instance the complete graph on four vertices

    o—o

    |\ /|

    | X |

    |/ \|

    o—o

has sixteen spanning trees:

    o—o    o—o    o   o    o—o

    |   |    |        |   |        |

    |   |    |        |   |        |

    |   |    |        |   |        |

    o   o    o—o    o—o    o—o

 

    o—o    o   o    o   o    o   o

     \ /     |\ /      \ /      \ /|

      X      | X        X        X |

     / \     |/ \      / \      / \|

    o   o    o   o    o—o    o   o

 

    o   o    o—o    o   o    o—o

    |\  |       /     |  /|     \

    | \ |      /      | / |      \

    |  \|     /       |/  |       \

    o   o    o—o    o   o    o—o

 

    o—o    o   o    o   o    o—o

    |\       |  /      \  |       /|

    | \      | /        \ |      / |

    |  \     |/          \|     /  |

    o   o    o—o    o—o    o   o

Minimum spanning trees

Now suppose the edges of the graph have weights or lengths. The weight of a tree is just the sum of weights of its edges. Obviously, different trees have different lengths. The problem: how to find the minimum length spanning tree?

This problem can be solved by many different algorithms. It is the topic of some very recent research. There are several “best” algorithms, depending on the assumptions you make:

  • A randomized algorithm can solve it in linear expected time. [Karger, Klein, and Tarjan, "A randomized linear-time algorithm to find minimum spanning trees", J. ACM, vol. 42, 1995, pp. 321-328.]
  • It can be solved in linear worst case time if the weights are small integers. [Fredman and Willard, "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", 31st IEEE Symp. Foundations of Comp. Sci., 1990, pp. 719--725.]
  • Otherwise, the best solution is very close to linear but not exactly linear. The exact bound is O(m log beta(m,n)) where the beta function has a complicated definition: the smallest i such that log(log(log(…log(n)…))) is less than m/n, where the logs are nested i times. [Gabow, Galil, Spencer, and Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, vol. 6, 1986, pp. 109--122.]

These algorithms are all quite complicated, and probably not that great in practice unless you’re looking at really huge graphs. The book tries to keep things simpler, so it only describes one algorithm but (in my opinion) doesn’t do a very good job of it. I’ll go through three simple classical algorithms (spending not so much time on each one).

 

#2.)

Kruskal’s Algorithm, as described in CLRS, is directly based on the generic MST algorithm. It builds the MST in forest. Initially, each vertex is in its own tree in forest. Then, algorithm consider each edge in turn, order by increasing weight. If an edge (u, v) connects two different trees, then (u, v) is added to the set of edges of the MST, and two trees connected by an edge (u, v) are merged into a single tree on the other hand, if an edge (u, v) connects two vertices in the same tree, then edge (u, v) is discarded.

A little more formally, given a connected, undirected, weighted graph with a function w : E → R.

  • Starts with each vertex being its own component.
  • Repeatedly merges two components into one by choosing the light edge that connects them (i.e., the light edge crossing the cut between them).
  • Scans the set of edges in monotonically increasing order by weight.
  • Uses a disjoint-set data structure to determine whether an edge connects vertices in different components.
  • Start with an empty set A, and select at every stage the shortest edge that has not been chosen or rejected, regardless of where this edge is situated in the graph.
  • KRUSKAL(V, E, w)
  • A ← { }           ▷ Set A will ultimately contains the edges of the MST
    for each vertex v in V
        do MAKE-SET(v)
    sort E into nondecreasing order by weight w
    for each (u, v) taken from the sorted list
        do if FIND-SET(u) = FIND-SET(v)
            then A ← A ∪ {(u, v)}
                UNION(u, v)
    return A

 

Minimum Spanning Tree: Kruskal’s Algorithm

We studied disjoint sets in the previous exercise. In today’s exercise we use disjoint sets to implement Kruskal’s algorithm to find the minimum spanning tree of a graph.

A graph is a generalized tree in which vertices may be connected by edges in any configuration. Edges may be directed (from one vertex to another) or undirected, and may be weighted or unweighted. On an undirected weighted graph, a spanning tree is a collection of edges that connects all vertices, and a minimum spanning tree has the lowest total edge-weight of all possible spanning trees. A minimum spanning tree always has one less edge than there are vertices in the graph.

Joseph Kruskal developed the following algorithm for determining the minimum spanning tree in 1956, where V is the set of vertices and E is the set of weighted edges:

  • Create a disjoint set in which each vertex is a singleton partition.
  • Loop over the edges in order by increasing weight
    • If the current edge connects two unconnected partitions
      • Add the edge to the minimum spanning tree
      • Merge the two partitions
    • If the spanning tree is complete, return it, otherwise go to the next-larger edge

Your task is to write a program that implements Kruskal’s algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

 

 

#3.)

“Minimum Spanning Tree: Kruskal’s Algorithm”

  1. Stanley said

ad-hoc Josl version:

-include myhelpers.j
-include list.j

-variable ungrouped-nodes grouped-nodes ungrouped-edges grouped-edges is-first

# ( — i:max-val)
max-int
1 63 <two-chars
0 over at chr
swap 1 swap at chr

# (b:x b:y — b:z)
xor?
not if
# if not y, return b
else
not # if y, return not b
end

# (s:edge-name)
is-ungrouped?
>two-chars
ungrouped-nodes @ has-key?
swap ungrouped-nodes @ has-key?
xor? is-first @ or?

# ( — s:min-name i:min-dist)
min-ungrouped-edge
“none” max-int # (min-name min-dist)
ungrouped-edges @ keys each
dup ungrouped-edges @ @ # (min-name min-dist cur-name cur-dist)
over is-ungrouped?
if
dup 3 pick # (min-name min-dist cur-name cur-dist cur-dist min-dist)
two-chars # (min-name min-dist first-char second-char)
group-a-node
group-a-node # (min-name min-dist)
group-an-edge # ()
# stack-show

# ( — )
print-all
“ungrouped-nodes: ” print ungrouped-nodes @ printlist “” println
“grouped-nodes: ” print grouped-nodes @ printlist “” println
“ungrouped-edges: ” print ungrouped-edges @ printlist “” println
“grouped-edges: ” print grouped-edges @ printlist “” println

# (d:acc x:val s:key –)
d, 2 pick !

main
1 is-first !
dict ungrouped-nodes !
dict grouped-nodes !
dict ungrouped-edges !
dict grouped-edges !

ungrouped-nodes @ 1 “A” d, 1 “B” d,
1 “C” d, 1 “D” d, 1 “E” d, 1 “F” d, 1 “G” d,
ungrouped-nodes !
stack-show

ungrouped-edges @ 5 “AD” d, 7 “AB” d, 9 “BD” d, 8 “BC” d,
5 “CE” d, 7 “BE” d, 15 “DE” d, 6 “DF” d, 8 “EF” d, 9 “EG” d, 11 “FG” d,
ungrouped-edges !
stack-show

while ungrouped-nodes @ len 0 >
do
min-ungrouped-edge # (s:min-name i:min-dist)
group-edge
end
print-all

 Image

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s