1 /*

     2  *    Copyright 2007 Intel Corporation

     3  * 

     4  *    Licensed under the Apache License, Version 2.0 (the "License");

     5  *    you may not use this file except in compliance with the License.

     6  *    You may obtain a copy of the License at

     7  * 

     8  *        http://www.apache.org/licenses/LICENSE-2.0

     9  * 

    10  *    Unless required by applicable law or agreed to in writing, software

    11  *    distributed under the License is distributed on an "AS IS" BASIS,

    12  *    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

    13  *    See the License for the specific language governing permissions and

    14  *    limitations under the License.

    15  */

    16 

    17 #include "MultiGraph.h"

    18 #include <oasys/util/StringAppender.h>

    19 #include <oasys/util/UpdatablePriorityQueue.h>

    20 

    21 namespace dtn {

    22 

    23 //----------------------------------------------------------------------

    24 template <typename _NodeInfo, typename _EdgeInfo>

    25 inline MultiGraph<_NodeInfo,_EdgeInfo>

    26 ::MultiGraph()

    27     : Logger("MultiGraph", "/dtn/route/graph")

    28 {

    29 }

    30 

    31 //----------------------------------------------------------------------

    32 template <typename _NodeInfo, typename _EdgeInfo>

    33 inline MultiGraph<_NodeInfo,_EdgeInfo>

    34 ::~MultiGraph()

    35 {

    36 }

    37 

    38 //----------------------------------------------------------------------

    39 template <typename _NodeInfo, typename _EdgeInfo>

    40 inline class MultiGraph<_NodeInfo,_EdgeInfo>::Node*

    41 MultiGraph<_NodeInfo,_EdgeInfo>

    42 ::add_node(const std::string& id, const _NodeInfo& info)

    43 {

    44     Node* n = new Node(id, info);

    45     this->nodes_.push_back(n);

    46     return n;

    47 }

    48 

    49 //----------------------------------------------------------------------

    50 template <typename _NodeInfo, typename _EdgeInfo>

    51 inline class MultiGraph<_NodeInfo,_EdgeInfo>::Node*

    52 MultiGraph<_NodeInfo,_EdgeInfo>

    53 ::find_node(const std::string& id) const

    54 {

    55     typename NodeVector::const_iterator iter;

    56     for (iter = this->nodes_.begin(); iter != this->nodes_.end(); ++iter) {

    57         if ((*iter)->id_ == id) {

    58             return *iter;

    59         }

    60     }

    61     return NULL;

    62 }

    63     

    64 //----------------------------------------------------------------------

    65 template <typename _NodeInfo, typename _EdgeInfo>

    66 inline bool

    67 MultiGraph<_NodeInfo,_EdgeInfo>

    68 ::del_node(const std::string& id)

    69 {

    70     class NodeVector::iterator iter;

    71     for (iter = this->nodes_.begin(); iter != this->nodes_.end(); ++iter) {

    72         if ((*iter)->id_ == id) {

    73             delete (*iter);

    74             this->nodes_.erase(iter);

    75             return true;

    76         }

    77     }

    78 

    79     return false;

    80 }

    81     

    82 //----------------------------------------------------------------------

    83 template <typename _NodeInfo, typename _EdgeInfo>

    84 inline void

    85 MultiGraph<_NodeInfo,_EdgeInfo>

    86 ::clear()

    87 {

    88     class NodeVector::iterator iter;

    89     for (iter = this->nodes_.begin(); iter != this->nodes_.end(); ++iter) {

    90         delete (*iter);

    91     }

    92 

    93     this->nodes_.clear();

    94 }

    95     

    96 //----------------------------------------------------------------------

    97 template <typename _NodeInfo, typename _EdgeInfo>

    98 inline class MultiGraph<_NodeInfo,_EdgeInfo>::Edge*

    99 MultiGraph<_NodeInfo,_EdgeInfo>

   100 ::add_edge(Node* a, Node* b, const _EdgeInfo& info)

   101 {

   102     Edge* e = new Edge(a, b, info);

   103     a->out_edges_.push_back(e);

   104     b->in_edges_.push_back(e);

   105     return e;

   106 }

   107 

   108 //----------------------------------------------------------------------

   109 template <typename _NodeInfo, typename _EdgeInfo>

   110 inline class MultiGraph<_NodeInfo,_EdgeInfo>::Edge*

   111 MultiGraph<_NodeInfo,_EdgeInfo>

   112 ::find_edge(const Node* a, const Node* b, const _EdgeInfo& info)

   113 {

   114     typename EdgeVector::const_iterator iter;

   115     for (iter = a->out_edges_.begin(); iter != a->out_edges_.end(); ++iter) {

   116         const Edge* edge = *iter;

   117         if ((edge->dest() == b) && (edge->info() == info))

   118         {

   119             return *iter;

   120         }

   121     }

   122 

   123     return NULL;

   124 }

   125 

   126 //----------------------------------------------------------------------

   127 template <typename _NodeInfo, typename _EdgeInfo>

   128 inline bool

   129 MultiGraph<_NodeInfo,_EdgeInfo>

   130 ::del_edge(Node* node, Edge* edge)

   131 {

   132     return node->del_edge(edge);

   133 }

   134 

   135 

   136 //----------------------------------------------------------------------

   137 template <typename _NodeInfo, typename _EdgeInfo>

   138 inline

   139 MultiGraph<_NodeInfo,_EdgeInfo>

   140 ::Node::~Node()

   141 {

   142     while (! this->out_edges_.empty()) {

   143         this->del_edge(*this->out_edges_.begin());

   144     }

   145 

   146     while (! this->in_edges_.empty()) {

   147         Edge* edge = *this->in_edges_.begin();

   148         edge->source()->del_edge(edge);

   149     }

   150 }

   151 

   152 //----------------------------------------------------------------------

   153 template <typename _NodeInfo, typename _EdgeInfo>

   154 inline bool

   155 MultiGraph<_NodeInfo,_EdgeInfo>

   156 ::Node::del_edge(Edge* edge)

   157 {

   158     typename EdgeVector::iterator ei, ei2;

   159     for (ei = this->out_edges_.begin();

   160          ei != this->out_edges_.end(); ++ei)

   161     {

   162         if (*ei == edge)

   163         {

   164             // delete the corresponding in_edge pointer, which must

   165             // exist or else there's some internal inconsistency

   166             ei2 = edge->dest()->in_edges_.begin();

   167             while (1) {

   168                 ASSERTF(ei2 != edge->dest()->in_edges_.end(),

   169                         "out_edge / in_edge mismatch!!");

   170                 if (*ei2 == edge)

   171                     break;

   172                 ++ei2;

   173             }

   174             

   175             this->out_edges_.erase(ei);

   176             edge->dest()->in_edges_.erase(ei2);

   177             delete edge;

   178             return true;

   179         }

   180     }

   181     

   182     return false;

   183 }

   184 

   185 //----------------------------------------------------------------------

   186 template <typename _NodeInfo, typename _EdgeInfo>

   187 inline

   188 MultiGraph<_NodeInfo,_EdgeInfo>

   189 ::SearchInfo::SearchInfo(Bundle* bundle)

   190     : bundle_(bundle)

   191 {

   192     now_.get_time();

   193 }

   194         

   195 //----------------------------------------------------------------------

   196 template <typename _NodeInfo, typename _EdgeInfo>

   197 inline bool

   198 MultiGraph<_NodeInfo,_EdgeInfo>

   199 ::get_reverse_path(const Node* a, const Node* b, EdgeVector* path)

   200 {

   201     const Node* cur = b;

   202     do {

   203         ASSERT(cur->prev_->dest() == cur);

   204         ASSERT(cur->prev_->source() != cur);

   205 

   206         path->push_back(cur->prev_);

   207         cur = cur->prev_->source();

   208     } while (cur != a);

   209 

   210     return true;

   211 }

   212 

   213 //----------------------------------------------------------------------

   214 template <typename _NodeInfo, typename _EdgeInfo>

   215 inline void

   216 MultiGraph<_NodeInfo,_EdgeInfo>

   217 ::shortest_path(const Node* a, const Node* b,

   218                 EdgeVector* path, WeightFn* weight_fn,

   219                 Bundle* bundle)

   220 {

   221     log_debug("calculating shortest path from %s -> %s",

   222               a->id_.c_str(), b->id_.c_str());

   223     

   224     ASSERT(a != NULL);

   225     ASSERT(b != NULL);

   226     ASSERT(path != NULL);

   227     ASSERT(a != b);

   228     path->clear();

   229 

   230     // cons up the search info

   231     SearchInfo info(bundle);

   232     

   233     // first clear the existing distances

   234     for (typename NodeVector::iterator i = this->nodes_.begin();

   235          i != this->nodes_.end(); ++i)

   236     {

   237         (*i)->distance_ = 0xffffffff;

   238         (*i)->color_    = Node::WHITE;

   239         (*i)->prev_     = NULL;

   240     }

   241     

   242     // compute dijkstra distances

   243     oasys::UpdatablePriorityQueue<const Node*,

   244         std::vector<const Node*>,

   245         DijkstraCompare> q;

   246     

   247     a->distance_ = 0;

   248     q.push(a);

   249     do {

   250         const Node* cur = q.top();

   251         q.pop();

   252 

   253         for (typename EdgeVector::const_iterator ei = cur->out_edges_.begin();

   254              ei != cur->out_edges_.end(); ++ei)

   255         {

   256             Edge* edge = *ei;

   257             Node* peer = edge->dest();

   258 

   259             ASSERT(edge->source() == cur);

   260             ASSERT(peer != cur); // no loops

   261             

   262             u_int32_t weight = (*weight_fn)(info, edge);

   263 

   264             log_debug("examining edge id %s (weight %u) "

   265                       "from %s (distance %u) -> %s (distance %u)",

   266                       EdgeFormatter().format(edge->info()),

   267                       weight, cur->id_.c_str(), cur->distance_,

   268                       peer->id_.c_str(), peer->distance_);

   269             

   270             if (weight != 0xffffffff &&

   271                 peer->distance_ > cur->distance_ + weight)

   272             {

   273                 if (peer->color_ == Node::BLACK)

   274                 {

   275                     log_crit("revisiting black node when "

   276                              "calculating shortest path from %s -> %s!!!",

   277                              a->id_.c_str(), b->id_.c_str());

   278                     

   279                     log_crit("cur %s: distance %u edge %s weight %u "

   280                              "prev edge %s from %s",

   281                              cur->id_.c_str(), cur->distance_,

   282                              EdgeFormatter().format(edge->info()),

   283                              weight,

   284                              cur->prev_

   285                                ? EdgeFormatter().format(cur->prev_->info())

   286                                : "NULL!",

   287                              cur->prev_ ?

   288                              cur->prev_->source()->id_.c_str() : "");

   289 

   290                     log_crit("peer %s: distance %u, prev edge %s from %s",

   291                              peer->id_.c_str(), peer->distance_,

   292                              peer->prev_

   293                                ? EdgeFormatter().format(peer->prev_->info())

   294                                : "NULL!",

   295                              peer->prev_ ?

   296                                peer->prev_->source()->id_.c_str() : "");

   297 

   298                     continue;

   299                 }

   300                     

   301                 peer->distance_ = cur->distance_ + weight;

   302                 peer->prev_     = edge;

   303 

   304                 if (peer->color_ == Node::WHITE)

   305                 {

   306                     log_debug("pushing node %s (distance %u) onto queue",

   307                               peer->id_.c_str(), peer->distance_);

   308                     peer->color_ = Node::GRAY;

   309                     q.push(peer);

   310                 }

   311                 else if (peer->color_ == Node::GRAY)

   312                 {

   313                     log_debug("updating node %s in queue", peer->id_.c_str());

   314                     q.update(peer);

   315                 }

   316                 else {

   317                     NOTREACHED;

   318                 }

   319             }

   320         }

   321 

   322         cur->color_ = Node::BLACK;

   323 

   324         // safe to bail once we reach the destination

   325         if (cur == b) {

   326             break;

   327         }

   328              

   329     } while (!q.empty());

   330     

   331     if (b->distance_ == 0xffffffff) {

   332         log_debug("no path found from %s -> %s",

   333                   a->id_.c_str(), b->id_.c_str());

   334         return; // no path

   335     }

   336 

   337     get_reverse_path(a, b, path);

   338     

   339     size_t len = path->size();

   340     log_debug("found path of length %zu from %s -> %s",

   341               len, a->id_.c_str(), b->id_.c_str());

   342     for (size_t i = 0; i < len; ++i) {

   343         Edge* e = (*path)[len - i - 1];

   344         (void)e;

   345         log_debug("hop %zu: %s -> %s %s", i,

   346                   e->source()->id_.c_str(), e->dest()->id_.c_str(), 

   347                   EdgeFormatter().format(e->info()));

   348     }

   349 }

   350 

   351 //----------------------------------------------------------------------

   352 template <typename _NodeInfo, typename _EdgeInfo>

   353 inline class MultiGraph<_NodeInfo,_EdgeInfo>::Edge*

   354 MultiGraph<_NodeInfo,_EdgeInfo>

   355 ::best_next_hop(const Node* a, const Node* b, WeightFn* weight_fn,

   356                 Bundle* bundle)

   357 {

   358     EdgeVector path;

   359     shortest_path(a, b, &path, weight_fn, bundle);

   360     if (path.empty()) {

   361         return NULL;

   362     }

   363 

   364     ASSERT(path.back()->source() == a); // sanity

   365     return path.back();

   366 }

   367 

   368 //----------------------------------------------------------------------

   369 template <typename _NodeInfo, typename _EdgeInfo>

   370 inline int

   371 MultiGraph<_NodeInfo,_EdgeInfo>

   372 ::format(char* buf, size_t sz) const

   373 {

   374     oasys::StringAppender sa(buf, sz);

   375     

   376     typename NodeVector::const_iterator ni;

   377     typename EdgeVector::const_iterator ei;

   378     

   379     for (ni = this->nodes_.begin(); ni != this->nodes_.end(); ++ni)

   380     {

   381         sa.appendf("%s ->", (*ni)->id_.c_str());

   382         

   383         for (ei = (*ni)->out_edges_.begin();

   384              ei != (*ni)->out_edges_.end(); ++ei)

   385         {

   386             sa.appendf(" %s(%s)", 

   387                        (*ei)->dest()->id_.c_str(),

   388                        EdgeFormatter().format((*ei)->info()));

   389         }

   390         sa.append("\n");

   391     }

   392 

   393     return sa.desired_length();

   394 }

   395 

   396 //----------------------------------------------------------------------

   397 template <typename _NodeInfo, typename _EdgeInfo>

   398 inline int

   399 MultiGraph<_NodeInfo,_EdgeInfo>

   400 ::NodeVector::format(char* buf, size_t sz) const

   401 {

   402     oasys::StringAppender sa(buf, sz);

   403     typename NodeVector::const_iterator i;

   404     for (i = this->begin(); i != this->end(); ++i)

   405     {

   406         sa.appendf("%s%s",

   407                    i == this->begin() ? "" : " ",

   408                    (*i)->id().c_str());

   409     }

   410     return sa.desired_length();

   411 }

   412 

   413 //----------------------------------------------------------------------

   414 template <typename _NodeInfo, typename _EdgeInfo>

   415 inline int

   416 MultiGraph<_NodeInfo,_EdgeInfo>

   417 ::EdgeVector::format(char* buf, size_t sz) const

   418 {

   419     oasys::StringAppender sa(buf, sz);

   420     typename EdgeVector::const_iterator i;

   421     for (i = this->begin(); i != this->end(); ++i)

   422     {

   423         sa.appendf("%s[%s -> %s(%s)]",

   424                    i == this->begin() ? "" : " ",

   425                    (*i)->source()->id().c_str(),

   426                    (*i)->dest()->id().c_str(),

   427                    EdgeFormatter().format((*i)->info()));

   428     }

   429     return sa.desired_length();

   430 }

   431 

   432 //----------------------------------------------------------------------

   433 template <typename _NodeInfo, typename _EdgeInfo>

   434 inline void

   435 MultiGraph<_NodeInfo,_EdgeInfo>

   436 ::EdgeVector::debug_format(oasys::StringBuffer* buf) const

   437 {

   438     typename EdgeVector::const_iterator i;

   439     for (i = this->begin(); i != this->end(); ++i)

   440     {

   441         buf->appendf("\t%s -> %s (%s) (distance %u)\n",

   442                      (*i)->source()->id().c_str(),

   443                      (*i)->dest()->id().c_str(),

   444                      EdgeFormatter().format((*i)->info()),

   445                      MultiGraph<_NodeInfo,_EdgeInfo>::NodeDistance((*i)->dest()));

   446     }

   447 }

   448 

   449 

   450 } // namespace dtn

   451