Scotch Brand 5.1.10 - Manual (Page 26)

of the target graph vertex onto which it is mapped. Mapping pairs can be stored
in any order in the file; however, labels of source graph vertices must be all dif-
ferent. For example, Figure 9 shows the result obtained when mapping the source
graph of Figure 4 onto the target architecture of Figure 7. This one-to-one embed-
ding of H(3) into UB(2, 3) has dilation 1, except for one hypercube edge which has
dilation 3.
8
0
1
1 3
2 2
3 5
4 0
5 7
6 4
7 6
Figure 9: Mapping file obtained when mapping the hypercube source graph of
Figure 4 onto the binary de Bruijn architecture of Figure 7.
Mapping files are also used on output of the block orderer to represent the
allocation of the vertices of the original graph to the column blocks associated with
the ordering. In this case, column blocks are labeled in ascending order, such that
the number of a block is always greater than the ones of its predecessors in the
elimination process, that is, its leaves in the elimination tree.
5.6 Ordering files
Ordering files, which usually end in “.ord”, contain the result of the ordering of
source graphs or meshes that represent sparse matrices. They associate a number
with every vertex of the source graph or mesh.
The structure of ordering files is analogous to the one of mapping files; they
differ only by the meaning of their data.
Ordering files begin with the number of ordering lines which they contain, that
is the number of vertices in the source graph or the number of nodes in the source
mesh, followed by that many ordering lines. Each ordering line holds an ordering
pair, made of two integer numbers which are the label of a source graph or mesh
vertex and its rank in the ordering. Ranks range from the base value of the graph or
mesh (baseval) to the base value plus the number of vertices (resp. nodes), minus
one (baseval + vertnbr − 1 for graphs, and baseval + vnodnbr − 1 for meshes).
Ordering pairs can be stored in any order in the file; however, indices of source
vertices must be all different.
For example, Figure 10 shows the result obtained when reordering the source
graph of Figure 4.
The advantage of having both graph and mesh orderings start from baseval
(and not vnodbas in the case of meshes) is that an ordering computed on the nodal
graph of some mesh has the same structure as an ordering computed from the native
mesh structure, allowing for greater modularity. However, in memory, permutation
indices for meshes are numbered from vnodbas to vnodbas + vnodnbr − 1.
5.7 Vertex list files
Vertex lists are used by programs that select vertices from graphs.
26