Small pieces of code

(That may be of use to somebody else)


Fibonacci heap (or Fibonacci trees)

In the course of the development of my main research project, Scotch, I needed to sort elements according to several criteria, which might not always be single integer values. Consequently, the bucket sorting algorithms that I used before were not adequate. After looking at the Red-Black tree data structure (a thoughtful description and implementation of which can be found here), I turned to the Fibonacci heap (also called «Fibonacci trees», since it is technically a forest of trees with given degree properties), which better fitted my needs. Indeed, in the context of graph partitioning, I planned to use this data structure to select the best vertex to move from one part to another, depending on the improvement such a move may bring to the current partition. Such local optimisation algorithms are classically referred to as «Fiduccia-Mattheyses» or «Kernighan-Lin», depending on the way vertices are moved or swapped between parts. In such algorithms, once a vertex of best gain value has been selected for moving, the gains of all its neighbors have to be recomputed. Consequently, the data structure will be subject to much more deletion and insertion operations of «unsorted» arbitrary elements than to searches for, and deletions of, elements of best gain value. By adding and removing arbitrary vertices quickly (in constant time for addition), and by postponing the expensive sorting operations up to the moment when searching for the element of extremal value, Fibonacci trees are just what I needed when list buckets cannot be used.

However, all of the existing free/libre implementations that I could find on the Internet had two drawbacks. First, all of them were recursive, incurring a heavy recursion cost for a few useful instructions per function call. Second, all of them treated elements as independent data structures, which were internally allocated and freed at insertion and deletion time. Both of these features made them completely inappropriate for the kind of heavy use that I had in mind, for which such routines have to be called millions of times, and vertex elements are already embodied within data structures such as hash table arrays (yes, high performance computing can be real fun in terms of data structures!).

Consequently, I wrote my own, de-recursived, implementation of the Fibonacci trees data structure. The code is small, as this is really a very elegant data structure. Save for the pointer array internally used by the consolidation routine, no memory allocation is performed by this module. The allocation and freeing of the individual elements is left to the users of the module, who can opt for the kind of memory handling that they want. Unlike most implementations, the element of minimum value is not internally recorded, as I had no need to preserve it; however, module users can easily implement this feature on top of the existing routines. All module routines, except the consolidation routine which computes the current extremal value, are written as macros, which can be used as is or embodied within regular functions, depending on the pre-definition of symbolic constants.

Fibonacci trees are handled by means of a FiboTree data structure. Elements to be inserted and searched for must comprise a FiboNode substructure. Elements can belong to several tree structures, provided they possess as many FiboNode substructures as needed, and provided that users have a means for determining the offset of the element structure from the pointer to the FiboNode which is returned by the module routines. The module routines are the following:

fiboTreeInit
Initializes a FiboTree data structure, by allocating the internal consolidation array.
fiboTreeExit
Destroys a FiboTree data structure, by freeing the internal consolidation array. Tree elements are not modified in any way. If elements have to be individually processed at freeing time, for instance to be freed themselves, then they have to be removed one by one from the tree before fiboTreeExit is called, or be handled by means of external iterators (for instance by traversing their support array if they were all allocated together).
fiboTreeFree
Makes the FiboTree data structure become free, by removing all of its elements. Like for fiboTreeExit, tree elements are not themselves considered nor modified in any way. Their chaining pointers just become meaningless, so that removing any previously inserted FiboNode element from a freed tree may lead to segmentation violation errors.
fiboTreeAdd
Adds a FiboNode to a FiboTree.
fiboTreeDel
Removes the given FiboNode from its FiboTree.
fiboTreeConsolidate
Consolidates the current tree and returns a pointer to its extremal element. This element itself is not modified, and still belongs to the FiboTree.
fiboTreeMin
Returns the tree element of extremal value (assumed to be «minimal» in my original context), without removing it from the FiboTree. At the time being, this routine just calls fiboTreeConsolidate. Module users willing to keep track of the element of extremal gain can redefine this routine, as well as the fiboTreeAdd and fiboTreeDel routines, such that a pointer to the element of extremal gain is preserved in the FiboTree data structure. The recorded element must be compared against elements which are removed and deleted, and updated whenever necessary (which may require a call to fiboTreeConsolidate if the extremal element is the one which is being removed from the FiboTree).
fiboTreeCheck
When the FIBO_DEBUG debugging flag has been set at compile time, this routine checks the consistency of the given FiboTree structure.

The tarball of my implementation of the Fibonacci tree module can be obtained here. It contains files fibo.c, fibo.h, and test_fibo.c, as a sample use. I have placed this version of my module under a CeCILL-B license (equivalent in its principle to a «BSD» license), for maximal re-use.


François Pellegrini