COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 211:9222a9b8b323 in lemon-0.x for src/work/jacint


Ignore:
Timestamp:
03/19/04 23:16:05 (21 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@306
Message:

updating

Location:
src/work/jacint
Files:
8 edited

Legend:

Unmodified
Added
Removed

  • src/work/jacint/dijkstra.cc

    r173 r211  
    22#include <fstream>
    33
    4 #include <list_graph.hh>
    5 #include <dimacs.hh>
     4#include <smart_graph.h>
     5#include <list_graph.h>
     6#include <dimacs.h>
    67#include <dijkstra.h>
    78#include <time_measure.h>
    … …  
    1314
    1415int main(int, char **) {
    15   typedef ListGraph::NodeIt NodeIt;
    16   typedef ListGraph::EachNodeIt EachNodeIt;
    17   typedef ListGraph::InEdgeIt InEdgeIt;
     16  typedef SmartGraph::Node Node;
     17  typedef SmartGraph::NodeIt NodeIt;
     18  typedef SmartGraph::InEdgeIt InEdgeIt;
    1819
    19   ListGraph G;
    20   NodeIt s, t;
    21   ListGraph::EdgeMap<int> cap(G);
     20  SmartGraph G;
     21  Node s, t;
     22  SmartGraph::EdgeMap<int> cap(G);
    2223  readDimacsMaxFlow(std::cin, G, s, t, cap);
    2324
    … …  
    2526 
    2627  double pre_time=currTime();
    27     Dijkstra<ListGraph, int, FibHeap<ListGraph::NodeIt, int,
    28     ListGraph::NodeMap<int> > > dijkstra_test(G, s, cap);
    29     dijkstra_test.run();
     28    Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
     29    SmartGraph::NodeMap<int> > > dijkstra_test(G, cap);
     30    dijkstra_test.run(s);
    3031  double post_time=currTime();
    3132   
    … …  
    3435 
    3536  pre_time=currTime();
    36   Dijkstra<ListGraph, int, BinHeap<ListGraph::NodeIt, int,
    37     ListGraph::NodeMap<int> > > dijkstra_test2(G, s, cap);
    38   dijkstra_test2.run();
     37  Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int,
     38    SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap);
     39  dijkstra_test2.run(s);
    3940  post_time=currTime();
    4041 
    … …  
    4546  int hiba_fib=0;
    4647  int hiba_bin=0;
    47   EachNodeIt u;
    48   for ( G.getFirst(u) ; G.valid(u); G.next(u) ) {
     48  NodeIt u;
     49  for ( G.first(u) ; G.valid(u); G.next(u) ) {
    4950    InEdgeIt e;
    50     for ( G.getFirst(e,u); G.valid(e); G.next(e) ) {
    51       NodeIt v=G.tail(e);
     51    for ( G.first(e,u); G.valid(e); G.next(e) ) {
     52      Node v=G.tail(e);
    5253      if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) )
    5354        {
    … …  
    8889  std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
    8990            << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
    90 
     91 
    9192  std::cout << "Hibas elek szama a binarisos Dijkstraban: "
    9293            << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
    93 
     94 
    9495
    9596

  • src/work/jacint/dijkstra.h

    r171 r211  
    11// -*- C++ -*-
    2 
    3 //ha predecessor az elejen nem invalid, akkor hagyd csak ugy
    4 //scanned mutatja hogy jo ertek van-e benne vagy szemet
    5 
    62/*
    7  *template <Graph, T, Heap=FibHeap>
     3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
    84 *
    95 *Constructor:
    106 *
    11  *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
     7 *Dijkstra(Graph G, LengthMap length)
    128 *
    139 *
    14  *Member functions:
     10 *Methods:
    1511 *
    16  *void run()
     12 *void run(Node s)
    1713 *
    18  *  The following function should be used after run() was already run.
     14 *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
     15 *   Returns T() if v is not reachable from s.
    1916 *
    20  *T dist(NodeIt v) : returns the distance from s to v.
    21  *   It is 0 if v is not reachable from s.
     17 *Edge pred(Node v) : After run(s) was run, it returns the last
     18 *   edge of a shortest s-v path. It is INVALID for s and for
     19 *   the nodes not reachable from s.
    2220 *
    23  *EdgeIt pred(NodeIt v) : returns the last edge
    24  *   of a shortest s-v path. Returns an invalid iterator
    25  *   if v=s or v is not reachable from s.
    26  *
    27  *bool reach(NodeIt v) : true iff v is reachable from s
     21 *bool reached(Node v) : After run(s) was run, it is true iff v is
     22 *   reachable from s
    2823 *
    2924 */
    3025
    31 #ifndef DIJKSTRA_H
    32 #define DIJKSTRA_H
     26#ifndef HUGO_DIJKSTRA_H
     27#define HUGO_DIJKSTRA_H
    3328
    3429#include <fib_heap.h>
     30#include <invalid.h>
    3531
    3632namespace hugo {
    37 
     33 
    3834  template <typename Graph, typename T,
    39     typename Heap=FibHeap<typename Graph::NodeIt, T,
    40     typename Graph::NodeMap<int> > >
    41     class Dijkstra{
    42       typedef typename Graph::NodeIt NodeIt;
    43       typedef typename Graph::EdgeIt EdgeIt;
    44       typedef typename Graph::OutEdgeIt OutEdgeIt;
    45      
    46       Graph& G;
    47       NodeIt s;
    48       typename Graph::NodeMap<EdgeIt> predecessor;
    49       typename Graph::NodeMap<T> distance;
    50       typename Graph::EdgeMap<T>& length;
    51       typename Graph::NodeMap<bool> reached;
    52          
     35    typename Heap=FibHeap<typename Graph::Node, T,
     36    typename Graph::NodeMap<int> >,
     37    typename LengthMap=typename Graph::EdgeMap<T> >
     38  class Dijkstra{
     39    typedef typename Graph::Node Node;
     40    typedef typename Graph::NodeIt NodeIt;
     41    typedef typename Graph::Edge Edge;
     42    typedef typename Graph::OutEdgeIt OutEdgeIt;
     43   
     44    const Graph& G;
     45    const LengthMap& length;
     46    typename Graph::NodeMap<Edge> predecessor;
     47    typename Graph::NodeMap<T> distance;
     48    typename Graph::NodeMap<bool> reach;
     49   
    5350  public :
    54 
     51   
    5552    /*
    5653      The distance of the nodes is 0.
    5754    */
    58     Dijkstra(Graph& _G, NodeIt const _s,
    59              typename Graph::EdgeMap<T>& _length) :
    60       G(_G), s(_s), predecessor(G), distance(G),
    61       length(_length), reached(G, false) { }
     55    Dijkstra(Graph& _G, LengthMap& _length) : G(_G),
     56      length(_length), predecessor(_G), distance(_G), reach(_G) { }
    6257   
     58
     59    void run(Node s) {
    6360     
    64       void run() {
     61      NodeIt u;
     62      for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
     63        predecessor.set(u,INVALID);
     64        distance.set(u,0);
     65        reach.set(u,false);
     66      }
     67     
     68      typename Graph::NodeMap<bool> scanned(G,false);
     69      typename Graph::NodeMap<int> heap_map(G,-1);
     70     
     71      Heap heap(heap_map);
     72
     73      heap.push(s,0);
     74      reach.set(s, true);
     75
     76      while ( !heap.empty() ) {
    6577       
    66         typename Graph::NodeMap<bool> scanned(G, false);
    67         typename Graph::NodeMap<int> heap_map(G,-1);
     78        Node v=heap.top();
     79        T oldvalue=heap.get(v);
     80        heap.pop();
     81        distance.set(v, oldvalue);
     82        scanned.set(v,true);
    6883
    69         Heap heap(heap_map);
    70 
    71         heap.push(s,0);
    72         reached.set(s, true);
    73 
    74         while ( !heap.empty() ) {
    75 
    76           NodeIt v=heap.top();
    77           T oldvalue=heap.get(v);
    78           heap.pop();
    79           distance.set(v, oldvalue);
    80           scanned.set(v,true);
    81 
    82           OutEdgeIt e;
    83           for( G.getFirst(e,v); G.valid(e); G.next(e)) {
    84             NodeIt w=G.bNode(e);
     84        OutEdgeIt e;
     85        for( G.first(e,v); G.valid(e); G.next(e)) {
     86          Node w=G.head(e);
    8587           
    86             if ( !scanned.get(w) ) {
    87               if ( !reached.get(w) ) {
    88                 reached.set(w,true);
    89                 heap.push(w,oldvalue+length.get(e));
    90                 predecessor.set(w,e);
    91               } else if ( oldvalue+length.get(e) < heap.get(w) ) {
    92                 predecessor.set(w,e);
    93                 heap.decrease(w, oldvalue+length.get(e));
    94               }
     88          if ( !scanned[w] ) {
     89            if ( !reach[w] ) {
     90              reach.set(w,true);
     91              heap.push(w,oldvalue+length[e]);
     92              predecessor.set(w,e);
     93            } else if ( oldvalue+length[e] < heap.get(w) ) {
     94              predecessor.set(w,e);
     95              heap.decrease(w, oldvalue+length[e]);
    9596            }
    9697          }
    9798        }
    98       }
    99      
     99      }
     100    }
     101   
    100102
    101       T dist(NodeIt v) {
    102         return distance.get(v);
    103       }
     103    T dist(Node v) {
     104      return distance[v];
     105    }
    104106
    105107
    106       EdgeIt pred(NodeIt v) {
    107         if ( v!=s ) return predecessor.get(v);
    108         else return EdgeIt();
    109       }
     108    Edge pred(Node v) {
     109      return predecessor[v];
     110    }
    110111     
    111112
    112       bool reach(NodeIt v) {
    113         return reached.get(v);
    114       }
    115      
    116     };
     113    bool reached(Node v) {
     114      return reach[v];
     115    }
     116   
     117  };
    117118 
    118119}

  • src/work/jacint/fib_heap.h

    r173 r211  
    144144   
    145145
     146
     147
     148    PrioType& operator[](const Item& it) const {
     149      return container[iimap.get(it)].prio;
     150    }
     151   
     152    const PrioType& operator[](const Item& it) const {
     153      return container[iimap.get(it)].prio;
     154    }
     155
    146156    const PrioType get(const Item& it) const {
    147157      return container[iimap.get(it)].prio;
    148158    }
     159
    149160
    150161

  • src/work/jacint/makefile

    r200 r211  
    22CXX2 = g++-2.95
    33CXXFLAGS = -W -Wall -ansi -pedantic
    4 LEDAROOT = /ledasrc/LEDA-4.1
     4LEDAROOT ?= /ledasrc/LEDA-4.1
    55
    6 BINARIES = preflow dijkstra prim
     6BINARIES = dijkstra prim preflow
    77
    88all: $(BINARIES)
    … …  
    1212
    1313preflow:
    14         $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o preflow preflow.cc
     14        $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o preflow preflow.cc
    1515
    1616dijkstra:
    17         $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o dijkstra dijkstra.cc
     17        $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar  -o dijkstra dijkstra.cc
    1818
    1919prim:
    20         $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o prim prim.cc
     20        $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o prim prim.cc
    2121
    2222clean:

  • src/work/jacint/preflow.cc

    r113 r211  
    22#include <fstream>
    33
    4 #include <list_graph.hh>
    5 #include <dimacs.hh>
     4#include <list_graph.h>
     5#include <dimacs.h>
    66#include <preflow.h>
    77#include <time_measure.h>
    … …  
    1212// read_dimacs_demo < dimacs_max_flow_file
    1313int main(int, char **) {
    14   typedef ListGraph::NodeIt NodeIt;
    15   typedef ListGraph::EachEdgeIt EachEdgeIt;
     14  typedef ListGraph::Node Node;
     15  typedef ListGraph::EdgeIt EdgeIt;
    1616
    1717  ListGraph G;
    18   NodeIt s, t;
     18  Node s, t;
    1919  ListGraph::EdgeMap<int> cap(G);
    2020  readDimacsMaxFlow(std::cin, G, s, t, cap);
    … …  
    2525
    2626  for ( int i=1; i!=11; ++i ) {
     27    ListGraph::EdgeMap<int> flow(G);
    2728    double pre_time=currTime();
    28     preflow<ListGraph, int> max_flow_test(G, s, t, cap);
     29    Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
     30    max_flow_test.run();
    2931    double post_time=currTime();
    3032    if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
    3133  }
    3234
    33   double pre_time=currTime();
    34     preflow<ListGraph, int> max_flow_test(G, s, t, cap);
    35   double post_time=currTime();
    36    
     35  ListGraph::EdgeMap<int> flow(G);
     36  Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
     37  max_flow_test.run();
     38 
    3739  ListGraph::NodeMap<bool> cut(G);
    3840  max_flow_test.minCut(cut);
    3941  int min_cut_value=0;
    40   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     42  EdgeIt e;
     43  for(G.first(e); G.valid(e); G.next(e)) {
    4144    if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
    4245  }
    … …  
    4548  max_flow_test.minMinCut(cut1);
    4649  int min_min_cut_value=0;
    47   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     50  for(G.first(e); G.valid(e); G.next(e)) {
    4851    if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
    4952      min_min_cut_value+=cap.get(e);
    … …  
    5356  max_flow_test.maxMinCut(cut2);
    5457  int max_min_cut_value=0;
    55   for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
     58  for(G.first(e); G.valid(e); G.next(e)) {
    5659    if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
    5760      max_min_cut_value+=cap.get(e);
    … …  
    5962 
    6063  std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
    61   std::cout << "phase 0: " << max_flow_test.time-pre_time
    62             << " sec"<< std::endl;
    63   std::cout << "phase 1: " << post_time-max_flow_test.time
    64             << " sec"<< std::endl;
    65   std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
     64  std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
    6665  std::cout << "min cut value: "<< min_cut_value << std::endl;
    6766  std::cout << "min min cut value: "<< min_min_cut_value << std::endl;

  • src/work/jacint/preflow.h

    r174 r211  
    11// -*- C++ -*-
    22/*
    3 preflow.h
    4 by jacint.
    53Heuristics:
    64 2 phase
    … …  
    1311Parameters H0 and H1 are initialized to 20 and 10.
    1412
    15 The best preflow I could ever write.
    16 
    17 The constructor runs the algorithm.
     13Constructors:
     14
     15Preflow(Graph, Node, Node, CapMap, FlowMap)
    1816
    1917Members:
    2018
    21 T maxFlow() : returns the value of a maximum flow
    22 
    23 T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
    24 
    25 FlowMap Flow() : returns the fixed maximum flow x
     19void run()
     20
     21T flowValue() : returns the value of a maximum flow
    2622
    2723void minMinCut(CutMap& M) : sets M to the characteristic vector of the
    … …  
    3632*/
    3733
    38 #ifndef PREFLOW_H
    39 #define PREFLOW_H
     34#ifndef HUGO_PREFLOW_H
     35#define HUGO_PREFLOW_H
    4036
    4137#define H0 20
    … …  
    4440#include <vector>
    4541#include <queue>
    46 
    47 #include <time_measure.h>
    4842
    4943namespace hugo {
    … …  
    5246    typename FlowMap=typename Graph::EdgeMap<T>,
    5347    typename CapMap=typename Graph::EdgeMap<T> >
    54   class preflow {
     48  class Preflow {
    5549   
     50    typedef typename Graph::Node Node;
     51    typedef typename Graph::Edge Edge;
    5652    typedef typename Graph::NodeIt NodeIt;
    57     typedef typename Graph::EdgeIt EdgeIt;
    58     typedef typename Graph::EachNodeIt EachNodeIt;
    5953    typedef typename Graph::OutEdgeIt OutEdgeIt;
    6054    typedef typename Graph::InEdgeIt InEdgeIt;
    6155   
    62     Graph& G;
    63     NodeIt s;
    64     NodeIt t;
    65     FlowMap flow;
    66     CapMap& capacity; 
     56    const Graph& G;
     57    Node s;
     58    Node t;
     59    FlowMap& flow;
     60    const CapMap& capacity; 
    6761    T value;
    6862
    6963  public:
    70     double time;
    71     preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
    72       G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity)
    73     {
     64    Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, FlowMap& _flow ) :
     65      G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) {}
     66
     67
     68    void run() {
    7469
    7570      bool phase=0;        //phase 0 is the 1st phase, phase 1 is the 2nd
    … …  
    9590      typename Graph::NodeMap<T> excess(G);
    9691
    97       std::vector<NodeIt> active(n);
    98       typename Graph::NodeMap<NodeIt> next(G);
     92      std::vector<Node> active(n,INVALID);
     93      typename Graph::NodeMap<Node> next(G,INVALID);
    9994      //Stack of the active nodes in level i < n.
    10095      //We use it in both phases.
    10196
    102       typename Graph::NodeMap<NodeIt> left(G);
    103       typename Graph::NodeMap<NodeIt> right(G);
    104       std::vector<NodeIt> level_list(n);
     97      typename Graph::NodeMap<Node> left(G,INVALID);
     98      typename Graph::NodeMap<Node> right(G,INVALID);
     99      std::vector<Node> level_list(n,INVALID);
    105100      /*
    106101        List of the nodes in level i<n.
    … …  
    109104      /*Reverse_bfs from t, to find the starting level.*/
    110105      level.set(t,0);
    111       std::queue<NodeIt> bfs_queue;
     106      std::queue<Node> bfs_queue;
    112107      bfs_queue.push(t);
    113108
    114109      while (!bfs_queue.empty()) {
    115110
    116         NodeIt v=bfs_queue.front();     
     111        Node v=bfs_queue.front();       
    117112        bfs_queue.pop();
    118         int l=level.get(v)+1;
    119 
    120         for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
    121           NodeIt w=G.tail(e);
    122           if ( level.get(w) == n && w != s ) {
     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 ) {
    123119            bfs_queue.push(w);
    124             NodeIt first=level_list[l];
    125             if ( first != 0 ) left.set(first,w);
     120            Node first=level_list[l];
     121            if ( G.valid(first) ) left.set(first,w);
    126122            right.set(w,first);
    127123            level_list[l]=w;
    … …  
    135131
    136132      /* Starting flow. It is everywhere 0 at the moment. */     
    137       for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
     133      OutEdgeIt e;
     134      for(G.first(e,s); G.valid(e); G.next(e))
    138135        {
    139           T c=capacity.get(e);
     136          T c=capacity[e];
    140137          if ( c == 0 ) continue;
    141           NodeIt w=G.head(e);
    142           if ( level.get(w) < n ) {       
    143             if ( excess.get(w) == 0 && w!=t ) {
    144               next.set(w,active[level.get(w)]);
    145               active[level.get(w)]=w;
     138          Node w=G.head(e);
     139          if ( level[w] < n ) {   
     140            if ( excess[w] == 0 && w!=t ) {
     141              next.set(w,active[level[w]]);
     142              active[level[w]]=w;
    146143            }
    147144            flow.set(e, c);
    148             excess.set(w, excess.get(w)+c);
     145            excess.set(w, excess[w]+c);
    149146          }
    150147        }
    … …  
    169166          } else {
    170167            phase=1;
    171             time=currTime();
    172168            level.set(s,0);
    173             std::queue<NodeIt> bfs_queue;
     169            std::queue<Node> bfs_queue;
    174170            bfs_queue.push(s);
    175171           
    176172            while (!bfs_queue.empty()) {
    177173             
    178               NodeIt v=bfs_queue.front();       
     174              Node v=bfs_queue.front();
    179175              bfs_queue.pop();
    180               int l=level.get(v)+1;
    181              
    182               for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
    183                 if ( capacity.get(e) == flow.get(e) ) continue;
    184                 NodeIt u=G.tail(e);
    185                 if ( level.get(u) >= n ) {
     176              int l=level[v]+1;
     177             
     178              InEdgeIt e;
     179              for(G.first(e,v); G.valid(e); G.next(e)) {
     180                if ( capacity[e] == flow[e] ) continue;
     181                Node u=G.tail(e);
     182                if ( level[u] >= n ) {
    186183                  bfs_queue.push(u);
    187184                  level.set(u, l);
    188                   if ( excess.get(u) > 0 ) {
     185                  if ( excess[u] > 0 ) {
    189186                    next.set(u,active[l]);
    190187                    active[l]=u;
    … …  
    193190              }
    194191           
    195               for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
    196                 if ( 0 == flow.get(e) ) continue;
    197                 NodeIt u=G.head(e);
    198                 if ( level.get(u) >= n ) {
     192              OutEdgeIt f;
     193              for(G.first(f,v); G.valid(f); G.next(f)) {
     194                if ( 0 == flow[f] ) continue;
     195                Node u=G.head(f);
     196                if ( level[u] >= n ) {
    199197                  bfs_queue.push(u);
    200198                  level.set(u, l);
    201                   if ( excess.get(u) > 0 ) {
     199                  if ( excess[u] > 0 ) {
    202200                    next.set(u,active[l]);
    203201                    active[l]=u;
    … …  
    212210         
    213211         
    214         if ( active[b] == 0 ) --b;
     212        if ( !G.valid(active[b]) ) --b;
    215213        else {
    216214          end=false; 
    217215
    218           NodeIt w=active[b];
    219           active[b]=next.get(w);
    220           int lev=level.get(w);
    221           T exc=excess.get(w);
     216          Node w=active[b];
     217          active[b]=next[w];
     218          int lev=level[w];
     219          T exc=excess[w];
    222220          int newlevel=n;       //bound on the next level of w
    223221         
    224           for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
    225            
    226             if ( flow.get(e) == capacity.get(e) ) continue;
    227             NodeIt v=G.head(e);           
     222          OutEdgeIt e;
     223          for(G.first(e,w); G.valid(e); G.next(e)) {
     224           
     225            if ( flow[e] == capacity[e] ) continue;
     226            Node v=G.head(e);           
    228227            //e=wv         
    229228           
    230             if( lev > level.get(v) ) {     
     229            if( lev > level[v] ) {     
    231230              /*Push is allowed now*/
    232231             
    233               if ( excess.get(v)==0 && v!=t && v!=s ) {
    234                 int lev_v=level.get(v);
     232              if ( excess[v]==0 && v!=t && v!=s ) {
     233                int lev_v=level[v];
    235234                next.set(v,active[lev_v]);
    236235                active[lev_v]=v;
    237236              }
    238237             
    239               T cap=capacity.get(e);
    240               T flo=flow.get(e);
     238              T cap=capacity[e];
     239              T flo=flow[e];
    241240              T remcap=cap-flo;
    242241             
    … …  
    245244               
    246245                flow.set(e, flo+exc);
    247                 excess.set(v, excess.get(v)+exc);
     246                excess.set(v, excess[v]+exc);
    248247                exc=0;
    249248                break;
    … …  
    253252               
    254253                flow.set(e, cap);
    255                 excess.set(v, excess.get(v)+remcap);
     254                excess.set(v, excess[v]+remcap);
    256255                exc-=remcap;
    257256              }
    258             } else if ( newlevel > level.get(v) ){
    259               newlevel = level.get(v);
     257            } else if ( newlevel > level[v] ){
     258              newlevel = level[v];
    260259            }       
    261260           
    … …  
    264263       
    265264        if ( exc > 0 ) {       
    266           for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
    267            
    268             if( flow.get(e) == 0 ) continue;
    269             NodeIt v=G.tail(e); 
     265          InEdgeIt e;
     266          for(G.first(e,w); G.valid(e); G.next(e)) {
     267           
     268            if( flow[e] == 0 ) continue;
     269            Node v=G.tail(e); 
    270270            //e=vw
    271271           
    272             if( lev > level.get(v) ) { 
     272            if( lev > level[v] ) { 
    273273              /*Push is allowed now*/
    274274             
    275               if ( excess.get(v)==0 && v!=t && v!=s ) {
    276                 int lev_v=level.get(v);
     275              if ( excess[v]==0 && v!=t && v!=s ) {
     276                int lev_v=level[v];
    277277                next.set(v,active[lev_v]);
    278278                active[lev_v]=v;
    279279              }
    280280             
    281               T flo=flow.get(e);
     281              T flo=flow[e];
    282282             
    283283              if ( flo >= exc ) {
    … …  
    285285               
    286286                flow.set(e, flo-exc);
    287                 excess.set(v, excess.get(v)+exc);
     287                excess.set(v, excess[v]+exc);
    288288                exc=0;
    289289                break;
    … …  
    291291                /*A saturating push.*/
    292292               
    293                 excess.set(v, excess.get(v)+flo);
     293                excess.set(v, excess[v]+flo);
    294294                exc-=flo;
    295295                flow.set(e,0);
    296296              } 
    297             } else if ( newlevel > level.get(v) ) {
    298               newlevel = level.get(v);
     297            } else if ( newlevel > level[v] ) {
     298              newlevel = level[v];
    299299            }       
    300300          } //for in edges vw
    … …  
    319319          } else {
    320320            //unlacing starts
    321             NodeIt right_n=right.get(w);
    322             NodeIt left_n=left.get(w);
    323 
    324             if ( right_n != 0 ) {
    325               if ( left_n != 0 ) {
     321            Node right_n=right[w];
     322            Node left_n=left[w];
     323
     324            if ( G.valid(right_n) ) {
     325              if ( G.valid(left_n) ) {
    326326                right.set(left_n, right_n);
    327327                left.set(right_n, left_n);
    328328              } else {
    329329                level_list[lev]=right_n;   
    330                 left.set(right_n, 0);
     330                left.set(right_n, INVALID);
    331331              }
    332332            } else {
    333               if ( left_n != 0 ) {
    334                 right.set(left_n, 0);
     333              if ( G.valid(left_n) ) {
     334                right.set(left_n, INVALID);
    335335              } else {
    336                 level_list[lev]=0;   
    337 
     336                level_list[lev]=INVALID;   
    338337              }
    339338            }
    … …  
    341340               
    342341            //gapping starts
    343             if ( level_list[lev]==0 ) {
     342            if ( !G.valid(level_list[lev]) ) {
    344343             
    345344              for (int i=lev; i!=k ; ) {
    346                 NodeIt v=level_list[++i];
    347                 while ( v != 0 ) {
     345                Node v=level_list[++i];
     346                while ( G.valid(v) ) {
    348347                  level.set(v,n);
    349                   v=right.get(v);
     348                  v=right[v];
    350349                }
    351                 level_list[i]=0;
    352                 if ( !what_heur ) active[i]=0;
     350                level_list[i]=INVALID;
     351                if ( !what_heur ) active[i]=INVALID;
    353352              }     
    354353
    … …  
    366365                if ( what_heur ) b=newlevel;
    367366                if ( k < newlevel ) ++k;
    368                 NodeIt first=level_list[newlevel];
    369                 if ( first != 0 ) left.set(first,w);
     367                Node first=level_list[newlevel];
     368                if ( G.valid(first) ) left.set(first,w);
    370369                right.set(w,first);
    371                 left.set(w,0);
     370                left.set(w,INVALID);
    372371                level_list[newlevel]=w;
    373372              }
    … …  
    399398
    400399
    401       value = excess.get(t);
     400      value = excess[t];
    402401      /*Max flow value.*/
    403402     
    … …  
    412411     */
    413412
    414     T maxFlow() {
     413    T flowValue() {
    415414      return value;
    416415    }
    417 
    418 
    419 
    420     /*
    421       For the maximum flow x found by the algorithm,
    422       it returns the flow value on edge e, i.e. x(e).
    423     */
    424    
    425     T flowOnEdge(EdgeIt e) {
    426       return flow.get(e);
    427     }
    428 
    429416
    430417
    … …  
    436423   
    437424    void Flow(FlowMap& _flow ) {
    438       for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
    439         _flow.set(v,flow.get(v));
    440         }
     425      NodeIt v;
     426      for(G.first(v) ; G.valid(v); G.next(v))
     427        _flow.set(v,flow[v]);
     428    }
    441429
    442430
    … …  
    449437    void minMinCut(_CutMap& M) {
    450438   
    451       std::queue<NodeIt> queue;
     439      std::queue<Node> queue;
    452440     
    453441      M.set(s,true);     
    … …  
    455443
    456444      while (!queue.empty()) {
    457         NodeIt w=queue.front();
     445        Node w=queue.front();
    458446        queue.pop();
    459447
    460         for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
    461           NodeIt v=G.head(e);
    462           if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
     448        OutEdgeIt e;
     449        for(G.first(e,w) ; G.valid(e); G.next(e)) {
     450          Node v=G.head(e);
     451          if (!M[v] && flow[e] < capacity[e] ) {
    463452            queue.push(v);
    464453            M.set(v, true);
    … …  
    466455        }
    467456
    468         for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
    469           NodeIt v=G.tail(e);
    470           if (!M.get(v) && flow.get(e) > 0 ) {
     457        InEdgeIt f;
     458        for(G.first(f,w) ; G.valid(f); G.next(f)) {
     459          Node v=G.tail(f);
     460          if (!M[v] && flow[f] > 0 ) {
    471461            queue.push(v);
    472462            M.set(v, true);
    … …  
    486476    void maxMinCut(_CutMap& M) {
    487477   
    488       std::queue<NodeIt> queue;
     478      std::queue<Node> queue;
    489479     
    490480      M.set(t,true);       
    … …  
    492482
    493483      while (!queue.empty()) {
    494         NodeIt w=queue.front();
     484        Node w=queue.front();
    495485        queue.pop();
    496486
    497         for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
    498           NodeIt v=G.tail(e);
    499           if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
     487
     488        InEdgeIt e;
     489        for(G.first(e,w) ; G.valid(e); G.next(e)) {
     490          Node v=G.tail(e);
     491          if (!M[v] && flow[e] < capacity[e] ) {
    500492            queue.push(v);
    501493            M.set(v, true);
    502494          }
    503495        }
    504 
    505         for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
    506           NodeIt v=G.head(e);
    507           if (!M.get(v) && flow.get(e) > 0 ) {
     496       
     497        OutEdgeIt f;
     498        for(G.first(f,w) ; G.valid(f); G.next(f)) {
     499          Node v=G.head(f);
     500          if (!M[v] && flow[f] > 0 ) {
    508501            queue.push(v);
    509502            M.set(v, true);
    … …  
    512505      }
    513506
    514       for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
    515         M.set(v, !M.get(v));
     507      NodeIt v;
     508      for(G.first(v) ; G.valid(v); G.next(v)) {
     509        M.set(v, !M[v]);
    516510      }
    517511

  • src/work/jacint/prim.cc

    r173 r211  
    22#include <fstream>
    33
    4 #include <list_graph.hh>
    5 #include <dimacs.hh>
     4#include <list_graph.h>
     5#include <dimacs.h>
    66#include <prim.h>
    77#include <time_measure.h>
    … …  
    1313
    1414int main(int, char **) {
    15   typedef ListGraph::NodeIt NodeIt;
     15  typedef ListGraph::Node Node;
    1616
    1717  ListGraph G;
    18   NodeIt s, t;
     18  Node s, t;
    1919  ListGraph::EdgeMap<int> cap(G);
    2020  readDimacsMaxFlow(std::cin, G, s, t, cap);
    … …  
    2323 
    2424  double pre_time=currTime();
    25     Prim<ListGraph, int, FibHeap<ListGraph::NodeIt, int,
     25    Prim<ListGraph, int, FibHeap<ListGraph::Node, int,
    2626    ListGraph::NodeMap<int> > > prim_test(G, cap);
    2727    prim_test.run();
    … …  
    3232 
    3333  pre_time=currTime();
    34   Prim<ListGraph, int, BinHeap<ListGraph::NodeIt, int,
     34  Prim<ListGraph, int, BinHeap<ListGraph::Node, int,
    3535    ListGraph::NodeMap<int> > > prim_test2(G, cap);
    3636  prim_test2.run();

  • src/work/jacint/prim.h

    r173 r211  
    11// -*- C++ -*-
    2 
    3 //kell hogy tree_edge invalid elekbol alljon, Szep
    4 //lenne ha az elejen a konstrualas ilyet adna, de
    5 //ugy fest nem igy lesz, ekkor invalidalni kell
    6 
    72/*
    8  *template <Graph, T, Heap=FibHeap>
     3 *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
    94 *
    105 *Constructor:
    116 *
    12  *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
     7 *Prim(Graph G, LengthMap weight)
    138 *
    149 *
    1510 *Methods:
    1611 *
    17  *void run()
     12 *void run() : Runs the Prim-algorithm from a random node
    1813 *
    19  *  The followings functions should be used after run() was already run.
     14 *void run(Node r) : Runs the Prim-algorithm from node s
    2015 *
    21  *T weight() : returns the minimum weight of a spanning tree of the
    22  *   component of the root.
     16 *T weight() : After run(r) was run, it returns the minimum
     17 *   weight of a spanning tree of the component of the root.
    2318 *
    24  *EdgeIt tree(NodeIt v) : returns the first edge in the path from v
    25  *   to the root. Returns an invalid iterator if v=s or v is
    26  *   not reachable from the root.
     19 *Edge tree(Node v) : After run(r) was run, it returns the
     20 *   first edge in the path from v to the root. Returns
     21 *   INVALID if v=r or v is not reachable from the root.
    2722 *
    28  *bool conn() : true iff G is connected
     23 *bool conn() : After run(r) was run, it is true iff G is connected
    2924 *
    30  *bool reach(NodeIt v) : true iff v is in the same component as the root
     25 *bool reached(Node v) : After run(r) was run, it is true
     26 *   iff v is in the same component as the root
    3127 *
    32  *NodeIt root() : returns the root
     28 *Node root() : returns the root
    3329 *
    3430 */
    3531
    36 #ifndef PRIM_H
    37 #define PRIM_H
     32#ifndef HUGO_PRIM_H
     33#define HUGO_PRIM_H
    3834
    3935#include <fib_heap.h>
    40 
    41 #include <iostream>
     36#include <invalid.h>
    4237
    4338namespace hugo {
    4439
    4540  template <typename Graph, typename T,
    46     typename Heap=FibHeap<typename Graph::NodeIt, T,
    47     typename Graph::NodeMap<int> > >
     41    typename Heap=FibHeap<typename Graph::Node, T,
     42    typename Graph::NodeMap<int> >,
     43    typename LengthMap=typename Graph::EdgeMap<T> >
    4844    class Prim{
     45      typedef typename Graph::Node Node;
    4946      typedef typename Graph::NodeIt NodeIt;
    50       typedef typename Graph::EachNodeIt EachNodeIt;
    51       typedef typename Graph::EdgeIt EdgeIt;
     47      typedef typename Graph::Edge Edge;
    5248      typedef typename Graph::OutEdgeIt OutEdgeIt;
    5349      typedef typename Graph::InEdgeIt InEdgeIt; 
    5450
    55       Graph& G;
    56       NodeIt r;
    57       typename Graph::NodeMap<EdgeIt> tree_edge;
     51      const Graph& G;
     52      const LengthMap& edge_weight;
     53      typename Graph::NodeMap<Edge> tree_edge;
    5854      typename Graph::NodeMap<T> min_weight;
    59       typename Graph::EdgeMap<T>& edge_weight;
    60       typename Graph::NodeMap<bool> reached;
     55      typename Graph::NodeMap<bool> reach;
    6156         
    6257  public :
    6358
    64       Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight,
    65            NodeIt const _r) :
    66       G(_G), r(_r), tree_edge(G), min_weight(G),
    67       edge_weight(_edge_weight), reached(G, false) { }
     59      Prim(Graph& _G, LengthMap& _edge_weight) :
     60        G(_G), edge_weight(_edge_weight),
     61        tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { }
    6862
    69       Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) :
    70       G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)
    71       {
    72         EachNodeIt _r;     //FIXME
    73         G.getFirst(_r);
    74         r=_r;
     63
     64      void run() {
     65        NodeIt _r;     
     66        G.first(_r);
     67        run(_r);
    7568      }
    7669
    7770
    78       void run() {
     71      void run(Node r) {
     72
     73        NodeIt u;
     74        for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
     75          tree_edge.set(u,INVALID);
     76          min_weight.set(u,0);
     77          reach.set(u,false);
     78        }
     79
    7980
    8081        typename Graph::NodeMap<bool> scanned(G, false);
    … …  
    8485
    8586        heap.push(r,0);
    86         reached.set(r, true);
     87        reach.set(r, true);
    8788
    8889        while ( !heap.empty() ) {
    8990
    90           NodeIt v=heap.top();
     91          Node v=heap.top();
    9192          min_weight.set(v, heap.get(v));
    9293          heap.pop();
    … …  
    9495
    9596          OutEdgeIt e;
    96           for( G.getFirst(e,v); G.valid(e); G.next(e)) {
    97             NodeIt w=G.head(e);
     97          for( G.first(e,v); G.valid(e); G.next(e)) {
     98            Node w=G.head(e);
    9899           
    99             if ( !scanned.get(w) ) {
    100               if ( !reached.get(w) ) {
    101                 reached.set(w,true);
    102                 heap.push(w, edge_weight.get(e));
     100            if ( !scanned[w] ) {
     101              if ( !reach[w] ) {
     102                reach.set(w,true);
     103                heap.push(w, edge_weight[e]);
    103104                tree_edge.set(w,e);
    104               } else if ( edge_weight.get(e) < heap.get(w) ) {
     105              } else if ( edge_weight[e] < heap.get(w) ) {
    105106                tree_edge.set(w,e);
    106                 heap.decrease(w, edge_weight.get(e));
     107                heap.decrease(w, edge_weight[e]);
    107108              }
    108109            }
    … …  
    110111
    111112          InEdgeIt f;
    112           for( G.getFirst(f,v); G.valid(f); G.next(f)) {
    113             NodeIt w=G.tail(f);
     113          for( G.first(f,v); G.valid(f); G.next(f)) {
     114            Node w=G.tail(f);
    114115           
    115             if ( !scanned.get(w) ) {
    116               if ( !reached.get(w) ) {
    117                 reached.set(w,true);
    118                 heap.push(w, edge_weight.get(f));
     116            if ( !scanned[w] ) {
     117              if ( !reach[w] ) {
     118                reach.set(w,true);
     119                heap.push(w, edge_weight[f]);
    119120                tree_edge.set(w,f);
    120               } else if ( edge_weight.get(f) < heap.get(w) ) {
     121              } else if ( edge_weight[f] < heap.get(w) ) {
    121122                tree_edge.set(w,f);
    122                 heap.decrease(w, edge_weight.get(f));
     123                heap.decrease(w, edge_weight[f]);
    123124              }
    124125            }
    … …  
    130131      T weight() {
    131132        T w=0;
    132         EachNodeIt u;
    133         for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
     133        NodeIt u;
     134        for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
    134135        return w;
    135136      }
    136137     
    137138
    138       EdgeIt tree(NodeIt v) {
    139         return tree_edge.get(v);
     139      Edge tree(Node v) {
     140        return tree_edge[v];
    140141      }
    141142
    … …  
    143144      bool conn() {
    144145        bool c=true;
    145         EachNodeIt u;
    146         for ( G.getFirst(u) ; G.valid(u) ; G.next(u) )
    147           if ( !reached.get(u) ) {
     146        NodeIt u;
     147        for ( G.first(u) ; G.valid(u) ; G.next(u) )
     148          if ( !reached[u] ) {
    148149            c=false;
    149150            break;
    … …  
    153154
    154155
    155       bool reach(NodeIt v) {
    156         return reached.get(v);
     156      bool reached(Node v) {
     157        return reached[v];
    157158      }
    158159
    159160
    160       NodeIt root() {
     161      Node root() {
    161162        return r;
    162163      }
Note: See TracChangeset for help on using the changeset viewer.