org.graphstream.algorithm

## Class Kruskal

• All Implemented Interfaces:
Algorithm, SpanningTree
Direct Known Subclasses:
Prim

```public class Kruskal
extends AbstractSpanningTree```
Compute a spanning tree using the Kruskal algorithm.

Kruskal's algorithm is a greedy algorithm which allows to find a minimal spanning tree in a weighted connected graph. More informations on Wikipedia.

## Example

The following example generates a graph with the Dorogovtsev-Mendes generator and then computes a spanning-tree using the Kruskal algorithm. The generator creates random weights for edges that will be used by the Kruskal algorithm. If no weight is present, algorithm considers that all weights are set to 1. When an edge is in the spanning tree, the algorithm will set its "ui.class" attribute to "intree", else the attribute is set to "notintree". According to the css stylesheet that is defined, spanning will be displayed with thick black lines while edges not in the spanning tree will be displayed with thin gray lines.
``` 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.display();

gen.setEdgeAttributesRange(1, 100);
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`
Computational Complexity:
O(m log n) where m is the number of edges and n is the number of nodes of the graph
Scientific Reference:
Joseph. B. Kruskal: On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. In: Proceedings of the American Mathematical Society, Vol 7, No. 1 (Feb, 1956), pp. 48–50
• ### Field Summary

Fields
Modifier and Type Field and Description
`static java.lang.String` `DEFAULT_WEIGHT_ATTRIBUTE`
Default weight attribute
• ### Constructor Summary

Constructors
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.
• ### Method Summary

All Methods
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.
• ### Methods inherited from class org.graphstream.algorithm.AbstractSpanningTree

`compute, getFlagAttribute, getFlagOff, getFlagOn, getTreeEdges, init, setFlagAttribute, setFlagOff, setFlagOn`
• ### Methods inherited from class java.lang.Object

`equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Field Detail

• #### DEFAULT_WEIGHT_ATTRIBUTE

`public static final java.lang.String DEFAULT_WEIGHT_ATTRIBUTE`
Default weight attribute
Constant Field Values
• ### Constructor Detail

• #### Kruskal

`public Kruskal()`
Create a new Kruskal's algorithm. Uses the default weight attribute and does not tag the edges.
• #### Kruskal

```public Kruskal(java.lang.String weightAttribute,
java.lang.String flagAttribute)```
Create a new Kruskal's algorithm. The value of the flag attribute is `true` for the tree edges and false for the non-tree edges.
Parameters:
`weightAttribute` - attribute used to compare edges
`flagAttribute` - attribute used to set if an edge is in the spanning tree
• #### Kruskal

```public Kruskal(java.lang.String flagAttribute,
java.lang.Object flagOn,
java.lang.Object flagOff)```
Create a new Kruskal's algorithm. Uses the default weight attribute.
Parameters:
`flagAttribute` - attribute used to set if an edge is in the spanning tree
`flagOn` - value of the flagAttribute if edge is in the spanning tree
`flagOff` - value of the flagAttribute if edge is not in the spanning tree
• #### Kruskal

```public Kruskal(java.lang.String weightAttribute,
java.lang.String flagAttribute,
java.lang.Object flagOn,
java.lang.Object flagOff)```
Create a new Kruskal's algorithm.
Parameters:
`weightAttribute` - attribute used to compare edges
`flagAttribute` - attribute used to set if an edge is in the spanning tree
`flagOn` - value of the flagAttribute if edge is in the spanning tree
`flagOff` - value of the flagAttribute if edge is not in the spanning tree
• ### Method Detail

• #### getWeightAttribute

`public java.lang.String getWeightAttribute()`
Get weight attribute used to compare edges.
Returns:
weight attribute
• #### setWeightAttribute

`public void setWeightAttribute(java.lang.String newWeightAttribute)`
Set the weight attribute.
Parameters:
`newWeightAttribute` - new attribute used
• #### getTreeEdgesStream

`public java.util.stream.Stream<org.graphstream.graph.Edge> getTreeEdgesStream()`
Description copied from interface: `SpanningTree`
An iterator on the tree edges.
Specified by:
`getTreeEdgesStream` in interface `SpanningTree`
Specified by:
`getTreeEdgesStream` in class `AbstractSpanningTree`
Returns:
An iterator on the tree edges
• #### clear

`public void clear()`
Description copied from interface: `SpanningTree`
Removes the tags of all edges. Use this method to save memory if the spanning tree is used no more.
Specified by:
`clear` in interface `SpanningTree`
Overrides:
`clear` in class `AbstractSpanningTree`
• #### getTreeWeight

`public double getTreeWeight()`
Returns the total weight of the minimum spanning tree
Returns:
The sum of the weights of the edges in the spanning tree
• #### defaultResult

`public java.lang.String defaultResult()`