COIN-OR::LEMON - Graph Library

Changeset 306:4d15193e3a5d in lemon-0.x


Ignore:
Timestamp:
04/05/04 19:33:04 (16 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@424
Message:

Compiles and segfaults again. Renamed from Suurballe.

Location:
src/work/athos
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/minlengthpaths.h

    r299 r306  
    11// -*- c++ -*-
    2 #ifndef HUGO_SUURBALLE_H
    3 #define HUGO_SUURBALLE_H
     2#ifndef HUGO_MINLENGTHPATHS_H
     3#define HUGO_MINLENGTHPATHS_H
    44
    55///\file
    6 ///\brief Suurballe algorithm.
     6///\brief An algorithm for finding k paths of minimal total length.
    77
    88#include <iostream>
    99#include <dijkstra.h>
    1010#include <graph_wrapper.h>
     11#include <maps.h>
     12
    1113namespace hugo {
    1214
    1315
    14 ///\brief Implementation of Suurballe's algorithm
     16///\brief Implementation of an algorithm for finding k paths between 2 nodes
     17  /// of minimal total length
    1518///
    16 /// The class \ref hugo::Suurballe "Suurballe" implements
    17 /// Suurballe's algorithm which seeks for k edge-disjoint paths
     19/// The class \ref hugo::MinLengthPaths "MinLengthPaths" implements
     20/// an algorithm which finds k edge-disjoint paths
    1821/// from a given source node to a given target node in an
    19 /// edge-weighted directed graph having minimal total cost.
     22/// edge-weighted directed graph having minimal total weigth (length).
    2023///
    2124///
     
    2326  template <typename Graph, typename T,
    2427    typename LengthMap=typename Graph::EdgeMap<T> >
    25   class Suurballe {
     28  class MinLengthPaths {
    2629
    2730
    28     //Writing maps
    29     class ConstMap {
    30     public :
    31       typedef int ValueType;
    32       typedef typename Graph::Edge KeyType;
     31//      class ConstMap {
     32//      public :
     33//        typedef int ValueType;
     34//        typedef typename Graph::Edge KeyType;
    3335
    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     */
     36//        int operator[](typename Graph::Edge e) const {
     37//      return 1;
     38//        }
     39//      };
    5940
    6041
     
    6344    typedef typename Graph::Edge Edge;
    6445    typedef typename Graph::OutEdgeIt OutEdgeIt;
     46    typedef typename Graph::EdgeMap<int> EdgeIntMap;
     47
     48    typedef ConstMap<Edge,int> ConstMap;
     49
    6550    typedef TrivGraphWrapper<const Graph> TrivGraphType;
    66     typedef ResGraphWrapper<TrivGraphType,int,typename Graph::EdgeMap<int>,
     51    typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
    6752      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        }
     71        return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
     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   
    6879
    6980    const Graph& G;
    7081    const LengthMap& length;
    7182
     83    //auxiliary variable
     84    //The value is 1 iff the edge is reversed
     85    EdgeIntMap reversed;
    7286
    73     //auxiliary variables
    74    
    75     typename Graph::EdgeMap<int> reversed;
    76     typename Graph::NodeMap<T> dijkstra_dist;
    7787   
    7888  public :
    7989   
    8090
    81     Suurballe(Graph& _G, LengthMap& _length) : G(_G),
    82       length(_length), reversed(_G), dijkstra_dist(_G){ }
     91    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
     92      length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
    8393
    84     ///Runs Suurballe's algorithm
     94    ///Runs the algorithm
    8595   
    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) {
     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);
    89101
    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);
     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);
    99109     
    100110      for (int i=0; i<k; ++i){
     
    102112        if (!dijkstra.reached(t)){
    103113          //There is no k path from s to t
    104           return false;
     114          return ++i;
    105115        };
     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        /*
    106127        {
    107128          //We have to copy the potential
     
    114135          }
    115136        }
    116        
     137        */
     138
    117139        //Reversing the sortest path
    118140        Node n=t;
     
    126148         
    127149      }
    128       return true;
     150      return k;
    129151    }
    130152           
     
    133155
    134156
    135   };//class Suurballe
     157  };//class MinLengthPaths
    136158
    137159
     
    140162} //namespace hugo
    141163
    142 #endif //HUGO_SUURBALLE_H
     164#endif //HUGO_MINLENGTHPATHS_H
  • src/work/athos/suurballe.cc

    r292 r306  
    55
    66#include <list_graph.h>
    7 #include <suurballe.h>
     7#include <minlengthpaths.h>
    88
    99using namespace hugo;
     
    120120 
    121121  int k=3;
    122   Suurballe<ListGraph, int> surb_test(graph, length);
     122  MinLengthPaths<ListGraph, int> surb_test(graph, length);
    123123  std::cout << surb_test.run(s,t,k)<<std::endl;
    124124
Note: See TracChangeset for help on using the changeset viewer.