projects
/
mtp.git
/ commitdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
| commitdiff |
tree
raw
|
patch
|
inline
| side by side (parent:
1f3de34
)
Simplified and optimized compute_dp_ordering.
author
Francois Fleuret
<francois@fleuret.org>
Wed, 2 Jan 2013 02:23:40 +0000
(
03:23
+0100)
committer
Francois Fleuret
<francois@fleuret.org>
Wed, 2 Jan 2013 02:23:40 +0000
(
03:23
+0100)
mtp_graph.cc
patch
|
blob
|
history
diff --git
a/mtp_graph.cc
b/mtp_graph.cc
index
a03f60e
..
4cfd1f8
100644
(file)
--- a/
mtp_graph.cc
+++ b/
mtp_graph.cc
@@
-424,23
+424,15
@@
int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
//////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////
-static int compare_vertices_on_distance(const void *v1, const void *v2) {
- scalar_t delta =
- (*((Vertex **) v1))->distance_from_source -
- (*((Vertex **) v2))->distance_from_source;
- if(delta < 0) return -1;
- else if(delta > 0) return 1;
- else return 0;
-}
-
void MTPGraph::compute_dp_ordering() {
Vertex *v;
Edge *e;
int ntv;
void MTPGraph::compute_dp_ordering() {
Vertex *v;
Edge *e;
int ntv;
- // This method computes for each node the length of the longest link
- // from the source, and orders the node in _dp_order according to
- // it. It aborts if the graph is not a DAG.
+ // This method orders the nodes by putting first the ones with no
+ // predecessors, then going on adding nodes whose predecessors have
+ // all been already added. Computing the distances from the source
+ // by visiting nodes in that order is equivalent to DP.
int *nb_predecessors = new int[_nb_vertices];
int *nb_predecessors = new int[_nb_vertices];
@@
-464,12
+456,10
@@
void MTPGraph::compute_dp_ordering() {
}
}
}
}
- scalar_t rank = 1;
while(already_processed < front) {
new_front = front;
while(already_processed < front) {
v = *(already_processed++);
while(already_processed < front) {
new_front = front;
while(already_processed < front) {
v = *(already_processed++);
- v->distance_from_source = rank;
for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) {
ntv = int(e->terminal_vertex - _vertices);
nb_predecessors[ntv]--;
for(e = v->leaving_edge_list_root; e; e = e->next_leaving_edge) {
ntv = int(e->terminal_vertex - _vertices);
nb_predecessors[ntv]--;
@@
-480,7
+470,6
@@
void MTPGraph::compute_dp_ordering() {
}
}
front = new_front;
}
}
front = new_front;
- rank++;
}
if(already_processed < _dp_order + _nb_vertices) {
}
if(already_processed < _dp_order + _nb_vertices) {
@@
-489,9
+478,6
@@
void MTPGraph::compute_dp_ordering() {
}
delete[] nb_predecessors;
}
delete[] nb_predecessors;
-
- for(int v = 0; v < _nb_vertices; v++) { _dp_order[v] = &_vertices[v]; }
- qsort(_dp_order, _nb_vertices, sizeof(Vertex *), compare_vertices_on_distance);
}
//////////////////////////////////////////////////////////////////////
}
//////////////////////////////////////////////////////////////////////