MeshKit
1.0
|
00001 00002 #include "meshkit/MKCore.hpp" 00003 #include "Dijkstra.hpp" 00004 #include <iostream> 00005 #include <algorithm> 00006 #include <math.h> 00007 #include <map> 00008 00009 00010 00011 00012 00013 00014 namespace MeshKit 00015 { 00016 00017 00018 //---------------------------------------------------------------------------// 00019 // construction function for Dijkstra class 00020 Dijkstra::Dijkstra(vector<vector<double> > t) 00021 { 00022 dist.insert(dist.begin(), t.begin(), t.end()); 00023 } 00024 00025 void Dijkstra::getResults(vector<vector<double> > &d) 00026 { 00027 d.resize(dist.size()); 00028 order_dist.resize(dist.size()); 00029 for (unsigned int i = 0; i < dist.size(); i++){ 00030 algs(i, d[i]); 00031 order_dist[i].insert(order_dist[i].begin(), d[i].begin(), d[i].end()); 00032 } 00033 } 00034 00035 void Dijkstra::getTopMostSurf() 00036 { 00037 00038 for (unsigned int i = 0; i < order_dist.size(); i++){ 00039 bool is_negative = true; 00040 for (unsigned int j = 0; j < order_dist[i].size(); j++) 00041 is_negative = is_negative && (order_dist[i][j] <= 0); 00042 if (is_negative) 00043 topmost_target_surf = i; 00044 } 00045 00046 std::cout << "topmost target surf index = " << topmost_target_surf << std::endl; 00047 } 00048 00049 void Dijkstra::getSurfList(vector<vector<vector<int> > > &l, int src_size, int tgt_size) 00050 { 00051 std::cout << "====================\n"; 00052 for (unsigned int i = 0; i < order_dist.size(); i++){ 00053 00054 for (unsigned int j = 0; j < order_dist[i].size(); j++) 00055 std::cout << order_dist[i][j] << "\t"; 00056 std::cout << std::endl; 00057 } 00058 00059 std::cout << "====================\n"; 00060 00061 std::vector<double> dist_array; 00062 getTopMostSurf(); 00063 00064 for (unsigned int i = 0; i < order_dist[topmost_target_surf].size(); i++) 00065 std::cout << order_dist[topmost_target_surf][i] << "\t"; 00066 std::cout << std::endl; 00067 00068 dist_array.insert(dist_array.begin(), order_dist[topmost_target_surf].begin(), order_dist[topmost_target_surf].end()); 00069 std::vector<double> bak_dist_array; 00070 bak_dist_array.insert(bak_dist_array.begin(), dist_array.begin(), dist_array.end()); 00071 //sort the distances 00072 std::sort(dist_array.begin(), dist_array.end()); 00073 //get the index 00074 int layer_index = -1; 00075 double previous_dist = 1.0e10; 00076 00077 std::cout << "sorted array\n"; 00078 for (unsigned int i = 0; i < dist_array.size(); i++) 00079 std::cout << dist_array[i] << "\t"; 00080 std::cout << std::endl; 00081 00082 00083 for (int i = dist_array.size() - 1; i >= 0; i--){ 00084 std::vector<double>::iterator it; 00085 it = std::find(bak_dist_array.begin(), bak_dist_array.end(), dist_array[i]); 00086 int index = std::distance(bak_dist_array.begin(), it); 00087 surf_list.push_back(index); 00088 //l.push_back(index); 00089 if (i==(dist_array.size()-1)){ 00090 layer_index++; 00091 l.resize(layer_index+1); 00092 addSurfToList(layer_index, index, src_size, l[layer_index]); 00093 } 00094 else{ 00095 if (fabs(dist_array[i]-previous_dist) < 1.0e-5){//on the same layer 00096 addSurfToList(layer_index, index, src_size, l[layer_index]); 00097 } 00098 else{ 00099 layer_index++; 00100 l.resize(layer_index+1); 00101 addSurfToList(layer_index, index, src_size, l[layer_index]); 00102 } 00103 00104 } 00105 previous_dist = dist_array[i]; 00106 bak_dist_array[index] = 1.0e10; 00107 } 00108 00109 // 00110 for (unsigned int i = 0; i < l.size(); i++){ 00111 for (unsigned int j = 0; j < l[i].size(); j++){ 00112 std::cout << "layer = " << i << "\tsurf index = " << j << "\tsurf_id = " << l[i][j][0] << std::endl; 00113 } 00114 } 00115 } 00116 00117 void Dijkstra::addSurfToList(int layer_index, int value, int src_size, vector<vector<int> > &datalist){ 00118 int surf_index = datalist.size(); 00119 datalist.resize(surf_index+1); 00120 if (value < src_size){ 00121 datalist[surf_index].push_back(value); 00122 datalist[surf_index].push_back(0); 00123 } 00124 else{ 00125 datalist[surf_index].push_back(value-src_size); 00126 datalist[surf_index].push_back(1); 00127 } 00128 } 00129 00130 void Dijkstra::algs(int s, vector<double> &f_list) 00131 { 00132 //Initializaton: set every distance to INFINITY until we discover a path 00133 vector<double> d(dist.size(), 1.0e10); 00134 //sptSet[i] will true if vertex i is included in the shortest path tree or 00135 //shortest distance from s to i is finalized. 00136 vector<bool> sptSet(dist.size(), false); 00137 //the distance from the source to the source is defined to be zero. 00138 d[s] = 0.0; 00139 /* 00140 This loop corresponds to sending out the explorers walking the paths, 00141 where the step of picking "the vertex, v, with the shortest path to s" 00142 corresponds to an explorer arriving at an unexplored vertex. 00143 */ 00144 int V = (int)dist.size(); 00145 // Find shortest path for all vertices 00146 for (int count = 0; count < V-1; count++){ 00147 //pick the minimum distance vertex from the set of vertices not yet 00148 //processed. u is always equal to s in the first iteration 00149 int u = minDistance(d, sptSet); 00150 //Mark the picked vertex as processed. 00151 sptSet[u] = true; 00152 //Update d value of the adjacent vertices of the picked vertex 00153 for (int v = 0; v < V; v++){ 00154 //update d[v] only if is not in sptSet, there is an edge from u to 00155 //v, and total weight of apth from s to v through u is smaller than 00156 //current value of d[v] 00157 if (!sptSet[v] && dist[u][v] && d[u] != 1.0e10 && d[u]+dist[u][v]<d[v]) 00158 d[v] = d[u]+dist[u][v]; 00159 } 00160 } 00161 00162 //pass results to the list 00163 for (unsigned int i = 0; i < d.size(); i++) 00164 f_list.push_back(d[i]); 00165 00166 } 00167 //A utility function to find the vertex with minimum distance value, from the 00168 //set of vertices not yet included in shortest path tree 00169 int Dijkstra::minDistance(vector<double> d, vector<bool> sptSet) 00170 { 00171 //Initialize min value 00172 double minvalue = 1.0e10; 00173 int min_index; 00174 for (int v = 0; v < dist.size(); v++){ 00175 if (sptSet[v] == false && d[v] <= minvalue){ 00176 minvalue = d[v]; 00177 min_index = v; 00178 } 00179 } 00180 return min_index; 00181 } 00182 00183 //---------------------------------------------------------------------------// 00184 // deconstruction function for Dijkstra class 00185 Dijkstra::~Dijkstra() 00186 { 00187 std::cout << "Dijkstra algorithm is over\n"; 00188 } 00189 00190 00191 00192 00193 } 00194