mascoptDev.algos.graph
Class PrimPreproc2

java.lang.Object
  |
  +--mascoptDev.algos.graph.PrimPreproc2

public class PrimPreproc2

extends Object

This algorithm called Boruvka's Algorithm is used to preprocess graphs before using the Prim's Algorithm. It can be run iteratively to generate a Minimum Spanning Tree itself.

At each node the minimum weight edge incident on it is selected and the corresponding neighbour is added to the initial node's component. The graph is then reconstructed with components representing the nodes and edges between nodes in the same component removed.

Version:

7/06/2002.

Author:

srai@sophia.inria.fr

See Also:

constructMst

Field Summary

static String

edgeW The string used to store values on edges for capcities.

Constructor Summary

PrimPreproc2(Graph g)
Default Constructor.

Method Summary

void	constructMst() This function constructs the Minimum Spanning Tree for the graph in iterations.
int	getMinEdgeWt(Vertex n1, Vertex n2, EdgeSet e) Returns the least weight found among the edges connecting two nodes in an EdgeSet
int	getMinEdgeWt(Vertex n1, Vertex n2, Graph g) Returns the least weight found among the edges connecting two nodes in a given graph.
int	getMinWeight() This function is used to find the weight of the Minimum Spanning Tree constructed

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

edgeW

public static final String edgeW

The string used to store values on edges for capcities.

See Also:

Constant Field Values

Constructor Detail

PrimPreproc2

public PrimPreproc2(Graph g)

Default Constructor.

Parameters:

g - the graph to be used

Method Detail

constructMst

public void constructMst()

This function constructs the Minimum Spanning Tree for the graph in iterations. Each node is looked at and its nearest neighbour is selected to lie in the same component. Then the process is repeated for the new node until you find a node which has already been visited. After one iteration each component is contracted to yield one node and the process continues in the new reduced graph until we have just one connected component left

getMinEdgeWt

public int getMinEdgeWt(Vertex n1,
                        Vertex n2,
                        Graph g)

Returns the least weight found among the edges connecting two nodes in a given graph.

Parameters:

n1 - Node 1

n2 - Node 2

g - The Graph to be used

getMinEdgeWt

public int getMinEdgeWt(Vertex n1,
                        Vertex n2,
                        EdgeSet e)

Returns the least weight found among the edges connecting two nodes in an EdgeSet

Parameters:

e - The EdgeSet to be used.

getMinWeight

public int getMinWeight()

This function is used to find the weight of the Minimum Spanning Tree constructed

See Also:

constructMst