summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/lib/eina_graph.c23
-rw-r--r--src/lib/eina_graph.h13
-rw-r--r--src/lib/eina_graph_private.h1
-rw-r--r--src/tests/eina_graph_suite.c46
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);
}
generated by cgit v1.1-2-g2b99 at 2024-11-22 06:16:38 +0100