-void MTPGraph::initialize_work_lengths() {
- scalar_t length_min = 0;
- for(int n = 0; n < _nb_vertices; n++) {
- for(Edge *e = vertices[n].root_edge; e; e = e->next) {
- length_min = min(e->length, length_min);
- }
+int MTPGraph::compute_dp_ranks() {
+ Vertex *v;
+ Edge *e;
+
+ // 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.
+
+ Vertex **active = new Vertex *[_nb_vertices];
+
+ // All the nodes are active at first
+ for(int k = 0; k < _nb_vertices; k++) {
+ _vertices[k].distance_from_source = 0;
+ active[k] = &_vertices[k];