From ef6d10c4980eaf0feeb8569bc983075cc023ad83 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?J=C3=A9r=C3=A9my=20Zurcher?= Date: Fri, 10 Jan 2014 16:46:46 +0100 Subject: add eina_graph supports directed graphs --- src/lib/eina_graph.c | 23 ++++++++++++++++++---- src/lib/eina_graph.h | 13 ++++++++++++- src/lib/eina_graph_private.h | 1 + src/tests/eina_graph_suite.c | 46 +++++++++++++++++++++++++++++++++++++++++--- 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); } -- cgit v1.1-2-g2b99