applications/test/router/router.H

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 2011 OpenFOAM Foundation
   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
  13     the Free Software Foundation, either version 3 of the License, or
  14     (at your 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, see <http://www.gnu.org/licenses/>.
  23
  24 Class
  25     Foam::router
  26
  27 Description
  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)
  30
  31     Use e.g.
  32
  33         // Enter topology/geometry
  34         router cellRouter
  35         (
  36             mesh().cellCells(),
  37             mesh().cellCentres()
  38         );
  39
  40         // Try to route connections one by one. Specify unique value (<0) to
  41         // mark path with.
  42         forAll(wantedConnections, i)
  43         {
  44             bool success = cellRouter.route(wantedConnections[i], -(i+1));
  45         }
  46
  47
  48     The coordinates are only used at the moment for diagonal preference of
  49     routing:
  50
  51     So not:
  52
  53     +A
  54     |
  55     |
  56     |
  57     |
  58     ------+B
  59
  60     But:
  61
  62     + A
  63     |_
  64       |_
  65         |_
  66           |_
  67             |
  68             + B
  69
  70
  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.
  76
  77 SourceFiles
  78     router.C
  79
  80 \*---------------------------------------------------------------------------*/
  81
  82 #ifndef router_H
  83 #define router_H
  84
  85 #include "labelList.H"
  86 #include "pointField.H"
  87 #include "DynamicList.H"
  88
  89 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
  90
  91 namespace Foam
  92 {
  93
  94 // Forward declaration of classes
  95
  96 /*---------------------------------------------------------------------------*\
  97                            Class router Declaration
  98 \*---------------------------------------------------------------------------*/
  99
 100 class router
 101 {
 102     // Private data
 103
 104         //- Connections
 105         const labelListList connections_;
 106
 107         //- Coordinates of nodes
 108         const pointField coords_;
 109
 110         //- Routing table
 111         labelList weights_;
 112
 113     // Private Member Functions
 114
 115         //- Return number of weights. Utility function
 116         label count(const label weight) const;
 117
 118         //- Set distance from nodeI
 119         void setWeights
 120         (
 121             const label weight,
 122             const label nodeI
 123         );
 124
 125         //- Finds path from nodeI to startNodeI by travelling in direction
 126         //  of lowest weight
 127         void fixWeights
 128         (
 129             const label startNodeI,
 130             const label endNodeI,
 131             const label nodeI,
 132             const label prevNodeI
 133         );
 134
 135         //- Routes single path
 136         bool shortestPath
 137         (
 138             const labelList& path,
 139             const label pathValue
 140         );
 141
 142         //- Linear search for element with weight
 143         label getValue(const label) const;
 144
 145         //- Find node which has no neighbours with pathValue
 146         label findEndNode
 147         (
 148             const label startNodeI,
 149             const label prevNodeI,
 150             const label pathValue
 151         ) const;
 152
 153         //- Append all pathValue weights to route.
 154         void storeRoute
 155         (
 156             const label startNodeI,
 157             const label prevNodeI,
 158             const label pathValue,
 159             DynamicList<label>& route
 160         ) const;
 161
 162         //- Disallow default bitwise copy construct
 163         router(const router&);
 164
 165         //- Disallow default bitwise assignment
 166         void operator=(const router&);
 167
 168
 169 public:
 170
 171     // Constructors
 172
 173         //- Construct from connections, route later.
 174         router
 175         (
 176             const labelListList& connections,
 177             const List<point>& coords
 178         );
 179
 180
 181     // Member Functions
 182
 183         // Access
 184
 185             const labelList& weights() const
 186             {
 187                 return weights_;
 188             }
 189
 190         // Edit
 191
 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);
 196
 197             //- Extract labels of route with given value.
 198             labelList getRoute(const label pathValue) const;
 199
 200 };
 201
 202
 203 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 204
 205 } // End namespace Foam
 206
 207 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 208
 209 #endif
 210
 211 // ************************************************************************* //