hgeometry- Geometric Algorithms, Data structures, and Data types.

Safe HaskellNone




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.