Tulip  5.3.0
Large graphs analysis and drawing
tuliphash.h
1 /*
2  *
3  * This file is part of Tulip (http://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef TLP_HASH_H
22 #define TLP_HASH_H
23 
24 /**
25  * @brief This file defines what class is used to provide a hashmap.
26  * The TLP_HASH_MAP macro defines which implementation is used for hash maps.
27  * The TLP_HASH_SET macro defines which implementation is used for hash sets.
28  *
29  * TLP_BEGIN_HASH_NAMESPACE is defined to open the namespace in which the hash classes are defined,
30  * to define new hashes (e.g. for Edge).
31  * TLP_END_HASH_NAMESPACE is defined to close the namespace
32  * TLP_HASH_NAMESPACE allows to use a specific hasher class when declaring a hash set or a hash map.
33  */
34 
35 #include <unordered_map>
36 #include <unordered_set>
37 #define TLP_HASH_MAP std::unordered_map
38 #define TLP_HASH_SET std::unordered_set
39 #define TLP_HASH_NAMESPACE std
40 #define TLP_BEGIN_HASH_NAMESPACE namespace std
41 #define TLP_END_HASH_NAMESPACE
42 
43 // The hash_combine function from the boost library
44 // Call it repeatedly to incrementally create a hash value from several variables.
45 
46 // Explanation of the formula from StackOverflow
47 // (http://stackoverflow.com/questions/4948780/magic-numbers-in-boosthash-combine) :
48 // The magic number 0x9e3779b9 = 2^32 / ((1 + sqrt(5)) / 2) is the reciprocal of the golden ratio.
49 // It is supposed to be 32 random bits, where each is equally likely to be 0 or 1, and with no
50 // simple correlation between the bits.
51 // So including this number "randomly" changes each bit of the seed; as you say, this means that
52 // consecutive values will be far apart.
53 // Including the shifted versions of the old seed makes sure that, even if hash_value() has a fairly
54 // small range of values,
55 // differences will soon be spread across all the bits.
56 TLP_BEGIN_HASH_NAMESPACE {
57  template <class T>
58  inline void tlp_hash_combine(std::size_t & seed, const T &v) {
59  hash<T> hasher;
60  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
61  }
62 }
63 TLP_END_HASH_NAMESPACE
64 
65 #endif
66 ///@endcond