Logo AND Algorithmique Numérique Distribuée

Public GIT Repository
Dijkstra is so ugly, I could spend weeks cleaning it up
[simgrid.git] / src / kernel / routing / DijkstraZone.cpp
1 /* Copyright (c) 2009-2018. The SimGrid Team. All rights reserved.          */
2
3 /* This program is free software; you can redistribute it and/or modify it
4  * under the terms of the license (GNU LGPL) which comes with this package. */
5
6 #include "simgrid/kernel/routing/DijkstraZone.hpp"
7 #include "simgrid/kernel/routing/NetPoint.hpp"
8 #include "src/surf/network_interface.hpp"
9 #include "src/surf/xml/platf_private.hpp"
10 #include "surf/surf.hpp"
11
12 #include <cfloat>
13 #include <queue>
14 #include <vector>
15
16 XBT_LOG_NEW_DEFAULT_SUBCATEGORY(surf_route_dijkstra, surf, "Routing part of surf -- dijkstra routing logic");
17
18 namespace simgrid {
19 namespace kernel {
20 namespace routing {
21
22 class GraphNodeData {
23 public:
24   GraphNodeData(int id) : id_(id) {}
25   int id_;
26   int graph_id_ = -1; /* used for caching internal graph id's */
27 };
28
29 DijkstraZone::DijkstraZone(NetZoneImpl* father, std::string name, bool cached)
30     : RoutedZone(father, name), cached_(cached)
31 {
32 }
33
34 static void graph_node_data_free(void* n)
35 {
36   delete static_cast<simgrid::kernel::routing::GraphNodeData*>(n);
37 }
38
39 static void graph_edge_data_free(void* e)
40 {
41   delete static_cast<simgrid::kernel::routing::RouteCreationArgs*>(e);
42 }
43
44 DijkstraZone::~DijkstraZone()
45 {
46   xbt_graph_free_graph(route_graph_, &graph_node_data_free, &graph_edge_data_free, nullptr);
47 }
48
49 void DijkstraZone::seal()
50 {
51   unsigned int cursor;
52   xbt_node_t node = nullptr;
53
54   if (not route_graph_)
55     route_graph_ = xbt_graph_new_graph(1, nullptr);
56
57   /* Add the loopback if needed */
58   if (surf_network_model->loopback_ && hierarchy_ == RoutingMode::base) {
59
60     xbt_dynar_foreach (xbt_graph_get_nodes(route_graph_), cursor, node) {
61       bool found = false;
62       xbt_edge_t edge = nullptr;
63       unsigned int cursor2;
64       xbt_dynar_foreach (xbt_graph_node_get_outedges(node), cursor2, edge) {
65         if (xbt_graph_edge_get_target(edge) == node) { // There is an edge from node to itself
66           found = true;
67           break;
68         }
69       }
70
71       if (not found) {
72         RouteCreationArgs* e_route = new simgrid::kernel::routing::RouteCreationArgs();
73         e_route->link_list.push_back(surf_network_model->loopback_);
74         xbt_graph_new_edge(route_graph_, node, node, e_route);
75       }
76     }
77   }
78
79   /* initialize graph indexes in nodes after graph has been built */
80   xbt_dynar_t nodes = xbt_graph_get_nodes(route_graph_);
81
82   xbt_dynar_foreach (nodes, cursor, node) {
83     GraphNodeData* data = static_cast<GraphNodeData*>(xbt_graph_node_get_data(node));
84     data->graph_id_     = cursor;
85   }
86 }
87
88 xbt_node_t DijkstraZone::route_graph_new_node(int id)
89 {
90   xbt_node_t node = xbt_graph_new_node(route_graph_, new GraphNodeData(id));
91   graph_node_map_.emplace(id, node);
92
93   return node;
94 }
95
96 xbt_node_t DijkstraZone::node_map_search(int id)
97 {
98   auto ret = graph_node_map_.find(id);
99   return ret == graph_node_map_.end() ? nullptr : ret->second;
100 }
101
102 /* Parsing */
103
104 void DijkstraZone::get_local_route(NetPoint* src, NetPoint* dst, RouteCreationArgs* route, double* lat)
105 {
106   get_route_check_params(src, dst);
107   int src_id = src->id();
108   int dst_id = dst->id();
109
110   xbt_dynar_t nodes = xbt_graph_get_nodes(route_graph_);
111
112   /* Use the graph_node id mapping set to quickly find the nodes */
113   xbt_node_t src_elm = node_map_search(src_id);
114   xbt_node_t dst_elm = node_map_search(dst_id);
115
116   int src_node_id = static_cast<GraphNodeData*>(xbt_graph_node_get_data(src_elm))->graph_id_;
117   int dst_node_id = static_cast<GraphNodeData*>(xbt_graph_node_get_data(dst_elm))->graph_id_;
118
119   /* if the src and dst are the same */
120   if (src_node_id == dst_node_id) {
121
122     xbt_node_t node_s_v = xbt_dynar_get_as(nodes, src_node_id, xbt_node_t);
123     xbt_node_t node_e_v = xbt_dynar_get_as(nodes, dst_node_id, xbt_node_t);
124     xbt_edge_t edge     = xbt_graph_get_edge(route_graph_, node_s_v, node_e_v);
125
126     if (edge == nullptr)
127       THROWF(arg_error, 0, "No route from '%s' to '%s'", src->get_cname(), dst->get_cname());
128
129     RouteCreationArgs* e_route = static_cast<RouteCreationArgs*>(xbt_graph_edge_get_data(edge));
130
131     for (auto const& link : e_route->link_list) {
132       route->link_list.insert(route->link_list.begin(), link);
133       if (lat)
134         *lat += static_cast<resource::LinkImpl*>(link)->get_latency();
135     }
136   }
137
138   auto elm                   = route_cache_.emplace(src_id, std::vector<int>());
139   std::vector<int>& pred_arr = elm.first->second;
140
141   if (elm.second) { /* new element was inserted (not cached mode, or cache miss) */
142     int nr_nodes      = xbt_dynar_length(nodes);
143     std::vector<double> cost_arr(nr_nodes); /* link cost from src to other hosts */
144     pred_arr.resize(nr_nodes);              /* predecessors in path from src */
145     typedef std::pair<double, int> Qelt;
146     std::priority_queue<Qelt, std::vector<Qelt>, std::greater<Qelt>> pqueue;
147
148     /* initialize */
149     cost_arr[src_node_id] = 0.0;
150
151     for (int i = 0; i < nr_nodes; i++) {
152       if (i != src_node_id) {
153         cost_arr[i] = DBL_MAX;
154       }
155
156       pred_arr[i] = 0;
157
158       /* initialize priority queue */
159       pqueue.emplace(cost_arr[i], i);
160     }
161
162     /* apply dijkstra using the indexes from the graph's node array */
163     while (not pqueue.empty()) {
164       int v_id = pqueue.top().second;
165       pqueue.pop();
166       xbt_node_t v_node = xbt_dynar_get_as(nodes, v_id, xbt_node_t);
167       xbt_edge_t edge   = nullptr;
168       unsigned int cursor;
169
170       xbt_dynar_foreach (xbt_graph_node_get_outedges(v_node), cursor, edge) {
171         xbt_node_t u_node                  = xbt_graph_edge_get_target(edge);
172         GraphNodeData* data                = static_cast<GraphNodeData*>(xbt_graph_node_get_data(u_node));
173         int u_id                           = data->graph_id_;
174         RouteCreationArgs* tmp_e_route     = static_cast<RouteCreationArgs*>(xbt_graph_edge_get_data(edge));
175         int cost_v_u                       = tmp_e_route->link_list.size(); /* count of links, old model assume 1 */
176
177         if (cost_v_u + cost_arr[v_id] < cost_arr[u_id]) {
178           pred_arr[u_id] = v_id;
179           cost_arr[u_id] = cost_v_u + cost_arr[v_id];
180           pqueue.emplace(cost_arr[u_id], u_id);
181         }
182       }
183     }
184   }
185
186   /* compose route path with links */
187   NetPoint* gw_src   = nullptr;
188   NetPoint* first_gw = nullptr;
189
190   for (int v = dst_node_id; v != src_node_id; v = pred_arr[v]) {
191     xbt_node_t node_pred_v = xbt_dynar_get_as(nodes, pred_arr[v], xbt_node_t);
192     xbt_node_t node_v      = xbt_dynar_get_as(nodes, v, xbt_node_t);
193     xbt_edge_t edge        = xbt_graph_get_edge(route_graph_, node_pred_v, node_v);
194
195     if (edge == nullptr)
196       THROWF(arg_error, 0, "No route from '%s' to '%s'", src->get_cname(), dst->get_cname());
197
198     RouteCreationArgs* e_route = static_cast<RouteCreationArgs*>(xbt_graph_edge_get_data(edge));
199
200     NetPoint* prev_gw_src = gw_src;
201     gw_src                = e_route->gw_src;
202     NetPoint* gw_dst      = e_route->gw_dst;
203
204     if (v == dst_node_id)
205       first_gw = gw_dst;
206
207     if (hierarchy_ == RoutingMode::recursive && v != dst_node_id && gw_dst->get_name() != prev_gw_src->get_name()) {
208       std::vector<resource::LinkImpl*> e_route_as_to_as;
209
210       NetPoint* gw_dst_net_elm      = nullptr;
211       NetPoint* prev_gw_src_net_elm = nullptr;
212       get_global_route(gw_dst_net_elm, prev_gw_src_net_elm, e_route_as_to_as, nullptr);
213       auto pos = route->link_list.begin();
214       for (auto const& link : e_route_as_to_as) {
215         route->link_list.insert(pos, link);
216         if (lat)
217           *lat += link->get_latency();
218         pos++;
219       }
220     }
221
222     for (auto const& link : e_route->link_list) {
223       route->link_list.insert(route->link_list.begin(), link);
224       if (lat)
225         *lat += static_cast<resource::LinkImpl*>(link)->get_latency();
226     }
227   }
228
229   if (hierarchy_ == RoutingMode::recursive) {
230     route->gw_src = gw_src;
231     route->gw_dst = first_gw;
232   }
233
234   if (not cached_)
235     route_cache_.clear();
236 }
237
238 void DijkstraZone::add_route(NetPoint* src, NetPoint* dst, NetPoint* gw_src, NetPoint* gw_dst,
239                              std::vector<resource::LinkImpl*>& link_list, bool symmetrical)
240 {
241   add_route_check_params(src, dst, gw_src, gw_dst, link_list, symmetrical);
242
243   if (not route_graph_)
244     route_graph_ = xbt_graph_new_graph(1, nullptr);
245
246   new_edge(src->id(), dst->id(), new_extended_route(hierarchy_, src, dst, gw_src, gw_dst, link_list, symmetrical, 1));
247
248   if (symmetrical == true)
249     new_edge(dst->id(), src->id(), new_extended_route(hierarchy_, dst, src, gw_dst, gw_src, link_list, symmetrical, 0));
250 }
251
252 void DijkstraZone::new_edge(int src_id, int dst_id, simgrid::kernel::routing::RouteCreationArgs* route)
253 {
254   XBT_DEBUG("Create Route from '%d' to '%d'", src_id, dst_id);
255
256   // Get the extremities, or create them if they don't exist yet
257   xbt_node_t src = node_map_search(src_id);
258   if (src == nullptr)
259     src = route_graph_new_node(src_id);
260
261   xbt_node_t dst = node_map_search(dst_id);
262   if (dst == nullptr)
263     dst = route_graph_new_node(dst_id);
264
265   // Make sure that this graph edge was not already added to the graph
266   if (xbt_graph_get_edge(route_graph_, src, dst) != nullptr) {
267     if (route->gw_dst == nullptr || route->gw_src == nullptr)
268       THROWF(arg_error, 0, "Route from %s to %s already exists", route->src->get_cname(), route->dst->get_cname());
269     else
270       THROWF(arg_error, 0, "Route from %s@%s to %s@%s already exists", route->src->get_cname(),
271              route->gw_src->get_cname(), route->dst->get_cname(), route->gw_dst->get_cname());
272   }
273
274   // Finally add it
275   xbt_graph_new_edge(route_graph_, src, dst, route);
276 }
277 }
278 }
279 } // namespace