# Distributed Graphs in ScotchPy

Distributed graphs are implemented in ScotchPy with the DGraph class.

## The DGraph class

** WARNING: the DGraph class and related tests only work if mpi4py is installed. **

class DGraph(init=True)

  The distributed graph constructor itself calls libscotch’s `dgraphAlloc` function, and usually `dgraphInit` is called too.

  Parameters:

    init – If True, the graph allocation is followed by the init. If not, the `init()` method needs to be called before `build()` or `load()`.

  The graph object stores the arguments given to the `build()` method as integers and numpy arrays. They are accessible even when the graph has been constructed with `load()`. They default to None if the argument was not given.

  init()

    This routine Initializes the fields of the DGraph object instance. Called by a class constructor when `init=True` (by default). Mandatory before calling either `build()` or `load()`, or after calling `exit()` in order to re-use the same DGraph instance.

  exit()

    This routine cleans-up all fields of the instance. Is the opposite of the `init()` routine. Called automatically when the object is destroyed. Calling explicitly this method is only required when an `init()` call follows.

  free()

    This routine resets the instance fields so that it can hold a new DGraph topology. Is equivalent to calling `exit()` and `init()` successively.

  build(baseval=None, vertglbnbr=None, vertlocnbr=None, vertlocmax=None, vertgstnbr=None, vertloctab=None, vendloctab=None, veloloctab=None, vlblloctab=None, edgeglbnbr=None, edgelocnbr=None, edgelocsiz=None, edgeloctab=None, edgegsttab=None, edloloctab=None)

    This routine builds the distributed graph itself using the given values. Arguments should be given as ints and ideally numpy arrays of ints, although any iterable would work. Mutating these arrays is not recommended as it may cause runtime errors while Scotch handles them.

    Some arguments may be omitted, but :

      - `baseval` must be given if the graph is not compact.

      - if `vertloctab` has no size, `baseval`, `vertlocnbr` and `edgelocnbr` must be given.

  Parameters:

    - baseval (Integer) – DGraph base value for index arrays.

    - vertglbnbr (Integer) – The global number of vertices.

    - vertlocnbr (Integer) – The number of local vertices.

    - vertlocmax (Integer) – The maximum number of local vertices.

    - vertgstnbr (Integer) – The number of ghost vertices.

    - vertloctab (Any iterable of integers ideally numpy array) – The local adjacency index array (Required).

    - vendloctab (Any iterable of integers ideally numpy array) – The adjacency end index array of size vertlocnbr if disjoint from vertloctab (Optional).

    - veloloctab (Any iterable of integers ideally numpy array) – The local vertex load array of size vertlocnbr (Optional).

    - vlblloctab (Any iterable of integers ideally numpy array) – The vertex label array of size vertlocnbr (Optional).

    - edgeglbnbr (Integer) – The global number of edges.

    - edgelocnbr (Integer) – The number of local edges.

    - edgelocsiz (Integer) – The size of the local edge array.

    - edgeloctab (Any iterable of integers ideally numpy array) – The local adjacency array of size edgelocsiz (more if not compact) (Required).

    - edgegsttab (Any iterable of integers ideally numpy array) – The global adjacency array of size edgelocsiz (more if not compact) (Required).

    - edloloctab (Any iterable of integers ideally numpy array) – The local arc load array of size edgelocsiz (Optional).

  build_grid_3d(baseval, dimxval, dimyval, dimzval, incrval, flagval)

    This routine fills the distributed graph with the description of a 3D grid of dimensions `dimxval`, `dimyval` and `dimzval`, using `baseval` as the base value for vertex and edge indices.

  Parameters:

    - baseval (Integer) – The base value for index arrays.

    - dimxval (Integer) – The number of vertices in the X dimension.

    - dimyval (Integer) – The number of vertices in the Y dimension.

    - dimzval (Integer) – The number of vertices in the Z dimension.

    - incrval (Integer) – The increment value for vertex indices.

    - flagval (Integer) –

      The flagval value is a combination of the following integer values,

        that may be added or bitwise-ored:

      - `1` : 26-neighbor mesh (defaults at 6-neighbor mesh).

      - `2` : torus (defaults at mesh)

      - `4` : weighted vertices (defaults at no weights).

      - `8` : weighted edges (ddefaults at no weights).

  load(stream, baseval=-1, flagval=0)

    This routine builds the distributed graph with `build()` from data included in the given file or stream.

  Parameters:

    - stream (Either a file object (result of an `open()`, don’t forget to close it) or a filename, as a string or as a bytes object (such as `b"file/name"`)) – Input file or stream to read from.

    - baseval (Integer) – The graph base value for index arrays(0 or 1), takes the baseval value from the `stream` data if -1.

    - flagval (Integer) –

      The flagval value is a combination of the following integer values, that may be added or bitwise-ored:

      - `0` : Keep vertex and edge weights if they are present in the stream data.

      - `1` : Remove vertex weights. The graph read will have all of its vertex weights set to one, regardless of what is specified in the stream data.

      - `2` : Remove edge weights. The graph read will have all of its edge weights set to one, regardless of what is specified in the stream data.

  The following routines can’t be called before the graph is properly built either with DGraph.build or with DGraph.load:

  save(stream)

    This routine saves the distributed graph to the given file or stream in the Scotch graph format.

  Parameters:

    stream (Either a file object (result of an `open()`, don’t forget to close it) or a filename, as a string or as a bytes object (such as `b"file/name"`)) – input file or stream to read from.

  check()

    Runs a self-test to check data consistency after the `build()` or `load()` method is called, raises a `LibraryError` if not.

  data(as_dict=None)

    This routine returns the values taken by the `build()` method. The arrays are returned as numpy arrays.

  Parameters:

    as_dict (Boolean) – If True, the requested data is returned as a dict. If not, it is returned as a 15-element tuple.

  Returns:

    Values in this order: (`baseval`, `vertglbnbr`, `vertlocnbr`, `vertlocmax`, `vertgstnbr`, `vertloctab`, `vendloctab`, `veloloctab`, `vlblloctab`, `edgeglbnbr`, `edgelocnbr`, `edgelocsiz`, `edgeloctab`, `edgegsttab`, `edloloctab`).

  Return type:

    Tuple or Dict

  size(as_dict=None)

    This routine returns the values of `edgeglbnbr`, `edgelocnbr`, `vertlocnbr` and `vertglbnbr` taken by the `build()` method.

  Parameters:

    as_dict (Boolean) – If True, the requested data is returned as a dict. If not, it is returned as a 4-element tuple.

  Returns:

    Values in this order: (`edgeglbnbr`, `edgelocnbr`, `vertlocnbr`, `vertglbnbr`).

  Return type:

    Tuple or Dict

  part(partnbr, strat=Strat(init=True), partloctab=None)

    This routine computes a vertex-separated partition, into `partnbr` parts, of the graph itself, with respect to the given strategy.

  Parameters:

    - partnbr (Integer) – The number of parts in the partitioning.

    - strat (`Strat`) – Strategy to be used for the partitioning.

    - partloctab (Any kind of iterable or a numpy array) – The local partition array. If given as a list or numpy array of integers, it is updated with the returned values.

  induce_part(orgpartloctab, indpartval, indvertlocnbr, indgraf)

    This routine induces a partition of the distributed graph itself from the given partition array `orgpartloctab` to the induced distributed graph `indgraf` with respect to the given induced partition value `indpartval` and the number of local vertices `indvertlocnbr`.

  Parameters:

    - orgpartloctab (Any kind of iterable or a numpy array) – The original partition array.

    - indpartval (Integer) – The induced partition value.

    - indvertlocnbr (Integer) – The number of local vertices.

    - indgraf (`DGraph`) – The induced graph.

  map(arch, strat=Strat(init=True), partloctab=None)

    This routine computes a mapping of the distributed graph itself onto the given target architecture `arch` , with respect to the given strategy `strat`.

  Parameters:

    - arch (`Arch`) – The target architecture.

    - strat (`Strat`) – Strategy to be used for the mapping.

    - partloctab (Any kind of iterable or a numpy array) – The partition array. If given as a list or numpy array of integers, it is updated with the returned values.

  map_init(mapping, arch, partloctab=None)

    This routine initializes an API opaque mapping with respect to the distributed graph itself and the given parameters.

  Parameters:

    - mapping (`Mapping`) – The mapping to be initialized.

    - arch (`Arch`) – The target architecture.

    - partloctab (Any kind of iterable or a numpy array) – The partition array. If given as a list or numpy array of integers, it is updated with the returned values.

  map_exit(mapping)

    This routine frees an API mapping instance.

  Parameters:

    mapping (`Mapping`) – The mapping to be freed.

  map_view(mapping, stream)

    This routine writes mapping statistics (load of target processors, number of neigh- boring domains, average dilation and expansion, edge cut size, distribution of edge dilations) to the given stream.

  Parameters:

    - mapping (`Mapping`) – The mapping to be viewed.

    - stream (Either a file object (result of an `open()`, don’t forget to close it) or a filename, as a string or as a bytes object (such as `b"file/name"`)) – Input file or stream to write to.

  map_compute(mapping, strat)

    This routine computes a mapping of the API mapping structure `mapping` with respect to the given strategy `strat` .

  Parameters:

    - mapping (`Mapping`) – The mapping to be computed.

    - strat (`Strat`) – Strategy to be used for the mapping .

  map_save(mapping, stream)

    This routine saves the contents of the given user mapping `mapping` to the given stream `stream`.

  Parameters:

    - mapping (`Mapping`) – The mapping to be saved.

    - stream (Either a file object (result of an `open()`, don’t forget to close it) or a filename, as a string or as a bytes object (such as `b"file/name"`)) – Input file or stream to write to.

  map_view(mapping, stream)

    This routine writes mapping statistics (load of target processors, number of neigh- boring domains, average dilation and expansion, edge cut size, distribution of edge dilations) to the given stream.

  Parameters:

    - mapping (`Mapping`) – The mapping to be displayed.

    - stream (Either a file object (result of an `open()`, don’t forget to close it) or a filename, as a string or as a bytes object (such as `b"file/name"`)) – Input file or stream to write to.

  order_init(ordering)

    This routine initializes an ordering instance.

  Parameters:

    ordering (`Ordering`) – Ordering to be initialized.

  order_exit(ordering)

    This routine frees an ordering instance.

  Parameters:

    ordering (`Ordering`) – Ordering to be freed.

  order_compute(ordering, strat)

    This routine computes a block ordering of the distributed graph itself with respect to the given strategy `strat`. Stores the result in the given ordering instance `ordering`.

  Parameters:

    - ordering (`Ordering`) – Ordering to be computed.

    - strat (`Strat`) – Strategy to be used for the ordering.

  order_save(ordering, stream)

    This routine saves the contents of the given ordering instance `ordering` to the given stream `stream`.

  Parameters:

    - ordering (`Ordering`) – Ordering to be saved.

    - stream (Either a file object (result of an `open()`, don’t forget to close it) or a filename, as a string or as a bytes object (such as `b"file/name"`)) – Input file or stream to write to.

  order_cblk_dist(ordering)

    This routine returns the global number of distributed elimination tree (super-)nodes possessed by the given distributed ordering instance `ordering`.

  Parameters:

    ordering (`Ordering`) – Ordering to be used.

  order_save_map(ordering, stream)

    This routine saves the contents of the given ordering instance `ordering` to the given stream `stream` in the Scotch mapping format.

  Parameters:

    - ordering (`Ordering`) – Ordering to be saved.

    - stream (Either a file object (result of an `open()`, don’t forget to close it) or a filename, as a string or as a bytes object (such as `b"file/name"`)) – Input file or stream to write to.

  order_save_tree(ordering, stream)

    This routine saves the contents of the given ordering instance `ordering` to the given stream `stream` in the tree output format format.

  Parameters:

    - ordering (`Ordering`) – Ordering to be saved.

    - stream (Either a file object (result of an `open()`, don’t forget to close it) or a filename, as a string or as a bytes object (such as `b"file/name"`)) – Input file or stream to write to.

  order_perm(ordering, permloctab=None)

    This routine fills the distributed direct permutation array `permloctab` with the inverse permutation of the ordering array `ordering`.

  Parameters:

    - ordering (`Ordering`) – Ordering to be used.

    - permloctab (Any kind of iterable or a numpy array) – The permutation array or size vertlocnbr. If given as a list or numpy array of integers, it is updated with the returned values.

  order_tree_dist(ordering, treeglbtab=None, sizeglbtab=None)

    This routine fills on all processes the arrays representing the distributed part of the elimination tree associated with the given ordering instance `ordering`.

  Parameters:

    - ordering (`Ordering`) – Ordering to be used.

    - treeglbtab (Any kind of iterable or a numpy array) – The global elimination tree array. If given as a list or numpy array of integers, it is updated with the returned values.

    - sizeglbtab (Any kind of iterable or a numpy array) – The global size array. If given as a list or numpy array of integers, it is updated with the returned values.

  centralized_order_exit(cordering)

    This routine frees a centralized ordering instance.

  Parameters:

    cordering (`Ordering`) – Centralized ordering to be freed.

  centralized_order_init(cordering, permtab=None, peritab=None, cblknbr=None, rangtab=None, treetab=None)

    This routine fills the centralized ordering instance `cordering` with the given parameters.

  Parameters:

    - cordering (`Ordering`) – Centralized ordering to be filled.

    - permtab (Any kind of iterable or a numpy array) – The ordering permutation array.

    - peritab (Any kind of iterable or a numpy array) – The inverse ordering permutation array.

    - cblknbr (Integer) – The number of column blocks.

    - rangtab (Any kind of iterable or a numpy array) – The column block span array.

    - treetab (Any kind of iterable or a numpy array) – The separators tree array.

  grow(seedlocnbr, seedloctab, distmax, partgsttab=None)

    This routine grows areas of the distributed graph itself from a set of colored seeds provided on each process.

  Parameters:

    - seedlocnbr (Integer) – The number of local vertices in the seed.

    - seedloctab (Any kind of iterable or a numpy array) – The local vertex array of the seed.

    - distval (Integer) – The distance value.

    - partgsttab (Any kind of iterable or a numpy array) – The ghost partition array. If given as a list or numpy array of integers, it is updated with the returned values.

  coarsen(coarnbr, coarrat, flagval, coargraf, multloctab=None)

    This routine coarsens the graph itself with respect to the given parameters. The coarsened distributed graph is created only if it comprises more than `coarnbr` vertices, or if the coarsening ratio is lower than `coarrat`. Valid coarsening ratio values range from 0.5 (in the case of a perfect matching) to 1.0 (if no vertex could be coarsened). Classical threshold values range from 0.7 to 0.8. Raises `CannotCoarsen` if not because of threshold parameters, raises `LibraryError` otherwise.

  Parameters:

    - coarnbr – Number of vertices in the coarsened graph.

    - coarrat (Floating-point number) – Coarsening ratio.

    - flagval (Integer) – The flagval flag specifies the type of coarsening

    - coargraf (`DGraph`) – Another `DGraph` instance, which gets modified.

    - multloctab – The vertex-to-vertex multiplicity array. If given as a list or numpy array of integers, it is updated with the returned values.

  stat(as_dict=False)

    This routine gives various stats about the distributed graph:

    - `velomin`, `velomax`, `velosum`, `veloavg`, `velodlt`, are the minimum vertex load, the maximum vertex load, the sum of all vertex loads, the average vertex load and the variance of the vertex degrees, respectively.

    - `degrmin`, `degrmax`, `degravg`, `degrdlt`, are the minimum vertex degree, the maximum vertex degree, the average vertex degree and the variance of the vertex degrees, respectively.

    - `edlomin`, `edlomax`, `edlosum`, `edloavg`, `edlodlt` are the minimum edge load, the maximum edge load, the sum of all edge loads, the average edge load and the variance of the edge loads, respectively.

    Parameters:

      as_dict (Boolean) – If True, the requested data is returned as a dict. If not, it is returned as a 14-element tuple.

    Returns:

      various stats about the distributed graph, in this specific order :(`velomin`, `velomax`, `velosum`, `veloavg`, `velodlt`, `degrmin`, `degrmax`, `degravg`, `degrdlt`, `edlomin`, `edlomax`, `edlosum`, `edloavg`, `edlodlt`).

    Return type:

      Tuple or Dict

  coarsen_vert_loc_max(flagval)

    This routine computes an upper bound on the local number of coarse vertices that can be created by the coarsening process.

  Parameters:

    flagval (Integer) – The flagval flag specifies the type of coarsening.

  Returns:

    The upper bound on the local number of coarse vertices.

  Return type:

    Integer

  gather(cgrf)

    This routine gathers the contents of the distributed graph itself into the centralized graph `cgrf`.

  Parameters:

    cgrf (`Graph`) – The centralized graph to be filled.

  scatter(cgrf)

    This routine scatters the contents of the centralized graph `cgrf` into the distributed graph itself.

  Parameters:

    cgrf (`Graph`) – The centralized graph to be scattered.

  redist(partloctab, permgsttab, vertlocdlt, edgelocdlt, redgraf)

    This routine initializes and fills the redistributed graph `redgraf` with a new distributed graph made from the original graph itself and the given parameters.

  Parameters:

    - partloctab (Any kind of iterable or a numpy array) – The partition array.

    - permgsttab (Any kind of iterable or a numpy array) – The global permutation array.

    - vertlocdlt (Any kind of iterable or a numpy array) – The local vertex weight array.

    - edgelocdlt (Any kind of iterable or a numpy array) – The local edge weight array.

    - redgraf (`DGraph`) – The redistributed graph.

  ghst()

    This routine fills the `edgegsttab` array of the distributed graph itself with the local and ghost vertex indices corresponding to the global vertex indices contained in the `edgeloctab` array.

  halo(datatab, typeval)

    This routine propagates the data borne by local vertices to all of the corresponding halo vertices located on neighboring processes.

  Parameters:

    - datatab (Any kind of iterable or a numpy array) – The data array to be propagated of size `vertgstnbr` at least.

    - typeval (Integer) – The type of data to be propagated.

  halo_async(datatab, typeval, requ)

    This routine propagates the data borne by local vertices to all of the corresponding halo vertices located on neighboring processes, asynchronously.

  Parameters:

    - datatab (Any kind of iterable or a numpy array) – The data array to be propagated of size `vertgstnbr` at least.

    - typeval (Integer) – The type of data to be propagated.

    - requ (`HaloReq` instance) – HaloReq data structure.

  halo_wait(requ)

    This routine waits for the completion of the asynchronous halo exchange process.

  Parameters:

    requ (`HaloReq` instance) – HaloReq data structure.

Various functions are defined as wrappers of DGraph operations:

dgraph_alloc()

  Recreates the `dgraphAlloc` function, returning a non-initialized `DGraph` instance. It will need the `init()` method to be called before the instance be built or loaded upon.

build_dgraph(*args, **kwargs)

  Returns a properly built graph instance. Positional and keyword arguments need to be given in the same fashion as `DGraph.build()` takes them.

load_dgraph(*args, **kwargs)

  Returns a distributed graph instance loaded from the given file or stream. Positional arguments need to be given in the same fashion as `DGraph.load()` takes them.

There is no explicit equivalent to Scotch’s `memFree` function, since its call is included in the class destructor. To delete the `graf` variable and free the related graph structure before the local scope expires, simply use:

    del graf

However, due to how Python’s garbage-collector works, the `memFree` function may not be called immediately.

## Good practices

All in all, the Python and ScotchPy good practices tend not to use the `init()` and `exit()` methods and the `DGraph` constructor. They return unfinished and per se unusable objects, since they are included for compatibility with the C version of PT-Scotch. The use of the `build_dgraph()` or `load_dgraph()` functions is therefore advised.