equal
deleted
inserted
replaced
1 // -*- c++ -*- |
1 // -*- c++ -*- |
2 #ifndef HUGO_SUURBALLE_H |
2 #ifndef HUGO_SUURBALLE_H |
3 #define HUGO_SUURBALLE_H |
3 #define HUGO_SUURBALLE_H |
|
4 |
|
5 ///\file |
|
6 ///\brief Suurballe algorithm. |
4 |
7 |
5 #include <iostream> |
8 #include <iostream> |
6 #include <dijkstra.h> |
9 #include <dijkstra.h> |
7 #include <graph_wrapper.h> |
10 #include <graph_wrapper.h> |
8 namespace hugo { |
11 namespace hugo { |
14 /// Suurballe's algorithm which seeks for k edge-disjoint paths |
17 /// Suurballe's algorithm which seeks for k edge-disjoint paths |
15 /// from a given source node to a given target node in an |
18 /// from a given source node to a given target node in an |
16 /// edge-weighted directed graph having minimal total cost. |
19 /// edge-weighted directed graph having minimal total cost. |
17 /// |
20 /// |
18 /// |
21 /// |
19 |
|
20 |
22 |
21 template <typename Graph, typename T, |
23 template <typename Graph, typename T, |
22 typename LengthMap=typename Graph::EdgeMap<T> > |
24 typename LengthMap=typename Graph::EdgeMap<T> > |
23 class Suurballe { |
25 class Suurballe { |
24 |
26 |
78 |
80 |
79 Suurballe(Graph& _G, LengthMap& _length) : G(_G), |
81 Suurballe(Graph& _G, LengthMap& _length) : G(_G), |
80 length(_length), reversed(_G), dijkstra_dist(_G){ } |
82 length(_length), reversed(_G), dijkstra_dist(_G){ } |
81 |
83 |
82 ///Runs Suurballe's algorithm |
84 ///Runs Suurballe's algorithm |
|
85 |
|
86 ///Runs Suurballe's algorithm |
83 ///Returns true iff there are k edge-disjoint paths from s to t |
87 ///Returns true iff there are k edge-disjoint paths from s to t |
84 bool run(Node s, Node t, int k) { |
88 bool run(Node s, Node t, int k) { |
85 |
89 |
86 LengthMap mod_length_c = length; |
90 LengthMap mod_length_c = length; |
87 ConstMap const1map; |
91 ConstMap const1map; |