X-Git-Url: https://git.ozlabs.org/?a=blobdiff_plain;f=ccan%2Fagar%2Fagar.h;h=abd11301e6f86abafabfdd5563e5ae9f4b67ddb8;hb=578c4bfb22dd2df3c8133066b28397725b76734a;hp=495ef7c3bdf548b354234e365c9d7b50bd0b5ead;hpb=c2966d1879c825cfaf0e7d6848a5da052ee4a038;p=ccan

diff --git a/ccan/agar/agar.h b/ccan/agar/agar.h
index 495ef7c3..abd11301 100644
--- a/ccan/agar/agar.h
+++ b/ccan/agar/agar.h
@@ -9,6 +9,7 @@
 
 struct agar_edge_info {
 	const void *to;
+	aga_icost_t icost; /* integer edge cost */
 };
 
 struct agar_graph;
@@ -30,6 +31,9 @@ struct agar_graph {
 	agar_next_edge_fn next_edge;
 };
 
+#define AGAR_INIT_GRAPH(fe, ne, ei) \
+	{ (ei), (fe), (ne), }
+
 void agar_init_graph(struct agar_graph *gr,
 		     agar_first_edge_fn first_edge,
 		     agar_next_edge_fn next_edge,
@@ -70,4 +74,16 @@ bool agar_bfs_explore(struct agar_state *sr, const void *nr,
 #define agar_bfs(_nr, _sr, _startr)					\
 	for ((_nr) = (_startr); agar_bfs_explore((_sr), (_nr), &(_nr)); )
 
+/*
+ * Dijkstra's algorithm
+ */
+
+struct agar_state *agar_dijkstra_new(void *ctx, struct agar_graph *gr,
+				     const void *nr);
+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);
+
 #endif /* CCAN_AGAR_H */