diff options
| -rw-r--r-- | src/lib/eina_graph_bfs.c | 6 | ||||
| -rw-r--r-- | src/lib/eina_graph_dfs.c | 16 | ||||
| -rw-r--r-- | src/lib/eina_graph_private.h | 28 |
3 files changed, 23 insertions, 27 deletions
diff --git a/src/lib/eina_graph_bfs.c b/src/lib/eina_graph_bfs.c index c2f2f63..5631683 100644 --- a/src/lib/eina_graph_bfs.c +++ b/src/lib/eina_graph_bfs.c @@ -71,7 +71,7 @@ _eina_graph_bfs_walk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, dst = 0; vd = &_bfs->data[s]; vd->m = EINA_TRUE; - vd->e = s; + vd->p = s; vd->d = dst; fifo = eina_list_append(fifo, CAST_V(s)); @@ -90,7 +90,7 @@ _eina_graph_bfs_walk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, if (!vd->m) { vd->m = EINA_TRUE; - vd->e = p; + vd->p = p; vd->d = dst; if (has_target && (d == w)) { @@ -188,7 +188,7 @@ eina_graph_bfs_path_get(Eina_Graph_BFS *bfs, unsigned int v) while (w != _bfs->s) { path = eina_list_prepend(path, CAST_V(w)); - w = _bfs->data[w].e; + w = _bfs->data[w].p; } path = eina_list_prepend(path, CAST_V(_bfs->s)); diff --git a/src/lib/eina_graph_dfs.c b/src/lib/eina_graph_dfs.c index 3488185..2476de6 100644 --- a/src/lib/eina_graph_dfs.c +++ b/src/lib/eina_graph_dfs.c @@ -39,7 +39,6 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, { Eina_Array *stack = NULL; Eina_Array *adjs; - _Eina_Graph_DFS_Data *vd; unsigned int p, w, n, i; p = v; @@ -51,10 +50,9 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, w = eina_array_top_uint_get(stack); eina_array_pop(stack); - vd = &_dfs->data[w]; - if(vd->m) continue; - vd->m = EINA_TRUE; - vd->e = p; + if (_dfs->data[w].m) continue; + _dfs->data[w].m = EINA_TRUE; + _dfs->data[w].p = p; p = w; adjs = _g->adjs[w]; @@ -74,7 +72,6 @@ static void _eina_graph_dfs_rwalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v) { Eina_Array *adjs; - _Eina_Graph_DFS_Data *vd; unsigned int i, n, w; _dfs->data[v].m = EINA_TRUE; @@ -84,11 +81,10 @@ _eina_graph_dfs_rwalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v) for (i = 0; i < n; i++) { w = eina_array_uint_nth_get(adjs, i); - vd = &_dfs->data[w]; - if (!vd->m) + if (!_dfs->data[w].m) { + _dfs->data[w].p = v; _eina_graph_dfs_rwalk(_g, _dfs, w); - vd->e = v; } } } @@ -174,7 +170,7 @@ eina_graph_dfs_path_get(Eina_Graph_DFS *dfs, unsigned int v) while (w != _dfs->s) { path = eina_list_prepend(path, CAST_V(w)); - w = _dfs->data[w].e; + w = _dfs->data[w].p; } path = eina_list_prepend(path, CAST_V(_dfs->s)); diff --git a/src/lib/eina_graph_private.h b/src/lib/eina_graph_private.h index 1925cf7..122650e 100644 --- a/src/lib/eina_graph_private.h +++ b/src/lib/eina_graph_private.h @@ -93,36 +93,36 @@ eina_array_top_uint_get(const Eina_Array *array) typedef struct _Eina_Graph { - unsigned int vertices; - unsigned int edges; - Eina_Array *adjs[]; + unsigned int vertices; // count + unsigned int edges; // count + Eina_Array *adjs[]; // adjacent lists } _Eina_Graph; typedef struct _Eina_Graph_DFS_Data { - Eina_Bool m; - unsigned int e; + Eina_Bool m; // marked + unsigned int p; // parent } _Eina_Graph_DFS_Data; typedef struct _Eina_Graph_DFS { - unsigned int s; - unsigned int vertices; - _Eina_Graph_DFS_Data *data; + unsigned int s; // source + unsigned int vertices; // count + _Eina_Graph_DFS_Data *data; // data array } _Eina_Graph_DFS; typedef struct _Eina_Graph_BFS_Data { - Eina_Bool m; - unsigned int e; - unsigned int d; + Eina_Bool m; // marked + unsigned int p; // parent + unsigned int d; // dist } _Eina_Graph_BFS_Data; typedef struct _Eina_Graph_BFS { - unsigned int s; - unsigned int vertices; - _Eina_Graph_BFS_Data *data; + unsigned int s; // source + unsigned int vertices; // count + _Eina_Graph_BFS_Data *data; // data array } _Eina_Graph_BFS; #endif /* _EINA_GRAPH_PRIVATE_H */ |