(3M) Calculator User Manual

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, Fig ure 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 sour c e gra ph of
Figure 4 onto the binary de Bruijn architecture of Figure 7.
Mapping files are also us e d 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 e liminatio n 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 matr ice s. They associate a number
with every vertex o f the source graph or mesh.
The structure of order ing files is analogous to the o ne of mapping files; they
differ only by the meaning of their data.
Ordering files begin with the number of order ing lines which they contain, that
is the number of vertices in the source gra ph or the number of nodes in the source
mesh, followed by that many or dering 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 bas e 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 sto red in any o rder in the file; however, indices of source
vertices must be all different.
For example, Figure 10 shows the result obtained when reordering the sourc e
graph of Figure 4 .
The advantage of having both gr aph 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 str uctur e , allowing for greater modularity. However, in memory, permutation
indices for meshes a re numbered from vnodbas to vnodbas + vnodnbr − 1.
5.7 Vertex list files
Vertex lists are used by programs that select vertices from graphs.
26