In this tutorial we will see how to use and implements spanning tree algorithms.
Spanning tree
A spanning tree of a connected graph G(V,E) is a tree T(V,E') as E' is a subset of E.
In case of a weighted-graph, we usually try to find a minimum spanning tree as weight-sum
of edges in E' is minimum.
We can find a full article in wikipedia about
Spanning Tree.
AbstractSpanningTree class
AbstractSpanningTree is the base for spanning-tree algorithms. It allows user to specify an attribute and two values which will define if edges are in the tree or not. This class is an Algorithm implementation. Subclasses must implement makeTree() method which build the tree.
...
public abstract class AbstractSpanningTree implements Algorithm
{
public AbstractSpanningTree( Graph graph, String flagAttribute,
Object flagOn, Object flagOff )
{
...
}
protected void edgeOn( Edge e )
{
e.changeAttribute( flagAttribute, flagOn );
}
protected void edgeOff( Edge e )
{
e.changeAttribute( flagAttribute, flagOff );
}
...
}
Subclasses will use edgeOn(..) and edgeOff(..) methods to set if edges are in the resulting tree. A call to the compute() method will call edgeOff(..) for all edges of the current graph. Then, AbstractSpanningTree will call makeTree() method.
The flagAttribute allows users to define action produced by the algorithms. For example, algorithm can colorize the spanning tree by specifying the "color" attribute as flagAttribute:
... AbstractSpanningTree ast = new SpanningTreeImpl( graph, "color", "red", "black" ); ast.compute(); ...
This will colorize edges of the spanning tree in red, and other edges in black. Note that edgeOn and edgeOff are Object not only String to enlarge use of this type of algorithms.
Implemented algorithms
There are actually two spanning tree algorithms which compute a minimum spanning tree:
Users must specify the weight attribute of edges. This attribute can be of any type but it must be a Comparable object.
...
public class Kruskal extends AbstractSpanningTree
{
public Kruskal( Graph graph, String weightAttribute, String flagAttribute,
Object flagOn, Object flagOff)
{
...
}
...
}