00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039 #include <stdlib.h>
00040 #include <set>
00041 #include <queue>
00042
00043 #include "LinkStateGraph.h"
00044
00045
00046 namespace dtn {
00047 using namespace std;
00048
00050 LinkStateGraph::LinkStateGraph()
00051 : Logger("LinkStateGraph", "/dtn/route/linkstate/graph")
00052 {}
00053
00055 LinkStateGraph::Vertex*
00056 LinkStateGraph::findNextHop(Vertex* from, Vertex *to)
00057 {
00058 priority_queue< Vertex*, vector<Vertex*>, less<Vertex*> > queue;
00059 Vertex* current;
00060
00061 if(!from || !to)
00062 {
00063 log_info("Can't route to null Vertex.");
00064 return 0;
00065 }
00066
00067 queue.push(from);
00068
00069
00070 for(set<Vertex*>::iterator i=vertices_.begin(); i!=vertices_.end(); i++)
00071 (*i)->dijkstra_distance_=100000;
00072
00073 from->dijkstra_distance_=0;
00074
00075
00076 while(!queue.empty())
00077 {
00078 current = queue.top();
00079 queue.pop();
00080 for(map<Vertex*, Edge*>::iterator e=from->outgoing_edges_.begin();
00081 e!=from->outgoing_edges_.end(); e++)
00082 {
00083 Vertex* peer=(*e).first;
00084 Edge* edge=(*e).second;
00085
00086 ASSERT(peer && edge);
00087
00088 if(peer->dijkstra_distance_ >= current->dijkstra_distance_ +
00089 edge->cost_)
00090 {
00091 peer->dijkstra_distance_ = current->dijkstra_distance_ +
00092 edge->cost_;
00093 queue.push(peer);
00094 }
00095 }
00096 }
00097
00098 if(to->dijkstra_distance_ == 100000) {
00099 log_debug( "No link-state route to %s from %s.",to->eid_, from->eid_);
00100 return 0;
00101 }
00102
00103
00104
00105 current = to;
00106 while(true)
00107 {
00108 Vertex* best=(*current->incoming_edges_.begin()).first;
00109 for(map<Vertex*, Edge*>::iterator e=current->incoming_edges_.begin(); e != current->incoming_edges_.end(); e++)
00110 {
00111 if((*e).first->dijkstra_distance_ < best->dijkstra_distance_)
00112 best=(*e).first;
00113 }
00114
00115 if(best == from)
00116 return current;
00117 else
00118 current = best;
00119 }
00120 return current;
00121 }
00122
00124 LinkStateGraph::Edge*
00125 LinkStateGraph::addEdge(Vertex *from, Vertex *to, cost_t cost) {
00126 if(!from->outgoing_edges_[to]) {
00127 Edge* e=new Edge(from, to, cost);
00128
00129 from->outgoing_edges_[to]=e;
00130 to->incoming_edges_[from]=e;
00131 return e;
00132 }
00133 else return 0;
00134 }
00135
00137 LinkStateGraph::Edge*
00138 LinkStateGraph::getEdge(Vertex *from, Vertex *to)
00139 {
00140 return from->outgoing_edges_[to];
00141 }
00142
00144 void
00145 LinkStateGraph::removeEdge(Edge* e)
00146 {
00147 Vertex *from=e->from_, *to=e->to_;
00148
00149 ASSERT(from->outgoing_edges_[to]==e);
00150 ASSERT(to->incoming_edges_[from]==e);
00151
00152 from->outgoing_edges_[to]=0;
00153 to->incoming_edges_[from]=0;
00154
00155 delete e;
00156 }
00157
00159 LinkStateGraph::Vertex *
00160 LinkStateGraph::getMatchingVertex(const char* eid) {
00161
00162 log_info("getMatchingVertex has %zu vertices.",
00163 vertices_.size());
00164
00165 for(set<Vertex*>::iterator iter=vertices_.begin();iter!=vertices_.end();iter++)
00166 {
00167 char* pattern=(*iter)->eid_;
00168 unsigned int len=min(strlen(pattern),strlen(eid));
00169
00170 log_info("Matching pattern %s against eid %s.",pattern,eid);
00171
00172
00173
00174
00175 for(unsigned int i=0;i<len;i++)
00176 if(pattern[i]!=eid[i] &&
00177 !(i==strlen(pattern) &&
00178 pattern[i]=='*'))
00179 goto not_a_match;
00180
00181
00182 log_debug("Found a match! %s matches %s",pattern,eid);
00183 return *iter;
00184
00185 not_a_match:
00186 continue;
00187
00188 }
00189 return 0;
00190 }
00191
00192 LinkStateGraph::Vertex *
00193 LinkStateGraph::getVertex(const char* eid) {
00194 Vertex * v;
00195 for(set<Vertex*>::iterator i=vertices_.begin();i!=vertices_.end();i++)
00196 {
00197 if(strcmp(eid,(*i)->eid_)==0) {
00198 log_debug("Found matching vertex for %s.",eid);
00199 return *i;
00200 }
00201 }
00202
00203 v=new Vertex(eid);
00204 vertices_.insert(v);
00205 return v;
00206 }
00207
00208 void
00209 LinkStateGraph::dumpGraph(oasys::StringBuffer* buf)
00210 {
00211
00212 for(set<Edge*>::iterator i=edges_.begin();i!=edges_.end();i++)
00213 buf->appendf("%s %s %d",(*i)->from_->eid_, (*i)->to_->eid_, (*i)->cost_);
00214 }
00215
00216 std::set<LinkStateGraph::Edge*>
00217 LinkStateGraph::edges()
00218 {
00219 return edges_;
00220 }
00221
00222 LinkStateGraph::Vertex::Vertex(const char * eid) {
00223 memset(eid_,0,MAX_EID);
00224 strcpy(eid_,eid);
00225 dijkstra_distance_=0;
00226 }
00227
00228 LinkStateGraph::Edge::Edge(Vertex* from, Vertex* to, cost_t cost)
00229 {
00230 from_=from;
00231 to_=to;
00232 cost_=cost;
00233 contact_.start=0;
00234 contact_.duration=0;
00235 }
00236
00237 }