KiCad PCB EDA Suite
minimun_spanning_tree.cpp
Go to the documentation of this file.
1
5 /*
6  * This program source code file is part of KiCad, a free EDA CAD application.
7  *
8  * Copyright (C) 2011 Jean-Pierre Charras
9  * Copyright (C) 2004-2011 KiCad Developers, see change_log.txt for contributors.
10  *
12  * http://compprog.wordpress.com/2007/11/09/minimal-spanning-trees-prims-algorithm
13  *
14  * This program is free software; you can redistribute it and/or
15  * modify it under the terms of the GNU General Public License
16  * as published by the Free Software Foundation; either version 2
17  * of the License, or (at your option) any later version.
18  *
19  * This program is distributed in the hope that it will be useful,
20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
22  * GNU General Public License for more details.
23  *
24  * You should have received a copy of the GNU General Public License
25  * along with this program; if not, you may find one here:
27  * or you may search the http://www.gnu.org website for the version 2 license,
28  * or you may write to the Free Software Foundation, Inc.,
29  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
30  */
31
32 #include <limits.h>
33
34 #include <minimun_spanning_tree.h>
36
37 /*
38  * The class MIN_SPAN_TREE calculates the rectilinear minimum spanning tree
39  * of a set of points (pads usually having the same net)
40  * using the Prim's algorithm.
41  */
42
43 /*
44  * Prim's Algorithm
45  * Step 0
46  * Pick any vertex as a starting vertex. (Call it S).
47  * Mark it with any given flag, say 1.
48  *
49  * Step 1
50  * Find the nearest neighbour of S (call it P1).
51  * Mark both P1 and the edge SP1.
52  * cheapest unmarked edge in the graph that doesn't close a marked circuit.
53  * Mark this edge.
54  *
55  * Step 2
56  * Find the nearest unmarked neighbour to the marked subgraph
57  * (i.e., the closest vertex to any marked vertex).
58  * Mark it and the edge connecting the vertex.
59  *
60  * Step 3
61  * Repeat Step 2 until all vertices are marked.
62  * The marked subgraph is a minimum spanning tree.
63  */
65 {
66  MSP_Init( 0 );
67 }
68
69
70 void MIN_SPAN_TREE::MSP_Init( int aNodesCount )
71 {
72  m_Size = std::max( aNodesCount, 1 );
73  inTree.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 }
97
98
99 /* updateDistances(int target)
100  * should be called immediately after target is added to the tree;
101  * updates dist so that the values are correct (goes through target's
102  * neighbours making sure that the distances between them and the tree
103  * are indeed minimum)
104  */
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 }
120
121
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...
void MSP_Init(int aNodesCount)
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