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 |
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
MSTKruskal
public MSTKruskal()
- Empty and only constructor matching to the
Algorithm
convention.
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 performedprefix
- the prefix identifying the results within the Graph's
propertiesweightProperty
- the name of the property which provides the weight of the
Edges
. If set to null
, each Edge
has weight 1tracer
- 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 performedprefix
- the prefix identifying the results within the Graph's
propertiesweightProperty
- the name of the property which provides the weight of the
Edges
. If set to null
, each Edge
has weight 1