projects
/
mtp.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Updated the header.
[mtp.git]
/
mtp.cc
diff --git
a/mtp.cc
b/mtp.cc
index
307da22
..
88e6557
100644
(file)
--- a/
mtp.cc
+++ b/
mtp.cc
@@
-18,7
+18,11
@@
// Multi-Tracked Path
// Multi-Tracked Path
-// #define VERBOSE
+// Takes the graph description file as input and produces a dot file.
+
+// EXAMPLE: ./mtp ./graph2.txt | dot -T pdf -o- | xpdf -
+
+#define VERBOSE
#include <iostream>
#include <fstream>
#include <iostream>
#include <fstream>
@@
-52,11
+56,9
@@
public:
class Vertex {
public:
class Vertex {
public:
- int id;
-
+ int id, iteration;
Edge *root_edge;
scalar_t distance_from_source;
Edge *root_edge;
scalar_t distance_from_source;
-
Vertex *pred_vertex;
Edge *pred_edge;
Vertex *pred_vertex;
Edge *pred_edge;
@@
-85,7
+87,6
@@
class Graph {
Edge *edge_heap;
Vertex *vertices;
Vertex *source, *sink;
Edge *edge_heap;
Vertex *vertices;
Vertex *source, *sink;
-
public:
Graph(int nb_vertices, int nb_edges, int *from, int *to, scalar_t *lengths,
int source, int sink);
public:
Graph(int nb_vertices, int nb_edges, int *from, int *to, scalar_t *lengths,
int source, int sink);
@@
-166,30
+167,43
@@
void Graph::find_shortest_path(Vertex **front, Vertex **new_front) {
Vertex *v, *tv;
scalar_t d;
Vertex *v, *tv;
scalar_t d;
+#ifdef VERBOSE
+ cout << "find_shortest_path" << endl;
+#endif
+
#ifdef DEBUG
#ifdef DEBUG
+ scalar_t residual_error = 0.0;
+#endif
for(int n = 0; n < nb_vertices; n++) {
for(Edge *e = vertices[n].root_edge; e; e = e->next) {
if(e->work_length < 0) {
for(int n = 0; n < nb_vertices; n++) {
for(Edge *e = vertices[n].root_edge; e; e = e->next) {
if(e->work_length < 0) {
- cerr << "DEBUG error in find_shortest_path: Edge fixed lengths have to be positive."
- << endl;
- abort();
+#ifdef DEBUG
+ residual_error -= e->work_length;
+#endif
+ e->work_length = 0.0;
}
}
}
}
}
}
+#ifdef DEBUG
+ cout << "DEBUG residual_error " << residual_error << endl;
#endif
for(int v = 0; v < nb_vertices; v++) {
vertices[v].distance_from_source = FLT_MAX;
vertices[v].pred_vertex = 0;
vertices[v].pred_edge = 0;
#endif
for(int v = 0; v < nb_vertices; v++) {
vertices[v].distance_from_source = FLT_MAX;
vertices[v].pred_vertex = 0;
vertices[v].pred_edge = 0;
+ vertices[v].iteration = 0;
}
}
+ int iteration = 0;
+
int front_size = 0, new_front_size;
front[front_size++] = source;
source->distance_from_source = 0;
do {
new_front_size = 0;
int front_size = 0, new_front_size;
front[front_size++] = source;
source->distance_from_source = 0;
do {
new_front_size = 0;
+ iteration++;
for(int f = 0; f < front_size; f++) {
v = front[f];
for(Edge *e = v->root_edge; e; e = e->next) {
for(int f = 0; f < front_size; f++) {
v = front[f];
for(Edge *e = v->root_edge; e; e = e->next) {
@@
-199,7
+213,10
@@
void Graph::find_shortest_path(Vertex **front, Vertex **new_front) {
tv->distance_from_source = d;
tv->pred_vertex = v;
tv->pred_edge = e;
tv->distance_from_source = d;
tv->pred_vertex = v;
tv->pred_edge = e;
- new_front[new_front_size++] = tv;
+ if(tv->iteration < iteration) {
+ new_front[new_front_size++] = tv;
+ tv->iteration = iteration;
+ }
}
}
}
}
}
}
@@
-319,10
+336,10
@@
int main(int argc, char **argv) {
source, sink,
result_edge_occupation);
source, sink,
result_edge_occupation);
- dot_print(nb_vertices, nb_edges,
- vertex_from, vertex_to, edge_lengths,
- source, sink,
- result_edge_occupation);
+
//
dot_print(nb_vertices, nb_edges,
+
//
vertex_from, vertex_to, edge_lengths,
+
//
source, sink,
+
//
result_edge_occupation);
delete[] result_edge_occupation;
delete[] edge_lengths;
delete[] result_edge_occupation;
delete[] edge_lengths;