Průvodce: More styling

[leo.git] / graph.c

diff --git a/graph.c b/graph.c
index 47b4b3dca4e2b616b91aa8ae6dcdb440848f69a6..b7eeabf73f7a92c6e3711ebd9fe6ac71089611c8 100644 (file)
--- a/graph.c
+++ b/graph.c
@@ -18,7 +18,7 @@
 #include "map.h"
 #include "graph.h"
 
-static uint bidir;
+static uint bidir;     // 0=unidir, 1=bidir balanced by #opened, 2=bidir balanced by distance
 static uint astar;
 
 static struct cf_section graph_cf = {
@@ -256,13 +256,18 @@ static void bidir_dijkstra(struct graph_vertex *v_src, struct graph_vertex *v_de
   v_dest->state[1] = 1;
   v_dest->dist[1] = 0;
 
-  uint open[2] = { 1, 1 };
+  uint opened[2] = { 1, 1 }, closed[2] = { 0, 0 };
+  double last_dist[2] = { 0, 0 };
   struct graph_vertex *w;
 
   for (;;)
     {
       double best_d = 0;
-      uint dir = (open[0] <= open[1]) ? 0 : 1;
+      uint dir;
+      if (bidir == 2)
+       dir = (last_dist[0] <= last_dist[1]) ? 0 : 1;
+      else
+       dir = (opened[0] <= opened[1]) ? 0 : 1;
       w = NULL;
       // msg(L_DEBUG, "Dijkstra: dir=%d", dir);
 
@@ -282,6 +287,8 @@ static void bidir_dijkstra(struct graph_vertex *v_src, struct graph_vertex *v_de
        die("Path not found");
 
       // msg(L_DEBUG, "Dijkstra: closing vertex #%jd (d=%f, dir %d)", w->node->o.id, best_d, dir);
+      closed[dir]++;
+      last_dist[dir] = best_d;
 
       w->state[dir] = 2;
       if (w->state[!dir] == 2)
@@ -299,7 +306,7 @@ static void bidir_dijkstra(struct graph_vertex *v_src, struct graph_vertex *v_de
              x->state[dir] = 1;
              x->dist[dir] = d;
              x->via_edge[dir] = e;
-             open[dir]++;
+             opened[dir]++;
            }
        }
     }
@@ -333,6 +340,7 @@ static void bidir_dijkstra(struct graph_vertex *v_src, struct graph_vertex *v_de
       w = ev;
     }
 
+  msg(L_DEBUG, "Dijkstra: Stats: %u/%u opened, %u/%u closed", opened[0], opened[1], closed[0], closed[1]);
   visualize_states(v_src, v_dest);
   visualize_path(w, 0);
   visualize_path(w, 1);
@@ -345,10 +353,13 @@ static void dijkstra(struct graph_vertex *v_src, struct graph_vertex *v_dest)
   v_src->state[0] = 1;
   v_src->dist[0] = 0;
 
+  uint opened = 1, closed = 0;
+  struct graph_vertex *w;
+
   for (;;)
     {
-      struct graph_vertex *w = NULL;
       double best_d = 0;
+      w = NULL;
 
       CLIST_FOR_EACH(struct graph_vertex *, v, graph_vertices)
        if (v->state[0] == 1)
@@ -364,14 +375,10 @@ static void dijkstra(struct graph_vertex *v_src, struct graph_vertex *v_dest)
        die("Path not found");
 
       // msg(L_DEBUG, "Dijkstra: closing vertex #%jd", w->node->o.id);
+      closed++;
 
       if (w == v_dest)
-       {
-         msg(L_INFO, "Found path: dist=%f", w->dist[0]);
-         visualize_states(v_src, v_dest);
-         visualize_path(v_dest, 0);
-         return;
-       }
+       break;
 
       w->state[0] = 2;
       CLIST_FOR_EACH(struct graph_edge *, e, w->edges)
@@ -386,9 +393,15 @@ static void dijkstra(struct graph_vertex *v_src, struct graph_vertex *v_dest)
              x->state[0] = 1;
              x->dist[0] = d;
              x->via_edge[0] = e;
+             opened++;
            }
        }
     }
+
+  msg(L_INFO, "Dijkstra: Found path: dist=%f", w->dist[0]);
+  msg(L_INFO, "Dijkstra: Stats: %u opened, %u closed", opened, closed);
+  visualize_states(v_src, v_dest);
+  visualize_path(v_dest, 0);
 }
 
 void graph_build(void)
@@ -418,8 +431,8 @@ void graph_build(void)
   struct graph_vertex *v1 = graph_vertex_by_node_id(96745573); // Beroun, Lidická x Pražská
   // struct graph_vertex *v2 = graph_vertex_by_node_id(21289321);      // Brno, Heršpická x Opuštěná
   // struct graph_vertex *v2 = graph_vertex_by_node_id(271385400);     // Znojmo, Vídeňská třída x Brněnská
-  // struct graph_vertex *v2 = graph_vertex_by_node_id(26753344);      // Šumperk, Jesenická x Lidická
-  struct graph_vertex *v2 = graph_vertex_by_node_id(714908910);        // Ostrava, Mariánskohorská x Plzeňská x 28. října
+  struct graph_vertex *v2 = graph_vertex_by_node_id(26753344); // Šumperk, Jesenická x Lidická
+  // struct graph_vertex *v2 = graph_vertex_by_node_id(714908910);     // Ostrava, Mariánskohorská x Plzeňská x 28. října
   ASSERT(graph_degree(v1) && graph_degree(v2));
 
   if (bidir)