COIN-OR::LEMON - Graph Library

Changeset 372:e6a156fc186d in lemon-0.x


Ignore:
Timestamp:
04/22/04 16:11:28 (20 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@502
Message:
 
Location:
src/work/jacint
Files:
1 added
6 edited

Legend:

Unmodified
Added
Removed
  • src/work/jacint/dijkstra.cc

    r258 r372  
    22#include <fstream>
    33
    4 #include <smart_graph.h>
    5 #include <list_graph.h>
    6 #include <dimacs.h>
     4#include <list_graph.hh>
     5#include <dimacs.hh>
    76#include <dijkstra.h>
    87#include <time_measure.h>
    9 
    10 #include <bin_heap.h>
    11 #include <fib_heap.h>
     8#include <bin_heap.hh>
    129
    1310using namespace hugo;
    1411
    1512int main(int, char **) {
    16   typedef SmartGraph::Node Node;
    17   typedef SmartGraph::NodeIt NodeIt;
    18   typedef SmartGraph::InEdgeIt InEdgeIt;
     13 
     14  typedef ListGraph Graph;
    1915
    20   SmartGraph G;
     16  typedef Graph::Node Node;
     17  typedef Graph::EdgeIt EdgeIt;
     18
     19  Graph G;
    2120  Node s, t;
    22   SmartGraph::EdgeMap<int> cap(G);
     21  Graph::EdgeMap<int> cap(G);
    2322  readDimacsMaxFlow(std::cin, G, s, t, cap);
    24 
    25   std::cout << "dijkstra demo ..." << std::endl;
     23  Timer ts;
    2624 
    27   double pre_time=currTime();
    28   Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
    29     SmartGraph::NodeMap<int> > > dijkstra_test(G, cap);
    30   dijkstra_test.run(s);
     25  std::cout << "Testing dijkstra.h with Fibonacci-heap
     26implementation fib_heap.h ..." << std::endl;
     27 
     28  Dijkstra<Graph, int
     29      //      , BinHeap<ListGraph::NodeIt, int, ListGraph::NodeMap<int> >
     30> dijkstra_test(G, s, cap);
     31   ts.reset();
     32    dijkstra_test.run();
     33    std::cout << "elapsed time: " << ts << std::endl;
    3134  double post_time=currTime();
    3235   
    33     std::cout << "running time with fib_heap: "
    34             << post_time-pre_time << " sec"<< std::endl;
     36  std::cout << "running time: " << post_time-pre_time << " sec"<< std::endl;
    3537 
    36   pre_time=currTime();
    37   Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int,
    38     SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap);
    39   dijkstra_test2.run(s);
    40   post_time=currTime();
    41  
    42   std::cout << "running time with bin_heap: "
    43             << post_time-pre_time << " sec"<< std::endl;
    44  
     38  EachEdgeIt e;
    4539
    46   int hiba_fib=0;
    47   int hiba_bin=0;
    48   NodeIt u;
    49   for ( G.first(u) ; G.valid(u); G.next(u) ) {
    50     InEdgeIt e;
    51     for ( G.first(e,u); G.valid(e); G.next(e) ) {
    52       Node v=G.tail(e);
    53       if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
    54         {
    55           std::cout<<"Hibas el a fibonaccis Dijkstraban: "
    56                    << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
    57             cap[e]<<std::endl;
    58           ++hiba_fib;
    59         }
    60       if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
    61         {
    62           std::cout<<"Hibas el a binarisos Dijkstraban: "
    63                    << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
    64             cap[e]<<std::endl;
    65           ++hiba_bin;
    66         }
    67       if ( e==dijkstra_test.pred(u) &&
    68            dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
    69         {
    70           std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
    71             dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
    72           ++hiba_fib;
    73         }
    74       if ( e==dijkstra_test2.pred(u) &&
    75            dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
    76         {
    77           std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
    78             dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
    79           ++hiba_bin;
    80         }
     40  int hiba=0;
     41
     42  int edge=0;
     43
     44  for ( G.getFirst(e) ; G.valid(e); G.next(e) ) {
     45    NodeIt u=G.tail(e);
     46    NodeIt v=G.head(e);
     47    ++edge;
     48    if ( dijkstra_test.dist(v) - dijkstra_test.dist(u) > cap.get(e) ) {
     49      std::cout<<"Hiba: "<<edge<<": "<<dijkstra_test.dist(v) - dijkstra_test.dist(u) - cap.get(e)<<std::endl;
     50      ++hiba;
    8151    }
    82  
    83     if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
    84       std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
     52  }
    8553
    86 
    87  }
    88 
    89   std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
    90             << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
    91  
    92   std::cout << "Hibas elek szama a binarisos Dijkstraban: "
    93             << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
    94  
    95 
    96 
     54  std::cout << "Osszhibas el: " << hiba << " osszel: " << G.edgeNum() << std::endl;
    9755
    9856  return 0;
  • src/work/jacint/dijkstra.h

    r220 r372  
    11// -*- C++ -*-
     2
    23/*
    34 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
     
    2728#define HUGO_DIJKSTRA_H
    2829
     30///\file
     31///\brief Dijkstra algorithm.
     32
    2933#include <fib_heap.h>
     34#include <bin_heap.h>
    3035#include <invalid.h>
    3136
    3237namespace hugo {
    3338 
    34   template <typename Graph, typename T,
    35     typename Heap=FibHeap<typename Graph::Node, T,
    36     typename Graph::NodeMap<int> >,
    37     typename LengthMap=typename Graph::EdgeMap<T> >
     39  //Alpar: Changed the order of the parameters
     40 
     41  ///%Dijkstra algorithm class.
     42
     43  ///This class provides an efficient implementation of %Dijkstra algorithm.
     44  ///The edge lengths are passed to the algorithm using a
     45  ///\ref ReadMapSkeleton "readable map",
     46  ///so it is easy to change it to any kind of length.
     47  ///
     48  ///The type of the length is determined by the \c ValueType of the length map.
     49  ///
     50  ///It is also possible to change the underlying priority heap.
     51  ///
     52  ///\param Graph The graph type the algorithm runs on.
     53  ///\param LengthMap This read-only
     54  ///EdgeMap
     55  ///determines the
     56  ///lengths of the edges. It is read once for each edge, so the map
     57  ///may involve in relatively time consuming process to compute the edge
     58  ///length if it is necessary. The default map type is
     59  ///\ref GraphSkeleton::EdgeMap "Graph::EdgeMap<int>"
     60  ///\param Heap The heap type used by the %Dijkstra
     61  ///algorithm. The default
     62  ///is using \ref BinHeap "binary heap".
     63 
     64#ifdef DOXYGEN
     65  template <typename Graph,
     66            typename LengthMap,
     67            typename Heap>
     68#else
     69  template <typename Graph,
     70            typename LengthMap=typename Graph::EdgeMap<int>,
     71            template <class,class,class> class Heap = BinHeap >
     72#endif
    3873  class Dijkstra{
     74  public:
    3975    typedef typename Graph::Node Node;
    4076    typedef typename Graph::NodeIt NodeIt;
     
    4278    typedef typename Graph::OutEdgeIt OutEdgeIt;
    4379   
     80    typedef typename LengthMap::ValueType ValueType;
     81    typedef typename Graph::NodeMap<Edge> PredMap;
     82    typedef typename Graph::NodeMap<Node> PredNodeMap;
     83    typedef typename Graph::NodeMap<ValueType> DistMap;
     84
     85  private:
    4486    const Graph& G;
    4587    const LengthMap& length;
    46     typename Graph::NodeMap<Edge> predecessor;
    47     typename Graph::NodeMap<T> distance;
    48     //FIXME:
    49     typename Graph::NodeMap<bool> reach;
    50     //typename Graph::NodeMap<int> reach;
     88    PredMap predecessor;
     89    PredNodeMap pred_node;
     90    DistMap distance;
    5191   
    5292  public :
    5393   
    54     /*
    55       The distance of the nodes is 0.
    56     */
    57     Dijkstra(Graph& _G, LengthMap& _length) : G(_G),
    58       length(_length), predecessor(_G), distance(_G), reach(_G) { }
    59    
    60 
    61     void run(Node s) {
    62      
    63       NodeIt u;
    64       for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
    65         predecessor.set(u,INVALID);
    66         distance.set(u,0);
    67         reach.set(u,false);
    68       }
    69      
    70       //FIXME:
    71       typename Graph::NodeMap<bool> scanned(G,false);
    72       //typename Graph::NodeMap<int> scanned(G,false);
    73       typename Graph::NodeMap<int> heap_map(G,-1);
    74      
    75       Heap heap(heap_map);
    76 
    77       heap.push(s,0);
    78       reach.set(s, true);
    79 
     94    Dijkstra(Graph& _G, LengthMap& _length) :
     95      G(_G), length(_length), predecessor(_G), pred_node(_G), distance(_G) { }
     96   
     97    void run(Node s);
     98   
     99    ///The distance of a node from the source.
     100
     101    ///Returns the distance of a node from the source.
     102    ///\pre \ref run() must be called before using this function.
     103    ///\warning If node \c v in unreachable from the source the return value
     104    ///of this funcion is undefined.
     105    ValueType dist(Node v) const { return distance[v]; }
     106    ///Returns the edges of the shortest path tree.
     107
     108    ///For a node \c v it returns the last edge of the shortest path
     109    ///from the source to \c v or INVALID if \c v is unreachable
     110    ///from the source.
     111    ///\pre \ref run() must be called before using this function.
     112    Edge pred(Node v) const { return predecessor[v]; }
     113    ///Returns the nodes of the shortest paths.
     114
     115    ///For a node \c v it returns the last but one node of the shortest path
     116    ///from the source to \c v or INVALID if \c v is unreachable
     117    ///from the source.
     118    ///\pre \ref run() must be called before using this function.
     119    Node predNode(Node v) const { return pred_node[v]; }
     120   
     121    ///Returns a reference to the NodeMap of distances.
     122
     123    ///\pre \ref run() must be called before using this function.
     124    ///
     125    const DistMap &distMap() const { return distance;}
     126    ///Returns a reference to the shortest path tree map.
     127
     128    ///Returns a reference to the NodeMap of the edges of the
     129    ///shortest path tree.
     130    ///\pre \ref run() must be called before using this function.
     131    const PredMap &predMap() const { return predecessor;}
     132    ///Returns a reference to the map of nodes of  shortest paths.
     133
     134    ///Returns a reference to the NodeMap of the last but one nodes of the
     135    ///shortest paths.
     136    ///\pre \ref run() must be called before using this function.
     137    const PredNodeMap &predNodeMap() const { return pred_node;}
     138
     139    ///Checks if a node is reachable from the source.
     140
     141    ///Returns \c true if \c v is reachable from the source.
     142    ///\warning the source node is reported to be unreached!
     143    ///\todo Is this what we want?
     144    ///\pre \ref run() must be called before using this function.
     145    ///
     146    bool reached(Node v) { return G.valid(predecessor[v]); }
     147   
     148  };
     149 
     150
     151  // **********************************************************************
     152  //  IMPLEMENTATIONS
     153  // **********************************************************************
     154
     155  ///Runs %Dijkstra algorithm from node the source.
     156
     157  ///This method runs the %Dijkstra algorithm from a source node \c s
     158  ///in order to
     159  ///compute the
     160  ///shortest path to each node. The algorithm computes
     161  ///- The shortest path tree.
     162  ///- The distance of each node from the source.
     163  template <typename Graph, typename LengthMap,
     164            template<class,class,class> class Heap >
     165  void Dijkstra<Graph,LengthMap,Heap>::run(Node s) {
     166   
     167    NodeIt u;
     168    for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
     169      predecessor.set(u,INVALID);
     170      pred_node.set(u,INVALID);
     171      // If a node is unreacheable, then why should be the dist=0?
     172      // distance.set(u,0);
     173      //      reach.set(u,false);
     174    }
     175   
     176    typename Graph::NodeMap<int> heap_map(G,-1);
     177   
     178    Heap<Node,ValueType,typename Graph::NodeMap<int> > heap(heap_map);
     179   
     180    heap.push(s,0);
     181   
    80182      while ( !heap.empty() ) {
    81183       
    82184        Node v=heap.top();
    83         T oldvalue=heap.get(v);
     185        ValueType oldvalue=heap[v];
    84186        heap.pop();
    85187        distance.set(v, oldvalue);
    86         scanned.set(v,true);
    87 
    88         OutEdgeIt e;
    89         for( G.first(e,v); G.valid(e); G.next(e)) {
     188       
     189        { //FIXME this bracket is for e to be local
     190          OutEdgeIt e;
     191        for(G.first(e, v);
     192            G.valid(e); G.next(e)) {
    90193          Node w=G.head(e);
    91            
    92           if ( !scanned[w] ) {
    93             if ( !reach[w] ) {
    94               reach.set(w,true);
    95               heap.push(w,oldvalue+length[e]);
     194         
     195          switch(heap.state(w)) {
     196          case heap.PRE_HEAP:
     197            heap.push(w,oldvalue+length[e]);
     198            predecessor.set(w,e);
     199            pred_node.set(w,v);
     200            break;
     201          case heap.IN_HEAP:
     202            if ( oldvalue+length[e] < heap[w] ) {
     203              heap.decrease(w, oldvalue+length[e]);
    96204              predecessor.set(w,e);
    97             } else if ( oldvalue+length[e] < heap.get(w) ) {
    98               predecessor.set(w,e);
    99               heap.decrease(w, oldvalue+length[e]);
     205              pred_node.set(w,v);
    100206            }
     207            break;
     208          case heap.POST_HEAP:
     209            break;
    101210          }
    102211        }
     212      } //FIXME tis bracket
    103213      }
    104     }
    105    
    106     T dist(Node v) {
    107       return distance[v];
    108     }
    109 
    110     Edge pred(Node v) {
    111       return predecessor[v];
    112     }
    113      
    114     bool reached(Node v) {
    115       return reach[v];
    116     }
    117    
    118   };
    119  
    120 }
     214  }
     215 
     216} //END OF NAMESPACE HUGO
    121217
    122218#endif
  • src/work/jacint/makefile

    r311 r372  
    44CC=$(CXX)
    55INCLUDEDIRS ?= -I../../include -I.. -I../{marci,jacint,alpar,klao,akos,athos}
    6 CXXFLAGS = -W -Wall -ansi -pedantic -O3 $(INCLUDEDIRS) 
     6CXXFLAGS = -W -Wall -ansi -pedantic -O3 $(INCLUDEDIRS)
    77LEDAROOT ?= /ledasrc/LEDA-4.1
    88
    9 BINARIES = preflow #dijkstra prim
     9BINARIES = preflow #dijkstra_bin_fib_test #preflow # prim
    1010
    1111all: $(BINARIES)
  • src/work/jacint/preflow.cc

    r220 r372  
    11#include <iostream>
    2 #include <fstream>
    32
    43#include <smart_graph.h>
    54#include <list_graph.h>
    65#include <dimacs.h>
    7 #include <preflow.h>
     6#include <preflowproba.h>
    87#include <time_measure.h>
    98
    109using namespace hugo;
    1110
    12 // Use a DIMACS max flow file as stdin.
    13 // read_dimacs_demo < dimacs_max_flow_file
    1411int main(int, char **) {
    15   typedef SmartGraph::Node Node;
    16   typedef SmartGraph::EdgeIt EdgeIt;
     12 
     13  typedef SmartGraph Graph;
     14 
     15  typedef Graph::Node Node;
     16  typedef Graph::EdgeIt EdgeIt;
    1717
    18   SmartGraph G;
     18  Graph G;
    1919  Node s, t;
    20   SmartGraph::EdgeMap<int> cap(G);
     20  Graph::EdgeMap<int> cap(G);
    2121  readDimacsMaxFlow(std::cin, G, s, t, cap);
    22 
     22  Timer ts;
     23 
    2324  std::cout << "preflow demo ..." << std::endl;
    2425 
    25   double mintime=1000000;
    26 
    27   for ( int i=1; i!=11; ++i ) {
    28     SmartGraph::EdgeMap<int> flow(G);
    29     double pre_time=currTime();
    30     Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
    31     max_flow_test.run();
    32     double post_time=currTime();
    33     if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
    34   }
    35 
    36   SmartGraph::EdgeMap<int> flow(G);
    37   Preflow<SmartGraph, int> max_flow_test(G, s, t, cap, flow);
     26  Graph::EdgeMap<int> flow(G);
     27  Preflow<Graph, int> max_flow_test(G, s, t, cap, flow, 1);
     28  ts.reset();
    3829  max_flow_test.run();
     30  std::cout << "elapsed time: " << ts << std::endl;
    3931 
    40   SmartGraph::NodeMap<bool> cut(G);
     32  Graph::NodeMap<bool> cut(G);
    4133  max_flow_test.minCut(cut);
    4234  int min_cut_value=0;
     
    4638  }
    4739
    48   SmartGraph::NodeMap<bool> cut1(G);
     40  Graph::NodeMap<bool> cut1(G);
    4941  max_flow_test.minMinCut(cut1);
    5042  int min_min_cut_value=0;
     
    5446  }
    5547
    56   SmartGraph::NodeMap<bool> cut2(G);
     48  Graph::NodeMap<bool> cut2(G);
    5749  max_flow_test.maxMinCut(cut2);
    5850  int max_min_cut_value=0;
     
    6254      }
    6355 
    64   std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
    6556  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    6657  std::cout << "min cut value: "<< min_cut_value << std::endl;
  • src/work/jacint/preflow.h

    r330 r372  
    11// -*- C++ -*-
     2
     3//run gyorsan tudna adni a minmincutot a 2 fazis elejen , ne vegyuk be konstruktorba egy cutmapet?
     4//constzero jo igy?
     5
     6//majd marci megmondja betegyem-e bfs-t meg resgraphot
     7
    28/*
    39Heuristics:
     
    1319Constructors:
    1420
    15 Preflow(Graph, Node, Node, CapMap, FlowMap)
     21Preflow(Graph, Node, Node, CapMap, FlowMap, bool) : bool must be false if
     22     FlowMap is not constant zero, and should be true if it is
    1623
    1724Members:
     
    3037     a min cut. M should be a map of bools initialized to false.
    3138
     39FIXME reset
     40
    3241*/
    3342
     
    4554  template <typename Graph, typename T,
    4655            typename CapMap=typename Graph::EdgeMap<T>,
    47             typename FlowMap=typename Graph::EdgeMap<T> >
     56            typename FlowMap=typename Graph::EdgeMap<T> >
    4857  class Preflow {
    4958   
     
    6069    FlowMap& flow;
    6170    T value;
     71    bool constzero;
    6272
    6373  public:
    64     Preflow(const Graph& _G, Node _s, Node _t, const CapMap& _capacity,
    65             FlowMap& _flow ) :
    66       G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow) {}
    67 
     74    Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity,
     75            FlowMap& _flow, bool _constzero ) :
     76      G(_G), s(_s), t(_t), capacity(_capacity), flow(_flow), constzero(_constzero) {}
     77   
     78   
    6879    void run() {
     80     
     81      value=0;                //for the subsequent runs
    6982
    7083      bool phase=0;        //phase 0 is the 1st phase, phase 1 is the 2nd
     
    90103      typename Graph::NodeMap<T> excess(G);
    91104
    92       std::vector<Node> active(n,INVALID);
     105      std::vector<Node> active(n-1,INVALID);
    93106      typename Graph::NodeMap<Node> next(G,INVALID);
    94107      //Stack of the active nodes in level i < n.
     
    102115      */
    103116
    104       /*Reverse_bfs from t, to find the starting level.*/
    105       level.set(t,0);
    106       std::queue<Node> bfs_queue;
    107       bfs_queue.push(t);
    108 
    109       while (!bfs_queue.empty()) {
    110 
    111         Node v=bfs_queue.front();       
    112         bfs_queue.pop();
    113         int l=level[v]+1;
    114 
    115         InEdgeIt e;
    116         for(G.first(e,v); G.valid(e); G.next(e)) {
    117           Node w=G.tail(e);
    118           if ( level[w] == n && w != s ) {
    119             bfs_queue.push(w);
    120             Node first=level_list[l];
    121             if ( G.valid(first) ) left.set(first,w);
    122             right.set(w,first);
    123             level_list[l]=w;
    124             level.set(w, l);
    125           }
    126         }
    127       }
    128      
    129       level.set(s,n);
    130      
    131 
    132       /* Starting flow. It is everywhere 0 at the moment. */     
    133       OutEdgeIt e;
    134       for(G.first(e,s); G.valid(e); G.next(e))
     117
     118      if ( constzero ) {
     119     
     120        /*Reverse_bfs from t, to find the starting level.*/
     121        level.set(t,0);
     122        std::queue<Node> bfs_queue;
     123        bfs_queue.push(t);
     124       
     125        while (!bfs_queue.empty()) {
     126         
     127          Node v=bfs_queue.front();     
     128          bfs_queue.pop();
     129          int l=level[v]+1;
     130         
     131          InEdgeIt e;
     132          for(G.first(e,v); G.valid(e); G.next(e)) {
     133            Node w=G.tail(e);
     134            if ( level[w] == n && w != s ) {
     135              bfs_queue.push(w);
     136              Node first=level_list[l];
     137              if ( G.valid(first) ) left.set(first,w);
     138              right.set(w,first);
     139              level_list[l]=w;
     140              level.set(w, l);
     141            }
     142          }
     143        }
     144
     145        //the starting flow
     146        OutEdgeIt e;
     147        for(G.first(e,s); G.valid(e); G.next(e))
    135148        {
    136149          T c=capacity[e];
     
    146159          }
    147160        }
     161      }
     162      else
     163      {
     164       
     165        /*
     166          Reverse_bfs from t in the residual graph,
     167          to find the starting level.
     168        */
     169        level.set(t,0);
     170        std::queue<Node> bfs_queue;
     171        bfs_queue.push(t);
     172       
     173        while (!bfs_queue.empty()) {
     174         
     175          Node v=bfs_queue.front();     
     176          bfs_queue.pop();
     177          int l=level[v]+1;
     178         
     179          InEdgeIt e;
     180          for(G.first(e,v); G.valid(e); G.next(e)) {
     181            if ( capacity[e] == flow[e] ) continue;
     182            Node w=G.tail(e);
     183            if ( level[w] == n && w != s ) {
     184              bfs_queue.push(w);
     185              Node first=level_list[l];
     186              if ( G.valid(first) ) left.set(first,w);
     187              right.set(w,first);
     188              level_list[l]=w;
     189              level.set(w, l);
     190            }
     191          }
     192           
     193          OutEdgeIt f;
     194          for(G.first(f,v); G.valid(f); G.next(f)) {
     195            if ( 0 == flow[f] ) continue;
     196            Node w=G.head(f);
     197            if ( level[w] == n && w != s ) {
     198              bfs_queue.push(w);
     199              Node first=level_list[l];
     200              if ( G.valid(first) ) left.set(first,w);
     201              right.set(w,first);
     202              level_list[l]=w;
     203              level.set(w, l);
     204            }
     205          }
     206        }
     207     
     208       
     209        /*
     210          Counting the excess
     211        */
     212        NodeIt v;
     213        for(G.first(v); G.valid(v); G.next(v)) {
     214          T exc=0;
     215
     216          InEdgeIt e;
     217          for(G.first(e,v); G.valid(e); G.next(e)) exc+=flow[e];
     218          OutEdgeIt f;
     219          for(G.first(f,v); G.valid(f); G.next(f)) exc-=flow[e];
     220
     221          excess.set(v,exc);     
     222
     223          //putting the active nodes into the stack
     224          int lev=level[v];
     225          if ( exc > 0 && lev < n ) {
     226            next.set(v,active[lev]);
     227            active[lev]=v;
     228          }
     229        }
     230
     231
     232        //the starting flow
     233        OutEdgeIt e;
     234        for(G.first(e,s); G.valid(e); G.next(e))
     235        {
     236          T rem=capacity[e]-flow[e];
     237          if ( rem == 0 ) continue;
     238          Node w=G.head(e);
     239          if ( level[w] < n ) {   
     240            if ( excess[w] == 0 && w!=t ) {
     241              next.set(w,active[level[w]]);
     242              active[level[w]]=w;
     243            }
     244            flow.set(e, capacity[e]);
     245            excess.set(w, excess[w]+rem);
     246          }
     247        }
     248       
     249        InEdgeIt f;
     250        for(G.first(f,s); G.valid(f); G.next(f))
     251        {
     252          if ( flow[f] == 0 ) continue;
     253          Node w=G.head(f);
     254          if ( level[w] < n ) {   
     255            if ( excess[w] == 0 && w!=t ) {
     256              next.set(w,active[level[w]]);
     257              active[level[w]]=w;
     258            }
     259            excess.set(w, excess[w]+flow[f]);
     260            flow.set(f, 0);
     261          }
     262        }
     263      }
     264
     265
     266
    148267
    149268      /*
     
    339458            //unlacing ends
    340459               
    341             //gapping starts
    342460            if ( !G.valid(level_list[lev]) ) {
    343461             
     462               //gapping starts
    344463              for (int i=lev; i!=k ; ) {
    345464                Node v=level_list[++i];
     
    356475              k=b;
    357476              //gapping ends
     477           
    358478            } else {
    359479             
     
    364484                active[newlevel]=w;
    365485                if ( what_heur ) b=newlevel;
    366                 if ( k < newlevel ) ++k;
     486                if ( k < newlevel ) ++k;      //now k=newlevel
    367487                Node first=level_list[newlevel];
    368488                if ( G.valid(first) ) left.set(first,w);
     
    519639    }
    520640
     641   
     642    void reset_target (Node _t) {t=_t;}
     643    void reset_source (Node _s) {s=_s;}
     644   
     645    template<typename _CapMap>   
     646    void reset_cap (_CapMap _cap) {capacity=_cap;}
     647
     648    template<typename _FlowMap>   
     649    void reset_cap (_FlowMap _flow, bool _constzero) {
     650      flow=_flow;
     651      constzero=_constzero;
     652    }
     653
     654
    521655
    522656  };
  • src/work/jacint/preflowproba.h

    r370 r372  
    303303              int l=level[v]+1;
    304304             
    305               ResInEdgeIt e;
     305              /*              ResInEdgeIt e;
    306306              for(res_graph.first(e,s); res_graph.valid(e);
    307307                  res_graph.next(e)) {
     
    315315                  }
    316316                }
    317               }
    318               /*              InEdgeIt e;
     317                }*/
     318                    InEdgeIt e;
    319319              for(G.first(e,v); G.valid(e); G.next(e)) {
    320320                if ( capacity[e] == flow[e] ) continue;
     
    342342                  }
    343343                }
    344                 }*/
     344                }
    345345            }
    346346            b=n-2;
Note: See TracChangeset for help on using the changeset viewer.