COIN-OR::LEMON - Graph Library

Changeset 527:7550fed0cd91 in lemon-0.x for src/work


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

Nem tudom, a hugo-n miert nem megy.

Location:
src/work/athos
Files:
2 edited
1 copied

Legend:

Unmodified
Added
Removed
  • src/work/athos/makefile

    r511 r527  
    1 BINARIES = suurballe minlength_demo
     1BINARIES = suurballe minlength_demo mincostflows_test
    22INCLUDEDIRS= -I../../include -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos}
    33include ../makefile
  • src/work/athos/mincostflows.h

    r523 r527  
    3939
    4040    typedef typename LengthMap::ValueType Length;
     41
     42    typedef typename LengthMap::ValueType Length;
    4143   
    4244    typedef typename Graph::Node Node;
     
    4648    typedef typename Graph::template EdgeMap<int> EdgeIntMap;
    4749
    48     typedef ConstMap<Edge,int> ConstMap;
    49 
    50     typedef ResGraphWrapper<const Graph,int,ConstMap,EdgeIntMap> ResGraphType;
     50    //    typedef ConstMap<Edge,int> ConstMap;
     51
     52    typedef ResGraphWrapper<const Graph,int,EdgeIntMap,EdgeIntMap> ResGraphType;
    5153
    5254    class ModLengthMap {   
    5355      typedef typename ResGraphType::template NodeMap<Length> NodeMap;
    5456      const ResGraphType& G;
    55       const EdgeIntMap& rev;
     57      //      const EdgeIntMap& rev;
    5658      const LengthMap &ol;
    5759      const NodeMap &pot;
     
    6163       
    6264      ValueType operator[](typename ResGraphType::Edge e) const {     
    63         //if ( (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)] ) <0 ){
    64         //  std::cout<<"Negative length!!"<<std::endl;
    65         //}
    66         return (1-2*rev[e])*ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
     65        if (G.forward(e))
     66          return  ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
     67        else
     68          return -ol[e]-(pot[G.head(e)]-pot[G.tail(e)]);   
    6769      }     
    6870       
    6971      ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
    7072                   const LengthMap &o,  const NodeMap &p) :
    71         G(_G), rev(_rev), ol(o), pot(p){};
     73        G(_G), /*rev(_rev),*/ ol(o), pot(p){};
    7274    };//ModLengthMap
    7375
    7476
    7577   
    76 
     78    //Input
    7779    const Graph& G;
    7880    const LengthMap& length;
     81    const EdgeIntMap& capacity;
    7982
    8083    //auxiliary variables
     
    8386    //If the algorithm has finished, the edges of the seeked paths are
    8487    //exactly those that are reversed
    85     EdgeIntMap reversed;
     88    EdgeIntMap flow;
    8689   
    8790    //Container to store found paths
     
    9699
    97100
    98     MinLengthPaths(Graph& _G, LengthMap& _length) : G(_G),
    99       length(_length), reversed(_G)/*, dijkstra_dist(_G)*/{ }
     101    MinLengthPaths(Graph& _G, LengthMap& _length, EdgeIntMap& _cap) : G(_G),
     102      length(_length), capacity(_cap), flow(_G)/*, dijkstra_dist(_G)*/{ }
    100103
    101104   
     
    106109    ///Otherwise it returns the number of found edge-disjoint paths from s to t.
    107110    int run(Node s, Node t, int k) {
    108       ConstMap const1map(1);
    109 
    110 
    111       //We need a residual graph, in which some of the edges are reversed
    112       ResGraphType res_graph(G, const1map, reversed);
     111
     112
     113      //We need a residual graph
     114      ResGraphType res_graph(G, capacity, flow);
    113115
    114116      //Initialize the copy of the Dijkstra potential to zero
    115117      typename ResGraphType::template NodeMap<Length> dijkstra_dist(res_graph);
    116       ModLengthMap mod_length(res_graph, reversed, length, dijkstra_dist);
     118      ModLengthMap mod_length(res_graph, length, dijkstra_dist);
    117119
    118120      Dijkstra<ResGraphType, ModLengthMap> dijkstra(res_graph, mod_length);
     
    135137
    136138
    137         //Reversing the sortest path
     139        //Augmenting on the sortest path
    138140        Node n=t;
    139141        Edge e;
     
    141143          e = dijkstra.pred(n);
    142144          n = dijkstra.predNode(n);
    143           reversed[e] = 1-reversed[e];
     145          G.augment(e,1);
    144146        }
    145147
     
    147149      }
    148150     
     151      /*
     152        ///\TODO To be implemented later
     153
    149154      //Let's find the paths
    150155      //We put the paths into stl vectors (as an inner representation).
     
    176181       
    177182      }
     183      */
    178184
    179185      return i;
     
    207213} //namespace hugo
    208214
    209 #endif //HUGO_MINLENGTHPATHS_H
     215#endif //HUGO_MINCOSTFLOW_H
  • src/work/athos/mincostflows_test.cc

    r520 r527  
    11#include <iostream>
    22#include <list_graph.h>
    3 #include <minlengthpaths.h>
    4 #include <path.h>
     3#include <mincostflows.h>
     4//#include <path.h>
     5#include <maps.h>
    56
    67using namespace std;
     
    6162  length.set(v5_t, 8);
    6263
     64  ConstMap const1map(1);
    6365  std::cout << "Minlengthpaths algorithm test..." << std::endl;
    6466
    6567 
    6668  int k=3;
    67   MinLengthPaths< ListGraph, ListGraph::EdgeMap<int> >
    68     surb_test(graph, length);
     69  MinCostFlows< ListGraph, ListGraph::EdgeMap<int> >
     70    surb_test(graph, length, const1map);
    6971
    7072  check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
Note: See TracChangeset for help on using the changeset viewer.