COIN-OR::LEMON - Graph Library

Changeset 530:d9c06ac0b3a3 in lemon-0.x


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

Minimum cost flows of small values: algorithm from Andras Frank's lecture notes (approximately)

Location:
src/work/athos
Files:
2 edited

Legend:

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

    r527 r530  
    1212#include <maps.h>
    1313#include <vector.h>
    14 
     14#include <for_each_macros.h>
    1515
    1616namespace hugo {
     
    3535  ///
    3636  ///\author Attila Bernath
    37   template <typename Graph, typename LengthMap>
     37  template <typename Graph, typename LengthMap, typename CapacityMap>
    3838  class MinCostFlows {
    3939
    4040    typedef typename LengthMap::ValueType Length;
    4141
    42     typedef typename LengthMap::ValueType Length;
     42    //Warning: this should be integer type
     43    typedef typename CapacityMap::ValueType Capacity;
    4344   
    4445    typedef typename Graph::Node Node;
     
    5051    //    typedef ConstMap<Edge,int> ConstMap;
    5152
    52     typedef ResGraphWrapper<const Graph,int,EdgeIntMap,EdgeIntMap> ResGraphType;
    53 
     53    typedef ResGraphWrapper<const Graph,int,CapacityMap,EdgeIntMap> ResGraphType;
     54    typedef typename ResGraphType::Edge ResGraphEdge;
    5455    class ModLengthMap {   
    5556      typedef typename ResGraphType::template NodeMap<Length> NodeMap;
     
    6970      }     
    7071       
    71       ModLengthMap(const ResGraphType& _G, const EdgeIntMap& _rev,
     72      ModLengthMap(const ResGraphType& _G,
    7273                   const LengthMap &o,  const NodeMap &p) :
    7374        G(_G), /*rev(_rev),*/ ol(o), pot(p){};
     
    7980    const Graph& G;
    8081    const LengthMap& length;
    81     const EdgeIntMap& capacity;
     82    const CapacityMap& capacity;
    8283
    8384    //auxiliary variables
     
    99100
    100101
    101     MinLengthPaths(Graph& _G, LengthMap& _length, EdgeIntMap& _cap) : G(_G),
     102    MinCostFlows(Graph& _G, LengthMap& _length, CapacityMap& _cap) : G(_G),
    102103      length(_length), capacity(_cap), flow(_G)/*, dijkstra_dist(_G)*/{ }
    103104
     
    110111    int run(Node s, Node t, int k) {
    111112
    112 
     113      //Resetting variables from previous runs
     114      total_length = 0;
     115      FOR_EACH_LOC(typename Graph::EdgeIt, e, G){
     116        flow.set(e,0);
     117      }
     118
     119     
    113120      //We need a residual graph
    114121      ResGraphType res_graph(G, capacity, flow);
     
    139146        //Augmenting on the sortest path
    140147        Node n=t;
    141         Edge e;
     148        ResGraphEdge e;
    142149        while (n!=s){
    143150          e = dijkstra.pred(n);
    144151          n = dijkstra.predNode(n);
    145           G.augment(e,1);
     152          res_graph.augment(e,1);
     153          //Let's update the total length
     154          if (res_graph.forward(e))
     155            total_length += length[e];
     156          else
     157            total_length -= length[e];     
    146158        }
    147159
     
    149161      }
    150162     
    151       /*
    152         ///\TODO To be implemented later
    153 
    154       //Let's find the paths
    155       //We put the paths into stl vectors (as an inner representation).
    156       //In the meantime we lose the information stored in 'reversed'.
    157       //We suppose the lengths to be positive now.
    158 
    159       //Meanwhile we put the total length of the found paths
    160       //in the member variable total_length
    161       paths.clear();
    162       total_length=0;
    163       paths.resize(k);
    164       for (int j=0; j<i; ++j){
    165         Node n=s;
    166         OutEdgeIt e;
    167 
    168         while (n!=t){
    169 
    170 
    171           G.first(e,n);
    172          
    173           while (!reversed[e]){
    174             G.next(e);
    175           }
    176           n = G.head(e);
    177           paths[j].push_back(e);
    178           total_length += length[e];
    179           reversed[e] = 1-reversed[e];
    180         }
    181        
    182       }
    183       */
    184163
    185164      return i;
    186165    }
     166
     167
    187168
    188169    ///This function gives back the total length of the found paths.
     
    191172      return total_length;
    192173    }
     174
     175    /*
     176      ///\todo To be implemented later
    193177
    194178    ///This function gives back the \c j-th path in argument p.
     
    207191    }
    208192
    209   }; //class MinLengthPaths
     193    */
     194
     195  }; //class MinCostFlows
    210196
    211197  ///@}
  • src/work/athos/mincostflows_test.cc

    r527 r530  
    6262  length.set(v5_t, 8);
    6363
    64   ConstMap const1map(1);
    65   std::cout << "Minlengthpaths algorithm test..." << std::endl;
     64  ConstMap<Edge, int> const1map(1);
     65  std::cout << "Mincostflows algorithm test..." << std::endl;
    6666
    6767 
    6868  int k=3;
    69   MinCostFlows< ListGraph, ListGraph::EdgeMap<int> >
     69  MinCostFlows< ListGraph, ListGraph::EdgeMap<int>, ConstMap<Edge, int> >
    7070    surb_test(graph, length, const1map);
    7171
    7272  check(  surb_test.run(s,t,k) == 2 && surb_test.totalLength() == 46,"Two paths, total length should be 46");
    7373
     74  k=1;
     75  check(  surb_test.run(s,t,k) == 1 && surb_test.totalLength() == 19,"One path, total length should be 19");
     76 
     77  //cout << surb_test.run(s,t,k) << surb_test.totalLength()<<endl;
     78  /*
    7479  typedef DirPath<ListGraph> DPath;
    7580  DPath P(graph);
     
    8691  surb_test.getPath(P,0);
    8792  check(P.length() == 4, "First path should contain 4 edges."); 
    88 
     93  */
    8994  cout << (passed ? "All tests passed." : "Some of the tests failed!!!")
    9095       << endl;
Note: See TracChangeset for help on using the changeset viewer.