Alex Bikfalvi
SimStream Documentation
TopoBriteRoute.cpp
00001 #include "Headers.h" 00002 #include "TopoBriteRoute.h" 00003 00004 #define MAX_DIST ((double)1.7E+308) 00005 00006 CTopoBriteRoute::CTopoBriteRoute( 00007 __uint32 numNodes, 00008 __uint32 numEdges, 00009 CTopoBriteNode** nodes, 00010 CTopoBriteEdge** edges 00011 ) 00012 { 00013 assert(nodes); 00014 assert(edges); 00015 assert(numNodes); 00016 assert(numEdges); 00017 00018 this->numNodes = numNodes; 00019 this->numEdges = numEdges; 00020 00021 this->nodes = nodes; 00022 this->edges = edges; 00023 00024 // Create the route (nodes and edges) 00025 this->routeNode = new int[this->numNodes*this->numNodes]; 00026 assert(this->routeNode); 00027 00028 this->routeEdge = new int[this->numNodes*this->numNodes]; 00029 assert(this->routeNode); 00030 00031 // Init the route 00032 for(__uint32 index = 0; index < this->numNodes*this->numNodes; index++) 00033 { 00034 this->routeNode[index] = -1; 00035 this->routeEdge[index] = -1; 00036 } 00037 00038 // Distance vector 00039 this->distance = new __uint32[this->numNodes*this->numNodes]; 00040 assert(this->numNodes); 00041 00042 // Calculate the shortest path tree for each node 00043 for(__uint32 index = 0; index < this->numNodes; index++) 00044 this->ShortestPath(index); 00045 } 00046 00047 CTopoBriteRoute::~CTopoBriteRoute() 00048 { 00049 delete[] this->routeNode; 00050 delete[] this->routeEdge; 00051 delete[] this->distance; 00052 } 00053 00054 void CTopoBriteRoute::ShortestPath(__uint32 node) 00055 { 00056 // The shortest path from every node in the graph to "node" 00057 00058 // Allocate the distance array 00059 double* dist = new double[this->numNodes]; 00060 assert(dist); 00061 00062 // Allocate the results array 00063 bool* res = new bool[this->numNodes]; 00064 00065 // Init 00066 this->ShortestPathInit(node, dist, res); 00067 00068 for(__uint32 numRes = this->numNodes; numRes;) 00069 { 00070 // Search for the node with the lowest distance that was not previously selected 00071 __uint32 bestNode; 00072 double bestDist = MAX_DIST; 00073 for(__uint32 index = 0; index < this->numNodes; index++) 00074 { 00075 if(res[index]) 00076 if(dist[index] < bestDist) 00077 { 00078 bestDist = dist[index]; 00079 bestNode = index; 00080 } 00081 } 00082 00083 // If the minimum distance is infinite, stop 00084 if(MAX_DIST == bestDist) break; 00085 00086 // Set the node with the minimum distance as selected 00087 res[bestNode] = 0; 00088 00089 // For each node connected to the best node 00090 for(__uint32 index = 0; index < this->nodes[bestNode]->Degree(); index++) 00091 { 00092 // Get the node (the node that is at the other end of the link) 00093 __uint32 neighbor = this->edges[this->nodes[bestNode]->Edge(index)]->OtherNode(bestNode); 00094 00095 double cost = dist[bestNode] + this->edges[this->nodes[bestNode]->Edge(index)]->Cost(); 00096 00097 if(cost < dist[neighbor]) 00098 { 00099 dist[neighbor] = cost; 00100 this->distance[node*this->numNodes+neighbor] = this->distance[node*this->numNodes+bestNode] + 1; 00101 00102 // The next node from "neighbor" on the route to the "node" is "bestNode" 00103 this->routeNode[node * this->numNodes + neighbor] = bestNode; 00104 this->routeEdge[node * this->numNodes + neighbor] = this->nodes[bestNode]->Edge(index); 00105 } 00106 } 00107 00108 } 00109 00110 // Delete the distance array 00111 delete[] dist; 00112 00113 // Delete the results array 00114 delete[] res; 00115 } 00116 00117 void CTopoBriteRoute::ShortestPathInit(__uint32 node, double* dist, bool* res) 00118 { 00119 for(__uint32 index = 0; index < this->numNodes; index++) 00120 { 00121 this->distance[node*this->numNodes+index] = 0xFFFFFFFF; 00122 dist[index] = MAX_DIST; 00123 res[index] = 1; 00124 } 00125 this->distance[node*this->numNodes+node] = 0; 00126 dist[node] = 0; 00127 } 00128 00129 __uint32 CTopoBriteRoute::NextEdge(__uint32 node, __uint32 dst) 00130 { 00131 assert(this->routeNode[dst * this->numNodes + node] >= 0); 00132 return this->routeEdge[dst * this->numNodes + node]; 00133 } 00134 00135 __uint32 CTopoBriteRoute::NextNode(__uint32 node, __uint32 dst) 00136 { 00137 assert(this->routeNode[dst * this->numNodes + node] >= 0); 00138 return this->routeNode[dst * this->numNodes + node]; 00139 } 00140 00141 __uint32 CTopoBriteRoute::Distance(__uint32 src, __uint32 dst) 00142 { 00143 return this->distance[src*this->numNodes+dst]; 00144 }
Last updated: February 8, 2011