Removed miniksp, cosmetics on mtp.

[mtp.git] / mtp.cc

diff --git a/mtp.cc b/mtp.cc
index 94dde64..307da22 100644 (file)
--- a/mtp.cc
+++ b/mtp.cc
@@ -44,7 +44,7 @@ class Vertex;
 
 class Edge {
 public:
-  int occupied;
+  int id, occupied;
   scalar_t length, work_length;
   Vertex *terminal_vertex;
   Edge *next, *pred;
@@ -54,23 +54,23 @@ class Vertex {
 public:
   int id;
 
-  Edge *first_edge;
+  Edge *root_edge;
   scalar_t distance_from_source;
 
   Vertex *pred_vertex;
   Edge *pred_edge;
 
-  Vertex() { first_edge = 0; }
+  Vertex() { root_edge = 0; }
 
   inline void add_edge(Edge *e) {
-    e->next = first_edge;
+    e->next = root_edge;
     e->pred = 0;
-    if(first_edge) { first_edge->pred = e; }
-    first_edge = e;
+    if(root_edge) { root_edge->pred = e; }
+    root_edge = e;
   }
 
   inline void del_edge(Edge *e) {
-    if(e == first_edge) { first_edge = e->next; }
+    if(e == root_edge) { root_edge = e->next; }
     if(e->pred) { e->pred->next = e->next; }
     if(e->next) { e->next->pred = e->pred; }
   }
@@ -92,49 +92,22 @@ public:
 
   ~Graph();
 
-  void find_best_paths();
+  void find_best_paths(int *result_edge_occupation);
   void print();
-  void print_occupied_edges();
-  void dot_print();
 };
 
 void Graph::print() {
   for(int n = 0; n < nb_vertices; n++) {
-    for(Edge *e = vertices[n].first_edge; e; e = e->next) {
-      cout << n << " -> " << e->terminal_vertex->id << " " << e->length << endl;
-    }
-  }
-}
-
-void Graph::print_occupied_edges() {
-  for(int n = 0; n < nb_vertices; n++) {
-    for(Edge *e = vertices[n].first_edge; e; e = e->next) {
+    for(Edge *e = vertices[n].root_edge; e; e = e->next) {
+      cout << n << " -> " << e->terminal_vertex->id << " " << e->length;
       if(e->occupied) {
-        int a = n, b = e->terminal_vertex->id;
-        if(a > b) { int c = a; a = b; b = c; }
-        cout << a << " " << b << endl;
+        cout << " *";
       }
+      cout << endl;
     }
   }
 }
 
-void Graph::dot_print() {
-  cout << "digraph {" << endl;
-  cout << "  node[shape=circle];" << endl;
-  for(int n = 0; n < nb_vertices; n++) {
-    for(Edge *e = vertices[n].first_edge; e; e = e->next) {
-      int a = n, b = e->terminal_vertex->id;
-      if(e->occupied) {
-        int c = a; a = b; b = c;
-        cout << "  " << a << " -> " << b << " [style=bold,color=black,label=\"" << -e->length << "\"];" << endl;
-      } else {
-        cout << "  " << a << " -> " << b << " [color=gray,label=\"" << e->length << "\"];" << endl;
-      }
-    }
-  }
-  cout << "}" << endl;
-}
-
 Graph::Graph(int nb_vrt, int nb_edges,
              int *from, int *to, scalar_t *lengths,
              int src, int snk) {
@@ -153,6 +126,7 @@ Graph::Graph(int nb_vrt, int nb_edges,
   for(int e = 0; e < nb_edges; e++) {
     vertices[from[e]].add_edge(&edge_heap[e]);
     edge_heap[e].occupied = 0;
+    edge_heap[e].id = e;
     edge_heap[e].length = lengths[e];
     edge_heap[e].terminal_vertex = &vertices[to[e]];
   }
@@ -166,12 +140,12 @@ Graph::~Graph() {
 void Graph::initialize_work_lengths() {
   scalar_t length_min = 0;
   for(int n = 0; n < nb_vertices; n++) {
-    for(Edge *e = vertices[n].first_edge; e; e = e->next) {
+    for(Edge *e = vertices[n].root_edge; e; e = e->next) {
       length_min = min(e->length, length_min);
     }
   }
   for(int n = 0; n < nb_vertices; n++) {
-    for(Edge *e = vertices[n].first_edge; e; e = e->next) {
+    for(Edge *e = vertices[n].root_edge; e; e = e->next) {
       e->work_length = e->length - length_min;
     }
   }
@@ -180,7 +154,7 @@ void Graph::initialize_work_lengths() {
 void Graph::update_work_length() {
   for(int n = 0; n < nb_vertices; n++) {
     scalar_t d = vertices[n].distance_from_source;
-    for(Edge *e = vertices[n].first_edge; e; e = e->next) {
+    for(Edge *e = vertices[n].root_edge; e; e = e->next) {
       e->work_length += d - e->terminal_vertex->distance_from_source;
     }
   }
@@ -194,7 +168,7 @@ void Graph::find_shortest_path(Vertex **front, Vertex **new_front) {
 
 #ifdef DEBUG
   for(int n = 0; n < nb_vertices; n++) {
-    for(Edge *e = vertices[n].first_edge; e; e = e->next) {
+    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;
@@ -218,7 +192,7 @@ void Graph::find_shortest_path(Vertex **front, Vertex **new_front) {
     new_front_size = 0;
     for(int f = 0; f < front_size; f++) {
       v = front[f];
-      for(Edge *e = v->first_edge; e; e = e->next) {
+      for(Edge *e = v->root_edge; e; e = e->next) {
         d = v->distance_from_source + e->work_length;
         tv = e->terminal_vertex;
         if(d < tv->distance_from_source) {
@@ -240,7 +214,7 @@ void Graph::find_shortest_path(Vertex **front, Vertex **new_front) {
   } while(front_size > 0);
 }
 
-void Graph::find_best_paths() {
+void Graph::find_best_paths(int *result_edge_occupation) {
   Vertex **front = new Vertex *[nb_vertices];
   Vertex **new_front = new Vertex *[nb_vertices];
 
@@ -277,23 +251,39 @@ void Graph::find_best_paths() {
     }
   } while(total_length < 0.0);
 
-  // // We put all occupied edges back to their original orientations
-  // for(int n = 0; n < nb_vertices; n++) {
-    // Vertex *v = &vertices[n];
-    // for(Edge *e = v->first_edge; e; e = e->next) {
-      // if(e->occupied) {
-        // e->terminal_vertex = v->pred_vertex;
-        // e->length = - e->length;
-        // e->work_length = 0;
-        // v->pred_vertex->del_edge(e);
-        // v->add_edge(e);
-      // }
-    // }
-  // }
-
-
   delete[] front;
   delete[] new_front;
+
+  for(int n = 0; n < nb_vertices; n++) {
+    Vertex *v = &vertices[n];
+    for(Edge *e = v->root_edge; e; e = e->next) {
+      result_edge_occupation[e->id] = e->occupied;
+    }
+  }
+}
+
+void find_best_paths(int nb_vertices,
+                     int nb_edges, int *ea, int *eb, scalar_t *el,
+                     int source, int sink,
+                     int *result_edge_occupation) {
+  Graph graph(nb_vertices, nb_edges, ea, eb, el, source, sink);
+  graph.find_best_paths(result_edge_occupation);
+}
+
+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;
+    }
+  }
+  cout << "}" << endl;
 }
 
 //////////////////////////////////////////////////////////////////////
@@ -315,32 +305,29 @@ int main(int argc, char **argv) {
     (*file) >> nb_vertices >> nb_edges;
     (*file) >> source >> sink;
 
-    // cout << "INPUT nb_edges " << nb_edges << endl;
-    // cout << "INPUT nb_vertices " << nb_vertices << endl;
-    // cout << "INPUT source " << source << endl;
-    // cout << "INPUT sink " << sink << endl;
-
-    scalar_t *el = new scalar_t[nb_edges];
-    int *ea = new int[nb_edges];
-    int *eb = new int[nb_edges];
+    scalar_t *edge_lengths = new scalar_t[nb_edges];
+    int *vertex_from = new int[nb_edges];
+    int *vertex_to = new int[nb_edges];
+    int *result_edge_occupation = new int[nb_edges];
 
     for(int e = 0; e < nb_edges; e++) {
-      (*file) >> ea[e] >> eb[e] >> el[e];
+      (*file) >> vertex_from[e] >> vertex_to[e] >> edge_lengths[e];
     }
 
-    // for(int e = 0; e < nb_edges; e++) {
-      // cout << "INPUT_EDGE " << ea[e] << " " << eb[e] << " " << el[e] << endl;
-    // }
-
-    Graph graph(nb_vertices, nb_edges, ea, eb, el, source, sink);
+    find_best_paths(nb_vertices, nb_edges,
+                    vertex_from, vertex_to, edge_lengths,
+                    source, sink,
+                    result_edge_occupation);
 
-    graph.find_best_paths();
-    // graph.print_occupied_edges();
-    graph.dot_print();
+    dot_print(nb_vertices, nb_edges,
+              vertex_from, vertex_to, edge_lengths,
+              source, sink,
+              result_edge_occupation);
 
-    delete[] el;
-    delete[] ea;
-    delete[] eb;
+    delete[] result_edge_occupation;
+    delete[] edge_lengths;
+    delete[] vertex_from;
+    delete[] vertex_to;
 
   } else {