Minimum Spanning Tree
Given a connected weighted graph with a weight function assigning to each edge its weight , its minimum spanning tree is a graph such that , is a tree (i.e., a connected graph without cycles) and is minimum possible among such trees. The figure shows an example of a connected weighted graph and its minimum spanning tree.
Your task is to implement an algorithm computing the minimum spanning tree, i.e., a function returning for a given connected weighted graph the subset of edges in the minimum spanning tree. There are various greedy algorithms computing the minimum spanning tree. You can use, for instance, use Jarnik's algorithm, whose pseudocode is below.
vertices = [list of graph vertices]
edges = [list of graph edges]
covered = [v0] # select an arbitrary vertex as the initial one
tree_edges = []
until covered == vertices:
find the minimum-weight edge e=(u,v) connecting a vertex u in covered
with a vertex v not in covered
add v to covered
add e to tree_edges
return tree_edgesRacket
In Scheme, implement a function (minimum-spanning-tree gr) that accepts a connected weighted graph gr and returns a list of edges forming the minimum spanning tree. The graph and weighted edges are represented by the following structures:
(struct edge (u v weight) #:transparent)
(struct graph (nodes edges) #:transparent)Your file has to be called spanning-tree.rkt, provide the function minimum-spanning-tree and the above structures so it should start like this:
#lang racket
(provide minimum-spanning-tree (struct-out edge) graph)
(struct edge (u v weight) #:transparent)
(struct graph (nodes edges) #:transparent)
; your code goes hereExample
The graph from the figure is represented as follows:
(define gr (graph '(A B C D E F)
(list (edge 'A 'B 1)
(edge 'D 'E 4)
(edge 'E 'F 7)
(edge 'A 'D 5)
(edge 'B 'E 2)
(edge 'C 'F 5)
(edge 'D 'B 6)
(edge 'E 'C 4)
(edge 'A 'E 3))))
> (minimum-spanning-tree gr)
(list (edge 'C 'F 5) (edge 'E 'D 4) (edge 'E 'C 4)
(edge 'B 'E 2) (edge 'A 'B 1))Note that the structure (edge x y w) represents a bidirectional edge so it can be used in Jarn'ik's algorithm as (x,y) and also as (y,x).
The returned list of edges might be ordered arbitrarily. Each edge might be ordered arbitrarily as well. For instance, it does not matter if your output contains (edge 'C 'F 5) or (edge 'F 'C 5). However, do not include both variants in your output.
Hint
To find the minimum-weight edge, you may want to sort a list of edges by their weight. This can be done by the function sort allowing sorting w.r.t. a given comparing function, e.g.,
> (sort (list (edge 'a 'b 3) (edge 'b 'c 1) (edge 'c 'a 2))
(lambda (e1 e2) (< (edge-weight e1) (edge-weight e2))))
(list (edge 'b 'c 1) (edge 'c 'a 2) (edge 'a 'b 3))Solution
#lang racket
(provide minimum-spanning-tree graph edge)
(struct edge (u v weight) #:transparent)
(struct graph (nodes edges) #:transparent)
(define gr (graph '(1 2 3 4) (list (edge 1 2 10) (edge 1 3 20) (edge 1 4 30) (edge 2 4 20) (edge 3 4 20))))
(define gr2 (graph '(A B C D E F)
(list (edge 'A 'B 1)
(edge 'D 'E 4)
(edge 'E 'F 7)
(edge 'A 'D 5)
(edge 'B 'E 2)
(edge 'C 'F 5)
(edge 'D 'B 6)
(edge 'E 'C 4)
(edge 'A 'E 3))))
(define (reverse-edge e)
(match e
[(edge u v w) (edge v u w)]))
(define (reverse-edges gr)
(graph (graph-nodes gr)
(append (graph-edges gr) (map reverse-edge (graph-edges gr)))))
(define (find-edge edges covered uncovered)
(car (sort (filter (lambda (e)
(and (member (edge-u e) covered)
(member (edge-v e) uncovered)))
edges)
(lambda (e1 e2) (< (edge-weight e1) (edge-weight e2))))))
(define (iter gr covered uncovered tree-edges)
(if (null? uncovered)
tree-edges
(let* ([e (find-edge (graph-edges gr) covered uncovered)]
[v (edge-v e)])
(iter gr (cons v covered) (remove v uncovered) (cons e tree-edges)))))
(define (minimum-spanning-tree gr)
(let* ([enriched-gr (reverse-edges gr)]
[nodes (graph-nodes gr)]
[covered (list (car nodes))]
[uncovered (cdr nodes)])
(iter enriched-gr covered uncovered '())))Haskell
In Haskell, we represent the weighted graph and edges by the following types:
data Edge a b = Edge { u :: a,
v :: a,
weight :: b } deriving (Eq,Show)
data Graph a b = Graph { nodes :: [a],
edges :: [Edge a b] } deriving ShowImplement a function minSpanningTree :: (Eq a, Ord b) => Graph a b -> [Edge a b] that accepts a connected weighed graph and returns a list of edges from the minimum spanning tree.
Example
gr :: Graph Char Int
gr = Graph{ nodes = ['A'..'F'],
edges = [Edge 'A' 'B' 1,
Edge 'D' 'E' 4,
Edge 'E' 'F' 7,
Edge 'A' 'D' 5,
Edge 'B' 'E' 2,
Edge 'C' 'F' 5,
Edge 'D' 'B' 6,
Edge 'E' 'C' 4,
Edge 'A' 'E' 3] }
> minSpanningTree gr
[Edge {u = 'C', v = 'F', weight = 5},Edge {u = 'E', v = 'D', weight = 4},
Edge {u = 'E', v = 'C', weight = 4},Edge {u = 'B', v = 'E', weight = 2},
Edge {u = 'A', v = 'B', weight = 1}]The returned list of edges might be ordered arbitrarily. Each edge might be ordered arbitrarily as well. For instance, it does not matter if your output contains Edge {u='C', v='F', weight=5} or Edge {u='F', v='C', weight=5}. However, do not include both variants in your output.
Your file has to be called SpanningTree.hs and must export the function minSpanningTree and the data types Graph a b, Edge a b so it should start like this:
module Task4 (minSpanningTree, Graph (..), Edge (..)) where
import Data.List -- for sortOn
data Edge a b = Edge { u :: a,
v :: a,
weight :: b } deriving (Eq,Show)
data Graph a b = Graph { nodes :: [a],
edges :: [Edge a b] } deriving Show
-- your code goes hereHint
To find the minimum-weight edge, you may want to sort a list of edges by their weight. This can be done by the function sortOn :: :: Ord b => (a -> b) -> [a] -> [a] provided by Data.List. Below is an example.
import Data.List
> sortOn weight [Edge 'A' 'B' 4, Edge 'B' 'C' 3, Edge 'C' 'A' 1]
[Edge {u = 'C', v = 'A', weight = 1},Edge {u = 'B', v = 'C', weight = 3},
Edge {u = 'A', v = 'B', weight = 4}]Solution
module Task4 (minSpanningTree, Graph (..), Edge (..)) where
import Data.List
data Edge a b = Edge { u :: a,
v :: a,
weight :: b } deriving (Eq,Show)
data Graph a b = Graph { nodes :: [a],
edges :: [Edge a b] } deriving Show
gr2 :: Graph Char Int
gr2 = Graph{ nodes = ['A'..'F'],
edges = [Edge 'A' 'B' 1,
Edge 'D' 'E' 4,
Edge 'E' 'F' 7,
Edge 'A' 'D' 5,
Edge 'B' 'E' 2,
Edge 'C' 'F' 5,
Edge 'D' 'B' 6,
Edge 'E' 'C' 4,
Edge 'A' 'E' 3] }
reverseEdge :: Edge a b -> Edge a b
reverseEdge e = e{ u=v e, v=u e}
reverseEdges :: Graph a b -> Graph a b
reverseEdges g@Graph{ edges=es } = g{ edges=nes }
where nes = es ++ map reverseEdge es
findEdge :: (Eq a, Ord b) => [Edge a b] -> [a] -> [a] -> Edge a b
findEdge es covered uncovered = head active
where active = sortOn weight [ e | e <- es, u e `elem` covered, v e `elem` uncovered ]
jarnik :: (Eq a, Ord b) => Graph a b -> [a] -> [a] -> [Edge a b] -> [Edge a b]
jarnik _ _ [] es = es
jarnik g covered uncovered es = jarnik g (x:covered) (delete x uncovered) (ne:es)
where ne = findEdge (edges g) covered uncovered
x = v ne
minSpanningTree :: (Eq a, Ord b) => Graph a b -> [Edge a b]
minSpanningTree g = jarnik g' [x] xs []
where g' = reverseEdges g
(x:xs) = nodes g