1 // This file is part of OpenMVG, an Open Multiple View Geometry C++ library. 2 3 // Copyright (c) 2016 Pierre MOULON. 4 5 // This Source Code Form is subject to the terms of the Mozilla Public 6 // License, v. 2.0. If a copy of the MPL was not distributed with this 7 // file, You can obtain one at http://mozilla.org/MPL/2.0/. 8 9 #ifndef OPENMVG_TRACKS_UNION_FIND_DISJOINT_SET_HPP 10 #define OPENMVG_TRACKS_UNION_FIND_DISJOINT_SET_HPP 11 12 #include <numeric> 13 #include <vector> 14 15 namespace openMVG { 16 17 // Union-Find/Disjoint-Set data structure 18 //-- 19 // A disjoint-set data structure also called a union–find data structure 20 // or merge–find set, is a data structure that keeps track of a set of elements 21 // partitioned into a number of disjoint (non-overlapping) subsets. 22 // It supports two operations: 23 // - Find: Determine which subset a particular element is in. 24 // - It returns an item from this set that serves as its "representative"; 25 // - Union: Join two subsets into a single subset. 26 // Sometime a Connected method is implemented: 27 // - Connected: 28 // - By comparing the result of two Find operations, one can determine whether 29 // two elements are in the same subset. 30 //-- 31 struct UnionFind 32 { 33 // Represent the DS/UF forest thanks to two array: 34 // A parent 'pointer tree' where each node holds a reference to its parent node 35 std::vector<unsigned int> m_cc_parent; 36 // A rank array used for union by rank 37 std::vector<unsigned int> m_cc_rank; 38 // A 'size array' to know the size of each connected component 39 std::vector<unsigned int> m_cc_size; 40 41 // Init the UF structure with num_cc nodes InitSetsopenMVG::UnionFind42 void InitSets 43 ( 44 const unsigned int num_cc 45 ) 46 { 47 // all set size are 1 (independent nodes) 48 m_cc_size.resize(num_cc, 1); 49 // Parents id have their own CC id {0,n} 50 m_cc_parent.resize(num_cc); 51 std::iota(m_cc_parent.begin(), m_cc_parent.end(), 0); 52 // Rank array (0) 53 m_cc_rank.resize(num_cc, 0); 54 } 55 56 // Return the number of nodes that have been initialized in the UF tree GetNumNodesopenMVG::UnionFind57 unsigned int GetNumNodes() const 58 { 59 return static_cast<unsigned int>(m_cc_size.size()); 60 } 61 62 // Return the representative set id of I nth component FindopenMVG::UnionFind63 unsigned int Find 64 ( 65 unsigned int i 66 ) 67 { 68 // Recursively set all branch as children of root (Path compression) 69 if (m_cc_parent[i] != i) 70 m_cc_parent[i] = Find(m_cc_parent[i]); 71 return m_cc_parent[i]; 72 } 73 74 // Replace sets containing I and J with their union UnionopenMVG::UnionFind75 void Union 76 ( 77 unsigned int i, 78 unsigned int j 79 ) 80 { 81 i = Find(i); 82 j = Find(j); 83 if (i == j) 84 { // Already in the same set. Nothing to do 85 return; 86 } 87 88 // x and y are not already in same set. Merge them. 89 // Perform an union by rank: 90 // - always attach the smaller tree to the root of the larger tree 91 if (m_cc_rank[i] < m_cc_rank[j]) 92 { 93 m_cc_parent[i] = j; 94 m_cc_size[j] += m_cc_size[i]; 95 } 96 else 97 { 98 m_cc_parent[j] = i; 99 m_cc_size[i] += m_cc_size[j]; 100 if (m_cc_rank[i] == m_cc_rank[j]) 101 ++m_cc_rank[i]; 102 } 103 } 104 }; 105 106 } // namespace openMVG 107 108 #endif // OPENMVG_TRACKS_UNION_FIND_DISJOINT_SET_HPP 109