LinkStateGraph.cc

Go to the documentation of this file.
00001 /*
00002  *    Copyright 2004-2006 Intel Corporation
00003  * 
00004  *    Licensed under the Apache License, Version 2.0 (the "License");
00005  *    you may not use this file except in compliance with the License.
00006  *    You may obtain a copy of the License at
00007  * 
00008  *        http://www.apache.org/licenses/LICENSE-2.0
00009  * 
00010  *    Unless required by applicable law or agreed to in writing, software
00011  *    distributed under the License is distributed on an "AS IS" BASIS,
00012  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
00013  *    See the License for the specific language governing permissions and
00014  *    limitations under the License.
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     /* first reset all the costs in the link state graph */
00049     for(set<Vertex*>::iterator i=vertices_.begin(); i!=vertices_.end(); i++) 
00050         (*i)->dijkstra_distance_=100000;  //maxint?
00051     
00052     from->dijkstra_distance_=0;
00053 
00054     /* now compute the dijkstra distances for each node */
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); // sanity check
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     /* to get the next hop (or the entire path), walk backwards from
00083      * the destination */
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         // compare the string against the pattern. 
00152         // XXX/jakob - this matching is pretty lame. what can we do 
00153         //             without making too many assumptions about eids? 
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         // if we found a match, we're done  (XXX/jakob - not bothering with many matches at the moment)
00161         log_debug("Found a match! %s matches %s",pattern,eid);
00162         return *iter;
00163 
00164  not_a_match:
00165         continue;
00166         // try the next vertex
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     // XXX/jakob - later on, this also needs to dump the link schedule, if one exists.
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 } // namespace dtn

Generated on Sat Sep 8 08:36:17 2007 for DTN Reference Implementation by  doxygen 1.5.3