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 Soumyajit De 00008 */ 00009 00010 #include <shogun/lib/common.h> 00011 00012 #ifdef HAVE_COLPACK 00013 #ifdef HAVE_EIGEN3 00014 00015 #include <vector> 00016 #include <string> 00017 #include <cstring> 00018 #include <shogun/lib/SGVector.h> 00019 #include <shogun/lib/SGString.h> 00020 #include <shogun/base/Parameter.h> 00021 #include <shogun/mathematics/eigen3.h> 00022 #include <shogun/mathematics/Random.h> 00023 #include <shogun/mathematics/linalg/linop/SparseMatrixOperator.h> 00024 #include <shogun/mathematics/linalg/ratapprox/tracesampler/ProbingSampler.h> 00025 #include <ColPack/ColPackHeaders.h> 00026 00027 using namespace Eigen; 00028 using namespace ColPack; 00029 00030 namespace shogun 00031 { 00032 00033 CProbingSampler::CProbingSampler() : CTraceSampler() 00034 { 00035 init(); 00036 } 00037 00038 CProbingSampler::CProbingSampler( 00039 CSparseMatrixOperator<float64_t>* matrix_operator, int64_t power, 00040 EOrderingVariant ordering, EColoringVariant coloring) 00041 : CTraceSampler(matrix_operator->get_dimension()) 00042 { 00043 init(); 00044 00045 m_power=power; 00046 m_matrix_operator=matrix_operator; 00047 m_ordering=ordering; 00048 m_coloring=coloring; 00049 00050 SG_REF(m_matrix_operator); 00051 } 00052 00053 void CProbingSampler::init() 00054 { 00055 m_matrix_operator=NULL; 00056 m_power=1; 00057 m_ordering=NATURAL; 00058 m_coloring=DISTANCE_TWO; 00059 m_is_precomputed=false; 00060 00061 SG_ADD(&m_coloring_vector, "coloring_vector", "the coloring vector generated" 00062 " from coloring", MS_NOT_AVAILABLE); 00063 00064 SG_ADD(&m_power, "matrix_power", "power of the sparse-matrix for coloring", 00065 MS_NOT_AVAILABLE); 00066 00067 SG_ADD(&m_is_precomputed, "is_precomputed", 00068 "flag that is true if already precomputed", MS_NOT_AVAILABLE); 00069 00070 SG_ADD((CSGObject**)&m_matrix_operator, "matrix_operator", 00071 "the sparse-matrix linear opeator for coloring", MS_NOT_AVAILABLE); 00072 } 00073 00074 CProbingSampler::~CProbingSampler() 00075 { 00076 SG_UNREF(m_matrix_operator); 00077 } 00078 00079 void CProbingSampler::set_coloring_vector(SGVector<int32_t> coloring_vector) 00080 { 00081 m_coloring_vector=coloring_vector; 00082 m_is_precomputed=true; 00083 } 00084 00085 SGVector<int32_t> CProbingSampler::get_coloring_vector() const 00086 { 00087 return m_coloring_vector; 00088 } 00089 00090 void CProbingSampler::precompute() 00091 { 00092 SG_DEBUG("Entering\n"); 00093 00094 // if already precomputed, nothing to do 00095 if (m_is_precomputed) 00096 { 00097 SG_DEBUG("Coloring vector already computed! Exiting!\n"); 00098 return; 00099 } 00100 00101 // do coloring things here and save the coloring vector 00102 SparsityStructure* sp_str=m_matrix_operator->get_sparsity_structure(m_power); 00103 00104 GraphColoringInterface* Color 00105 =new GraphColoringInterface(SRC_MEM_ADOLC, sp_str->m_ptr, sp_str->m_num_rows); 00106 00107 std::string str_ordering; 00108 switch(m_ordering) 00109 { 00110 case NATURAL: 00111 str_ordering="NATURAL"; 00112 break; 00113 case LARGEST_FIRST: 00114 str_ordering="LARGEST_FIRST"; 00115 break; 00116 case DYNAMIC_LARGEST_FIRST: 00117 str_ordering="DYNAMIC_LARGEST_FIRST"; 00118 break; 00119 case DISTANCE_TWO_LARGEST_FIRST: 00120 str_ordering="DISTANCE_TWO_LARGEST_FIRST"; 00121 break; 00122 case SMALLEST_LAST: 00123 str_ordering="SMALLEST_LAST"; 00124 break; 00125 case DISTANCE_TWO_SMALLEST_LAST: 00126 str_ordering="DISTANCE_TWO_SMALLEST_LAST"; 00127 break; 00128 case INCIDENCE_DEGREE: 00129 str_ordering="INCIDENCE_DEGREE"; 00130 break; 00131 case DISTANCE_TWO_INCIDENCE_DEGREE: 00132 str_ordering="DISTANCE_TWO_INCIDENCE_DEGREE"; 00133 break; 00134 case RANDOM: 00135 str_ordering="RANDOM"; 00136 break; 00137 } 00138 00139 std::string str_coloring; 00140 switch(m_coloring) 00141 { 00142 case DISTANCE_ONE: 00143 str_coloring="DISTANCE_ONE"; 00144 break; 00145 case ACYCLIC: 00146 str_coloring="ACYCLIC"; 00147 break; 00148 case ACYCLIC_FOR_INDIRECT_RECOVERY: 00149 str_coloring="ACYCLIC_FOR_INDIRECT_RECOVERY"; 00150 break; 00151 case STAR: 00152 str_coloring="STAR"; 00153 break; 00154 case RESTRICTED_STAR: 00155 str_coloring="RESTRICTED_STAR"; 00156 break; 00157 case DISTANCE_TWO: 00158 str_coloring="DISTANCE_TWO"; 00159 break; 00160 } 00161 00162 Color->Coloring(str_ordering, str_coloring); 00163 00164 std::vector<int32_t> vi_VertexColors; 00165 Color->GetVertexColors(vi_VertexColors); 00166 00167 REQUIRE(vi_VertexColors.size()==static_cast<uint32_t>(m_dimension), 00168 "dimension mismatch, %d vs %d!\n", vi_VertexColors.size(), m_dimension); 00169 00170 m_coloring_vector=SGVector<int32_t>(vi_VertexColors.size()); 00171 00172 for (std::vector<int32_t>::iterator it=vi_VertexColors.begin(); 00173 it!=vi_VertexColors.end(); it++) 00174 { 00175 index_t i=static_cast<index_t>(std::distance(vi_VertexColors.begin(), it)); 00176 m_coloring_vector[i]=*it; 00177 } 00178 00179 Map<VectorXi> colors(m_coloring_vector.vector, m_coloring_vector.vlen); 00180 m_num_samples=colors.maxCoeff()+1; 00181 SG_DEBUG("Using %d samples (aka colours) for probing trace sampler\n", 00182 m_num_samples); 00183 00184 delete sp_str; 00185 delete Color; 00186 00187 // set the precomputed flag true 00188 m_is_precomputed=true; 00189 00190 SG_DEBUG("Leaving\n"); 00191 } 00192 00193 SGVector<float64_t> CProbingSampler::sample(index_t idx) const 00194 { 00195 REQUIRE(idx<m_num_samples, "Given index (%d) must be smaller than " 00196 "number of samples to draw (%d)\n", idx, m_num_samples); 00197 00198 SGVector<float64_t> s(m_dimension); 00199 s.set_const(0.0); 00200 00201 for (index_t i=0; i<m_dimension; ++i) 00202 { 00203 if (m_coloring_vector[i]==idx) 00204 { 00205 float64_t x=sg_rand->std_normal_distrib(); 00206 s[i]=(x>0)-(x<0); 00207 } 00208 } 00209 00210 return s; 00211 } 00212 00213 } 00214 00215 #endif // HAVE_EIGEN3 00216 #endif // HAVE_COLPACK