/* 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