implement eina_graph_bfs_shortest_path() with tests

2 files changed, 50 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.