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 String |
DEFAULT_WEIGHT_ATTRIBUTE
Default weight attribute
|
| Constructor and Description |
|---|
Kruskal()
Create a new Kruskal's algorithm.
|
Kruskal(String flagAttribute,
Object flagOn,
Object flagOff)
Create a new Kruskal's algorithm.
|
Kruskal(String weightAttribute,
String flagAttribute)
Create a new Kruskal's algorithm.
|
Kruskal(String weightAttribute,
String flagAttribute,
Object flagOn,
Object flagOff)
Create a new Kruskal's algorithm.
|
| Modifier and Type | Method and Description |
|---|---|
void |
clear()
Removes the tags of all edges.
|
<T extends org.graphstream.graph.Edge> |
getTreeEdgesIterator()
An iterator on the tree edges.
|
double |
getTreeWeight()
Returns the total weight of the minimum spanning tree
|
String |
getWeightAttribute()
Get weight attribute used to compare edges.
|
void |
setWeightAttribute(String newWeightAttribute)
Set the weight attribute.
|
compute, getFlagAttribute, getFlagOff, getFlagOn, getTreeEdges, init, setFlagAttribute, setFlagOff, setFlagOnpublic static final String DEFAULT_WEIGHT_ATTRIBUTE
public Kruskal()
public Kruskal(String weightAttribute, 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(String flagAttribute, Object flagOn, 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(String weightAttribute, String flagAttribute, Object flagOn, 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 String getWeightAttribute()
public void setWeightAttribute(String newWeightAttribute)
newWeightAttribute - new attribute usedpublic <T extends org.graphstream.graph.Edge> Iterator<T> getTreeEdgesIterator()
SpanningTreegetTreeEdgesIterator in interface SpanningTreegetTreeEdgesIterator in class AbstractSpanningTreepublic void clear()
SpanningTreeclear in interface SpanningTreeclear in class AbstractSpanningTreepublic double getTreeWeight()
Copyright © 2015. All rights reserved.