Nektar++
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
SubStructuredGraph.h
Go to the documentation of this file.
1 ///////////////////////////////////////////////////////////////////////////////
2 //
3 // File SubStructuredGraph.h
4 //
5 // For more information, please see: http://www.nektar.info
6 //
7 // The MIT License
8 //
9 // Copyright (c) 2006 Division of Applied Mathematics, Brown University (USA),
10 // Department of Aeronautics, Imperial College London (UK), and Scientific
11 // Computing and Imaging Institute, University of Utah (USA).
12 //
13 // License for the specific language governing rights and limitations under
14 // Permission is hereby granted, free of charge, to any person obtaining a
15 // copy of this software and associated documentation files (the "Software"),
16 // to deal in the Software without restriction, including without limitation
17 // the rights to use, copy, modify, merge, publish, distribute, sublicense,
18 // and/or sell copies of the Software, and to permit persons to whom the
19 // Software is furnished to do so, subject to the following conditions:
20 //
21 // The above copyright notice and this permission notice shall be included
22 // in all copies or substantial portions of the Software.
23 //
24 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
25 // OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
27 // THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
29 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
30 // DEALINGS IN THE SOFTWARE.
31 //
32 // Description: a collection of classes that facilitates the implementation
33 // of the multi-level static condensation routines
34 //
35 ///////////////////////////////////////////////////////////////////////////////
36 
37 #ifndef MULTIREGIONS_SUBSTRUCTUREDGRAPH_H
38 #define MULTIREGIONS_SUBSTRUCTUREDGRAPH_H
39 
41 
44 
45 #include <vector>
46 #include <set>
47 #include <boost/config.hpp>
48 #include <boost/graph/adjacency_list.hpp>
49 #include <boost/graph/cuthill_mckee_ordering.hpp>
50 #include <boost/graph/properties.hpp>
51 #include <boost/graph/bandwidth.hpp>
52 
53 namespace Nektar
54 {
55  namespace MultiRegions
56  {
57  class BottomUpSubStructuredGraph;
58  class SubGraph;
59  class MultiLevelBisectedGraph;
60  class PatchMap;
61 
62  typedef boost::shared_ptr<BottomUpSubStructuredGraph>
64  typedef boost::shared_ptr<SubGraph>
66  typedef boost::shared_ptr<MultiLevelBisectedGraph>
68  typedef boost::shared_ptr<PatchMap>
70 
71  class PatchMap
72  {
73  public:
75  MULTI_REGIONS_EXPORT PatchMap(const int vals);
78  const int n,
79  const int patchId,
80  const int dofId,
81  const unsigned int bndPatch,
82  const NekDouble sign);
83 
85  {
86  return m_patchId;
87  }
88 
90  {
91  return m_dofId;
92  }
93 
95  {
96  return m_bndPatch;
97  }
98 
100  {
101  return m_sign;
102  }
103 
104  protected:
109  };
110 
111  class SubGraph
112  {
113  public:
114 
116  const int nVerts, const int idOffset = 0) :
117  m_nVerts(nVerts),
118  m_idOffset(idOffset)
119  {
120  }
121 
123  {
124  }
125 
126  inline int GetNverts(void) const
127  {
128  return m_nVerts;
129  }
130 
131  inline void SetNverts(const int i)
132  {
133  m_nVerts = i;
134  }
135 
136  inline int GetIdOffset(void) const
137  {
138  return m_idOffset;
139  }
140 
141  inline void SetIdOffset(const int i)
142  {
143  m_idOffset = i;
144  }
145 
146  protected:
147  int m_nVerts;
149  };
150 
152 
154  {
155  public:
157  const Array<OneD, const int> sepTree);
160  const int nPartition);
162  const int nBndDofs);
164 
165  MULTI_REGIONS_EXPORT int GetTotDofs() const;
167  MULTI_REGIONS_EXPORT void DumpNBndDofs(void) const;
169  std::vector<SubGraphSharedPtr>& leaves) const;
172  MULTI_REGIONS_EXPORT inline int GetNdaughterGraphs() const;
173 
174  inline const SubGraphSharedPtr GetBndDofsGraph() const
175  {
176  return m_BndDofs;
177  }
178 
179  protected:
183  };
184 
185 
187  {
188  public:
190  const Array<OneD, const int> septree,
191  const int nPartition);
193  const MultiLevelBisectedGraphSharedPtr& graph);
195  const int nVerts);
197 
198  MULTI_REGIONS_EXPORT int GetTotDofs() const;
199 
201  Array<OneD, int>& perm,
202  Array<OneD, int>& iperm) const;
203 
205  const Array<OneD, const int>& wgts);
206 
208  const int leveltomask,
209  Array<OneD, NekDouble>& maskarray) const;
210 
212  const int whichlevel) const;
213 
215  const int whichlevel,
216  Array<OneD, unsigned int> &outarray) const;
217 
219  const int whichlevel,
220  const int patch = 0) const;
221 
222  MULTI_REGIONS_EXPORT std::vector<SubGraphSharedPtr>
223  GetInteriorBlocks(const int whichlevel) const;
224 
226  const int whichlevel) const;
227 
228  MULTI_REGIONS_EXPORT int GetNlevels() const;
229 
230  MULTI_REGIONS_EXPORT void Dump() const;
231 
232  protected:
233  std::vector<SubGraphSharedPtr> m_IntBlocks;
234  BottomUpSubStructuredGraphSharedPtr m_daughterGraph;
235 
236  private:
237  void SetBottomUpReordering(Array<OneD, int>& iperm) const;
238 
239  inline BottomUpSubStructuredGraphSharedPtr GetDaughterGraph() const
240  {
241  return m_daughterGraph;
242  }
243  inline std::vector<SubGraphSharedPtr> GetInteriorBlocks() const
244  {
245  return m_IntBlocks;
246  }
247  };
248 
249  namespace
250  {
251  typedef boost::adjacency_list<
252  boost::setS, boost::vecS, boost::undirectedS> BoostGraph;
253  }
254 
256  const BoostGraph& graph,
257  Array<OneD, int>& perm,
258  Array<OneD, int>& iperm);
259 
261  const BoostGraph &graph,
262  Array<OneD, int> &perm,
263  Array<OneD, int> &iperm,
264  BottomUpSubStructuredGraphSharedPtr &substructgraph,
265  std::set<int> partVerts = std::set<int>(),
266  int mdswitch = 1);
267 
268  // The parameter MDSWITCH.
269  //
270  // This parameters defines the maximal size of the smallest patches. If
271  // at a certain level, a patch bundles less than MDSWITCH
272  // graph-vertices, metis is not going to partition this subgraph any
273  // further. Some quick and basis test have shown that 30 seems to be
274  // good value. However, this optimal value will probably depend on the
275  // polynomial order of the expansion and there is still room for
276  // optimisation here.
277 
278  MULTI_REGIONS_EXPORT void NoReordering(const BoostGraph& graph,
279  Array<OneD, int>& perm,
280  Array<OneD, int>& iperm);
281  } // end of namespace
282 } // end of namespace
283 
284 #endif // MULTIREGIONS_SUBSTRUCTUREDGRAPH_H
Array< OneD, NekDouble > m_sign
int GetNpatchesWithInterior(const int whichlevel) const
Array< OneD, const int > GetDofId() const
void MaskPatches(const int leveltomask, Array< OneD, NekDouble > &maskarray) const
void GetNintDofsPerPatch(const int whichlevel, Array< OneD, unsigned int > &outarray) const
void MultiLevelBisectionReordering(const BoostGraph &graph, Array< OneD, int > &perm, Array< OneD, int > &iperm, BottomUpSubStructuredGraphSharedPtr &substructgraph, std::set< int > partVerts, int mdswitch)
#define sign(a, b)
return the sign(b)*a
Definition: Polylib.cpp:22
MultiLevelBisectedGraph(const Array< OneD, const int > sepTree)
Array< OneD, const unsigned int > IsBndDof() const
boost::shared_ptr< BottomUpSubStructuredGraph > BottomUpSubStructuredGraphSharedPtr
#define MULTI_REGIONS_EXPORT
void CuthillMckeeReordering(const BoostGraph &graph, Array< OneD, int > &perm, Array< OneD, int > &iperm)
BottomUpSubStructuredGraphSharedPtr GetDaughterGraph() const
BottomUpSubStructuredGraph(const Array< OneD, const int > septree, const int nPartition)
boost::shared_ptr< MultiLevelBisectedGraph > MultiLevelBisectedGraphSharedPtr
boost::shared_ptr< PatchMap > PatchMapSharedPtr
void CollectLeaves(std::vector< SubGraphSharedPtr > &leaves) const
boost::shared_ptr< SubGraph > SubGraphSharedPtr
Array< OneD, const int > GetPatchId() const
Array< OneD, unsigned int > m_bndPatch
void ExpandGraphWithVertexWeights(const Array< OneD, const int > &wgts)
MultiLevelBisectedGraphSharedPtr m_rightDaughterGraph
double NekDouble
std::vector< SubGraphSharedPtr > GetInteriorBlocks() const
BottomUpSubStructuredGraphSharedPtr m_daughterGraph
Array< OneD, const NekDouble > GetSign() const
void UpdateBottomUpReordering(Array< OneD, int > &perm, Array< OneD, int > &iperm) const
bool SubGraphWithoutVerts(const SubGraphSharedPtr g)
const SubGraphSharedPtr GetBndDofsGraph() const
SubGraph(const int nVerts, const int idOffset=0)
MultiLevelBisectedGraphSharedPtr m_leftDaughterGraph
void SetBottomUpReordering(Array< OneD, int > &iperm) const
void SetPatchMap(const int n, const int patchId, const int dofId, const unsigned int bndPatch, const NekDouble sign)
int GetInteriorOffset(const int whichlevel, const int patch=0) const
void NoReordering(const BoostGraph &graph, Array< OneD, int > &perm, Array< OneD, int > &iperm)