levl
The level of the subgraph in the separators tree, starting from zero
at the root of the tree. Integer.
proc
The number of processors on which the current subgraph is dis-
tributed at this level of the separators tree. This variable is available
only when calling from routines of the
PT-Scotch
parallel library.
Integer.
rank
The rank of the current processor among the group of processors
on which the current subgraph is distributed at this level of the
separators tree. This variable is available only when calling from
routines of the
PT-Scotch
parallel library, for instance to decide
which node separation strategy should be used on which processor
in a multi-sequential approach. Integer.
vert
The number of vertices of the current subgraph. Integer.
The currently available vertex separation methods are the following.
b
Band method. Available only for graph separation strategies. This method
builds a band graph of given width around the current separator of the graph
to which it is applied, and calls a graph separation strategy to refine the
equivalent separator of the band graph. Then, the refined separator of the
band graph is projected back to the current graph. This method, presented
in [8], was created to reduce the cost of separator refinement algorithms in a
multi-level context, but it improves partition quality too. The parameters of
the band separation method are listed below.
bnd=
strat
Set the vertex separation strategy to be used on the band graph.
org=
strat
Set the fallback vertex separation strategy to be used on the original
graph if the band graph strategy could not be used. The three cases
which require the use of this fallback strategy are the following. First, if
the separator of the original graph is empty, which makes it impossible
to compute a band graph. Second, if any part of the band graph to be
built is of the same size as the one of the original graph. Third, if the
application of the
bnd
vertex separation method to the band graph leads
to a situation where both anchor vertices are placed in the same part.
width=
val
Set the width of the band graph. All graph vertices that are at a distance
less than or equal to
val
from any separator vertex are kept in the band
graph.
e
Edge-separation method. Available only for graph separation strategies. This
method builds vertex separators from edge separators, by the method pro-
posed by Pothen and Fang [48], which uses a variant of the Hopcroft and
Karp algorithm due to Duff [9]. This method is expensive and most often
yields poorer results than direct vertex-oriented methods such as the vertex
vertex Greedy-graph-growing and the vertex Fiduccia-Mattheyses algorithms.
The parameters of the edge-separation method are listed below.
67
