KiCad PCB EDA Suite
minimun_spanning_tree.h
Go to the documentation of this file.
1 /*
2  * This program source code file is part of KiCad, a free EDA CAD application.
3  *
4  * Copyright (C) 2011-2014 Jean-Pierre Charras, jp.charras at wanadoo.fr
5  * Copyright (C) 1992-2012 KiCad Developers, see AUTHORS.txt for contributors.
6  *
7  * This program is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  *
12  * This program is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, you may find one here:
19  * http://www.gnu.org/licenses/old-licenses/gpl-2.0.html
20  * or you may search the http://www.gnu.org website for the version 2 license,
21  * or you may write to the Free Software Foundation, Inc.,
22  * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
23  */
24 
29 #include <vector>
30 
41 {
42 protected:
43  int m_Size; /* The number of nodes in the graph
44  */
45 private:
46  std::vector<char> inTree; /* inTree[ii] is a flag set to 1 if the node ii
47  * is already in the minimum spanning tree; 0 otherwise
48  */
49  std::vector<int> linkedTo; /* linkedTo[ii] holds the index of the node ii would have to be
50  * linked to in order to get a distance of d[ii]
51  * NOTE: linkedTo[0] is the starting point of the tree
52  * linkedTo[1] is the first linked point to use
53  * ii and linkedTo[ii] are the 2 ends of an edge in the graph
54  */
55  std::vector<int> distTo; /* distTo[ii] is the distance between node ii and the minimum spanning
56  * tree;
57  * this is initially infinity (INT_MAX);
58  * if ii is already in the tree, then d[ii] is undefined;
59  * this is just a temporary variable. It's not necessary but speeds
60  * up execution considerably (by a factor of n)
61  */
62 public:
63  MIN_SPAN_TREE();
64  void MSP_Init( int aNodesCount );
65  void BuildTree();
66 
67  int GetWhoTo( int aIdx )
68  {
69  return linkedTo[aIdx];
70  }
71 
72 
73  int GetDist( int aIdx )
74  {
75  return distTo[aIdx];
76  }
77 
87  virtual int GetWeight( int aItem1, int aItem2 ) = 0;
88 
89 private:
90 
99  void updateDistances( int aTarget );
100 
101 };
int GetDist(int aIdx)
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
The class MIN_SPAN_TREE calculates the rectilinear minimum spanning tree of a set of points (pads usu...
std::vector< int > distTo
int GetWhoTo(int aIdx)