Scotch Brand 5.1.10 - Manual (Page 130)

simple mesh, in the form of a bipartite graph, the definition of which is given in
file mesh.h, respectively. From this structure are derived enriched graph and mesh
structures:
• Bgraph, in file bgraph.h: graph with bipartition, that is, edge separation,
information attached to it;
• Kgraph, in file kgraph.h: graph with mapping information attached to it;
• Hgraph, in file hgraph.h: graph with halo information attached to it, for
computing graph orderings;
• Vgraph, in file vgraph.h: graph with vertex bipartition information attached
to it;
• Hmesh, in file hmesh.h: mesh with halo information attached to it, for com-
puting mesh orderings;
• Vmesh, in file vmesh.h: graph with vertex bipartition information attached to
it.
As version 5.1 of the libScotch does not provide mesh mapping capabilities, nei-
ther Bmesh nor Kmesh structures have been defined to date, but this work is in
progress, and these features should be available in the upcoming releases.
All of the structures are in fact defined as typedefed types.
10.2 Methods and partition data
Methods are routines which take one of the above structures as input, and update
the fields of the given structure according to the implemented algorithm. Initial
methods will behave irrespective of the former values of the structure (like graph
growing methods, which compute partitions from scratch), while refinement meth-
ods must be provided an existing partition to improve.
In addition to the topological description of the underlying graph, the working
graph and mesh structures comprise variables describing the current state of the
vertex or edge partition. In all cases is provided a partition array called parttax,
of size equal to the number of graph vertices, which tells which part every vertex
is assigned to. Other variables comprise the communication load and the load
imbalance of the current cut, that is, all of the data necessary to measure the
quality of a partition. Some other data are also often provided, such as the number
of vertices in each part and the list of frontier vertices. They are not relevant to
measure the quality of the partition, but to improve the speed of computations.
They are used for instance in the multi-level algorithms to compute incremental
updates of the current partition state, without having to recompute these values
from scratch by considering all of the graph vertices. Implementers of new methods
are highly encouraged to use these variables to speed-up their computations, taking
examples on typical algorithms such as the multi-level or Fiduccia-Mattheyses ones.
10.3 Adding a new method to Scotch
We will assume in this section that the new method to add is a graph separation
method. The procedure explained below is exactly the same for graph bipartition-
ing, graph mapping, graph ordering, mesh separation, or mesh ordering methods.
Please proceed as explained below.
130