COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 217:fc549fac0dd0 in lemon-0.x for src/work


Ignore:
Timestamp:
03/20/04 17:13:19 (21 years ago)
Author:
Alpar Juttner
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@312
Message:

Several bugfixes

Location:
src/work/jacint
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • src/work/jacint/bin_heap.hh

    r170 r217  
    154154
    155155    void erase(const Key &k) {
    156       rmidx(kim.get(k));
    157     }
    158 
    159     const Val get(const Key &k) const {
    160       int idx = kim.get(k);
     156      rmidx(kim[k]);
     157    }
     158
     159    Val operator[](const Key &k) const {
     160      int idx = kim[k];
    161161      return data[idx].second;
    162162    }
     163   
    163164    void put(const Key &k, const Val &v) {
    164       int idx = kim.get(k);
     165      int idx = kim[k];
    165166      if( idx < 0 ) {
    166167        push(k,v);
    … …  
    175176
    176177    void decrease(const Key &k, const Val &v) {
    177       int idx = kim.get(k);
     178      int idx = kim[k];
    178179      bubble_up(idx, PairType(k,v));
    179180    }
    180181    void increase(const Key &k, const Val &v) {
    181       int idx = kim.get(k);
     182      int idx = kim[k];
    182183      bubble_down(idx, PairType(k,v), data.size());
    183184    }
    184185
    185186    state_enum state(const Key &k) const {
    186       int s = kim.get(k);
     187      int s = kim[k];
    187188      if( s>=0 )
    188189        s=0;

  • src/work/jacint/dijkstra.cc

    r211 r217  
    2626 
    2727  double pre_time=currTime();
    28     Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
     28  Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
    2929    SmartGraph::NodeMap<int> > > dijkstra_test(G, cap);
    30     dijkstra_test.run(s);
     30  dijkstra_test.run(s);
    3131  double post_time=currTime();
    3232   
    33   std::cout << "running time with fib_heap: "
     33    std::cout << "running time with fib_heap: "
    3434            << post_time-pre_time << " sec"<< std::endl;
    3535 
    … …  
    5151    for ( G.first(e,u); G.valid(e); G.next(e) ) {
    5252      Node v=G.tail(e);
    53       if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) )
     53      if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap[e] )
    5454        {
    5555          std::cout<<"Hibas el a fibonaccis Dijkstraban: "
    5656                   << dijkstra_test.dist(u) - dijkstra_test.dist(v) -
    57             cap.get(e)<<std::endl;
     57            cap[e]<<std::endl;
    5858          ++hiba_fib;
    5959        }
    60       if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap.get(e) )
     60      if ( dijkstra_test2.dist(u) - dijkstra_test2.dist(v) > cap[e] )
    6161        {
    6262          std::cout<<"Hibas el a binarisos Dijkstraban: "
    6363                   << dijkstra_test2.dist(u) - dijkstra_test2.dist(v) -
    64             cap.get(e)<<std::endl;
     64            cap[e]<<std::endl;
    6565          ++hiba_bin;
    6666        }
    6767      if ( e==dijkstra_test.pred(u) &&
    68            dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) )
     68           dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap[e] )
    6969        {
    7070          std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
    71             dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<std::endl;
     71            dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap[e]<<std::endl;
    7272          ++hiba_fib;
    7373        }
    7474      if ( e==dijkstra_test2.pred(u) &&
    75            dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) )
     75           dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap[e] )
    7676        {
    7777          std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
    78             dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl;
     78            dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap[e]<<std::endl;
    7979          ++hiba_bin;
    8080        }

  • src/work/jacint/dijkstra.h

    r211 r217  
    4646    typename Graph::NodeMap<Edge> predecessor;
    4747    typename Graph::NodeMap<T> distance;
     48    //FIXME:
    4849    typename Graph::NodeMap<bool> reach;
     50    //typename Graph::NodeMap<int> reach;
    4951   
    5052  public :
    … …  
    6668      }
    6769     
     70      //FIXME:
    6871      typename Graph::NodeMap<bool> scanned(G,false);
     72      //typename Graph::NodeMap<int> scanned(G,false);
    6973      typename Graph::NodeMap<int> heap_map(G,-1);
    7074     
    … …  
    7781       
    7882        Node v=heap.top();
    79         T oldvalue=heap.get(v);
     83        T oldvalue=heap[v];
    8084        heap.pop();
    8185        distance.set(v, oldvalue);
    … …  
    9195              heap.push(w,oldvalue+length[e]);
    9296              predecessor.set(w,e);
    93             } else if ( oldvalue+length[e] < heap.get(w) ) {
     97            } else if ( oldvalue+length[e] < heap[w] ) {
    9498              predecessor.set(w,e);
    9599              heap.decrease(w, oldvalue+length[e]);
    … …  
    98102        }
    99103      }
    100     } 
     104    }
    101105   
    102 
    103106    T dist(Node v) {
    104107      return distance[v];
    105108    }
    106 
    107109
    108110    Edge pred(Node v) {
    … …  
    110112    }
    111113     
    112 
    113114    bool reached(Node v) {
    114115      return reach[v];

  • src/work/jacint/fib_heap.h

    r211 r217  
    9595
    9696    void set (Item const it, PrioType const value) {
    97       int i=iimap.get(it);
     97      int i=iimap[it];
    9898      if ( i >= 0 && container[i].in ) {
    9999        if ( comp(value, container[i].prio) ) decrease(it, value);
    … …  
    104104
    105105    void push (Item const it, PrioType const value) {
    106       int i=iimap.get(it);     
     106      int i=iimap[it];     
    107107      if ( i < 0 ) {
    108108        int s=container.size();
    … …  
    146146
    147147
    148     PrioType& operator[](const Item& it) const {
    149       return container[iimap.get(it)].prio;
     148    PrioType& operator[](const Item& it) {
     149      return container[iimap[it]].prio;
    150150    }
    151151   
    152152    const PrioType& operator[](const Item& it) const {
    153       return container[iimap.get(it)].prio;
    154     }
    155 
    156     const PrioType get(const Item& it) const {
    157       return container[iimap.get(it)].prio;
    158     }
    159 
    160 
     153      return container[iimap[it]].prio;
     154    }
     155
     156//     const PrioType get(const Item& it) const {
     157//       return container[iimap[it]].prio;
     158//     }
    161159
    162160    void pop() {
    … …  
    193191   
    194192    void erase (const Item& it) {
    195       int i=iimap.get(it);
     193      int i=iimap[it];
    196194     
    197195      if ( i >= 0 && container[i].in ) {       
    … …  
    208206
    209207    void decrease (Item it, PrioType const value) {
    210       int i=iimap.get(it);
     208      int i=iimap[it];
    211209      container[i].prio=value;
    212210      int p=container[i].parent;
    … …  
    227225
    228226    state_enum state(const Item &it) const {
    229       int i=iimap.get(it);
     227      int i=iimap[it];
    230228      if( i>=0 ) {
    231229        if ( container[i].in ) i=0;
Note: See TracChangeset for help on using the changeset viewer.