COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/athos/suurballe.h @ 291:65460cbf9e90

Last change on this file since 291:65460cbf9e90 was 291:65460cbf9e90, checked in by athos, 20 years ago

Mukodik a Suurballe

File size: 3.4 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      typedef typename Graph::Edge KeyType;
31
32      int operator[](typename Graph::Edge e) const {
33        return 1;
34      }
35    };
36    /*
37    //    template <typename Graph, typename T>
38    class ModLengthMap {   
39      typedef typename Graph::EdgeMap<T> EdgeMap;
40      typedef typename Graph::NodeMap<T> NodeMap;
41
42      const EdgeMap &ol;   
43      const NodeMap &pot;     
44    public :
45      typedef typename EdgeMap::KeyType KeyType;
46      typedef typename EdgeMap::ValueType ValueType;
47
48      double operator[](typename Graph::EdgeIt e) const {     
49        return 10;//ol.get(e)-pot.get(v)-pot.get(u);   
50      }     
51
52      ModLengthMap(const EdgeMap &o,
53                   const NodeMap &p) :
54        ol(o), pot(p){};
55    };
56    */
57
58
59    typedef typename Graph::Node Node;
60    typedef typename Graph::NodeIt NodeIt;
61    typedef typename Graph::Edge Edge;
62    typedef typename Graph::OutEdgeIt OutEdgeIt;
63    typedef TrivGraphWrapper<const Graph> TrivGraphType;
64    typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
65      ConstMap> ResGraphType;
66
67    const Graph& G;
68    const LengthMap& length;
69
70
71    //auxiliary variables
72   
73    typename Graph::EdgeMap<int> reversed;
74    typename Graph::NodeMap<T> dijkstra_dist;
75   
76  public :
77   
78
79    Suurballe(Graph& _G, LengthMap& _length) : G(_G),
80      length(_length), reversed(_G), dijkstra_dist(_G){ }
81
82    ///Runs Suurballe's algorithm
83    ///Returns true iff there are k edge-disjoint paths from s to t
84    bool run(Node s, Node t, int k) {
85
86      LengthMap mod_length_c = length;
87      ConstMap const1map;
88      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
89      TrivGraphType ize(G);
90      ResGraphType res_graph(ize, reversed, const1map);
91      //ModLengthMap modified_length(length, dijkstra_dist);
92      //Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, modified_length);
93      //ResGraphWrapper< Graph,T,typename Graph::EdgeMap<int>, ConstMap>
94      Dijkstra<ResGraphType, LengthMap> dijkstra(res_graph, mod_length_c);
95     
96      for (int i=0; i<k; ++i){
97        dijkstra.run(s);
98        if (!dijkstra.reached(t)){
99          //There is no k path from s to t
100          return false;
101        };
102        {
103          //We have to copy the potential
104          typename ResGraphType::EdgeIt e;
105          for ( res_graph.first(e) ; res_graph.valid(e) ; res_graph.next(e) ) {
106            //dijkstra_dist[e] = dijkstra.distMap()[e];
107            mod_length_c[Edge(e)] = mod_length_c[Edge(e)] -
108              dijkstra.distMap()[res_graph.head(e)] + 
109              dijkstra.distMap()[res_graph.tail(e)];
110          }
111        }
112       
113        //Reversing the sortest path
114        Node n=t;
115        Edge e;
116        while (n!=s){
117          e = dijkstra.pred(n);
118          n = dijkstra.predNode(n);
119          reversed[e] = 1-reversed[e];
120        }
121
122         
123      }
124      return true;
125    }
126           
127     
128
129
130
131  };//class Suurballe
132
133
134
135
136} //namespace hugo
137
138#endif //HUGO_SUURBALLE_H
Note: See TracBrowser for help on using the repository browser.