jbnc.graphs
Class MinSpanTree

java.lang.Object
  jbnc.graphs.MinSpanTree

public class MinSpanTree

extends java.lang.Object

Minimum Spanning Tree algorithm.
Assumes that edges are undirected and there is only at most one edge between any two nodes.

Since:

June 1, 1999

Author:

Jarek Sacha

Constructor Summary

MinSpanTree()

Method Summary

Edge[]	getDirectedEdges(Graph graph, Vertex root) Returns edges of a minimum spanning tree of a graph.
static void	main(java.lang.String[] argv) Test the class.
protected void	orientEdges(Edge[] edges, Vertex root) Make sure that graph represents a directed tree (each vertex has at most one parent
Graph	run(Graph graph, Vertex root) Return a minimum spanning tree for a graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

MinSpanTree

public MinSpanTree()

Method Detail

main

public static void main(java.lang.String[] argv)

Test the class.

Parameters:

argv - The command line arguments

getDirectedEdges

public Edge[] getDirectedEdges(Graph graph,
                               Vertex root)
                        throws java.lang.Exception

Returns edges of a minimum spanning tree of a graph. Edges of the graph contain weights. Implements Kruskal's algorithm.

Parameters:

graph - graph to span with a tree.

root - vertex designated as the root of the full tree.

Returns:

list of directed edges. Edges are listed from strongest to weakest.

Throws:

java.lang.Exception

run

public Graph run(Graph graph,
                 Vertex root)
          throws java.lang.Exception

Return a minimum spanning tree for a graph. Implements Kruskal's algorithm.

Parameters:

graph - Description of Parameter

root - Description of Parameter

Returns:

Description of the Returned Value

Throws:

java.lang.Exception - Description of Exception

orientEdges

protected void orientEdges(Edge[] edges,
                           Vertex root)
                    throws java.lang.Exception

Make sure that graph represents a directed tree (each vertex has at most one parent

Parameters:

root - Vertex that should be treated as root of the directed tree.

edges - Description of Parameter

Throws:

java.lang.Exception - Description of Exception