diff options
| -rw-r--r-- | src/lib/eina_graph_bfs.c | 50 | ||||
| -rw-r--r-- | src/lib/eina_graph_bfs.h | 13 | ||||
| -rw-r--r-- | src/tests/eina_graph_suite.c | 11 |
3 files changed, 61 insertions, 13 deletions
diff --git a/src/lib/eina_graph_bfs.c b/src/lib/eina_graph_bfs.c index 12fa0ad..a7ce983 100644 --- a/src/lib/eina_graph_bfs.c +++ b/src/lib/eina_graph_bfs.c @@ -59,28 +59,28 @@ error_bfs: } static void -_eina_graph_bfs_walk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v) +_eina_graph_bfs_walk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, + unsigned int s, unsigned int d) { + Eina_Bool has_target = (s != d); Eina_List *fifo = NULL; Eina_Array *adjs; _Eina_Graph_BFS_Data *vd; - unsigned int p, w, n, i, d; + unsigned int p, w, n, i, dst; - d = 0; - vd = &_bfs->data[v]; + dst = 0; + vd = &_bfs->data[s]; vd->m = EINA_TRUE; - vd->e = v; - vd->d = d; - fifo = eina_list_append(fifo, CAST_V(v)); + vd->e = s; + vd->d = dst; + fifo = eina_list_append(fifo, CAST_V(s)); while (eina_list_count(fifo) > 0) { - w = CAST_D(eina_list_data_get(fifo)); + dst++; + p = w = CAST_D(eina_list_data_get(fifo)); fifo = eina_list_remove(fifo, CAST_V(w)); - p = w; - d++; - adjs = _g->adjs[w]; n = eina_array_count_get(adjs); for (i = 0; i < n; i++) @@ -91,7 +91,12 @@ _eina_graph_bfs_walk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v) { vd->m = EINA_TRUE; vd->e = p; - vd->d = d; + vd->d = dst; + if (has_target && (d == w)) + { + eina_list_free(fifo); + return; + } fifo = eina_list_append(fifo, CAST_V(w)); } } @@ -100,6 +105,25 @@ _eina_graph_bfs_walk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v) eina_list_free(fifo); } +EAPI Eina_List * +eina_graph_bfs_shortest_path(Eina_Graph *g, unsigned int s, unsigned int d) +{ + Eina_List *path; + Eina_Graph_BFS *bfs; + _Eina_Graph * _g = (_Eina_Graph *) g; + + bfs = _eina_graph_bfs_allocate(_g, s); + if (!bfs) return NULL; + + _eina_graph_bfs_walk(_g, (_Eina_Graph_BFS *)bfs, s, d); + path = eina_graph_bfs_path_to(bfs, d); + + eina_graph_bfs_free(bfs); + + return path; +} + + EAPI Eina_Graph_BFS * eina_graph_bfs_new(Eina_Graph *g, unsigned int s) { @@ -109,7 +133,7 @@ eina_graph_bfs_new(Eina_Graph *g, unsigned int s) bfs = _eina_graph_bfs_allocate(_g, s); if (!bfs) return NULL; - _eina_graph_bfs_walk(_g, (_Eina_Graph_BFS *)bfs, s); + _eina_graph_bfs_walk(_g, (_Eina_Graph_BFS *)bfs, s, s); return bfs; } diff --git a/src/lib/eina_graph_bfs.h b/src/lib/eina_graph_bfs.h index 77d8b3c..f367cf4 100644 --- a/src/lib/eina_graph_bfs.h +++ b/src/lib/eina_graph_bfs.h @@ -39,6 +39,19 @@ typedef struct _Eina_Graph_BFS_Opaque Eina_Graph_BFS; /** + * return the path to reach the given destination from the source. + * + * @param g the graph to compute the shortest path on. + * @param s the source vertex. + * @param d the destination vertex. + * + * @return a list of vertices to follow from source to reach v, + * NULL if v is not reachable. + */ +EAPI Eina_List * +eina_graph_bfs_shortest_path(Eina_Graph *g, unsigned int s, unsigned int d); + +/** * returns a Breadth First Search of the given graph. * * @param g the graph to build the BFS from. diff --git a/src/tests/eina_graph_suite.c b/src/tests/eina_graph_suite.c index 695e7ab..dd1d852 100644 --- a/src/tests/eina_graph_suite.c +++ b/src/tests/eina_graph_suite.c @@ -58,6 +58,17 @@ static void _bfs_tests(unsigned int vertices[], unsigned int n) path = NULL; eina_graph_bfs_free(bfs); + path = eina_graph_bfs_shortest_path(g, 0, 3); + ck_assert(path != NULL); + ck_assert(eina_list_count(path) == n); + i = 0; + EINA_LIST_FREE(path, data) + { + ck_assert(vertices[i] == CAST_D(data)); + i++; + } + path = NULL; + eina_graph_free(g); ck_assert(eina_graph_shutdown() == 0); |