ksp.zip_K._KSP

#include "Graph.h" using namespace Mido::Utility; #define INFINITY 0xFFFFFFFF Graph::Graph() : _N(0), _size(0) { } Graph::Graph(const dag_t& array) { _N = _size = array.size(); _array.resize(_size); for(int i=0;i<_size;i++) { _array[i].resize(_size); for(int j=0;j<_size;j++) _array[i][j] = array[i][j]; } } Graph::Graph(const double **array, unsigned N) : _N(N), _size(N) { _array.resize(_size); for(int i=0;i<_size;i++) { _array[i].resize(_size); for(int j=0;j<_size;j++) _array[i][j] = array[i][j]; } //this->Output(); // for debug } Graph::~Graph() { } void Graph::Restart(const dag_t& array) { _array.clear(); _N = _size = array.size(); _array.resize(_size); for(int i=0;i<_size;i++) { _array[i].resize(_size); for(int j=0;j<_size;j++) _array[i][j] = array[i][j]; } //this->Output(); // for debug } void Graph::Restart(const double** array,unsigned N) { _array.clear(); _N = _size = N; _array.resize(_size); for(int i=0;i<_size;i++) { _array[i].resize(_size); for(int j=0;j<_size;j++) _array[i][j] = array[i][j]; } } double Graph::Dijkstra( path_t& path ) { int* paths = new int[_size]; double min = dijkstra(paths); if(min < 0) { delete[] paths; return -1;} // parse the shortest path int i = _size - 1; while(i>=0) { path.push(i); i=paths[i]; } // push the start node path.push(0); delete[] paths; return min; } double Graph::Dijkstra( unsigned start , unsigned end , path_t& path ) { if(end == start || start >= _size) return -1; int* paths = new int[_size]; double min = dijkstra(paths,start,end); if(min < 0) { delete[] paths; return -1;} // parse the shortest path if(end > _size-1) end = _size - 1; int i = end; while(i>=0) { path.push(i); i=paths[i]; } // push the start node if(_array[start][path.top()]>=0) path.push(start); else { delete[] paths; return -1;} delete[] paths; return min; } void Graph::Output(ostream& out) { for(int i=0;i<_size;i++) { out.width(2); out << std::right << i << " "; for(int j=0;j<_size;j++) { out.width(10); //out.precision(8); out << std::right <<_array[i][j] <<" "; } out << endl; } } /* S -- START node. T -- END node Path[] -- Path[i]=j indicates the previous node of node i is j. Path[i]=-1 indicates node i has not previous node, e.g. START node. It could be expanded dynamically. Dist[] -- store the lengths of the shortest pathes from START node to END node. It could be expanded dynamically.Dist[i]=INFINITY indicates there is not a path from START node to node i. Prime[] -- Prime[i] indicates node Prime[i] is the prime node of node i. Prime[i]=-1 indicates the node i has not prime node. Base[] -- In opposition to Prime[i], node Base[i] is the original node of node i, that is to say, node i is the prime node of node Base[i]. S -- 开始节点。 T -- 终止节点。 Path[] -- 存储从开始节点到其他节点的最短路径信息。核心思想是每个元素中存储其最短 路径中前一个节点的编号。在MS算法中,由于有向图中扩展节点的加入，此数组会 进行动态扩充。Path[i]=-1表示节点i无前驱节点。 Dist[] -- 存储从开始节点到其他节点的最短距离值。同样此数据也会进行动态扩充。 Dist[i]=INFINITY表示从开始节点到i节点没有路径相连。 Prime[] -- 存储某个节点的扩展节点的编号。Prime[i]=-1表示节点i没有扩展节点。此数组 也会进行动态扩展。通过在Prime[]中寻找节点T的扩展节点T`,T``,T```, ……， 然后在Path[]中依次求得这些扩展节点对应的最短路径，即可以得到前k条最短路径。 Base[] -- Prime[]是用来从基本节点出发寻找扩展节点，而Base[]正好相反，它是用来记录扩展 节点对应的原始节点。如果本来就是原始节点则对应的值就是本身。 */ int Graph::MSAforKSP( unsigned k , path_list& kpaths ) { /* Initialize */ vector<int> Path, Prime, Base; vector<double> Dist; Path.resize(_size); Prime.resize(_size); Base.resize(_size); Dist.resize(_size); for(int i=0;i<_size;i++) { Prime[i] = -1; Base[i] = i; } /* Find the shortest path firstly */ if( dijkstra(&Path[0],&Dist[0]) < 0 ) return 0; path_t path; int j = _size - 1; while(j>=0) { path.push(j); j=Path[j]; } kpaths.push_back(path); // store the shortest path /* Find the 2th - kth shortest paths */ int ki = 1; while( ki < k ) { /* Find the first node with more than a single incoming arc */ unsigned nh = 0; while( path.size() ) { unsigned node = path.top(); path.pop(); int count = 0; for( int i=0; i<_size; i++ ) { if( _array[i][node] >= 0 ) count++; if( count > 1 ) break; } if( count > 1 ) { nh = node; break; } } if( !nh ) break; // there is NOT an alternative path, exit! unsigned ni = 0; /* Add the first prime node to graph */ if( Prime[nh] < 0 ) { unsigned nh1 = addNode(nh,Path[nh]); /* compute the minimal distance from node 0 to nh1 */ double min_dist = (unsigned)INFINITY; int min_node = -1; for(int i=0;i<_size-1;i++) { //cout << Dist[i] << " " << _array[i][nh1] << endl; // for debug if( Dist[i] + (unsigned)_array[i][nh1] < min_dist ) { min_dist = Dist[i] + _array[i][nh1]; min_node = i; } } Dist.push_back(min_dist); Path.push_back(min_node); Prime.push_back(-1); Prime[nh] = nh1; /* record the base node */ unsigned basei = nh; while(basei != Base[basei]) basei = Base[basei]; Base.push_back(basei); if(path.size()) { ni = path.top(); path.pop(); } } /* Get node ni, it must meet it's the first node following nh in path, but its prime node ni` is NOT in graph */ else { while( path.size() ) { ni = path.top(); path.pop(); if(Prime[ni] < 0) break; } } /* Add the other prime nodes to graph */ while(ni) { unsigned ni1 = addNode(ni,Path[ni]); if(Prime[Path[ni]]>=0) _array[Prime[Path[ni]]][ni1] = _array[Path[ni]][ni]; // add the arc -- (ni-1`,ni`) /* compute the minimal distance from node 0 to ni1 */ double min_dist = (unsigned)INFINITY; int min_node = -1; for(int i=0;i<_size-1;i++) { //cout << Dist[i] << " " << _array[i][ni1] << endl; // for debug if( Dist[i] + (unsigned)_array[i][ni1] < min_dist ) { min_dist = Dist[i] + _array[i][ni1]; min_node = i; } } Dist.push_back(min_dist); Path.push_back(min_node); Prime.push_back(-1); Prime[ni] = ni1; /* record the base node */ unsigned basei = ni; while(basei != Base[basei]) basei = Base[basei]; Base.push_back(basei); if( !path.size() ) break; ni = path.top(); path.pop(); } /* get the kth shortest path */ if( !ni ) ni = nh; // if nh is just the end node. path_t temp; int j = Prime[ni]; while(j>=0) { path.push(j); temp.push(Base[j]); j=Path[j]; } if(temp.size()<2) break; kpaths.push_back(temp); // store the kth shortest path ki++; //this->Output(); // for debug } return ki; } /* Look out: Dijkstra algorithm doesn't assure the generated tree from graph is minimal generated tree. */ /// Look out: the returned paths doesn'n include the start node! double Graph::dijkstra( int* paths , unsigned start , unsigned end ) { int* Used = new int[_N]; // label the used nodes, 0 - indicates not used. double* Dist = new double[_N]; // store the min distances from start node to node indicated by current suffix. /* Initialize */ unsigned i; for(i=0;i<_N;i++) { paths[i]= -1; Used[i] = 0; Dist[i] = (_array[start][i] < 0.0) ? INFINITY : _array[start][i]; } Used[start] = 1; // label the start node unsigned count = 0; while(count++ < _N) { int min_node = -1;