1.1 --- a/src/work/jacint/dijkstra.cc Fri Mar 19 21:15:14 2004 +0000
1.2 +++ b/src/work/jacint/dijkstra.cc Fri Mar 19 22:16:05 2004 +0000
1.3 @@ -1,8 +1,9 @@
1.4 #include <iostream>
1.5 #include <fstream>
1.6
1.7 -#include <list_graph.hh>
1.8 -#include <dimacs.hh>
1.9 +#include <smart_graph.h>
1.10 +#include <list_graph.h>
1.11 +#include <dimacs.h>
1.12 #include <dijkstra.h>
1.13 #include <time_measure.h>
1.14
1.15 @@ -12,30 +13,30 @@
1.16 using namespace hugo;
1.17
1.18 int main(int, char **) {
1.19 - typedef ListGraph::NodeIt NodeIt;
1.20 - typedef ListGraph::EachNodeIt EachNodeIt;
1.21 - typedef ListGraph::InEdgeIt InEdgeIt;
1.22 + typedef SmartGraph::Node Node;
1.23 + typedef SmartGraph::NodeIt NodeIt;
1.24 + typedef SmartGraph::InEdgeIt InEdgeIt;
1.25
1.26 - ListGraph G;
1.27 - NodeIt s, t;
1.28 - ListGraph::EdgeMap<int> cap(G);
1.29 + SmartGraph G;
1.30 + Node s, t;
1.31 + SmartGraph::EdgeMap<int> cap(G);
1.32 readDimacsMaxFlow(std::cin, G, s, t, cap);
1.33
1.34 std::cout << "dijkstra demo ..." << std::endl;
1.35
1.36 double pre_time=currTime();
1.37 - Dijkstra<ListGraph, int, FibHeap<ListGraph::NodeIt, int,
1.38 - ListGraph::NodeMap<int> > > dijkstra_test(G, s, cap);
1.39 - dijkstra_test.run();
1.40 + Dijkstra<SmartGraph, int, FibHeap<SmartGraph::Node, int,
1.41 + SmartGraph::NodeMap<int> > > dijkstra_test(G, cap);
1.42 + dijkstra_test.run(s);
1.43 double post_time=currTime();
1.44
1.45 std::cout << "running time with fib_heap: "
1.46 << post_time-pre_time << " sec"<< std::endl;
1.47
1.48 pre_time=currTime();
1.49 - Dijkstra<ListGraph, int, BinHeap<ListGraph::NodeIt, int,
1.50 - ListGraph::NodeMap<int> > > dijkstra_test2(G, s, cap);
1.51 - dijkstra_test2.run();
1.52 + Dijkstra<SmartGraph, int, BinHeap<SmartGraph::Node, int,
1.53 + SmartGraph::NodeMap<int> > > dijkstra_test2(G, cap);
1.54 + dijkstra_test2.run(s);
1.55 post_time=currTime();
1.56
1.57 std::cout << "running time with bin_heap: "
1.58 @@ -44,11 +45,11 @@
1.59
1.60 int hiba_fib=0;
1.61 int hiba_bin=0;
1.62 - EachNodeIt u;
1.63 - for ( G.getFirst(u) ; G.valid(u); G.next(u) ) {
1.64 + NodeIt u;
1.65 + for ( G.first(u) ; G.valid(u); G.next(u) ) {
1.66 InEdgeIt e;
1.67 - for ( G.getFirst(e,u); G.valid(e); G.next(e) ) {
1.68 - NodeIt v=G.tail(e);
1.69 + for ( G.first(e,u); G.valid(e); G.next(e) ) {
1.70 + Node v=G.tail(e);
1.71 if ( dijkstra_test.dist(u) - dijkstra_test.dist(v) > cap.get(e) )
1.72 {
1.73 std::cout<<"Hibas el a fibonaccis Dijkstraban: "
1.74 @@ -87,10 +88,10 @@
1.75
1.76 std::cout << "Hibas elek szama a fibonaccis Dijkstraban: "
1.77 << hiba_fib << " a " << G.edgeNum() <<"-bol."<< std::endl;
1.78 -
1.79 +
1.80 std::cout << "Hibas elek szama a binarisos Dijkstraban: "
1.81 << hiba_bin << " a " << G.edgeNum() <<"-bol."<< std::endl;
1.82 -
1.83 +
1.84
1.85
1.86
2.1 --- a/src/work/jacint/dijkstra.h Fri Mar 19 21:15:14 2004 +0000
2.2 +++ b/src/work/jacint/dijkstra.h Fri Mar 19 22:16:05 2004 +0000
2.3 @@ -1,119 +1,120 @@
2.4 // -*- C++ -*-
2.5 -
2.6 -//ha predecessor az elejen nem invalid, akkor hagyd csak ugy
2.7 -//scanned mutatja hogy jo ertek van-e benne vagy szemet
2.8 -
2.9 /*
2.10 - *template <Graph, T, Heap=FibHeap>
2.11 + *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
2.12 *
2.13 *Constructor:
2.14 *
2.15 - *Dijkstra(Graph G, NodeIt s, Graph::EdgeMap<T> length)
2.16 + *Dijkstra(Graph G, LengthMap length)
2.17 *
2.18 *
2.19 - *Member functions:
2.20 + *Methods:
2.21 *
2.22 - *void run()
2.23 + *void run(Node s)
2.24 *
2.25 - * The following function should be used after run() was already run.
2.26 + *T dist(Node v) : After run(s) was run, it returns the distance from s to v.
2.27 + * Returns T() if v is not reachable from s.
2.28 *
2.29 - *T dist(NodeIt v) : returns the distance from s to v.
2.30 - * It is 0 if v is not reachable from s.
2.31 + *Edge pred(Node v) : After run(s) was run, it returns the last
2.32 + * edge of a shortest s-v path. It is INVALID for s and for
2.33 + * the nodes not reachable from s.
2.34 *
2.35 - *EdgeIt pred(NodeIt v) : returns the last edge
2.36 - * of a shortest s-v path. Returns an invalid iterator
2.37 - * if v=s or v is not reachable from s.
2.38 - *
2.39 - *bool reach(NodeIt v) : true iff v is reachable from s
2.40 + *bool reached(Node v) : After run(s) was run, it is true iff v is
2.41 + * reachable from s
2.42 *
2.43 */
2.44
2.45 -#ifndef DIJKSTRA_H
2.46 -#define DIJKSTRA_H
2.47 +#ifndef HUGO_DIJKSTRA_H
2.48 +#define HUGO_DIJKSTRA_H
2.49
2.50 #include <fib_heap.h>
2.51 +#include <invalid.h>
2.52
2.53 namespace hugo {
2.54 -
2.55 +
2.56 template <typename Graph, typename T,
2.57 - typename Heap=FibHeap<typename Graph::NodeIt, T,
2.58 - typename Graph::NodeMap<int> > >
2.59 - class Dijkstra{
2.60 - typedef typename Graph::NodeIt NodeIt;
2.61 - typedef typename Graph::EdgeIt EdgeIt;
2.62 - typedef typename Graph::OutEdgeIt OutEdgeIt;
2.63 -
2.64 - Graph& G;
2.65 - NodeIt s;
2.66 - typename Graph::NodeMap<EdgeIt> predecessor;
2.67 - typename Graph::NodeMap<T> distance;
2.68 - typename Graph::EdgeMap<T>& length;
2.69 - typename Graph::NodeMap<bool> reached;
2.70 -
2.71 + typename Heap=FibHeap<typename Graph::Node, T,
2.72 + typename Graph::NodeMap<int> >,
2.73 + typename LengthMap=typename Graph::EdgeMap<T> >
2.74 + class Dijkstra{
2.75 + typedef typename Graph::Node Node;
2.76 + typedef typename Graph::NodeIt NodeIt;
2.77 + typedef typename Graph::Edge Edge;
2.78 + typedef typename Graph::OutEdgeIt OutEdgeIt;
2.79 +
2.80 + const Graph& G;
2.81 + const LengthMap& length;
2.82 + typename Graph::NodeMap<Edge> predecessor;
2.83 + typename Graph::NodeMap<T> distance;
2.84 + typename Graph::NodeMap<bool> reach;
2.85 +
2.86 public :
2.87 -
2.88 +
2.89 /*
2.90 The distance of the nodes is 0.
2.91 */
2.92 - Dijkstra(Graph& _G, NodeIt const _s,
2.93 - typename Graph::EdgeMap<T>& _length) :
2.94 - G(_G), s(_s), predecessor(G), distance(G),
2.95 - length(_length), reached(G, false) { }
2.96 + Dijkstra(Graph& _G, LengthMap& _length) : G(_G),
2.97 + length(_length), predecessor(_G), distance(_G), reach(_G) { }
2.98
2.99 +
2.100 + void run(Node s) {
2.101
2.102 - void run() {
2.103 + NodeIt u;
2.104 + for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
2.105 + predecessor.set(u,INVALID);
2.106 + distance.set(u,0);
2.107 + reach.set(u,false);
2.108 + }
2.109 +
2.110 + typename Graph::NodeMap<bool> scanned(G,false);
2.111 + typename Graph::NodeMap<int> heap_map(G,-1);
2.112 +
2.113 + Heap heap(heap_map);
2.114 +
2.115 + heap.push(s,0);
2.116 + reach.set(s, true);
2.117 +
2.118 + while ( !heap.empty() ) {
2.119
2.120 - typename Graph::NodeMap<bool> scanned(G, false);
2.121 - typename Graph::NodeMap<int> heap_map(G,-1);
2.122 + Node v=heap.top();
2.123 + T oldvalue=heap.get(v);
2.124 + heap.pop();
2.125 + distance.set(v, oldvalue);
2.126 + scanned.set(v,true);
2.127
2.128 - Heap heap(heap_map);
2.129 -
2.130 - heap.push(s,0);
2.131 - reached.set(s, true);
2.132 -
2.133 - while ( !heap.empty() ) {
2.134 -
2.135 - NodeIt v=heap.top();
2.136 - T oldvalue=heap.get(v);
2.137 - heap.pop();
2.138 - distance.set(v, oldvalue);
2.139 - scanned.set(v,true);
2.140 -
2.141 - OutEdgeIt e;
2.142 - for( G.getFirst(e,v); G.valid(e); G.next(e)) {
2.143 - NodeIt w=G.bNode(e);
2.144 + OutEdgeIt e;
2.145 + for( G.first(e,v); G.valid(e); G.next(e)) {
2.146 + Node w=G.head(e);
2.147
2.148 - if ( !scanned.get(w) ) {
2.149 - if ( !reached.get(w) ) {
2.150 - reached.set(w,true);
2.151 - heap.push(w,oldvalue+length.get(e));
2.152 - predecessor.set(w,e);
2.153 - } else if ( oldvalue+length.get(e) < heap.get(w) ) {
2.154 - predecessor.set(w,e);
2.155 - heap.decrease(w, oldvalue+length.get(e));
2.156 - }
2.157 + if ( !scanned[w] ) {
2.158 + if ( !reach[w] ) {
2.159 + reach.set(w,true);
2.160 + heap.push(w,oldvalue+length[e]);
2.161 + predecessor.set(w,e);
2.162 + } else if ( oldvalue+length[e] < heap.get(w) ) {
2.163 + predecessor.set(w,e);
2.164 + heap.decrease(w, oldvalue+length[e]);
2.165 }
2.166 }
2.167 }
2.168 - }
2.169 -
2.170 + }
2.171 + }
2.172 +
2.173
2.174 - T dist(NodeIt v) {
2.175 - return distance.get(v);
2.176 - }
2.177 + T dist(Node v) {
2.178 + return distance[v];
2.179 + }
2.180
2.181
2.182 - EdgeIt pred(NodeIt v) {
2.183 - if ( v!=s ) return predecessor.get(v);
2.184 - else return EdgeIt();
2.185 - }
2.186 + Edge pred(Node v) {
2.187 + return predecessor[v];
2.188 + }
2.189
2.190
2.191 - bool reach(NodeIt v) {
2.192 - return reached.get(v);
2.193 - }
2.194 -
2.195 - };
2.196 + bool reached(Node v) {
2.197 + return reach[v];
2.198 + }
2.199 +
2.200 + };
2.201
2.202 }
2.203
3.1 --- a/src/work/jacint/fib_heap.h Fri Mar 19 21:15:14 2004 +0000
3.2 +++ b/src/work/jacint/fib_heap.h Fri Mar 19 22:16:05 2004 +0000
3.3 @@ -143,11 +143,22 @@
3.4 }
3.5
3.6
3.7 +
3.8 +
3.9 + PrioType& operator[](const Item& it) const {
3.10 + return container[iimap.get(it)].prio;
3.11 + }
3.12 +
3.13 + const PrioType& operator[](const Item& it) const {
3.14 + return container[iimap.get(it)].prio;
3.15 + }
3.16 +
3.17 const PrioType get(const Item& it) const {
3.18 return container[iimap.get(it)].prio;
3.19 }
3.20
3.21
3.22 +
3.23 void pop() {
3.24 /*The first case is that there are only one root.*/
3.25 if ( container[minimum].left_neighbor==minimum ) {
4.1 --- a/src/work/jacint/makefile Fri Mar 19 21:15:14 2004 +0000
4.2 +++ b/src/work/jacint/makefile Fri Mar 19 22:16:05 2004 +0000
4.3 @@ -1,9 +1,9 @@
4.4 CXX3 := $(shell type -p g++-3.3 || type -p g++-3.2 || type -p g++-3.0 || type -p g++-3 || echo g++)
4.5 CXX2 = g++-2.95
4.6 CXXFLAGS = -W -Wall -ansi -pedantic
4.7 -LEDAROOT = /ledasrc/LEDA-4.1
4.8 +LEDAROOT ?= /ledasrc/LEDA-4.1
4.9
4.10 -BINARIES = preflow dijkstra prim
4.11 +BINARIES = dijkstra prim preflow
4.12
4.13 all: $(BINARIES)
4.14
4.15 @@ -11,13 +11,13 @@
4.16 sinclude .depend
4.17
4.18 preflow:
4.19 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o preflow preflow.cc
4.20 + $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o preflow preflow.cc
4.21
4.22 dijkstra:
4.23 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o dijkstra dijkstra.cc
4.24 + $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o dijkstra dijkstra.cc
4.25
4.26 prim:
4.27 - $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -o prim prim.cc
4.28 + $(CXX3) $(CXXFLAGS) -O3 -I. -I.. -I../marci -I../alpar -o prim prim.cc
4.29
4.30 clean:
4.31 $(RM) *.o $(BINARIES) .depend
5.1 --- a/src/work/jacint/preflow.cc Fri Mar 19 21:15:14 2004 +0000
5.2 +++ b/src/work/jacint/preflow.cc Fri Mar 19 22:16:05 2004 +0000
5.3 @@ -1,8 +1,8 @@
5.4 #include <iostream>
5.5 #include <fstream>
5.6
5.7 -#include <list_graph.hh>
5.8 -#include <dimacs.hh>
5.9 +#include <list_graph.h>
5.10 +#include <dimacs.h>
5.11 #include <preflow.h>
5.12 #include <time_measure.h>
5.13
5.14 @@ -11,11 +11,11 @@
5.15 // Use a DIMACS max flow file as stdin.
5.16 // read_dimacs_demo < dimacs_max_flow_file
5.17 int main(int, char **) {
5.18 - typedef ListGraph::NodeIt NodeIt;
5.19 - typedef ListGraph::EachEdgeIt EachEdgeIt;
5.20 + typedef ListGraph::Node Node;
5.21 + typedef ListGraph::EdgeIt EdgeIt;
5.22
5.23 ListGraph G;
5.24 - NodeIt s, t;
5.25 + Node s, t;
5.26 ListGraph::EdgeMap<int> cap(G);
5.27 readDimacsMaxFlow(std::cin, G, s, t, cap);
5.28
5.29 @@ -24,27 +24,30 @@
5.30 double mintime=1000000;
5.31
5.32 for ( int i=1; i!=11; ++i ) {
5.33 + ListGraph::EdgeMap<int> flow(G);
5.34 double pre_time=currTime();
5.35 - preflow<ListGraph, int> max_flow_test(G, s, t, cap);
5.36 + Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
5.37 + max_flow_test.run();
5.38 double post_time=currTime();
5.39 if ( mintime > post_time-pre_time ) mintime = post_time-pre_time;
5.40 }
5.41
5.42 - double pre_time=currTime();
5.43 - preflow<ListGraph, int> max_flow_test(G, s, t, cap);
5.44 - double post_time=currTime();
5.45 -
5.46 + ListGraph::EdgeMap<int> flow(G);
5.47 + Preflow<ListGraph, int> max_flow_test(G, s, t, cap, flow);
5.48 + max_flow_test.run();
5.49 +
5.50 ListGraph::NodeMap<bool> cut(G);
5.51 max_flow_test.minCut(cut);
5.52 int min_cut_value=0;
5.53 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
5.54 + EdgeIt e;
5.55 + for(G.first(e); G.valid(e); G.next(e)) {
5.56 if (cut.get(G.tail(e)) && !cut.get(G.head(e))) min_cut_value+=cap.get(e);
5.57 }
5.58
5.59 ListGraph::NodeMap<bool> cut1(G);
5.60 max_flow_test.minMinCut(cut1);
5.61 int min_min_cut_value=0;
5.62 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
5.63 + for(G.first(e); G.valid(e); G.next(e)) {
5.64 if (cut.get(G.tail(e)) && !cut.get(G.head(e)))
5.65 min_min_cut_value+=cap.get(e);
5.66 }
5.67 @@ -52,17 +55,13 @@
5.68 ListGraph::NodeMap<bool> cut2(G);
5.69 max_flow_test.maxMinCut(cut2);
5.70 int max_min_cut_value=0;
5.71 - for(EachEdgeIt e=G.first<EachEdgeIt>(); e.valid(); ++e) {
5.72 + for(G.first(e); G.valid(e); G.next(e)) {
5.73 if (cut2.get(G.tail(e)) && !cut2.get(G.head(e)))
5.74 max_min_cut_value+=cap.get(e);
5.75 }
5.76
5.77 std::cout << "min time of 10 runs: " << mintime << " sec"<< std::endl;
5.78 - std::cout << "phase 0: " << max_flow_test.time-pre_time
5.79 - << " sec"<< std::endl;
5.80 - std::cout << "phase 1: " << post_time-max_flow_test.time
5.81 - << " sec"<< std::endl;
5.82 - std::cout << "flow value: "<< max_flow_test.maxFlow() << std::endl;
5.83 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
5.84 std::cout << "min cut value: "<< min_cut_value << std::endl;
5.85 std::cout << "min min cut value: "<< min_min_cut_value << std::endl;
5.86 std::cout << "max min cut value: "<< max_min_cut_value <<
6.1 --- a/src/work/jacint/preflow.h Fri Mar 19 21:15:14 2004 +0000
6.2 +++ b/src/work/jacint/preflow.h Fri Mar 19 22:16:05 2004 +0000
6.3 @@ -1,7 +1,5 @@
6.4 // -*- C++ -*-
6.5 /*
6.6 -preflow.h
6.7 -by jacint.
6.8 Heuristics:
6.9 2 phase
6.10 gap
6.11 @@ -12,17 +10,15 @@
6.12
6.13 Parameters H0 and H1 are initialized to 20 and 10.
6.14
6.15 -The best preflow I could ever write.
6.16 +Constructors:
6.17
6.18 -The constructor runs the algorithm.
6.19 +Preflow(Graph, Node, Node, CapMap, FlowMap)
6.20
6.21 Members:
6.22
6.23 -T maxFlow() : returns the value of a maximum flow
6.24 +void run()
6.25
6.26 -T flowOnEdge(EdgeIt e) : for a fixed maximum flow x it returns x(e)
6.27 -
6.28 -FlowMap Flow() : returns the fixed maximum flow x
6.29 +T flowValue() : returns the value of a maximum flow
6.30
6.31 void minMinCut(CutMap& M) : sets M to the characteristic vector of the
6.32 minimum min cut. M should be a map of bools initialized to false.
6.33 @@ -35,8 +31,8 @@
6.34
6.35 */
6.36
6.37 -#ifndef PREFLOW_H
6.38 -#define PREFLOW_H
6.39 +#ifndef HUGO_PREFLOW_H
6.40 +#define HUGO_PREFLOW_H
6.41
6.42 #define H0 20
6.43 #define H1 1
6.44 @@ -44,33 +40,32 @@
6.45 #include <vector>
6.46 #include <queue>
6.47
6.48 -#include <time_measure.h>
6.49 -
6.50 namespace hugo {
6.51
6.52 template <typename Graph, typename T,
6.53 typename FlowMap=typename Graph::EdgeMap<T>,
6.54 typename CapMap=typename Graph::EdgeMap<T> >
6.55 - class preflow {
6.56 + class Preflow {
6.57
6.58 + typedef typename Graph::Node Node;
6.59 + typedef typename Graph::Edge Edge;
6.60 typedef typename Graph::NodeIt NodeIt;
6.61 - typedef typename Graph::EdgeIt EdgeIt;
6.62 - typedef typename Graph::EachNodeIt EachNodeIt;
6.63 typedef typename Graph::OutEdgeIt OutEdgeIt;
6.64 typedef typename Graph::InEdgeIt InEdgeIt;
6.65
6.66 - Graph& G;
6.67 - NodeIt s;
6.68 - NodeIt t;
6.69 - FlowMap flow;
6.70 - CapMap& capacity;
6.71 + const Graph& G;
6.72 + Node s;
6.73 + Node t;
6.74 + FlowMap& flow;
6.75 + const CapMap& capacity;
6.76 T value;
6.77
6.78 public:
6.79 - double time;
6.80 - preflow(Graph& _G, NodeIt _s, NodeIt _t, CapMap& _capacity ) :
6.81 - G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity)
6.82 - {
6.83 + Preflow(Graph& _G, Node _s, Node _t, CapMap& _capacity, FlowMap& _flow ) :
6.84 + G(_G), s(_s), t(_t), flow(_flow), capacity(_capacity) {}
6.85 +
6.86 +
6.87 + void run() {
6.88
6.89 bool phase=0; //phase 0 is the 1st phase, phase 1 is the 2nd
6.90 int n=G.nodeNum();
6.91 @@ -94,35 +89,36 @@
6.92 typename Graph::NodeMap<int> level(G,n);
6.93 typename Graph::NodeMap<T> excess(G);
6.94
6.95 - std::vector<NodeIt> active(n);
6.96 - typename Graph::NodeMap<NodeIt> next(G);
6.97 + std::vector<Node> active(n,INVALID);
6.98 + typename Graph::NodeMap<Node> next(G,INVALID);
6.99 //Stack of the active nodes in level i < n.
6.100 //We use it in both phases.
6.101
6.102 - typename Graph::NodeMap<NodeIt> left(G);
6.103 - typename Graph::NodeMap<NodeIt> right(G);
6.104 - std::vector<NodeIt> level_list(n);
6.105 + typename Graph::NodeMap<Node> left(G,INVALID);
6.106 + typename Graph::NodeMap<Node> right(G,INVALID);
6.107 + std::vector<Node> level_list(n,INVALID);
6.108 /*
6.109 List of the nodes in level i<n.
6.110 */
6.111
6.112 /*Reverse_bfs from t, to find the starting level.*/
6.113 level.set(t,0);
6.114 - std::queue<NodeIt> bfs_queue;
6.115 + std::queue<Node> bfs_queue;
6.116 bfs_queue.push(t);
6.117
6.118 while (!bfs_queue.empty()) {
6.119
6.120 - NodeIt v=bfs_queue.front();
6.121 + Node v=bfs_queue.front();
6.122 bfs_queue.pop();
6.123 - int l=level.get(v)+1;
6.124 + int l=level[v]+1;
6.125
6.126 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
6.127 - NodeIt w=G.tail(e);
6.128 - if ( level.get(w) == n && w != s ) {
6.129 + InEdgeIt e;
6.130 + for(G.first(e,v); G.valid(e); G.next(e)) {
6.131 + Node w=G.tail(e);
6.132 + if ( level[w] == n && w != s ) {
6.133 bfs_queue.push(w);
6.134 - NodeIt first=level_list[l];
6.135 - if ( first != 0 ) left.set(first,w);
6.136 + Node first=level_list[l];
6.137 + if ( G.valid(first) ) left.set(first,w);
6.138 right.set(w,first);
6.139 level_list[l]=w;
6.140 level.set(w, l);
6.141 @@ -134,18 +130,19 @@
6.142
6.143
6.144 /* Starting flow. It is everywhere 0 at the moment. */
6.145 - for(OutEdgeIt e=G.template first<OutEdgeIt>(s); e.valid(); ++e)
6.146 + OutEdgeIt e;
6.147 + for(G.first(e,s); G.valid(e); G.next(e))
6.148 {
6.149 - T c=capacity.get(e);
6.150 + T c=capacity[e];
6.151 if ( c == 0 ) continue;
6.152 - NodeIt w=G.head(e);
6.153 - if ( level.get(w) < n ) {
6.154 - if ( excess.get(w) == 0 && w!=t ) {
6.155 - next.set(w,active[level.get(w)]);
6.156 - active[level.get(w)]=w;
6.157 + Node w=G.head(e);
6.158 + if ( level[w] < n ) {
6.159 + if ( excess[w] == 0 && w!=t ) {
6.160 + next.set(w,active[level[w]]);
6.161 + active[level[w]]=w;
6.162 }
6.163 flow.set(e, c);
6.164 - excess.set(w, excess.get(w)+c);
6.165 + excess.set(w, excess[w]+c);
6.166 }
6.167 }
6.168
6.169 @@ -168,37 +165,38 @@
6.170 end=true;
6.171 } else {
6.172 phase=1;
6.173 - time=currTime();
6.174 level.set(s,0);
6.175 - std::queue<NodeIt> bfs_queue;
6.176 + std::queue<Node> bfs_queue;
6.177 bfs_queue.push(s);
6.178
6.179 while (!bfs_queue.empty()) {
6.180
6.181 - NodeIt v=bfs_queue.front();
6.182 + Node v=bfs_queue.front();
6.183 bfs_queue.pop();
6.184 - int l=level.get(v)+1;
6.185 + int l=level[v]+1;
6.186
6.187 - for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
6.188 - if ( capacity.get(e) == flow.get(e) ) continue;
6.189 - NodeIt u=G.tail(e);
6.190 - if ( level.get(u) >= n ) {
6.191 + InEdgeIt e;
6.192 + for(G.first(e,v); G.valid(e); G.next(e)) {
6.193 + if ( capacity[e] == flow[e] ) continue;
6.194 + Node u=G.tail(e);
6.195 + if ( level[u] >= n ) {
6.196 bfs_queue.push(u);
6.197 level.set(u, l);
6.198 - if ( excess.get(u) > 0 ) {
6.199 + if ( excess[u] > 0 ) {
6.200 next.set(u,active[l]);
6.201 active[l]=u;
6.202 }
6.203 }
6.204 }
6.205
6.206 - for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
6.207 - if ( 0 == flow.get(e) ) continue;
6.208 - NodeIt u=G.head(e);
6.209 - if ( level.get(u) >= n ) {
6.210 + OutEdgeIt f;
6.211 + for(G.first(f,v); G.valid(f); G.next(f)) {
6.212 + if ( 0 == flow[f] ) continue;
6.213 + Node u=G.head(f);
6.214 + if ( level[u] >= n ) {
6.215 bfs_queue.push(u);
6.216 level.set(u, l);
6.217 - if ( excess.get(u) > 0 ) {
6.218 + if ( excess[u] > 0 ) {
6.219 next.set(u,active[l]);
6.220 active[l]=u;
6.221 }
6.222 @@ -211,40 +209,41 @@
6.223 }
6.224
6.225
6.226 - if ( active[b] == 0 ) --b;
6.227 + if ( !G.valid(active[b]) ) --b;
6.228 else {
6.229 end=false;
6.230
6.231 - NodeIt w=active[b];
6.232 - active[b]=next.get(w);
6.233 - int lev=level.get(w);
6.234 - T exc=excess.get(w);
6.235 + Node w=active[b];
6.236 + active[b]=next[w];
6.237 + int lev=level[w];
6.238 + T exc=excess[w];
6.239 int newlevel=n; //bound on the next level of w
6.240
6.241 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
6.242 + OutEdgeIt e;
6.243 + for(G.first(e,w); G.valid(e); G.next(e)) {
6.244
6.245 - if ( flow.get(e) == capacity.get(e) ) continue;
6.246 - NodeIt v=G.head(e);
6.247 + if ( flow[e] == capacity[e] ) continue;
6.248 + Node v=G.head(e);
6.249 //e=wv
6.250
6.251 - if( lev > level.get(v) ) {
6.252 + if( lev > level[v] ) {
6.253 /*Push is allowed now*/
6.254
6.255 - if ( excess.get(v)==0 && v!=t && v!=s ) {
6.256 - int lev_v=level.get(v);
6.257 + if ( excess[v]==0 && v!=t && v!=s ) {
6.258 + int lev_v=level[v];
6.259 next.set(v,active[lev_v]);
6.260 active[lev_v]=v;
6.261 }
6.262
6.263 - T cap=capacity.get(e);
6.264 - T flo=flow.get(e);
6.265 + T cap=capacity[e];
6.266 + T flo=flow[e];
6.267 T remcap=cap-flo;
6.268
6.269 if ( remcap >= exc ) {
6.270 /*A nonsaturating push.*/
6.271
6.272 flow.set(e, flo+exc);
6.273 - excess.set(v, excess.get(v)+exc);
6.274 + excess.set(v, excess[v]+exc);
6.275 exc=0;
6.276 break;
6.277
6.278 @@ -252,50 +251,51 @@
6.279 /*A saturating push.*/
6.280
6.281 flow.set(e, cap);
6.282 - excess.set(v, excess.get(v)+remcap);
6.283 + excess.set(v, excess[v]+remcap);
6.284 exc-=remcap;
6.285 }
6.286 - } else if ( newlevel > level.get(v) ){
6.287 - newlevel = level.get(v);
6.288 + } else if ( newlevel > level[v] ){
6.289 + newlevel = level[v];
6.290 }
6.291
6.292 } //for out edges wv
6.293
6.294
6.295 if ( exc > 0 ) {
6.296 - for( InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
6.297 + InEdgeIt e;
6.298 + for(G.first(e,w); G.valid(e); G.next(e)) {
6.299
6.300 - if( flow.get(e) == 0 ) continue;
6.301 - NodeIt v=G.tail(e);
6.302 + if( flow[e] == 0 ) continue;
6.303 + Node v=G.tail(e);
6.304 //e=vw
6.305
6.306 - if( lev > level.get(v) ) {
6.307 + if( lev > level[v] ) {
6.308 /*Push is allowed now*/
6.309
6.310 - if ( excess.get(v)==0 && v!=t && v!=s ) {
6.311 - int lev_v=level.get(v);
6.312 + if ( excess[v]==0 && v!=t && v!=s ) {
6.313 + int lev_v=level[v];
6.314 next.set(v,active[lev_v]);
6.315 active[lev_v]=v;
6.316 }
6.317
6.318 - T flo=flow.get(e);
6.319 + T flo=flow[e];
6.320
6.321 if ( flo >= exc ) {
6.322 /*A nonsaturating push.*/
6.323
6.324 flow.set(e, flo-exc);
6.325 - excess.set(v, excess.get(v)+exc);
6.326 + excess.set(v, excess[v]+exc);
6.327 exc=0;
6.328 break;
6.329 } else {
6.330 /*A saturating push.*/
6.331
6.332 - excess.set(v, excess.get(v)+flo);
6.333 + excess.set(v, excess[v]+flo);
6.334 exc-=flo;
6.335 flow.set(e,0);
6.336 }
6.337 - } else if ( newlevel > level.get(v) ) {
6.338 - newlevel = level.get(v);
6.339 + } else if ( newlevel > level[v] ) {
6.340 + newlevel = level[v];
6.341 }
6.342 } //for in edges vw
6.343
6.344 @@ -318,38 +318,37 @@
6.345 b=newlevel;
6.346 } else {
6.347 //unlacing starts
6.348 - NodeIt right_n=right.get(w);
6.349 - NodeIt left_n=left.get(w);
6.350 + Node right_n=right[w];
6.351 + Node left_n=left[w];
6.352
6.353 - if ( right_n != 0 ) {
6.354 - if ( left_n != 0 ) {
6.355 + if ( G.valid(right_n) ) {
6.356 + if ( G.valid(left_n) ) {
6.357 right.set(left_n, right_n);
6.358 left.set(right_n, left_n);
6.359 } else {
6.360 level_list[lev]=right_n;
6.361 - left.set(right_n, 0);
6.362 + left.set(right_n, INVALID);
6.363 }
6.364 } else {
6.365 - if ( left_n != 0 ) {
6.366 - right.set(left_n, 0);
6.367 + if ( G.valid(left_n) ) {
6.368 + right.set(left_n, INVALID);
6.369 } else {
6.370 - level_list[lev]=0;
6.371 -
6.372 + level_list[lev]=INVALID;
6.373 }
6.374 }
6.375 //unlacing ends
6.376
6.377 //gapping starts
6.378 - if ( level_list[lev]==0 ) {
6.379 + if ( !G.valid(level_list[lev]) ) {
6.380
6.381 for (int i=lev; i!=k ; ) {
6.382 - NodeIt v=level_list[++i];
6.383 - while ( v != 0 ) {
6.384 + Node v=level_list[++i];
6.385 + while ( G.valid(v) ) {
6.386 level.set(v,n);
6.387 - v=right.get(v);
6.388 + v=right[v];
6.389 }
6.390 - level_list[i]=0;
6.391 - if ( !what_heur ) active[i]=0;
6.392 + level_list[i]=INVALID;
6.393 + if ( !what_heur ) active[i]=INVALID;
6.394 }
6.395
6.396 level.set(w,n);
6.397 @@ -365,10 +364,10 @@
6.398 active[newlevel]=w;
6.399 if ( what_heur ) b=newlevel;
6.400 if ( k < newlevel ) ++k;
6.401 - NodeIt first=level_list[newlevel];
6.402 - if ( first != 0 ) left.set(first,w);
6.403 + Node first=level_list[newlevel];
6.404 + if ( G.valid(first) ) left.set(first,w);
6.405 right.set(w,first);
6.406 - left.set(w,0);
6.407 + left.set(w,INVALID);
6.408 level_list[newlevel]=w;
6.409 }
6.410 }
6.411 @@ -398,7 +397,7 @@
6.412 } // while(true)
6.413
6.414
6.415 - value = excess.get(t);
6.416 + value = excess[t];
6.417 /*Max flow value.*/
6.418
6.419 } //void run()
6.420 @@ -411,23 +410,11 @@
6.421 Returns the maximum value of a flow.
6.422 */
6.423
6.424 - T maxFlow() {
6.425 + T flowValue() {
6.426 return value;
6.427 }
6.428
6.429
6.430 -
6.431 - /*
6.432 - For the maximum flow x found by the algorithm,
6.433 - it returns the flow value on edge e, i.e. x(e).
6.434 - */
6.435 -
6.436 - T flowOnEdge(EdgeIt e) {
6.437 - return flow.get(e);
6.438 - }
6.439 -
6.440 -
6.441 -
6.442 FlowMap Flow() {
6.443 return flow;
6.444 }
6.445 @@ -435,9 +422,10 @@
6.446
6.447
6.448 void Flow(FlowMap& _flow ) {
6.449 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v)
6.450 - _flow.set(v,flow.get(v));
6.451 - }
6.452 + NodeIt v;
6.453 + for(G.first(v) ; G.valid(v); G.next(v))
6.454 + _flow.set(v,flow[v]);
6.455 + }
6.456
6.457
6.458
6.459 @@ -448,26 +436,28 @@
6.460 template<typename _CutMap>
6.461 void minMinCut(_CutMap& M) {
6.462
6.463 - std::queue<NodeIt> queue;
6.464 + std::queue<Node> queue;
6.465
6.466 M.set(s,true);
6.467 queue.push(s);
6.468
6.469 while (!queue.empty()) {
6.470 - NodeIt w=queue.front();
6.471 + Node w=queue.front();
6.472 queue.pop();
6.473
6.474 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
6.475 - NodeIt v=G.head(e);
6.476 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
6.477 + OutEdgeIt e;
6.478 + for(G.first(e,w) ; G.valid(e); G.next(e)) {
6.479 + Node v=G.head(e);
6.480 + if (!M[v] && flow[e] < capacity[e] ) {
6.481 queue.push(v);
6.482 M.set(v, true);
6.483 }
6.484 }
6.485
6.486 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
6.487 - NodeIt v=G.tail(e);
6.488 - if (!M.get(v) && flow.get(e) > 0 ) {
6.489 + InEdgeIt f;
6.490 + for(G.first(f,w) ; G.valid(f); G.next(f)) {
6.491 + Node v=G.tail(f);
6.492 + if (!M[v] && flow[f] > 0 ) {
6.493 queue.push(v);
6.494 M.set(v, true);
6.495 }
6.496 @@ -485,34 +475,38 @@
6.497 template<typename _CutMap>
6.498 void maxMinCut(_CutMap& M) {
6.499
6.500 - std::queue<NodeIt> queue;
6.501 + std::queue<Node> queue;
6.502
6.503 M.set(t,true);
6.504 queue.push(t);
6.505
6.506 while (!queue.empty()) {
6.507 - NodeIt w=queue.front();
6.508 + Node w=queue.front();
6.509 queue.pop();
6.510
6.511 - for(InEdgeIt e=G.template first<InEdgeIt>(w) ; e.valid(); ++e) {
6.512 - NodeIt v=G.tail(e);
6.513 - if (!M.get(v) && flow.get(e) < capacity.get(e) ) {
6.514 +
6.515 + InEdgeIt e;
6.516 + for(G.first(e,w) ; G.valid(e); G.next(e)) {
6.517 + Node v=G.tail(e);
6.518 + if (!M[v] && flow[e] < capacity[e] ) {
6.519 queue.push(v);
6.520 M.set(v, true);
6.521 }
6.522 }
6.523 -
6.524 - for(OutEdgeIt e=G.template first<OutEdgeIt>(w) ; e.valid(); ++e) {
6.525 - NodeIt v=G.head(e);
6.526 - if (!M.get(v) && flow.get(e) > 0 ) {
6.527 +
6.528 + OutEdgeIt f;
6.529 + for(G.first(f,w) ; G.valid(f); G.next(f)) {
6.530 + Node v=G.head(f);
6.531 + if (!M[v] && flow[f] > 0 ) {
6.532 queue.push(v);
6.533 M.set(v, true);
6.534 }
6.535 }
6.536 }
6.537
6.538 - for(EachNodeIt v=G.template first<EachNodeIt>() ; v.valid(); ++v) {
6.539 - M.set(v, !M.get(v));
6.540 + NodeIt v;
6.541 + for(G.first(v) ; G.valid(v); G.next(v)) {
6.542 + M.set(v, !M[v]);
6.543 }
6.544
6.545 }
7.1 --- a/src/work/jacint/prim.cc Fri Mar 19 21:15:14 2004 +0000
7.2 +++ b/src/work/jacint/prim.cc Fri Mar 19 22:16:05 2004 +0000
7.3 @@ -1,8 +1,8 @@
7.4 #include <iostream>
7.5 #include <fstream>
7.6
7.7 -#include <list_graph.hh>
7.8 -#include <dimacs.hh>
7.9 +#include <list_graph.h>
7.10 +#include <dimacs.h>
7.11 #include <prim.h>
7.12 #include <time_measure.h>
7.13
7.14 @@ -12,17 +12,17 @@
7.15 using namespace hugo;
7.16
7.17 int main(int, char **) {
7.18 - typedef ListGraph::NodeIt NodeIt;
7.19 + typedef ListGraph::Node Node;
7.20
7.21 ListGraph G;
7.22 - NodeIt s, t;
7.23 + Node s, t;
7.24 ListGraph::EdgeMap<int> cap(G);
7.25 readDimacsMaxFlow(std::cin, G, s, t, cap);
7.26
7.27 std::cout << "prim demo ..." << std::endl;
7.28
7.29 double pre_time=currTime();
7.30 - Prim<ListGraph, int, FibHeap<ListGraph::NodeIt, int,
7.31 + Prim<ListGraph, int, FibHeap<ListGraph::Node, int,
7.32 ListGraph::NodeMap<int> > > prim_test(G, cap);
7.33 prim_test.run();
7.34 double post_time=currTime();
7.35 @@ -31,7 +31,7 @@
7.36 << post_time-pre_time << " sec"<< std::endl;
7.37
7.38 pre_time=currTime();
7.39 - Prim<ListGraph, int, BinHeap<ListGraph::NodeIt, int,
7.40 + Prim<ListGraph, int, BinHeap<ListGraph::Node, int,
7.41 ListGraph::NodeMap<int> > > prim_test2(G, cap);
7.42 prim_test2.run();
7.43 post_time=currTime();
8.1 --- a/src/work/jacint/prim.h Fri Mar 19 21:15:14 2004 +0000
8.2 +++ b/src/work/jacint/prim.h Fri Mar 19 22:16:05 2004 +0000
8.3 @@ -1,81 +1,82 @@
8.4 // -*- C++ -*-
8.5 -
8.6 -//kell hogy tree_edge invalid elekbol alljon, Szep
8.7 -//lenne ha az elejen a konstrualas ilyet adna, de
8.8 -//ugy fest nem igy lesz, ekkor invalidalni kell
8.9 -
8.10 /*
8.11 - *template <Graph, T, Heap=FibHeap>
8.12 + *template <Graph, T, Heap=FibHeap, LengthMap=Graph::EdgeMap<T> >
8.13 *
8.14 *Constructor:
8.15 *
8.16 - *Prim(Graph G, Graph::EdgeMap<T> weight, NodeIt root=[G.first()])
8.17 + *Prim(Graph G, LengthMap weight)
8.18 *
8.19 *
8.20 *Methods:
8.21 *
8.22 - *void run()
8.23 + *void run() : Runs the Prim-algorithm from a random node
8.24 *
8.25 - * The followings functions should be used after run() was already run.
8.26 + *void run(Node r) : Runs the Prim-algorithm from node s
8.27 *
8.28 - *T weight() : returns the minimum weight of a spanning tree of the
8.29 - * component of the root.
8.30 + *T weight() : After run(r) was run, it returns the minimum
8.31 + * weight of a spanning tree of the component of the root.
8.32 *
8.33 - *EdgeIt tree(NodeIt v) : returns the first edge in the path from v
8.34 - * to the root. Returns an invalid iterator if v=s or v is
8.35 - * not reachable from the root.
8.36 + *Edge tree(Node v) : After run(r) was run, it returns the
8.37 + * first edge in the path from v to the root. Returns
8.38 + * INVALID if v=r or v is not reachable from the root.
8.39 *
8.40 - *bool conn() : true iff G is connected
8.41 + *bool conn() : After run(r) was run, it is true iff G is connected
8.42 *
8.43 - *bool reach(NodeIt v) : true iff v is in the same component as the root
8.44 + *bool reached(Node v) : After run(r) was run, it is true
8.45 + * iff v is in the same component as the root
8.46 *
8.47 - *NodeIt root() : returns the root
8.48 + *Node root() : returns the root
8.49 *
8.50 */
8.51
8.52 -#ifndef PRIM_H
8.53 -#define PRIM_H
8.54 +#ifndef HUGO_PRIM_H
8.55 +#define HUGO_PRIM_H
8.56
8.57 #include <fib_heap.h>
8.58 -
8.59 -#include <iostream>
8.60 +#include <invalid.h>
8.61
8.62 namespace hugo {
8.63
8.64 template <typename Graph, typename T,
8.65 - typename Heap=FibHeap<typename Graph::NodeIt, T,
8.66 - typename Graph::NodeMap<int> > >
8.67 + typename Heap=FibHeap<typename Graph::Node, T,
8.68 + typename Graph::NodeMap<int> >,
8.69 + typename LengthMap=typename Graph::EdgeMap<T> >
8.70 class Prim{
8.71 + typedef typename Graph::Node Node;
8.72 typedef typename Graph::NodeIt NodeIt;
8.73 - typedef typename Graph::EachNodeIt EachNodeIt;
8.74 - typedef typename Graph::EdgeIt EdgeIt;
8.75 + typedef typename Graph::Edge Edge;
8.76 typedef typename Graph::OutEdgeIt OutEdgeIt;
8.77 typedef typename Graph::InEdgeIt InEdgeIt;
8.78
8.79 - Graph& G;
8.80 - NodeIt r;
8.81 - typename Graph::NodeMap<EdgeIt> tree_edge;
8.82 + const Graph& G;
8.83 + const LengthMap& edge_weight;
8.84 + typename Graph::NodeMap<Edge> tree_edge;
8.85 typename Graph::NodeMap<T> min_weight;
8.86 - typename Graph::EdgeMap<T>& edge_weight;
8.87 - typename Graph::NodeMap<bool> reached;
8.88 + typename Graph::NodeMap<bool> reach;
8.89
8.90 public :
8.91
8.92 - Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight,
8.93 - NodeIt const _r) :
8.94 - G(_G), r(_r), tree_edge(G), min_weight(G),
8.95 - edge_weight(_edge_weight), reached(G, false) { }
8.96 + Prim(Graph& _G, LengthMap& _edge_weight) :
8.97 + G(_G), edge_weight(_edge_weight),
8.98 + tree_edge(_G,INVALID), min_weight(_G), reach(_G, false) { }
8.99
8.100 - Prim(Graph& _G, typename Graph::EdgeMap<T>& _edge_weight) :
8.101 - G(_G), tree_edge(G), min_weight(G), edge_weight(_edge_weight), reached(G, false)
8.102 - {
8.103 - EachNodeIt _r; //FIXME
8.104 - G.getFirst(_r);
8.105 - r=_r;
8.106 +
8.107 + void run() {
8.108 + NodeIt _r;
8.109 + G.first(_r);
8.110 + run(_r);
8.111 }
8.112
8.113
8.114 - void run() {
8.115 + void run(Node r) {
8.116 +
8.117 + NodeIt u;
8.118 + for ( G.first(u) ; G.valid(u) ; G.next(u) ) {
8.119 + tree_edge.set(u,INVALID);
8.120 + min_weight.set(u,0);
8.121 + reach.set(u,false);
8.122 + }
8.123 +
8.124
8.125 typename Graph::NodeMap<bool> scanned(G, false);
8.126 typename Graph::NodeMap<int> heap_map(G,-1);
8.127 @@ -83,43 +84,43 @@
8.128 Heap heap(heap_map);
8.129
8.130 heap.push(r,0);
8.131 - reached.set(r, true);
8.132 + reach.set(r, true);
8.133
8.134 while ( !heap.empty() ) {
8.135
8.136 - NodeIt v=heap.top();
8.137 + Node v=heap.top();
8.138 min_weight.set(v, heap.get(v));
8.139 heap.pop();
8.140 scanned.set(v,true);
8.141
8.142 OutEdgeIt e;
8.143 - for( G.getFirst(e,v); G.valid(e); G.next(e)) {
8.144 - NodeIt w=G.head(e);
8.145 + for( G.first(e,v); G.valid(e); G.next(e)) {
8.146 + Node w=G.head(e);
8.147
8.148 - if ( !scanned.get(w) ) {
8.149 - if ( !reached.get(w) ) {
8.150 - reached.set(w,true);
8.151 - heap.push(w, edge_weight.get(e));
8.152 + if ( !scanned[w] ) {
8.153 + if ( !reach[w] ) {
8.154 + reach.set(w,true);
8.155 + heap.push(w, edge_weight[e]);
8.156 tree_edge.set(w,e);
8.157 - } else if ( edge_weight.get(e) < heap.get(w) ) {
8.158 + } else if ( edge_weight[e] < heap.get(w) ) {
8.159 tree_edge.set(w,e);
8.160 - heap.decrease(w, edge_weight.get(e));
8.161 + heap.decrease(w, edge_weight[e]);
8.162 }
8.163 }
8.164 }
8.165
8.166 InEdgeIt f;
8.167 - for( G.getFirst(f,v); G.valid(f); G.next(f)) {
8.168 - NodeIt w=G.tail(f);
8.169 + for( G.first(f,v); G.valid(f); G.next(f)) {
8.170 + Node w=G.tail(f);
8.171
8.172 - if ( !scanned.get(w) ) {
8.173 - if ( !reached.get(w) ) {
8.174 - reached.set(w,true);
8.175 - heap.push(w, edge_weight.get(f));
8.176 + if ( !scanned[w] ) {
8.177 + if ( !reach[w] ) {
8.178 + reach.set(w,true);
8.179 + heap.push(w, edge_weight[f]);
8.180 tree_edge.set(w,f);
8.181 - } else if ( edge_weight.get(f) < heap.get(w) ) {
8.182 + } else if ( edge_weight[f] < heap.get(w) ) {
8.183 tree_edge.set(w,f);
8.184 - heap.decrease(w, edge_weight.get(f));
8.185 + heap.decrease(w, edge_weight[f]);
8.186 }
8.187 }
8.188 }
8.189 @@ -129,22 +130,22 @@
8.190
8.191 T weight() {
8.192 T w=0;
8.193 - EachNodeIt u;
8.194 - for ( G.getFirst(u) ; G.valid(u) ; G.next(u) ) w+=min_weight.get(u);
8.195 + NodeIt u;
8.196 + for ( G.first(u) ; G.valid(u) ; G.next(u) ) w+=min_weight[u];
8.197 return w;
8.198 }
8.199
8.200
8.201 - EdgeIt tree(NodeIt v) {
8.202 - return tree_edge.get(v);
8.203 + Edge tree(Node v) {
8.204 + return tree_edge[v];
8.205 }
8.206
8.207
8.208 bool conn() {
8.209 bool c=true;
8.210 - EachNodeIt u;
8.211 - for ( G.getFirst(u) ; G.valid(u) ; G.next(u) )
8.212 - if ( !reached.get(u) ) {
8.213 + NodeIt u;
8.214 + for ( G.first(u) ; G.valid(u) ; G.next(u) )
8.215 + if ( !reached[u] ) {
8.216 c=false;
8.217 break;
8.218 }
8.219 @@ -152,12 +153,12 @@
8.220 }
8.221
8.222
8.223 - bool reach(NodeIt v) {
8.224 - return reached.get(v);
8.225 + bool reached(Node v) {
8.226 + return reached[v];
8.227 }
8.228
8.229
8.230 - NodeIt root() {
8.231 + Node root() {
8.232 return r;
8.233 }
8.234