From 19390ab685d27f2b2c3153dd53b5661998edcfaf Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= <jeremy@asynk.ch>
Date: Tue, 4 Feb 2014 00:17:12 +0100
Subject: implement eina_graph_bfs_shortest_path() with tests

---
 src/lib/eina_graph_bfs.c     | 50 ++++++++++++++++++++++++++++++++------------
 src/lib/eina_graph_bfs.h     | 13 ++++++++++++
 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);
-- 
cgit v1.1-2-g2b99