1 /*---------------------------------------------------------------------------*\
3 \\ / F ield | OpenFOAM: The Open Source CFD Toolbox
5 \\ / A nd | Copyright (C) 1991-2008 OpenCFD Ltd.
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 the
13 Free Software Foundation; either version 2 of the License, or (at your
14 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, write to the Free Software Foundation,
23 Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
27 \*---------------------------------------------------------------------------*/
31 // * * * * * * * * * * * * * Private Member Functions * * * * * * * * * * * //
33 Foam::label Foam::router::count(const label weight) const
37 forAll(weights_, nodeI)
39 cnt += weights_[nodeI];
46 // Given connections between nodes set minimum distance from nodeI
47 void Foam::router::setWeights
53 // Set weight at current node
54 weights_[nodeI] = weight;
56 const labelList& myNeighbours = connections_[nodeI];
58 forAll(myNeighbours, neighbourI)
60 if (weights_[myNeighbours[neighbourI]] > weight + 1)
62 // Distribute weight+1 to neighbours
66 myNeighbours[neighbourI]
73 // Mark shortest path from endNode to startNode by setting the weights
75 void Foam::router::fixWeights
77 const label startNodeI,
88 label minDist = labelMax;
91 const labelList& myNeighbours = connections_[nodeI];
93 forAll(myNeighbours, neighbourI)
95 label nbrNodeI = myNeighbours[neighbourI];
97 if (nbrNodeI != prevNodeI)
99 if (weights_[nbrNodeI] == 0)
105 else if (weights_[nbrNodeI] > 0)
107 if (weights_[nbrNodeI] < minDist)
109 minDist = weights_[nbrNodeI];
113 else if (weights_[nbrNodeI] == minDist)
123 // Reached starting point.
131 "Foam::router::fixWeights"
132 "(const label startNodeI, const label endNodeI,"
133 "const label nodeI, const label prevNodeI)"
134 ) << "Cannot route from node " << nodeI
135 << " since all neigbours of node "
136 << "already allocated:" << endl;
138 forAll(myNeighbours, neighbourI)
140 label nbrNodeI = myNeighbours[neighbourI];
144 "Foam::router::fixWeights"
145 "(const label startNodeI, const label endNodeI,"
146 "const label nodeI, const label prevNodeI)"
147 ) << " neighbour:" << nbrNodeI
148 << " weight:" << weights_[nbrNodeI] << endl;
156 // Multiple paths, all with same weight. Use some heuristic
157 // to choose one. Here: smallest angle to vector end-start
158 vector n(coords_[endNodeI] - coords_[startNodeI]);
160 scalar maxCosAngle = -GREAT;
162 forAll(myNeighbours, neighbourI)
164 label nbrNodeI = myNeighbours[neighbourI];
166 if (weights_[nbrNodeI] == minDist)
168 vector n2(coords_[nbrNodeI] - coords_[startNodeI]);
170 scalar magN2 = mag(n2);
176 scalar cosAngle = n & n2;
178 if (cosAngle > maxCosAngle)
180 maxCosAngle = cosAngle;
189 // Recursively go mark the path at minNode
200 Foam::label Foam::router::getValue(const label pathValue) const
202 forAll(weights_, nodeI)
204 if (weights_[nodeI] == pathValue)
213 // Find node which has no neighbours with pathValue
214 Foam::label Foam::router::findEndNode
216 const label startNodeI,
217 const label prevNodeI,
218 const label pathValue
221 const labelList& myNeighbours = connections_[startNodeI];
223 forAll(myNeighbours, neighbourI)
225 label nodeI = myNeighbours[neighbourI];
227 if (nodeI != prevNodeI)
229 if (weights_[nodeI] == pathValue)
231 return findEndNode(nodeI, startNodeI, pathValue);
236 // No neighbours with pathValue found. Return this node
241 // Append all pathValue weights to route.
242 void Foam::router::storeRoute
244 const label startNodeI,
245 const label prevNodeI,
246 const label pathValue,
247 DynamicList<label>& route
250 const labelList& myNeighbours = connections_[startNodeI];
252 forAll(myNeighbours, neighbourI)
254 label nodeI = myNeighbours[neighbourI];
256 if (nodeI != prevNodeI)
258 if (weights_[nodeI] == pathValue)
275 // * * * * * * * * * * * * * * * * Constructors * * * * * * * * * * * * * * //
277 // Construct from connections, route later
280 const labelListList& connections,
281 const List<point>& coords
284 connections_(connections),
286 weights_(coords.size(), 0)
290 // * * * * * * * * * * * * * * * Member Functions * * * * * * * * * * * * * //
292 bool Foam::router::route(const labelList& path, const label pathValue)
296 FatalErrorIn("router::route(const labelList&, const label)")
297 << "Illegal pathValue " << pathValue << exit(FatalError);
300 // Reset all non-allocated weights to maximum distance
301 forAll(weights_, nodeI)
303 if (weights_[nodeI] >= 0)
305 weights_[nodeI] = labelMax;
309 if (weights_[path[0]] < 0)
314 // Get weights according to distance to starting node
315 setWeights(0, path[0]);
317 // Check if all endPoints can be reached
318 for(label leafI = 1; leafI < path.size(); leafI++)
320 if (weights_[path[leafI]] == labelMax)
322 //Info<< "Cannot route leaf from " << path[0]
323 // << " to " << path[leafI] << " of path " << path
324 // << " since there is no valid route between them" << endl;
326 // Do not fix any paths but return
331 // Search back from all endpoints to start and fix weights
332 for(label leafI = 1; leafI < path.size(); leafI++)
342 if (leafI < path.size() - 1)
344 // Update distance to take new connections into account
345 forAll(weights_, nodeI)
347 if (weights_[nodeI]== 0)
349 // Include these nodes in distance calculation
350 setWeights(0, nodeI);
356 // All nodes on the path will now have value 0.
357 // Mark these nodes with the (negative) pathvalue
358 forAll(weights_, nodeI)
360 if (weights_[nodeI] == 0)
362 weights_[nodeI] = pathValue;
366 // Reset unallocated weights to 0
367 forAll(weights_, nodeI)
369 if (weights_[nodeI] > 0)
379 Foam::labelList Foam::router::getRoute(const label pathValue) const
381 // Find a starting point
382 label pathNodeI = getValue(pathValue);
386 FatalErrorIn("router::getRoute(const label)")
387 << "No route with value " << pathValue << endl;
390 // Find end or start by walking
391 label startNodeI = findEndNode(pathNodeI, -1, pathValue);
393 // Walk to other end and store
395 DynamicList<label> route(weights_.size());
397 route.append(startNodeI);
399 storeRoute(startNodeI, -1, pathValue, route);
406 // ************************************************************************* //