gtl/src/dijkstra.cpp

0001 /* This software is distributed under the GNU Lesser General Public License */
0002 //==========================================================================
0003 //
0004 //   dijkstra.cpp
0005 //
0006 //==========================================================================
0007 //$Id: dijkstra.cpp,v 1.6 2002/12/23 13:46:41 chris Exp $
0008
0009 #include <GTL/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] == dijkstra::black) &&
0053         ((*mark)[n2] == dijkstra::black))
0054     {
0055         return false;
0056     }
0057     else if ((*mark)[n1] == dijkstra::black)
0058     {
0059         return false;
0060     }
0061     else if ((*mark)[n2] == 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 dijkstra::dijkstra()
0083 {
0084     reset_algorithm();
0085 }
0086
0087
0088 dijkstra::~dijkstra()
0089 {
0090 }
0091
0092
0093 void dijkstra::source(const node& n)
0094 {
0095     s = n;
0096 }
0097
0098
0099 void dijkstra::target(const node& n)
0100 {
0101     t = n;
0102 }
0103
0104
0105 void dijkstra::weights(const edge_map<double>& weight)
0106 {
0107     this->weight = weight;
0108     weights_set = true;
0109 }
0110
0111
0112 void dijkstra::store_preds(bool set)
0113 {
0114     preds_set = set;
0115 }
0116
0117
0118 int dijkstra::check(graph& G)
0119 {
0120     if ((s == node()) || (!weights_set))
0121     {
0122     return GTL_ERROR;
0123     }
0124
0125     bool source_found = false;
0126     graph::node_iterator node_it;
0127     graph::node_iterator nodes_end = G.nodes_end();
0128     for (node_it = G.nodes_begin(); node_it != nodes_end; ++node_it)
0129     {
0130     if (*node_it == s)
0131         {
0132         source_found = true;
0133         break;
0134     }
0135     }
0136     if (!source_found)
0137     {
0138     return(GTL_ERROR);
0139     }
0140
0141     graph::edge_iterator edge_it;
0142     graph::edge_iterator edges_end = G.edges_end();
0143     for(edge_it = G.edges_begin(); edge_it != edges_end; ++edge_it)
0144     {
0145     if (weight[*edge_it] < 0.0)
0146     {
0147         return false;
0148     }
0149     }
0150
0151     return GTL_OK;
0152 }
0153
0154
0155 int dijkstra::run(graph& G)
0156 {
0157     init(G);
0158
0159     less_dist prd(&dist, &mark);
0160     bin_heap<node, less_dist> node_heap(prd, G.number_of_nodes());
0161     mark[s] = grey;
0162     dist[s] = 0.0;
0163     node_heap.push(s);
0164     while (!node_heap.is_empty())
0165     {
0166
0167     // debug:
0168     // node_heap.print_data_container();
0169
0170     node cur_node = node_heap.top();
0171     node_heap.pop();
0172
0173     // debug:
0174     // node_heap.print_data_container();
0175
0176     mark[cur_node] = white;
0177     if (cur_node == t)
0178     {
0179         // if @a t is set through #target we are ready
0180         return GTL_OK;
0181     }
0182
0183     node::adj_edges_iterator adj_edge_it;
0184     node::adj_edges_iterator adj_edges_end = cur_node.adj_edges_end();
0185     for (adj_edge_it = cur_node.adj_edges_begin();
0186          adj_edge_it != adj_edges_end;
0187          ++adj_edge_it)
0188     {
0189         node op_node = (*adj_edge_it).opposite(cur_node);
0190         if (mark[op_node] == black)
0191         {
0192         mark[op_node] = grey;
0193         dist[op_node] = dist[cur_node] + weight[*adj_edge_it];
0194         node_heap.push(op_node);
0195
0196         // debug:
0197         // node_heap.print_data_container();
0198
0199         if (preds_set)
0200         {
0201             pred[op_node] = *adj_edge_it;
0202         }
0203         }
0204         else if (mark[op_node] == grey)
0205         {
0206         if (dist[op_node] > dist[cur_node] + weight[*adj_edge_it])
0207         {
0208             dist[op_node] = dist[cur_node] + weight[*adj_edge_it];
0209             node_heap.changeKey(op_node);
0210
0211             // debug:
0212             // node_heap.print_data_container();
0213
0214             if (preds_set)
0215             {
0216             pred[op_node] = *adj_edge_it;
0217             }
0218         }
0219             }
0220         else    // (mark[op_node] == white)
0221         {
0222         // nothing to do: shortest distance to op_node is already
0223         //        computed
0224         }
0225     }
0226     }
0227
0228     return GTL_OK;
0229 }
0230
0231
0232 node dijkstra::source() const
0233 {
0234     return s;
0235 }
0236
0237
0238 node dijkstra::target() const
0239 {
0240     return t;
0241 }
0242
0243
0244 bool dijkstra::store_preds() const
0245 {
0246     return preds_set;
0247 }
0248
0249
0250 bool dijkstra::reached(const node& n) const
0251 {
0252     return mark[n] != black;
0253 }
0254
0255
0256 double dijkstra::distance(const node& n) const
0257 {
0258     return dist[n];
0259 }
0260
0261
0262 node dijkstra::predecessor_node(const node& n) const
0263 {
0264     assert(preds_set);
0265     if ((n == s) || (!reached(n)))
0266     {
0267     return node();
0268     }
0269     return pred[n].opposite(n);
0270 }
0271
0272
0273 edge dijkstra::predecessor_edge(const node& n) const
0274 {
0275     assert(preds_set);
0276     return pred[n];
0277 }
0278
0279
0280 dijkstra::shortest_path_node_iterator dijkstra::shortest_path_nodes_begin(
0281     const node& dest)
0282 {
0283     assert(preds_set);
0284     if ((shortest_path_node_list[dest].empty()) &&
0285     (dest != s) &&
0286     (reached(dest)))
0287     {
0288     fill_node_list(dest);
0289     }
0290     return shortest_path_node_list[dest].begin();
0291 }
0292
0293
0294 dijkstra::shortest_path_node_iterator dijkstra::shortest_path_nodes_end(
0295     const node& dest)
0296 {
0297     assert(preds_set);
0298     if ((shortest_path_node_list[dest].empty()) &&
0299     (dest != s) &&
0300     (reached(dest)))
0301     {
0302     fill_node_list(dest);
0303     }
0304     return shortest_path_node_list[dest].end();
0305 }
0306
0307
0308 dijkstra::shortest_path_edge_iterator dijkstra::shortest_path_edges_begin(
0309     const node& dest)
0310 {
0311     assert(preds_set);
0312     if ((shortest_path_edge_list[dest].empty()) &&
0313     (dest != s) &&
0314     (reached(dest)))
0315     {
0316     fill_edge_list(dest);
0317     }
0318     return shortest_path_edge_list[dest].begin();
0319 }
0320
0321
0322 dijkstra::shortest_path_edge_iterator dijkstra::shortest_path_edges_end(
0323     const node& dest)
0324 {
0325     assert(preds_set);
0326     if ((shortest_path_edge_list[dest].empty()) &&
0327     (dest != s) &&
0328     (reached(dest)))
0329     {
0330     fill_edge_list(dest);
0331     }
0332     return shortest_path_edge_list[dest].end();
0333 }
0334
0335
0336 void dijkstra::reset()
0337 {
0338     reset_algorithm();
0339 }
0340
0341
0342 void dijkstra::reset_algorithm()
0343 {
0344     s = node();
0345     t = node();
0346     weights_set = false;
0347     preds_set = false;
0348 }
0349
0350
0351 void dijkstra::init(graph& G)
0352 {
0353     dist.init(G, -1.0);
0354     mark.init(G, black);
0355
0356     if (preds_set)
0357     {
0358     pred.init(G, edge());
0359     graph::node_iterator node_it;
0360     graph::node_iterator nodes_end = G.nodes_end();
0361     for (node_it = G.nodes_begin(); node_it != nodes_end; ++node_it)
0362     {
0363         shortest_path_node_list[(*node_it)].clear();
0364         shortest_path_edge_list[(*node_it)].clear();
0365     }
0366     }
0367 }
0368
0369
0370 void dijkstra::fill_node_list(const node& dest)
0371 {
0372     if ((dest == s) || (!reached(dest)))
0373     {
0374     return;
0375     }
0376
0377     node cur_node = dest;
0378     while (cur_node != node())
0379     {
0380     shortest_path_node_list[dest].push_front(cur_node);
0381     cur_node = predecessor_node(cur_node);
0382     }
0383 }
0384
0385
0386 void dijkstra::fill_edge_list(const node& dest)
0387 {
0388     if ((dest == s) || (!reached(dest)))
0389     {
0390     return;
0391     }
0392
0393     node cur_node = dest;
0394     edge cur_edge = predecessor_edge(dest);
0395     while (cur_edge != edge())
0396     {
0397     shortest_path_edge_list[dest].push_front(cur_edge);
0398     cur_node = predecessor_node(cur_node);
0399     cur_edge = predecessor_edge(cur_node);
0400     }
0401 }
0402
0403 __GTL_END_NAMESPACE
0404
0405 //--------------------------------------------------------------------------
0406 //   end of file
0407 //--------------------------------------------------------------------------