From 968e95ae0f9bb6a7c68d1ed80f3e9055787c2311 Mon Sep 17 00:00:00 2001 From: Francois Fleuret Date: Fri, 28 Dec 2012 23:55:59 +0100 Subject: [PATCH] A new version of compute_dp_ranks, orders of magnitude faster. --- mtp_graph.cc | 71 +++++++++++++++++++++++++++++++--------------------- 1 file changed, 43 insertions(+), 28 deletions(-) diff --git a/mtp_graph.cc b/mtp_graph.cc index dc38321..0fe3cf0 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -192,6 +192,7 @@ MTPGraph::~MTPGraph() { void MTPGraph::compute_dp_ranks() { Vertex *v; Edge *e; + int tv; // This procedure computes for each node the longest link from the // source and abort if the graph is not a DAG. It works by removing @@ -203,47 +204,61 @@ void MTPGraph::compute_dp_ranks() { // rank of a node is the iteration at which is it removed, and we // set the distance_from_source fields to this value. - Vertex **with_predecessor = new Vertex *[_nb_vertices]; + int *nb_predecessors = new int[_nb_vertices]; + int *without_predecessors = new int[_nb_vertices]; + int *new_without_predecessors = new int[_nb_vertices]; + int nb_without_predecessors, new_nb_without_predecessors; - // All the nodes are with_predecessor at first for(int k = 0; k < _nb_vertices; k++) { - _vertices[k].distance_from_source = 0; - with_predecessor[k] = &_vertices[k]; + nb_predecessors[k] = 0; } - scalar_t rank = 1; - int nb_with_predecessor = _nb_vertices, pred_nb_with_predecessor; - - do { - // We set the distance_from_source field of all the vertices with incoming - // edges to the current rank value - for(int f = 0; f < nb_with_predecessor; f++) { - v = with_predecessor[f]; - for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) { - e->terminal_vertex->distance_from_source = rank; - } + for(int k = 0; k < _nb_vertices; k++) { + v = _vertices + k; + for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) { + tv = e->terminal_vertex - _vertices; + nb_predecessors[tv]++; } + } - pred_nb_with_predecessor = nb_with_predecessor; - nb_with_predecessor = 0; + nb_without_predecessors = 0; + for(int k = 0; k < _nb_vertices; k++) { + if(nb_predecessors[k] == 0) { + without_predecessors[nb_without_predecessors++] = k; + } + } - // We keep all the vertices with incoming nodes - for(int f = 0; f < pred_nb_with_predecessor; f++) { - v = with_predecessor[f]; - if(v->distance_from_source == rank) { - with_predecessor[nb_with_predecessor++] = v; + scalar_t rank = 1; + while(nb_without_predecessors > 0) { + new_nb_without_predecessors = 0; + for(int l = 0; l < nb_without_predecessors; l++) { + v = _vertices + without_predecessors[l]; + v->distance_from_source = rank; + for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) { + tv = e->terminal_vertex - _vertices; + nb_predecessors[tv]--; + ASSERT(nb_predecessors[tv] >= 0); + if(nb_predecessors[tv] == 0) { + new_without_predecessors[new_nb_without_predecessors++] = tv; + } } } + swap(without_predecessors, new_without_predecessors); + nb_without_predecessors = new_nb_without_predecessors; rank++; - } while(nb_with_predecessor < pred_nb_with_predecessor); - - delete[] with_predecessor; + } - if(nb_with_predecessor > 0) { - cerr << __FILE__ << ": The graph is not a DAG." << endl; - abort(); + for(int k = 0; k < _nb_vertices; k++) { + if(nb_predecessors[k] > 0) { + cerr << __FILE__ << ": The graph is not a DAG." << endl; + abort(); + } } + + delete[] nb_predecessors; + delete[] without_predecessors; + delete[] new_without_predecessors; } ////////////////////////////////////////////////////////////////////// -- 2.39.5