summaryrefslogtreecommitdiffstats
path: root/src/lib
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib')
-rw-r--r--src/lib/eina_graph_bfs.c51
-rw-r--r--src/lib/eina_graph_dfs.c41
-rw-r--r--src/lib/eina_graph_private.h20
3 files changed, 54 insertions, 58 deletions
diff --git a/src/lib/eina_graph_bfs.c b/src/lib/eina_graph_bfs.c
index c1e67d7..80f6be7 100644
--- a/src/lib/eina_graph_bfs.c
+++ b/src/lib/eina_graph_bfs.c
@@ -38,12 +38,14 @@ _eina_graph_bfs_fwalk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v)
{
Eina_List *fifo = NULL;
_Eina_Graph_Adjacents *adjs;
+ _Eina_Graph_BFS_Data *vd;
unsigned int p, w, n, i, d;
d = 0;
- _bfs->marked[v] = EINA_TRUE;
- _bfs->edge_to[v] = v;
- _bfs->dist_to[v] = d;
+ vd = &_bfs->data[v];
+ vd->m = EINA_TRUE;
+ vd->e = v;
+ vd->d = d;
fifo = eina_list_append(fifo, CAST_V(v));
while (eina_list_count(fifo) > 0)
@@ -58,12 +60,13 @@ _eina_graph_bfs_fwalk(_Eina_Graph *_g, _Eina_Graph_BFS *_bfs, unsigned int v)
n = adjs->count;
for (i = 0; i < n; i++)
{
- w = adjs->data[i];
- if (!_bfs->marked[w])
+ w = adjs->data[i];
+ vd = &_bfs->data[w];
+ if (!vd->m)
{
- _bfs->marked[w] = EINA_TRUE;
- _bfs->edge_to[w] = p;
- _bfs->dist_to[w] = d;
+ vd->m = EINA_TRUE;
+ vd->e = p;
+ vd->d = d;
fifo = eina_list_append(fifo, CAST_V(w));
}
}
@@ -80,17 +83,9 @@ eina_graph_bfs_new(Eina_Graph *g, unsigned int s)
if (!_bfs)
goto error_bfs;
- _bfs->marked = calloc(_g->vertices, sizeof(Eina_Bool));
- if (!_bfs->marked)
- goto error_marked;
-
- _bfs->edge_to = calloc(_g->vertices, sizeof(unsigned int));
- if (!_bfs->edge_to)
- goto error_edge_to;
-
- _bfs->dist_to = calloc(_g->vertices, sizeof(unsigned int));
- if (!_bfs->dist_to)
- goto error_dist_to;
+ _bfs->data = calloc(_g->vertices, sizeof(_Eina_Graph_BFS_Data));
+ if (!_bfs->data)
+ goto error_data;
_bfs->s = s;
_bfs->vertices = _g->vertices;
@@ -99,11 +94,7 @@ eina_graph_bfs_new(Eina_Graph *g, unsigned int s)
return (Eina_Graph_BFS *) _bfs;
-error_dist_to:
- free(_bfs->edge_to);
-error_edge_to:
- free(_bfs->marked);
-error_marked:
+error_data:
free(_bfs);
error_bfs:
ERR("calloc failed : %s", strerror(errno));
@@ -115,9 +106,7 @@ eina_graph_bfs_free(Eina_Graph_BFS *bfs)
{
_Eina_Graph_BFS *_bfs = (_Eina_Graph_BFS *) bfs;
- free(_bfs->marked);
- free(_bfs->edge_to);
- free(_bfs->dist_to);
+ free(_bfs->data);
free(_bfs);
}
@@ -140,7 +129,7 @@ eina_graph_bfs_has_path_to(Eina_Graph_BFS *bfs, unsigned int v)
return EINA_FALSE;
}
- return _bfs->marked[v];
+ return _bfs->data[v].m;
}
EAPI Eina_List *
@@ -156,13 +145,13 @@ eina_graph_bfs_path_to(Eina_Graph_BFS *bfs, unsigned int v)
return NULL;
}
- if (!_bfs->marked[v])
+ if (!_bfs->data[v].m)
return NULL;
while (w != _bfs->s)
{
path = eina_list_prepend(path, CAST_V(w));
- w = _bfs->edge_to[w];
+ w = _bfs->data[w].e;
}
path = eina_list_prepend(path, CAST_V(_bfs->s));
@@ -180,5 +169,5 @@ eina_graph_bfs_dist_to(Eina_Graph_BFS *bfs, unsigned int v)
return UINT_MAX;
}
- return _bfs->dist_to[v];
+ return _bfs->data[v].d;
}
diff --git a/src/lib/eina_graph_dfs.c b/src/lib/eina_graph_dfs.c
index 7951b3c..1b9a61a 100644
--- a/src/lib/eina_graph_dfs.c
+++ b/src/lib/eina_graph_dfs.c
@@ -38,6 +38,7 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
{
Eina_List *stack = NULL;
_Eina_Graph_Adjacents *adjs;
+ _Eina_Graph_DFS_Data *vd;
unsigned int p, w, n, i;
p = v;
@@ -48,9 +49,10 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
w = CAST_D(eina_list_data_get(stack));
stack = eina_list_remove(stack, CAST_V(w));
- if(_dfs->marked[w]) continue;
- _dfs->marked[w] = EINA_TRUE;
- _dfs->edge_to[w] = p;
+ vd = &_dfs->data[w];
+ if(vd->m) continue;
+ vd->m = EINA_TRUE;
+ vd->e = p;
p = w;
adjs = &_g->adjs[w];
@@ -58,7 +60,7 @@ _eina_graph_dfs_swalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
for (i = 0; i < n; i++)
{
w = adjs->data[i];
- if (!_dfs->marked[w])
+ if (!_dfs->data[w].m)
{
stack = eina_list_prepend(stack, CAST_V(w));
}
@@ -70,19 +72,21 @@ static void
_eina_graph_dfs_rwalk(_Eina_Graph *_g, _Eina_Graph_DFS *_dfs, unsigned int v)
{
_Eina_Graph_Adjacents *adjs;
+ _Eina_Graph_DFS_Data *vd;
unsigned int i, n, w;
- _dfs->marked[v] = EINA_TRUE;
+ _dfs->data[v].m = EINA_TRUE;
adjs = &_g->adjs[v];
n = adjs->count;
for (i = 0; i < n; i++)
{
w = adjs->data[i];
- if (!_dfs->marked[w])
+ vd = &_dfs->data[w];
+ if (!vd->m)
{
_eina_graph_dfs_rwalk(_g, _dfs, w);
- _dfs->edge_to[w] = v;
+ vd->e = v;
}
}
}
@@ -97,13 +101,9 @@ eina_graph_dfs_new(Eina_Graph *g, unsigned int s, Eina_Bool r)
if (!_dfs)
goto error_dfs;
- _dfs->marked = calloc(_g->vertices, sizeof(Eina_Bool));
- if (!_dfs->marked)
- goto error_marked;
-
- _dfs->edge_to = calloc(_g->vertices, sizeof(unsigned int));
- if (!_dfs->edge_to)
- goto error_edge_to;
+ _dfs->data = calloc(_g->vertices, sizeof(_Eina_Graph_DFS_Data));
+ if (!_dfs->data)
+ goto error_data;
_dfs->s = s;
_dfs->vertices = _g->vertices;
@@ -115,9 +115,7 @@ eina_graph_dfs_new(Eina_Graph *g, unsigned int s, Eina_Bool r)
return (Eina_Graph_DFS *) _dfs;
-error_edge_to:
- free(_dfs->marked);
-error_marked:
+error_data:
free(_dfs);
error_dfs:
ERR("calloc failed : %s", strerror(errno));
@@ -129,8 +127,7 @@ eina_graph_dfs_free(Eina_Graph_DFS *dfs)
{
_Eina_Graph_DFS *_dfs = (_Eina_Graph_DFS *) dfs;
- free(_dfs->marked);
- free(_dfs->edge_to);
+ free(_dfs->data);
free(_dfs);
}
@@ -153,7 +150,7 @@ eina_graph_dfs_has_path_to(Eina_Graph_DFS *dfs, unsigned int v)
return EINA_FALSE;
}
- return _dfs->marked[v];
+ return _dfs->data[v].m;
}
EAPI Eina_List *
@@ -169,13 +166,13 @@ eina_graph_dfs_path_to(Eina_Graph_DFS *dfs, unsigned int v)
return NULL;
}
- if (!_dfs->marked[v])
+ if (!_dfs->data[v].m)
return NULL;
while (w != _dfs->s)
{
path = eina_list_prepend(path, CAST_V(w));
- w = _dfs->edge_to[w];
+ w = _dfs->data[w].e;
}
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 ccbff01..526e4e4 100644
--- a/src/lib/eina_graph_private.h
+++ b/src/lib/eina_graph_private.h
@@ -103,21 +103,31 @@ typedef struct _Eina_Graph
_Eina_Graph_Adjacents *adjs;
} _Eina_Graph;
+typedef struct _Eina_Graph_DFS_Data
+{
+ Eina_Bool m;
+ unsigned int e;
+} _Eina_Graph_DFS_Data;
+
typedef struct _Eina_Graph_DFS
{
unsigned int s;
unsigned int vertices;
- Eina_Bool *marked;
- unsigned int *edge_to;
+ _Eina_Graph_DFS_Data *data;
} _Eina_Graph_DFS;
+typedef struct _Eina_Graph_BFS_Data
+{
+ Eina_Bool m;
+ unsigned int e;
+ unsigned int d;
+} _Eina_Graph_BFS_Data;
+
typedef struct _Eina_Graph_BFS
{
unsigned int s;
unsigned int vertices;
- Eina_Bool *marked;
- unsigned int *edge_to;
- unsigned int *dist_to;
+ _Eina_Graph_BFS_Data *data;
} _Eina_Graph_BFS;
#endif /* _EINA_GRAPH_PRIVATE_H */
generated by cgit v1.1-2-g2b99 at 2024-11-21 16:59:05 +0100