COIN-OR::LEMON - Graph Library

Changeset 662:0155001b6f65 in lemon-0.x


Ignore:
Timestamp:
05/25/04 19:01:26 (15 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@865
Message:

Almost compiles.

Location:
src/work/athos
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/min_cost_flow.cc

    r661 r662  
    4242  Node t=graph.addNode();
    4343
     44  ListGraph::NodeMap<int> supply_demand(graph);
     45
     46  supply_demand.set(s, 2);
     47  supply_demand.set(v1, 3);
     48  supply_demand.set(v3, -1);
     49  supply_demand.set(t, -4);
     50
    4451  Edge s_v1=graph.addEdge(s, v1);
    4552  Edge v1_v2=graph.addEdge(v1, v2);
     
    8289    min_cost_flow_test(graph, cost, supply_demand);
    8390
    84   int k=1;
     91  min_cost_flow_test.run();
     92  //int k=1;
    8593
    8694  /*
  • src/work/athos/mincostflow.h

    r661 r662  
    1212#include <vector>
    1313#include <list>
     14#include <values.h>
    1415#include <hugo/for_each_macros.h>
    1516#include <hugo/unionfind.h>
     17#include <hugo/bin_heap.h>
     18#include <bfs_dfs.h>
    1619
    1720namespace hugo {
     
    9497    //To store the flow
    9598    FlowMap flow;
    96     //To store the potentila (dual variables)
    97     typename Graph::template NodeMap<Cost> potential;
     99    //To store the potential (dual variables)
     100    typedef typename Graph::template NodeMap<Cost> PotentialMap;
     101    PotentialMap potential;
    98102    //To store excess-deficit values
    99103    SupplyDemandMap excess_deficit;
     
    106110
    107111
    108     MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand) : graph(_graph),
    109       cost(_cost), supply_demand(_supply_demand), flow(_graph), potential(_graph){ }
     112   MinCostFlow(Graph& _graph, CostMap& _cost, SupplyDemandMap& _supply_demand):
     113     graph(_graph),
     114     cost(_cost),
     115     supply_demand(_supply_demand),
     116     flow(_graph),
     117     potential(_graph),
     118     excess_deficit(_graph){ }
    110119
    111120   
     
    122131
    123132      typedef typename Graph::template NodeMap<int> HeapMap;
    124       typedef Heap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
     133      typedef BinHeap< Node, SupplyDemand, typename Graph::template NodeMap<int>,
    125134        std::greater<SupplyDemand> >    HeapType;
    126135
     
    134143
    135144      //A container to store nonabundant arcs
    136       list<Edge> nonabundant_arcs;
     145      std::list<Edge> nonabundant_arcs;
    137146
    138147       
     
    148157
    149158      //A union-find structure to store the abundant components
    150       UFE::MapType abund_comp_map(graph);
     159      typename UFE::MapType abund_comp_map(graph);
    151160      UFE abundant_components(abund_comp_map);
    152161
     
    178187     
    179188      ///\bug This is a serious cheat here, before we have an uncapacitated ResGraph
    180       ConstEdgeMap const_inf_map(MAX_INT);
     189      ConstEdgeMap const_inf_map(MAXINT);
    181190     
    182191      //We need a residual graph which is uncapacitated
     
    184193     
    185194      //An EdgeMap to tell which arcs are abundant
    186       template typename Graph::EdgeMap<bool> abundant_arcs(graph);
     195      typename Graph::template EdgeMap<bool> abundant_arcs(graph);
    187196
    188197      //Let's construct the sugraph consisting only of the abundant edges
    189198      typedef ConstMap< typename Graph::Node, bool > ConstNodeMap;
    190199      ConstNodeMap const_true_map(true);
    191       typedef SubGraphWrapper< Graph, ConstNodeMap,
    192          template typename Graph::EdgeMap<bool> >
     200      typedef SubGraphWrapper< const Graph, ConstNodeMap,
     201         typename Graph::template EdgeMap<bool> >
    193202        AbundantGraph;
    194203      AbundantGraph abundant_graph(graph, const_true_map, abundant_arcs );
    195204     
    196205      //Let's construct the residual graph for the abundant graph
    197       typedef ResGraphWrapper<const AbundantGraph,int,CapacityMap,EdgeIntMap>
     206      typedef ResGraphWrapper<const AbundantGraph,int,ConstEdgeMap,FlowMap>
    198207        ResAbGraph;
    199208      //Again uncapacitated
     
    201210     
    202211      //We need things for the bfs
    203       typename ResAbGraph::NodeMap<bool> bfs_reached(res_ab_graph);
    204       typename ResAbGraph::NodeMap<typename ResAbGraph::Edge>
     212      typename ResAbGraph::template NodeMap<bool> bfs_reached(res_ab_graph);
     213      typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>
    205214        bfs_pred(res_ab_graph);
    206       NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy(res_ab_graph);
     215      NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy;
    207216      //We want to run bfs-es (more) on this graph 'res_ab_graph'
    208217      Bfs < ResAbGraph ,
    209         typename ResAbGraph::NodeMap<bool>,
    210         typename ResAbGraph::NodeMap<typename ResAbGraph::Edge>,
     218        typename ResAbGraph::template NodeMap<bool>,
     219        typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>,
    211220        NullMap<typename ResAbGraph::Node, int> >
    212221        bfs(res_ab_graph, bfs_reached, bfs_pred, bfs_dist_dummy);
     222      /*This is what Marci wants for a bfs
     223        template <typename Graph,
     224            typename ReachedMap=typename Graph::template NodeMap<bool>,
     225            typename PredMap
     226            =typename Graph::template NodeMap<typename Graph::Edge>,
     227            typename DistMap=typename Graph::template NodeMap<int> >
     228            class Bfs : public BfsIterator<Graph, ReachedMap> {
     229
     230       */
    213231     
    214232      ModCostMap mod_cost(res_graph, cost, potential);
     
    231249        {
    232250          SupplyDemand buf=8*number_of_nodes*delta;
    233           list<Edge>::iterator i = nonabundant_arcs.begin();
     251          typename std::list<Edge>::iterator i = nonabundant_arcs.begin();
    234252          while ( i != nonabundant_arcs.end() ){
    235253            if (flow[i]>=buf){
     
    302320
    303321
    304         while(max_excess > (n-1)*delta/n){
     322        while(max_excess > (number_of_nodes-1)*delta/number_of_nodes){
    305323         
    306324         
     
    411429    ///Returns a const reference to the EdgeMap \c flow. \pre \ref run() must
    412430    ///be called before using this function.
    413     const EdgeIntMap &getFlow() const { return flow;}
     431    const FlowMap &getFlow() const { return flow;}
    414432
    415433  ///Returns a const reference to the NodeMap \c potential (the dual solution).
    416434    /// \pre \ref run() must be called before using this function.
    417     const EdgeIntMap &getPotential() const { return potential;}
     435    const PotentialMap &getPotential() const { return potential;}
    418436
    419437    ///This function checks, whether the given solution is optimal
Note: See TracChangeset for help on using the changeset viewer.