KiCad PCB EDA Suite
MIN_SPAN_TREE Class Referenceabstract

The class MIN_SPAN_TREE calculates the rectilinear minimum spanning tree of a set of points (pads usually having the same net) this class is an abstract class because you must provide the function int GetWeight( int aItem1, int aItem2 ) that calculate the distance between 2 items MIN_SPAN_TREE does not know anything about the actual items to link by the tree. More...

#include <minimun_spanning_tree.h>

Public Member Functions

 MIN_SPAN_TREE ()
 
void MSP_Init (int aNodesCount)
 
void BuildTree ()
 
int GetWhoTo (int aIdx)
 
int GetDist (int aIdx)
 
virtual int GetWeight (int aItem1, int aItem2)=0
 Function GetWeight calculates the weight between 2 items NOTE: The weight between a node and itself should be 0 It is virtual pure, you must provide your GetWeight function. More...
 

Protected Attributes

int m_Size
 

Private Member Functions

void updateDistances (int aTarget)
 Function updateDistances should be called immediately after target is added to the tree; updates d so that the values are correct (goes through target's neighbours making sure that the distances between them and the tree are indeed minimum) More...
 

Private Attributes

std::vector< char > inTree
 
std::vector< int > linkedTo
 
std::vector< int > distTo
 

Detailed Description

The class MIN_SPAN_TREE calculates the rectilinear minimum spanning tree of a set of points (pads usually having the same net) this class is an abstract class because you must provide the function int GetWeight( int aItem1, int aItem2 ) that calculate the distance between 2 items MIN_SPAN_TREE does not know anything about the actual items to link by the tree.

Definition at line 40 of file minimun_spanning_tree.h.

Constructor & Destructor Documentation

MIN_SPAN_TREE::MIN_SPAN_TREE ( )

Definition at line 64 of file minimun_spanning_tree.cpp.

References MSP_Init().

65 {
66  MSP_Init( 0 );
67 }
void MSP_Init(int aNodesCount)

Member Function Documentation

void MIN_SPAN_TREE::BuildTree ( )

Definition at line 122 of file minimun_spanning_tree.cpp.

References distTo, inTree, m_Size, min, and updateDistances().

123 {
124  // Add the first node to the tree
125  inTree[0] = 1;
126  updateDistances( 0 );
127 
128  for( int treeSize = 1; treeSize < m_Size; ++treeSize )
129  {
130  // Find the node with the smallest distance to the tree
131  int min = -1;
132 
133  for( int ii = 0; ii < m_Size; ++ii )
134  {
135  if( !inTree[ii] )
136  {
137  if( (min == -1) || (distTo[min] > distTo[ii]) )
138  min = ii;
139  }
140  }
141 
142  inTree[min] = 1;
143  updateDistances( min );
144  }
145 }
void updateDistances(int aTarget)
Function updateDistances should be called immediately after target is added to the tree; updates d so...
std::vector< char > inTree
std::vector< int > distTo
#define min(a, b)
Definition: auxiliary.h:85
int MIN_SPAN_TREE::GetDist ( int  aIdx)
inline

Definition at line 73 of file minimun_spanning_tree.h.

74  {
75  return distTo[aIdx];
76  }
std::vector< int > distTo
virtual int MIN_SPAN_TREE::GetWeight ( int  aItem1,
int  aItem2 
)
pure virtual

Function GetWeight calculates the weight between 2 items NOTE: The weight between a node and itself should be 0 It is virtual pure, you must provide your GetWeight function.

Parameters
aItem1= first item
aItem2= other item
Returns
the weight between items ( usually the distance )

Referenced by updateDistances().

int MIN_SPAN_TREE::GetWhoTo ( int  aIdx)
inline

Definition at line 67 of file minimun_spanning_tree.h.

68  {
69  return linkedTo[aIdx];
70  }
std::vector< int > linkedTo
void MIN_SPAN_TREE::MSP_Init ( int  aNodesCount)

Definition at line 70 of file minimun_spanning_tree.cpp.

References distTo, inTree, linkedTo, m_Size, and max.

Referenced by MIN_SPAN_TREE().

71 {
72  m_Size = std::max( aNodesCount, 1 );
73  inTree.clear();
74  linkedTo.clear();
75  distTo.clear();
76 
77  if( m_Size == 0 )
78  return;
79 
80  // Reserve space in memory
81  inTree.reserve( m_Size );
82  linkedTo.reserve( m_Size );
83  distTo.reserve( m_Size );
84 
85  // Initialize values:
86  for( int ii = 0; ii < m_Size; ii++ )
87  {
88  // Initialise dist with infinity:
89  distTo.push_back( INT_MAX );
90 
91  // Mark all nodes as NOT beeing in the minimum spanning tree:
92  inTree.push_back( 0 );
93 
94  linkedTo.push_back( 0 );
95  }
96 }
std::vector< char > inTree
std::vector< int > linkedTo
std::vector< int > distTo
#define max(a, b)
Definition: auxiliary.h:86
void MIN_SPAN_TREE::updateDistances ( int  aTarget)
private

Function updateDistances should be called immediately after target is added to the tree; updates d so that the values are correct (goes through target's neighbours making sure that the distances between them and the tree are indeed minimum)

Parameters
aTarget= index of curr item

Definition at line 105 of file minimun_spanning_tree.cpp.

References distTo, GetWeight(), inTree, linkedTo, and m_Size.

Referenced by BuildTree().

106 {
107  for( int ii = 0; ii < m_Size; ++ii )
108  {
109  if( !inTree[ii] ) // no need to evaluate weight for already in tree items
110  {
111  int weight = GetWeight( target, ii );
112  if( (weight > 0) && (distTo[ii] > weight ) )
113  {
114  distTo[ii] = weight;
115  linkedTo[ii] = target;
116  }
117  }
118  }
119 }
virtual int GetWeight(int aItem1, int aItem2)=0
Function GetWeight calculates the weight between 2 items NOTE: The weight between a node and itself s...
std::vector< char > inTree
std::vector< int > linkedTo
std::vector< int > distTo

Member Data Documentation

std::vector<int> MIN_SPAN_TREE::distTo
private

Definition at line 55 of file minimun_spanning_tree.h.

Referenced by BuildTree(), MSP_Init(), and updateDistances().

std::vector<char> MIN_SPAN_TREE::inTree
private

Definition at line 46 of file minimun_spanning_tree.h.

Referenced by BuildTree(), MSP_Init(), and updateDistances().

std::vector<int> MIN_SPAN_TREE::linkedTo
private

Definition at line 49 of file minimun_spanning_tree.h.

Referenced by MSP_Init(), and updateDistances().

int MIN_SPAN_TREE::m_Size
protected

Definition at line 43 of file minimun_spanning_tree.h.

Referenced by BuildTree(), MSP_Init(), and updateDistances().


The documentation for this class was generated from the following files: