projects
/
mtp.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Cosmetics.
[mtp.git]
/
mtp_graph.cc
diff --git
a/mtp_graph.cc
b/mtp_graph.cc
index
ea8f91b
..
682dd80
100644
(file)
--- a/
mtp_graph.cc
+++ b/
mtp_graph.cc
@@
-202,44
+202,44
@@
int MTPGraph::compute_dp_ranks() {
// rank of a node is the iteration at which is it removed, and we
// set the distance_from_source fields to this value.
// rank of a node is the iteration at which is it removed, and we
// set the distance_from_source fields to this value.
- Vertex **
active
= new Vertex *[_nb_vertices];
+ Vertex **
with_predecessor
= new Vertex *[_nb_vertices];
- // All the nodes are
active
at first
+ // All the nodes are
with_predecessor
at first
for(int k = 0; k < _nb_vertices; k++) {
_vertices[k].distance_from_source = 0;
for(int k = 0; k < _nb_vertices; k++) {
_vertices[k].distance_from_source = 0;
-
active
[k] = &_vertices[k];
+
with_predecessor
[k] = &_vertices[k];
}
scalar_t rank = 1;
}
scalar_t rank = 1;
- int nb_
active = _nb_vertices, pred_nb_active
;
+ int nb_
with_predecessor = _nb_vertices, pred_nb_with_predecessor
;
do {
// We set the distance_from_source field of all the vertices with incoming
// edges to the current rank value
do {
// We set the distance_from_source field of all the vertices with incoming
// edges to the current rank value
- for(int f = 0; f < nb_
active
; f++) {
- v =
active
[f];
+ for(int f = 0; f < nb_
with_predecessor
; f++) {
+ v =
with_predecessor
[f];
for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
e->terminal_vertex->distance_from_source = rank;
}
}
for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
e->terminal_vertex->distance_from_source = rank;
}
}
- pred_nb_
active = nb_active
;
- nb_
active
= 0;
+ pred_nb_
with_predecessor = nb_with_predecessor
;
+ nb_
with_predecessor
= 0;
// We keep all the vertices with incoming nodes
// We keep all the vertices with incoming nodes
- for(int f = 0; f < pred_nb_
active
; f++) {
- v =
active
[f];
+ for(int f = 0; f < pred_nb_
with_predecessor
; f++) {
+ v =
with_predecessor
[f];
if(v->distance_from_source == rank) {
if(v->distance_from_source == rank) {
-
active[nb_active
++] = v;
+
with_predecessor[nb_with_predecessor
++] = v;
}
}
rank++;
}
}
rank++;
- } while(nb_
active < pred_nb_active
);
+ } while(nb_
with_predecessor < pred_nb_with_predecessor
);
- delete[]
active
;
+ delete[]
with_predecessor
;
- return nb_
active
== 0;
+ return nb_
with_predecessor
== 0;
}
//////////////////////////////////////////////////////////////////////
}
//////////////////////////////////////////////////////////////////////
@@
-300,7
+300,6
@@
void MTPGraph::force_positivized_lengths() {
Edge *e = _edges + k;
if(e->positivized_length < 0) {
Edge *e = _edges + k;
if(e->positivized_length < 0) {
-
#ifdef VERBOSE
residual_error -= e->positivized_length;
max_error = max(max_error, - e->positivized_length);
#ifdef VERBOSE
residual_error -= e->positivized_length;
max_error = max(max_error, - e->positivized_length);
@@
-333,7
+332,6
@@
void MTPGraph::dp_compute_distances() {
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;
- tv->decrease_distance_in_heap(_heap);
}
}
}
}
}
}
@@
-344,7
+342,7
@@
void MTPGraph::dp_compute_distances() {
// pred_edge_toward_source.
void MTPGraph::find_shortest_path() {
// pred_edge_toward_source.
void MTPGraph::find_shortest_path() {
- Vertex *v, *tv, **
a, **b
;
+ Vertex *v, *tv, **
last_slot
;
Edge *e;
scalar_t d;
Edge *e;
scalar_t d;
@@
-361,15
+359,15
@@
void MTPGraph::find_shortest_path() {
// Get the closest to the source
v = _heap[0];
// Get the closest to the source
v = _heap[0];
- // Remove it from the heap (swap it with the last in the heap, and
+ // Remove it from the heap (swap it with the last
_slot
in the heap, and
// update the distance of that one)
_heap_size--;
// update the distance of that one)
_heap_size--;
- a = _heap;
- b = _heap + _heap_size;
- swap(*a, *b); swap((*a)->heap_slot, (*b)->heap_slot);
+ last_slot = _heap + _heap_size;
+ swap(*_heap, *last_slot); swap((*_heap)->heap_slot, (*last_slot)->heap_slot);
_heap[0]->increase_distance_in_heap(_heap, _heap + _heap_size);
_heap[0]->increase_distance_in_heap(_heap, _heap + _heap_size);
- // Now update the neighbors of the currently closest to the source
+ // Now update the neighbors of the node currently closest to the
+ // source
for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
d = v->distance_from_source + e->positivized_length;
tv = e->terminal_vertex;
for(e = v->leaving_edges; e; e = e->next_leaving_edge) {
d = v->distance_from_source + e->positivized_length;
tv = e->terminal_vertex;
@@
-384,7
+382,7
@@
void MTPGraph::find_shortest_path() {
}
void MTPGraph::find_best_paths(scalar_t *lengths) {
}
void MTPGraph::find_best_paths(scalar_t *lengths) {
- scalar_t
total
_length;
+ scalar_t
shortest_path
_length;
Vertex *v;
Edge *e;
Vertex *v;
Edge *e;
@@
-394,7
+392,7
@@
void MTPGraph::find_best_paths(scalar_t *lengths) {
_edges[e].positivized_length = _edges[e].length;
}
_edges[e].positivized_length = _edges[e].length;
}
- // Compute the distance of
every node
from the source by just
+ // Compute the distance of
all the nodes
from the source by just
// visiting them in the proper DAG ordering we computed when
// building the graph
dp_compute_distances();
// visiting them in the proper DAG ordering we computed when
// building the graph
dp_compute_distances();
@@
-408,7
+406,7
@@
void MTPGraph::find_best_paths(scalar_t *lengths) {
find_shortest_path();
find_shortest_path();
-
total
_length = 0.0;
+
shortest_path
_length = 0.0;
// Do we reach the sink?
if(_sink->pred_edge_toward_source) {
// Do we reach the sink?
if(_sink->pred_edge_toward_source) {
@@
-416,13
+414,13
@@
void MTPGraph::find_best_paths(scalar_t *lengths) {
// original edge lengths
v = _sink;
while(v->pred_edge_toward_source) {
// original edge lengths
v = _sink;
while(v->pred_edge_toward_source) {
-
total
_length += v->pred_edge_toward_source->length;
+
shortest_path
_length += v->pred_edge_toward_source->length;
v = v->pred_edge_toward_source->origin_vertex;
}
// If that length is negative
v = v->pred_edge_toward_source->origin_vertex;
}
// If that length is negative
- if(
total
_length < 0.0) {
+ if(
shortest_path
_length < 0.0) {
#ifdef VERBOSE
#ifdef VERBOSE
- cerr << __FILE__ << ": Found a path of length " <<
total
_length << endl;
+ cerr << __FILE__ << ": Found a path of length " <<
shortest_path
_length << endl;
#endif
// Invert all the edges along the best path
v = _sink;
#endif
// Invert all the edges along the best path
v = _sink;
@@
-437,7
+435,7
@@
void MTPGraph::find_best_paths(scalar_t *lengths) {
}
}
}
}
- } while(
total
_length < 0.0);
+ } while(
shortest_path
_length < 0.0);
// Put back the graph in its original state (i.e. invert edges which
// have been inverted in the process)
// Put back the graph in its original state (i.e. invert edges which
// have been inverted in the process)