* [PATCH 1/5] aga,agar: Add edge costs
2015-11-12 11:42 [PATCH 0/5] aga,agar: Dijkstra's algorithm David Gibson
@ 2015-11-12 11:42 ` David Gibson
2015-11-12 11:42 ` [PATCH 2/5] aga,agar: Dijkstra's algorithm David Gibson
` (4 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: David Gibson @ 2015-11-12 11:42 UTC (permalink / raw)
To: ccan
This allows the edge_info callback to supply a cost or length for an edge.
For now we only support 'long' valued costs. If the callback doesn't
supply a cost, it's considered cost 1.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
ccan/aga/aga.c | 1 +
ccan/aga/aga.h | 8 ++++++++
ccan/agar/agar.c | 4 ++++
ccan/agar/agar.h | 1 +
4 files changed, 14 insertions(+)
diff --git a/ccan/aga/aga.c b/ccan/aga/aga.c
index c721b14..a6e0539 100644
--- a/ccan/aga/aga.c
+++ b/ccan/aga/aga.c
@@ -93,6 +93,7 @@ int aga_edge_info(const struct aga_graph *g, const struct aga_node *n,
int rc;
ei->to = NULL;
+ ei->icost = 1;
rc = g->edge_info(g, n, e, ei);
assert(rc <= 0);
return rc;
diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
index 8675150..a8a888b 100644
--- a/ccan/aga/aga.h
+++ b/ccan/aga/aga.h
@@ -72,6 +72,10 @@
* reference to that node by the edge callback for *any* node and
* index MUST use the same pointer.
*
+ * - The ei->icost field MAY be set by the edge_info callback to
+ * indicate the edge's cost / length represented as an integer (of
+ * type aga_icost_t), Otherwise the cost defaults to 1.
+ *
* Concurrency
* ===========
*
@@ -127,9 +131,13 @@ typedef const void *(*aga_next_edge_fn)(const struct aga_graph *g,
const struct aga_node *n,
const void *e);
+typedef long aga_icost_t;
+
struct aga_edge_info {
struct aga_node *to;
+ aga_icost_t icost; /* integer edge cost */
};
+
typedef int (*aga_edge_info_fn)(const struct aga_graph *g,
const struct aga_node *n,
const void *e, struct aga_edge_info *ei);
diff --git a/ccan/agar/agar.c b/ccan/agar/agar.c
index b2809ab..2be9daf 100644
--- a/ccan/agar/agar.c
+++ b/ccan/agar/agar.c
@@ -79,6 +79,7 @@ static int convert_edge_info(const struct aga_graph *g,
int rc;
eir.to = NULL;
+ eir.icost = ei->icost; /* Inherit the default from aga */
rc = sr->gr->edge_info(sr->gr, nr, e, &eir);
@@ -87,6 +88,8 @@ static int convert_edge_info(const struct aga_graph *g,
else
ei->to = NULL;
+ ei->icost = eir.icost;
+
return rc;
}
@@ -164,6 +167,7 @@ int agar_edge_info(const struct agar_graph *gr, const void *nr, const void *e,
int rc;
eir->to = NULL;
+ eir->icost = 1;
rc = gr->edge_info(gr, nr, e, eir);
assert(rc <= 0);
return rc;
diff --git a/ccan/agar/agar.h b/ccan/agar/agar.h
index 495ef7c..d63615a 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;
--
2.5.0
_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 2/5] aga,agar: Dijkstra's algorithm
2015-11-12 11:42 [PATCH 0/5] aga,agar: Dijkstra's algorithm David Gibson
2015-11-12 11:42 ` [PATCH 1/5] aga,agar: Add edge costs David Gibson
@ 2015-11-12 11:42 ` David Gibson
2015-11-12 21:59 ` Emilio G. Cota
2015-11-12 11:42 ` [PATCH 3/5] aga, agar: Non-equal edge costs for parallel test graph David Gibson
` (3 subsequent siblings)
5 siblings, 1 reply; 9+ messages in thread
From: David Gibson @ 2015-11-12 11:42 UTC (permalink / raw)
To: ccan
Implement Dijkstra's algorithm for one-source shortest-path.
This uses the lpq module as the implementation of the priority queue. That
means this implementation is some way behind the theoretical efficiency of
Dijkstra's algorithm. It should be reasonably straightforward to swap out
the priority queue for a better one in the future, though.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
ccan/aga/_info | 2 +
ccan/aga/aga.h | 86 ++++++++++++++++
ccan/aga/dijkstra.c | 131 ++++++++++++++++++++++++
ccan/aga/test/api-dijkstra.c | 222 ++++++++++++++++++++++++++++++++++++++++
ccan/agar/agar.c | 57 +++++++++++
ccan/agar/agar.h | 12 +++
ccan/agar/test/api-dijkstra.c | 229 ++++++++++++++++++++++++++++++++++++++++++
7 files changed, 739 insertions(+)
create mode 100644 ccan/aga/dijkstra.c
create mode 100644 ccan/aga/test/api-dijkstra.c
create mode 100644 ccan/agar/test/api-dijkstra.c
diff --git a/ccan/aga/_info b/ccan/aga/_info
index fa5e8fe..f65a1c3 100644
--- a/ccan/aga/_info
+++ b/ccan/aga/_info
@@ -33,6 +33,8 @@ int main(int argc, char *argv[])
printf("ccan/check_type\n");
printf("ccan/lstack\n");
printf("ccan/lqueue\n");
+ printf("ccan/order\n");
+ printf("ccan/lpq\n");
return 0;
}
diff --git a/ccan/aga/aga.h b/ccan/aga/aga.h
index a8a888b..d09d4c7 100644
--- a/ccan/aga/aga.h
+++ b/ccan/aga/aga.h
@@ -118,6 +118,7 @@
#include <ccan/check_type/check_type.h>
#include <ccan/lstack/lstack.h>
#include <ccan/lqueue/lqueue.h>
+#include <ccan/lpq/lpq.h>
struct aga_graph;
struct aga_node;
@@ -157,6 +158,13 @@ struct aga_node {
struct lqueue_link next;
const void *edge;
} bfs;
+ struct {
+ aga_icost_t distance;
+ struct aga_node *prev;
+ const void *prevedge;
+ bool complete;
+ struct lpq_link pqlink;
+ } dijkstra;
} u;
};
@@ -167,6 +175,9 @@ struct aga_graph {
aga_first_edge_fn first_edge;
aga_next_edge_fn next_edge;
aga_edge_info_fn edge_info;
+ union {
+ LPQ(struct aga_node, u.dijkstra.pqlink) dijkstra;
+ } state;
};
/*
@@ -213,6 +224,8 @@ void aga_init_graph_(struct aga_graph *g,
enum aga_error {
/* No error */
AGA_ERR_NONE = 0,
+ /* Negative edge cost (in a context where it's not valid) */
+ AGA_ERR_NEGATIVE_COST = 1,
};
/**
@@ -341,4 +354,77 @@ struct aga_node *aga_bfs_explore(struct aga_graph *g, struct aga_node *n);
#define aga_bfs(_n, _g, _start) \
for ((_n) = (_start) ; ((_n) = aga_bfs_explore((_g), (_n))) != NULL; )
+/*
+ * Dijkstra's algorithm
+ */
+
+/**
+ * aga_dijkstra_start - Start Dijkstra's algorithm
+ * @g: graph
+ * @source: source node
+ *
+ * Start's Dijkstra's algorithm on @g to find shortest paths from node
+ * @source, to other nodes in @g.
+ */
+int aga_dijkstra_start(struct aga_graph *g, struct aga_node *source);
+
+
+/**
+ * aga_dijkstra_step - Find the node with the next shortest path
+ * @g: graph
+ *
+ * The first call to this function returns the source node specified
+ * in aga_dijkstra_start(). Subsequent calls return the next closest
+ * node to source by shortest path cost. Returns NULL if no further
+ * nodes are reachable from source.
+ */
+struct aga_node *aga_dijkstra_step(struct aga_graph *g);
+
+/**
+ * aga_dijkstra_path - Find the shortest path to a node
+ * @g: graph
+ * @dest: destination node
+ * @prev: Second last node in the path *output)
+ * @prevedge: Last edge in the path
+ *
+ * Finds the shortest path from the source node (specified in
+ * aga_dijkstra_start() to @dest using Dijkstra's algorithm.
+ *
+ * If no path exists, return false.
+ *
+ * If a path does exist, returns true. Additionally if @total_cost is
+ * non-NULL, store the total cost of the path in *@total_cost, if
+ * @prev is non-NULL, store the node in the path immediately before
+ * @dest in *@prev and if @prevedge is non-NULL stores the edge which
+ * leads from *@prev to @dest in *@prevedge.
+ *
+ * If @dest is the same as source, 0 will be stored in @cost, and NULL
+ * will be stored in *@prev and *@prevedge.
+ *
+ * The full path from source to @dest can be determined by repeatedly
+ * calling aga_dijkstra_path() on *@prev.
+ *
+ * NOTE: Dijkstra's algorithm will not work correctly on a graph which
+ * has negative costs on some edges. If aga detects this case, it
+ * will set aga_error() to AGA_ERR_NEGATIVE_COST. However,
+ * aga_dijkstra_path() may produce incorrect results without detecting
+ * this situation. aga_dijkstra_all_paths() *is* guaranteed to
+ * discover any negative cost edge reachable from the starting node.
+ */
+bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *dest,
+ aga_icost_t *total_cost,
+ struct aga_node **prev, const void **prevedge);
+
+/**
+ * aga_dijkstra_all_paths - 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
+ * guaranteed to complete in O(1) time for all destinations.
+ */
+void aga_dijkstra_all_paths(struct aga_graph *g);
+
#endif /* CCAN_AGA_H */
diff --git a/ccan/aga/dijkstra.c b/ccan/aga/dijkstra.c
new file mode 100644
index 0000000..97b485f
--- /dev/null
+++ b/ccan/aga/dijkstra.c
@@ -0,0 +1,131 @@
+/* Licensed under LGPLv2+ - see LICENSE file for details */
+#include "config.h"
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <assert.h>
+
+#include <ccan/build_assert/build_assert.h>
+#include <ccan/check_type/check_type.h>
+#include <ccan/order/order.h>
+#include <ccan/lpq/lpq.h>
+
+#include <ccan/aga/aga.h>
+#include "private.h"
+
+/*
+ * Dijkstra's algorithm
+ */
+
+/* Node states */
+#define STATE_INFINITE 0
+#define STATE_FINITE 1
+#define STATE_COMPLETE 2
+
+
+static void candidate_path(struct aga_graph *g, struct aga_node *node,
+ aga_icost_t distance,
+ struct aga_node *prev, const void *prevedge)
+{
+ if (aga_update_node(g, node)) {
+ /* New node, treat has having infinite distance */
+ node->u.dijkstra.distance = distance;
+ node->u.dijkstra.prev = prev;
+ node->u.dijkstra.prevedge = prevedge;
+ node->u.dijkstra.complete = false;
+
+ lpq_enqueue(&g->state.dijkstra, node);
+ } else if (distance < node->u.dijkstra.distance) {
+ assert(!node->u.dijkstra.complete);
+
+ node->u.dijkstra.distance = distance;
+ node->u.dijkstra.prev = prev;
+ node->u.dijkstra.prevedge = prevedge;
+
+ lpq_reorder(&g->state.dijkstra, node);
+ }
+}
+
+int aga_dijkstra_start(struct aga_graph *g, struct aga_node *source)
+{
+ total_order_by_field(order, long_reverse,
+ struct aga_node, u.dijkstra.distance);
+ int rc;
+
+ /* Make sure we're actually using the right ordering for
+ * aga_icost_t */
+ BUILD_ASSERT(check_types_match(long, aga_icost_t) == 0);
+
+ rc = aga_start(g);
+ if (rc < 0)
+ return rc;
+
+ lpq_init(&g->state.dijkstra, order.cb, order.ctx);
+
+ candidate_path(g, source, 0, NULL, NULL);
+
+ return 0;
+}
+
+struct aga_node *aga_dijkstra_step(struct aga_graph *g)
+{
+ struct aga_node *n = lpq_dequeue(&g->state.dijkstra);
+ const void *e;
+ struct aga_edge_info ei;
+ int err;
+
+ if (!aga_check_state(g))
+ return NULL;
+
+ if (!n)
+ return NULL;
+
+ aga_for_each_edge_info(e, ei, err, g, n) {
+ if (ei.icost < 0) {
+ aga_fail(g, AGA_ERR_NEGATIVE_COST);
+ return NULL;
+ }
+ candidate_path(g, ei.to,
+ n->u.dijkstra.distance + ei.icost, n, e);
+ }
+ if (err) {
+ aga_fail(g, err);
+ return NULL;
+ }
+
+ n->u.dijkstra.complete = true;
+
+ return n;
+}
+
+bool aga_dijkstra_path(struct aga_graph *g, struct aga_node *node,
+ aga_icost_t *total_cost,
+ struct aga_node **prev, const void **prevedge)
+{
+ if (!aga_check_state(g))
+ return false;
+
+ while (aga_node_needs_update(g, node) || !node->u.dijkstra.complete) {
+ if (!aga_dijkstra_step(g))
+ return false;
+ };
+
+ if (total_cost)
+ *total_cost = node->u.dijkstra.distance;
+ if (prev)
+ *prev = node->u.dijkstra.prev;
+ if (prevedge)
+ *prevedge = node->u.dijkstra.prevedge;
+
+ return true;
+}
+
+void aga_dijkstra_all_paths(struct aga_graph *g)
+{
+ if (!aga_check_state(g))
+ return;
+
+ while (aga_dijkstra_step(g))
+ ;
+}
+
diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
new file mode 100644
index 0000000..08b4728
--- /dev/null
+++ b/ccan/aga/test/api-dijkstra.c
@@ -0,0 +1,222 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+#include <stdlib.h>
+
+#include <ccan/tap/tap.h>
+#include <ccan/array_size/array_size.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+static void test_trivial(void)
+{
+ struct trivial_graph tg;
+ aga_icost_t cost;
+ struct aga_node *node;
+ const void *edge;
+
+ trivial_graph_init(&tg);
+
+ ok1(aga_dijkstra_start(&tg.sg.g, &tg.sg.nodes[1]) == 0);
+ ok1(aga_dijkstra_step(&tg.sg.g) == &tg.sg.nodes[1]);
+ ok1(aga_dijkstra_step(&tg.sg.g) == NULL);
+ ok1(aga_dijkstra_path(&tg.sg.g, &tg.sg.nodes[1], &cost, &node, &edge));
+ ok1(cost == 0);
+ ok1(node == NULL);
+ ok1(edge == NULL);
+ aga_finish(&tg.sg.g);
+}
+
+static void test_parallel(void)
+{
+ struct parallel_graph pg;
+ aga_icost_t cost;
+ struct aga_node *node;
+
+ parallel_graph_init(&pg, 3);
+
+ ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
+ ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[1]);
+ ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
+ ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
+ ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
+ ok1(cost == 1);
+ ok1(node == &pg.sg.nodes[1]);
+ aga_finish(&pg.sg.g);
+
+ ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[2]) == 0);
+ ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[2]);
+ ok1(aga_dijkstra_step(&pg.sg.g) == NULL);
+ ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(!aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
+ aga_finish(&pg.sg.g);
+}
+
+#define FULL_LEN 4
+
+static void test_full(void)
+{
+ struct full_graph fg;
+ int i, j;
+
+ full_graph_init(&fg, FULL_LEN);
+
+ for (i = 1; i <= FULL_LEN; i++) {
+ ok1(aga_dijkstra_start(&fg.sg.g, &fg.sg.nodes[i]) == 0);
+
+ for (j = 1; j <= FULL_LEN; j++) {
+ aga_icost_t cost;
+ struct aga_node *node;
+ const void *edge;
+
+ ok1(aga_dijkstra_path(&fg.sg.g, &fg.sg.nodes[j],
+ &cost, &node, &edge));
+ if (i == j) {
+ ok1(cost == 0);
+ ok1(node == NULL);
+ ok1(edge == NULL);
+ } else {
+ ok1(cost == 1);
+ ok1(node == &fg.sg.nodes[i]);
+ ok1(edge == &fg.sg.nodes[j]);
+ }
+ }
+
+ aga_finish(&fg.sg.g);
+ }
+}
+
+#define CHAIN_LEN 8
+
+static void test_chain(void)
+{
+ struct chain_graph cg;
+ int i, j;
+
+ chain_graph_init(&cg, CHAIN_LEN);
+
+ for (i = 1; i <= CHAIN_LEN; i++) {
+ ok1(aga_dijkstra_start(&cg.fg.sg.g, &cg.fg.sg.nodes[i]) == 0);
+
+ for (j = 1; j <= CHAIN_LEN; j++) {
+ aga_icost_t cost;
+
+ ok1(aga_dijkstra_path(&cg.fg.sg.g, &cg.fg.sg.nodes[j],
+ &cost, NULL, NULL));
+ ok1(cost == labs(i - j));
+ }
+
+ aga_finish(&cg.fg.sg.g);
+ }
+}
+
+static void test_error(void)
+{
+ struct error_graph eg;
+ aga_icost_t cost;
+
+ error_graph_init(&eg);
+
+ ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[1]) == 0);
+ ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[1], &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[2], &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
+ ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
+ aga_finish(&eg.sg.g);
+
+ ok1(aga_dijkstra_start(&eg.sg.g, &eg.sg.nodes[3]) == 0);
+ ok1(aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[3], &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(!aga_dijkstra_path(&eg.sg.g, &eg.sg.nodes[4], &cost, NULL, NULL));
+ ok1(aga_error(&eg.sg.g) == -1);
+ aga_finish(&eg.sg.g);
+}
+
+static void test_traversal1(void)
+{
+ struct traversal1_graph t1g;
+ aga_icost_t cost;
+
+ /* This is mostly about testing we correctly handle
+ * non-reachable nodes */
+ traversal1_graph_init(&t1g);
+
+ ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[1]) == 0);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
+ &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
+ &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
+ &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
+ NULL, NULL, NULL));
+ ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
+ NULL, NULL, NULL));
+ ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
+ NULL, NULL, NULL));
+ aga_finish(&t1g.sg.g);
+
+ ok1(aga_dijkstra_start(&t1g.sg.g, &t1g.sg.nodes[9]) == 0);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[9],
+ &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[8],
+ &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[7],
+ &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[6],
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[5],
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[4],
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[3],
+ NULL, NULL, NULL));
+ ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[2],
+ NULL, NULL, NULL));
+ ok1(!aga_dijkstra_path(&t1g.sg.g, &t1g.sg.nodes[1],
+ NULL, NULL, NULL));
+ aga_finish(&t1g.sg.g);
+}
+
+int main(void)
+{
+ plan_tests(7 + 15
+ + FULL_LEN * (1 + FULL_LEN*4)
+ + CHAIN_LEN * (1 + CHAIN_LEN*2)
+ + 12 + 32);
+
+ test_trivial();
+ test_parallel();
+ test_full();
+ test_chain();
+ test_error();
+ test_traversal1();
+
+ return exit_status();
+}
diff --git a/ccan/agar/agar.c b/ccan/agar/agar.c
index 2be9daf..e930d7a 100644
--- a/ccan/agar/agar.c
+++ b/ccan/agar/agar.c
@@ -234,3 +234,60 @@ bool agar_bfs_explore(struct agar_state *sr, const void *nr,
*nextr = n_to_nr(sr, next);
return true;
}
+
+/*
+ * Dijkstra's algorithm
+ */
+
+struct agar_state *agar_dijkstra_new(void *ctx, struct agar_graph *gr,
+ const void *nr)
+{
+ struct agar_state *sr = agar_new(ctx, gr);
+
+ if (aga_dijkstra_start(&sr->g, nr_to_n(sr, nr)) < 0) {
+ tal_free(sr);
+ return NULL;
+ }
+
+ return sr;
+}
+
+bool agar_dijkstra_step(struct agar_state *sr, const void **nextr)
+{
+ struct aga_node *next = aga_dijkstra_step(&sr->g);
+
+ if (!next)
+ return false;
+
+ *nextr = n_to_nr(sr, next);
+ return true;
+}
+
+bool agar_dijkstra_path(struct agar_state *sr, const void *destr,
+ aga_icost_t *total_cost,
+ const void **prevr, const void **prevedge)
+{
+ struct aga_node *dest = nr_to_n(sr, destr);
+ struct aga_node *prev;
+
+ if (!aga_dijkstra_path(&sr->g, dest, total_cost, &prev, prevedge))
+ return false;
+
+ /*
+ * When destr is the same as the source node, there obviously
+ * isn't a previous node or edge. In that case aga, sets them
+ * to NULL. But for agar, NULL could be a valid node
+ * references (particularly if using ptrint). So we don't
+ * have much choice here but to leave *prevr as undefined when
+ * destr is the source node. */
+ if (prevr && prev)
+ *prevr = n_to_nr(sr, prev);
+
+ return true;
+}
+
+void agar_dijkstra_all_paths(struct agar_state *sr)
+{
+ aga_dijkstra_all_paths(&sr->g);
+}
+
diff --git a/ccan/agar/agar.h b/ccan/agar/agar.h
index d63615a..122cb97 100644
--- a/ccan/agar/agar.h
+++ b/ccan/agar/agar.h
@@ -71,4 +71,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 */
diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
new file mode 100644
index 0000000..4b03bc6
--- /dev/null
+++ b/ccan/agar/test/api-dijkstra.c
@@ -0,0 +1,229 @@
+#include "config.h"
+
+#include <stddef.h>
+#include <assert.h>
+#include <stdlib.h>
+
+#include <ccan/tap/tap.h>
+#include <ccan/tal/tal.h>
+#include <ccan/array_size/array_size.h>
+
+#include <ccan/agar/agar.h>
+
+#include "simple-graphr.h"
+
+static void test_trivial(void)
+{
+ struct trivial_graphr tgr;
+ struct agar_state *sr;
+ aga_icost_t cost;
+ const void *node;
+
+ trivial_graphr_init(&tgr);
+
+ ok1(sr = agar_dijkstra_new(NULL, &tgr.gr, int2ptr(1)));
+ ok1(agar_dijkstra_step(sr, &node));
+ ok1(ptr2int(node) == 1);
+ ok1(!agar_dijkstra_step(sr, &node));
+ ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
+ ok1(cost == 0);
+ tal_free(sr);
+}
+
+static void test_parallel(void)
+{
+ struct parallel_graphr pgr;
+ struct agar_state *sr;
+ aga_icost_t cost;
+ const void *node;
+
+ parallel_graphr_init(&pgr, 3);
+
+ ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
+ ok1(agar_dijkstra_step(sr, &node));
+ ok1(ptr2int(node) == 1);
+ ok1(agar_dijkstra_step(sr, &node));
+ ok1(ptr2int(node) == 2);
+ ok1(!agar_dijkstra_step(sr, &node));
+ ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
+ ok1(cost == 1);
+ ok1(node == int2ptr(1));
+ tal_free(sr);
+
+ ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(2)));
+ ok1(agar_dijkstra_step(sr, &node));
+ ok1(ptr2int(node) == 2);
+ ok1(!agar_dijkstra_step(sr, &node));
+ ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(!agar_dijkstra_path(sr, int2ptr(1), NULL, NULL, NULL));
+ tal_free(sr);
+}
+
+#define FULL_LEN 4
+
+static void test_full(void)
+{
+ struct full_graphr fgr;
+ int i, j;
+
+ full_graphr_init(&fgr, FULL_LEN);
+
+ for (i = 1; i <= FULL_LEN; i++) {
+ struct agar_state *sr;
+
+ ok1(sr = agar_dijkstra_new(NULL, &fgr.gr, int2ptr(i)));
+
+ for (j = 1; j <= FULL_LEN; j++) {
+ aga_icost_t cost;
+ const void *node, *edge;
+
+ ok1(agar_dijkstra_path(sr, int2ptr(j),
+ &cost, &node, &edge));
+ if (i == j) {
+ ok1(cost == 0);
+ } else {
+ ok1(cost == 1);
+ ok1(node == int2ptr(i));
+ ok1(edge == int2ptr(j));
+ }
+ }
+
+ tal_free(sr);
+ }
+}
+
+#define CHAIN_LEN 8
+
+static void test_chain(void)
+{
+ struct chain_graphr cgr;
+ int i, j;
+
+ chain_graphr_init(&cgr, CHAIN_LEN);
+
+ for (i = 1; i <= CHAIN_LEN; i++) {
+ struct agar_state *sr;
+
+ ok1(sr = agar_dijkstra_new(NULL, &cgr.fgr.gr, int2ptr(i)));
+
+ for (j = 1; j <= CHAIN_LEN; j++) {
+ aga_icost_t cost;
+
+ ok1(agar_dijkstra_path(sr, int2ptr(j),
+ &cost, NULL, NULL));
+ ok1(cost == labs(i - j));
+ }
+
+ tal_free(sr);
+ }
+}
+
+static void test_error(void)
+{
+ struct error_graphr egr;
+ struct agar_state *sr;
+ aga_icost_t cost;
+
+ error_graphr_init(&egr);
+
+ ok1(sr = agar_dijkstra_new(NULL, &egr.gr, int2ptr(1)));
+ ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(!agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
+ ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
+ tal_free(sr);
+
+ ok1(sr = agar_dijkstra_new(NULL, &egr.gr, int2ptr(3)));
+ ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(!agar_dijkstra_path(sr, int2ptr(4), &cost, NULL, NULL));
+ ok1(agar_error(sr) == -1);
+ tal_free(sr);
+}
+
+static void test_traversal1(void)
+{
+ struct traversal1_graphr t1gr;
+ struct agar_state *sr;
+ aga_icost_t cost;
+
+ /* This is mostly about testing we correctly handle
+ * non-reachable nodes */
+ traversal1_graphr_init(&t1gr);
+
+ ok1(sr = agar_dijkstra_new(NULL, &t1gr.gr, int2ptr(1)));
+ ok1(agar_dijkstra_path(sr, int2ptr(1),
+ &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(agar_dijkstra_path(sr, int2ptr(2),
+ &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(agar_dijkstra_path(sr, int2ptr(3),
+ &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(agar_dijkstra_path(sr, int2ptr(4),
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(agar_dijkstra_path(sr, int2ptr(5),
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(agar_dijkstra_path(sr, int2ptr(6),
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(!agar_dijkstra_path(sr, int2ptr(7),
+ NULL, NULL, NULL));
+ ok1(!agar_dijkstra_path(sr, int2ptr(8),
+ NULL, NULL, NULL));
+ ok1(!agar_dijkstra_path(sr, int2ptr(9),
+ NULL, NULL, NULL));
+ tal_free(sr);
+
+ ok1(sr = agar_dijkstra_new(NULL, &t1gr.gr, int2ptr(9)));
+ ok1(agar_dijkstra_path(sr, int2ptr(9),
+ &cost, NULL, NULL));
+ ok1(cost == 0);
+ ok1(agar_dijkstra_path(sr, int2ptr(8),
+ &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(agar_dijkstra_path(sr, int2ptr(7),
+ &cost, NULL, NULL));
+ ok1(cost == 1);
+ ok1(agar_dijkstra_path(sr, int2ptr(6),
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(agar_dijkstra_path(sr, int2ptr(5),
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(agar_dijkstra_path(sr, int2ptr(4),
+ &cost, NULL, NULL));
+ ok1(cost == 2);
+ ok1(!agar_dijkstra_path(sr, int2ptr(3),
+ NULL, NULL, NULL));
+ ok1(!agar_dijkstra_path(sr, int2ptr(2),
+ NULL, NULL, NULL));
+ ok1(!agar_dijkstra_path(sr, int2ptr(1),
+ NULL, NULL, NULL));
+ tal_free(sr);
+}
+
+int main(void)
+{
+ plan_tests(6 + 18
+ + FULL_LEN * (FULL_LEN*4 - 1)
+ + CHAIN_LEN * (1 + CHAIN_LEN*2)
+ + 12 + 32);
+
+ test_trivial();
+ test_parallel();
+ test_full();
+ test_chain();
+ test_error();
+ test_traversal1();
+
+ return exit_status();
+}
--
2.5.0
_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan
^ permalink raw reply related [flat|nested] 9+ messages in thread* Re: [PATCH 2/5] aga,agar: Dijkstra's algorithm
2015-11-12 11:42 ` [PATCH 2/5] aga,agar: Dijkstra's algorithm David Gibson
@ 2015-11-12 21:59 ` Emilio G. Cota
2015-11-13 2:02 ` David Gibson
0 siblings, 1 reply; 9+ messages in thread
From: Emilio G. Cota @ 2015-11-12 21:59 UTC (permalink / raw)
To: David Gibson; +Cc: ccan
On Thu, Nov 12, 2015 at 22:42:45 +1100, David Gibson wrote:
> This uses the lpq module as the implementation of the priority queue. That
> means this implementation is some way behind the theoretical efficiency of
> Dijkstra's algorithm. It should be reasonably straightforward to swap out
> the priority queue for a better one in the future, though.
Have you considered using the heap module?
Thanks,
Emilio
_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [PATCH 2/5] aga,agar: Dijkstra's algorithm
2015-11-12 21:59 ` Emilio G. Cota
@ 2015-11-13 2:02 ` David Gibson
0 siblings, 0 replies; 9+ messages in thread
From: David Gibson @ 2015-11-13 2:02 UTC (permalink / raw)
To: Emilio G. Cota; +Cc: ccan
[-- Attachment #1.1: Type: text/plain, Size: 1116 bytes --]
On Thu, Nov 12, 2015 at 04:59:51PM -0500, Emilio G. Cota wrote:
> On Thu, Nov 12, 2015 at 22:42:45 +1100, David Gibson wrote:
> > This uses the lpq module as the implementation of the priority queue. That
> > means this implementation is some way behind the theoretical efficiency of
> > Dijkstra's algorithm. It should be reasonably straightforward to swap out
> > the priority queue for a better one in the future, though.
>
> Have you considered using the heap module?
The aga module (unlike agar) isn't supposed to allocate memory,
instead using the structures that the caller embeds in their own data
structures.
Unfortunately, that means it's not possible to use a binary heap - at
least not the usual array based implementation. You could make a link
only based implementation, but it gets so horrible that you might as
well use a better data structure (e.g. a pairing heap) at that point.
--
David Gibson | I'll have my music baroque, and my code
david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_
| _way_ _around_!
http://www.ozlabs.org/~dgibson
[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
[-- Attachment #2: Type: text/plain, Size: 127 bytes --]
_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan
^ permalink raw reply [flat|nested] 9+ messages in thread
* [PATCH 3/5] aga, agar: Non-equal edge costs for parallel test graph
2015-11-12 11:42 [PATCH 0/5] aga,agar: Dijkstra's algorithm David Gibson
2015-11-12 11:42 ` [PATCH 1/5] aga,agar: Add edge costs David Gibson
2015-11-12 11:42 ` [PATCH 2/5] aga,agar: Dijkstra's algorithm David Gibson
@ 2015-11-12 11:42 ` David Gibson
2015-11-12 11:42 ` [PATCH 4/5] aga, agar: New shortcut1 sample graph and testcases based on it David Gibson
` (2 subsequent siblings)
5 siblings, 0 replies; 9+ messages in thread
From: David Gibson @ 2015-11-12 11:42 UTC (permalink / raw)
To: ccan
At the moment the "parallel" test graph just uses the default cost of 1
for all the links between the two nodes. This patch changes that so that
the links have cost 2, except (optionally) one with cost 1. This provides
a useful test for the Dijkstra's algorithm implementation to ensure that
it picks the correct link for the shortest path.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
ccan/aga/test/api-adjacency.c | 2 +-
ccan/aga/test/api-bfs.c | 2 +-
ccan/aga/test/api-dfs.c | 2 +-
ccan/aga/test/api-dijkstra.c | 16 +++++++++++++---
ccan/aga/test/parallel.c | 7 ++++++-
ccan/aga/test/simple-graph.h | 3 ++-
ccan/agar/test/api-adjacency.c | 2 +-
ccan/agar/test/api-bfs.c | 2 +-
ccan/agar/test/api-dfs.c | 2 +-
ccan/agar/test/api-dijkstra.c | 16 ++++++++++++----
ccan/agar/test/parallel.c | 10 +++++++++-
ccan/agar/test/simple-graphr.h | 4 +++-
12 files changed, 51 insertions(+), 17 deletions(-)
diff --git a/ccan/aga/test/api-adjacency.c b/ccan/aga/test/api-adjacency.c
index 5e9bac2..2212600 100644
--- a/ccan/aga/test/api-adjacency.c
+++ b/ccan/aga/test/api-adjacency.c
@@ -67,7 +67,7 @@ int main(void)
trivial_graph_init(&tg);
test_adjacency("trivial", &tg.sg, trivial_adjacency);
- parallel_graph_init(&pg, 3);
+ parallel_graph_init(&pg, 3, 0);
test_adjacency("parallel nlinks 3", &pg.sg,
parallel_adjacency_nlinks3);
diff --git a/ccan/aga/test/api-bfs.c b/ccan/aga/test/api-bfs.c
index e59c756..90fcc62 100644
--- a/ccan/aga/test/api-bfs.c
+++ b/ccan/aga/test/api-bfs.c
@@ -49,7 +49,7 @@ int main(void)
trivial_graph_init(&tg);
test_bfs(&tg.sg, 1, 1);
- parallel_graph_init(&pg, 3);
+ parallel_graph_init(&pg, 3, 0);
test_bfs(&pg.sg, 1, 1, 2);
full_graph_init(&fg, 5);
diff --git a/ccan/aga/test/api-dfs.c b/ccan/aga/test/api-dfs.c
index 8ab1591..24d1a4f 100644
--- a/ccan/aga/test/api-dfs.c
+++ b/ccan/aga/test/api-dfs.c
@@ -49,7 +49,7 @@ int main(void)
trivial_graph_init(&tg);
test_dfs(&tg.sg, 1, 1);
- parallel_graph_init(&pg, 3);
+ parallel_graph_init(&pg, 3, 0);
test_dfs(&pg.sg, 1, 1, 2);
full_graph_init(&fg, 5);
diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
index 08b4728..9be747d 100644
--- a/ccan/aga/test/api-dijkstra.c
+++ b/ccan/aga/test/api-dijkstra.c
@@ -35,8 +35,9 @@ static void test_parallel(void)
struct parallel_graph pg;
aga_icost_t cost;
struct aga_node *node;
+ const void *edge;
- parallel_graph_init(&pg, 3);
+ parallel_graph_init(&pg, 3, 0);
ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
ok1(aga_dijkstra_step(&pg.sg.g) == &pg.sg.nodes[1]);
@@ -45,7 +46,7 @@ static void test_parallel(void)
ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], &cost, NULL, NULL));
ok1(cost == 0);
ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, NULL));
- ok1(cost == 1);
+ ok1(cost == 2);
ok1(node == &pg.sg.nodes[1]);
aga_finish(&pg.sg.g);
@@ -56,6 +57,15 @@ static void test_parallel(void)
ok1(cost == 0);
ok1(!aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[1], NULL, NULL, NULL));
aga_finish(&pg.sg.g);
+
+
+ parallel_graph_init(&pg, 3, 2);
+ ok1(aga_dijkstra_start(&pg.sg.g, &pg.sg.nodes[1]) == 0);
+ ok1(aga_dijkstra_path(&pg.sg.g, &pg.sg.nodes[2], &cost, &node, &edge));
+ ok1(cost == 1);
+ ok1(node == &pg.sg.nodes[1]);
+ ok1(ptr2int(edge) == 2);
+ aga_finish(&pg.sg.g);
}
#define FULL_LEN 4
@@ -206,7 +216,7 @@ static void test_traversal1(void)
int main(void)
{
- plan_tests(7 + 15
+ plan_tests(7 + 20
+ FULL_LEN * (1 + FULL_LEN*4)
+ CHAIN_LEN * (1 + CHAIN_LEN*2)
+ 12 + 32);
diff --git a/ccan/aga/test/parallel.c b/ccan/aga/test/parallel.c
index 997280b..bea9511 100644
--- a/ccan/aga/test/parallel.c
+++ b/ccan/aga/test/parallel.c
@@ -50,12 +50,17 @@ static int parallel_edge_info(const struct aga_graph *g, const struct aga_node *
assert(n == &pg->sg.nodes[1]);
ei->to = &pg->sg.nodes[2];
+ if (ptr2int(edge) == pg->cheaplink)
+ ei->icost = 1;
+ else
+ ei->icost = 2;
return 0;
}
-void parallel_graph_init(struct parallel_graph *pg, int nlinks)
+void parallel_graph_init(struct parallel_graph *pg, int nlinks, int cheaplink)
{
pg->nlinks = nlinks;
+ pg->cheaplink = cheaplink;
simple_graph_init(&pg->sg, parallel_first_edge, parallel_next_edge,
parallel_edge_info);
diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
index 3f4f9ac..57f87a8 100644
--- a/ccan/aga/test/simple-graph.h
+++ b/ccan/aga/test/simple-graph.h
@@ -52,9 +52,10 @@ static const struct adjacency_list trivial_adjacency[] = {
*/
struct parallel_graph {
int nlinks;
+ int cheaplink;
struct simple_graph sg;
};
-void parallel_graph_init(struct parallel_graph *pg, int nlinks);
+void parallel_graph_init(struct parallel_graph *pg, int nlinks, int cheaplink);
static const struct adjacency_list parallel_adjacency_nlinks3[] = {
{1, {2, 2, 2}},
{2, {}},
diff --git a/ccan/agar/test/api-adjacency.c b/ccan/agar/test/api-adjacency.c
index c17ead5..469cd83 100644
--- a/ccan/agar/test/api-adjacency.c
+++ b/ccan/agar/test/api-adjacency.c
@@ -61,7 +61,7 @@ int main(void)
trivial_graphr_init(&tgr);
test_adjacency("trivial", &tgr.gr, trivial_adjacencyr);
- parallel_graphr_init(&pgr, 3);
+ parallel_graphr_init(&pgr, 3, 0);
test_adjacency("parallel nlinks 3", &pgr.gr,
parallel_adjacencyr_nlinks3);
diff --git a/ccan/agar/test/api-bfs.c b/ccan/agar/test/api-bfs.c
index 8823df8..fae0f84 100644
--- a/ccan/agar/test/api-bfs.c
+++ b/ccan/agar/test/api-bfs.c
@@ -53,7 +53,7 @@ int main(void)
trivial_graphr_init(&tgr);
test_bfs(&tgr.gr, 1, 1);
- parallel_graphr_init(&pgr, 3);
+ parallel_graphr_init(&pgr, 3, 0);
test_bfs(&pgr.gr, 1, 1, 2);
full_graphr_init(&fgr, 5);
diff --git a/ccan/agar/test/api-dfs.c b/ccan/agar/test/api-dfs.c
index 2a7e4ce..ecc05bd 100644
--- a/ccan/agar/test/api-dfs.c
+++ b/ccan/agar/test/api-dfs.c
@@ -53,7 +53,7 @@ int main(void)
trivial_graphr_init(&tgr);
test_dfs(&tgr.gr, 1, 1);
- parallel_graphr_init(&pgr, 3);
+ parallel_graphr_init(&pgr, 3, 0);
test_dfs(&pgr.gr, 1, 1, 2);
full_graphr_init(&fgr, 5);
diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
index 4b03bc6..5edccd7 100644
--- a/ccan/agar/test/api-dijkstra.c
+++ b/ccan/agar/test/api-dijkstra.c
@@ -35,9 +35,9 @@ static void test_parallel(void)
struct parallel_graphr pgr;
struct agar_state *sr;
aga_icost_t cost;
- const void *node;
+ const void *node, *edge;
- parallel_graphr_init(&pgr, 3);
+ parallel_graphr_init(&pgr, 3, 0);
ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
ok1(agar_dijkstra_step(sr, &node));
@@ -48,7 +48,7 @@ static void test_parallel(void)
ok1(agar_dijkstra_path(sr, int2ptr(1), &cost, NULL, NULL));
ok1(cost == 0);
ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
- ok1(cost == 1);
+ ok1(cost == 2);
ok1(node == int2ptr(1));
tal_free(sr);
@@ -60,6 +60,14 @@ static void test_parallel(void)
ok1(cost == 0);
ok1(!agar_dijkstra_path(sr, int2ptr(1), NULL, NULL, NULL));
tal_free(sr);
+
+ parallel_graphr_init(&pgr, 3, 2);
+ ok1(sr = agar_dijkstra_new(NULL, &pgr.gr, int2ptr(1)));
+ ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, &edge));
+ ok1(cost == 1);
+ ok1(ptr2int(node) == 1);
+ ok1(ptr2int(edge) == 2);
+ tal_free(sr);
}
#define FULL_LEN 4
@@ -213,7 +221,7 @@ static void test_traversal1(void)
int main(void)
{
- plan_tests(6 + 18
+ plan_tests(6 + 23
+ FULL_LEN * (FULL_LEN*4 - 1)
+ CHAIN_LEN * (1 + CHAIN_LEN*2)
+ 12 + 32);
diff --git a/ccan/agar/test/parallel.c b/ccan/agar/test/parallel.c
index 741ff3a..6034ad1 100644
--- a/ccan/agar/test/parallel.c
+++ b/ccan/agar/test/parallel.c
@@ -47,15 +47,23 @@ static int parallel_edge_info_r(const struct agar_graph *gr,
const void *nr, const void *edge,
struct agar_edge_info *eir)
{
+ const struct parallel_graphr *pgr
+ = container_of(gr, struct parallel_graphr, gr);
assert(ptr2int(nr) == 1);
eir->to = int2ptr(2);
+ if (ptr2int(edge) == pgr->cheaplink)
+ eir->icost = 1;
+ else
+ eir->icost = 2;
return 0;
}
-void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks)
+void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks,
+ int cheaplink)
{
pgr->nlinks = nlinks;
+ pgr->cheaplink = cheaplink;
agar_init_graph(&pgr->gr, parallel_first_edge_r, parallel_next_edge_r,
parallel_edge_info_r);
diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
index de48ff6..2abe72d 100644
--- a/ccan/agar/test/simple-graphr.h
+++ b/ccan/agar/test/simple-graphr.h
@@ -37,9 +37,11 @@ static const struct adjacency_listr trivial_adjacencyr[] = {
*/
struct parallel_graphr {
int nlinks;
+ int cheaplink;
struct agar_graph gr;
};
-void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks);
+void parallel_graphr_init(struct parallel_graphr *pgr, int nlinks,
+ int cheaplink);
static const struct adjacency_listr parallel_adjacencyr_nlinks3[] = {
{1, {2, 2, 2}},
{2, {}},
--
2.5.0
_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 4/5] aga, agar: New shortcut1 sample graph and testcases based on it
2015-11-12 11:42 [PATCH 0/5] aga,agar: Dijkstra's algorithm David Gibson
` (2 preceding siblings ...)
2015-11-12 11:42 ` [PATCH 3/5] aga, agar: Non-equal edge costs for parallel test graph David Gibson
@ 2015-11-12 11:42 ` David Gibson
2015-11-12 11:42 ` [PATCH 5/5] aga, agar: New shortcut2 " David Gibson
2015-11-20 6:21 ` [PATCH 0/5] aga,agar: Dijkstra's algorithm David Gibson
5 siblings, 0 replies; 9+ messages in thread
From: David Gibson @ 2015-11-12 11:42 UTC (permalink / raw)
To: ccan
For all the existing test graphs, the shortest path by cost is also the
shortest path by number of edges. This patch adds a new test graph where
that is not the case, in order to test that the Dijkstra's algorithm
implementation correctly handles that case.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
ccan/aga/test/api-adjacency.c | 6 ++-
ccan/aga/test/api-dijkstra.c | 23 ++++++++++-
ccan/aga/test/shortcut1.c | 93 ++++++++++++++++++++++++++++++++++++++++++
ccan/aga/test/simple-graph.h | 20 +++++++++
ccan/agar/test/api-adjacency.c | 6 ++-
ccan/agar/test/api-dijkstra.c | 22 +++++++++-
ccan/agar/test/shortcut1.c | 86 ++++++++++++++++++++++++++++++++++++++
ccan/agar/test/simple-graphr.h | 20 +++++++++
8 files changed, 272 insertions(+), 4 deletions(-)
create mode 100644 ccan/aga/test/shortcut1.c
create mode 100644 ccan/agar/test/shortcut1.c
diff --git a/ccan/aga/test/api-adjacency.c b/ccan/aga/test/api-adjacency.c
index 2212600..8f6c6d5 100644
--- a/ccan/aga/test/api-adjacency.c
+++ b/ccan/aga/test/api-adjacency.c
@@ -61,8 +61,9 @@ int main(void)
struct grid_graph gg1, gg2;
struct error_graph eg;
struct traversal1_graph t1g;
+ struct shortcut1_graph s1g;
- plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30);
+ plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9);
trivial_graph_init(&tg);
test_adjacency("trivial", &tg.sg, trivial_adjacency);
@@ -91,5 +92,8 @@ int main(void)
traversal1_graph_init(&t1g);
test_adjacency("traversal1 graph", &t1g.sg, traversal1_adjacency);
+ shortcut1_graph_init(&s1g);
+ test_adjacency("shortcut1 graph", &s1g.sg, shortcut1_adjacency);
+
return exit_status();
}
diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
index 9be747d..9b94c98 100644
--- a/ccan/aga/test/api-dijkstra.c
+++ b/ccan/aga/test/api-dijkstra.c
@@ -214,12 +214,32 @@ static void test_traversal1(void)
aga_finish(&t1g.sg.g);
}
+static void test_shortcut1(void)
+{
+ struct shortcut1_graph s1g;
+ aga_icost_t cost;
+ struct aga_node *node;
+
+ shortcut1_graph_init(&s1g);
+
+ ok1(aga_dijkstra_start(&s1g.sg.g, &s1g.sg.nodes[1]) == 0);
+ ok1(aga_dijkstra_path(&s1g.sg.g, &s1g.sg.nodes[3],
+ &cost, &node, NULL));
+ ok1(cost == 2);
+ ok1(node == &s1g.sg.nodes[2]);
+ ok1(aga_dijkstra_path(&s1g.sg.g, &s1g.sg.nodes[2],
+ &cost, &node, NULL));
+ ok1(cost == 1);
+ ok1(node == &s1g.sg.nodes[1]);
+ aga_finish(&s1g.sg.g);
+}
+
int main(void)
{
plan_tests(7 + 20
+ FULL_LEN * (1 + FULL_LEN*4)
+ CHAIN_LEN * (1 + CHAIN_LEN*2)
- + 12 + 32);
+ + 12 + 32 + 7);
test_trivial();
test_parallel();
@@ -227,6 +247,7 @@ int main(void)
test_chain();
test_error();
test_traversal1();
+ test_shortcut1();
return exit_status();
}
diff --git a/ccan/aga/test/shortcut1.c b/ccan/aga/test/shortcut1.c
new file mode 100644
index 0000000..bea05a6
--- /dev/null
+++ b/ccan/aga/test/shortcut1.c
@@ -0,0 +1,93 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+static ptrint_t *shortcut1_first_edge(const struct aga_graph *g,
+ const struct aga_node *n)
+{
+ struct shortcut1_graph *s1g = container_of(g, struct shortcut1_graph,
+ sg.g);
+ int ni = n - s1g->sg.nodes;
+
+ switch (ni) {
+ case 1:
+ case 2:
+ return int2ptr(1);
+
+ case 3:
+ return NULL;
+
+ default:
+ assert(0);
+ }
+}
+
+static ptrint_t *shortcut1_next_edge(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *e)
+{
+ struct shortcut1_graph *s1g = container_of(g, struct shortcut1_graph,
+ sg.g);
+ int ni = n - s1g->sg.nodes;
+ int index = ptr2int(e);
+
+ switch (ni) {
+ case 1:
+ if (index == 1)
+ return int2ptr(2);
+ assert(index == 2);
+ return NULL;
+
+ case 2:
+ assert(index == 1);
+ return NULL;
+
+ default:
+ assert(0);
+ }
+}
+
+static int shortcut1_edge_info(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *e, struct aga_edge_info *ei)
+{
+ struct shortcut1_graph *s1g = container_of(g, struct shortcut1_graph,
+ sg.g);
+ int ni = n - s1g->sg.nodes;
+ int index = ptr2int(e);
+
+ switch (ni) {
+ case 1:
+ if (index == 1) {
+ ei->to = &s1g->sg.nodes[3];
+ ei->icost = 3;
+ } else {
+ assert(index == 2);
+ ei->to = &s1g->sg.nodes[2];
+ }
+ break;
+
+ case 2:
+ assert(index == 1);
+ ei->to = &s1g->sg.nodes[3];
+ break;
+
+ default:
+ assert(0);
+ }
+ return 0;
+}
+
+void shortcut1_graph_init(struct shortcut1_graph *s1g)
+{
+ simple_graph_init(&s1g->sg, shortcut1_first_edge,
+ shortcut1_next_edge,
+ shortcut1_edge_info);
+}
diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
index 57f87a8..77ba2a6 100644
--- a/ccan/aga/test/simple-graph.h
+++ b/ccan/aga/test/simple-graph.h
@@ -215,4 +215,24 @@ static const struct adjacency_list traversal1_adjacency[] = {
{},
};
+/* Shortcut-1 graph
+ *
+ * A ---- (3) -----> C
+ * \ /
+ * (1)-> B --(1)
+ *
+ * This provides an example of a graph where the lowest cost path from
+ * (A) to (C) is not the path with the smallest number od edges.
+ */
+struct shortcut1_graph {
+ struct simple_graph sg;
+};
+void shortcut1_graph_init(struct shortcut1_graph *s1g);
+static const struct adjacency_list shortcut1_adjacency[] = {
+ {1, {3, 2}},
+ {2, {3}},
+ {3, {}},
+ {},
+};
+
#endif /* _TEST_GRAPHS_H */
diff --git a/ccan/agar/test/api-adjacency.c b/ccan/agar/test/api-adjacency.c
index 469cd83..9482bba 100644
--- a/ccan/agar/test/api-adjacency.c
+++ b/ccan/agar/test/api-adjacency.c
@@ -55,8 +55,9 @@ int main(void)
struct chain_graphr cgr;
struct grid_graphr ggr1, ggr2;
struct error_graphr egr;
+ struct shortcut1_graphr s1gr;
- plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6);
+ plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6 + 6);
trivial_graphr_init(&tgr);
test_adjacency("trivial", &tgr.gr, trivial_adjacencyr);
@@ -82,5 +83,8 @@ int main(void)
error_graphr_init(&egr);
test_adjacency("error graph", &egr.gr, error_adjacencyr);
+ shortcut1_graphr_init(&s1gr);
+ test_adjacency("shortcut1 graph", &s1gr.gr, shortcut1_adjacencyr);
+
return exit_status();
}
diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
index 5edccd7..3ade158 100644
--- a/ccan/agar/test/api-dijkstra.c
+++ b/ccan/agar/test/api-dijkstra.c
@@ -219,12 +219,31 @@ static void test_traversal1(void)
tal_free(sr);
}
+static void test_shortcut1(void)
+{
+ struct shortcut1_graphr s1gr;
+ struct agar_state *sr;
+ aga_icost_t cost;
+ const void *node;
+
+ shortcut1_graphr_init(&s1gr);
+
+ ok1(sr = agar_dijkstra_new(NULL, &s1gr.gr, int2ptr(1)));
+ ok1(agar_dijkstra_path(sr, int2ptr(3), &cost, &node, NULL));
+ ok1(cost == 2);
+ ok1(node == int2ptr(2));
+ ok1(agar_dijkstra_path(sr, int2ptr(2), &cost, &node, NULL));
+ ok1(cost == 1);
+ ok1(node == int2ptr(1));
+ tal_free(sr);
+}
+
int main(void)
{
plan_tests(6 + 23
+ FULL_LEN * (FULL_LEN*4 - 1)
+ CHAIN_LEN * (1 + CHAIN_LEN*2)
- + 12 + 32);
+ + 12 + 32 + 7);
test_trivial();
test_parallel();
@@ -232,6 +251,7 @@ int main(void)
test_chain();
test_error();
test_traversal1();
+ test_shortcut1();
return exit_status();
}
diff --git a/ccan/agar/test/shortcut1.c b/ccan/agar/test/shortcut1.c
new file mode 100644
index 0000000..efae316
--- /dev/null
+++ b/ccan/agar/test/shortcut1.c
@@ -0,0 +1,86 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#include "simple-graphr.h"
+
+static const void *shortcut1_first_edge_r(const struct agar_graph *gr,
+ const void *nr)
+{
+ int ni = ptr2int(nr);
+
+ switch (ni) {
+ case 1:
+ case 2:
+ return int2ptr(1);
+
+ case 3:
+ return NULL;
+
+ default:
+ assert(0);
+ }
+}
+
+static const void *shortcut1_next_edge_r(const struct agar_graph *gr,
+ const void *nr, const void *e)
+{
+ int ni = ptr2int(nr);
+ int index = ptr2int(e);
+
+ switch (ni) {
+ case 1:
+ if (index == 1)
+ return int2ptr(2);
+ assert(index == 2);
+ return NULL;
+
+ case 2:
+ assert(index == 1);
+ return NULL;
+
+ default:
+ assert(0);
+ }
+}
+
+static int shortcut1_edge_info_r(const struct agar_graph *gr,
+ const void *nr, const void *e,
+ struct agar_edge_info *eir)
+{
+ int ni = ptr2int(nr);
+ int index = ptr2int(e);
+
+ switch (ni) {
+ case 1:
+ if (index == 1) {
+ eir->to = int2ptr(3);
+ eir->icost = 3;
+ } else {
+ assert(index == 2);
+ eir->to = int2ptr(2);
+ }
+ break;
+
+ case 2:
+ assert(index == 1);
+ eir->to = int2ptr(3);
+ break;
+
+ default:
+ assert(0);
+ }
+ return 0;
+}
+
+void shortcut1_graphr_init(struct shortcut1_graphr *s1gr)
+{
+ agar_init_graph(&s1gr->gr, shortcut1_first_edge_r,
+ shortcut1_next_edge_r,
+ shortcut1_edge_info_r);
+}
diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
index 2abe72d..168ee29 100644
--- a/ccan/agar/test/simple-graphr.h
+++ b/ccan/agar/test/simple-graphr.h
@@ -199,4 +199,24 @@ static const struct adjacency_listr traversal1_adjacency[] = {
{},
};
+/* Shortcut-1 graph
+ *
+ * A ---- (3) -----> C
+ * \ /
+ * (1)-> B --(1)
+ *
+ * This provides an example of a graph where the lowest cost path from
+ * (A) to (C) is not the path with the smallest number od edges.
+ */
+struct shortcut1_graphr {
+ struct agar_graph gr;
+};
+void shortcut1_graphr_init(struct shortcut1_graphr *s1gr);
+static const struct adjacency_listr shortcut1_adjacencyr[] = {
+ {1, {3, 2}},
+ {2, {3}},
+ {3, {}},
+ {},
+};
+
#endif /* _SIMPLE_GRAPHR_H */
--
2.5.0
_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan
^ permalink raw reply related [flat|nested] 9+ messages in thread* [PATCH 5/5] aga, agar: New shortcut2 sample graph and testcases based on it
2015-11-12 11:42 [PATCH 0/5] aga,agar: Dijkstra's algorithm David Gibson
` (3 preceding siblings ...)
2015-11-12 11:42 ` [PATCH 4/5] aga, agar: New shortcut1 sample graph and testcases based on it David Gibson
@ 2015-11-12 11:42 ` David Gibson
2015-11-20 6:21 ` [PATCH 0/5] aga,agar: Dijkstra's algorithm David Gibson
5 siblings, 0 replies; 9+ messages in thread
From: David Gibson @ 2015-11-12 11:42 UTC (permalink / raw)
To: ccan
This patch adds a new test graph "shortcut2" which includes a negative cost
edge. Along with that we add a testcase for Dijkstra's algorithm checking
that it gracefully fails in this case.
Signed-off-by: David Gibson <david@gibson.dropbear.id.au>
---
ccan/aga/test/api-adjacency.c | 6 ++-
ccan/aga/test/api-dijkstra.c | 15 ++++++-
ccan/aga/test/shortcut2.c | 94 ++++++++++++++++++++++++++++++++++++++++++
ccan/aga/test/simple-graph.h | 21 ++++++++++
ccan/agar/test/api-adjacency.c | 6 ++-
ccan/agar/test/api-dijkstra.c | 16 ++++++-
ccan/agar/test/shortcut2.c | 87 ++++++++++++++++++++++++++++++++++++++
ccan/agar/test/simple-graphr.h | 21 ++++++++++
8 files changed, 262 insertions(+), 4 deletions(-)
create mode 100644 ccan/aga/test/shortcut2.c
create mode 100644 ccan/agar/test/shortcut2.c
diff --git a/ccan/aga/test/api-adjacency.c b/ccan/aga/test/api-adjacency.c
index 8f6c6d5..6e50430 100644
--- a/ccan/aga/test/api-adjacency.c
+++ b/ccan/aga/test/api-adjacency.c
@@ -62,8 +62,9 @@ int main(void)
struct error_graph eg;
struct traversal1_graph t1g;
struct shortcut1_graph s1g;
+ struct shortcut2_graph s2g;
- plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9);
+ plan_tests(2 + 7 + 35 + 30 + 30 + 42 + 9 + 30 + 9 + 9);
trivial_graph_init(&tg);
test_adjacency("trivial", &tg.sg, trivial_adjacency);
@@ -95,5 +96,8 @@ int main(void)
shortcut1_graph_init(&s1g);
test_adjacency("shortcut1 graph", &s1g.sg, shortcut1_adjacency);
+ shortcut2_graph_init(&s2g);
+ test_adjacency("shortcut2 graph", &s2g.sg, shortcut2_adjacency);
+
return exit_status();
}
diff --git a/ccan/aga/test/api-dijkstra.c b/ccan/aga/test/api-dijkstra.c
index 9b94c98..f9b8d76 100644
--- a/ccan/aga/test/api-dijkstra.c
+++ b/ccan/aga/test/api-dijkstra.c
@@ -234,12 +234,24 @@ static void test_shortcut1(void)
aga_finish(&s1g.sg.g);
}
+static void test_shortcut2(void)
+{
+ struct shortcut2_graph s2g;
+
+ shortcut2_graph_init(&s2g);
+
+ ok1(aga_dijkstra_start(&s2g.sg.g, &s2g.sg.nodes[1]) == 0);
+ aga_dijkstra_all_paths(&s2g.sg.g);
+ ok1(aga_error(&s2g.sg.g) == AGA_ERR_NEGATIVE_COST);
+ aga_finish(&s2g.sg.g);
+}
+
int main(void)
{
plan_tests(7 + 20
+ FULL_LEN * (1 + FULL_LEN*4)
+ CHAIN_LEN * (1 + CHAIN_LEN*2)
- + 12 + 32 + 7);
+ + 12 + 32 + 7 + 2);
test_trivial();
test_parallel();
@@ -248,6 +260,7 @@ int main(void)
test_error();
test_traversal1();
test_shortcut1();
+ test_shortcut2();
return exit_status();
}
diff --git a/ccan/aga/test/shortcut2.c b/ccan/aga/test/shortcut2.c
new file mode 100644
index 0000000..33eee0a
--- /dev/null
+++ b/ccan/aga/test/shortcut2.c
@@ -0,0 +1,94 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/aga/aga.h>
+
+#include "simple-graph.h"
+
+static ptrint_t *shortcut2_first_edge(const struct aga_graph *g,
+ const struct aga_node *n)
+{
+ struct shortcut2_graph *s1g = container_of(g, struct shortcut2_graph,
+ sg.g);
+ int ni = n - s1g->sg.nodes;
+
+ switch (ni) {
+ case 1:
+ case 2:
+ return int2ptr(1);
+
+ case 3:
+ return NULL;
+
+ default:
+ assert(0);
+ }
+}
+
+static ptrint_t *shortcut2_next_edge(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *e)
+{
+ struct shortcut2_graph *s1g = container_of(g, struct shortcut2_graph,
+ sg.g);
+ int ni = n - s1g->sg.nodes;
+ int index = ptr2int(e);
+
+ switch (ni) {
+ case 1:
+ if (index == 1)
+ return int2ptr(2);
+ assert(index == 2);
+ return NULL;
+
+ case 2:
+ assert(index == 1);
+ return NULL;
+
+ default:
+ assert(0);
+ }
+}
+
+static int shortcut2_edge_info(const struct aga_graph *g,
+ const struct aga_node *n,
+ ptrint_t *e, struct aga_edge_info *ei)
+{
+ struct shortcut2_graph *s1g = container_of(g, struct shortcut2_graph,
+ sg.g);
+ int ni = n - s1g->sg.nodes;
+ int index = ptr2int(e);
+
+ switch (ni) {
+ case 1:
+ if (index == 1) {
+ ei->to = &s1g->sg.nodes[3];
+ } else {
+ assert(index == 2);
+ ei->to = &s1g->sg.nodes[2];
+ }
+ ei->icost = 2;
+ break;
+
+ case 2:
+ assert(index == 1);
+ ei->to = &s1g->sg.nodes[3];
+ ei->icost = -1;
+ break;
+
+ default:
+ assert(0);
+ }
+ return 0;
+}
+
+void shortcut2_graph_init(struct shortcut2_graph *s1g)
+{
+ simple_graph_init(&s1g->sg, shortcut2_first_edge,
+ shortcut2_next_edge,
+ shortcut2_edge_info);
+}
diff --git a/ccan/aga/test/simple-graph.h b/ccan/aga/test/simple-graph.h
index 77ba2a6..b8da3ad 100644
--- a/ccan/aga/test/simple-graph.h
+++ b/ccan/aga/test/simple-graph.h
@@ -235,4 +235,25 @@ static const struct adjacency_list shortcut1_adjacency[] = {
{},
};
+/* Shortcut-2 graph
+ *
+ * A ---- (2) -----> C
+ * \ /
+ * (2)-> B --(-1)
+ *
+ * This provides an example of a graph with a negative edge cost, but
+ * no negative cost cycles (and so still with well defined shortest
+ * paths).
+ */
+struct shortcut2_graph {
+ struct simple_graph sg;
+};
+void shortcut2_graph_init(struct shortcut2_graph *s2g);
+static const struct adjacency_list shortcut2_adjacency[] = {
+ {1, {3, 2}},
+ {2, {3}},
+ {3, {}},
+ {},
+};
+
#endif /* _TEST_GRAPHS_H */
diff --git a/ccan/agar/test/api-adjacency.c b/ccan/agar/test/api-adjacency.c
index 9482bba..2b2637d 100644
--- a/ccan/agar/test/api-adjacency.c
+++ b/ccan/agar/test/api-adjacency.c
@@ -56,8 +56,9 @@ int main(void)
struct grid_graphr ggr1, ggr2;
struct error_graphr egr;
struct shortcut1_graphr s1gr;
+ struct shortcut2_graphr s2gr;
- plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6 + 6);
+ plan_tests(1 + 5 + 30 + 22 + 21 + 33 + 6 + 6 + 6);
trivial_graphr_init(&tgr);
test_adjacency("trivial", &tgr.gr, trivial_adjacencyr);
@@ -86,5 +87,8 @@ int main(void)
shortcut1_graphr_init(&s1gr);
test_adjacency("shortcut1 graph", &s1gr.gr, shortcut1_adjacencyr);
+ shortcut2_graphr_init(&s2gr);
+ test_adjacency("shortcut2 graph", &s2gr.gr, shortcut2_adjacencyr);
+
return exit_status();
}
diff --git a/ccan/agar/test/api-dijkstra.c b/ccan/agar/test/api-dijkstra.c
index 3ade158..1321e26 100644
--- a/ccan/agar/test/api-dijkstra.c
+++ b/ccan/agar/test/api-dijkstra.c
@@ -238,12 +238,25 @@ static void test_shortcut1(void)
tal_free(sr);
}
+static void test_shortcut2(void)
+{
+ struct shortcut2_graphr s2gr;
+ struct agar_state *sr;
+
+ shortcut2_graphr_init(&s2gr);
+
+ ok1(sr = agar_dijkstra_new(NULL, &s2gr.gr, int2ptr(1)));
+ agar_dijkstra_all_paths(sr);
+ ok1(agar_error(sr) == AGA_ERR_NEGATIVE_COST);
+ tal_free(sr);
+}
+
int main(void)
{
plan_tests(6 + 23
+ FULL_LEN * (FULL_LEN*4 - 1)
+ CHAIN_LEN * (1 + CHAIN_LEN*2)
- + 12 + 32 + 7);
+ + 12 + 32 + 7 + 2);
test_trivial();
test_parallel();
@@ -252,6 +265,7 @@ int main(void)
test_error();
test_traversal1();
test_shortcut1();
+ test_shortcut2();
return exit_status();
}
diff --git a/ccan/agar/test/shortcut2.c b/ccan/agar/test/shortcut2.c
new file mode 100644
index 0000000..aff89a6
--- /dev/null
+++ b/ccan/agar/test/shortcut2.c
@@ -0,0 +1,87 @@
+#include "config.h"
+
+#include <assert.h>
+
+#include <ccan/container_of/container_of.h>
+#include <ccan/ptrint/ptrint.h>
+
+#include <ccan/agar/agar.h>
+
+#include "simple-graphr.h"
+
+static const void *shortcut2_first_edge_r(const struct agar_graph *gr,
+ const void *nr)
+{
+ int ni = ptr2int(nr);
+
+ switch (ni) {
+ case 1:
+ case 2:
+ return int2ptr(1);
+
+ case 3:
+ return NULL;
+
+ default:
+ assert(0);
+ }
+}
+
+static const void *shortcut2_next_edge_r(const struct agar_graph *gr,
+ const void *nr, const void *e)
+{
+ int ni = ptr2int(nr);
+ int index = ptr2int(e);
+
+ switch (ni) {
+ case 1:
+ if (index == 1)
+ return int2ptr(2);
+ assert(index == 2);
+ return NULL;
+
+ case 2:
+ assert(index == 1);
+ return NULL;
+
+ default:
+ assert(0);
+ }
+}
+
+static int shortcut2_edge_info_r(const struct agar_graph *gr,
+ const void *nr, const void *e,
+ struct agar_edge_info *eir)
+{
+ int ni = ptr2int(nr);
+ int index = ptr2int(e);
+
+ switch (ni) {
+ case 1:
+ if (index == 1) {
+ eir->to = int2ptr(3);
+ } else {
+ assert(index == 2);
+ eir->to = int2ptr(2);
+ }
+ eir->icost = 2;
+ break;
+
+ case 2:
+ assert(index == 1);
+ eir->to = int2ptr(3);
+ eir->icost = -1;
+ break;
+
+ default:
+ assert(0);
+ }
+ return 0;
+}
+
+void shortcut2_graphr_init(struct shortcut2_graphr *s1gr)
+{
+ agar_init_graph(&s1gr->gr, shortcut2_first_edge_r,
+ shortcut2_next_edge_r,
+ shortcut2_edge_info_r);
+}
diff --git a/ccan/agar/test/simple-graphr.h b/ccan/agar/test/simple-graphr.h
index 168ee29..2fe98a4 100644
--- a/ccan/agar/test/simple-graphr.h
+++ b/ccan/agar/test/simple-graphr.h
@@ -219,4 +219,25 @@ static const struct adjacency_listr shortcut1_adjacencyr[] = {
{},
};
+/* Shortcut-2 graph
+ *
+ * A ---- (2) -----> C
+ * \ /
+ * (2)-> B --(-1)
+ *
+ * This provides an example of a graph with a negative edge cost, but
+ * no negative cost cycles (and so still with well defined shortest
+ * paths).
+ */
+struct shortcut2_graphr {
+ struct agar_graph gr;
+};
+void shortcut2_graphr_init(struct shortcut2_graphr *s2gr);
+static const struct adjacency_listr shortcut2_adjacencyr[] = {
+ {1, {3, 2}},
+ {2, {3}},
+ {3, {}},
+ {},
+};
+
#endif /* _SIMPLE_GRAPHR_H */
--
2.5.0
_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan
^ permalink raw reply related [flat|nested] 9+ messages in thread* Re: [PATCH 0/5] aga,agar: Dijkstra's algorithm
2015-11-12 11:42 [PATCH 0/5] aga,agar: Dijkstra's algorithm David Gibson
` (4 preceding siblings ...)
2015-11-12 11:42 ` [PATCH 5/5] aga, agar: New shortcut2 " David Gibson
@ 2015-11-20 6:21 ` David Gibson
5 siblings, 0 replies; 9+ messages in thread
From: David Gibson @ 2015-11-20 6:21 UTC (permalink / raw)
To: ccan
[-- Attachment #1.1: Type: text/plain, Size: 549 bytes --]
On Thu, Nov 12, 2015 at 10:42:43PM +1100, David Gibson wrote:
> After many diversions, I'm finally ready to paint this bikeshed, with
> a brush of finest yak hair.
>
> This series implements Dijkstra's algorithm for single-source
> shortest-path in the aga and agar modules.
I'm going to take silence as assent, and have commited this series.
--
David Gibson | I'll have my music baroque, and my code
david AT gibson.dropbear.id.au | minimalist, thank you. NOT _the_ _other_
| _way_ _around_!
http://www.ozlabs.org/~dgibson
[-- Attachment #1.2: signature.asc --]
[-- Type: application/pgp-signature, Size: 819 bytes --]
[-- Attachment #2: Type: text/plain, Size: 127 bytes --]
_______________________________________________
ccan mailing list
ccan@lists.ozlabs.org
https://lists.ozlabs.org/listinfo/ccan
^ permalink raw reply [flat|nested] 9+ messages in thread