Scotch Brand 5.1.10 - Manual (Page 52)

Dynamic graphs can be handled elegantly by using the vendtab array. In order
to dynamically manage graphs, one just has to allocate verttab, vendtab and
edgetab
arrays that are large enough to contain all of the expected new vertex and
edge data. Original vertices are labeled starting from baseval, leaving free space at
the end of the arrays. To remove some vertex i, one just has to replace verttab[i]
and vendtab[i] with the values of verttab[vertnbr-1] and vendtab[vertnbr-1],
respectively, and browse the adjacencies of all neighbors of former vertex vertnbr-1
such that all (vertnbr-1) indices are turned into is. Then, vertnbr must be
decremented, and SCOTCH graphBuild() must be called to account for the change
of topology. If a graph building routine such as SCOTCH graphLoad() or SCOTCH
graphBuild()
had already been called on the SCOTCH Graph structure, SCOTCH
graphFree() has to be called first in order to free the internal structures associated
with the older version of the graph, else these data would be lost, which would
result in memory leakage.
To add a new vertex, one has to fill verttab[vertnbr-1] and vendtab[vertnbr
-1] with the starting and end indices of the adjacency sub-array of the new vertex.
Then, the adjacencies of its neighbor vertices must also be updated to account for it.
If free space had been reserved at the end of each of the neighbors, one just has to
increment the vendtab[i] values of every neighbor i, and add the index of the new
vertex at the end of the adjacency sub-array. If the sub-array cannot be extended,
then it has to be copied elsewhere in the edge array, and both verttab[i] and
vendtab[i]
must be updated accordingly. With simple housekeeping of free areas
of the edge array, dynamic arrays can be updated with as little data movement as
possible.
7.2.3 Mesh format
Since meshes are basically bipartite graphs, source meshes are also described by
means of adjacency lists. The description of a mesh requires several SCOTCH Num
scalars and arrays, as shown in Figure 18. They have the following meaning:
velmbas
Base value for element indexings.
vnodbas
Base value for node indexings. The base value of the underlying graph,
baseval
, is set as min(velmbas, vnodbas).
velmnbr
Number of element vertices in mesh.
vnodnbr
Number of node vertices in mesh. The overall number of vertices in the
underlying graph, vertnbr, is set as velmnbr + vnodnbr.
edgenbr
Number of arcs in mesh. Since edges are represented by both of their ends,
the number of edge data in the mesh is twice the number of edges.
verttab
Array of start indices in edgetab of vertex (that is, both elements and nodes)
adjacency sub-arrays.
52