ug4
parallel_dual_graph.h
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2012-2015: G-CSC, Goethe University Frankfurt
3  * Author: Sebastian Reiter
4  *
5  * This file is part of UG4.
6  *
7  * UG4 is free software: you can redistribute it and/or modify it under the
8  * terms of the GNU Lesser General Public License version 3 (as published by the
9  * Free Software Foundation) with the following additional attribution
10  * requirements (according to LGPL/GPL v3 §7):
11  *
12  * (1) The following notice must be displayed in the Appropriate Legal Notices
13  * of covered and combined works: "Based on UG4 (www.ug4.org/license)".
14  *
15  * (2) The following notice must be displayed at a prominent place in the
16  * terminal output of covered works: "Based on UG4 (www.ug4.org/license)".
17  *
18  * (3) The following bibliography is recommended for citation and must be
19  * preserved in all covered files:
20  * "Reiter, S., Vogel, A., Heppner, I., Rupp, M., and Wittum, G. A massively
21  * parallel geometric multigrid solver on hierarchically distributed grids.
22  * Computing and visualization in science 16, 4 (2013), 151-164"
23  * "Vogel, A., Reiter, S., Rupp, M., Nägel, A., and Wittum, G. UG4 -- a novel
24  * flexible software system for simulating pde based models on high performance
25  * computers. Computing and visualization in science 16, 4 (2013), 165-179"
26  *
27  * This program is distributed in the hope that it will be useful,
28  * but WITHOUT ANY WARRANTY; without even the implied warranty of
29  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
30  * GNU Lesser General Public License for more details.
31  */
32 
33 #ifndef __H__LIB_GRID__PARALLEL_DUAL_GRAPH__
34 #define __H__LIB_GRID__PARALLEL_DUAL_GRAPH__
35 
36 #include <vector>
37 #include "lib_grid/lg_base.h"
39 #include "../distributed_grid.h"
40 #include "../parallelization_util.h"
41 
42 namespace ug
43 {
44 
46 
51 template <class TGeomBaseObj, class TIndexType,
52  class TConnectingObj = typename TGeomBaseObj::side>
54  public:
55  typedef typename std::vector<TGeomBaseObj*>::iterator element_iterator_t;
56 
57  ParallelDualGraph(MultiGrid* pmg = NULL);
59 
60  void set_grid(MultiGrid* pmg);
61 
63 
66  TIndexType num_graph_vertices();
67  TIndexType num_graph_edges();
68  TIndexType* adjacency_map_structure();
69  TIndexType* adjacency_map();
70  TIndexType* parallel_offset_map();
74 
76  bool was_considered(TGeomBaseObj* o);
77 
79  TGeomBaseObj* get_element(size_t gvrtIndex) {return m_elems[gvrtIndex];}
80 
82 
85  TConnectingObj* get_connection(size_t connIndex) {return m_connections.at(connIndex);}
86 
89 
92 
94  TIndexType get_index(TGeomBaseObj* elem) {return m_aaElemIndex[elem];}
95 
97 
101  void generate_graph(int level, pcl::ProcessCommunicator procCom =
103 
105 
109 
110  private:
111  void attach_data();
112  void detach_data();
113 
115  // Members
118 
121  std::vector<TGeomBaseObj*> m_elems;
122  std::vector<TConnectingObj*> m_connections;
123  std::vector<TIndexType> m_adjacencyMapStructure;
124  std::vector<TIndexType> m_adjacencyMap;
125  std::vector<TIndexType> m_nodeOffsetMap;
130 };
131 
133 
178 template <class TGeomBaseObj, class TIndexType>
180  std::vector<TIndexType>& adjacencyMapStructureOut,
181  std::vector<TIndexType>& adjacencyMapOut,
182  std::vector<TIndexType>& nodeOffsetMapOut,
183  MultiGrid& mg, size_t level,
184  pcl::ProcessCommunicator procCom,
185  Attachment<TIndexType>* paIndex = NULL,
186  TGeomBaseObj** pGeomObjsOut = NULL,
187  NeighborhoodType nbhType = NHT_DEFAULT)
188 {
190  using namespace std;
191  typedef TGeomBaseObj Elem;
192  typedef typename geometry_traits<Elem>::iterator ElemIterator;
193 
194 // set up index attachment and attachment accessor
195  typedef Attachment<TIndexType> AIndex;
196  AIndex aIndex;
197  if(paIndex)
198  aIndex = *paIndex;
199 
200  if(!mg.has_attachment<Elem>(aIndex))
201  mg.attach_to<Elem>(aIndex);
202 
203  Grid::AttachmentAccessor<Elem, AIndex> aaInd(mg, aIndex);
204 
205 // init the indices and count ghosts and normal elements on the fly
206  size_t numElems = 0;
207  {
209  for(ElemIterator iter = mg.begin<Elem>(level);
210  iter != mg.end<Elem>(level); ++iter)
211  {
212  if(distGridMgr.is_ghost(*iter))
213  aaInd[*iter] = -1;
214  else
215  aaInd[*iter] = numElems++;
216  }
217  }
218 
219 // generate the nodeOffsetMap
220  nodeOffsetMapOut.clear();
221  int localNodeOffset = 0;
222 
223  int numElemsTmp = (int)numElems;
224  vector<int> elemCounts(procCom.size());
225  procCom.allgather(&numElemsTmp, 1, PCL_DT_INT,
226  &elemCounts.front(), 1, PCL_DT_INT);
227 
228  nodeOffsetMapOut.resize(procCom.size() + 1);
229  int numElemsTotal = 0;
230  for(size_t i = 0; i < elemCounts.size(); ++i){
231  nodeOffsetMapOut[i] = numElemsTotal;
232  numElemsTotal += elemCounts[i];
233  }
234  nodeOffsetMapOut[elemCounts.size()] = numElemsTotal;
235  localNodeOffset = nodeOffsetMapOut[procCom.get_local_proc_id()];
236 
237 // init the adjacencyMapStructure
238  adjacencyMapStructureOut.resize(numElems + 1);
239  adjacencyMapOut.clear();
240 
241 // construct the graph
242  vector<Elem*> vNeighbours;
243  int ind = 0;
244 
245 // generate adjacency structure first
246  for(ElemIterator iter = mg.begin<Elem>(level);
247  iter != mg.end<Elem>(level); ++iter)
248  {
249  Elem* elem = *iter;
250 
251  if(aaInd[elem] == -1)
252  continue;
253 
254  // get all neighbours
255  CollectNeighbors(vNeighbours, elem, mg, nbhType);
256 
257  // store first entry at which the connections will be written to the map
258  adjacencyMapStructureOut[ind] = adjacencyMapOut.size();
259 
260  // iterate over the neighbours and push adjacent indices to the adjacencyMap
261  for(size_t i = 0; i < vNeighbours.size(); ++i){
262  if(aaInd[vNeighbours[i]] != -1)
263  adjacencyMapOut.push_back(localNodeOffset + aaInd[vNeighbours[i]]);
264  }
265 
266  ++ind;
267  }
268 
269 // add the final element
270  adjacencyMapStructureOut[adjacencyMapStructureOut.size() - 1] = adjacencyMapOut.size();
271 
272 // fill pGeomObjsOut
273  if(pGeomObjsOut)
274  {
275  int ind = 0;
276  for(ElemIterator iter = mg.begin<Elem>(level);
277  iter != mg.end<Elem>(level); ++iter)
278  {
279  if(aaInd[*iter] != -1){
280  pGeomObjsOut[ind] = *iter;
281  ++ind;
282  }
283  }
284  }
285 
286 // clean up
287  if(!paIndex)
288  mg.detach_from<Elem>(aIndex);
289 }
290 
291 }// end of namespace
292 
293 
295 // include implementation
297 
298 #endif
Definition: pcl_process_communicator.h:70
size_t size() const
returns the size of the communicator
Definition: pcl_process_communicator.cpp:71
int get_local_proc_id(int globalProcID=pcl::ProcRank()) const
returns the proc-id relative to this communicator
Definition: pcl_process_communicator.cpp:95
void allgather(const void *sendBuf, int sendCount, DataType sendType, void *recBuf, int recCount, DataType recType) const
performs MPI_Allgather on the processes of the communicator.
Definition: pcl_process_communicator.cpp:421
manages the layouts and interfaces which are associated with a distributed grid.
Definition: distributed_grid.h:88
bool is_ghost(TElem *elem) const
returns true if the element is a ghost
Definition: distributed_grid_impl.hpp:67
the generic attachment-accessor for access to grids attachment pipes.
Definition: grid.h:182
void detach_from(IAttachment &attachment)
Definition: grid_impl.hpp:369
DistributedGridManager * distributed_grid_manager()
returns a pointer to the associated distributed grid manager.
Definition: grid_impl.hpp:53
void attach_to(IAttachment &attachment, bool passOnValues)
attach with custom pass-on-behaviour and unspecified default value.
Definition: grid_impl.hpp:296
bool has_attachment(IAttachment &attachment)
Definition: grid.h:796
Definition: multi_grid.h:72
geometry_traits< TElem >::iterator end(int level)
Definition: multi_grid.h:168
geometry_traits< TElem >::iterator begin(int level)
Definition: multi_grid.h:158
Generates the parralel dual graph of a MultiGrid as, e.g., required by Parmetis.
Definition: parallel_dual_graph.h:53
TGeomBaseObj * get_element(size_t gvrtIndex)
returns the graph-vertex for the given index
Definition: parallel_dual_graph.h:79
~ParallelDualGraph()
Definition: parallel_dual_graph_impl.hpp:55
ParallelDualGraph(MultiGrid *pmg=NULL)
Definition: parallel_dual_graph_impl.hpp:45
element_iterator_t elements_end()
returns the begin-iterator to the elements corresponding to graph vertices*‍/
Definition: parallel_dual_graph.h:91
TIndexType get_index(TGeomBaseObj *elem)
returns the graph-vertex index of the given element
Definition: parallel_dual_graph.h:94
std::vector< TGeomBaseObj * > m_elems
Definition: parallel_dual_graph.h:121
std::vector< TConnectingObj * > m_connections
Definition: parallel_dual_graph.h:122
TIndexType * adjacency_map()
Access to the graph which was generated during the last call to generate_graph.
Definition: parallel_dual_graph_impl.hpp:104
std::vector< TIndexType > m_adjacencyMapStructure
Definition: parallel_dual_graph.h:123
Grid::AttachmentAccessor< TConnectingObj, AElemIndices > m_aaElemIndices
Definition: parallel_dual_graph.h:129
void attach_data()
Definition: parallel_dual_graph_impl.hpp:131
AElemIndex m_aElemIndex
Definition: parallel_dual_graph.h:126
std::vector< TIndexType > m_adjacencyMap
Definition: parallel_dual_graph.h:124
TConnectingObj * get_connection(size_t connIndex)
returns the graph-edge for the given index
Definition: parallel_dual_graph.h:85
TIndexType * parallel_offset_map()
Access to the graph which was generated during the last call to generate_graph.
Definition: parallel_dual_graph_impl.hpp:113
bool was_considered(TGeomBaseObj *o)
Some vertices are not considered for the dual graph (e.g. ghosts).
Definition: parallel_dual_graph_impl.hpp:123
MultiGrid * m_pMG
Definition: parallel_dual_graph.h:120
std::vector< TGeomBaseObj * >::iterator element_iterator_t
Definition: parallel_dual_graph.h:55
TIndexType num_graph_vertices()
Access to the graph which was generated during the last call to generate_graph.
Definition: parallel_dual_graph_impl.hpp:78
TIndexType * adjacency_map_structure()
Access to the graph which was generated during the last call to generate_graph.
Definition: parallel_dual_graph_impl.hpp:95
Grid::AttachmentAccessor< TGeomBaseObj, AElemIndex > m_aaElemIndex
Definition: parallel_dual_graph.h:128
std::vector< TIndexType > m_nodeOffsetMap
Definition: parallel_dual_graph.h:125
Attachment< std::vector< int > > AElemIndices
Definition: parallel_dual_graph.h:117
pcl::ProcessCommunicator process_communicator() const
returns a process communicator which only contains processes which contain an element.
Definition: parallel_dual_graph.h:108
TIndexType num_graph_edges()
Access to the graph which was generated during the last call to generate_graph.
Definition: parallel_dual_graph_impl.hpp:88
pcl::ProcessCommunicator m_procCom
Definition: parallel_dual_graph.h:119
void set_grid(MultiGrid *pmg)
Definition: parallel_dual_graph_impl.hpp:63
void detach_data()
Definition: parallel_dual_graph_impl.hpp:142
AElemIndices m_aElemIndices
Definition: parallel_dual_graph.h:127
void generate_graph(int level, pcl::ProcessCommunicator procCom=pcl::ProcessCommunicator(pcl::PCD_WORLD))
generates the graph for the given level.
Definition: parallel_dual_graph_impl.hpp:154
element_iterator_t elements_begin()
returns the begin-iterator to the elements corresponding to graph vertices*‍/
Definition: parallel_dual_graph.h:88
Attachment< int > AElemIndex
Definition: parallel_dual_graph.h:116
Definition: grid_base_object_traits.h:68
NeighborhoodType
Constants to specify a neighborhood.
Definition: neighborhood.h:53
void CollectNeighbors(std::vector< Vertex * > &vNeighborsOut, Grid &grid, Vertex *vrt, uint nbhType, Grid::edge_traits::callback considerEdge, Grid::face_traits::callback considerFace, Grid::volume_traits::callback considerVol)
Collects all vertices that are connected by elements of the specified type.
Definition: neighborhood.cpp:43
@ NHT_DEFAULT
Definition: neighborhood.h:54
#define PCL_DT_INT
Definition: pcl_datatype.h:51
@ PCD_WORLD
Definition: pcl_process_communicator.h:55
#define GDIST_PROFILE_FUNC()
Definition: parallelization_util.h:41
Definition: smart_pointer.h:814
the ug namespace
void ConstructParallelDualGraphMGLevel(std::vector< TIndexType > &adjacencyMapStructureOut, std::vector< TIndexType > &adjacencyMapOut, std::vector< TIndexType > &nodeOffsetMapOut, MultiGrid &mg, size_t level, pcl::ProcessCommunicator procCom, Attachment< TIndexType > *paIndex=NULL, TGeomBaseObj **pGeomObjsOut=NULL, NeighborhoodType nbhType=NHT_DEFAULT)
Definition: parallel_dual_graph.h:179