projects
/
mtp.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
c752952
)
Cosmetics.
author
Francois Fleuret
<francois@fleuret.org>
Thu, 20 Dec 2012 14:40:59 +0000
(15:40 +0100)
committer
Francois Fleuret
<francois@fleuret.org>
Thu, 20 Dec 2012 14:40:59 +0000
(15:40 +0100)
mtp_graph.cc
patch
|
blob
|
history
diff --git
a/mtp_graph.cc
b/mtp_graph.cc
index
5a7da77
..
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 **
unreached
= new Vertex *[_nb_vertices];
+ Vertex **
with_predecessor
= new Vertex *[_nb_vertices];
- // All the nodes are
unreached
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;
-
unreached
[k] = &_vertices[k];
+
with_predecessor
[k] = &_vertices[k];
}
scalar_t rank = 1;
}
scalar_t rank = 1;
- int nb_
unreached = _nb_vertices, pred_nb_unreached
;
+ 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_
unreached
; f++) {
- v =
unreached
[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_
unreached = nb_unreached
;
- nb_
unreached
= 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_
unreached
; f++) {
- v =
unreached
[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) {
-
unreached[nb_unreached
++] = v;
+
with_predecessor[nb_with_predecessor
++] = v;
}
}
rank++;
}
}
rank++;
- } while(nb_
unreached < pred_nb_unreached
);
+ } while(nb_
with_predecessor < pred_nb_with_predecessor
);
- delete[]
unreached
;
+ delete[]
with_predecessor
;
- return nb_
unreached
== 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;
@@
-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();