add eina_graph supports directed graphs

4 files changed, 75 insertions, 8 deletions

diff --git a/src/lib/eina_graph.c b/src/lib/eina_graph.c
index e3bf209..8d887cf 100644
--- a/src/lib/eina_graph.c
+++ b/src/lib/eina_graph.c
@@ -34,7 +34,7 @@
 #include "eina_graph_private.h"
 
 EAPI Eina_Graph *
-eina_graph_new(unsigned int v, unsigned int step)
+eina_graph_new(unsigned int v, unsigned int step, Eina_Bool directed)
 {
    unsigned int i;
    _Eina_Graph *_g;
@@ -47,6 +47,7 @@ eina_graph_new(unsigned int v, unsigned int step)
      }
 
    _g->vertices = v;
+   _g->directed = directed;
    for (i = 0; i < v; i++)
      _g->adjs[i] = eina_array_new(step);
 
@@ -65,6 +66,14 @@ eina_graph_free(Eina_Graph *g)
    free(_g);
 }
 
+EAPI Eina_Bool
+eina_graph_directed(const Eina_Graph *g)
+{
+   _Eina_Graph * _g = (_Eina_Graph *) g;
+
+   return _g->directed;
+}
+
 EAPI unsigned int
 eina_graph_vertices_count(const Eina_Graph *g)
 {
@@ -152,7 +161,7 @@ eina_graph_edge_add(Eina_Graph *g, unsigned int v, unsigned int w)
      }
 
    if (!eina_array_push_uint(_g->adjs[v], w)) return EINA_FALSE;
-   if (v != w )
+   if (!_g->directed && (v != w))
      if (!eina_array_push_uint(_g->adjs[w], v)) return EINA_FALSE;
 
    _g->edges++;
@@ -169,7 +178,10 @@ eina_graph_dot_write(Eina_Graph *g, FILE *f)
    Eina_Array *ar;
    _Eina_Graph * _g = (_Eina_Graph *) g;
 
-   fwrite("digraph {\n", 10, 1, f);
+   if (_g->directed)
+     fwrite("digraph {\n", 10, 1, f);
+   else
+     fwrite("strict graph {\n", 15, 1, f);
 
    for (i = 0; i< _g->vertices; i++)
      {
@@ -177,7 +189,10 @@ eina_graph_dot_write(Eina_Graph *g, FILE *f)
         n = eina_array_count_get(ar);
         for (j = 0; j < n; j++)
           {
-             r = snprintf(buf, 32, "%u -> %u;\n", i, eina_array_uint_nth_get(ar, j));
+             if (_g->directed)
+               r = snprintf(buf, 32, "%u -> %u;\n", i, eina_array_uint_nth_get(ar, j));
+             else
+               r = snprintf(buf, 32, "%u -- %u;\n", i, eina_array_uint_nth_get(ar, j));
              fwrite(buf, r, 1, f);
           }
      }
diff --git a/src/lib/eina_graph.h b/src/lib/eina_graph.h
index 3297a22..c47c66a 100644
--- a/src/lib/eina_graph.h
+++ b/src/lib/eina_graph.h
@@ -46,11 +46,12 @@ typedef struct _Eina_Graph_Opaque Eina_Graph;
  *
  * @param v the number of vertices.
  * @param step grow step for the adjacent lists.
+ * @param directed graph or not.
  *
  * @return a pointer to the Eina_Graph.
  */
 EAPI Eina_Graph *
-eina_graph_new(unsigned int v, unsigned int step);
+eina_graph_new(unsigned int v, unsigned int step, Eina_Bool directed);
 
 /**
  * free the given graph.
@@ -61,6 +62,16 @@ EAPI void
 eina_graph_free(Eina_Graph *g);
 
 /**
+ * returns true if it is a directed graph.
+ *
+ * @param g the graph to consider.
+ *
+ * @retur true if this is a directed graph.
+ */
+EAPI Eina_Bool
+eina_graph_directed(const Eina_Graph *g);
+
+/**
  * returns the number of vertices of the graph.
  *
  * @param g the graph to consider.
diff --git a/src/lib/eina_graph_private.h b/src/lib/eina_graph_private.h
index 1925cf7..e8138a9 100644
--- a/src/lib/eina_graph_private.h
+++ b/src/lib/eina_graph_private.h
@@ -95,6 +95,7 @@ typedef struct _Eina_Graph
 {
    unsigned int vertices;
    unsigned int edges;
+   Eina_Bool directed;
    Eina_Array *adjs[];
 } _Eina_Graph;
 
diff --git a/src/tests/eina_graph_suite.c b/src/tests/eina_graph_suite.c
index bb4cdf1..14b21f8 100644
--- a/src/tests/eina_graph_suite.c
+++ b/src/tests/eina_graph_suite.c
@@ -33,7 +33,7 @@ START_TEST (test_eina_graph_simple_bfs)
    unsigned int vsr[] = { 0, 5, 3 };
 
    ck_assert(eina_graph_init() == 1);
-   Eina_Graph *g = eina_graph_new(13, 2);
+   Eina_Graph *g = eina_graph_new(13, 2, EINA_FALSE);
    ck_assert(g != NULL);
 
    _feed_simple_graph(g);
@@ -73,7 +73,7 @@ START_TEST (test_eina_graph_simple_dfs)
    unsigned int vss[] = { 0, 6, 4, 5, 3 };
 
    ck_assert(eina_graph_init() == 1);
-   Eina_Graph *g = eina_graph_new(13, 2);
+   Eina_Graph *g = eina_graph_new(13, 2, EINA_FALSE);
    ck_assert(g != NULL);
 
    _feed_simple_graph(g);
@@ -125,11 +125,13 @@ START_TEST (test_eina_graph_simple)
    ck_assert(eina_graph_init() == 1);
    ck_assert(eina_graph_init() == 2);
 
-   Eina_Graph *g = eina_graph_new(13, 2);
+   Eina_Graph *g = eina_graph_new(13, 2, EINA_FALSE);
    ck_assert(g != NULL);
 
    _feed_simple_graph(g);
 
+   ck_assert(eina_graph_directed(g) == EINA_FALSE);
+
    ck_assert(eina_graph_edge_add(g, -1, 3) == EINA_FALSE);
    ck_assert(eina_graph_edge_add(g, 3, -1) == EINA_FALSE);
    ck_assert(eina_graph_edge_add(g, 13, 3) == EINA_FALSE);
@@ -161,6 +163,44 @@ START_TEST (test_eina_graph_simple)
 
    eina_graph_free(g);
 
+   g = eina_graph_new(13, 2, EINA_TRUE);
+   ck_assert(g != NULL);
+
+   _feed_simple_graph(g);
+
+   ck_assert(eina_graph_directed(g) == EINA_TRUE);
+
+   ck_assert(eina_graph_edge_add(g, -1, 3) == EINA_FALSE);
+   ck_assert(eina_graph_edge_add(g, 3, -1) == EINA_FALSE);
+   ck_assert(eina_graph_edge_add(g, 13, 3) == EINA_FALSE);
+   ck_assert(eina_graph_edge_add(g, 3, 13) == EINA_FALSE);
+
+   ck_assert(eina_graph_vertices_count(g) == 13);
+   ck_assert(eina_graph_edges_count(g) == 13);
+   ck_assert(eina_graph_degree(g, 4) == 1);
+   ck_assert(eina_graph_degree(g, 0) == 4);
+   ck_assert(eina_graph_degree(g, 15) == 0);
+   ck_assert(eina_graph_degree_max(g) == 4);
+   ck_assert(eina_graph_degree_avg(g) == 2.0);
+   ck_assert(eina_graph_self_loops(g) == 0);
+
+   ck_assert(eina_graph_edge_add(g, 0, 0) == EINA_TRUE);
+
+   ck_assert(eina_graph_vertices_count(g) == 13);
+   ck_assert(eina_graph_edges_count(g) == 14);
+   ck_assert(eina_graph_degree(g, 4) == 1);
+   ck_assert(eina_graph_degree(g, 0) == 5);
+   ck_assert(eina_graph_degree_max(g) == 5);
+   ck_assert(eina_graph_degree_avg(g) > 2.153);
+   ck_assert(eina_graph_degree_avg(g) < 2.154);
+   ck_assert(eina_graph_self_loops(g) == 1);
+
+   outf = fopen("/tmp/eina_graph_directed.dot", "w");
+   eina_graph_dot_write(g, outf);
+   fclose(outf);
+
+   eina_graph_free(g);
+
    ck_assert(eina_graph_shutdown() == 1);
    ck_assert(eina_graph_shutdown() == 0);
 }