24 #include "boost/lambda/lambda.hpp"
43 adj_of_proc( vtx_distr.np() )
54 : vtx_distr(loc_size, comm),
58 adj_of_proc( vtx_distr.np() )
80 memcpy(
vtx_XYZ+3*loc_index, xyz, 3*
sizeof(
float));
100 ASSERT(
adj==NULL ).error(
"Graph is already finalized\n");
105 unsigned int edge_size=3;
117 sdispls[proc] = total_size;
118 scounts[proc] = edge_size * (s)->size();
119 total_size += edge_size * ((s)->size)();
121 int * sendbuf =
new int [(total_size+1)];
128 "Mismatch between displacement and buffer position.\n");
129 while ( ! (s)->empty() ) {
131 sendbuf[buf_pos++]=
edge.from;
132 sendbuf[buf_pos++]=
edge.to;
133 sendbuf[buf_pos++]=
edge.weight;
152 rdispls[proc] = total_size;
153 total_size += rcounts[proc];
156 int * recvbuf =
new int [total_size+1];
159 sendbuf, scounts, sdispls,
MPI_INT,
160 recvbuf, rcounts, rdispls,
MPI_INT,
172 int size=total_size/edge_size;
173 std::sort(edges, edges + size);
184 Edge unknown_edge={-1,-1,0};
185 Edge *last_edge=&unknown_edge;
187 for(i=0;i<size;i++) {
188 if (! (*last_edge < edges[i]) )
continue;
192 "Received non-local edge at position 'i'\n");
195 ASSERT( row <= loc_from )(i).error(
"Decrease in sorted edges at 'i'\n");
197 while ( row < loc_from )
rows[++row]=i;
198 adj[i_adj]=edges[i].
to;
222 unsigned int n_proc=0;
238 DebugOut() <<
"Connectivity of subgraphs is OK.\n";
247 ASSERT( vtx>=0 && vtx< (
int)
vtx_distr.
size() )(vtx).error(
"Invalid entry vertex in DFS.\n");
249 for(
int i_neigh=
rows[vtx]; i_neigh<
rows[vtx+1];i_neigh++) {
250 neighbour =
adj[i_neigh];
263 ASSERT(
adj ).error(
"Can not view non finalized graph.\n");
268 for(col=
rows[row]; col<
rows[row+1]; col++) {
279 int loc_row, row, row_pos;
280 int col_pos,col,loc_col;
284 for(row_pos=
rows[loc_row];row_pos<
rows[loc_row+1];row_pos++) {
289 for(col_pos=
rows[loc_col]; col_pos<
rows[loc_col+1]; col_pos++)
290 if (
adj[col_pos]==row)
break;
291 if (
adj[col_pos]!=row)
return false;
327 PetscMalloc(lsize_vtxs*
sizeof(
int), &
rows);
328 PetscMalloc(lsize_adj*
sizeof(
int),&
adj);
335 ASSERT(
adj &&
rows ).error(
"Can not make partition of non finalized graph.\n");
345 const PetscInt *is_array;
346 ISGetIndices(
part_IS, &is_array);
348 ISRestoreIndices(
part_IS, &is_array);
373 rows =
new int[lsize_vtxs];
374 adj =
new int[lsize_adj];
382 .error(
"METIS could be used only with localized distribution.\n");
396 #if (METIS_VER_MAJOR >= 5)
397 if (
sizeof(idx_t) !=
sizeof(
int) ) {
398 printf(
"ERROR in GRAPH_DIVIDE_C: Wrong type of integers for METIS.\n");
405 int options[METIS_NOPTIONS];
407 for (
unsigned int i = 0;i < METIS_NOPTIONS;i++) options[i] = -1;
409 options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_CUT;
410 options[METIS_OPTION_CTYPE] = METIS_CTYPE_RM;
411 options[METIS_OPTION_IPTYPE] = METIS_IPTYPE_GROW;
412 options[METIS_OPTION_RTYPE] = METIS_RTYPE_GREEDY;
413 options[METIS_OPTION_NCUTS] = 1;
414 options[METIS_OPTION_NSEPS] = 1;
415 options[METIS_OPTION_NUMBERING] = num_flag;
416 options[METIS_OPTION_NITER] = 10;
417 options[METIS_OPTION_SEED] = 12345;
418 options[METIS_OPTION_MINCONN] = 1;
419 options[METIS_OPTION_CONTIG] = 1;
420 options[METIS_OPTION_COMPRESS] = 0;
421 options[METIS_OPTION_CCORDER] = 0;
422 options[METIS_OPTION_UFACTOR] = 30;
424 options[METIS_OPTION_DBGLVL] = 0;
429 for (
unsigned int i = 0; i < 5; i++ ) options[i] = 0;
435 for (
unsigned int i = 0; i <
vtx_distr.
lsize(); i++ ) part[i] = num_flag;
443 #if (METIS_VER_MAJOR >= 5)
444 options[METIS_OPTION_PTYPE] = METIS_PTYPE_RB;
445 options[METIS_OPTION_UFACTOR] = 1;
446 METIS_PartGraphRecursive(&n_vtx, &ncon,
rows,
adj,
448 ubvec, options, &edgecut,part);
450 METIS_PartGraphRecursive(&n_vtx,
rows,
adj,
452 &n_proc, options, &edgecut, part);
456 #if (METIS_VER_MAJOR >= 5)
457 options[METIS_OPTION_PTYPE] = METIS_PTYPE_KWAY;
458 options[METIS_OPTION_UFACTOR] = 30;
459 METIS_PartGraphKway(&n_vtx, &ncon,
rows,
adj,
461 ubvec, options, &edgecut, part);
463 METIS_PartGraphKway(&n_vtx,
rows,
adj,
465 &n_proc,options,&edgecut,part);
#define ASSERT_PERMANENT(expr)
Allow use shorter versions of macro names if these names is not used with external library.
#define ASSERT_EQ(a, b)
Definition of comparative assert macro (EQual) only for debug mode.
bool is_local(unsigned int idx) const
identify local index
unsigned int myp() const
get my processor
unsigned int begin(int proc) const
get starting local index
unsigned int lsize(int proc) const
get local size
unsigned int get_proc(unsigned int idx) const
get processor of the given index
MPI_Comm get_comm() const
Returns communicator.
unsigned int size() const
get global size
unsigned int np() const
get num of processors
virtual void partition(int *loc_part)
virtual void allocate_sparse_graph(int lsize_vtxs, int lsize_adj)
virtual ~SparseGraphMETIS()
MatPartitioning petsc_part
virtual void partition(int *loc_part)
virtual void allocate_sparse_graph(int lsize_vtxs, int lsize_adj)
virtual ~SparseGraphPETSC()
Virtual class for construction and partitioning of a distributed sparse graph.
float * vtx_XYZ
optional vertex coordinates (global array)
int proc_to_check
subgraph to check
int * vtx_weights
Vertex weights for computations (optional).
void set_vtx_position(const int vtx, const float xyz[3], int weight=1)
virtual void allocate_sparse_graph(int lsize_vtxs, int lsize_adj)=0
void set_edge(const int a, const int b, int weight=1)
void finalize()
Make sparse graph structures: rows, adj.
vector< stack< Edge > > adj_of_proc
storage for graph edges for individual processors
Distribution vtx_distr
distribution of vertexes
int * part_to_check
created partitioning used through check of connectivity
std::vector< int > checked_vtx
coloring of DFS algorithm
SparseGraph(const Distribution &distr)
bool check_subgraph_connectivity(int *part)
Support classes for parallel programing.
#define WarningOut()
Macro defining 'warning' record of log.
#define MessageOut()
Macro defining 'message' record of log.
#define DebugOut()
Macro defining 'debug' record of log.
#define MPI_Alltoall(sendbuf, sendcount, sendtype, recvbuf, recvcount, recvtype, comm)
#define MPI_Alltoallv(sendbuf, sendcounts, sdispls, sendtype, recvbuf, recvcounts, rdispls, recvtype, comm)
void printf(BasicWriter< Char > &w, BasicCStringRef< Char > format, ArgList args)
ostream & operator<<(ostream &out, const SparseGraph &)
Output a sparse graph.
bool operator<(const SparseGraph::Edge &a, const SparseGraph::Edge &b)
Distributed sparse graphs, partitioning.
int weight
Edge weights for communication (optional).
void chkerr(unsigned int ierr)
Replacement of new/delete operator in the spirit of xmalloc.