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