applications/test/router/router.H

   1 /*---------------------------------------------------------------------------*\
   2   =========                 |
   3   \\      /  F ield         | OpenFOAM: The Open Source CFD Toolbox
   4    \\    /   O peration     |
   5     \\  /    A nd           | Copyright (C) 1991-2009 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 Class
  26     Foam::router
  27
  28 Description
  29     Lee's PCB routing algorithm. Construct with list of connections between
  30     nodes (i.e. topology) and list of coordinates of nodes (can be vector::zero)
  31
  32     Use e.g.
  33
  34         // Enter topology/geometry
  35         router cellRouter
  36         (
  37             mesh().cellCells(),
  38             mesh().cellCentres()
  39         );
  40
  41         // Try to route connections one by one. Specify unique value (<0) to
  42         // mark path with.
  43         forAll(wantedConnections, i)
  44         {
  45             bool success = cellRouter.route(wantedConnections[i], -(i+1));
  46         }
  47
  48
  49     The coordinates are only used at the moment for diagonal preference of
  50     routing:
  51
  52     So not:
  53
  54     +A
  55     |
  56     |
  57     |
  58     |
  59     ------+B
  60
  61     But:
  62
  63     + A
  64     |_
  65       |_
  66         |_
  67           |_
  68             |
  69             + B
  70
  71
  72     Lee algo: take array with same dimensions as grid of nodes. Initialize to
  73     large number. Put 0 at starting point. Now recursively assign neighbours
  74     as current value plus one. Stop if you hit node which has smaller number.
  75     Phase two is where you search path with lowest value. These are assigned
  76     negative number so they for next route are not overwritten.
  77
  78 SourceFiles
  79     router.C
  80
  81 \*---------------------------------------------------------------------------*/
  82
  83 #ifndef router_H
  84 #define router_H
  85
  86 #include <OpenFOAM/labelList.H>
  87 #include <OpenFOAM/pointField.H>
  88 #include <OpenFOAM/DynamicList.H>
  89
  90 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
  91
  92 namespace Foam
  93 {
  94
  95 // Forward declaration of classes
  96
  97 /*---------------------------------------------------------------------------*\
  98                            Class router Declaration
  99 \*---------------------------------------------------------------------------*/
 100
 101 class router
 102 {
 103     // Private data
 104
 105         //- Connections
 106         const labelListList connections_;
 107
 108         //- Coordinates of nodes
 109         const pointField coords_;
 110
 111         //- Routing table
 112         labelList weights_;
 113
 114     // Private Member Functions
 115
 116         //- Return number of weights. Utility function
 117         label count(const label weight) const;
 118
 119         //- Set distance from nodeI
 120         void setWeights
 121         (
 122             const label weight,
 123             const label nodeI
 124         );
 125
 126         //- Finds path from nodeI to startNodeI by travelling in direction
 127         //  of lowest weight
 128         void fixWeights
 129         (
 130             const label startNodeI,
 131             const label endNodeI,
 132             const label nodeI,
 133             const label prevNodeI
 134         );
 135
 136         //- Routes single path
 137         bool shortestPath
 138         (
 139             const labelList& path,
 140             const label pathValue
 141         );
 142
 143         //- Linear search for element with weight
 144         label getValue(const label) const;
 145
 146         //- Find node which has no neighbours with pathValue
 147         label findEndNode
 148         (
 149             const label startNodeI,
 150             const label prevNodeI,
 151             const label pathValue
 152         ) const;
 153
 154         //- Append all pathValue weights to route.
 155         void storeRoute
 156         (
 157             const label startNodeI,
 158             const label prevNodeI,
 159             const label pathValue,
 160             DynamicList<label>& route
 161         ) const;
 162
 163         //- Disallow default bitwise copy construct
 164         router(const router&);
 165
 166         //- Disallow default bitwise assignment
 167         void operator=(const router&);
 168
 169
 170 public:
 171
 172     // Constructors
 173
 174         //- Construct from connections, route later.
 175         router
 176         (
 177             const labelListList& connections,
 178             const List<point>& coords
 179         );
 180
 181
 182     // Member Functions
 183
 184         // Access
 185
 186             const labelList& weights() const
 187             {
 188                 return weights_;
 189             }
 190
 191         // Edit
 192
 193             //- Find path from first element in path to all other elements
 194             //  Mark resulting path in weights with (negative) pathValue.
 195             //  Returns false and does not mark any elements if cannot route.
 196             bool route(const labelList& path, const label pathValue);
 197
 198             //- Extract labels of route with given value.
 199             labelList getRoute(const label pathValue) const;
 200
 201 };
 202
 203
 204 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 205
 206 } // End namespace Foam
 207
 208 // * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * //
 209
 210 #endif
 211
 212 // ************************ vim: set sw=4 sts=4 et: ************************ //