COIN-OR::LEMON - Graph Library

Changeset 671:708df4dc6ab6 in lemon-0.x


Ignore:
Timestamp:
06/01/04 13:00:24 (20 years ago)
Author:
athos
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@905
Message:

Compiles now

Location:
src/work
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • src/work/athos/makefile

    r661 r671  
    1 BINARIES = min_cost_flow
     1BINARIES = bfs_test min_cost_flow
    22INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos}
    33include ../makefile
  • src/work/athos/mincostflow.h

    r662 r671  
    214214        bfs_pred(res_ab_graph);
    215215      NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy;
     216      //Teszt celbol:
     217      //BfsIterator<ResAbGraph, typename ResAbGraph::template NodeMap<bool> >
     218      //izebize(res_ab_graph, bfs_reached);
    216219      //We want to run bfs-es (more) on this graph 'res_ab_graph'
    217       Bfs < ResAbGraph ,
     220      Bfs < const ResAbGraph ,
    218221        typename ResAbGraph::template NodeMap<bool>,
    219222        typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>,
     
    234237      Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost);
    235238
     239      //We will use the number of the nodes of the graph often
     240      int number_of_nodes = graph.nodeNum();
    236241
    237242      while (max_excess > 0){
     
    251256          typename std::list<Edge>::iterator i = nonabundant_arcs.begin();
    252257          while ( i != nonabundant_arcs.end() ){
    253             if (flow[i]>=buf){
    254               Node a = abundant_components.find(res_graph.head(i));
    255               Node b = abundant_components.find(res_graph.tail(i));
     258            if (flow[*i]>=buf){
     259              Node a = abundant_components.find(res_graph.head(*i));
     260              Node b = abundant_components.find(res_graph.tail(*i));
    256261              //Merge
    257262              if (a != b){
     
    270275                if (qty_to_augment>0){
    271276                  //Find path and augment
    272                   bfs.run(non_root);
     277                  bfs.run(typename AbundantGraph::Node(non_root));
    273278                  //root should be reached
    274279                 
     
    277282                  ResGraphEdge e;
    278283                  while (n!=non_root){
    279                     e = bfs_pred(n);
     284                    e = bfs_pred[n];
    280285                    n = res_graph.tail(e);
    281286                    res_graph.augment(e,qty_to_augment);
     
    283288         
    284289                  //We know that non_root had positive excess
    285                   excess_nodes[non_root] -= qty_to_augment;
     290                  excess_nodes.set(non_root,
     291                                   excess_nodes[non_root] - qty_to_augment);
    286292                  //But what about root node
    287293                  //It might have been positive and so became larger
    288294                  if (excess_deficit[root]>0){
    289                     excess_nodes[root] += qty_to_augment;
     295                    excess_nodes.set(root,
     296                                     excess_nodes[root] + qty_to_augment);
    290297                  }
    291298                  else{
    292299                    //Or negative but not turned into positive
    293                     deficit_nodes[root] -= qty_to_augment;
     300                    deficit_nodes.set(root,
     301                                      deficit_nodes[root] - qty_to_augment);
    294302                  }
    295303
     
    304312              //Marci and Zsolt says I shouldn't do such things
    305313              nonabundant_arcs.erase(i++);
    306               abundant_arcs[i] = true;
     314              abundant_arcs[*i] = true;
    307315            }
    308316            else
     
    370378          }
    371379          else{
    372             excess_nodes[s] -= delta;
     380            excess_nodes.set(s, excess_nodes[s] - delta);
    373381          }
    374382          //Update the deficit_nodes heap
     
    380388          }
    381389          else{
    382             deficit_nodes[t] -= delta;
     390            deficit_nodes.set(t, deficit_nodes[t] - delta);
    383391          }
    384392          //Dijkstra part ends here
     
    415423     
    416424
    417       return i;
     425      //return i;
    418426    }
    419427
  • src/work/marci/bfs_dfs.h

    r650 r671  
    152152    /// the nodes which are \c false initially.
    153153    /// The constructor makes no initial changes on the maps.
    154     Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
     154    Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) :
     155      BfsIterator<Graph, ReachedMap>(_graph, _reached),
     156      pred(_pred), dist(_dist) { }
    155157    /// \c s is marked to be reached and pushed in the bfs queue.
    156158    /// If the queue is empty, then the first out-edge is processed.
     
    297299    /// the nodes which are \c false initially.
    298300    /// The constructor makes no initial changes on the maps.
    299     Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
     301    Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
    300302    /// \c s is marked to be reached and pushed in the bfs queue.
    301303    /// If the queue is empty, then the first out-edge is processed.
Note: See TracChangeset for help on using the changeset viewer.