COIN-OR::LEMON - Graph Library

Changeset 173:de9849252e78 in lemon-0.x


Ignore:
Timestamp:
03/12/04 00:31:13 (21 years ago)
Author:
jacint
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@246
Message:

* empty log message *

Location:
src/work/jacint
Files:
2 added
3 edited

Legend:

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

    r170 r173  
    6767           dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) )
    6868        {
    69           std::cout<<"Hibas fael a fibonaccis Dijkstraban!"<<std::endl;
     69          std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
     70            dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<std::endl;
    7071          ++hiba_fib;
    7172        }
     
    7374           dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) )
    7475        {
    75           std::cout<<"Hibas fael a binarisos Dijkstraban!"<<std::endl;
     76          std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
     77            dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl;
    7678          ++hiba_bin;
    7779        }
    7880    }
    79   }
     81 
     82    if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
     83      std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
     84
     85
     86 }
    8087
    8188  std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
     
    8592            << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
    8693
     94
     95
     96
    8797  return 0;
    8898}
  • src/work/jacint/fib_heap.h

    r167 r173  
    2222 *     mustn't be in the heap.
    2323 *
    24  *Item top() : returns the Item with least Prio
     24 *Item top() : returns the Item with least Prio.
     25 *     Must be called only if heap is nonempty.
    2526 *
    2627 *Prio prio() : returns the least Prio
    27  * 
     28 *     Must be called only if heap is nonempty.
     29 *
    2830 *Prio get(Item) : returns Prio of Item
     31 *     Must be called only if Item is in heap.
    2932 *
    3033 *void pop() : deletes the Item with least Prio
     
    6669    std::vector<store> container;
    6770    int minimum;
    68     bool blank;
    6971    ItemIntMap &iimap;
    7072    Compare comp;
     73    int num_items;
    7174
    7275    enum state_enum {
     
    7881  public :
    7982   
    80     FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {}
     83    FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {}
    8184    FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
    82       blank(true), iimap(_iimap), comp(_comp) {}
     85      iimap(_iimap), comp(_comp), num_items() {}
    8386   
    8487   
    8588    int size() const {
    86       int s=0;
    87       for ( unsigned int i=0; i!=container.size(); ++i )
    88         if ( container[i].in ) ++s;
    89       return s;
    90     }
    91 
    92 
    93     bool empty() const { return blank; }
     89      return num_items;
     90    }
     91
     92
     93    bool empty() const { return num_items==0; }
    9494
    9595
     
    9797      int i=iimap.get(it);
    9898      if ( i >= 0 && container[i].in ) {
    99         if ( !comp(container[i].prio, value) ) decrease(it, value);
     99        if ( comp(value, container[i].prio) ) decrease(it, value);
    100100        if ( comp(container[i].prio, value) ) increase(it, value);
    101101      } else push(it, value);
     
    119119      }
    120120
    121       if ( !blank ) {
     121      if ( num_items ) {
    122122        container[container[minimum].right_neighbor].left_neighbor=i;
    123123        container[i].right_neighbor=container[minimum].right_neighbor;
    124124        container[minimum].right_neighbor=i;
    125125        container[i].left_neighbor=minimum;
    126         if ( !comp( container[minimum].prio, value) ) minimum=i;
     126        if ( comp( value, container[minimum].prio) ) minimum=i;
    127127      } else {
    128128        container[i].right_neighbor=container[i].left_neighbor=i;
    129129        minimum=i;     
    130         blank=false;
    131130      }
    132131      container[i].prio=value;
     132      ++num_items;
    133133    }
    134134   
    135135
    136136    Item top() const {
    137       if ( !blank ) {
    138         return container[minimum].name;
    139       } else {
    140         return Item();
    141       }
     137      return container[minimum].name;
    142138    }
    143139   
    144140   
    145141    PrioType prio() const {
    146       if ( !blank ) {
    147         return container[minimum].prio;
    148       } else {
    149         return PrioType();
    150       }
     142      return container[minimum].prio;
    151143    }
    152144   
    153145
    154146    const PrioType get(const Item& it) const {
    155       int i=iimap.get(it);
    156      
    157       if ( i >= 0 && container[i].in ) {
    158         return container[i].prio;
    159       } else {
    160         return PrioType();
    161       }
    162     }
    163 
    164 
     147      return container[iimap.get(it)].prio;
     148    }
    165149
    166150
     
    169153      if ( container[minimum].left_neighbor==minimum ) {
    170154        container[minimum].in=false;
    171         if ( container[minimum].degree==0 ) blank=true;
    172         else {
     155        if ( container[minimum].degree!=0 ) {
    173156          makeroot(container[minimum].child);
    174157          minimum=container[minimum].child;
    175158          balance();
    176         } 
     159        }
    177160      } else {
    178161        int right=container[minimum].right_neighbor;
     
    194177        balance();
    195178      } // the case where there are more roots
     179      --num_items;   
    196180    }
    197181
     
    200184      int i=iimap.get(it);
    201185     
    202       if ( i >= 0 && container[i].in ) {
    203        
    204        if ( container[i].parent!=-1 ) {
    205          int p=container[i].parent;
    206          cut(i,p);         
    207          cascade(p);
    208          minimum=i;     //As if its prio would be -infinity
    209        }
    210        pop();
    211      }
    212    }
     186      if ( i >= 0 && container[i].in ) {       
     187        if ( container[i].parent!=-1 ) {
     188          int p=container[i].parent;
     189          cut(i,p);         
     190          cascade(p);
     191        }
     192        minimum=i;     //As if its prio would be -infinity
     193        pop();
     194      }
     195    }
    213196   
    214197
     
    221204        cut(i,p);           
    222205        cascade(p);
    223         if ( comp(value, container[minimum].prio) ) minimum=i;
    224       }
     206      }     
     207      if ( comp(value, container[minimum].prio) ) minimum=i;
    225208    }
    226209   
     
    311294     
    312295     
    313       /*Lacing i to the roots.*/
     296      /*Lacing a to the roots.*/
    314297      int right=container[minimum].right_neighbor;
    315298      container[minimum].right_neighbor=a;
     
    393376} //namespace hugo
    394377#endif
    395 
    396 
    397 
    398 
    399 
    400 
  • src/work/jacint/makefile

    r170 r173  
    44LEDAROOT = /ledasrc/LEDA-4.1
    55
    6 BINARIES = dijkstra
     6BINARIES = prim
    77
    88all: $(BINARIES)
Note: See TracChangeset for help on using the changeset viewer.