origin_vertex->del_leaving_edge(this);
terminal_vertex->add_leaving_edge(this);
Vertex *t = terminal_vertex;
origin_vertex->del_leaving_edge(this);
terminal_vertex->add_leaving_edge(this);
Vertex *t = terminal_vertex;
(*os) << " node [shape=circle,width=0.75,fixedsize=true];" << endl;
(*os) << " edge [color=gray,arrowhead=open]" << 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) << " node [shape=circle,width=0.75,fixedsize=true];" << endl;
(*os) << " edge [color=gray,arrowhead=open]" << 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;
- for(int n = 0; n < _nb_vertices; n++) {
- for(Edge *e = _vertices[n].leaving_edges; e; e = e->next_leaving_edge) {
- if(e->positivized_length < 0) {
+ for(int k = 0; k < _nb_edges; k++) {
+ Edge *e = _edges + k;
+
+ if(e->positivized_length < 0) {
+
+ if((e->origin_vertex->last_change < 0 && e->terminal_vertex->last_change >= 0) ||
+ (e->origin_vertex->last_change >= 0 && e->terminal_vertex->last_change < 0)) {
+ cout << "Inconsistent non-connexity (this should never happen)." << endl;
+ abort();
+ }
+ if(e->origin_vertex->last_change >= 0 &&
+ e->terminal_vertex->last_change >= 0 &&
+ e->positivized_length < 0) {
residual_error -= e->positivized_length;
max_error = max(max_error, - e->positivized_length);
residual_error -= e->positivized_length;
max_error = max(max_error, - e->positivized_length);
- iteration++;
- nb_with_incoming = 0;
-
- // We set the iteration field of all vertex with incoming edges to
- // the current iteration value
+ // We set the last_change field of all the vertices with incoming
+ // edges to the current iteration value
- new_front_size = 0;
- // We remove all vertex without incoming edge
- for(int f = 0; f < front_size; f++) {
+ pred_front_size = front_size;
+ front_size = 0;
+
+ // We keep all the vertices with incoming nodes
+ for(int f = 0; f < pred_front_size; f++) {
-// This method does not change the edge occupation. It update
-// distance_from_source and pred_edge_toward_source.
+// This method does not change the edge occupation. It only set
+// properly, for every vertex, the fields distance_from_source and
+// pred_edge_toward_source.
+
+#ifdef DEBUG
+ if(is_dag()) {
+ cout << "find_shortest_path: DAG -> ok" << endl;
+ } else {
+ for(int e = 0; e < _nb_edges; e++) {
+ if(_edges[e].positivized_length < 0) abort();
+ }
+ cout << "find_shortest_path: All positivized_length are positive -> ok" << endl;
+ }
+#endif
+
for(int k = 0; k < _nb_vertices; k++) {
_vertices[k].distance_from_source = FLT_MAX;
_vertices[k].pred_edge_toward_source = 0;
for(int k = 0; k < _nb_vertices; k++) {
_vertices[k].distance_from_source = FLT_MAX;
_vertices[k].pred_edge_toward_source = 0;
if(d < tv->distance_from_source) {
tv->distance_from_source = d;
tv->pred_edge_toward_source = e;
if(d < tv->distance_from_source) {
tv->distance_from_source = d;
tv->pred_edge_toward_source = e;
- // Let's be a bit paranoid
- ASSERT(is_dag());
-
- // We use one iteration of find_shortest_path simply to propagate
- // the distance to make all the edge lengths positive.
+ // We call find_shortest_path here to set properly the distances to
+ // the source, so that we can make all the edge lengths positive at
+ // the first iteration.
// Put back the graph in its original state (i.e. invert edges which
// have been inverted in the process)
for(int k = 0; k < _nb_edges; k++) {
// Put back the graph in its original state (i.e. invert edges which
// have been inverted in the process)
for(int k = 0; k < _nb_edges; k++) {
if(e->occupied) { e->invert(); }
}
}
int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
Edge *f, *next = 0;
if(e->occupied) { e->invert(); }
}
}
int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
Edge *f, *next = 0;
- if(f->occupied) { nb_choices++; next = f; }
- if(nb_choices == 0) {
- cerr << "retrieve_one_path: Non-sink end point." << endl;
- abort();
- }
- if(nb_choices > 1) {
- cerr << "retrieve_one_path: Non node-disjoint paths." << endl;
- abort();
- }
+ if(f->occupied) { nb_occupied_next++; next = f; }