KiCad PCB EDA Suite
MIN_SPAN_TREE_PADS Class Reference

class MIN_SPAN_TREE_PADS (derived from MIN_SPAN_TREE) specializes the base class to calculate a minimum spanning tree from a list of pads, and to add this tree as ratsnest to the main ratsnest list. More...

Inheritance diagram for MIN_SPAN_TREE_PADS:
MIN_SPAN_TREE

Public Member Functions

 MIN_SPAN_TREE_PADS ()
 
void MSP_Init (std::vector< D_PAD * > *aPadsList)
 
void AddTreeToRatsnest (std::vector< RATSNEST_ITEM > *aRatsnestList)
 Function AddTreeToRatsnest Adds the current minimum spanning tree as ratsnest items to the main ratsnest list. More...
 
int GetWeight (int aItem1, int aItem2) override
 Function GetWeight calculates the weight between 2 items NOTE: The weight between a node and itself should be 0. More...
 
void MSP_Init (int aNodesCount)
 
void BuildTree ()
 
int GetWhoTo (int aIdx)
 
int GetDist (int aIdx)
 

Public Attributes

std::vector< D_PAD * > * m_PadsList
 

Protected Attributes

int m_Size
 

Friends

class MIN_SPAN_TREE
 

Detailed Description

class MIN_SPAN_TREE_PADS (derived from MIN_SPAN_TREE) specializes the base class to calculate a minimum spanning tree from a list of pads, and to add this tree as ratsnest to the main ratsnest list.

Definition at line 51 of file ratsnest.cpp.

Constructor & Destructor Documentation

MIN_SPAN_TREE_PADS::MIN_SPAN_TREE_PADS ( )
inline

Definition at line 64 of file ratsnest.cpp.

64  : MIN_SPAN_TREE()
65  {
66  m_PadsList = NULL;
67  }
std::vector< D_PAD * > * m_PadsList
Definition: ratsnest.cpp:55

Member Function Documentation

void MIN_SPAN_TREE_PADS::AddTreeToRatsnest ( std::vector< RATSNEST_ITEM > *  aRatsnestList)

Function AddTreeToRatsnest Adds the current minimum spanning tree as ratsnest items to the main ratsnest list.

Parameters
aRatsnestList= a ratsnest list to add to

Definition at line 95 of file ratsnest.cpp.

References CH_ACTIF, CH_VISIBLE, MIN_SPAN_TREE::GetDist(), MIN_SPAN_TREE::GetWhoTo(), RATSNEST_ITEM::m_Length, RATSNEST_ITEM::m_PadEnd, m_PadsList, RATSNEST_ITEM::m_PadStart, MIN_SPAN_TREE::m_Size, RATSNEST_ITEM::m_Status, and RATSNEST_ITEM::SetNet().

Referenced by PCB_BASE_FRAME::Build_Board_Ratsnest(), and PCB_BASE_FRAME::build_ratsnest_module().

96 {
97  std::vector<D_PAD*>& padsBuffer = *m_PadsList;
98 
99  if( padsBuffer.empty() )
100  return;
101 
102  int netcode = padsBuffer[0]->GetNetCode();
103 
104  // Note: to get edges in minimum spanning tree,
105  // the index value 0 is not used: it is just
106  // the entry point of the minimum spanning tree.
107  // The first edge (i.e. rastnest) starts at index 1
108  for( int ii = 1; ii < m_Size; ii++ )
109  {
110  // Create the new ratsnest
111  RATSNEST_ITEM net;
112 
113  net.SetNet( netcode );
114  net.m_Status = CH_ACTIF | CH_VISIBLE;
115  net.m_Length = GetDist(ii);
116  net.m_PadStart = padsBuffer[ii];
117  net.m_PadEnd = padsBuffer[ GetWhoTo(ii) ];
118 
119  aRatsnestList->push_back( net );
120  }
121 }
int GetDist(int aIdx)
void SetNet(int aNetCode)
Definition: class_netinfo.h:90
#define CH_ACTIF
Definition: class_netinfo.h:60
D_PAD * m_PadEnd
Definition: class_netinfo.h:76
#define CH_VISIBLE
Definition: class_netinfo.h:57
int GetWhoTo(int aIdx)
D_PAD * m_PadStart
Definition: class_netinfo.h:75
Class RATSNEST_ITEM describes a ratsnest line: a straight line connecting 2 pads. ...
Definition: class_netinfo.h:68
std::vector< D_PAD * > * m_PadsList
Definition: ratsnest.cpp:55
void MIN_SPAN_TREE::BuildTree ( )
inherited

Definition at line 122 of file minimun_spanning_tree.cpp.

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

Referenced by PCB_BASE_FRAME::Build_Board_Ratsnest(), and PCB_BASE_FRAME::build_ratsnest_module().

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)
inlineinherited

Definition at line 73 of file minimun_spanning_tree.h.

Referenced by AddTreeToRatsnest().

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

Function GetWeight calculates the weight between 2 items NOTE: The weight between a node and itself should be 0.

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

Implements MIN_SPAN_TREE.

Definition at line 130 of file ratsnest.cpp.

References abs, D_PAD::GetPosition(), wxPoint::x, and wxPoint::y.

131 {
132  // NOTE: The distance (weight) between a node and itself should be 0
133  // so we add 1 to other distances to be sure we never have 0
134  // in cases other than a node and itself
135 
136  D_PAD* pad1 = (*m_PadsList)[aItem1];
137  D_PAD* pad2 = (*m_PadsList)[aItem2];
138 
139  if( pad1 == pad2 )
140  return 0;
141 
142  int weight = abs( pad2->GetPosition().x - pad1->GetPosition().x ) +
143  abs( pad2->GetPosition().y - pad1->GetPosition().y );
144  return weight + 1;
145 }
#define abs(a)
Definition: auxiliary.h:84
const wxPoint & GetPosition() const override
Definition: class_pad.h:170
int MIN_SPAN_TREE::GetWhoTo ( int  aIdx)
inlineinherited

Definition at line 67 of file minimun_spanning_tree.h.

Referenced by AddTreeToRatsnest().

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

Definition at line 70 of file minimun_spanning_tree.cpp.

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

Referenced by MIN_SPAN_TREE::MIN_SPAN_TREE(), and MSP_Init().

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_PADS::MSP_Init ( std::vector< D_PAD * > *  aPadsList)
inline

Definition at line 69 of file ratsnest.cpp.

References MIN_SPAN_TREE::MSP_Init().

Referenced by PCB_BASE_FRAME::Build_Board_Ratsnest(), and PCB_BASE_FRAME::build_ratsnest_module().

70  {
71  m_PadsList = aPadsList;
72  MIN_SPAN_TREE::MSP_Init( (int) m_PadsList->size() );
73  }
void MSP_Init(int aNodesCount)
std::vector< D_PAD * > * m_PadsList
Definition: ratsnest.cpp:55

Friends And Related Function Documentation

friend class MIN_SPAN_TREE
friend

Definition at line 53 of file ratsnest.cpp.

Member Data Documentation

std::vector<D_PAD*>* MIN_SPAN_TREE_PADS::m_PadsList

Definition at line 55 of file ratsnest.cpp.

Referenced by AddTreeToRatsnest().

int MIN_SPAN_TREE::m_Size
protectedinherited

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