Constructing the N graph
// C++
#include <ngraph.h>
// FORTRAN
use engpar
There are four functions required to construct an N-Graph. The first is a call to create an empty graph:
// C++
agi::Ngraph* g = createEmptyGraph();
// FORTRAN
type(c_ptr) :: graph
graph = cengpar_createEmptyGraph()
For the remaining three steps arrays must be filled with the appropriate data and passed into the N-graph to construct each part of the graph.
The first set of data sets up the vertices and sets the type of edges to either traditional or hyperedges. The function looks like the following:
// C++
void constructVerts(bool isHG, lid_t num_verts,
gid_t* verts, wgt_t* weights);
// FORTRAN
call cengpar_constructVerts(graph, isHG, verts, weights, nverts)
The isHG input argument indicates if the graph uses hyperedges (true or 1)
or not (false or 0). num_verts is the number of vertices on part.
The verts argument is a list of num_verts globally unique ids
for the vertices of the graph owned by the process. The weights argument is a
list of weights of each vertex. If the weights argument is omitted or set to NULL, the weights
will be uniformly assigned to 1. In the FORTRAN interface function nverts
specifies the number of entries in the verts and weights lists, and graph
is the opaque pointer to the Ngraph structure.
The FORTRAN interface numbers vertices starting with 1.
The C++ interface numbers vertices starting with 0.
The next set of data creates the adjacencies between the vertices just constructed. This data is provided with the following function:
// C++
etype constructEdges(gid_t num_edges, gid_t* edge_ids,
lid_t* degs, gid_t* pins,
wgt_t* e_weights);
// FORTRAN
call cengpar_constructEdges(graph, edge_ids, degs, weights, pins, nedges, npins)
The num_edges argument specifies the number of edges that are on this process, including the edges that are cut at the part boundaries. The argument edge_ids is similar to the vertex array in the previous call; it
provides a list of global edge ids. Unlike vertices though, a given edge id may appear
on multiple processes, if it is cut by the part boundary (i.e, it spans two or more parts).
The argument degs is a list defining how many vertices (both, on- and
off-process) are incident to each edge.
For a traditional graph, the degree of each edge will be two. The degree of
hyperedges is application dependent. The pins argument is the list of vertex
global ids incident to each (hyper)edge. The length of the pins list should
be equal to the sum of degrees in the degs list. The e_weights act the same way as the vertex weights.
If omitted or set to NULL, the default will uniformly set the weights to 1.
If there is more than one type of adjacency between the vertices, then multiple
edge types can be constructed by calling the constructEdges function once for
each type of adjacency. The value returned by the function is
an identifier for the edge type constructed and can be used to access that type
of edge in the APIs for the N-Graph.
The final set of data to set up is the layer of ghost vertices required by the
N-Graph. Specifically, for every vertex in the list of pins that is not locally
owned the remote owner of that vertex is required.
// C++
void constructGhosts(std::unordered_map<gid_t, part_t>& owns);
// FORTRAN
call cengpar_constructGhosts(graph, ghostverts, ghostowners, nghosts)
In the C++ interface the association of a ghost vertex global id with the owner part is
is defined by the owns map. In the FORTRAN interface two lists, ghostverts
and ghostowners of length nghosts define the association.
Once the graph has been constructed you can verify that the adjacency is correct by running the following function:
// C++
agi::checkValidity(g);
// FORTRAN
call cengpar_checkValidity(graph);
Finally, after everything that is needed with the N-Graph is completed, the following function should be called to destroy the graph and clean up all its memory.
// C++
agi::destroyGraph(g)
// FORTRAN
call cengpar_destroyGraph(graph);
The figure above depicts a mixed mesh on two processes with a vertex-based
partition.
There are six mesh elements labelled a through f.
Five of the elements are triangles and one is a quadrilateral.
The eight mesh vertices are labelled 0 through 7.
Mesh edges are not labelled.
The mesh elements on each part are defined by the locally owned vertices, and
the elements they are adjacent to.
Vertices 0, 1, and 2 are owned by part 0, P0. The remaining vertices
are owned by part 1, P1.
Due to this assignment of vertices, elements c, b, and d span the part
boundary between P0 and P1 and exist on both parts.
The lists shown to the right of the figure define the information needed to create an Ngraph with hyperedges from this partitioned mesh. For each mesh vertex a graph vertex is created. Likewise, for each mesh element a hyperedge is created.
Locally owned mesh vertices, and their weights, are defined by the vertices
and vtxWeights lists.
For this example we assume that the graph vertices are uniformly weighted.
Next, the hyperedges, and their weights, are created via the edges and
edgeWeights lists.
In the figure a hyperedge is marked with a square.
Note that the elements spanning the part boundary (c,b, and d) exist in
the edges list of both P0 and P1.
The weights associated with each type of element are symbolically denoted as t
and q, respectively.
Additional information is needed to complete the definition of hyperedges from
mesh elements and the vertices on their closure.
First, the number of vertices on the closure of each element defines the degree
of the hyperedges; i.e., degree(triangle)=3 and degree(quad)=4.
Next, the list of vertices on the closure are listed in pins.
In the figure a pin is depicted as an hashed edge between a hyperedge and a vertex.
Finally, each non-local vertex that exists in the pins list is placed in the
ghostVertices list along with its corresponding remote process id in the
ghostOwners list.
Like the ParMETIS_V3_PartKway distributed CSR, we use a global graph vertex numbering. The ParMETIS xadj array defines how many edges are incident to each locally owned graph vertex and the adjncy array defines the second vertex needed to defined each of the edges. These two arrays are replaced in the EnGPar graph construction by the element to vertex adjacencies arrays (edges, deg, and pins). For non-simplex elements (quadrilateral, hexahedron, etc.) this provides EnGPar additional information that is lost during the graph construction for ParMETIS; specifically, the relationship between vertices on opposing sides of the element (e.g., vertex 4 and 5 in the example above). The ParMETIS global offset array of vertex ownership, vtxdist, is replaced by information that defines the ownership of un-owned graph vertices (ghostVertices and ghostOwners). Applications producing the vtxdist array will easily be able to build the ghostOwners array. Likewise, creating the ghostVertices array, uses the same information that ParMETIS required in the adjncy array; the global id of a vertex (that defines an edge in ParMETIS, or for EnGPar, a vertex on the closure of an element) that is not locally owned.