gtl/src/bid_dijkstra.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   bid_dijkstra.cpp
0005 //
0006 //==========================================================================
0007 //$Id: bid_dijkstra.cpp,v 1.2 2004/05/06 11:58:19 chris Exp $
0008
0009 #include <GTL/bid_dijkstra.h>
0010 #include <GTL/bin_heap.h>
0011
0012 #include <cstdlib>
0013 #include <iostream>
0014 #include <cassert>
0015
0016 #ifdef __GTL_MSVCC
0017 #   ifdef _DEBUG
0018 #   ifndef SEARCH_MEMORY_LEAKS_ENABLED
0019 #   error SEARCH NOT ENABLED
0020 #   endif
0021 #   define new DEBUG_NEW
0022 #   undef THIS_FILE
0023 static char THIS_FILE[] = __FILE__;
0024 #   endif   // _DEBUG
0025 #endif  // __GTL_MSVCC
0026
0027 __GTL_BEGIN_NAMESPACE
0028
0029 /**
0030  * @internal
0031  * Binary predicate that compares two nodes according to their distance.
0032  */
0033 class less_dist : public binary_function<node, node, bool>
0034 {
0035 public:
0036     /**
0037      * @internal
0038      * Constructor sets pointer to node distances and infimum info.
0039      */
0040     less_dist(const node_map<double>* dist, const node_map<int>* mark)
0041     {
0042     this->dist = dist;
0043     this->mark = mark;
0044     }
0045
0046     /**
0047      * @internal
0048      * Compares distances of @p n1 and @p n2.
0049      */
0050     bool operator()(const node n1, const node n2) const
0051     {
0052     if (((*mark)[n1] == bid_dijkstra::black) &&
0053         ((*mark)[n2] == bid_dijkstra::black))
0054     {
0055         return false;
0056     }
0057     else if ((*mark)[n1] == bid_dijkstra::black)
0058     {
0059         return false;
0060     }
0061     else if ((*mark)[n2] == bid_dijkstra::black)
0062     {
0063         return true;
0064     }
0065     return (*dist)[n1] < (*dist)[n2];
0066     }
0067 private:
0068     /**
0069      * @internal
0070      * Node distances from source.
0071      */
0072     const node_map<double>* dist;
0073
0074     /**
0075      * @internal
0076      * Infimum distance info (color of nodes).
0077      */
0078     const node_map<int>* mark;
0079 };
0080
0081
0082 bid_dijkstra::bid_dijkstra()
0083 {
0084     reset_algorithm();
0085 }
0086
0087
0088 bid_dijkstra::~bid_dijkstra()
0089 {
0090 }
0091
0092
0093 void bid_dijkstra::source_target(const node& s, const node& t)
0094 {
0095     this->s = s;
0096     this->t = t;
0097 }
0098
0099
0100 void bid_dijkstra::weights(const edge_map<double>& weight)
0101 {
0102     this->weight = weight;
0103     weights_set = true;
0104 }
0105
0106
0107 void bid_dijkstra::store_path(bool set)
0108 {
0109     path_set = set;
0110 }
0111
0112
0113 int bid_dijkstra::check(graph& G)
0114 {
0115     if ((s == node()) || (t == node()) || (!weights_set))
0116     {
0117     return GTL_ERROR;
0118     }
0119
0120     bool source_found = false;
0121     bool target_found = false;
0122     graph::node_iterator node_it;
0123     graph::node_iterator nodes_end = G.nodes_end();
0124     for (node_it = G.nodes_begin(); node_it != nodes_end; ++node_it)
0125     {
0126     if (*node_it == s)
0127         {
0128         source_found = true;
0129         if (target_found)
0130         {
0131         break;
0132         }
0133     }
0134     if (*node_it == t)
0135     {
0136         target_found = true;
0137         if (source_found)
0138         {
0139         break;
0140         }
0141     }
0142     }
0143     if ((!source_found) || (!target_found))
0144     {
0145     return(GTL_ERROR);
0146     }
0147
0148     graph::edge_iterator edge_it;
0149     graph::edge_iterator edges_end = G.edges_end();
0150     for(edge_it = G.edges_begin(); edge_it != edges_end; ++edge_it)
0151     {
0152     if (weight[*edge_it] < 0.0)
0153     {
0154         return false;
0155     }
0156     }
0157
0158     return GTL_OK;
0159 }
0160
0161
0162 int bid_dijkstra::run(graph& G)
0163 {
0164     init(G);
0165
0166     double max_dist = 1;
0167     graph::edge_iterator edge_it;
0168     graph::edge_iterator edges_end = G.edges_end();
0169     for(edge_it = G.edges_begin(); edge_it != edges_end; ++edge_it)
0170     {
0171     max_dist += weight[*edge_it];
0172     }
0173
0174     less_dist source_prd(&source_dist, &source_mark);
0175     less_dist target_prd(&target_dist, &target_mark);
0176     bin_heap<node, less_dist> source_heap(source_prd,
0177                       G.number_of_nodes());
0178     bin_heap<node, less_dist> target_heap(target_prd,
0179                       G.number_of_nodes());
0180
0181     source_mark[s] = grey;
0182     source_dist[s] = 0.0;
0183     source_heap.push(s);
0184     target_mark[t] = grey;
0185     target_dist[t] = 0.0;
0186     target_heap.push(t);
0187     while ((!source_heap.is_empty()) || (!target_heap.is_empty()))
0188     {
0189     if (source_dist[source_heap.top()] <=
0190         target_dist[target_heap.top()])
0191     {
0192
0193         // debug:
0194         // source_heap.print_data_container();
0195
0196         node cur_node = source_heap.top();
0197         source_heap.pop();
0198
0199         // debug:
0200         // source_heap.print_data_container();
0201
0202         source_mark[cur_node] = white;
0203
0204         if ((target_mark[cur_node] == white) &&
0205         (max_dist == source_dist[cur_node] +
0206             target_dist[cur_node]))
0207         {
0208         fill_node_edge_lists(cur_node);
0209         break;
0210         }
0211
0212         node::adj_edges_iterator adj_edge_it;
0213         node::adj_edges_iterator adj_edges_end =
0214         cur_node.adj_edges_end();
0215         for (adj_edge_it = cur_node.adj_edges_begin();
0216         adj_edge_it != adj_edges_end;
0217         ++adj_edge_it)
0218         {
0219         node op_node = (*adj_edge_it).opposite(cur_node);
0220         if (source_mark[op_node] == black)
0221         {
0222             source_mark[op_node] = grey;
0223             source_dist[op_node] = source_dist[cur_node] +
0224             weight[*adj_edge_it];
0225             source_heap.push(op_node);
0226
0227             // debug:
0228             // source_heap.print_data_container();
0229
0230             if (path_set)
0231             {
0232             pred[op_node] = *adj_edge_it;
0233             }
0234
0235             if ((target_mark[op_node] == grey) ||
0236             (target_mark[op_node] == white))
0237             {
0238             if (max_dist > source_dist[op_node] +
0239                 target_dist[op_node])
0240             {
0241                 max_dist = source_dist[op_node] +
0242                 target_dist[op_node];
0243             }
0244             }
0245         }
0246         else if (source_mark[op_node] == grey)
0247         {
0248             if (source_dist[op_node] > source_dist[cur_node] +
0249             weight[*adj_edge_it])
0250             {
0251             source_dist[op_node] = source_dist[cur_node] +
0252                 weight[*adj_edge_it];
0253             source_heap.changeKey(op_node);
0254
0255             // debug:
0256             // source_heap.print_data_container();
0257
0258             if (path_set)
0259             {
0260                 pred[op_node] = *adj_edge_it;
0261             }
0262
0263             if ((target_mark[op_node] == grey) ||
0264                 (target_mark[op_node] == white))
0265             {
0266                 if (max_dist > source_dist[op_node] +
0267                 target_dist[op_node])
0268                 {
0269                 max_dist = source_dist[op_node] +
0270                     target_dist[op_node];
0271                 }
0272             }
0273             }
0274         }
0275         else    // (source_mark[op_node] == white)
0276         {
0277             // nothing to do: shortest distance to op_node is
0278             //            already computed
0279         }
0280         }
0281     }
0282     else    // (source_dist[source_heap.top()] >
0283         //  target_dist[target_heap.top()])
0284     {
0285
0286         // debug:
0287         // target_heap.print_data_container();
0288
0289         node cur_node = target_heap.top();
0290         target_heap.pop();
0291
0292         // debug:
0293         // target_heap.print_data_container();
0294
0295         target_mark[cur_node] = white;
0296
0297         if ((source_mark[cur_node] == white) &&
0298         (max_dist == source_dist[cur_node] +
0299             target_dist[cur_node]))
0300         {
0301         fill_node_edge_lists(cur_node);
0302         break;
0303         }
0304
0305         if (G.is_directed())
0306         {
0307         node::in_edges_iterator in_edge_it;
0308         node::in_edges_iterator in_edges_end =
0309             cur_node.in_edges_end();
0310         for (in_edge_it = cur_node.in_edges_begin();
0311              in_edge_it != in_edges_end;
0312              ++in_edge_it)
0313         {
0314             node op_node = (*in_edge_it).opposite(cur_node);
0315             if (target_mark[op_node] == black)
0316             {
0317             target_mark[op_node] = grey;
0318             target_dist[op_node] = target_dist[cur_node] +
0319                 weight[*in_edge_it];
0320             target_heap.push(op_node);
0321
0322             // debug:
0323             // target_heap.print_data_container();
0324
0325             if (path_set)
0326             {
0327                 succ[op_node] = *in_edge_it;
0328             }
0329
0330                 if ((source_mark[op_node] == grey) ||
0331                 (source_mark[op_node] == white))
0332             {
0333                 if (max_dist > source_dist[op_node] +
0334                 target_dist[op_node])
0335                 {
0336                 max_dist = source_dist[op_node] +
0337                     target_dist[op_node];
0338                 }
0339             }
0340             }
0341             else if (target_mark[op_node] == grey)
0342             {
0343             if (target_dist[op_node] > target_dist[cur_node] +
0344                 weight[*in_edge_it])
0345             {
0346                 target_dist[op_node] = target_dist[cur_node] +
0347                 weight[*in_edge_it];
0348                 target_heap.changeKey(op_node);
0349
0350                 // debug:
0351                 // target_heap.print_data_container();
0352
0353                 if (path_set)
0354                 {
0355                 succ[op_node] = *in_edge_it;
0356                 }
0357
0358                     if ((source_mark[op_node] == grey) ||
0359                     (source_mark[op_node] == white))
0360                 {
0361                     if (max_dist > source_dist[op_node] +
0362                     target_dist[op_node])
0363                 {
0364                     max_dist = source_dist[op_node] +
0365                     target_dist[op_node];
0366                 }
0367                 }
0368             }
0369             }
0370             else    // (target_mark[op_node] == white)
0371             {
0372             // nothing to do: shortest distance to op_node is
0373             //        already computed
0374             }
0375         }
0376         }
0377         else    // (G.is_undirected())
0378         {
0379         node::adj_edges_iterator adj_edge_it;
0380         node::adj_edges_iterator adj_edges_end =
0381             cur_node.adj_edges_end();
0382         for (adj_edge_it = cur_node.adj_edges_begin();
0383              adj_edge_it != adj_edges_end;
0384              ++adj_edge_it)
0385         {
0386             node op_node = (*adj_edge_it).opposite(cur_node);
0387             if (target_mark[op_node] == black)
0388             {
0389             target_mark[op_node] = grey;
0390             target_dist[op_node] = target_dist[cur_node] +
0391                 weight[*adj_edge_it];
0392             target_heap.push(op_node);
0393
0394             // debug:
0395             // target_heap.print_data_container();
0396
0397             if (path_set)
0398             {
0399                 succ[op_node] = *adj_edge_it;
0400             }
0401
0402                 if ((source_mark[op_node] == grey) ||
0403                 (source_mark[op_node] == white))
0404             {
0405                 if (max_dist > source_dist[op_node] +
0406                 target_dist[op_node])
0407                 {
0408                 max_dist = source_dist[op_node] +
0409                     target_dist[op_node];
0410                 }
0411             }
0412             }
0413             else if (target_mark[op_node] == grey)
0414             {
0415             if (target_dist[op_node] > target_dist[cur_node] +
0416                 weight[*adj_edge_it])
0417             {
0418                 target_dist[op_node] = target_dist[cur_node] +
0419                 weight[*adj_edge_it];
0420                 target_heap.changeKey(op_node);
0421
0422                 // debug:
0423                 // target_heap.print_data_container();
0424
0425                 if (path_set)
0426                 {
0427                 succ[op_node] = *adj_edge_it;
0428                 }
0429
0430                     if ((source_mark[op_node] == grey) ||
0431                 (source_mark[op_node] == white))
0432                 {
0433                 if (max_dist > source_dist[op_node] +
0434                     target_dist[op_node])
0435                 {
0436                     max_dist = source_dist[op_node] +
0437                     target_dist[op_node];
0438                 }
0439                 }
0440             }
0441             }
0442             else    // (target_mark[op_node] == white)
0443             {
0444             // nothing to do: shortest distance to op_node is
0445             //        already computed
0446             }
0447         }
0448         }
0449     }
0450     }
0451
0452     return GTL_OK;
0453 }
0454
0455
0456 node bid_dijkstra::source() const
0457 {
0458     return s;
0459 }
0460
0461
0462 node bid_dijkstra::target() const
0463 {
0464     return t;
0465 }
0466
0467
0468 bool bid_dijkstra::store_path() const
0469 {
0470     return path_set;
0471 }
0472
0473
0474 bool bid_dijkstra::reached() const
0475 {
0476     return reached_t;
0477 }
0478
0479
0480 double bid_dijkstra::distance() const
0481 {
0482     return dist;
0483 }
0484
0485
0486 bid_dijkstra::shortest_path_node_iterator
0487 bid_dijkstra::shortest_path_nodes_begin()
0488 {
0489     assert(path_set);
0490     return shortest_path_node_list.begin();
0491 }
0492
0493
0494 bid_dijkstra::shortest_path_node_iterator
0495 bid_dijkstra::shortest_path_nodes_end()
0496 {
0497     assert(path_set);
0498     return shortest_path_node_list.end();
0499 }
0500
0501
0502 bid_dijkstra::shortest_path_edge_iterator
0503 bid_dijkstra::shortest_path_edges_begin()
0504 {
0505     assert(path_set);
0506     return shortest_path_edge_list.begin();
0507 }
0508
0509
0510 bid_dijkstra::shortest_path_edge_iterator
0511 bid_dijkstra::shortest_path_edges_end()
0512 {
0513     assert(path_set);
0514     return shortest_path_edge_list.end();
0515 }
0516
0517
0518 void bid_dijkstra::reset()
0519 {
0520     reset_algorithm();
0521 }
0522
0523
0524 void bid_dijkstra::reset_algorithm()
0525 {
0526     s = node();
0527     t = node();
0528     weights_set = false;
0529     path_set = false;
0530     dist = -1.0;
0531     reached_t = false;
0532 }
0533
0534
0535 void bid_dijkstra::init(graph& G)
0536 {
0537     source_dist.init(G, -1.0);
0538     source_mark.init(G, black);
0539     target_dist.init(G, -1.0);
0540     target_mark.init(G, black);
0541
0542     if (path_set)
0543     {
0544     pred.init(G, edge());
0545     succ.init(G, edge());
0546     shortest_path_node_list.clear();
0547     shortest_path_edge_list.clear();
0548     }
0549 }
0550
0551
0552 void bid_dijkstra::fill_node_edge_lists(const node& n)
0553 {
0554     reached_t = true;
0555     if (t == s)
0556     {
0557     return;
0558     }
0559     dist = source_dist[n] + target_dist[n];
0560     if (path_set)
0561     {
0562     node cur_node;
0563     edge cur_edge;
0564
0565     cur_node = n;
0566     cur_edge = pred[cur_node];
0567     while (cur_edge != edge())
0568     {
0569         shortest_path_edge_list.push_front(cur_edge);
0570         cur_node = cur_edge.opposite(cur_node);
0571         cur_edge = pred[cur_node];
0572         shortest_path_node_list.push_front(cur_node);
0573     }
0574     shortest_path_node_list.push_back(n);
0575     cur_node = n;
0576     cur_edge = succ[cur_node];
0577     while (cur_edge != edge())
0578     {
0579         shortest_path_edge_list.push_back(cur_edge);
0580         cur_node = cur_edge.opposite(cur_node);
0581         cur_edge = succ[cur_node];
0582         shortest_path_node_list.push_back(cur_node);
0583     }
0584     }
0585 }
0586
0587 __GTL_END_NAMESPACE
0588
0589 //--------------------------------------------------------------------------
0590 //   end of file
0591 //--------------------------------------------------------------------------