1.1 --- a/src/work/athos/suurballe.h Mon Apr 05 14:56:32 2004 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,142 +0,0 @@
1.4 -// -*- c++ -*-
1.5 -#ifndef HUGO_SUURBALLE_H
1.6 -#define HUGO_SUURBALLE_H
1.7 -
1.8 -///\file
1.9 -///\brief Suurballe algorithm.
1.10 -
1.11 -#include <iostream>
1.12 -#include <dijkstra.h>
1.13 -#include <graph_wrapper.h>
1.14 -namespace hugo {
1.15 -
1.16 -
1.17 -///\brief Implementation of Suurballe's algorithm
1.18 -///
1.19 -/// The class \ref hugo::Suurballe "Suurballe" implements
1.20 -/// Suurballe's algorithm which seeks for k edge-disjoint paths
1.21 -/// from a given source node to a given target node in an
1.22 -/// edge-weighted directed graph having minimal total cost.
1.23 -///
1.24 -///
1.25 -
1.26 - template <typename Graph, typename T,
1.27 - typename LengthMap=typename Graph::EdgeMap<T> >
1.28 - class Suurballe {
1.29 -
1.30 -
1.31 - //Writing maps
1.32 - class ConstMap {
1.33 - public :
1.34 - typedef int ValueType;
1.35 - typedef typename Graph::Edge KeyType;
1.36 -
1.37 - int operator[](typename Graph::Edge e) const {
1.38 - return 1;
1.39 - }
1.40 - };
1.41 - /*
1.42 - // template <typename Graph, typename T>
1.43 - class ModLengthMap {
1.44 - typedef typename Graph::EdgeMap<T> EdgeMap;
1.45 - typedef typename Graph::NodeMap<T> NodeMap;
1.46 -
1.47 - const EdgeMap &ol;
1.48 - const NodeMap &pot;
1.49 - public :
1.50 - typedef typename EdgeMap::KeyType KeyType;
1.51 - typedef typename EdgeMap::ValueType ValueType;
1.52 -
1.53 - double operator[](typename Graph::EdgeIt e) const {
1.54 - return 10;//ol.get(e)-pot.get(v)-pot.get(u);
1.55 - }
1.56 -
1.57 - ModLengthMap(const EdgeMap &o,
1.58 - const NodeMap &p) :
1.59 - ol(o), pot(p){};
1.60 - };
1.61 - */
1.62 -
1.63 -
1.64 - typedef typename Graph::Node Node;
1.65 - typedef typename Graph::NodeIt NodeIt;
1.66 - typedef typename Graph::Edge Edge;
1.67 - typedef typename Graph::OutEdgeIt OutEdgeIt;
1.68 - typedef TrivGraphWrapper<const Graph> TrivGraphType;
1.69 - typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
1.70 - ConstMap> ResGraphType;
1.71 -
1.72 - const Graph& G;
1.73 - const LengthMap& length;
1.74 -
1.75 -
1.76 - //auxiliary variables
1.77 -
1.78 - typename Graph::EdgeMap<int> reversed;
1.79 - typename Graph::NodeMap<T> dijkstra_dist;
1.80 -
1.81 - public :
1.82 -
1.83 -
1.84 - Suurballe(Graph& _G, LengthMap& _length) : G(_G),
1.85 - length(_length), reversed(_G), dijkstra_dist(_G){ }
1.86 -
1.87 - ///Runs Suurballe's algorithm
1.88 -
1.89 - ///Runs Suurballe's algorithm
1.90 - ///Returns true iff there are k edge-disjoint paths from s to t
1.91 - bool run(Node s, Node t, int k) {
1.92 -
1.93 - LengthMap mod_length_c = length;
1.94 - ConstMap const1map;
1.95 - //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
1.96 - TrivGraphType ize(G);
1.97 - ResGraphType res_graph(ize, reversed, const1map);
1.98 - //ModLengthMap modified_length(length, dijkstra_dist);
1.99 - //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
1.100 - //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
1.101 - Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
1.102 -
1.103 - for (int i=0; i<k; ++i){
1.104 - dijkstra.run(s);
1.105 - if (!dijkstra.reached(t)){
1.106 - //There is no k path from s to t
1.107 - return false;
1.108 - };
1.109 - {
1.110 - //We have to copy the potential
1.111 - typename ResGraphType::EdgeIt e;
1.112 - for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
1.113 - //dijkstra_dist[e] = dijkstra.distMap()[e];
1.114 - mod_length_c[Edge(e)] = mod_length_c[Edge(e)] -
1.115 - dijkstra.distMap()[res_graph.head(e)] +
1.116 - dijkstra.distMap()[res_graph.tail(e)];
1.117 - }
1.118 - }
1.119 -
1.120 - //Reversing the sortest path
1.121 - Node n=t;
1.122 - Edge e;
1.123 - while (n!=s){
1.124 - e = dijkstra.pred(n);
1.125 - n = dijkstra.predNode(n);
1.126 - reversed[e] = 1-reversed[e];
1.127 - }
1.128 -
1.129 -
1.130 - }
1.131 - return true;
1.132 - }
1.133 -
1.134 -
1.135 -
1.136 -
1.137 -
1.138 - };//class Suurballe
1.139 -
1.140 -
1.141 -
1.142 -
1.143 -} //namespace hugo
1.144 -
1.145 -#endif //HUGO_SUURBALLE_H