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