# source:lemon-0.x/src/work/athos/suurballe.h@276:b38f4cfa76cf

Last change on this file since 276:b38f4cfa76cf was 276:b38f4cfa76cf, checked in by athos, 20 years ago

suurballe fordulo es segfaultolo(!) valtozata

File size: 3.2 KB
Line
1// -*- c++ -*-
2#ifndef HUGO_SUURBALLE_H
3#define HUGO_SUURBALLE_H
4
5#include <iostream>
6#include <dijkstra.h>
7#include <graph_wrapper.h>
8namespace hugo {
9
10
11///\brief Implementation of Suurballe's algorithm
12///
13/// The class \ref hugo::Suurballe "Suurballe" implements
14/// Suurballe's algorithm which seeks for k edge-disjoint paths
15/// from a given source node to a given target node in an
16/// edge-weighted directed graph having minimal total cost.
17///
18///
19
20
21  template <typename Graph, typename T,
22    typename LengthMap=typename Graph::EdgeMap<T> >
23  class Suurballe {
24
25
26    //Writing maps
27    class ConstMap {
28    public :
29      typedef int ValueType;
30      int operator[](typename Graph::Edge e) const {
31        return 1;
32      }
33    };
34    /*
35    //    template <typename Graph, typename T>
36    class ModLengthMap {
37      typedef typename Graph::EdgeMap<T> EdgeMap;
38      typedef typename Graph::NodeMap<T> NodeMap;
39
40      const EdgeMap &ol;
41      const NodeMap &pot;
42    public :
43      typedef typename EdgeMap::KeyType KeyType;
44      typedef typename EdgeMap::ValueType ValueType;
45
46      double operator[](typename Graph::EdgeIt e) const {
47        return 10;//ol.get(e)-pot.get(v)-pot.get(u);
48      }
49
50      ModLengthMap(const EdgeMap &o,
51                   const NodeMap &p) :
52        ol(o), pot(p){};
53    };
54    */
55
56
57    typedef typename Graph::Node Node;
58    typedef typename Graph::NodeIt NodeIt;
59    typedef typename Graph::Edge Edge;
60    typedef typename Graph::OutEdgeIt OutEdgeIt;
61    typedef ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap > ResGraphType;
62
63    const Graph& G;
64    const LengthMap& length;
65
66
67    //auxiliary variables
68
69    typename Graph::EdgeMap<int> reversed;
70    typename Graph::NodeMap<T> dijkstra_dist;
71
72  public :
73
74
75    Suurballe(Graph& _G, LengthMap& _length) : G(_G),
76      length(_length), reversed(_G), dijkstra_dist(_G){ }
77
78    ///Runs Suurballe's algorithm
79    ///Returns true iff there are k edge-disjoint paths from s to t
80    bool run(Node s, Node t, int k) {
81
82      LengthMap mod_length_c = length;
83      ConstMap const1map;
84      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
85      ResGraphType res_graph(G, reversed, const1map);
86      //ModLengthMap modified_length(length, dijkstra_dist);
87      //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
88      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
89      Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
90
91      for (int i=0; i<k; ++i){
92        dijkstra.run(s);
93        if (!dijkstra.reached(t)){
94          //There is no k path from s to t
95          return false;
96        };
97        {
98          //We have to copy the potential
99          typename ResGraphType::EdgeIt e;
100          for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
101            //dijkstra_dist[e] = dijkstra.distMap()[e];
102            mod_length_c[Edge(e)] = mod_length_c[Edge(e)] -
104              dijkstra.distMap()[res_graph.tail(e)];
105          }
106        }
107
108        //Reversing the sortest path
109        Node n=t;
110        Edge e;
111        while (n!=s){
112          e=dijkstra.pred(n);
113          n=dijkstra.predNode(n);
114          reversed[e] = 1-reversed[e];
115        }
116
117
118      }
119      return true;
120    }
121
122
123
124
125
126  };//class Suurballe
127
128
129
130
131} //namespace hugo
132
133#endif //HUGO_SUURBALLE_H
Note: See TracBrowser for help on using the repository browser.