X-Git-Url: https://fleuret.org/cgi-bin/gitweb/gitweb.cgi?a=blobdiff_plain;f=mtp_graph.cc;h=c17917ee675a3ed61eed111ba4965b9cfa0c0647;hb=9d423de49725cbb204657653340f8585a0557f55;hp=7cd7e52b0248ad960dba87aeef6e0dc10b825ba8;hpb=4370046158668af82bad9e18802b184cb00467b5;p=mtp.git diff --git a/mtp_graph.cc b/mtp_graph.cc index 7cd7e52..c17917e 100644 --- a/mtp_graph.cc +++ b/mtp_graph.cc @@ -133,17 +133,6 @@ void Vertex::increase_distance_in_heap(Vertex **heap, Vertex **heap_bottom) { ////////////////////////////////////////////////////////////////////// -static int compare_vertices_on_distance(const void *v1, const void *v2) { - scalar_t delta = - (*((Vertex **) v1))->distance_from_source - - (*((Vertex **) v2))->distance_from_source; - if(delta < 0) return -1; - else if(delta > 0) return 1; - else return 0; -} - -////////////////////////////////////////////////////////////////////// - MTPGraph::MTPGraph(int nb_vertices, int nb_edges, int *vertex_from, int *vertex_to, int source, int sink) { @@ -173,9 +162,7 @@ MTPGraph::MTPGraph(int nb_vertices, int nb_edges, paths = 0; nb_paths = 0; - compute_dp_ranks(); - for(int v = 0; v < _nb_vertices; v++) { _dp_order[v] = &_vertices[v]; } - qsort(_dp_order, _nb_vertices, sizeof(Vertex *), compare_vertices_on_distance); + compute_dp_ordering(); } MTPGraph::~MTPGraph() { @@ -189,80 +176,6 @@ 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 - // successively nodes without predecessor: At the first iteration it - // removes the source, then the nodes with incoming edge only from - // the source, etc. If it can remove all the nodes that way, the - // graph is a DAG. If at some point it can not remove node anymore - // and there are some remaining nodes, the graph is not a DAG. The - // rank of a node is the iteration at which is it removed, and we - // set the distance_from_source fields to this value. - - int *nb_predecessors = new int[_nb_vertices]; - int *without_predecessor = new int[_nb_vertices]; - int *new_without_predecessor = new int[_nb_vertices]; - int nb_without_predecessor, new_nb_without_predecessor; - - for(int k = 0; k < _nb_vertices; k++) { - nb_predecessors[k] = 0; - } - - 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 = int(e->terminal_vertex - _vertices); - nb_predecessors[tv]++; - } - } - - nb_without_predecessor = 0; - for(int k = 0; k < _nb_vertices; k++) { - if(nb_predecessors[k] == 0) { - without_predecessor[nb_without_predecessor++] = k; - } - } - - scalar_t rank = 1; - while(nb_without_predecessor > 0) { - new_nb_without_predecessor = 0; - for(int l = 0; l < nb_without_predecessor; l++) { - v = &_vertices[without_predecessor[l]]; - v->distance_from_source = rank; - for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) { - tv = int(e->terminal_vertex - _vertices); - nb_predecessors[tv]--; - ASSERT(nb_predecessors[tv] >= 0); - if(nb_predecessors[tv] == 0) { - new_without_predecessor[new_nb_without_predecessor++] = tv; - } - } - } - - swap(without_predecessor, new_without_predecessor); - nb_without_predecessor = new_nb_without_predecessor; - rank++; - } - - 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_predecessor; - delete[] new_without_predecessor; -} - -////////////////////////////////////////////////////////////////////// - void MTPGraph::print(ostream *os) { for(int k = 0; k < _nb_edges; k++) { Edge *e = &_edges[k]; @@ -504,6 +417,80 @@ int MTPGraph::retrieve_one_path(Edge *e, Path *path) { return l; } +////////////////////////////////////////////////////////////////////// + +static int compare_vertices_on_distance(const void *v1, const void *v2) { + scalar_t delta = + (*((Vertex **) v1))->distance_from_source - + (*((Vertex **) v2))->distance_from_source; + if(delta < 0) return -1; + else if(delta > 0) return 1; + else return 0; +} + +void MTPGraph::compute_dp_ordering() { + Vertex *v; + Edge *e; + int ntv; + + // This method computes for each node the length of the longest link + // from the source, and orders the node in _dp_order according to + // it. It aborts if the graph is not a DAG. + + int *nb_predecessors = new int[_nb_vertices]; + + Vertex **already_processed = _dp_order, **front = _dp_order, **new_front = _dp_order; + + for(int k = 0; k < _nb_vertices; k++) { + nb_predecessors[k] = 0; + } + + for(int k = 0; k < _nb_vertices; k++) { + v = &_vertices[k]; + for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) { + ntv = int(e->terminal_vertex - _vertices); + nb_predecessors[ntv]++; + } + } + + for(int k = 0; k < _nb_vertices; k++) { + if(nb_predecessors[k] == 0) { + *(front++) = _vertices + k; + } + } + + scalar_t rank = 1; + while(already_processed < front) { + new_front = front; + while(already_processed < front) { + v = *(already_processed++); + v->distance_from_source = rank; + for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) { + ntv = int(e->terminal_vertex - _vertices); + nb_predecessors[ntv]--; + ASSERT(nb_predecessors[ntv] >= 0); + if(nb_predecessors[ntv] == 0) { + *(new_front++) = e->terminal_vertex; + } + } + } + front = new_front; + rank++; + } + + if(already_processed < _dp_order + _nb_vertices) { + cerr << __FILE__ << ": The graph is not a DAG." << endl; + abort(); + } + + delete[] nb_predecessors; + + for(int v = 0; v < _nb_vertices; v++) { _dp_order[v] = &_vertices[v]; } + qsort(_dp_order, _nb_vertices, sizeof(Vertex *), compare_vertices_on_distance); +} + +////////////////////////////////////////////////////////////////////// + void MTPGraph::retrieve_disjoint_paths() { Edge *e; int p, l;