1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/jacint/dijkstra.cc Tue Mar 09 15:32:40 2004 +0000
1.3 @@ -0,0 +1,242 @@
1.4 +#include <iostream>
1.5 +#include <vector>
1.6 +#include <string>
1.7 +
1.8 +#include <list_graph.hh>
1.9 +#include <dijkstra.h>
1.10 +
1.11 +using namespace hugo;
1.12 +
1.13 +int main (int, char*[])
1.14 +{
1.15 + typedef ListGraph::NodeIt NodeIt;
1.16 + typedef ListGraph::EdgeIt EdgeIt;
1.17 + typedef ListGraph::EachNodeIt EachNodeIt;
1.18 + typedef ListGraph::EachEdgeIt EachEdgeIt;
1.19 + typedef ListGraph::OutEdgeIt OutEdgeIt;
1.20 + typedef ListGraph::InEdgeIt InEdgeIt;
1.21 +
1.22 + ListGraph flow_test;
1.23 +
1.24 + /* //Ahuja könyv példája, maxflowvalue=13
1.25 + NodeIt s=flow_test.addNode();
1.26 + NodeIt v1=flow_test.addNode();
1.27 + NodeIt v2=flow_test.addNode();
1.28 + NodeIt v3=flow_test.addNode();
1.29 + NodeIt v4=flow_test.addNode();
1.30 + NodeIt v5=flow_test.addNode();
1.31 + NodeIt t=flow_test.addNode();
1.32 +
1.33 + ListGraph::NodeMap<std::string> Node_name(flow_test);
1.34 + Node_name.set(s, "s");
1.35 + Node_name.set(v1, "v1");
1.36 + Node_name.set(v2, "v2");
1.37 + Node_name.set(v3, "v3");
1.38 + Node_name.set(v4, "v4");
1.39 + Node_name.set(v5, "v5");
1.40 + Node_name.set(t, "t");
1.41 +
1.42 + EdgeIt s_v1=flow_test.addEdge(s, v1);
1.43 + EdgeIt s_v2=flow_test.addEdge(s, v2);
1.44 + EdgeIt s_v3=flow_test.addEdge(s, v3);
1.45 + EdgeIt v2_v4=flow_test.addEdge(v2, v4);
1.46 + EdgeIt v2_v5=flow_test.addEdge(v2, v5);
1.47 + EdgeIt v3_v5=flow_test.addEdge(v3, v5);
1.48 + EdgeIt v4_t=flow_test.addEdge(v4, t);
1.49 + EdgeIt v5_t=flow_test.addEdge(v5, t);
1.50 + EdgeIt v2_s=flow_test.addEdge(v2, s);
1.51 +
1.52 + ListGraph::EdgeMap<int> cap(flow_test);
1.53 + cap.set(s_v1, 0);
1.54 + cap.set(s_v2, 10);
1.55 + cap.set(s_v3, 10);
1.56 + cap.set(v2_v4, 5);
1.57 + cap.set(v2_v5, 8);
1.58 + cap.set(v3_v5, 5);
1.59 + cap.set(v4_t, 8);
1.60 + cap.set(v5_t, 8);
1.61 + cap.set(v2_s, 0);
1.62 + */
1.63 +
1.64 +
1.65 + //Marci példája, maxflowvalue=23
1.66 + NodeIt s=flow_test.addNode();
1.67 + NodeIt v1=flow_test.addNode();
1.68 + NodeIt v2=flow_test.addNode();
1.69 + NodeIt v3=flow_test.addNode();
1.70 + NodeIt v4=flow_test.addNode();
1.71 + NodeIt t=flow_test.addNode();
1.72 + NodeIt z=flow_test.addNode();
1.73 +
1.74 +
1.75 + ListGraph::NodeMap<std::string> Node_name(flow_test);
1.76 + Node_name.set(s, "s");
1.77 + Node_name.set(v1, "v1");
1.78 + Node_name.set(v2, "v2");
1.79 + Node_name.set(v3, "v3");
1.80 + Node_name.set(v4, "v4");
1.81 + Node_name.set(t, "t");
1.82 + Node_name.set(z, "z");
1.83 +
1.84 + EdgeIt s_v1=flow_test.addEdge(s, v1);
1.85 + EdgeIt s_v2=flow_test.addEdge(s, v2);
1.86 + EdgeIt v1_v2=flow_test.addEdge(v1, v2);
1.87 + EdgeIt v2_v1=flow_test.addEdge(v2, v1);
1.88 + EdgeIt v1_v3=flow_test.addEdge(v1, v3);
1.89 + EdgeIt v3_v2=flow_test.addEdge(v3, v2);
1.90 + EdgeIt v2_v4=flow_test.addEdge(v2, v4);
1.91 + EdgeIt v4_v3=flow_test.addEdge(v4, v3);
1.92 + EdgeIt v3_t=flow_test.addEdge(v3, t);
1.93 + EdgeIt v4_t=flow_test.addEdge(v4, t);
1.94 + EdgeIt v3_v3=flow_test.addEdge(v3, v3);
1.95 + EdgeIt s_z=flow_test.addEdge(s, z);
1.96 + // EdgeIt v2_s=flow_test.addEdge(v2, s);
1.97 +
1.98 +
1.99 +
1.100 + ListGraph::EdgeMap<int> cap(flow_test);
1.101 + cap.set(s_v1, 16);
1.102 + cap.set(s_v2, 13);
1.103 + cap.set(v1_v2, 10);
1.104 + cap.set(v2_v1, 4);
1.105 + cap.set(v1_v3, 12);
1.106 + cap.set(v3_v2, 9);
1.107 + cap.set(v2_v4, 14);
1.108 + cap.set(v4_v3, 7);
1.109 + cap.set(v3_t, 20);
1.110 + cap.set(v4_t, 4);
1.111 + cap.set(v3_v3, 4);
1.112 + cap.set(s_z, 4);
1.113 + // cap.set(v2_s, 0);
1.114 +
1.115 +
1.116 +
1.117 + //pelda 3, maxflowvalue=4
1.118 + /* NodeIt s=flow_test.addNode();
1.119 + NodeIt v1=flow_test.addNode();
1.120 + NodeIt v2=flow_test.addNode();
1.121 + NodeIt t=flow_test.addNode();
1.122 + NodeIt w=flow_test.addNode();
1.123 +
1.124 + NodeMap<ListGraph, std::string> Node_name(flow_test);
1.125 + Node_name.set(s, "s");
1.126 + Node_name.set(v1, "v1");
1.127 + Node_name.set(v2, "v2");
1.128 + Node_name.set(t, "t");
1.129 + Node_name.set(w, "w");
1.130 +
1.131 + EdgeIt s_v1=flow_test.addEdge(s, v1);
1.132 + EdgeIt v1_v2=flow_test.addEdge(v1, v2);
1.133 + EdgeIt v2_t=flow_test.addEdge(v2, t);
1.134 + EdgeIt v1_v1=flow_test.addEdge(v1, v1);
1.135 + EdgeIt s_w=flow_test.addEdge(s, w);
1.136 +
1.137 +
1.138 + EdgeMap<ListGraph, int> cap(flow_test);
1.139 +
1.140 + cap.set(s_v1, 16);
1.141 + cap.set(v1_v2, 10);
1.142 + cap.set(v2_t, 4);
1.143 + cap.set(v1_v1, 3);
1.144 + cap.set(s_w, 5);
1.145 + */
1.146 +
1.147 +
1.148 +
1.149 + /*
1.150 + std::cout << "Testing reverse_bfs..." << std::endl;
1.151 +
1.152 + reverse_bfs<ListGraph> bfs_test(flow_test, t);
1.153 +
1.154 + bfs_test.run();
1.155 +
1.156 + for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
1.157 + std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
1.158 + }
1.159 +
1.160 + */
1.161 +
1.162 +
1.163 + /*
1.164 + std::cout << "Testing preflow_push_hl..." << std::endl;
1.165 +
1.166 + preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
1.167 +
1.168 + preflow_push_test.run();
1.169 +
1.170 + std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
1.171 +
1.172 + std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
1.173 +
1.174 + ListGraph::EdgeMap<int> flow=preflow_push_test.allflow();
1.175 + for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
1.176 + std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
1.177 + }
1.178 +
1.179 + std::cout << "A minimum cut: " <<std::endl;
1.180 + ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
1.181 +
1.182 + for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
1.183 + if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
1.184 + }
1.185 +
1.186 + std::cout<<"\n\n"<<std::endl;
1.187 +
1.188 +
1.189 +
1.190 +
1.191 + std::cout << "Testing preflow_push_max_flow..." << std::endl;
1.192 +
1.193 + preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
1.194 +
1.195 + max_flow_test.run();
1.196 +
1.197 + std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
1.198 +
1.199 + std::cout << "A minimum cut: " <<std::endl;
1.200 + ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
1.201 +
1.202 + for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
1.203 + if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
1.204 + }
1.205 +
1.206 + std::cout << std::endl <<std::endl;
1.207 + */
1.208 +
1.209 +
1.210 + std::cout << "Testing dijkstra..." << std::endl;
1.211 +
1.212 + NodeIt root=s;
1.213 +
1.214 + Dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);
1.215 +
1.216 + dijkstra_test.run();
1.217 +
1.218 + EachNodeIt w;
1.219 +
1.220 + for ( flow_test.getFirst(w); flow_test.valid(w) ; flow_test.next(w) ) {
1.221 + if (dijkstra_test.reach(w)) {
1.222 + std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);
1.223 + if (dijkstra_test.pred(w).valid()) {
1.224 + std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl;
1.225 + } else {
1.226 + std::cout <<", this is the root."<<std::endl; }
1.227 +
1.228 + } else {
1.229 + std::cout << w << " is not reachable from " << root <<std::endl;
1.230 + }
1.231 + }
1.232 +
1.233 +
1.234 +
1.235 + return 0;
1.236 +}
1.237 +
1.238 +
1.239 +
1.240 +
1.241 +
1.242 +
1.243 +
1.244 +
1.245 +
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/work/jacint/dijkstra.h Tue Mar 09 15:32:40 2004 +0000
2.3 @@ -0,0 +1,124 @@
2.4 +// -*- C++ -*-
2.5 +/*
2.6 + *template <Graph, T, Heap=FibHeap>
2.7 + *
2.8 + *
2.9 + *Constructor:
2.10 + *
2.11 + *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
2.12 + *
2.13 + *
2.14 + *
2.15 + *Member functions:
2.16 + *
2.17 + *void run()
2.18 + *
2.19 + * The following function should be used after run() was already run.
2.20 + *
2.21 + *
2.22 + *T dist(NodeIt v) : returns the distance from s to v.
2.23 + * It is 0 if v is not reachable from s.
2.24 + *
2.25 + *
2.26 + *EdgeIt pred(NodeIt v) : returns the last edge
2.27 + * of a shortest s-v path. Returns an invalid iterator
2.28 + * if v=s or v is not reachable from s.
2.29 + *
2.30 + *
2.31 + *bool reach(NodeIt v) : true iff v is reachable from s
2.32 + *
2.33 + */
2.34 +
2.35 +#ifndef DIJKSTRA_HH
2.36 +#define DIJKSTRA_HH
2.37 +
2.38 +#include <fib_heap.h>
2.39 +
2.40 +namespace hugo {
2.41 +
2.42 + template <typename Graph, typename T,
2.43 + typename Heap=FibHeap<typename Graph::NodeIt, T,
2.44 + typename Graph::NodeMap<int> > >
2.45 + class Dijkstra{
2.46 + typedef typename Graph::NodeIt NodeIt;
2.47 + typedef typename Graph::EdgeIt EdgeIt;
2.48 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.49 +
2.50 + Graph& G;
2.51 + NodeIt s;
2.52 + typename Graph::NodeMap<EdgeIt> predecessor;
2.53 + typename Graph::NodeMap<T> distance;
2.54 + typename Graph::EdgeMap<T>& length;
2.55 + typename Graph::NodeMap<bool> reached;
2.56 +
2.57 + public :
2.58 +
2.59 + /*
2.60 + The distance of the nodes is 0.
2.61 + */
2.62 + Dijkstra(Graph& _G, NodeIt const _s,
2.63 + typename Graph::EdgeMap<T>& _length) :
2.64 + G(_G), s(_s), predecessor(G), distance(G),
2.65 + length(_length), reached(G, false) { }
2.66 +
2.67 +
2.68 + void run() {
2.69 +
2.70 + typename Graph::NodeMap<bool> scanned(G, false);
2.71 + typename Graph::NodeMap<int> heap_map(G,-1);
2.72 +
2.73 + Heap heap(heap_map);
2.74 +
2.75 + heap.push(s,0);
2.76 + reached.set(s, true);
2.77 +
2.78 + while ( !heap.empty() ) {
2.79 +
2.80 + NodeIt v=heap.top();
2.81 + T oldvalue=heap.get(v);
2.82 + distance.set(v, oldvalue);
2.83 + heap.pop();
2.84 +
2.85 + OutEdgeIt e;
2.86 + for( G.getFirst(e,v); G.valid(e); G.next(e)) {
2.87 + NodeIt w=G.head(e);
2.88 +
2.89 + if ( !scanned.get(w) ) {
2.90 + if ( !reached.get(w) ) {
2.91 + reached.set(w,true);
2.92 + heap.push(w,oldvalue+length.get(e));
2.93 + predecessor.set(w,e);
2.94 +
2.95 + } else if ( oldvalue+length.get(e) < heap.get(w) ) {
2.96 + predecessor.set(w,e);
2.97 + heap.decrease(w, oldvalue+length.get(e));
2.98 + }
2.99 + }
2.100 + }
2.101 + scanned.set(v,true);
2.102 + }
2.103 + }
2.104 +
2.105 +
2.106 + T dist(NodeIt v) {
2.107 + return distance.get(v);
2.108 + }
2.109 +
2.110 +
2.111 + EdgeIt pred(NodeIt v) {
2.112 + if ( v!=s ) return predecessor.get(v);
2.113 + else return EdgeIt();
2.114 + }
2.115 +
2.116 +
2.117 + bool reach(NodeIt v) {
2.118 + return reached.get(v);
2.119 + }
2.120 +
2.121 + };
2.122 +
2.123 +}
2.124 +
2.125 +#endif
2.126 +
2.127 +
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/work/jacint/fib_heap.h Tue Mar 09 15:32:40 2004 +0000
3.3 @@ -0,0 +1,399 @@
3.4 +// -*- C++ -*-
3.5 +/*
3.6 + *template <typename Item,
3.7 + * typename Prio,
3.8 + * typename ItemIntMap,
3.9 + * typename Compare = std::less<Prio> >
3.10 + *
3.11 + *constructors:
3.12 + *
3.13 + *FibHeap(ItemIntMap), FibHeap(ItemIntMap, Compare)
3.14 + *
3.15 + *Member functions:
3.16 + *
3.17 + *int size() : returns the number of elements in the heap
3.18 + *
3.19 + *bool empty() : true iff size()=0
3.20 + *
3.21 + *void push(Item, Prio) : pushes Item to the heap with priority Prio. If
3.22 + * Item was already in the heap, it calls decrease(Item, Prio)
3.23 + *
3.24 + *Item top() : returns the Item with least Prio
3.25 + *
3.26 + *Prio prio() : returns the least Prio
3.27 + *
3.28 + *Prio get(Item) : returns Prio of Item
3.29 + *
3.30 + *void pop() : deletes the Item with least Prio
3.31 + *
3.32 + *void erase(Item) : deletes Item from the heap if it was already there
3.33 + *
3.34 + *void decrease(Item, P) : If Item was not in the heap, then it calls
3.35 + * push(Item, P). If item is in the heap with Prio more than P
3.36 + * then sets its Prio to P.
3.37 + *
3.38 + *void increase(Item, P) : If Item was not in the heap, then it calls
3.39 + * push(Item, P). If item is in the heap with Prio less than P
3.40 + * then sets its Prio to P.
3.41 + *
3.42 + *
3.43 + *In Fibonacci heaps, increase and erase are not efficient, in case of
3.44 + *many calls to these operations, it is better to use bin_heap.
3.45 + */
3.46 +
3.47 +#ifndef FIB_HEAP_H
3.48 +#define FIB_HEAP_H
3.49 +
3.50 +#include <vector>
3.51 +#include <functional>
3.52 +#include <math.h>
3.53 +
3.54 +namespace hugo {
3.55 +
3.56 + template <typename Item, typename Prio, typename ItemIntMap,
3.57 + typename Compare = std::less<Prio> >
3.58 +
3.59 + class FibHeap {
3.60 +
3.61 + typedef Prio PrioType;
3.62 +
3.63 + class store;
3.64 +
3.65 + std::vector<store> container;
3.66 + int minimum;
3.67 + bool blank;
3.68 + ItemIntMap &iimap;
3.69 + Compare comp;
3.70 +
3.71 + public :
3.72 +
3.73 + FibHeap(ItemIntMap &_iimap) : minimum(), blank(true), iimap(_iimap) {}
3.74 + FibHeap(ItemIntMap &_iimap, const Compare &_comp) : minimum(),
3.75 + blank(true), iimap(_iimap), comp(_comp) {}
3.76 +
3.77 +
3.78 + int size() const {
3.79 + int s=0;
3.80 + for ( unsigned int i=0; i!=container.size(); ++i )
3.81 + if ( container[i].in ) ++s;
3.82 + return s;
3.83 + }
3.84 +
3.85 +
3.86 + bool empty() const { return blank; }
3.87 +
3.88 +
3.89 + void push (Item const it, PrioType const value)
3.90 + {
3.91 +
3.92 + int i=iimap.get(it);
3.93 +
3.94 + if ( i >= 0 && container[i].in ) decrease(it, value);
3.95 + else {
3.96 + if ( i < 0 ) {
3.97 + int s=container.size();
3.98 + iimap.set( it, s );
3.99 + store st;
3.100 + st.name=it;
3.101 + container.push_back(st);
3.102 + i=s;
3.103 + }
3.104 +
3.105 + if ( !blank ) {
3.106 + container[container[minimum].right_neighbor].left_neighbor=i;
3.107 + container[i].right_neighbor=container[minimum].right_neighbor;
3.108 + container[minimum].right_neighbor=i;
3.109 + container[i].left_neighbor=minimum;
3.110 + if ( !comp( container[minimum].prio, value) ) minimum=i;
3.111 +
3.112 +
3.113 +
3.114 + } else {
3.115 + container[i].right_neighbor=container[i].left_neighbor=i;
3.116 + minimum=i;
3.117 + blank=false;
3.118 + }
3.119 + container[i].prio=value;
3.120 + }
3.121 + }
3.122 +
3.123 +
3.124 + Item top() const {
3.125 + if ( !blank ) {
3.126 + return container[minimum].name;
3.127 + } else {
3.128 + return Item();
3.129 + }
3.130 + }
3.131 +
3.132 +
3.133 + PrioType prio() const {
3.134 + if ( !blank ) {
3.135 + return container[minimum].prio;
3.136 + } else {
3.137 + return PrioType();
3.138 + }
3.139 + }
3.140 +
3.141 +
3.142 + const PrioType get(const Item& it) const
3.143 + {
3.144 + int i=iimap.get(it);
3.145 +
3.146 + if ( i >= 0 && container[i].in ) {
3.147 + return container[i].prio;
3.148 + } else {
3.149 + return PrioType();
3.150 + }
3.151 + }
3.152 +
3.153 +
3.154 + void pop() {
3.155 + if ( !blank ) {
3.156 +
3.157 + /*The first case is that there are only one root.*/
3.158 + if ( container[minimum].left_neighbor==minimum ) {
3.159 + container[minimum].in=false;
3.160 + if ( container[minimum].degree==0 ) blank=true;
3.161 + else {
3.162 + makeroot(container[minimum].child);
3.163 + minimum=container[minimum].child;
3.164 + balance();
3.165 + }
3.166 + } else {
3.167 + int right=container[minimum].right_neighbor;
3.168 + unlace(minimum);
3.169 + container[minimum].in=false;
3.170 + if ( container[minimum].degree > 0 ) {
3.171 + int left=container[minimum].left_neighbor;
3.172 + int child=container[minimum].child;
3.173 + int last_child=container[child].left_neighbor;
3.174 +
3.175 + container[left].right_neighbor=child;
3.176 + container[child].left_neighbor=left;
3.177 + container[right].left_neighbor=last_child;
3.178 + container[last_child].right_neighbor=right;
3.179 +
3.180 + makeroot(child);
3.181 + }
3.182 + minimum=right;
3.183 + balance();
3.184 + } // the case where there are more roots
3.185 + }
3.186 + }
3.187 +
3.188 +
3.189 + void erase (const Item& it) {
3.190 + int i=iimap.get(it);
3.191 +
3.192 + if ( i >= 0 && container[i].in ) {
3.193 +
3.194 + if ( container[i].parent!=-1 ) {
3.195 + int p=container[i].parent;
3.196 + cut(i,p);
3.197 + cascade(p);
3.198 + minimum=i; //As if its prio would be -infinity
3.199 + }
3.200 + pop();
3.201 + }
3.202 + }
3.203 +
3.204 +
3.205 + void decrease (Item it, PrioType const value) {
3.206 + int i=iimap.get(it);
3.207 + if ( i >= 0 && container[i].in ) {
3.208 +
3.209 + if ( comp(value, container[i].prio) ) {
3.210 + container[i].prio=value;
3.211 +
3.212 + if ( container[i].parent!=-1 ) {
3.213 + int p=container[i].parent;
3.214 +
3.215 + if ( !comp(container[p].prio, value) ) {
3.216 + cut(i,p);
3.217 + cascade(p);
3.218 + if ( comp(value, container[minimum].prio) ) minimum=i;
3.219 + }
3.220 + }
3.221 + }
3.222 + } else push(it, value);
3.223 + }
3.224 +
3.225 +
3.226 + void increase (Item it, PrioType const value) {
3.227 + int i=iimap.get(it);
3.228 +
3.229 + if ( i >= 0 && container[i].in ) {
3.230 + if ( comp(container[i].prio, value) ) {
3.231 + erase(it);
3.232 + push(it, value);
3.233 + }
3.234 + } else push(it, value);
3.235 + }
3.236 +
3.237 +
3.238 + private:
3.239 +
3.240 + void balance() {
3.241 + int maxdeg=int( floor( 2.08*log(double(container.size()))))+1;
3.242 +
3.243 + std::vector<int> A(maxdeg,-1);
3.244 +
3.245 + /*
3.246 + *Recall that now minimum does not point to the minimum prio element.
3.247 + *We set minimum to this during balance().
3.248 + */
3.249 + int anchor=container[minimum].left_neighbor;
3.250 + int next=minimum;
3.251 + bool end=false;
3.252 +
3.253 + do {
3.254 + int active=next;
3.255 + int d=container[active].degree;
3.256 + if ( anchor==active ) end=true;
3.257 + next = container[active].right_neighbor;
3.258 + if ( !comp(container[minimum].prio, container[active].prio) )
3.259 + minimum=active;
3.260 +
3.261 + while (A[d]!=-1) {
3.262 +
3.263 + if( comp(container[active].prio, container[A[d]].prio) ) {
3.264 + fuse(active,A[d]);
3.265 + } else {
3.266 + fuse(A[d],active);
3.267 + active=A[d];
3.268 + }
3.269 + A[d]=-1;
3.270 + ++d;
3.271 + }
3.272 +
3.273 + A[d]=active;
3.274 + } while ( !end );
3.275 + }
3.276 +
3.277 +
3.278 +
3.279 +
3.280 + /*
3.281 + *All the siblings of a are made roots.
3.282 + */
3.283 + void makeroot (int c)
3.284 + {
3.285 + int s=c;
3.286 + do {
3.287 + container[s].parent=-1;
3.288 + s=container[s].right_neighbor;
3.289 + } while ( s != c );
3.290 + }
3.291 +
3.292 +
3.293 + void cut (int a, int b)
3.294 + {
3.295 +
3.296 + /*
3.297 + *Replacing a from the children of b.
3.298 + */
3.299 + --container[b].degree;
3.300 +
3.301 + if ( container[b].degree !=0 ) {
3.302 + int child=container[b].child;
3.303 + if ( child==a )
3.304 + container[b].child=container[child].right_neighbor;
3.305 +
3.306 + unlace(a);
3.307 +
3.308 + }
3.309 +
3.310 +
3.311 + /*Lacing i to the roots.*/
3.312 + int right=container[minimum].right_neighbor;
3.313 + container[minimum].right_neighbor=a;
3.314 + container[a].left_neighbor=minimum;
3.315 + container[a].right_neighbor=right;
3.316 + container[right].left_neighbor=a;
3.317 +
3.318 + container[a].parent=-1;
3.319 + container[a].marked=false;
3.320 + }
3.321 +
3.322 +
3.323 + void cascade (int a)
3.324 + {
3.325 + if ( container[a].parent!=-1 ) {
3.326 + int p=container[a].parent;
3.327 +
3.328 + if ( container[a].marked==false ) container[a].marked=true;
3.329 + else {
3.330 + cut(a,p);
3.331 + cascade(p);
3.332 + }
3.333 + }
3.334 + }
3.335 +
3.336 +
3.337 + void fuse (int a, int b)
3.338 + {
3.339 +
3.340 + unlace(b);
3.341 +
3.342 +
3.343 + /*Lacing b under a.*/
3.344 + container[b].parent=a;
3.345 +
3.346 + if (container[a].degree==0) {
3.347 + container[b].left_neighbor=b;
3.348 + container[b].right_neighbor=b;
3.349 + container[a].child=b;
3.350 + } else {
3.351 + int child=container[a].child;
3.352 + int last_child=container[child].left_neighbor;
3.353 + container[child].left_neighbor=b;
3.354 + container[b].right_neighbor=child;
3.355 + container[last_child].right_neighbor=b;
3.356 + container[b].left_neighbor=last_child;
3.357 + }
3.358 +
3.359 + ++container[a].degree;
3.360 +
3.361 + container[b].marked=false;
3.362 + }
3.363 +
3.364 +
3.365 + /*
3.366 + *It is invoked only if a has siblings.
3.367 + */
3.368 +
3.369 + void unlace (int a) {
3.370 + int leftn=container[a].left_neighbor;
3.371 + int rightn=container[a].right_neighbor;
3.372 + container[leftn].right_neighbor=rightn;
3.373 + container[rightn].left_neighbor=leftn;
3.374 + }
3.375 +
3.376 +
3.377 + class store {
3.378 + friend class FibHeap;
3.379 +
3.380 + Item name;
3.381 + int parent;
3.382 + int left_neighbor;
3.383 + int right_neighbor;
3.384 + int child;
3.385 + int degree;
3.386 + bool marked;
3.387 + bool in;
3.388 + PrioType prio;
3.389 +
3.390 + store() : parent(-1), child(-1), degree(), marked(false), in(true) {}
3.391 + };
3.392 +
3.393 + };
3.394 +
3.395 +} //namespace hugo
3.396 +#endif
3.397 +
3.398 +
3.399 +
3.400 +
3.401 +
3.402 +
4.1 --- a/src/work/jacint/makefile Mon Mar 08 12:29:07 2004 +0000
4.2 +++ b/src/work/jacint/makefile Tue Mar 09 15:32:40 2004 +0000
4.3 @@ -3,7 +3,7 @@
4.4 CXXFLAGS = -W -Wall -ansi -pedantic
4.5 LEDAROOT = /ledasrc/LEDA-4.1
4.6
4.7 -BINARIES = preflow
4.8 +BINARIES = preflow dijkstra
4.9
4.10 all: $(BINARIES)
4.11
4.12 @@ -13,6 +13,9 @@
4.13 preflow:
4.14 $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o preflow preflow.cc
4.15
4.16 +dijkstra:
4.17 + $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o dijkstra dijkstra.cc
4.18 +
4.19 clean:
4.20 $(RM) *.o $(BINARIES) .depend
4.21