klao@308
|
1 |
// -*- c++ -*-
|
klao@308
|
2 |
#ifndef HUGO_MINLENGTHPATHS_H
|
klao@308
|
3 |
#define HUGO_MINLENGTHPATHS_H
|
klao@308
|
4 |
|
klao@308
|
5 |
///\file
|
klao@308
|
6 |
///\brief An algorithm for finding k paths of minimal total length.
|
klao@308
|
7 |
|
klao@308
|
8 |
#include <iostream>
|
klao@308
|
9 |
#include <dijkstra.h>
|
klao@308
|
10 |
#include <graph_wrapper.h>
|
klao@308
|
11 |
#include <maps.h>
|
klao@308
|
12 |
|
klao@308
|
13 |
namespace hugo {
|
klao@308
|
14 |
|
klao@308
|
15 |
|
klao@308
|
16 |
///\brief Implementation of an algorithm for finding k paths between 2 nodes
|
klao@308
|
17 |
/// of minimal total length
|
klao@308
|
18 |
///
|
klao@308
|
19 |
/// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
|
klao@308
|
20 |
/// an algorithm which finds k edge-disjoint paths
|
klao@308
|
21 |
/// from a given source node to a given target node in an
|
klao@308
|
22 |
/// edge-weighted directed graph having minimal total weigth (length).
|
klao@308
|
23 |
///
|
klao@308
|
24 |
///
|
klao@308
|
25 |
|
klao@308
|
26 |
template <typename Graph, typename T,
|
klao@308
|
27 |
typename LengthMap=typename Graph::EdgeMap<T> >
|
klao@308
|
28 |
class MinLengthPaths {
|
klao@308
|
29 |
|
klao@308
|
30 |
|
klao@308
|
31 |
// class ConstMap {
|
klao@308
|
32 |
// public :
|
klao@308
|
33 |
// typedef int ValueType;
|
klao@308
|
34 |
// typedef typename Graph::Edge KeyType;
|
klao@308
|
35 |
|
klao@308
|
36 |
// int operator[](typename Graph::Edge e) const {
|
klao@308
|
37 |
// return 1;
|
klao@308
|
38 |
// }
|
klao@308
|
39 |
// };
|
klao@308
|
40 |
|
klao@308
|
41 |
|
klao@308
|
42 |
typedef typename Graph::Node Node;
|
klao@308
|
43 |
typedef typename Graph::NodeIt NodeIt;
|
klao@308
|
44 |
typedef typename Graph::Edge Edge;
|
klao@308
|
45 |
typedef typename Graph::OutEdgeIt OutEdgeIt;
|
klao@308
|
46 |
typedef typename Graph::EdgeMap<int> EdgeIntMap;
|
klao@308
|
47 |
|
klao@308
|
48 |
typedef ConstMap<Edge,int> ConstMap;
|
klao@308
|
49 |
|
klao@308
|
50 |
typedef TrivGraphWrapper<const Graph> TrivGraphType;
|
klao@308
|
51 |
typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
|
klao@308
|
52 |
ConstMap> ResGraphType;
|
klao@308
|
53 |
|
klao@308
|
54 |
|
klao@308
|
55 |
//template <typename Graph, typename T>
|
klao@308
|
56 |
class ModLengthMap {
|
klao@308
|
57 |
typedef typename ResGraphType::NodeMap<T> NodeMap;
|
klao@308
|
58 |
const ResGraphType& G;
|
klao@308
|
59 |
const EdgeIntMap& rev;
|
klao@308
|
60 |
const LengthMap &ol;
|
klao@308
|
61 |
const NodeMap &pot;
|
klao@308
|
62 |
public :
|
klao@308
|
63 |
typedef typename LengthMap::KeyType KeyType;
|
klao@308
|
64 |
typedef typename LengthMap::ValueType ValueType;
|
klao@308
|
65 |
|
klao@308
|
66 |
ValueType operator[](typename ResGraphType::Edge e) const {
|
klao@308
|
67 |
if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
|
klao@308
|
68 |
///\TODO This has to be removed
|
klao@308
|
69 |
std::cout<<"Negative length!!"<<std::endl;
|
klao@308
|
70 |
}
|
klao@308
|
71 |
return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);
|
klao@308
|
72 |
}
|
klao@308
|
73 |
|
klao@308
|
74 |
ModLengthMap( const ResGraphType& _G, const EdgeIntMap& _rev,
|
klao@308
|
75 |
const LengthMap &o, const NodeMap &p) :
|
klao@308
|
76 |
G(_G), rev(_rev), ol(o), pot(p){};
|
klao@308
|
77 |
};
|
klao@308
|
78 |
|
klao@308
|
79 |
|
klao@308
|
80 |
const Graph& G;
|
klao@308
|
81 |
const LengthMap& length;
|
klao@308
|
82 |
|
klao@308
|
83 |
//auxiliary variable
|
klao@308
|
84 |
//The value is 1 iff the edge is reversed
|
klao@308
|
85 |
EdgeIntMap reversed;
|
klao@308
|
86 |
|
klao@308
|
87 |
|
klao@308
|
88 |
public :
|
klao@308
|
89 |
|
klao@308
|
90 |
|
klao@308
|
91 |
MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
|
klao@308
|
92 |
length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
|
klao@308
|
93 |
|
klao@308
|
94 |
///Runs the algorithm
|
klao@308
|
95 |
|
klao@308
|
96 |
///Runs the algorithm
|
klao@308
|
97 |
///Returns k if there are at least k edge-disjoint paths from s to t.
|
klao@308
|
98 |
///Otherwise it returns the number of edge-disjoint paths from s to t.
|
klao@308
|
99 |
int run(Node s, Node t, int k) {
|
klao@308
|
100 |
ConstMap const1map(1);
|
klao@308
|
101 |
|
klao@308
|
102 |
ResGraphType res_graph(G, reversed, const1map);
|
klao@308
|
103 |
|
klao@308
|
104 |
//Initialize the copy of the Dijkstra potential to zero
|
klao@308
|
105 |
typename ResGraphType::NodeMap<T> dijkstra_dist(G);
|
klao@308
|
106 |
ModLengthMap mod_length( res_graph, reversed, length, dijkstra_dist);
|
klao@308
|
107 |
|
klao@308
|
108 |
Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
|
klao@308
|
109 |
|
klao@308
|
110 |
for (int i=0; i<k; ++i){
|
klao@308
|
111 |
dijkstra.run(s);
|
klao@308
|
112 |
if (!dijkstra.reached(t)){
|
klao@308
|
113 |
//There is no k path from s to t
|
klao@308
|
114 |
return ++i;
|
klao@308
|
115 |
};
|
klao@308
|
116 |
|
klao@308
|
117 |
{
|
klao@308
|
118 |
//We have to copy the potential
|
klao@308
|
119 |
typename ResGraphType::NodeIt n;
|
klao@308
|
120 |
for ( res_graph.first(n) ; res_graph.valid(n) ; res_graph.next(n) ) {
|
klao@308
|
121 |
dijkstra_dist[n] += dijkstra.distMap()[n];
|
klao@308
|
122 |
}
|
klao@308
|
123 |
}
|
klao@308
|
124 |
|
klao@308
|
125 |
|
klao@308
|
126 |
/*
|
klao@308
|
127 |
{
|
klao@308
|
128 |
//We have to copy the potential
|
klao@308
|
129 |
typename ResGraphType::EdgeIt e;
|
klao@308
|
130 |
for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
|
klao@308
|
131 |
//dijkstra_dist[e] = dijkstra.distMap()[e];
|
klao@308
|
132 |
mod_length_c[Edge(e)] = mod_length_c[Edge(e)] -
|
klao@308
|
133 |
dijkstra.distMap()[res_graph.head(e)] +
|
klao@308
|
134 |
dijkstra.distMap()[res_graph.tail(e)];
|
klao@308
|
135 |
}
|
klao@308
|
136 |
}
|
klao@308
|
137 |
*/
|
klao@308
|
138 |
|
klao@308
|
139 |
//Reversing the sortest path
|
klao@308
|
140 |
Node n=t;
|
klao@308
|
141 |
Edge e;
|
klao@308
|
142 |
while (n!=s){
|
klao@308
|
143 |
e = dijkstra.pred(n);
|
klao@308
|
144 |
n = dijkstra.predNode(n);
|
klao@308
|
145 |
reversed[e] = 1-reversed[e];
|
klao@308
|
146 |
}
|
klao@308
|
147 |
|
klao@308
|
148 |
|
klao@308
|
149 |
}
|
klao@308
|
150 |
return k;
|
klao@308
|
151 |
}
|
klao@308
|
152 |
|
klao@308
|
153 |
|
klao@308
|
154 |
|
klao@308
|
155 |
|
klao@308
|
156 |
|
klao@308
|
157 |
};//class MinLengthPaths
|
klao@308
|
158 |
|
klao@308
|
159 |
|
klao@308
|
160 |
|
klao@308
|
161 |
|
klao@308
|
162 |
} //namespace hugo
|
klao@308
|
163 |
|
klao@308
|
164 |
#endif //HUGO_MINLENGTHPATHS_H
|