24 #include "boost/lambda/lambda.hpp" 43 adj_of_proc( vtx_distr.np() )
80 memcpy(
vtx_XYZ+3*loc_index, xyz, 3*
sizeof(
float));
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 %d and buffer position %d. \n", sdispls[proc], buf_pos );
129 while ( ! (s)->empty() ) {
131 sendbuf[buf_pos++]=edge.from;
132 sendbuf[buf_pos++]=edge.to;
133 sendbuf[buf_pos++]=edge.weight;
147 rdispls[proc] = total_size;
148 total_size += rcounts[proc];
151 int * recvbuf =
new int [total_size+1];
154 sendbuf, scounts, sdispls,
MPI_INT,
155 recvbuf, rcounts, rdispls,
MPI_INT,
167 int size=total_size/edge_size;
168 std::sort(edges, edges + size);
179 Edge unknown_edge={-1,-1,0};
180 Edge *last_edge=&unknown_edge;
182 for(i=0;i<size;i++) {
183 if (! (*last_edge < edges[i]) )
continue;
187 "Received non-local edge: %d %d at position %d\n",edges[i].
from, edges[i].
to,i);
190 OLD_ASSERT( row <= loc_from,
"Decrease in sorted edges at %d\n",i);
192 while ( row < loc_from ) rows[++row]=i;
193 adj[i_adj]=edges[i].
to;
217 unsigned int n_proc=0;
233 DebugOut() <<
"Connectivity of subgraphs is OK.\n";
244 for(
int i_neigh=
rows[vtx]; i_neigh<
rows[vtx+1];i_neigh++) {
245 neighbour =
adj[i_neigh];
263 for(col=
rows[row]; col<
rows[row+1]; col++) {
274 int loc_row, row, row_pos;
275 int col_pos,col,loc_col;
279 for(row_pos=
rows[loc_row];row_pos<
rows[loc_row+1];row_pos++) {
284 for(col_pos=rows[loc_col]; col_pos<rows[loc_col+1]; col_pos++)
285 if (
adj[col_pos]==row)
break;
286 if (
adj[col_pos]!=row)
return false;
321 PetscMalloc(lsize_vtxs*
sizeof(
int), &
rows);
322 PetscMalloc(lsize_adj*
sizeof(
int),&
adj);
334 MatPartitioningSetAdjacency(petsc_part, petsc_adj_mat);
335 MatPartitioningSetFromOptions(petsc_part);
336 MatPartitioningApply(petsc_part,&part_IS);
339 const PetscInt *is_array;
340 ISGetIndices(part_IS, &is_array);
342 ISRestoreIndices(part_IS, &is_array);
349 MatPartitioningDestroy(&petsc_part);
350 MatDestroy(&petsc_adj_mat);
367 rows =
new int[lsize_vtxs];
368 adj =
new int[lsize_adj];
376 "METIS could be used only with localized distribution.\n");
390 #if (METIS_VER_MAJOR >= 5) 391 if (
sizeof(idx_t) !=
sizeof(
int) ) {
392 printf(
"ERROR in GRAPH_DIVIDE_C: Wrong type of integers for METIS.\n");
399 int options[METIS_NOPTIONS];
401 for (
unsigned int i = 0;i < METIS_NOPTIONS;i++) options[i] = -1;
403 options[METIS_OPTION_OBJTYPE] = METIS_OBJTYPE_CUT;
404 options[METIS_OPTION_CTYPE] = METIS_CTYPE_RM;
405 options[METIS_OPTION_IPTYPE] = METIS_IPTYPE_GROW;
406 options[METIS_OPTION_RTYPE] = METIS_RTYPE_GREEDY;
407 options[METIS_OPTION_NCUTS] = 1;
408 options[METIS_OPTION_NSEPS] = 1;
409 options[METIS_OPTION_NUMBERING] = num_flag;
410 options[METIS_OPTION_NITER] = 10;
411 options[METIS_OPTION_SEED] = 12345;
412 options[METIS_OPTION_MINCONN] = 1;
413 options[METIS_OPTION_CONTIG] = 0;
414 options[METIS_OPTION_COMPRESS] = 0;
415 options[METIS_OPTION_CCORDER] = 0;
416 options[METIS_OPTION_UFACTOR] = 30;
418 options[METIS_OPTION_DBGLVL] = 0;
423 for (
unsigned int i = 0; i < 5; i++ ) options[i] = 0;
429 for (
unsigned int i = 0; i <
vtx_distr.
lsize(); i++ ) part[i] = num_flag;
437 #if (METIS_VER_MAJOR >= 5) 438 options[METIS_OPTION_PTYPE] = METIS_PTYPE_RB;
439 options[METIS_OPTION_UFACTOR] = 1;
440 METIS_PartGraphRecursive(&n_vtx, &ncon,
rows,
adj,
442 ubvec, options, &edgecut,part);
444 METIS_PartGraphRecursive(&n_vtx,
rows,
adj,
446 &n_proc, options, &edgecut, part);
450 #if (METIS_VER_MAJOR >= 5) 451 options[METIS_OPTION_PTYPE] = METIS_PTYPE_KWAY;
452 options[METIS_OPTION_UFACTOR] = 30;
453 METIS_PartGraphKway(&n_vtx, &ncon,
rows,
adj,
455 ubvec, options, &edgecut, part);
457 METIS_PartGraphKway(&n_vtx,
rows,
adj,
459 &n_proc,options,&edgecut,part);
unsigned int size() const
get global size
unsigned int get_proc(unsigned int idx) const
get processor of the given index
ostream & operator<<(ostream &out, const SparseGraph &fcall)
Output a sparse graph.
bool check_subgraph_connectivity(int *part)
#define MessageOut()
Macro defining 'message' record of log.
SparseGraph(const Distribution &distr)
void set_vtx_position(const int vtx, const float xyz[3], int weight=1)
virtual ~SparseGraphPETSC()
int * part_to_check
created partitioning used through check of connectivity
Global macros to enhance readability and debugging, general constants.
int weight
Edge weights for communication (optional).
bool is_local(unsigned int idx) const
identify local index
#define MPI_Alltoall(sendbuf, sendcount, sendtype, recvbuf, recvcount, recvtype, comm)
void finalize()
Make sparse graph structures: rows, adj.
Virtual class for construction and partitioning of a distributed sparse graph.
Distribution vtx_distr
distribution of vertexes
virtual void allocate_sparse_graph(int lsize_vtxs, int lsize_adj)=0
unsigned int begin(int proc) const
get starting local index
vector< stack< Edge > > adj_of_proc
storage for graph edges for individual processors
virtual void partition(int *loc_part)
int proc_to_check
subgraph to check
unsigned int np() const
get num of processors
std::vector< int > checked_vtx
coloring of DFS algorithm
unsigned int myp() const
get my processor
Support classes for parallel programing.
float * vtx_XYZ
optional vertex coordinates (global array)
virtual ~SparseGraphMETIS()
virtual void allocate_sparse_graph(int lsize_vtxs, int lsize_adj)
MPI_Comm get_comm() const
Returns communicator.
Distributed sparse graphs, partitioning.
#define WarningOut()
Macro defining 'warning' record of log.
virtual void allocate_sparse_graph(int lsize_vtxs, int lsize_adj)
int * vtx_weights
Vertex weights for computations (optional).
#define DebugOut()
Macro defining 'debug' record of log.
friend bool operator<(const Edge &a, const Edge &b)
void set_edge(const int a, const int b, int weight=1)
virtual void partition(int *loc_part)
#define MPI_Alltoallv(sendbuf, sendcounts, sdispls, sendtype, recvbuf, recvcounts, rdispls, recvtype, comm)
void printf(BasicWriter< Char > &w, BasicCStringRef< Char > format, ArgList args)
unsigned int lsize(int proc) const
get local size