cout << "}" << endl;
}
-
-void dot_print(int nb_vertices,
- int nb_edges, int *ea, int *eb, scalar_t *el,
- int _source, int _sink,
- int *edge_occupation) {
- for(int e = 0; e < nb_edges; e++) {
- }
- cout << "}" << endl;
-}
MTPGraph::MTPGraph(int nb_vertices, int nb_edges,
int *from, int *to,
int src, int snk) {
edges = new Edge[_nb_edges];
vertices = new Vertex[_nb_vertices];
+ _front = new Vertex *[_nb_vertices];
+ _new_front = new Vertex *[_nb_vertices];
_source = &vertices[src];
_sink = &vertices[snk];
edges[e].terminal_vertex = &vertices[to[e]];
}
- _front = new Vertex *[_nb_vertices];
- _new_front = new Vertex *[_nb_vertices];
}
MTPGraph::~MTPGraph() {
}
}
-void MTPGraph::update_work_length() {
+void MTPGraph::update_work_lengths() {
for(int n = 0; n < _nb_vertices; n++) {
scalar_t d = vertices[n].distance_from_source;
for(Edge *e = vertices[n].root_edge; e; e = e->next) {
}
}
-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_length();
+ 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) {