LinkStateGraph.cc

Go to the documentation of this file.
00001 /*
00002  * IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. By
00003  * downloading, copying, installing or using the software you agree to
00004  * this license. If you do not agree to this license, do not download,
00005  * install, copy or use the software.
00006  * 
00007  * Intel Open Source License 
00008  * 
00009  * Copyright (c) 2004 Intel Corporation. All rights reserved. 
00010  * 
00011  * Redistribution and use in source and binary forms, with or without
00012  * modification, are permitted provided that the following conditions are
00013  * met:
00014  * 
00015  *   Redistributions of source code must retain the above copyright
00016  *   notice, this list of conditions and the following disclaimer.
00017  * 
00018  *   Redistributions in binary form must reproduce the above copyright
00019  *   notice, this list of conditions and the following disclaimer in the
00020  *   documentation and/or other materials provided with the distribution.
00021  * 
00022  *   Neither the name of the Intel Corporation nor the names of its
00023  *   contributors may be used to endorse or promote products derived from
00024  *   this software without specific prior written permission.
00025  *  
00026  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
00027  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
00028  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
00029  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE INTEL OR
00030  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
00031  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
00032  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
00033  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
00034  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
00035  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00036  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
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     /* first reset all the costs in the link state graph */
00070     for(set<Vertex*>::iterator i=vertices_.begin(); i!=vertices_.end(); i++) 
00071         (*i)->dijkstra_distance_=100000;  //maxint?
00072     
00073     from->dijkstra_distance_=0;
00074 
00075     /* now compute the dijkstra distances for each node */
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); // sanity check
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     /* to get the next hop (or the entire path), walk backwards from
00104      * the destination */
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         // compare the string against the pattern. 
00173         // XXX/jakob - this matching is pretty lame. what can we do 
00174         //             without making too many assumptions about eids? 
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         // if we found a match, we're done  (XXX/jakob - not bothering with many matches at the moment)
00182         log_debug("Found a match! %s matches %s",pattern,eid);
00183         return *iter;
00184 
00185  not_a_match:
00186         continue;
00187         // try the next vertex
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     // XXX/jakob - later on, this also needs to dump the link schedule, if one exists.
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 } // namespace dtn

Generated on Fri Dec 22 14:47:59 2006 for DTN Reference Implementation by  doxygen 1.5.1