/*
Copyright Universite de Versailles Saint-Quentin en Yvelines 2009
AUTHORS: Sebastien Briais, Sid Touati
This file is part of GDD.
GDD is free software: you can redistribute it and/or modify it
under the terms of the GNU Lesser General Public License as
published by the Free Software Foundation, either version 3 of the
License, or (at your option) any later version.
GDD is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public
License along with GDD. If not, see
.
*/
#include
#include
#include
#include
#include "dag.h"
#include "util.h"
#if(GDD_DAG_PRECALC)
static void GDD_dag_delete_gf(GDD_DAG *ddg) {
if(ddg->gf == NULL) {
return;
}
SCEDA_graph_delete(ddg->gf);
SCEDA_hashmap_delete(ddg->g_to_gf);
ddg->gf = NULL;
ddg->g_to_gf = NULL;
}
static void GDD_dag_compute_gf(GDD_DAG *ddg) {
if(ddg->gf != NULL) {
return;
}
SCEDA_Graph *gf = SCEDA_graph_transitive_closure(ddg->g); // this also computes a topological order of g
ddg->gf = gf;
// fprintf(stderr,"|V| = %d, |E| = %d\n",SCEDA_graph_vcount(gf), SCEDA_graph_ecount(gf));
ddg->g_to_gf = SCEDA_vertex_map_create(NULL);
SCEDA_VerticesIterator gf_vertice;
SCEDA_vertices_iterator_init(gf, &gf_vertice);
while(SCEDA_vertices_iterator_has_next(&gf_vertice)) {
SCEDA_Vertex *vf = SCEDA_vertices_iterator_next(&gf_vertice);
SCEDA_Vertex *v = SCEDA_vertex_get_data(SCEDA_Vertex *, vf);
safe_call(SCEDA_hashmap_put(ddg->g_to_gf, v, vf, NULL));
}
SCEDA_vertices_iterator_cleanup(&gf_vertice);
}
#endif
static void GDD_dag_delete_precalc(GDD_DAG *ddg) {
#if(GDD_DAG_PRECALC)
GDD_dag_delete_gf(ddg);
#endif
}
static void GDD_dag_create_precalc(GDD_DAG *ddg) {
#if(GDD_DAG_PRECALC)
GDD_dag_compute_gf(ddg);
#endif
}
/** Updates the precomputed values. This should be called if the underlying GDD
structure change.
@param[in] ddg = GDD_DAG to update */
void GDD_dag_update(GDD_DAG *ddg) {
GDD_dag_delete_precalc(ddg);
GDD_dag_create_precalc(ddg);
}
/** Create a new GDD_DAG.
@param[in] g = underlying DAG
@return a GDD or NULL if g is not acyclic */
GDD_DAG *GDD_dag_create(SCEDA_Graph *g) {
if(!SCEDA_graph_is_acyclic(g)) {
return NULL;
}
GDD_DAG *ddg = (GDD_DAG *)safe_malloc(sizeof(GDD_DAG));
ddg->g = g;
ddg->gf = NULL;
ddg->g_to_gf = NULL;
// compute Gf
GDD_dag_update(ddg);
return ddg;
}
/** Delete a GDD_DAG.
@param[in] ddg = GDD_DAG to delete
The underlying graph and arch are not deleted. */
void GDD_dag_delete(GDD_DAG *ddg) {
GDD_dag_delete_precalc(ddg);
memset(ddg, 0, sizeof(GDD_DAG));
free(ddg);
}
/** Test whether there is a path from v1 to v2, where v1 and v2 are
two vertices of the underlying DAG.
@param[in] ddg = GDD_DAG
@param[in] v1 = first vertex
@param[in] v2 = second vertex
@return TRUE iff there is a path from v1 to v2 */
int GDD_dag_lt(GDD_DAG *ddg, SCEDA_Vertex *v1, SCEDA_Vertex *v2) {
#if(GDD_DAG_PRECALC)
SCEDA_Vertex *v1f = SCEDA_hashmap_get(ddg->g_to_gf, v1);
SCEDA_Vertex *v2f = SCEDA_hashmap_get(ddg->g_to_gf, v2);
return SCEDA_vertex_is_succ_of(v2f, v1f);
#else
if(v1 == v2) {
return FALSE;
}
int reachable = FALSE;
SCEDA_BFSIterator desc;
SCEDA_bfs_iterator_init(v1, &desc);
while(SCEDA_bfs_iterator_has_next(&desc)) {
SCEDA_Vertex *v = SCEDA_bfs_iterator_next(&desc);
if(v == v2) {
reachable = TRUE;
}
}
SCEDA_bfs_iterator_cleanup(&desc);
return reachable;
#endif
}
/** Test whether the two given vertices (of the underlying DAG) are
parallel.
@param[in] ddg = GDD_DAG
@param[in] v1 = first vertex
@param[in] v2 = second vertex
@return TRUE iff the two vertices are parallel */
int GDD_dag_parallel(GDD_DAG *ddg, SCEDA_Vertex *v1, SCEDA_Vertex *v2) {
#if(GDD_DAG_PRECALC)
SCEDA_Vertex *v1f = SCEDA_hashmap_get(ddg->g_to_gf, v1);
SCEDA_Vertex *v2f = SCEDA_hashmap_get(ddg->g_to_gf, v2);
if(SCEDA_vertex_is_succ_of(v2f, v1f)) {
return FALSE;
}
return (!(SCEDA_vertex_is_succ_of(v1f, v2f)));
#else
if(GDD_dag_lt(ddg, v1, v2)) {
return FALSE;
}
return (!GDD_dag_lt(ddg, v2, v1));
#endif
}
#if(GDD_DAG_PRECALC)
/** Initialise an upset iterator.
@param[in] ddg = GDD_DAG
@param[in] v = vertex
@param[in] iter = iterator */
void GDD_dag_upset_iterator_init(GDD_DAG *ddg, SCEDA_Vertex *v, GDD_DAG_UpsetIterator *dsiter) {
SCEDA_Vertex *vf = SCEDA_hashmap_get(ddg->g_to_gf, v);
SCEDA_vertex_succ_iterator_init(vf, dsiter);
}
#endif