gishur.graph.algorithms
Class MSTKruskal

java.lang.Object
  |
  +--gishur.core.algorithms.Algorithm
        |
        +--gishur.graph.algorithms.MSTKruskal

public class MSTKruskal
extends Algorithm

Kruskal's algorithm to find the minimum-spanning-tree. The Graph on which it is performed may be directed or undirected as the directedness of Edges is ignored by this algorithm.

Version:
1.0
Author:
Christoph Sachse

Field Summary
static int BLACK
          Identifier for an Edge in the minimum-spanning-tree.
static int MSTKRUSKAL_STEP
          Trace label for a step of the algorithm
 
Constructor Summary
MSTKruskal()
          Empty and only constructor matching to the Algorithm convention.
 
Method Summary
 void mstKruskal(Graph g, java.lang.String prefix, java.lang.String weightProperty)
          Performs Kruskal's algorithm without tracing the steps.
 void mstKruskal(Graph g, java.lang.String prefix, java.lang.String weightProperty, Tracer tracer)
          Performs Kruskal's algorithm on g and writes the results to g's properties under the prefix prefix, i.e. the Edges which are part of the found minimum-spanning-tree will be marked with the property prefix.color==BLACK (see BLACK).
 
Methods inherited from class gishur.core.algorithms.Algorithm
execute, execute, execute, execute, execute, execute, execute, execute, getMethod, getParameter, getParameters, getReturnValue, setMethod, setParameter, setParameters
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

BLACK

public static final int BLACK
Identifier for an Edge in the minimum-spanning-tree.

MSTKRUSKAL_STEP

public static final int MSTKRUSKAL_STEP
Trace label for a step of the algorithm
Constructor Detail

MSTKruskal

public MSTKruskal()
Empty and only constructor matching to the Algorithm convention.
Method Detail

mstKruskal

public void mstKruskal(Graph g,
                       java.lang.String prefix,
                       java.lang.String weightProperty,
                       Tracer tracer)
Performs Kruskal's algorithm on g and writes the results to g's properties under the prefix prefix, i.e. the Edges which are part of the found minimum-spanning-tree will be marked with the property prefix.color==BLACK (see BLACK). The weight of each edge is taken from the property weightProperty. If g==null, the method returns effectiveless. If prefix==null, nothing will be written to the Graph's properties. Givinig weightProperty==null will cause the algorithm to assume each Edge to be weighted with an int weight of 1.
Parameters:
g - the Graph on which the algorithm shall be performed
prefix - the prefix identifying the results within the Graph's properties
weightProperty - the name of the property which provides the weight of the Edges. If set to null, each Edge has weight 1
tracer - a Tracer to record the algorithm steps

mstKruskal

public void mstKruskal(Graph g,
                       java.lang.String prefix,
                       java.lang.String weightProperty)
Performs Kruskal's algorithm without tracing the steps. See #mstKruskal(Graph,String,String,int).
Parameters:
g - the Graph on which the algorithm shall be performed
prefix - the prefix identifying the results within the Graph's properties
weightProperty - the name of the property which provides the weight of the Edges. If set to null, each Edge has weight 1