COIN-OR::LEMON - Graph Library

Changeset 310:76c005b15354 in lemon-0.x


Ignore:
Timestamp:
04/05/04 20:24:37 (20 years ago)
Author:
Mihaly Barasz
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@428
Message:

Converted the "minlengthpaths" alg. to the new style graph_wrappers.

Location:
src/work
Files:
1 deleted
5 edited

Legend:

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

    r306 r310  
    1414
    1515
    16 ///\brief Implementation of an algorithm for finding k paths between 2 nodes
     16  ///\brief Implementation of an algorithm for finding k paths between 2 nodes
    1717  /// 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 ///
     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).
    2523
    26   template <typename Graph, typename T,
    27     typename LengthMap=typename Graph::EdgeMap<T> >
     24  template <typename Graph, typename LengthMap>
    2825  class MinLengthPaths {
    2926
    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 
     27    typedef typename LengthMap::ValueType Length;
    4128
    4229    typedef typename Graph::Node Node;
     
    4835    typedef ConstMap<Edge,int> ConstMap;
    4936
    50     typedef TrivGraphWrapper<const Graph> TrivGraphType;
    51     typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
    52       ConstMap> ResGraphType;
     37    typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
    5338
    5439
    55     //template <typename Graph, typename T>
    5640    class ModLengthMap {   
    57       typedef typename ResGraphType::NodeMap<T> NodeMap;
     41      typedef typename ResGraphType::NodeMap<Length> NodeMap;
    5842      const ResGraphType& G;
    59       const EdgeIntMap& rev; 
    60       const LengthMap &ol;   
    61       const NodeMap &pot;     
     43      const EdgeIntMap& rev;
     44      const LengthMap &ol;
     45      const NodeMap &pot;
    6246    public :
    6347      typedef typename LengthMap::KeyType KeyType;
     
    7256      }     
    7357
    74       ModLengthMap(  const ResGraphType& _G, const EdgeIntMap& _rev,
    75                      const LengthMap &o,  const NodeMap &p) :
     58      ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
     59                   const LengthMap &o,  const NodeMap &p) :
    7660        G(_G), rev(_rev), ol(o), pot(p){};
    7761    };
     
    8771   
    8872  public :
    89    
     73
    9074
    9175    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
     
    10387
    10488      //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);
     89      typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
     90      ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
    10791
    10892      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
     
    11296        if (!dijkstra.reached(t)){
    11397          //There is no k path from s to t
    114           return ++i;
     98          /// \TODO mit keresett itt ez a ++?
     99          return i;
    115100        };
    116101       
     
    123108        }
    124109
    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)] -
    133               dijkstra.distMap()[res_graph.head(e)] + 
    134               dijkstra.distMap()[res_graph.tail(e)];
    135           }
    136         }
    137         */
    138110
    139111        //Reversing the sortest path
     
    150122      return k;
    151123    }
    152            
    153      
    154124
    155125
    156126
    157   };//class MinLengthPaths
    158127
    159128
     129  }; //class MinLengthPaths
    160130
    161131
  • src/work/athos/suurballe.cc

    r306 r310  
    120120 
    121121  int k=3;
    122   MinLengthPaths<ListGraph, int> surb_test(graph, length);
    123   std::cout << surb_test.run(s,t,k)<<std::endl;
     122  MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> >
     123    surb_test(graph, length);
     124  std::cout << surb_test.run(s,t,k) << std::endl;
    124125
    125126  return 0;
  • src/work/klao/Makefile

    r283 r310  
    1 BINARIES = path_test map_test
     1BINARIES = path_test map_test minlengthpaths
    22INCLUDEDIRS= -I. -I.. -I../../include -I../{marci,jacint,alpar,johanna,akos}
    33include ../makefile
  • src/work/klao/minlengthpaths.cc

    r308 r310  
    120120 
    121121  int k=3;
    122   MinLengthPaths<ListGraph, int> surb_test(graph, length);
    123   std::cout << surb_test.run(s,t,k)<<std::endl;
     122  MinLengthPaths<ListGraph, ListGraph::EdgeMap<int> >
     123    surb_test(graph, length);
     124  std::cout << surb_test.run(s,t,k) << std::endl;
    124125
    125126  return 0;
  • src/work/klao/minlengthpaths.h

    r308 r310  
    1414
    1515
    16 ///\brief Implementation of an algorithm for finding k paths between 2 nodes
     16  ///\brief Implementation of an algorithm for finding k paths between 2 nodes
    1717  /// 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 ///
     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).
    2523
    26   template <typename Graph, typename T,
    27     typename LengthMap=typename Graph::EdgeMap<T> >
     24  template <typename Graph, typename LengthMap>
    2825  class MinLengthPaths {
    2926
    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 
     27    typedef typename LengthMap::ValueType Length;
    4128
    4229    typedef typename Graph::Node Node;
     
    4835    typedef ConstMap<Edge,int> ConstMap;
    4936
    50     typedef TrivGraphWrapper<const Graph> TrivGraphType;
    51     typedef ResGraphWrapper<TrivGraphType,int,EdgeIntMap,
    52       ConstMap> ResGraphType;
     37    typedef ResGraphWrapper<const Graph,int,EdgeIntMap,ConstMap> ResGraphType;
    5338
    5439
    55     //template <typename Graph, typename T>
    5640    class ModLengthMap {   
    57       typedef typename ResGraphType::NodeMap<T> NodeMap;
     41      typedef typename ResGraphType::NodeMap<Length> NodeMap;
    5842      const ResGraphType& G;
    59       const EdgeIntMap& rev; 
    60       const LengthMap &ol;   
    61       const NodeMap &pot;     
     43      const EdgeIntMap& rev;
     44      const LengthMap &ol;
     45      const NodeMap &pot;
    6246    public :
    6347      typedef typename LengthMap::KeyType KeyType;
     
    7256      }     
    7357
    74       ModLengthMap(  const ResGraphType& _G, const EdgeIntMap& _rev,
    75                      const LengthMap &o,  const NodeMap &p) :
     58      ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
     59                   const LengthMap &o,  const NodeMap &p) :
    7660        G(_G), rev(_rev), ol(o), pot(p){};
    7761    };
     
    8771   
    8872  public :
    89    
     73
    9074
    9175    MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
     
    10387
    10488      //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);
     89      typename ResGraphType::NodeMap<Length> dijkstra_dist(res_graph);
     90      ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
    10791
    10892      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
     
    11296        if (!dijkstra.reached(t)){
    11397          //There is no k path from s to t
    114           return ++i;
     98          /// \TODO mit keresett itt ez a ++?
     99          return i;
    115100        };
    116101       
     
    123108        }
    124109
    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)] -
    133               dijkstra.distMap()[res_graph.head(e)] + 
    134               dijkstra.distMap()[res_graph.tail(e)];
    135           }
    136         }
    137         */
    138110
    139111        //Reversing the sortest path
     
    150122      return k;
    151123    }
    152            
    153      
    154124
    155125
    156126
    157   };//class MinLengthPaths
    158127
    159128
     129  }; //class MinLengthPaths
    160130
    161131
Note: See TracChangeset for help on using the changeset viewer.