Constructing the N graph

Construct the N-Graph

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 vectors must be filled with the appropriate data and passed into the N-graph to construct each part of the graph.

Constructing the vertices

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,
                      std::vector<gid_t>& verts,
                      std::vector<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). The verts argument is a list of 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 this list is provided as empty 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.

Constructing the edges

The next set of data creates the adjacencies between the vertices just constructed. This data is provided with the following function:

  // C++
  etype constructEdges(std::vector<gid_t>& edge_ids,
                       std::vector<lid_t>& degs,
                       std::vector<gid_t>& pins,
                       std::vector<wgt_t>& weights);
  // FORTRAN
  call cengpar_constructEdges(graph, edge_ids, degs, weights, pins, nedges, npins)

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 dependant. 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.

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.

Constructing the layer of ghosts

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);