SED navigation bar go to SED home page go to Dataplot home page go to NIST home page SED Home Page SED Staff SED Projects SED Products and Publications Search SED Pages
Dataplot Vol 2 Vol 1

MINIMUM SPANNING TREE

Name:
    MINIMUM SPANNING TREE
Type:
    LET Subcommand
Purpose:
    Compute the minimum spanning tree of either a set of vertices or a distance matrix.
Description:
    A spanning tree of a connected, undirected graph is a subgraph which is a tree that connects all the vertices together. A graph can more than one spanning tree. Distances are defined for each edge in the graph (alternatively, edges could be represented by weights or costs). the edges

    The minimum spanning tree is the spanning tree for which the sum of the distances over the edges in the spanning tree is a minimum.

    Dataplot supports two forms of the minimum spanning tree.

    1. The input is a set of x and y coordinates for the vertices in the graph. In this case, the distance between two vertices is simply the Euclidean distance between the vertices.

    2. The input is a distance matrix. In this case, the distance can denote a weight or a cost instead of a distance.
Syntax 1:
    LET <y2> <x2> <tag> = MINIMUM SPANNING TREE <y> <x>
                            <SUBSET/EXPCEPT/FOR qualification>
    where <y> is a variable containing the y-coordinates of the full data set;
                <x> is a variable containing the x-coordinates of the full data set;
                <y2> is a variable that will contain the y-coordinats of the returned minimum spanning tree;
                <x2> is a variable that will contain the x-coordinats of the returned minimum spanning tree;
                <tag> is a variable that will contain a trace-id (i.e., points that will be connected) of the returned minimum spanning tree;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.
Syntax 2:
    LET <edge1> <edge2> = MINIMUM SPANNING TREE <dist>
                            <SUBSET/EXPCEPT/FOR qualification>
    where <dist> is a matrix containing the distances (or weights or costs);
                <edge1> is a variable that will contain the first vertex of the edges in the mimimum spanning tree;
                <edge2> is a variable that will contain the second vertex of the edges in the mimimum spanning tree;
    and where the <SUBSET/EXCEPT/FOR qualification> is optional.
Examples:
    LET Y2 X2 TAG = MINIMUM SPANNING TREE Y X
    LET EDGE1 EDGE2 = MINIMUM SPANNING TREE DIST
Note:
    Dataplot uses the MINSPT algorithm given in Nijenhuis and Wilf (see the Reference section below).
Default:
    None.
Synonyms:
    None
Related Commands: References:
    Nijenhuis and Wilf (1978), "Combinatorial Algorithms", Second Edition, Academic Press, Chapter 30.
Applications:
    Graph Theory
Implementation Date:
    2008/4
Program 1:
     
    read matrix d
      0  100  125  120  110
    100    0   40   65   60
    125   40    0   45   55
    120   65   45    0   50
    110   60   55   50    0
    end of data
    .
    let y2 x2 = minimum spanning tree d
    set write decimals 1
    print y2 x2
        
    The following output is generated.
              2              1
              3              2
              4              3
              5              4
        
Program 2:
     
    skip 1
    read convex_hull.dat x y
    .
    let y2 x2 tag = minimum spanning tree y x
    .
    title case asis
    title offset 2
    title Minimum Spanning Tree
    y1label Y
    x1label X
    tic offset units screen
    tic offset 3 3
    x3label
    .
    plot y2 x2 tag
        
    plot generated by sample program

Date created: 1/26/2009
Last updated: 1/26/2009
Please email comments on this WWW page to alan.heckert@nist.gov.