Class PrimMST - PrimMST.h, PrimMST.cc


 
Definition:
Given a net this class finds a spanning tree for that net according to Prim's minimum spanning tree (MST) algorithm.  This algorithm is optimal.  The class can also break a multiple terminal net into a set of two terminal nets.  It does this by taking every edge of the MST and creating a two-terminal net from the pins of that edge.
Typedefs:
typedef vector<Net *> NetVector;
typedef NetVector::iterator NetVectorItr;
typedef priority_queue<PrimEdge *,vector<PrimEdge*>,PrimCompare> PrimPriorityQ;
Included:
#include <queue>
#include <vector>
#include "Net.h"


Variable Index
 
o Net * theNet
The net which will be used to make the MST.
o PinVector * parentPin
A vector which holds the parent of each pin.  The parent of a pin 'x' is the pin which is connected to pin 'x'.  You can use this vector to determine the edges of the spanning tree as well as the order in which the edges were introduced.  Mainly created for internal use while finding the spanning tree.
o PimOrderVector * pinOrder
A vector which contains the ordering of each pin.  This is created for convience as it makes it very easy to split a multi-terminal net into a set of two-terminal nets.
o PrimPriorityQ * primPQ
A priority queue used in Prim's algorithm to determine the next edge of the spanning tree.

Constructor Index

o PrimMST(Net *)

Serves as a default constructor.   The class needs a Net in order to work.
o ~PrimMST()
Deconstructor.


Method Index
 

o PinVector * getParentPins()
Returns a pointer to the parent pin vector parentPin.
o PrimOrderVector * getPinOrder()
Returns a pointer to the PrimOrderVector pinOrder.
o void findMST()
Method which actually performs Prim's MST algorithm.
o void twoTerminalNets(NetVector & twoTermNets)
Uses Prim's MST to create a set of two-terminal nets from a multi-terminal net.  It does this by making a two-terminal net out of every edge from the MST.