-void dot_print(int nb_vertices,
- int nb_edges, int *ea, int *eb, scalar_t *el,
- int source, int sink,
- int *edge_occupation) {
- cout << "digraph {" << endl;
- cout << " node[shape=circle];" << endl;
- for(int e = 0; e < nb_edges; e++) {
- if(edge_occupation[e]) {
- cout << " " << ea[e] << " -> " << eb[e] << " [style=bold,color=black,label=\"" << el[e] << "\"];" << endl;
- } else {
- cout << " " << ea[e] << " -> " << eb[e] << " [color=gray,label=\"" << el[e] << "\"];" << endl;
+//////////////////////////////////////////////////////////////////////
+
+void MTPGraph::compute_dp_ordering() {
+ Vertex *v;
+ Edge *e;
+ int ntv;
+
+ // This method orders the nodes by putting first the ones with no
+ // predecessors, then going on adding nodes whose predecessors have
+ // all been already added. Computing the distances from the source
+ // by visiting nodes in that order is equivalent to DP.
+
+ 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;
+ }
+ }
+
+ while(already_processed < front) {
+ // Here, nodes before already_processed can be ignored, nodes
+ // before front were set to 0 predecessors during the previous
+ // iteration. During this new iteration, we have to visit the
+ // successors of these ones only, since they are the only ones
+ // which may end up with no predecessors.
+ new_front = front;
+ while(already_processed < front) {
+ v = *(already_processed++);
+ 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;
+ }
+
+ if(already_processed < _dp_order + _nb_vertices) {
+ cerr << __FILE__ << ": The graph is not a DAG." << endl;
+ abort();
+ }
+
+ delete[] nb_predecessors;
+}
+
+//////////////////////////////////////////////////////////////////////
+
+void MTPGraph::retrieve_disjoint_paths() {
+ Edge *e;
+ int p, l;
+ int *used_edges;
+
+ for(int p = 0; p < nb_paths; p++) delete paths[p];
+ delete[] paths;
+
+ nb_paths = 0;
+ for(e = _source->leaving_edge_list_root; e; e = e->next_leaving_edge) {
+ if(e->occupied) { nb_paths++; }
+ }
+
+ paths = new Path *[nb_paths];
+ used_edges = new int[_nb_edges];
+ for(int e = 0; e < _nb_edges; e++) {
+ used_edges[e] = 0;
+ }
+
+ p = 0;
+ for(e = _source->leaving_edge_list_root; e; e = e->next_leaving_edge) {
+ if(e->occupied && !used_edges[e - _edges]) {
+ l = retrieve_one_path(e, 0, used_edges);
+ paths[p] = new Path(l);
+ retrieve_one_path(e, paths[p], used_edges);
+ used_edges[e - _edges] = 1;
+ p++;