Loading [MathJax]/extensions/tex2jax.js
ug4
All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Modules Pages
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
42namespace ug
43{
44
46
51template <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
178template <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,
185 Attachment<TIndexType>* paIndex = NULL,
186 TGeomBaseObj** pGeomObjsOut = NULL,
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
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
A generic specialization of IAttachment.
Definition attachment_pipe.h:263
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 begin(int level)
Definition multi_grid.h:158
geometry_traits< TElem >::iterator end(int level)
Definition multi_grid.h:168
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
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
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
TConnectingObj * get_connection(size_t connIndex)
returns the graph-edge for the given index
Definition parallel_dual_graph.h:85
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