SHOGUN  3.2.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
DisjointSet.h
Go to the documentation of this file.
1 /*
2  * This program is free software; you can redistribute it and/or modify
3  * it under the terms of the GNU General Public License as published by
4  * the Free Software Foundation; either version 3 of the License, or
5  * (at your option) any later version.
6  *
7  * Written (W) 2013 Shell Hu
8  * Copyright (C) 2013 Shell Hu
9  */
10 
11 #ifndef __DISJOINTSET_H__
12 #define __DISJOINTSET_H__
13 
14 #include <shogun/lib/config.h>
15 
16 #include <shogun/base/SGObject.h>
17 #include <shogun/lib/SGVector.h>
18 
19 namespace shogun
20 {
21 
26 class CDisjointSet : public CSGObject
27 {
28 public:
30  CDisjointSet();
31 
36  CDisjointSet(int32_t num_elements);
37 
40 
42  virtual const char* get_name() const { return "DisjointSet"; }
43 
45  void make_sets();
46 
52  int32_t find_set(int32_t x);
53 
60  int32_t link_set(int32_t xroot, int32_t yroot);
61 
69  bool union_set(int32_t x, int32_t y);
70 
77  bool is_same_set(int32_t x, int32_t y);
78 
84  int32_t get_unique_labeling(SGVector<int32_t> out_labels);
85 
90  int32_t get_num_sets();
91 
96  bool get_connected();
97 
102  void set_connected(bool is_connected);
103 
104 private:
106  void init();
107 
108 private:
110  int32_t m_num_elements;
111 
113  SGVector<int32_t> m_parent;
114 
116  SGVector<int32_t> m_rank;
117 
119  bool m_is_connected;
120 };
121 
122 }
123 
124 #endif
125 

SHOGUN Machine Learning Toolbox - Documentation