diff options
| -rw-r--r-- | src/Makefile_lib.am | 6 | ||||
| -rw-r--r-- | src/lib/Eina_Graph.h | 2 | ||||
| -rw-r--r-- | src/lib/eina_graph.c | 150 | ||||
| -rw-r--r-- | src/lib/eina_graph.h | 133 | ||||
| -rw-r--r-- | src/lib/eina_graph_main.c | 17 | ||||
| -rw-r--r-- | src/lib/eina_graph_private.h | 38 |
6 files changed, 344 insertions, 2 deletions
diff --git a/src/Makefile_lib.am b/src/Makefile_lib.am index f46abe0..79b3b8a 100644 --- a/src/Makefile_lib.am +++ b/src/Makefile_lib.am @@ -2,10 +2,12 @@ includesdir = $(includedir)/eina_graph-@VMAJ@ includes_HEADERS = \ - lib/Eina_Graph.h + lib/Eina_Graph.h \ + lib/eina_graph.h lib_libeina_graph_la_SOURCES = \ - lib/eina_graph_main.c + lib/eina_graph_main.c \ + lib/eina_graph.c EXTRA_DIST += lib/eina_graph_private.h diff --git a/src/lib/Eina_Graph.h b/src/lib/Eina_Graph.h index 2a444d8..e5dbf0b 100644 --- a/src/lib/Eina_Graph.h +++ b/src/lib/Eina_Graph.h @@ -57,4 +57,6 @@ eina_graph_init(void); EAPI int eina_graph_shutdown(void); +#include <eina_graph.h> + #endif /* _EINA_GRAPH_MAIN_H */ diff --git a/src/lib/eina_graph.c b/src/lib/eina_graph.c new file mode 100644 index 0000000..1216efc --- /dev/null +++ b/src/lib/eina_graph.c @@ -0,0 +1,150 @@ +/* EINA_GRAPH - EFL graph processing library + * Copyright (C) 2013 Jérémy Zurcher + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies of the Software and its Copyright notices. In addition publicly + * documented acknowledgment must be given that this software has been used if no + * source code of this software is made available publicly. This includes + * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing + * documents or any documentation provided with any product containing this + * software. This License does not apply to any software that links to the + * libraries provided by this software (statically or dynamically), but only to + * the software provided. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER + * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifdef HAVE_CONFIG_H +# include <config.h> +#endif /* HAVE_CONFIG_H */ + +#include <eina_graph.h> +#include "eina_graph_private.h" + +EAPI Eina_Graph * +eina_graph_new(unsigned int v, unsigned int step) +{ + _Eina_Graph *_g; + + _g = calloc(1, sizeof(_Eina_Graph) + (v * sizeof(Eina_Graph_Adjacents))); + if (!_g) + { + ERR("calloc failed : %s", strerror(errno)); + return NULL; + } + + _g->step = step; + _g->vertices = v; + _g->adjs = (Eina_Graph_Adjacents *) ((char *) _g + sizeof(_Eina_Graph)); + + return (Eina_Graph *) _g; +} + +EAPI void +eina_graph_free(Eina_Graph *g) +{ + unsigned int i; + _Eina_Graph * _g = (_Eina_Graph *) g; + + for (i = 0; i< _g->vertices; i++) + eina_graph_adjacents_free(&_g->adjs[i]); + + free(_g); +} + +EAPI unsigned int +eina_graph_vertices_count(const Eina_Graph *g) +{ + _Eina_Graph * _g = (_Eina_Graph *) g; + + return _g->vertices; +} + +EAPI unsigned int +eina_graph_edges_count(const Eina_Graph *g) +{ + _Eina_Graph * _g = (_Eina_Graph *) g; + + return _g->edges; +} + +EAPI unsigned int +eina_graph_degree(const Eina_Graph *g, unsigned int v) +{ + _Eina_Graph * _g = (_Eina_Graph *) g; + + return _g->adjs[v].count; +} + +EAPI unsigned int +eina_graph_degree_max(const Eina_Graph *g) +{ + unsigned int i, n, max; + _Eina_Graph * _g = (_Eina_Graph *) g; + + max = 0; + for (i = 0; i< _g->vertices; i++) + { + n = _g->adjs[i].count; + if ( n > max ) max = n; + } + + return max; +} + +EAPI float +eina_graph_degree_avg(const Eina_Graph *g) +{ + _Eina_Graph * _g = (_Eina_Graph *) g; + + return (2.0 * _g->edges) / _g->vertices; +} + +EAPI unsigned int +eina_graph_self_loops(const Eina_Graph *g) +{ + unsigned int *data; + unsigned int i, j, n, loops; + _Eina_Graph * _g = (_Eina_Graph *) g; + + loops = 0; + for (i = 0; i< _g->vertices; i++) + { + n = _g->adjs[i].count; + data = _g->adjs[i].data; + for (j = 0; j < n; j++) + { + if(i == data[j]) loops++; + } + } + + return loops; +} + +EAPI Eina_Bool +eina_graph_edge_add(Eina_Graph *g, unsigned int v, unsigned int w) +{ + _Eina_Graph * _g = (_Eina_Graph *) g; + + if ((v >= _g->vertices) || (w >= _g->vertices)) return EINA_FALSE; + + if(!eina_graph_adjacents_push(&_g->adjs[v], w, _g->step)) return EINA_FALSE; + if (v != w ) + if(!eina_graph_adjacents_push(&_g->adjs[w], v, _g->step)) return EINA_FALSE; + + _g->edges++; + + return EINA_TRUE; +} diff --git a/src/lib/eina_graph.h b/src/lib/eina_graph.h new file mode 100644 index 0000000..c748ede --- /dev/null +++ b/src/lib/eina_graph.h @@ -0,0 +1,133 @@ +/* EINA_GRAPH - EFL graph processing library + * Copyright (C) 2013 Jérémy Zurcher + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies of the Software and its Copyright notices. In addition publicly + * documented acknowledgment must be given that this software has been used if no + * source code of this software is made available publicly. This includes + * acknowledgments in either Copyright notices, Manuals, Publicity and Marketing + * documents or any documentation provided with any product containing this + * software. This License does not apply to any software that links to the + * libraries provided by this software (statically or dynamically), but only to + * the software provided. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER + * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. + */ + +#ifndef _EINA_GRAPH_H +#define _EINA_GRAPH_H + +#include <eina_types.h> + +/** + * @typedef Eina_Graph + * The basic Eina_Graph type. + */ +typedef struct _Eina_Graph_Opaque Eina_Graph; + +/** + * returns a graph with v vertices. + * + * This function returns an unweighted undirected graph + * with self loops and parallel edges allowed. + * + * @param v the number of vertices. + * @param step grow step for the adjacent lists. + * + * @return a pointer to the Eina_Graph. + */ +EAPI Eina_Graph * +eina_graph_new(unsigned int v, unsigned int step); + +/** + * free the given graph. + * + * @param g the graph to free. + */ +EAPI void +eina_graph_free(Eina_Graph *g); + +/** + * returns the number of vertices of the graph. + * + * @param g the graph to consider. + * + * @return the number of vertices of the graph. + */ +EAPI unsigned int +eina_graph_vertices_count(const Eina_Graph *g); + +/** + * returns the number of edges of the graph. + * + * @param g the graph to consider. + * + * @return the number of edges of the graph. + */ +EAPI unsigned int +eina_graph_edges_count(const Eina_Graph *g); + +/** + * returns the degree of vertex v. + * + * @param g the graph to consider. + * @param v the vertex to get the degree of. + * + * @return the degree of vertex v + */ +EAPI unsigned int +eina_graph_degree(const Eina_Graph *g, unsigned int v); + +/** + * returns the max degree of the graph. + * + * @param g the graph to consider. + * + * @return the max degree of the graph. + */ +EAPI unsigned int +eina_graph_degree_max(const Eina_Graph *g); + +/** + * returns the average degree of the graph. + * + * @param g the graph to consider. + * + * @return the average degree of the graph. + */ +EAPI float +eina_graph_degree_avg(const Eina_Graph *g); + +/** + * returns the number of self loops in the graph. + * + * @param g the graph to consider. + * + * @return the number of self loops in the graph. + */ +EAPI unsigned int +eina_graph_self_loops(const Eina_Graph *g); + +/** + * add an edge to the graph. + * + * @param g the graph to add to edje to. + * @param v a vertex of the edge. + * @param w another vertex of the edge. + */ +EAPI Eina_Bool +eina_graph_edge_add(Eina_Graph *g, unsigned int v, unsigned int w); + +#endif /* _EINA_GRAPH_H */ diff --git a/src/lib/eina_graph_main.c b/src/lib/eina_graph_main.c index bd8be47..6eac08d 100644 --- a/src/lib/eina_graph_main.c +++ b/src/lib/eina_graph_main.c @@ -90,3 +90,20 @@ eina_graph_shutdown(void) return _eina_graph_init_count; } + +Eina_Bool +_eina_graph_adjacents_grow(Eina_Graph_Adjacents *adjs, unsigned int step) +{ + unsigned int *tmp; + unsigned int total; + + total = adjs->total + step; + tmp = realloc(adjs->data, sizeof (unsigned int) * total); + if (EINA_UNLIKELY(!tmp)) return EINA_FALSE; + + adjs->total = total; + adjs->data = tmp; + + return EINA_TRUE; +} + diff --git a/src/lib/eina_graph_private.h b/src/lib/eina_graph_private.h index a75ed6b..75dfffb 100644 --- a/src/lib/eina_graph_private.h +++ b/src/lib/eina_graph_private.h @@ -60,4 +60,42 @@ extern int _eina_graph_log_dom; #endif #define DBG(...) EINA_LOG_DOM_DBG(_eina_graph_log_dom, __VA_ARGS__) +typedef struct _Eina_Graph_Adjacents +{ + unsigned int *data; + unsigned int total; + unsigned int count; +} Eina_Graph_Adjacents; + +static inline void +eina_graph_adjacents_free(Eina_Graph_Adjacents *adjs) +{ + if (adjs->data) + free(adjs->data); + adjs->data = NULL; +} + +Eina_Bool +_eina_graph_adjacents_grow(Eina_Graph_Adjacents *adjs, unsigned int step); + +static inline Eina_Bool +eina_graph_adjacents_push(Eina_Graph_Adjacents *adjs, unsigned int v, unsigned int step) +{ + if (EINA_UNLIKELY((adjs->count + 1) > adjs->total)) + if (!_eina_graph_adjacents_grow(adjs, step)) + return EINA_FALSE; + + adjs->data[adjs->count++] = v; + + return EINA_TRUE; +} + +typedef struct _Eina_Graph +{ + unsigned int vertices; + unsigned int edges; + unsigned int step; + Eina_Graph_Adjacents *adjs; +} _Eina_Graph; + #endif /* _EINA_GRAPH_PRIVATE_H */ |