1 /*---------------------------------------------------------------------------*\
3 \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
5 \\ / A nd | Copyright (C) 2011 OpenFOAM Foundation
7 -------------------------------------------------------------------------------
9 This file is part of OpenFOAM.
11 OpenFOAM is free software: you can redistribute it and/or modify it
12 under the terms of the GNU General Public License as published by
13 the Free Software Foundation, either version 3 of the License, or
14 (at your option) any later version.
16 OpenFOAM is distributed in the hope that it will be useful, but WITHOUT
17 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
18 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
21 You should have received a copy of the GNU General Public License
22 along with OpenFOAM. If not, see <http://www.gnu.org/licenses/>.
28 Lee's PCB routing algorithm. Construct with list of connections between
29 nodes (i.e. topology) and list of coordinates of nodes (can be vector::zero)
33 // Enter topology/geometry
40 // Try to route connections one by one. Specify unique value (<0) to
42 forAll(wantedConnections, i)
44 bool success = cellRouter.route(wantedConnections[i], -(i+1));
48 The coordinates are only used at the moment for diagonal preference of
71 Lee algo: take array with same dimensions as grid of nodes. Initialize to
72 large number. Put 0 at starting point. Now recursively assign neighbours
73 as current value plus one. Stop if you hit node which has smaller number.
74 Phase two is where you search path with lowest value. These are assigned
75 negative number so they for next route are not overwritten.
80 \*---------------------------------------------------------------------------*/
85 #include "labelList.H"
86 #include "pointField.H"
87 #include "DynamicList.H"
89 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
94 // Forward declaration of classes
96 /*---------------------------------------------------------------------------*\
97 Class router Declaration
98 \*---------------------------------------------------------------------------*/
105 const labelListList connections_;
107 //- Coordinates of nodes
108 const pointField coords_;
113 // Private Member Functions
115 //- Return number of weights. Utility function
116 label count(const label weight) const;
118 //- Set distance from nodeI
125 //- Finds path from nodeI to startNodeI by travelling in direction
129 const label startNodeI,
130 const label endNodeI,
132 const label prevNodeI
135 //- Routes single path
138 const labelList& path,
139 const label pathValue
142 //- Linear search for element with weight
143 label getValue(const label) const;
145 //- Find node which has no neighbours with pathValue
148 const label startNodeI,
149 const label prevNodeI,
150 const label pathValue
153 //- Append all pathValue weights to route.
156 const label startNodeI,
157 const label prevNodeI,
158 const label pathValue,
159 DynamicList<label>& route
162 //- Disallow default bitwise copy construct
163 router(const router&);
165 //- Disallow default bitwise assignment
166 void operator=(const router&);
173 //- Construct from connections, route later.
176 const labelListList& connections,
177 const List<point>& coords
185 const labelList& weights() const
192 //- Find path from first element in path to all other elements
193 // Mark resulting path in weights with (negative) pathValue.
194 // Returns false and does not mark any elements if cannot route.
195 bool route(const labelList& path, const label pathValue);
197 //- Extract labels of route with given value.
198 labelList getRoute(const label pathValue) const;
203 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
205 } // End namespace Foam
207 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
211 // ************************************************************************* //