}
}
-void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) {
- Vertex **tmp_front;
- int tmp_front_size;
- Vertex *v, *tv;
- scalar_t d;
-
+void MTPGraph::force_positive_work_lengths() {
#ifdef VERBOSE
scalar_t residual_error = 0.0;
#endif
#ifdef VERBOSE
cerr << "residual_error " << residual_error << endl;
#endif
+}
+
+void MTPGraph::find_shortest_path(Vertex **_front, Vertex **_new_front) {
+ Vertex **tmp_front;
+ int tmp_front_size;
+ Vertex *v, *tv;
+ scalar_t d;
for(int v = 0; v < _nb_vertices; v++) {
vertices[v].distance_from_source = FLT_MAX;
for(int e = 0; e < _nb_edges; e++) {
edges[e].length = lengths[e];
+ edges[e].work_length = edges[e].length;
}
- initialize_work_lengths();
+ find_shortest_path(_front, _new_front);
+ update_work_lengths();
+
+ // initialize_work_lengths();
do {
- total_length = 0.0;
+ force_positive_work_lengths();
find_shortest_path(_front, _new_front);
update_work_lengths();
+ total_length = 0.0;
+
// Do we reach the _sink?
if(_sink->pred_edge) {
}
}
}
+
} while(total_length < 0.0);
+ for(Edge *e = _sink->root_edge; e; e = e->next) {
+ if(e->occupied) {
+ Edge *f = e;
+ cout << "PATH " << _sink->id;
+ while(f) {
+ cout << " " << f->terminal_vertex->id;
+ for(f = f->terminal_vertex->root_edge; f && !f->occupied; f = f->next);
+ }
+ cout << endl;
+ }
+ }
+
for(int n = 0; n < _nb_vertices; n++) {
Vertex *v = &vertices[n];
for(Edge *e = v->root_edge; e; e = e->next) {