applications/test/router/router.C

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 1991-2008 OpenCFD Ltd.
   6      \\/     M anipulation  |
   7 -------------------------------------------------------------------------------
   8 License
   9     This file is part of OpenFOAM.
  10
  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.
  15
  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
  19     for more details.
  20
  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
  24
  25 Description
  26
  27 \*---------------------------------------------------------------------------*/
  28
  29 #include "router.H"
  30
  31 // * * * * * * * * * * * * * Private Member Functions  * * * * * * * * * * * //
  32
  33 Foam::label Foam::router::count(const label weight) const
  34 {
  35     label cnt = 0;
  36
  37     forAll(weights_, nodeI)
  38     {
  39         cnt += weights_[nodeI];
  40     }
  41
  42     return cnt;
  43 }
  44
  45
  46 // Given connections between nodes set minimum distance from nodeI
  47 void Foam::router::setWeights
  48 (
  49     const label weight,
  50     const label nodeI
  51 )
  52 {
  53     // Set weight at current node
  54     weights_[nodeI] = weight;
  55
  56     const labelList& myNeighbours = connections_[nodeI];
  57
  58     forAll(myNeighbours, neighbourI)
  59     {
  60         if (weights_[myNeighbours[neighbourI]] > weight + 1)
  61         {
  62             // Distribute weight+1 to neighbours
  63             setWeights
  64             (
  65                 weight+1,
  66                 myNeighbours[neighbourI]
  67             );
  68         }
  69     }
  70 }
  71
  72
  73 // Mark shortest path from endNode to startNode by setting the weights
  74 // to 0.
  75 void Foam::router::fixWeights
  76 (
  77     const label startNodeI,
  78     const label endNodeI,
  79
  80     const label nodeI,
  81     const label prevNodeI
  82 )
  83 {
  84     // Mark this node
  85     weights_[nodeI] = 0;
  86
  87     label minNodeI = -1;
  88     label minDist = labelMax;
  89     label nMinNodes = 0;
  90
  91     const labelList& myNeighbours = connections_[nodeI];
  92
  93     forAll(myNeighbours, neighbourI)
  94     {
  95         label nbrNodeI = myNeighbours[neighbourI];
  96
  97         if (nbrNodeI != prevNodeI)
  98         {
  99             if (weights_[nbrNodeI] == 0)
 100             {
 101                 // Reached end
 102                 minDist = 0;
 103                 break;
 104             }
 105             else if (weights_[nbrNodeI] > 0)
 106             {
 107                 if (weights_[nbrNodeI] < minDist)
 108                 {
 109                     minDist = weights_[nbrNodeI];
 110                     minNodeI = nbrNodeI;
 111                     nMinNodes = 1;
 112                 }
 113                 else if (weights_[nbrNodeI] == minDist)
 114                 {
 115                     nMinNodes++;
 116                 }
 117             }
 118         }
 119     }
 120
 121     if (minDist == 0)
 122     {
 123         // Reached starting point.
 124         return;
 125     }
 126
 127     if (minNodeI == -1)
 128     {
 129         WarningIn
 130         (
 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;
 137
 138         forAll(myNeighbours, neighbourI)
 139         {
 140             label nbrNodeI = myNeighbours[neighbourI];
 141
 142             WarningIn
 143             (
 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;
 149         }
 150         return;
 151     }
 152
 153
 154     if (nMinNodes > 1)
 155     {
 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]);
 159
 160         scalar maxCosAngle = -GREAT;
 161
 162         forAll(myNeighbours, neighbourI)
 163         {
 164             label nbrNodeI = myNeighbours[neighbourI];
 165
 166             if (weights_[nbrNodeI] == minDist)
 167             {
 168                 vector n2(coords_[nbrNodeI] - coords_[startNodeI]);
 169
 170                 scalar magN2 = mag(n2);
 171
 172                 if (magN2 > SMALL)
 173                 {
 174                     n2 /= mag(n2);
 175
 176                     scalar cosAngle = n & n2;
 177
 178                     if (cosAngle > maxCosAngle)
 179                     {
 180                         maxCosAngle = cosAngle;
 181                         minNodeI = nbrNodeI;
 182                     }
 183                 }
 184             }
 185         }
 186     }
 187
 188
 189     // Recursively go mark the path at minNode
 190     fixWeights
 191     (
 192         startNodeI,
 193         endNodeI,
 194         minNodeI,
 195         nodeI
 196     );
 197 }
 198
 199
 200 Foam::label Foam::router::getValue(const label pathValue) const
 201 {
 202     forAll(weights_, nodeI)
 203     {
 204         if (weights_[nodeI] == pathValue)
 205         {
 206             return nodeI;
 207         }
 208     }
 209     return -1;
 210 }
 211
 212
 213 // Find node which has no neighbours with pathValue
 214 Foam::label Foam::router::findEndNode
 215 (
 216     const label startNodeI,
 217     const label prevNodeI,
 218     const label pathValue
 219 ) const
 220 {
 221     const labelList& myNeighbours = connections_[startNodeI];
 222
 223     forAll(myNeighbours, neighbourI)
 224     {
 225         label nodeI = myNeighbours[neighbourI];
 226
 227         if (nodeI != prevNodeI)
 228         {
 229             if (weights_[nodeI] == pathValue)
 230             {
 231                 return findEndNode(nodeI, startNodeI, pathValue);
 232             }
 233         }
 234     }
 235
 236     // No neighbours with pathValue found. Return this node
 237     return startNodeI;
 238 }
 239
 240
 241 // Append all pathValue weights to route.
 242 void Foam::router::storeRoute
 243 (
 244     const label startNodeI,
 245     const label prevNodeI,
 246     const label pathValue,
 247     DynamicList<label>& route
 248 ) const
 249 {
 250     const labelList& myNeighbours = connections_[startNodeI];
 251
 252     forAll(myNeighbours, neighbourI)
 253     {
 254         label nodeI = myNeighbours[neighbourI];
 255
 256         if (nodeI != prevNodeI)
 257         {
 258             if (weights_[nodeI] == pathValue)
 259             {
 260                 route.append(nodeI);
 261
 262                 storeRoute
 263                 (
 264                     nodeI,
 265                     startNodeI,
 266                     pathValue,
 267                     route
 268                 );
 269             }
 270         }
 271     }
 272 }
 273
 274
 275 // * * * * * * * * * * * * * * * * Constructors  * * * * * * * * * * * * * * //
 276
 277 // Construct from connections, route later
 278 Foam::router::router
 279 (
 280     const labelListList& connections,
 281     const List<point>& coords
 282 )
 283 :
 284     connections_(connections),
 285     coords_(coords),
 286     weights_(coords.size(), 0)
 287 {}
 288
 289
 290 // * * * * * * * * * * * * * * * Member Functions  * * * * * * * * * * * * * //
 291
 292 bool Foam::router::route(const labelList& path, const label pathValue)
 293 {
 294     if (pathValue >= 0)
 295     {
 296         FatalErrorIn("router::route(const labelList&, const label)")
 297             << "Illegal pathValue " << pathValue << exit(FatalError);
 298     }
 299
 300     // Reset all non-allocated weights to maximum distance
 301     forAll(weights_, nodeI)
 302     {
 303         if (weights_[nodeI] >= 0)
 304         {
 305             weights_[nodeI] = labelMax;
 306         }
 307     }
 308
 309     if (weights_[path[0]] < 0)
 310     {
 311         // Already used
 312         return false;
 313     }
 314     // Get weights according to distance to starting node
 315     setWeights(0, path[0]);
 316
 317     // Check if all endPoints can be reached
 318     for(label leafI = 1; leafI < path.size(); leafI++)
 319     {
 320         if (weights_[path[leafI]] == labelMax)
 321         {
 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;
 325
 326             // Do not fix any paths but return
 327             return false;
 328         }
 329     }
 330
 331     // Search back from all endpoints to start and fix weights
 332     for(label leafI = 1; leafI < path.size(); leafI++)
 333     {
 334         fixWeights
 335         (
 336             path[0],
 337             path[leafI],
 338             path[leafI],
 339             -1
 340         );
 341
 342         if (leafI < path.size() - 1)
 343         {
 344             // Update distance to take new connections into account
 345             forAll(weights_, nodeI)
 346             {
 347                 if (weights_[nodeI]== 0)
 348                 {
 349                     // Include these nodes in distance calculation
 350                     setWeights(0, nodeI);
 351                 }
 352             }
 353         }
 354     }
 355
 356     // All nodes on the path will now have value 0.
 357     // Mark these nodes with the (negative) pathvalue
 358     forAll(weights_, nodeI)
 359     {
 360         if (weights_[nodeI] == 0)
 361         {
 362             weights_[nodeI] = pathValue;
 363         }
 364     }
 365
 366     // Reset unallocated weights to 0
 367     forAll(weights_, nodeI)
 368     {
 369         if (weights_[nodeI] > 0)
 370         {
 371             weights_[nodeI] = 0;
 372         }
 373     }
 374
 375     return true;
 376 }
 377
 378
 379 Foam::labelList Foam::router::getRoute(const label pathValue) const
 380 {
 381     // Find a starting point
 382     label pathNodeI = getValue(pathValue);
 383
 384     if (pathNodeI == -1)
 385     {
 386         FatalErrorIn("router::getRoute(const label)")
 387             << "No route with value " << pathValue << endl;
 388     }
 389
 390     // Find end or start by walking
 391     label startNodeI = findEndNode(pathNodeI, -1, pathValue);
 392
 393     // Walk to other end and store
 394
 395     DynamicList<label> route(weights_.size());
 396
 397     route.append(startNodeI);
 398
 399     storeRoute(startNodeI, -1, pathValue, route);
 400
 401     route.shrink();
 402
 403     return route;
 404 }
 405
 406 // ************************************************************************* //