projects
/
mtp.git
/ blobdiff
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
raw
|
inline
| side by side
Fixed retrieve_disjoint_paths to deal with non-node-disjoint situations.
[mtp.git]
/
mtp_graph.cc
diff --git
a/mtp_graph.cc
b/mtp_graph.cc
index
e69d4d6
..
8849acd
100644
(file)
--- a/
mtp_graph.cc
+++ b/
mtp_graph.cc
@@
-379,7
+379,7
@@
void MTPGraph::find_best_paths(scalar_t *lengths) {
}
}
}
}
-int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
+int MTPGraph::retrieve_one_path(Edge *e, Path *path
, int *used_edges
) {
Edge *f, *next = 0;
int l = 0, nb_occupied_next;
Edge *f, *next = 0;
int l = 0, nb_occupied_next;
@@
-396,7
+396,9
@@
int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
nb_occupied_next = 0;
for(f = e->terminal_vertex->leaving_edge_list_root; f; f = f->next_leaving_edge) {
nb_occupied_next = 0;
for(f = e->terminal_vertex->leaving_edge_list_root; f; f = f->next_leaving_edge) {
- if(f->occupied) { nb_occupied_next++; next = f; }
+ if(f->occupied && !used_edges[f - _edges]) {
+ nb_occupied_next++; next = f;
+ }
}
#ifdef DEBUG
}
#ifdef DEBUG
@@
-404,13
+406,10
@@
int MTPGraph::retrieve_one_path(Edge *e, Path *path) {
cerr << __FILE__ << ": retrieve_one_path: Non-sink end point." << endl;
abort();
}
cerr << __FILE__ << ": retrieve_one_path: Non-sink end point." << endl;
abort();
}
-
- else if(nb_occupied_next > 1) {
- cerr << __FILE__ << ": retrieve_one_path: Non node-disjoint paths." << endl;
- abort();
- }
#endif
#endif
+ if(path) { used_edges[next - _edges] = 1; }
+
e = next;
}
e = next;
}
@@
-490,6
+489,7
@@
void MTPGraph::compute_dp_ordering() {
void MTPGraph::retrieve_disjoint_paths() {
Edge *e;
int p, l;
void MTPGraph::retrieve_disjoint_paths() {
Edge *e;
int p, l;
+ int *used_edges;
for(int p = 0; p < nb_paths; p++) delete paths[p];
delete[] paths;
for(int p = 0; p < nb_paths; p++) delete paths[p];
delete[] paths;
@@
-500,14
+500,21
@@
void MTPGraph::retrieve_disjoint_paths() {
}
paths = new Path *[nb_paths];
}
paths = new Path *[nb_paths];
+ used_edges = new int[_nb_edges];
+ for(int e = 0; e < _nb_edges; e++) {
+ used_edges[e] = 0;
+ }
p = 0;
for(e = _source->leaving_edge_list_root; e; e = e->next_leaving_edge) {
p = 0;
for(e = _source->leaving_edge_list_root; e; e = e->next_leaving_edge) {
- if(e->occupied) {
- l = retrieve_one_path(e, 0);
+ if(e->occupied
&& !used_edges[e - _edges]
) {
+ l = retrieve_one_path(e, 0
, used_edges
);
paths[p] = new Path(l);
paths[p] = new Path(l);
- retrieve_one_path(e, paths[p]);
+ retrieve_one_path(e, paths[p], used_edges);
+ used_edges[e - _edges] = 1;
p++;
}
}
p++;
}
}
+
+ delete[] used_edges;
}
}