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.