public class Kruskal extends AbstractSpanningTree
Kruskal's algorithm is a greedy algorithm which allows to find a minimal spanning tree in a weighted connected graph. More informations on Wikipedia.
import org.graphstream.graph.Graph; import org.graphstream.graph.implementations.DefaultGraph; import org.graphstream.algorithm.Kruskal; import org.graphstream.algorithm.generator.DorogovtsevMendesGenerator; public class KruskalTest { public static void main(String .. args) { DorogovtsevMendesGenerator gen = new DorogovtsevMendesGenerator(); Graph graph = new DefaultGraph("Kruskal Test"); String css = "edge .notintree {size:1px;fill-color:gray;} " + "edge .intree {size:3px;fill-color:black;}"; graph.addAttribute("ui.stylesheet", css); graph.display(); gen.addEdgeAttribute("weight"); gen.setEdgeAttributesRange(1, 100); gen.addSink(graph); gen.begin(); for (int i = 0; i < 100 && gen.nextEvents(); i++) ; gen.end(); Kruskal kruskal = new Kruskal("ui.class", "intree", "notintree"); kruskal.init(g); kruskal.compute(); } }
AbstractSpanningTree
Modifier and Type | Field and Description |
---|---|
static java.lang.String |
DEFAULT_WEIGHT_ATTRIBUTE
Default weight attribute
|
Constructor and Description |
---|
Kruskal()
Create a new Kruskal's algorithm.
|
Kruskal(java.lang.String flagAttribute,
java.lang.Object flagOn,
java.lang.Object flagOff)
Create a new Kruskal's algorithm.
|
Kruskal(java.lang.String weightAttribute,
java.lang.String flagAttribute)
Create a new Kruskal's algorithm.
|
Kruskal(java.lang.String weightAttribute,
java.lang.String flagAttribute,
java.lang.Object flagOn,
java.lang.Object flagOff)
Create a new Kruskal's algorithm.
|
Modifier and Type | Method and Description |
---|---|
void |
clear()
Removes the tags of all edges.
|
java.lang.String |
defaultResult() |
java.util.stream.Stream<org.graphstream.graph.Edge> |
getTreeEdgesStream()
An iterator on the tree edges.
|
double |
getTreeWeight()
Returns the total weight of the minimum spanning tree
|
java.lang.String |
getWeightAttribute()
Get weight attribute used to compare edges.
|
void |
setWeightAttribute(java.lang.String newWeightAttribute)
Set the weight attribute.
|
compute, getFlagAttribute, getFlagOff, getFlagOn, getTreeEdges, init, setFlagAttribute, setFlagOff, setFlagOn
public static final java.lang.String DEFAULT_WEIGHT_ATTRIBUTE
public Kruskal()
public Kruskal(java.lang.String weightAttribute, java.lang.String flagAttribute)
true
for the tree edges and false for the non-tree edges.weightAttribute
- attribute used to compare edgesflagAttribute
- attribute used to set if an edge is in the spanning treepublic Kruskal(java.lang.String flagAttribute, java.lang.Object flagOn, java.lang.Object flagOff)
flagAttribute
- attribute used to set if an edge is in the spanning treeflagOn
- value of the flagAttribute if edge is in the spanning
treeflagOff
- value of the flagAttribute if edge is not in the
spanning treepublic Kruskal(java.lang.String weightAttribute, java.lang.String flagAttribute, java.lang.Object flagOn, java.lang.Object flagOff)
weightAttribute
- attribute used to compare edgesflagAttribute
- attribute used to set if an edge is in the spanning treeflagOn
- value of the flagAttribute if edge is in the spanning
treeflagOff
- value of the flagAttribute if edge is not in the
spanning treepublic java.lang.String getWeightAttribute()
public void setWeightAttribute(java.lang.String newWeightAttribute)
newWeightAttribute
- new attribute usedpublic java.util.stream.Stream<org.graphstream.graph.Edge> getTreeEdgesStream()
SpanningTree
getTreeEdgesStream
in interface SpanningTree
getTreeEdgesStream
in class AbstractSpanningTree
public void clear()
SpanningTree
clear
in interface SpanningTree
clear
in class AbstractSpanningTree
public double getTreeWeight()
public java.lang.String defaultResult()