Skip to content

Draft: New renumbering based on Hamiltonian path

Alon Zameret requested to merge hpathRenumbering into develop


Included a new renumbering method called 'hpathRenumber' which reorder the mesh cells using an Hamiltonian path approach.

Details of new models

Hamiltonian path is a path that traverses through the mesh faces and visits each cell exactly once. The Hamiltonian path approach tries to find such a path and renumber the mesh accordingly. This method ensures that after the mesh renumbering, consecutive cells in memory will likely share a common geometrical face. This in turn may allow for more efficient memory access and better vectorization performances when traversing the mesh.



Described below is the renumberMethodDict example used to apply Hamiltonian path renumbering:

method hpath;
    layered true;

The 'layered' argument (default true) controls whether the algorithm will separate the mesh cells into different 'layers' (otherwise, all cells are considered to be within the same layer). The layer separation approach is known to obtain better results and improved run-time for 3D cases, while 2D cases where a simpler Hamiltonian path may exist will benefit from avoiding the layer separation.

The algorithm will than try to find an Hamiltonian path traversing through all the cells sharing the same layer, and report the Hamiltonian path accuracy obtained. The path accuracy is defined as the percentage of consecutive cells in the renumbered order that share a common face.

Merge request reports