+
+ for(int k = 0; k < _nb_vertices; k++) {
+ if(nb_predecessors[k] == 0) {
+ *(front++) = _vertices + k;
+ }
+ }
+
+ scalar_t rank = 1;
+ while(already_processed < front) {
+ fresh = 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) {
+ tv = int(e->terminal_vertex - _vertices);
+ nb_predecessors[tv]--;
+ ASSERT(nb_predecessors[tv] >= 0);
+ if(nb_predecessors[tv] == 0) {
+ *(fresh++) = e->terminal_vertex;
+ }
+ }
+ }
+ front = fresh;
+ rank++;
+ }
+
+ if(already_processed < bunch + _nb_vertices) {
+ cerr << __FILE__ << ": The graph is not a DAG." << endl;
+ abort();
+ }
+
+ delete[] nb_predecessors;
+ delete[] bunch;
+}
+
+//////////////////////////////////////////////////////////////////////
+
+void MTPGraph::print(ostream *os) {
+ for(int k = 0; k < _nb_edges; k++) {
+ Edge *e = &_edges[k];
+ (*os) << e->origin_vertex - _vertices
+ << " -> "
+ << e->terminal_vertex - _vertices
+ << " (" << e->length << ")";
+ if(e->occupied) { (*os) << " *"; }
+ (*os) << endl;
+ }
+}
+
+void MTPGraph::print_dot(ostream *os) {
+ (*os) << "digraph {" << endl;
+ (*os) << " rankdir=\"LR\";" << endl;
+ (*os) << " node [shape=circle,width=0.75,fixedsize=true];" << endl;
+ (*os) << " edge [color=gray,arrowhead=open]" << endl;
+ (*os) << " " << _source - _vertices << " [peripheries=2];" << endl;
+ (*os) << " " << _sink - _vertices << " [peripheries=2];" << endl;
+ for(int k = 0; k < _nb_edges; k++) {
+ Edge *e = &_edges[k];
+ (*os) << " "
+ << e->origin_vertex - _vertices
+ << " -> "
+ << e->terminal_vertex - _vertices
+ << " [";
+ if(e->occupied) {
+ (*os) << "style=bold,color=black,";