Graphs in ScotchPy¶

Graphs are implemented in ScotchPy with the Graph class.

The Graph class¶

class Graph(init=True)¶

The graph constructor itself calls libscotch’s graphAlloc function, and usually graphInit 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 Graph 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 Graph 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 Graph topology. Is equivalent to calling exit() and init() successively.

build(baseval=None, vertnbr=None, verttab=None, vendtab=None, velotab=None, vlbltab=None, edgenbr=None, edgetab=None, edlotab=None)¶

This routine builds the 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 verttab has no size, baseval, vertnbr and edgenbr must be given.

Parameters:

baseval (Integer) – Graph base value for index arrays.
vertnbr (Integer) – Number of vertices.
verttab (Any iterable of integers ideally numpy array) – Adjacency index array (Required).
vendtab (Any iterable of integers ideally numpy array) – Adjacency end index array of size vertnbr if disjoint from verttab (Optional).
velotab (Any iterable of integers ideally numpy array) – Vertex load array of size vertnbr (Optional).
vlbltab (Any iterable of integers ideally numpy array) – Vertex label array of size vertnbr (Optional).
edgenbr (Integer) – Number of arcs (which is twice the number of edges).
edgetab (Any iterable of integers ideally numpy array) – Adjacency array of size edgenbr (more if not compact) (Required).
edlotab (Any iterable of integers ideally numpy array) – Arc load array of size edgenbr (Optional).

build_from_csgraph(csg)¶

This routine builds the graph csg using build().

Parameters:: csg (scipy.sparse.csr_matrix) – A scipy.csgraph matrix.

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

This routine builds the 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 Graph.build or with Graph.load:

base(baseval)¶

This routine re-sets the baseval value and modifies the stored arrays to maintain data consistency.

Parameters:: baseval (Integer) – Graph base value for index arrays.
Returns:: Former baseval value.
Return type:: Integer

save(stream)¶

This routine saves the 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 9-element tuple.
Returns:: Values in this order: (baseval, vertnbr, verttab, vendtab, velotab, vlbltab, edgenbr, edgetab, edlotab) .
Return type:: Tuple or Dict

size(as_dict=None)¶

This routine returns the values of edgenbr and vertnbr 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 2-element tuple.
Returns:: The values of edgenbr and vertnbr.
Return type:: Tuple or Dict

diam_pv()¶

This routine computes the the edge-weighted (pseudo) diameter of the graph and returns it.

Returns:: The graph’s diameter.
Return type:: Integer

stat(as_dict=None)¶

This routine gives various stats about the 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 graph, in this specific order :(velomin, velomax, velosum, veloavg, velodlt, degrmin, degrmax, degravg, degrdlt, edlomin, edlomax, edlosum, edloavg, edlodlt).
Return type:: Tuple or Dict

color(colotab=None, flagval=0)¶

This routine creates a color array for the given graph. To get the colonum value, the built-in max function can be called on colortab.

Parameters:

colotab (Any iterable of integers ideally numpy array) – If given as a list or numpy array of integers, it is updated with the returned values.
flagval (Integer) – Defaults to 0, not used for now.

tab_save(stream, parttab=None)¶

This routine saves the partition array parttab to the given file or stream in the Scotch mapping 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 write to.
parttab (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.

tab_load(stream, parttab=None)¶

This routine loads the partition array parttab from 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.
parttab (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.

part(partnbr, strat=Strat(init=True), parttab=None)¶: This routine computes an edge-separated partition ,into partnbr parts, of the graph itself, with respect to the given strategy.

Parameters:

partnbr (Integer) – The number of parts.
strat (Strat) – A Strat instance to be used for the partitioning.
parttab (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.

part_fixed(partnbr, strat=Strat(init=True), parttab=None)¶: This routine computes a edge-separated partition, into partnbr parts, of the graph itself, with respect to the given strategy and the fixed vertices in maptab.

Parameters:

partnbr (Integer) – The number of parts.
strat (Strat) – Strategy to be used for the partitioning.
parttab (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.

part_ovl(partnbr, strat=Strat(init=True), parttab=None)¶: This routine computes an overlapped vertex-separated partition, into partnbr parts, of the graph itself, with respect to the given strategy and the fixed vertices in maptab.

Parameters:

partnbr (Integer) – The number of parts.
strat (Strat) – Strategy to be used for the partitioning.
parttab (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.

induce_list(vnumnbr, vnumtab, indgraf)¶: This routine computes the induced graph of the graph itself, with respect to the given vertex list.

Parameters:

vnumnbr (Integer) – The number of vertices in the list.
vnumtab (Any kind of iterable or a numpy array) – The vertex list.
indgraf (Graph) – The induced subgraph.

induce_part(vnumnbr, vnumtab, partval, indgraf)¶: This routine computes the induced graph of the graph itself, with respect to the given vertex list and the given partition.

Parameters:

vnumnbr (Integer) – The number of vertices in the list.
vnumtab (Any kind of iterable or a numpy array) – The vertex list.
partval (Any kind of iterable or a numpy array) – The partition array.
indgraf (Graph) – The induced subgraph.

repart(partnbr, parotab, emraval, vmlotab, strat=Strat(init=True), parttab=None)¶: This routine computes an edge-separated repartition , into partnbr parts, of the graph itself, based on the old partition array parotab , with respect to the given strategy strat .

Parameters:

partnbr (Integer) – The number of parts.
parotab (Any kind of iterable or a numpy array) – The old partition array.
emraval (Floating-point number) – Individual migration cost.
vmlotab (Any kind of iterable or a numpy array) – Vertex migration cost array.
strat (Strat) – Strategy to be used for the partitioning.
parttab (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.

repart_fixed(partnbr, parotab, emraval, vmlotab, strat=Strat(init=True), parttab=None)¶: This routine computes an edge-separated repartition , into partnbr parts, of the graph itself, based on the old partition array parotab , with respect to the given strategy strat and the fixed vertices in maptab.

Parameters:

partnbr (Integer) – The number of parts.
parotab (Any kind of iterable or a numpy array) – The old partition array.
emraval (Floating-point number) – Individual migration cost.
vmlotab (Any kind of iterable or a numpy array) – Vertex migration cost array.
strat (Strat) – Strategy to be used for the partitioning.
parttab (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(arch, strat=Strat(init=True), parttab=None)¶: This routine computes a mapping of the given 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.
parttab (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_fixed(arch, strat=Strat(init=True), parttab=None)¶: This routine computes a mapping of the given graph itself onto the given target architecture arch , with respect to the given strategy strat and fixed vertices in maptab.

Parameters:

arch (Arch) – The target architecture.
strat (Strat) – Strategy to be used for the mapping.
parttab (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.

remap(arch, parotab, emraval, vmlotab, strat=Strat(init=True), parttab=None)¶: This routine computes a remapping of the graph itself onto the given target architecture arch , based on the old partition array parotab, with respect to the given strategy strat.

Parameters:

arch (Arch) – The target architecture.
parotab (Any kind of iterable or a numpy array) – The old mapping array.
emraval (Floating-point number) – Individual migration cost.
vmlotab (Any kind of iterable or a numpy array) – Vertex migration cost array.
strat (Strat) – Strategy to be used for the mapping.
parttab (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.

remap_fixed(arch, parotab, emraval, vmlotab, strat=Strat(init=True), parttab=None)¶: This routine computes a remapping of the graph itself onto the given target architecture arch , based on the old partition array parotab, with respect to the given strategy strat and the fixed vertices in maptab.

Parameters:

arch (Arch) – The target architecture.
parotab (Any kind of iterable or a numpy array) – The old mapping array.
emraval (Floating-point number) – Individual migration cost.
vmlotab (Any kind of iterable or a numpy array) – Vertex migration cost array.
strat (Strat) – Strategy to be used for the mapping.
parttab (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, parttab=None)¶: This routine initializes an API opaque mapping with respect to the graph itself and the locations of output parameters.

Parameters:

mapping (Mapping) – The mapping to be initialized.
arch (Arch) – The target architecture.
parttab (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_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_fixed_compute(mapping, strat)¶: This routine computes a mapping with fixed vertices of the API mapping structure with respect to the given strategy.

Parameters:

mapping (Mapping) – The mapping to be computed.
strat (Strat) – Strategy to be used for the mapping.

remap_compute(mapping, mapo, emraval, vmlotab, strat)¶: This routine computes a remapping of the API mapping structure mapping with respect to the given strategy strat.

Parameters:

mapping (Mapping) – The mapping to be computed.
mapo (Any kind of iterable or a numpy array) – The already computed mapping array used to account for migration costs.
emraval (Floating-point number) – Individual migration cost.
vmlotab (Any kind of iterable or a numpy array) – Vertex migration cost array.
strat (Strat) – Strategy to be used for the mapping.

remap_fixed_compute(mapping, mapo, emraval, vmlotab, strat)¶: This routine computes a remapping with fixed vertices of the API mapping structure mapping with respect to the given strategy strat.

Parameters:

mapping (Mapping) – The mapping to be computed.
mapo (Any kind of iterable or a numpy array) – The already computed mapping array used to account for migration costs.
emraval (Floating-point number) – Individual migration cost.
vmlotab (Any kind of iterable or a numpy array) – Vertex migration cost array.
strat (Strat) – Strategy to be used for the mapping.

map_load(mapping, stream)¶: This routine loads the contents of the given user mapping mapping from the given stream stream.

Parameters:

mapping (Mapping) – The mapping to be loaded.
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.

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

order(strat=Strat(init=True), permtab=None, peritab=None, cblknbr=None, rangtab=None, treetab=None)¶: This routine computes a block ordering of the unknowns of the symmetric sparse matrix the adjacency structure, which is represented by the graph itself.

Parameters:

strat (Strat) – Strategy to be used for the ordering.
permtab (Any kind of iterable or a numpy array) – Array holding the permutation of the reordered matrix. If given, the values of the returned array are copied in this one.
peritab (Any kind of iterable or a numpy array) – Inverse permutation of the reordered matrix. If given, the values of the returned array are copied in this one.
cblknbr (integer) – Number of column blocks in the block ordering. If given, the value is copied in this one.
rangtab (Any kind of iterable or a numpy array) – Array of ranges for the column blocks. If given, the values of the returned array are copied in this one.
treetab (Any kind of iterable or a numpy array) – Array of ascendants of permuted column blocks in the separators tree. If given, the values of the returned array are copied in this one.

order_init(ordering, permtab=None, peritab=None, cblknbr=None, rangtab=None, treetab=None)¶: This routine initializes an ordering structure with respect to the graph itself. If called using Ordering’s constructor however, nothing is returned.

Parameters:

ordering (Ordering) – Ordering to be initialized.
permtab (Any kind of iterable or a numpy array) – Array holding the permutation of the reordered matrix. If given, the values of the returned array are copied in this one.
peritab (Any kind of iterable or a numpy array) – Inverse permutation of the reordered matrix. If given, the values of the returned array are copied in this one.
cblknbr (Integer) – Number of column blocks in the block ordering. If given, the value is copied in this one.
rangtab (Any kind of iterable or a numpy array) – Array of ranges for the column blocks. If given, the values of the returned array are copied in this one.
treetab (Any kind of iterable or a numpy array) – Array of ascendants of permuted column blocks in the separators tree. If given, the values of the returned array are copied in this one.

order_exit(ordering)¶: This routine frees an ordering instance.

Parameters:: ordering (Ordering) – Ordering to be freed.

order_check(ordering)¶: This routine checks the consistency of the ordering instance.

Parameters:: ordering (Ordering) – Ordering to be checked.

order_compute(ordering, strat)¶: This routine computes a block ordering of the 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_compute_list(ordering, listtab, strat)¶: This routine computes a block ordering of the graph itself with respect to the given strategy strat. Stores the result in the given ordering instance ordering. The induced subgraph is described by means of a vertex list: listnbr holds the number of vertices to keep in the induced subgraph, the indices of which are given, in any order, in the listtab array.

Parameters:

ordering (Ordering) – Ordering to be computed.
listtab (Any kind of iterable or a numpy array) – The list of vertices to keep in the induced subgraph.
strat (Strat) – Strategy to be used for the ordering.

order_load(ordering, stream)¶: This routine loads the contents of the given ordering instance ordering from the given stream stream.

Parameters:

ordering (Ordering) – Ordering to be loaded.
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.

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

coarsen(coarvertnbr, coarrat, flagval, coargraf, coarmulttab=None)¶: This routine coarsens the graph itself with respect to the given parameters. The coarsened graph is created only if it comprises more than coarvertnbr 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:

coarvertnbr (Integer) – Number of vertices in the coarsened graph.
coarrat (Floating-point number) – Coarsening ratio.
flagval (Integer) – The flagval flag specifies the type of coarsening
coargraf (Graph) – Another Graph instance, which gets modified.
coarmulttab (Any kind of iterable or a numpy array) – The vertex-to-vertex multiplicity array. If given as a list or numpy array of integers, it is updated with the returned values.

coarsen_match(coarvertnbr, coarrat, flagval, finematetab=None)¶: The routine fills the finematetab array with a matching of the vertices of the graph itself. The matching is computed so as to minimize the sum of the weights of the matched edges. The matching is computed only if it comprises more than coarvertnbr 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:

coarvertnbr (Integer) – Number of vertices in the coarsened graph.
coarrat (Floating-point number) – Coarsening ratio.
flagval (Integer) – The flagval flag specifies the type of coarsening
finematetab (Any kind of iterable or a numpy array) – The matching array. If given as a list or numpy array of integers, it is updated with the returned values.

Returns:

The number of matched vertices.

Return type:

Integer

coarsen_build(coarvertnbr, finematetab, coargraf, coarmulttab=None)¶: This routine builds the coarsened graph itself with respect to the given parameters.

Parameters:

coarvertnbr (Integer) – Number of vertices in the coarsened graph.
finematetab (Any kind of iterable or a numpy array) – The matching array. If given as a list or numpy array of integers, it is updated with the returned values.
coargraf (Graph) – Another Graph instance, which gets modified.
coarmulttab (Any kind of iterable or a numpy array) – The vertex-to-vertex multiplicity array. If given as a list or numpy array of integers, it is updated with the returned values.

Various functions are defined as wrappers of Graph operations:

graph_alloc()¶: Recreates the graphAlloc function, returning a non-initialized Graph instance. It will need the init() method to be called before the instance be built or loaded upon.

build_graph(*args, **kwargs)¶: Returns a properly built graph instance. Positional and keyword arguments need to be given in the same fashion as Graph.build() takes them.

build_graph_from_csgraph(*args, **kwargs)¶: Returns a graph instance built from the given scipy.csgraph matrix. Positional and keyword arguments need to be given in the same fashion as Graph.build_from_csgraph() takes them.

load_graph(*args, **kwargs)¶: Returns a graph instance loaded from the given file or stream. Positional arguments need to be given in the same fashion as Graph.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 Graph constructor. They return unfinished and per se unusable objects, since they are included for compatibility with the C version of Scotch. The use of the build_graph(), build_graph_from_csgraph() or load_graph() functions is therefore advised.

Graphs in ScotchPy¶

The Graph class¶

Good practices¶

ScotchPy

Navigation

Related Topics