source:lemon-0.x/src/work/athos/minlengthpaths.h@299:54e8905344ba

Last change on this file since 299:54e8905344ba was 299:54e8905344ba, checked in by athos, 20 years ago

Renaming Suurballe to minlengthpaths

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