1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
/**
* @file minimun_spanning_tree.cpp
*/
/*
* This program source code file is part of KiCad, a free EDA CAD application.
*
* Copyright (C) 2011 Jean-Pierre Charras
* Copyright (C) 2004-2011 KiCad Developers, see change_log.txt for contributors.
*
* derived from this article:
* http://compprog.wordpress.com/2007/11/09/minimal-spanning-trees-prims-algorithm
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
* as published by the Free Software Foundation; either version 2
* of the License, or (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, you may find one here:
* http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
* or you may search the http://www.gnu.org website for the version 2 license,
* or you may write to the Free Software Foundation, Inc.,
* 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
*/
#include <limits.h>
#include <minimun_spanning_tree.h>
#include <class_pad.h>
/*
* The class MIN_SPAN_TREE calculates the rectilinear minimum spanning tree
* of a set of points (pads usually having the same net)
* using the Prim's algorithm.
*/
/*
* Prim's Algorithm
* Step 0
* Pick any vertex as a starting vertex. (Call it S).
* Mark it with any given flag, say 1.
*
* Step 1
* Find the nearest neighbour of S (call it P1).
* Mark both P1 and the edge SP1.
* cheapest unmarked edge in the graph that doesn't close a marked circuit.
* Mark this edge.
*
* Step 2
* Find the nearest unmarked neighbour to the marked subgraph
* (i.e., the closest vertex to any marked vertex).
* Mark it and the edge connecting the vertex.
*
* Step 3
* Repeat Step 2 until all vertices are marked.
* The marked subgraph is a minimum spanning tree.
*/
MIN_SPAN_TREE::MIN_SPAN_TREE()
{
MSP_Init( 0 );
}
void MIN_SPAN_TREE::MSP_Init( int aNodesCount )
{
m_Size = std::max( aNodesCount, 1 );
inTree.clear();
linkedTo.clear();
distTo.clear();
if( m_Size == 0 )
return;
// Reserve space in memory
inTree.reserve( m_Size );
linkedTo.reserve( m_Size );
distTo.reserve( m_Size );
// Initialize values:
for( int ii = 0; ii < m_Size; ii++ )
{
// Initialise dist with infinity:
distTo.push_back( INT_MAX );
// Mark all nodes as NOT beeing in the minimum spanning tree:
inTree.push_back( 0 );
linkedTo.push_back( 0 );
}
}
/* updateDistances(int target)
* should be called immediately after target is added to the tree;
* updates dist so that the values are correct (goes through target's
* neighbours making sure that the distances between them and the tree
* are indeed minimum)
*/
void MIN_SPAN_TREE::updateDistances( int target )
{
for( int ii = 0; ii < m_Size; ++ii )
{
if( !inTree[ii] ) // no need to evaluate weight for already in tree items
{
int weight = GetWeight( target, ii );
if( (weight > 0) && (distTo[ii] > weight ) )
{
distTo[ii] = weight;
linkedTo[ii] = target;
}
}
}
}
void MIN_SPAN_TREE::BuildTree()
{
// Add the first node to the tree
inTree[0] = 1;
updateDistances( 0 );
for( int treeSize = 1; treeSize < m_Size; ++treeSize )
{
// Find the node with the smallest distance to the tree
int min = -1;
for( int ii = 0; ii < m_Size; ++ii )
{
if( !inTree[ii] )
{
if( (min == -1) || (distTo[min] > distTo[ii]) )
min = ii;
}
}
inTree[min] = 1;
updateDistances( min );
}
}