SHOGUN
v3.2.0
|
00001 /* 00002 * This program is free software; you can redistribute it and/or modify 00003 * it under the terms of the GNU General Public License as published by 00004 * the Free Software Foundation; either version 3 of the License, or 00005 * (at your option) any later version. 00006 * 00007 * Written (W) 2013 Shell Hu 00008 * Copyright (C) 2013 Shell Hu 00009 */ 00010 00011 #ifndef __DISJOINTSET_H__ 00012 #define __DISJOINTSET_H__ 00013 00014 #include <shogun/base/SGObject.h> 00015 #include <shogun/lib/SGVector.h> 00016 00017 namespace shogun 00018 { 00019 00024 class CDisjointSet : public CSGObject 00025 { 00026 public: 00028 CDisjointSet(); 00029 00034 CDisjointSet(int32_t num_elements); 00035 00037 ~CDisjointSet() { } 00038 00040 virtual const char* get_name() const { return "DisjointSet"; } 00041 00043 void make_sets(); 00044 00050 int32_t find_set(int32_t x); 00051 00058 int32_t link_set(int32_t xroot, int32_t yroot); 00059 00067 bool union_set(int32_t x, int32_t y); 00068 00075 bool is_same_set(int32_t x, int32_t y); 00076 00082 int32_t get_unique_labeling(SGVector<int32_t> out_labels); 00083 00088 int32_t get_num_sets(); 00089 00094 bool get_connected(); 00095 00100 void set_connected(bool is_connected); 00101 00102 private: 00104 void init(); 00105 00106 private: 00108 int32_t m_num_elements; 00109 00111 SGVector<int32_t> m_parent; 00112 00114 SGVector<int32_t> m_rank; 00115 00117 bool m_is_connected; 00118 }; 00119 00120 } 00121 00122 #endif 00123