2 ///////////////////////////////////////////////////////////////////////////
5 // This program is free software: you can redistribute it and/or modify //
6 // it under the terms of the version 3 of the GNU General Public License //
7 // as published by the Free Software Foundation. //
9 // This program is distributed in the hope that it will be useful, but //
10 // WITHOUT ANY WARRANTY; without even the implied warranty of //
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU //
12 // General Public License for more details. //
14 // You should have received a copy of the GNU General Public License //
15 // along with this program. If not, see <http://www.gnu.org/licenses/>. //
17 // Written by and Copyright (C) Francois Fleuret //
18 // Contact <francois.fleuret@idiap.ch> for comments & bug reports //
21 ///////////////////////////////////////////////////////////////////////////
34 typedef float scalar_t;
37 #define ASSERT(x) if(!(x)) { \
38 std::cerr << "ASSERT FAILED IN " << __FILE__ << ":" << __LINE__ << endl; \
45 // Adds to all the edge length the length of the shortest (which can
47 void raise_es(int nb_edges, scalar_t *el) {
48 scalar_t min_es = el[0];
49 for(int e = 1; e < nb_edges; e++) {
50 min_es = min(min_es, el[e]);
52 for(int e = 0; e < nb_edges; e++) {
57 // Add to every edge length the differential of the psi function on it
58 void add_dpsi_es(int nb_edges, scalar_t *el, int *ea, int *eb, scalar_t *psi) {
59 for(int e = 0; e < nb_edges; e++) {
60 el[e] += psi[ea[e]] - psi[eb[e]];
64 // Find the shortest path in the graph and return in return_edge_back,
65 // for each vertex the edge to follow back from it to reach the source
66 // with the shortest path, and in return_dist the distance to the
67 // source. The edge lengths have to be positive.
68 void find_shortest(int nb_vertices,
69 int nb_edges, scalar_t *el, int *ea, int *eb,
71 int *return_edge_back, scalar_t *return_dist) {
72 for(int v = 0; v < nb_vertices; v++) {
80 for(int e = 0; e < nb_edges; e++) {
81 if(el[e] < 0) abort();
89 for(int e = 0; e < nb_edges; e++) {
90 d = dist[ea[e]] + el[e];
97 } while(nb_changes > 0);
100 void find_best_paths(int nb_vertices,
101 int nb_edges, scalar_t *el, int *ea, int *eb,
102 int source, int sink,
103 int *edge_occupation) {
104 scalar_t *dist = new scalar_t[nb_vertices];
105 int *edge_back = new int[nb_vertices];
106 scalar_t *positive_el = new scalar_t[nb_edges];
110 for(int e = 0; e < nb_edges; e++) {
111 positive_el[e] = el[e];
112 edge_occupation[e] = 0;
115 raise_es(nb_edges, positive_el);
118 find_shortest(nb_vertices, nb_edges, positive_el, ea, eb, source, sink, edge_back, dist);
119 add_dpsi_es(nb_edges, positive_el, ea, eb, dist);
122 // If the new path reaches the sink, we will backtrack on it to
123 // compute its score and invert edges
125 if(edge_back[sink] >= 0) {
129 int e = edge_back[v];
135 // We found a good path (score < 0), we revert the edges along
136 // the path and note that they are occupied
141 cout << "FOUND A PATH OF LENGTH " << s << endl;
144 int e = edge_back[v];
148 cout << "INVERTING " << ea[e] << " -> " << eb[e] << " [" << el[e] << "]" << endl;
153 positive_el[e] = - positive_el[e];
155 edge_occupation[e] = 1 - edge_occupation[e];
161 delete[] positive_el;
166 int main(int argc, char **argv) {
169 cerr << argv[0] << " <graph file>" << endl;
173 ifstream *file = new ifstream(argv[1]);
175 int nb_edges, nb_vertices;
180 (*file) >> nb_vertices >> nb_edges;
181 (*file) >> source >> sink;
183 cout << "INPUT nb_edges " << nb_edges << endl;
184 cout << "INPUT nb_vertices " << nb_vertices << endl;
185 cout << "INPUT source " << source << endl;
186 cout << "INPUT sink " << sink << endl;
188 scalar_t *el = new scalar_t[nb_edges];
189 int *ea = new int[nb_edges];
190 int *eb = new int[nb_edges];
191 int *edge_occupation = new int[nb_edges];
193 for(int e = 0; e < nb_edges; e++) {
194 (*file) >> ea[e] >> eb[e] >> el[e];
195 cout << "INPUT_EDGE " << ea[e] << " " << eb[e] << " " << el[e] << endl;
198 find_best_paths(nb_vertices, nb_edges, el, ea, eb, source, sink,
201 for(int e = 0; e < nb_edges; e++) {
202 if(edge_occupation[e]) {
203 cout << "RESULT_OCCUPIED_EDGE " << ea[e] << " " << eb[e] << endl;
207 delete[] edge_occupation;
214 cerr << "Can not open " << argv[1] << endl;