1.1 --- a/src/work/jacint/dijkstra.cc Thu Mar 11 19:24:28 2004 +0000
1.2 +++ b/src/work/jacint/dijkstra.cc Thu Mar 11 23:31:13 2004 +0000
1.3 @@ -66,17 +66,24 @@
1.4 if ( e==dijkstra_test.pred(u) &&
1.5 dijkstra_test.dist(u) - dijkstra_test.dist(v) != cap.get(e) )
1.6 {
1.7 - std::cout<<"Hibas fael a fibonaccis Dijkstraban!"<<std::endl;
1.8 + std::cout<<"Hibas fael a fibonaccis Dijkstraban: "<<
1.9 + dijkstra_test.dist(u) - dijkstra_test.dist(v)- cap.get(e)<<std::endl;
1.10 ++hiba_fib;
1.11 }
1.12 if ( e==dijkstra_test2.pred(u) &&
1.13 dijkstra_test2.dist(u) - dijkstra_test2.dist(v) != cap.get(e) )
1.14 {
1.15 - std::cout<<"Hibas fael a binarisos Dijkstraban!"<<std::endl;
1.16 + std::cout<<"Hibas fael a binarisos Dijkstraban: "<<
1.17 + dijkstra_test2.dist(u) - dijkstra_test2.dist(v)- cap.get(e)<<std::endl;
1.18 ++hiba_bin;
1.19 }
1.20 }
1.21 - }
1.22 +
1.23 + if ( dijkstra_test.dist(u) != dijkstra_test2.dist(u) )
1.24 + std::cout << "Nem egyezik meg a tavolsag!"<<std::endl;
1.25 +
1.26 +
1.27 + }
1.28
1.29 std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
1.30 << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
1.31 @@ -84,5 +91,8 @@
1.32 std::cout << "Hibas elek szama a binarisos Dijkstraban: "
1.33 << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
1.34
1.35 +
1.36 +
1.37 +
1.38 return 0;
1.39 }
2.1 --- a/src/work/jacint/fib_heap.h Thu Mar 11 19:24:28 2004 +0000
2.2 +++ b/src/work/jacint/fib_heap.h Thu Mar 11 23:31:13 2004 +0000
2.3 @@ -21,11 +21,14 @@
2.4 *void push(Item, Prio) : pushes Item to the heap with priority Prio. Item
2.5 * mustn't be in the heap.
2.6 *
2.7 - *Item top() : returns the Item with least Prio
2.8 + *Item top() : returns the Item with least Prio.
2.9 + * Must be called only if heap is nonempty.
2.10 *
2.11 *Prio prio() : returns the least Prio
2.12 - *
2.13 + * Must be called only if heap is nonempty.
2.14 + *
2.15 *Prio get(Item) : returns Prio of Item
2.16 + * Must be called only if Item is in heap.
2.17 *
2.18 *void pop() : deletes the Item with least Prio
2.19 *
2.20 @@ -65,9 +68,9 @@
2.21
2.22 std::vector<store> container;
2.23 int minimum;
2.24 - bool blank;
2.25 ItemIntMap &iimap;
2.26 Compare comp;
2.27 + int num_items;
2.28
2.29 enum state_enum {
2.30 IN_HEAP = 0,
2.31 @@ -77,26 +80,23 @@
2.32
2.33 public :
2.34
2.35 - FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {}
2.36 + FibHeap(ItemIntMap &_iimap) : minimum(), iimap(_iimap), num_items() {}
2.37 FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
2.38 - blank(true), iimap(_iimap), comp(_comp) {}
2.39 + iimap(_iimap), comp(_comp), num_items() {}
2.40
2.41
2.42 int size() const {
2.43 - int s=0;
2.44 - for ( unsigned int i=0; i!=container.size(); ++i )
2.45 - if ( container[i].in ) ++s;
2.46 - return s;
2.47 + return num_items;
2.48 }
2.49
2.50
2.51 - bool empty() const { return blank; }
2.52 + bool empty() const { return num_items==0; }
2.53
2.54
2.55 void set (Item const it, PrioType const value) {
2.56 int i=iimap.get(it);
2.57 if ( i >= 0 && container[i].in ) {
2.58 - if ( !comp(container[i].prio, value) ) decrease(it, value);
2.59 + if ( comp(value, container[i].prio) ) decrease(it, value);
2.60 if ( comp(container[i].prio, value) ) increase(it, value);
2.61 } else push(it, value);
2.62 }
2.63 @@ -118,62 +118,45 @@
2.64 container[i].marked=false;
2.65 }
2.66
2.67 - if ( !blank ) {
2.68 + if ( num_items ) {
2.69 container[container[minimum].right_neighbor].left_neighbor=i;
2.70 container[i].right_neighbor=container[minimum].right_neighbor;
2.71 container[minimum].right_neighbor=i;
2.72 container[i].left_neighbor=minimum;
2.73 - if ( !comp( container[minimum].prio, value) ) minimum=i;
2.74 + if ( comp( value, container[minimum].prio) ) minimum=i;
2.75 } else {
2.76 container[i].right_neighbor=container[i].left_neighbor=i;
2.77 minimum=i;
2.78 - blank=false;
2.79 }
2.80 container[i].prio=value;
2.81 + ++num_items;
2.82 }
2.83
2.84
2.85 Item top() const {
2.86 - if ( !blank ) {
2.87 - return container[minimum].name;
2.88 - } else {
2.89 - return Item();
2.90 - }
2.91 + return container[minimum].name;
2.92 }
2.93
2.94
2.95 PrioType prio() const {
2.96 - if ( !blank ) {
2.97 - return container[minimum].prio;
2.98 - } else {
2.99 - return PrioType();
2.100 - }
2.101 + return container[minimum].prio;
2.102 }
2.103
2.104
2.105 const PrioType get(const Item& it) const {
2.106 - int i=iimap.get(it);
2.107 -
2.108 - if ( i >= 0 && container[i].in ) {
2.109 - return container[i].prio;
2.110 - } else {
2.111 - return PrioType();
2.112 - }
2.113 + return container[iimap.get(it)].prio;
2.114 }
2.115
2.116
2.117 -
2.118 -
2.119 void pop() {
2.120 /*The first case is that there are only one root.*/
2.121 if ( container[minimum].left_neighbor==minimum ) {
2.122 container[minimum].in=false;
2.123 - if ( container[minimum].degree==0 ) blank=true;
2.124 - else {
2.125 + if ( container[minimum].degree!=0 ) {
2.126 makeroot(container[minimum].child);
2.127 minimum=container[minimum].child;
2.128 balance();
2.129 - }
2.130 + }
2.131 } else {
2.132 int right=container[minimum].right_neighbor;
2.133 unlace(minimum);
2.134 @@ -193,23 +176,23 @@
2.135 minimum=right;
2.136 balance();
2.137 } // the case where there are more roots
2.138 + --num_items;
2.139 }
2.140
2.141
2.142 void erase (const Item& it) {
2.143 int i=iimap.get(it);
2.144
2.145 - if ( i >= 0 && container[i].in ) {
2.146 -
2.147 - if ( container[i].parent!=-1 ) {
2.148 - int p=container[i].parent;
2.149 - cut(i,p);
2.150 - cascade(p);
2.151 - minimum=i; //As if its prio would be -infinity
2.152 - }
2.153 - pop();
2.154 - }
2.155 - }
2.156 + if ( i >= 0 && container[i].in ) {
2.157 + if ( container[i].parent!=-1 ) {
2.158 + int p=container[i].parent;
2.159 + cut(i,p);
2.160 + cascade(p);
2.161 + }
2.162 + minimum=i; //As if its prio would be -infinity
2.163 + pop();
2.164 + }
2.165 + }
2.166
2.167
2.168 void decrease (Item it, PrioType const value) {
2.169 @@ -220,8 +203,8 @@
2.170 if ( p!=-1 && comp(value, container[p].prio) ) {
2.171 cut(i,p);
2.172 cascade(p);
2.173 - if ( comp(value, container[minimum].prio) ) minimum=i;
2.174 - }
2.175 + }
2.176 + if ( comp(value, container[minimum].prio) ) minimum=i;
2.177 }
2.178
2.179
2.180 @@ -310,7 +293,7 @@
2.181 }
2.182
2.183
2.184 - /*Lacing i to the roots.*/
2.185 + /*Lacing a to the roots.*/
2.186 int right=container[minimum].right_neighbor;
2.187 container[minimum].right_neighbor=a;
2.188 container[a].left_neighbor=minimum;
2.189 @@ -392,9 +375,3 @@
2.190
2.191 } //namespace hugo
2.192 #endif
2.193 -
2.194 -
2.195 -
2.196 -
2.197 -
2.198 -
3.1 --- a/src/work/jacint/makefile Thu Mar 11 19:24:28 2004 +0000
3.2 +++ b/src/work/jacint/makefile Thu Mar 11 23:31:13 2004 +0000
3.3 @@ -3,7 +3,7 @@
3.4 CXXFLAGS = -W -Wall -ansi -pedantic
3.5 LEDAROOT = /ledasrc/LEDA-4.1
3.6
3.7 -BINARIES = dijkstra
3.8 +BINARIES = prim
3.9
3.10 all: $(BINARIES)
3.11
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/jacint/prim.cc Thu Mar 11 23:31:13 2004 +0000
4.3 @@ -0,0 +1,49 @@
4.4 +#include <iostream>
4.5 +#include <fstream>
4.6 +
4.7 +#include <list_graph.hh>
4.8 +#include <dimacs.hh>
4.9 +#include <prim.h>
4.10 +#include <time_measure.h>
4.11 +
4.12 +#include <bin_heap.hh>
4.13 +#include <fib_heap.h>
4.14 +
4.15 +using namespace hugo;
4.16 +
4.17 +int main(int, char **) {
4.18 + typedef ListGraph::NodeIt NodeIt;
4.19 +
4.20 + ListGraph G;
4.21 + NodeIt s, t;
4.22 + ListGraph::EdgeMap<int> cap(G);
4.23 + readDimacsMaxFlow(std::cin, G, s, t, cap);
4.24 +
4.25 + std::cout << "prim demo ..." << std::endl;
4.26 +
4.27 + double pre_time=currTime();
4.28 + Prim<ListGraph, int, FibHeap<ListGraph::NodeIt, int,
4.29 + ListGraph::NodeMap<int> > > prim_test(G, cap);
4.30 + prim_test.run();
4.31 + double post_time=currTime();
4.32 +
4.33 + std::cout << "running time with fib_heap: "
4.34 + << post_time-pre_time << " sec"<< std::endl;
4.35 +
4.36 + pre_time=currTime();
4.37 + Prim<ListGraph, int, BinHeap<ListGraph::NodeIt, int,
4.38 + ListGraph::NodeMap<int> > > prim_test2(G, cap);
4.39 + prim_test2.run();
4.40 + post_time=currTime();
4.41 +
4.42 + std::cout << "running time with bin_heap: "
4.43 + << post_time-pre_time << " sec"<< std::endl;
4.44 +
4.45 + std::cout<<"A minimalis feszitofa sulya fib kupaccal: "<< prim_test.weight() <<std::endl;
4.46 + std::cout<<"A minimalis feszitofa sulya bin kupaccal: "<< prim_test2.weight() <<std::endl;
4.47 + if ( prim_test.weight() != prim_test2.weight() )
4.48 + std::cout<<"Nem egyezik meg!"<<std::endl;
4.49 + else std::cout<<"Megegyezik."<<std::endl;
4.50 +
4.51 + return 0;
4.52 +}
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/jacint/prim.h Thu Mar 11 23:31:13 2004 +0000
5.3 @@ -0,0 +1,170 @@
5.4 +// -*- C++ -*-
5.5 +
5.6 +//kell hogy tree_edge invalid elekbol alljon, Szep
5.7 +//lenne ha az elejen a konstrualas ilyet adna, de
5.8 +//ugy fest nem igy lesz, ekkor invalidalni kell
5.9 +
5.10 +/*
5.11 + *template <Graph, T, Heap=FibHeap>
5.12 + *
5.13 + *Constructor:
5.14 + *
5.15 + *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
5.16 + *
5.17 + *
5.18 + *Methods:
5.19 + *
5.20 + *void run()
5.21 + *
5.22 + * The followings functions should be used after run() was already run.
5.23 + *
5.24 + *T weight() : returns the minimum weight of a spanning tree of the
5.25 + * component of the root.
5.26 + *
5.27 + *EdgeIt tree(NodeIt v) : returns the first edge in the path from v
5.28 + * to the root. Returns an invalid iterator if v=s or v is
5.29 + * not reachable from the root.
5.30 + *
5.31 + *bool conn() : true iff G is connected
5.32 + *
5.33 + *bool reach(NodeIt v) : true iff v is in the same component as the root
5.34 + *
5.35 + *NodeIt root() : returns the root
5.36 + *
5.37 + */
5.38 +
5.39 +#ifndef PRIM_H
5.40 +#define PRIM_H
5.41 +
5.42 +#include <fib_heap.h>
5.43 +
5.44 +#include <iostream>
5.45 +
5.46 +namespace hugo {
5.47 +
5.48 + template <typename Graph, typename T,
5.49 + typename Heap=FibHeap<typename Graph::NodeIt, T,
5.50 + typename Graph::NodeMap<int> > >
5.51 + class Prim{
5.52 + typedef typename Graph::NodeIt NodeIt;
5.53 + typedef typename Graph::EachNodeIt EachNodeIt;
5.54 + typedef typename Graph::EdgeIt EdgeIt;
5.55 + typedef typename Graph::OutEdgeIt OutEdgeIt;
5.56 + typedef typename Graph::InEdgeIt InEdgeIt;
5.57 +
5.58 + Graph& G;
5.59 + NodeIt r;
5.60 + typename Graph::NodeMap<EdgeIt> tree_edge;
5.61 + typename Graph::NodeMap<T> min_weight;
5.62 + typename Graph::EdgeMap<T>& edge_weight;
5.63 + typename Graph::NodeMap<bool> reached;
5.64 +
5.65 + public :
5.66 +
5.67 + Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight,
5.68 + NodeIt const _r) :
5.69 + G(_G), r(_r), tree_edge(G), min_weight(G),
5.70 + edge_weight(_edge_weight), reached(G, false) { }
5.71 +
5.72 + Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) :
5.73 + G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)
5.74 + {
5.75 + EachNodeIt _r; //FIXME
5.76 + G.getFirst(_r);
5.77 + r=_r;
5.78 + }
5.79 +
5.80 +
5.81 + void run() {
5.82 +
5.83 + typename Graph::NodeMap<bool> scanned(G, false);
5.84 + typename Graph::NodeMap<int> heap_map(G,-1);
5.85 +
5.86 + Heap heap(heap_map);
5.87 +
5.88 + heap.push(r,0);
5.89 + reached.set(r, true);
5.90 +
5.91 + while ( !heap.empty() ) {
5.92 +
5.93 + NodeIt v=heap.top();
5.94 + min_weight.set(v, heap.get(v));
5.95 + heap.pop();
5.96 + scanned.set(v,true);
5.97 +
5.98 + OutEdgeIt e;
5.99 + for( G.getFirst(e,v); G.valid(e); G.next(e)) {
5.100 + NodeIt w=G.head(e);
5.101 +
5.102 + if ( !scanned.get(w) ) {
5.103 + if ( !reached.get(w) ) {
5.104 + reached.set(w,true);
5.105 + heap.push(w, edge_weight.get(e));
5.106 + tree_edge.set(w,e);
5.107 + } else if ( edge_weight.get(e) < heap.get(w) ) {
5.108 + tree_edge.set(w,e);
5.109 + heap.decrease(w, edge_weight.get(e));
5.110 + }
5.111 + }
5.112 + }
5.113 +
5.114 + InEdgeIt f;
5.115 + for( G.getFirst(f,v); G.valid(f); G.next(f)) {
5.116 + NodeIt w=G.tail(f);
5.117 +
5.118 + if ( !scanned.get(w) ) {
5.119 + if ( !reached.get(w) ) {
5.120 + reached.set(w,true);
5.121 + heap.push(w, edge_weight.get(f));
5.122 + tree_edge.set(w,f);
5.123 + } else if ( edge_weight.get(f) < heap.get(w) ) {
5.124 + tree_edge.set(w,f);
5.125 + heap.decrease(w, edge_weight.get(f));
5.126 + }
5.127 + }
5.128 + }
5.129 + }
5.130 + }
5.131 +
5.132 +
5.133 + T weight() {
5.134 + T w=0;
5.135 + EachNodeIt u;
5.136 + for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
5.137 + return w;
5.138 + }
5.139 +
5.140 +
5.141 + EdgeIt tree(NodeIt v) {
5.142 + return tree_edge.get(v);
5.143 + }
5.144 +
5.145 +
5.146 + bool conn() {
5.147 + bool c=true;
5.148 + EachNodeIt u;
5.149 + for ( G.getFirst(u) ; G.valid(u) ; G.next(u) )
5.150 + if ( !reached.get(u) ) {
5.151 + c=false;
5.152 + break;
5.153 + }
5.154 + return c;
5.155 + }
5.156 +
5.157 +
5.158 + bool reach(NodeIt v) {
5.159 + return reached.get(v);
5.160 + }
5.161 +
5.162 +
5.163 + NodeIt root() {
5.164 + return r;
5.165 + }
5.166 +
5.167 + };
5.168 +
5.169 +}
5.170 +
5.171 +#endif
5.172 +
5.173 +