source:lemon-0.x/src/work/athos/minlengthpaths.h@307:0fac67bef95a

Last change on this file since 307:0fac67bef95a was 306:4d15193e3a5d, checked in by athos, 17 years ago

Compiles and segfaults again. Renamed from Suurballe.

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