aga,agar: Rename aga_dijkstra_all_paths()
authorDavid Gibson <david@gibson.dropbear.id.au>
Sat, 11 Jun 2016 03:10:58 +0000 (13:10 +1000)
committerDavid Gibson <david@gibson.dropbear.id.au>
Fri, 4 Nov 2016 12:38:47 +0000 (23:38 +1100)
aga_dijkstra_all_paths() runs Dijkstra's algorithm to completion (as
opposed to aga_dijkstra_path(), which operates lazily).  In effect this
computes the shortest path to all (reachable) nodes from the start node.

So, in this context the name makes sense.  But for an analogous function
for future algorithms (e.g. Bellman-Ford), the name doesn't make sense.

So, in the interests of consistency with those future extensions, change
the name of this to aga_dijkstra_complete().

Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
ccan/aga/aga.h
ccan/aga/dijkstra.c
ccan/aga/test/api-dijkstra.c
ccan/agar/agar.c
ccan/agar/agar.h
ccan/agar/test/api-dijkstra.c

index e9bd1dbc601875a6c23fe765ca4a126dc597a299..aa60bcc96a4404bd518b4d82120e7bc9f48e4db3 100644 (file)
@@ -416,15 +416,15 @@ bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *dest,
                       struct aga_node **prev, const void **prevedge);
 
 /**
- * aga_dijkstra_all_paths - Find shortest paths to all reachable nodes
+ * aga_dijkstra_complete - Find shortest paths to all reachable nodes
  * @g: graph
  *
  * Finds shortest paths from the source node (specified in
  * aga_dijkstra_start()) to all other reachable nodes in @g.  No
  * results are returned directly, but between calling
- * aga_dijkstra_all_paths() and aga_finish, aga_dijkstra_path() is
+ * aga_dijkstra_all_paths() and aga_finish(), aga_dijkstra_path() is
  * guaranteed to complete in O(1) time for all destinations.
  */
-void aga_dijkstra_all_paths(struct aga_graph *g);
+void aga_dijkstra_complete(struct aga_graph *g);
 
 #endif /* CCAN_AGA_H */
index 02177fb8415a82cf1d3095792484c898d70558bb..cbb79b90779596c6f7c56e0cae18ebee107aeb7b 100644 (file)
@@ -114,7 +114,7 @@ bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *node,
        return true;
 }
 
-void aga_dijkstra_all_paths(struct aga_graph *g)
+void aga_dijkstra_complete(struct aga_graph *g)
 {
        if (!aga_check_state(g))
                return;
index f9b8d764a7d6e198d23797afa404882b0009e8d6..74875fbc88f7de672acfb9be7a1cf6ea9e3f7eba 100644 (file)
@@ -241,7 +241,7 @@ static void test_shortcut2(void)
        shortcut2_graph_init(&s2g);
 
        ok1(aga_dijkstra_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0);
-       aga_dijkstra_all_paths(&s2g.sg.g);
+       aga_dijkstra_complete(&s2g.sg.g);
        ok1(aga_error(&s2g.sg.g) == AGA_ERR_NEGATIVE_COST);
        aga_finish(&s2g.sg.g);
 }
index e930d7aa6c7eeabde50110474502b087b78f05ae..0ee34e9ab94c63cd7c765870c43dd85531a44115 100644 (file)
@@ -286,8 +286,8 @@ bool agar_dijkstra_path(struct agar_state *sr, const void *destr,
        return true;
 }
 
-void agar_dijkstra_all_paths(struct agar_state *sr)
+void agar_dijkstra_complete(struct agar_state *sr)
 {
-       aga_dijkstra_all_paths(&sr->g);
+       aga_dijkstra_complete(&sr->g);
 }
 
index abd11301e6f86abafabfdd5563e5ae9f4b67ddb8..274c9cc1f9a308136bfd982612c519c0412a0d91 100644 (file)
@@ -84,6 +84,6 @@ bool agar_dijkstra_step(struct agar_state *sr, const void **nextr);
 bool agar_dijkstra_path(struct agar_state *sr, const void *destr,
                        aga_icost_t *total_cost,
                        const void **prevr, const void **prevedge);
-void agar_dijkstra_all_paths(struct agar_state *sr);
+void agar_dijkstra_complete(struct agar_state *sr);
 
 #endif /* CCAN_AGAR_H */
index ebdbf42d1a72d1a180c1441205e448d349943f7d..a5de2ea6b31b9e4074d871749293be4405151408 100644 (file)
@@ -231,7 +231,7 @@ static void test_shortcut2(void)
        struct agar_state *sr;
 
        ok1(sr = agar_dijkstra_new(NULL, &shortcut2_graphr.gr, int2ptr(1)));
-       agar_dijkstra_all_paths(sr);
+       agar_dijkstra_complete(sr);
        ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
        tal_free(sr);
 }