pmst

Builds the Minimum Spanning Tree of graph.

Synopsis

pmst [-m mask] [gr_in|-] [gr_out|-]

Description

pmst builds the Minimum Spanning Tree of the input graph gr_in.

A spanning tree of a graph is just a subgraph that contains all the vertices and is a tree. A minimum spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree.

The principle is based on the Prim's algorithm:

   Select an arbitrary node to start
   While (there are fringe vertices)
	select minimum-weight edge between tree and fringe
        add the selected edge and node to the tree

Edges between nodes are physically modified: the neighbor relationships are lost and the weight of the remain edges are set to 1.

Inputs

gr_in: a graph.

Outputs

gr_out: a graph.

Result

Returns SUCCESS or FAILURE.

Examples

   pmst g1.pan g2.pan

C++ prototype

Errc PMst( const Graph2d &gr_in, Graph2d &gr_out );

Version française

Construction de l'arbre de recouvrement minimal d'un graphe.

Author: François Angot