//////////////////////////////////////////////////////////////////////
-Path::Path(int l) {
- length = l;
- nodes = new int[length];
-}
-
-Path::~Path() {
- delete[] nodes;
-}
-
-//////////////////////////////////////////////////////////////////////
-
MTPGraph::MTPGraph(int nb_vertices, int nb_edges,
int *from, int *to,
int source, int sink) {
void MTPGraph::print_dot(ostream *os) {
(*os) << "digraph {" << endl;
- (*os) << " node[shape=circle];" << endl;
+ // (*os) << " node [shape=circle];" << endl;
+ (*os) << " " << _source->id << " [peripheries=2];" << endl;
+ (*os) << " " << _sink->id << " [peripheries=2];" << endl;
for(int k = 0; k < _nb_edges; k++) {
Edge *e = _edges + k;
// (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id
// << ";"
// << endl;
if(e->occupied) {
- (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id
+ (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id
<< " [style=bold,color=black,label=\"" << e->length << "\"];" << endl;
} else {
- (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id
+ (*os) << " " << e->origin_vertex->id << " -> " << e->terminal_vertex->id
<< " [color=gray,label=\"" << e->length << "\"];" << endl;
}
}
_new_front_size = 0;
iteration++;
- // for(int k = 0; k < _nb_edges; k++) {
- // Edge *e = _edges + k;
- // d = e->origin_vertex->distance_from_source + e->positivized_length;
- // if(d < e->terminal_vertex->distance_from_source) {
- // e->terminal_vertex->distance_from_source = d;
- // _new_front_size++;
- // }
- // }
-
- // for(int n = 0; n < _nb_vertices; n++) {
- // v = &_vertices[n];
- // for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
- // d = v->distance_from_source + e->positivized_length;
- // tv = e->terminal_vertex;
- // if(d < tv->distance_from_source) {
- // tv->distance_from_source = d;
- // tv->best_pred_edge_to_source = e;
- // if(tv->iteration < iteration) {
- // _new_front[_new_front_size++] = tv;
- // tv->iteration = iteration;
- // }
- // }
- // }
- // }
-
for(int f = 0; f < _front_size; f++) {
v = _front[f];
for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
_new_front_size = _front_size;
_front_size = tmp_front_size;
} while(_front_size > 0);
-
-#ifdef DEBUG
- scalar_t min_delta = 0, delta;
- for(int k = 0; k < _nb_edges; k++) {
- Edge *e = _edges + k;
- // d = e->origin_vertex->distance_from_source + e->positivized_length;
- // if(d > e->terminal_vertex->distance_from_source) { abort(); }
- delta = e->positivized_length +
- (e->origin_vertex->distance_from_source - e->terminal_vertex->distance_from_source);
- min_delta = min(delta, min_delta);
- }
- cout << "min_delta = " << delta << endl;
-#endif
}
void MTPGraph::find_best_paths(scalar_t *lengths) {
_edges[e].positivized_length = _edges[e].length;
}
- cout << "********************************************************" << endl;
- // print_dot(&cout);
-
// We use one iteration of find_shortest_path simply to propagate
// the distance to make all the edge lengths positive.
find_shortest_path(_front, _new_front);