Safe Haskell	None
Language	Haskell2010

Algorithms.Graph.MST

Synopsis

mst :: Ord e => PlanarGraph s w v e f -> Tree (VertexId s w)
mstEdges :: Ord e => PlanarGraph s w v e f -> [Dart s]
makeTree :: forall s w v e f. PlanarGraph s w v e f -> [Dart s] -> Tree (VertexId s w)

Documentation

mst :: Ord e => PlanarGraph s w v e f -> Tree (VertexId s w) Source #

Minimum spanning tree of the edges. The result is a rooted tree, in which the nodes are the vertices in the planar graph together with the edge weight of the edge to their parent. The root's weight is zero.

The algorithm used is Kruskal's.

running time: \(O(n \log n)\)

mstEdges :: Ord e => PlanarGraph s w v e f -> [Dart s] Source #

Computes the set of edges in the Minimum spanning tree

running time: \(O(n \log n)\)

makeTree :: forall s w v e f. PlanarGraph s w v e f -> [Dart s] -> Tree (VertexId s w) Source #

Given an underlying planar graph, and a set of edges that form a tree, create the actual tree.

pre: the planar graph has at least one vertex.