1.1 --- a/src/work/jacint/dijkstra.hh Mon Feb 16 15:57:59 2004 +0000
1.2 +++ b/src/work/jacint/dijkstra.hh Mon Feb 16 16:15:58 2004 +0000
1.3 @@ -1,11 +1,11 @@
1.4 /*
1.5 *dijkstra
1.6 *by jacint
1.7 - *Performs Dijkstra's algorithm from node s.
1.8 + *Performs Dijkstra's algorithm from Node s.
1.9 *
1.10 *Constructor:
1.11 *
1.12 - *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance)
1.13 + *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance)
1.14 *
1.15 *
1.16 *
1.17 @@ -16,17 +16,17 @@
1.18 * The following function should be used after run() was already run.
1.19 *
1.20 *
1.21 - *T dist(node_iterator v) : returns the distance from s to v.
1.22 + *T dist(NodeIt v) : returns the distance from s to v.
1.23 * It is 0 if v is not reachable from s.
1.24 *
1.25 *
1.26 - *edge_iterator pred(node_iterator v)
1.27 - * Returns the last edge of a shortest s-v path.
1.28 + *EdgeIt pred(NodeIt v)
1.29 + * Returns the last Edge of a shortest s-v path.
1.30 * Returns an invalid iterator if v=s or v is not
1.31 * reachable from s.
1.32 *
1.33 *
1.34 - *bool reach(node_iterator v) : true if v is reachable from s
1.35 + *bool reach(NodeIt v) : true if v is reachable from s
1.36 *
1.37 *
1.38 *
1.39 @@ -48,7 +48,7 @@
1.40 #include <algorithm>
1.41
1.42 #include <marci_graph_traits.hh>
1.43 -#include <marci_property_vector.hh>
1.44 +#include <marciMap.hh>
1.45
1.46
1.47 namespace std {
1.48 @@ -60,37 +60,37 @@
1.49
1.50 template <typename graph_type, typename T>
1.51 class dijkstra{
1.52 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.53 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.54 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.55 - typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
1.56 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.57 + typedef typename graph_traits<graph_type>::NodeIt NodeIt;
1.58 + typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
1.59 + typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
1.60 + typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
1.61 + typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt;
1.62
1.63
1.64 graph_type& G;
1.65 - node_iterator s;
1.66 - node_property_vector<graph_type, edge_iterator> predecessor;
1.67 - node_property_vector<graph_type, T> distance;
1.68 - edge_property_vector<graph_type, T> length;
1.69 - node_property_vector<graph_type, bool> reached;
1.70 + NodeIt s;
1.71 + NodeMap<graph_type, EdgeIt> predecessor;
1.72 + NodeMap<graph_type, T> distance;
1.73 + EdgeMap<graph_type, T> length;
1.74 + NodeMap<graph_type, bool> reached;
1.75
1.76 public :
1.77
1.78 /*
1.79 - The distance of all the nodes is 0.
1.80 + The distance of all the Nodes is 0.
1.81 */
1.82 - dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) :
1.83 + dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) :
1.84 G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }
1.85
1.86
1.87
1.88 /*By Misi.*/
1.89 - struct node_dist_comp
1.90 + struct Node_dist_comp
1.91 {
1.92 - node_property_vector<graph_type, T> &d;
1.93 - node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {}
1.94 + NodeMap<graph_type, T> &d;
1.95 + Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {}
1.96
1.97 - bool operator()(const node_iterator& u, const node_iterator& v) const
1.98 + bool operator()(const NodeIt& u, const NodeIt& v) const
1.99 { return d.get(u) < d.get(v); }
1.100 };
1.101
1.102 @@ -98,23 +98,23 @@
1.103
1.104 void run() {
1.105
1.106 - node_property_vector<graph_type, bool> scanned(G, false);
1.107 - std::priority_queue<node_iterator, vector<node_iterator>, node_dist_comp>
1.108 - heap(( node_dist_comp(distance) ));
1.109 + NodeMap<graph_type, bool> scanned(G, false);
1.110 + std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp>
1.111 + heap(( Node_dist_comp(distance) ));
1.112
1.113 heap.push(s);
1.114 reached.put(s, true);
1.115
1.116 while (!heap.empty()) {
1.117
1.118 - node_iterator v=heap.top();
1.119 + NodeIt v=heap.top();
1.120 heap.pop();
1.121
1.122
1.123 if (!scanned.get(v)) {
1.124
1.125 - for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) {
1.126 - node_iterator w=G.head(e);
1.127 + for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
1.128 + NodeIt w=G.head(e);
1.129
1.130 if (!scanned.get(w)) {
1.131 if (!reached.get(w)) {
1.132 @@ -147,29 +147,29 @@
1.133
1.134
1.135 /*
1.136 - *Returns the distance of the node v.
1.137 - *It is 0 for the root and for the nodes not
1.138 + *Returns the distance of the Node v.
1.139 + *It is 0 for the root and for the Nodes not
1.140 *reachable form the root.
1.141 */
1.142 - T dist(node_iterator v) {
1.143 + T dist(NodeIt v) {
1.144 return -distance.get(v);
1.145 }
1.146
1.147
1.148
1.149 /*
1.150 - * Returns the last edge of a shortest s-v path.
1.151 + * Returns the last Edge of a shortest s-v path.
1.152 * Returns an invalid iterator if v=root or v is not
1.153 * reachable from the root.
1.154 */
1.155 - edge_iterator pred(node_iterator v) {
1.156 + EdgeIt pred(NodeIt v) {
1.157 if (v!=s) { return predecessor.get(v);}
1.158 - else {return edge_iterator();}
1.159 + else {return EdgeIt();}
1.160 }
1.161
1.162
1.163
1.164 - bool reach(node_iterator v) {
1.165 + bool reach(NodeIt v) {
1.166 return reached.get(v);
1.167 }
1.168
2.1 --- a/src/work/jacint/flow_test.cc Mon Feb 16 15:57:59 2004 +0000
2.2 +++ b/src/work/jacint/flow_test.cc Mon Feb 16 16:15:58 2004 +0000
2.3 @@ -2,150 +2,147 @@
2.4 #include <vector>
2.5 #include <string>
2.6
2.7 -#include <marci_list_graph.hh>
2.8 -#include <marci_graph_traits.hh>
2.9 -#include <marci_property_vector.hh>
2.10 -#include <preflow_push_hl.hh>
2.11 -#include <preflow_push_max_flow.hh>
2.12 -#include <reverse_bfs.hh>
2.13 -//#include <dijkstra.hh>
2.14 +#include <list_graph.hh>
2.15 +#include <preflow_push_hl.h>
2.16 +#include <preflow_push_max_flow.h>
2.17 +#include <reverse_bfs.h>
2.18 +//#include <dijkstra.h>
2.19
2.20 using namespace marci;
2.21
2.22
2.23 int main (int, char*[])
2.24 {
2.25 - typedef graph_traits<list_graph>::node_iterator node_iterator;
2.26 - typedef graph_traits<list_graph>::edge_iterator edge_iterator;
2.27 - typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
2.28 - typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
2.29 - typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
2.30 - typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
2.31 - typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
2.32 -
2.33 - list_graph flow_test;
2.34 + typedef ListGraph::NodeIt NodeIt;
2.35 + typedef ListGraph::EdgeIt EdgeIt;
2.36 + typedef ListGraph::EachNodeIt EachNodeIt;
2.37 + typedef ListGraph::EachEdgeIt EachEdgeIt;
2.38 + typedef ListGraph::OutEdgeIt OutEdgeIt;
2.39 + typedef ListGraph::InEdgeIt InEdgeIt;
2.40 +
2.41 + ListGraph flow_test;
2.42
2.43 //Ahuja könyv példája, maxflowvalue=13
2.44 - node_iterator s=flow_test.add_node();
2.45 - node_iterator v1=flow_test.add_node();
2.46 - node_iterator v2=flow_test.add_node();
2.47 - node_iterator v3=flow_test.add_node();
2.48 - node_iterator v4=flow_test.add_node();
2.49 - node_iterator v5=flow_test.add_node();
2.50 - node_iterator t=flow_test.add_node();
2.51 + NodeIt s=flow_test.addNode();
2.52 + NodeIt v1=flow_test.addNode();
2.53 + NodeIt v2=flow_test.addNode();
2.54 + NodeIt v3=flow_test.addNode();
2.55 + NodeIt v4=flow_test.addNode();
2.56 + NodeIt v5=flow_test.addNode();
2.57 + NodeIt t=flow_test.addNode();
2.58
2.59 - node_property_vector<list_graph, std::string> node_name(flow_test);
2.60 - node_name.put(s, "s");
2.61 - node_name.put(v1, "v1");
2.62 - node_name.put(v2, "v2");
2.63 - node_name.put(v3, "v3");
2.64 - node_name.put(v4, "v4");
2.65 - node_name.put(v5, "v5");
2.66 - node_name.put(t, "t");
2.67 + ListGraph::NodeMap<std::string> Node_name(flow_test);
2.68 + Node_name.set(s, "s");
2.69 + Node_name.set(v1, "v1");
2.70 + Node_name.set(v2, "v2");
2.71 + Node_name.set(v3, "v3");
2.72 + Node_name.set(v4, "v4");
2.73 + Node_name.set(v5, "v5");
2.74 + Node_name.set(t, "t");
2.75
2.76 - edge_iterator s_v1=flow_test.add_edge(s, v1);
2.77 - edge_iterator s_v2=flow_test.add_edge(s, v2);
2.78 - edge_iterator s_v3=flow_test.add_edge(s, v3);
2.79 - edge_iterator v2_v4=flow_test.add_edge(v2, v4);
2.80 - edge_iterator v2_v5=flow_test.add_edge(v2, v5);
2.81 - edge_iterator v3_v5=flow_test.add_edge(v3, v5);
2.82 - edge_iterator v4_t=flow_test.add_edge(v4, t);
2.83 - edge_iterator v5_t=flow_test.add_edge(v5, t);
2.84 - edge_iterator v2_s=flow_test.add_edge(v2, s);
2.85 + EdgeIt s_v1=flow_test.addEdge(s, v1);
2.86 + EdgeIt s_v2=flow_test.addEdge(s, v2);
2.87 + EdgeIt s_v3=flow_test.addEdge(s, v3);
2.88 + EdgeIt v2_v4=flow_test.addEdge(v2, v4);
2.89 + EdgeIt v2_v5=flow_test.addEdge(v2, v5);
2.90 + EdgeIt v3_v5=flow_test.addEdge(v3, v5);
2.91 + EdgeIt v4_t=flow_test.addEdge(v4, t);
2.92 + EdgeIt v5_t=flow_test.addEdge(v5, t);
2.93 + EdgeIt v2_s=flow_test.addEdge(v2, s);
2.94
2.95 - edge_property_vector<list_graph, int> cap(flow_test);
2.96 - cap.put(s_v1, 0);
2.97 - cap.put(s_v2, 10);
2.98 - cap.put(s_v3, 10);
2.99 - cap.put(v2_v4, 5);
2.100 - cap.put(v2_v5, 8);
2.101 - cap.put(v3_v5, 5);
2.102 - cap.put(v4_t, 8);
2.103 - cap.put(v5_t, 8);
2.104 - cap.put(v2_s, 0);
2.105 + ListGraph::EdgeMap<int> cap(flow_test);
2.106 + cap.set(s_v1, 0);
2.107 + cap.set(s_v2, 10);
2.108 + cap.set(s_v3, 10);
2.109 + cap.set(v2_v4, 5);
2.110 + cap.set(v2_v5, 8);
2.111 + cap.set(v3_v5, 5);
2.112 + cap.set(v4_t, 8);
2.113 + cap.set(v5_t, 8);
2.114 + cap.set(v2_s, 0);
2.115
2.116
2.117
2.118 //Marci példája, maxflowvalue=23
2.119 - /* node_iterator s=flow_test.add_node();
2.120 - node_iterator v1=flow_test.add_node();
2.121 - node_iterator v2=flow_test.add_node();
2.122 - node_iterator v3=flow_test.add_node();
2.123 - node_iterator v4=flow_test.add_node();
2.124 - node_iterator t=flow_test.add_node();
2.125 - node_iterator w=flow_test.add_node();
2.126 + /* NodeIt s=flow_test.addNode();
2.127 + NodeIt v1=flow_test.addNode();
2.128 + NodeIt v2=flow_test.addNode();
2.129 + NodeIt v3=flow_test.addNode();
2.130 + NodeIt v4=flow_test.addNode();
2.131 + NodeIt t=flow_test.addNode();
2.132 + NodeIt w=flow_test.addNode();
2.133
2.134
2.135 - node_property_vector<list_graph, std::string> node_name(flow_test);
2.136 - node_name.put(s, "s");
2.137 - node_name.put(v1, "v1");
2.138 - node_name.put(v2, "v2");
2.139 - node_name.put(v3, "v3");
2.140 - node_name.put(v4, "v4");
2.141 - node_name.put(t, "t");
2.142 - node_name.put(w, "w");
2.143 + NodeMap<ListGraph, std::string> Node_name(flow_test);
2.144 + Node_name.set(s, "s");
2.145 + Node_name.set(v1, "v1");
2.146 + Node_name.set(v2, "v2");
2.147 + Node_name.set(v3, "v3");
2.148 + Node_name.set(v4, "v4");
2.149 + Node_name.set(t, "t");
2.150 + Node_name.set(w, "w");
2.151
2.152 - edge_iterator s_v1=flow_test.add_edge(s, v1);
2.153 - edge_iterator s_v2=flow_test.add_edge(s, v2);
2.154 - edge_iterator v1_v2=flow_test.add_edge(v1, v2);
2.155 - edge_iterator v2_v1=flow_test.add_edge(v2, v1);
2.156 - edge_iterator v1_v3=flow_test.add_edge(v1, v3);
2.157 - edge_iterator v3_v2=flow_test.add_edge(v3, v2);
2.158 - edge_iterator v2_v4=flow_test.add_edge(v2, v4);
2.159 - edge_iterator v4_v3=flow_test.add_edge(v4, v3);
2.160 - edge_iterator v3_t=flow_test.add_edge(v3, t);
2.161 - edge_iterator v4_t=flow_test.add_edge(v4, t);
2.162 - edge_iterator v3_v3=flow_test.add_edge(v3, v3);
2.163 - edge_iterator s_w=flow_test.add_edge(s, w);
2.164 - // edge_iterator v2_s=flow_test.add_edge(v2, s);
2.165 + EdgeIt s_v1=flow_test.addEdge(s, v1);
2.166 + EdgeIt s_v2=flow_test.addEdge(s, v2);
2.167 + EdgeIt v1_v2=flow_test.addEdge(v1, v2);
2.168 + EdgeIt v2_v1=flow_test.addEdge(v2, v1);
2.169 + EdgeIt v1_v3=flow_test.addEdge(v1, v3);
2.170 + EdgeIt v3_v2=flow_test.addEdge(v3, v2);
2.171 + EdgeIt v2_v4=flow_test.addEdge(v2, v4);
2.172 + EdgeIt v4_v3=flow_test.addEdge(v4, v3);
2.173 + EdgeIt v3_t=flow_test.addEdge(v3, t);
2.174 + EdgeIt v4_t=flow_test.addEdge(v4, t);
2.175 + EdgeIt v3_v3=flow_test.addEdge(v3, v3);
2.176 + EdgeIt s_w=flow_test.addEdge(s, w);
2.177 + // EdgeIt v2_s=flow_test.addEdge(v2, s);
2.178
2.179
2.180
2.181 - edge_property_vector<list_graph, int> cap(flow_test); //serves as length in dijkstra
2.182 - cap.put(s_v1, 16);
2.183 - cap.put(s_v2, 13);
2.184 - cap.put(v1_v2, 10);
2.185 - cap.put(v2_v1, 4);
2.186 - cap.put(v1_v3, 12);
2.187 - cap.put(v3_v2, 9);
2.188 - cap.put(v2_v4, 14);
2.189 - cap.put(v4_v3, 7);
2.190 - cap.put(v3_t, 20);
2.191 - cap.put(v4_t, 4);
2.192 - cap.put(v3_v3, 4);
2.193 - cap.put(s_w, 4);
2.194 - // cap.put(v2_s, 0);
2.195 + EdgeMap<ListGraph, int> cap(flow_test); //serves as length in dijkstra
2.196 + cap.set(s_v1, 16);
2.197 + cap.set(s_v2, 13);
2.198 + cap.set(v1_v2, 10);
2.199 + cap.set(v2_v1, 4);
2.200 + cap.set(v1_v3, 12);
2.201 + cap.set(v3_v2, 9);
2.202 + cap.set(v2_v4, 14);
2.203 + cap.set(v4_v3, 7);
2.204 + cap.set(v3_t, 20);
2.205 + cap.set(v4_t, 4);
2.206 + cap.set(v3_v3, 4);
2.207 + cap.set(s_w, 4);
2.208 + // cap.set(v2_s, 0);
2.209
2.210 */
2.211
2.212 //pelda 3, maxflowvalue=4
2.213 - /* node_iterator s=flow_test.add_node();
2.214 - node_iterator v1=flow_test.add_node();
2.215 - node_iterator v2=flow_test.add_node();
2.216 - node_iterator t=flow_test.add_node();
2.217 - node_iterator w=flow_test.add_node();
2.218 + /* NodeIt s=flow_test.addNode();
2.219 + NodeIt v1=flow_test.addNode();
2.220 + NodeIt v2=flow_test.addNode();
2.221 + NodeIt t=flow_test.addNode();
2.222 + NodeIt w=flow_test.addNode();
2.223
2.224 - node_property_vector<list_graph, std::string> node_name(flow_test);
2.225 - node_name.put(s, "s");
2.226 - node_name.put(v1, "v1");
2.227 - node_name.put(v2, "v2");
2.228 - node_name.put(t, "t");
2.229 - node_name.put(w, "w");
2.230 + NodeMap<ListGraph, std::string> Node_name(flow_test);
2.231 + Node_name.set(s, "s");
2.232 + Node_name.set(v1, "v1");
2.233 + Node_name.set(v2, "v2");
2.234 + Node_name.set(t, "t");
2.235 + Node_name.set(w, "w");
2.236
2.237 - edge_iterator s_v1=flow_test.add_edge(s, v1);
2.238 - edge_iterator v1_v2=flow_test.add_edge(v1, v2);
2.239 - edge_iterator v2_t=flow_test.add_edge(v2, t);
2.240 - edge_iterator v1_v1=flow_test.add_edge(v1, v1);
2.241 - edge_iterator s_w=flow_test.add_edge(s, w);
2.242 + EdgeIt s_v1=flow_test.addEdge(s, v1);
2.243 + EdgeIt v1_v2=flow_test.addEdge(v1, v2);
2.244 + EdgeIt v2_t=flow_test.addEdge(v2, t);
2.245 + EdgeIt v1_v1=flow_test.addEdge(v1, v1);
2.246 + EdgeIt s_w=flow_test.addEdge(s, w);
2.247
2.248
2.249 - edge_property_vector<list_graph, int> cap(flow_test);
2.250 + EdgeMap<ListGraph, int> cap(flow_test);
2.251
2.252 - cap.put(s_v1, 16);
2.253 - cap.put(v1_v2, 10);
2.254 - cap.put(v2_t, 4);
2.255 - cap.put(v1_v1, 3);
2.256 - cap.put(s_w, 5);
2.257 + cap.set(s_v1, 16);
2.258 + cap.set(v1_v2, 10);
2.259 + cap.set(v2_t, 4);
2.260 + cap.set(v1_v1, 3);
2.261 + cap.set(s_w, 5);
2.262 */
2.263
2.264
2.265 @@ -153,11 +150,11 @@
2.266 /*
2.267 std::cout << "Testing reverse_bfs..." << std::endl;
2.268
2.269 - reverse_bfs<list_graph> bfs_test(flow_test, t);
2.270 + reverse_bfs<ListGraph> bfs_test(flow_test, t);
2.271
2.272 bfs_test.run();
2.273
2.274 - for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
2.275 + for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
2.276 std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
2.277 }
2.278
2.279 @@ -167,24 +164,24 @@
2.280
2.281 std::cout << "Testing preflow_push_hl..." << std::endl;
2.282
2.283 - preflow_push_hl<list_graph, int> preflow_push_test(flow_test, s, t, cap);
2.284 + preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
2.285
2.286 preflow_push_test.run();
2.287
2.288 std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
2.289
2.290 - std::cout<< "The flow on edge s-v1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl;
2.291 + std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
2.292
2.293 - edge_property_vector<list_graph, int> flow=preflow_push_test.allflow();
2.294 - for (each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) {
2.295 - std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
2.296 + ListGraph::EdgeMap<int> flow=preflow_push_test.allflow();
2.297 + for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
2.298 + std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
2.299 }
2.300
2.301 std::cout << "A minimum cut: " <<std::endl;
2.302 - node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut();
2.303 + ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
2.304
2.305 - for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
2.306 - if (mincut.get(v)) std::cout <<node_name.get(v)<< " ";
2.307 + for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
2.308 + if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
2.309 }
2.310
2.311 std::cout<<"\n\n"<<std::endl;
2.312 @@ -194,17 +191,17 @@
2.313
2.314 std::cout << "Testing preflow_push_max_flow..." << std::endl;
2.315
2.316 - preflow_push_max_flow<list_graph, int> max_flow_test(flow_test, s, t, cap);
2.317 + preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
2.318
2.319 max_flow_test.run();
2.320
2.321 std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
2.322
2.323 std::cout << "A minimum cut: " <<std::endl;
2.324 - node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut();
2.325 + ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
2.326
2.327 - for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
2.328 - if (mincut2.get(v)) std::cout <<node_name.get(v)<< " ";
2.329 + for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
2.330 + if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
2.331 }
2.332
2.333 std::cout << std::endl <<std::endl;
2.334 @@ -213,17 +210,17 @@
2.335 /*
2.336 std::cout << "Testing dijkstra..." << std::endl;
2.337
2.338 - node_iterator root=v2;
2.339 + NodeIt root=v2;
2.340
2.341 - dijkstra<list_graph, int> dijkstra_test(flow_test, root, cap);
2.342 + dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);
2.343
2.344 dijkstra_test.run();
2.345
2.346 - for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
2.347 + for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
2.348 if (dijkstra_test.reach(w)) {
2.349 std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);
2.350 if (dijkstra_test.pred(w).valid()) {
2.351 - std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl;
2.352 + std::cout <<", a shortest path from the root ends with Edge " << dijkstra_test.pred(w) <<std::endl;
2.353 } else {
2.354 std::cout <<", this is the root."<<std::endl; }
2.355
3.1 --- a/src/work/jacint/preflow_push_hl.h Mon Feb 16 15:57:59 2004 +0000
3.2 +++ b/src/work/jacint/preflow_push_hl.h Mon Feb 16 16:15:58 2004 +0000
3.3 @@ -29,11 +29,11 @@
3.4 #include <vector>
3.5 #include <stack>
3.6
3.7 -#include <reverse_bfs.hh>
3.8 +#include <reverse_bfs.h>
3.9
3.10 namespace marci {
3.11
3.12 - template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
3.13 + template <typename Graph, typename T>
3.14 class preflow_push_hl {
3.15
3.16 typedef typename Graph::NodeIt NodeIt;
3.17 @@ -47,16 +47,16 @@
3.18 Graph& G;
3.19 NodeIt s;
3.20 NodeIt t;
3.21 - Graph::EdgeMap<T> flow;
3.22 - Graph::EdgeMap<T> capacity;
3.23 + typename Graph::EdgeMap<T> flow;
3.24 + typename Graph::EdgeMap<T> capacity;
3.25 T value;
3.26 - Graph::NodeMap<bool> mincutvector;
3.27 + typename Graph::NodeMap<bool> mincutvector;
3.28
3.29
3.30 public:
3.31
3.32 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t,
3.33 - Graph::EdgeMap<T>& _capacity) :
3.34 + typename Graph::EdgeMap<T>& _capacity) :
3.35 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
3.36
3.37
3.38 @@ -68,8 +68,8 @@
3.39 */
3.40 void run() {
3.41
3.42 - Graph::NodeMap<int> level(G); //level of Node
3.43 - Graph::NodeMap<T> excess(G); //excess of Node
3.44 + typename Graph::NodeMap<int> level(G); //level of Node
3.45 + typename Graph::NodeMap<T> excess(G); //excess of Node
3.46
3.47 int n=G.nodeNum(); //number of Nodes
3.48 int b=n;
3.49 @@ -82,7 +82,7 @@
3.50
3.51 /*Reverse_bfs from t, to find the starting level.*/
3.52
3.53 - reverse_bfs<list_graph> bfs(G, t);
3.54 + reverse_bfs<Graph> bfs(G, t);
3.55 bfs.run();
3.56 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
3.57 level.set(v, bfs.dist(v));
3.58 @@ -268,7 +268,7 @@
3.59 Returns the maximum flow x found by the algorithm.
3.60 */
3.61
3.62 - EdgeMap<graph_type, T> allflow() {
3.63 + typename Graph::EdgeMap<T> allflow() {
3.64 return flow;
3.65 }
3.66
3.67 @@ -278,7 +278,7 @@
3.68 Returns a minimum cut by using a reverse bfs from t in the residual graph.
3.69 */
3.70
3.71 - NodeMap<graph_type, bool> mincut() {
3.72 + typename Graph::NodeMap<bool> mincut() {
3.73
3.74 std::queue<NodeIt> queue;
3.75
3.76 @@ -310,8 +310,6 @@
3.77 return mincutvector;
3.78
3.79 }
3.80 -
3.81 -
3.82 };
3.83 }//namespace marci
3.84 #endif
4.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
4.2 +++ b/src/work/jacint/preflow_push_max_flow.h Mon Feb 16 16:15:58 2004 +0000
4.3 @@ -0,0 +1,313 @@
4.4 +/*
4.5 +preflow_push_max_flow_h
4.6 +by jacint.
4.7 +Runs a preflow push algorithm with the modification,
4.8 +that we do not push on Nodes with level at least n.
4.9 +Moreover, if a level gets empty, we.set all Nodes above that
4.10 +level to level n. Hence, in the end, we arrive at a maximum preflow
4.11 +with value of a max flow value. An empty level gives a minimum cut.
4.12 +
4.13 +Member functions:
4.14 +
4.15 +void run() : runs the algorithm
4.16 +
4.17 + The following functions should be used after run() was already run.
4.18 +
4.19 +T maxflow() : returns the value of a maximum flow
4.20 +
4.21 +NodeMap<Graph, bool> mincut(): returns a
4.22 + characteristic vector of a minimum cut.
4.23 +*/
4.24 +
4.25 +#ifndef PREFLOW_PUSH_MAX_FLOW_H
4.26 +#define PREFLOW_PUSH_MAX_FLOW_H
4.27 +
4.28 +#include <algorithm>
4.29 +#include <vector>
4.30 +#include <stack>
4.31 +
4.32 +#include <list_graph.hh>
4.33 +#include <reverse_bfs.h>
4.34 +
4.35 +
4.36 +namespace marci {
4.37 +
4.38 + template <typename Graph, typename T>
4.39 + class preflow_push_max_flow {
4.40 +
4.41 + typedef typename Graph::NodeIt NodeIt;
4.42 + typedef typename Graph::EachNodeIt EachNodeIt;
4.43 + typedef typename Graph::OutEdgeIt OutEdgeIt;
4.44 + typedef typename Graph::InEdgeIt InEdgeIt;
4.45 +
4.46 + Graph& G;
4.47 + NodeIt s;
4.48 + NodeIt t;
4.49 + typename Graph::EdgeMap<T>& capacity;
4.50 + T value;
4.51 + typename Graph::NodeMap<bool> mincutvector;
4.52 +
4.53 +
4.54 +
4.55 + public:
4.56 +
4.57 + preflow_push_max_flow(Graph& _G, NodeIt _s, NodeIt _t, typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
4.58 +
4.59 +
4.60 + /*
4.61 + The run() function runs a modified version of the highest label preflow-push, which only
4.62 + finds a maximum preflow, hence giving the value of a maximum flow.
4.63 + */
4.64 + void run() {
4.65 +
4.66 + typename Graph::EdgeMap<T> flow(G, 0); //the flow value, 0 everywhere
4.67 + typename Graph::NodeMap<int> level(G); //level of Node
4.68 + typename Graph::NodeMap<T> excess(G); //excess of Node
4.69 +
4.70 + int n=G.nodeNum(); //number of Nodes
4.71 + int b=n-2;
4.72 + /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/
4.73 +
4.74 + std::vector<int> numb(n); //The number of Nodes on level i < n.
4.75 +
4.76 + std::vector<std::stack<NodeIt> > stack(2*n-1); //Stack of the active Nodes in level i.
4.77 +
4.78 +
4.79 +
4.80 + /*Reverse_bfs from t, to find the starting level.*/
4.81 +
4.82 + reverse_bfs<Graph> bfs(G, t);
4.83 + bfs.run();
4.84 + for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v)
4.85 + {
4.86 + int dist=bfs.dist(v);
4.87 + level.set(v, dist);
4.88 + ++numb[dist];
4.89 + }
4.90 +
4.91 + /*The level of s is fixed to n*/
4.92 + level.set(s,n);
4.93 +
4.94 +
4.95 + /* Starting flow. It is everywhere 0 at the moment. */
4.96 +
4.97 + for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i)
4.98 + {
4.99 + NodeIt w=G.head(i);
4.100 + flow.set(i, capacity.get(i));
4.101 + stack[bfs.dist(w)].push(w);
4.102 + excess.set(w, capacity.get(i));
4.103 + }
4.104 +
4.105 +
4.106 + /*
4.107 + End of preprocessing
4.108 + */
4.109 +
4.110 +
4.111 +
4.112 +
4.113 + /*
4.114 + Push/relabel on the highest level active Nodes.
4.115 + */
4.116 +
4.117 + /*While there exists an active Node.*/
4.118 + while (b) {
4.119 +
4.120 + /*We decrease the bound if there is no active Node of level b.*/
4.121 + if (stack[b].empty()) {
4.122 + --b;
4.123 + } else {
4.124 +
4.125 + NodeIt w=stack[b].top(); //w is the highest label active Node.
4.126 + stack[b].pop(); //We delete w from the stack.
4.127 +
4.128 + int newlevel=2*n-2; //In newlevel we maintain the next level of w.
4.129 +
4.130 + for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
4.131 + NodeIt v=G.head(e);
4.132 + /*e is the Edge wv.*/
4.133 +
4.134 + if (flow.get(e)<capacity.get(e)) {
4.135 + /*e is an Edge of the residual graph */
4.136 +
4.137 + if(level.get(w)==level.get(v)+1) {
4.138 + /*Push is allowed now*/
4.139 +
4.140 + if (capacity.get(e)-flow.get(e) > excess.get(w)) {
4.141 + /*A nonsaturating push.*/
4.142 +
4.143 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
4.144 + /*v becomes active.*/
4.145 +
4.146 + flow.set(e, flow.get(e)+excess.get(w));
4.147 + excess.set(v, excess.get(v)+excess.get(w));
4.148 + excess.set(w,0);
4.149 + //std::cout << w << " " << v <<" elore elen nonsat pump " << std::endl;
4.150 + break;
4.151 + } else {
4.152 + /*A saturating push.*/
4.153 +
4.154 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
4.155 + /*v becomes active.*/
4.156 +
4.157 + excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
4.158 + excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
4.159 + flow.set(e, capacity.get(e));
4.160 + //std::cout << w <<" " << v <<" elore elen sat pump " << std::endl;
4.161 + if (excess.get(w)==0) break;
4.162 + /*If w is not active any more, then we go on to the next Node.*/
4.163 +
4.164 + } // if (capacity.get(e)-flow.get(e) > excess.get(w))
4.165 + } // if (level.get(w)==level.get(v)+1)
4.166 +
4.167 + else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
4.168 +
4.169 + } //if (flow.get(e)<capacity.get(e))
4.170 +
4.171 + } //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e)
4.172 +
4.173 +
4.174 +
4.175 + for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
4.176 + NodeIt v=G.tail(e);
4.177 + /*e is the Edge vw.*/
4.178 +
4.179 + if (excess.get(w)==0) break;
4.180 + /*It may happen, that w became inactive in the first 'for' cycle.*/
4.181 +
4.182 + if(flow.get(e)>0) {
4.183 + /*e is an Edge of the residual graph */
4.184 +
4.185 + if(level.get(w)==level.get(v)+1) {
4.186 + /*Push is allowed now*/
4.187 +
4.188 + if (flow.get(e) > excess.get(w)) {
4.189 + /*A nonsaturating push.*/
4.190 +
4.191 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
4.192 + /*v becomes active.*/
4.193 +
4.194 + flow.set(e, flow.get(e)-excess.get(w));
4.195 + excess.set(v, excess.get(v)+excess.get(w));
4.196 + excess.set(w,0);
4.197 + //std::cout << v << " " << w << " vissza elen nonsat pump " << std::endl;
4.198 + break;
4.199 + } else {
4.200 + /*A saturating push.*/
4.201 +
4.202 + if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v);
4.203 + /*v becomes active.*/
4.204 +
4.205 + flow.set(e,0);
4.206 + excess.set(v, excess.get(v)+flow.get(e));
4.207 + excess.set(w, excess.get(w)-flow.get(e));
4.208 + //std::cout << v <<" " << w << " vissza elen sat pump " << std::endl;
4.209 + if (excess.get(w)==0) { break;}
4.210 + } //if (flow.get(e) > excess.get(v))
4.211 + } //if(level.get(w)==level.get(v)+1)
4.212 +
4.213 + else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
4.214 + //std::cout << "Leveldecrease of Node " << w << " to " << newlevel << std::endl;
4.215 +
4.216 + } //if (flow.get(e)>0)
4.217 +
4.218 + } //for in-Edge
4.219 +
4.220 +
4.221 +
4.222 +
4.223 + /*
4.224 + Relabel
4.225 + */
4.226 + if (excess.get(w)>0) {
4.227 + /*Now newlevel <= n*/
4.228 +
4.229 + int l=level.get(w); //l is the old level of w.
4.230 + --numb[l];
4.231 +
4.232 + if (newlevel == n) {
4.233 + level.set(w,n);
4.234 +
4.235 + } else {
4.236 +
4.237 + if (numb[l]) {
4.238 + /*If the level of w remains nonempty.*/
4.239 +
4.240 + level.set(w,++newlevel);
4.241 + ++numb[newlevel];
4.242 + stack[newlevel].push(w);
4.243 + b=newlevel;
4.244 + } else {
4.245 + /*If the level of w gets empty.*/
4.246 +
4.247 + for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
4.248 + if (level.get(v) >= l ) {
4.249 + level.set(v,n);
4.250 + }
4.251 + }
4.252 +
4.253 + for (int i=l+1 ; i!=n ; ++i) numb[i]=0;
4.254 + } //if (numb[l])
4.255 +
4.256 + } // if (newlevel = n)
4.257 +
4.258 + } // if (excess.get(w)>0)
4.259 +
4.260 +
4.261 + } //else
4.262 +
4.263 + } //while(b)
4.264 +
4.265 + value=excess.get(t);
4.266 + /*Max flow value.*/
4.267 +
4.268 +
4.269 +
4.270 + /*
4.271 + We find an empty level, e. The Nodes above this level give
4.272 + a minimum cut.
4.273 + */
4.274 +
4.275 + int e=1;
4.276 +
4.277 + while(e) {
4.278 + if(numb[e]) ++e;
4.279 + else break;
4.280 + }
4.281 + for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
4.282 + if (level.get(v) > e) mincutvector.set(v, true);
4.283 + }
4.284 +
4.285 +
4.286 + } // void run()
4.287 +
4.288 +
4.289 +
4.290 + /*
4.291 + Returns the maximum value of a flow.
4.292 + */
4.293 +
4.294 + T maxflow() {
4.295 + return value;
4.296 + }
4.297 +
4.298 +
4.299 +
4.300 + /*
4.301 + Returns a minimum cut.
4.302 + */
4.303 +
4.304 + typename Graph::NodeMap<bool> mincut() {
4.305 + return mincutvector;
4.306 + }
4.307 +
4.308 +
4.309 + };
4.310 +}//namespace marci
4.311 +#endif
4.312 +
4.313 +
4.314 +
4.315 +
4.316 +
5.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
5.2 +++ b/src/work/jacint/reverse_bfs.h Mon Feb 16 16:15:58 2004 +0000
5.3 @@ -0,0 +1,89 @@
5.4 +/*
5.5 +reverse_bfs
5.6 +by jacint
5.7 +Performs a bfs on the out Edges. It does not count predecessors,
5.8 +only the distances, but one can easily modify it to know the pred as well.
5.9 +
5.10 +Constructor:
5.11 +
5.12 +reverse_bfs(Graph& G, NodeIt t)
5.13 +
5.14 +
5.15 +
5.16 +Member functions:
5.17 +
5.18 +void run(): runs a reverse bfs from t
5.19 +
5.20 + The following function should be used after run() was already run.
5.21 +
5.22 +int dist(NodeIt v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
5.23 +
5.24 +*/
5.25 +#ifndef REVERSE_BFS_H
5.26 +#define REVERSE_BFS_H
5.27 +
5.28 +#include <queue>
5.29 +#include <list_graph.hh>
5.30 +
5.31 +
5.32 +namespace marci {
5.33 +
5.34 + template <typename Graph>
5.35 + class reverse_bfs {
5.36 + typedef typename Graph::NodeIt NodeIt;
5.37 + typedef typename Graph::EachNodeIt EachNodeIt;
5.38 + typedef typename Graph::InEdgeIt InEdgeIt;
5.39 +
5.40 +
5.41 + Graph& G;
5.42 + NodeIt t;
5.43 + typename Graph::NodeMap<int> distance;
5.44 +
5.45 +
5.46 + public :
5.47 +
5.48 + /*
5.49 + The distance of the Nodes is n, except t for which it is 0.
5.50 + */
5.51 + reverse_bfs(Graph& _G, NodeIt _t) : G(_G), t(_t), distance(G, G.nodeNum()) {
5.52 + distance.set(t,0);
5.53 + }
5.54 +
5.55 + void run() {
5.56 +
5.57 + typename Graph::NodeMap<bool> reached(G, false);
5.58 + reached.set(t, true);
5.59 +
5.60 + std::queue<NodeIt> bfs_queue;
5.61 + bfs_queue.push(t);
5.62 +
5.63 + while (!bfs_queue.empty()) {
5.64 +
5.65 + NodeIt v=bfs_queue.front();
5.66 + bfs_queue.pop();
5.67 +
5.68 + for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
5.69 + NodeIt w=G.tail(e);
5.70 + if (!reached.get(w)) {
5.71 + bfs_queue.push(w);
5.72 + distance.set(w, distance.get(v)+1);
5.73 + reached.set(w, true);
5.74 + }
5.75 + }
5.76 + }
5.77 + }
5.78 +
5.79 +
5.80 +
5.81 + int dist(NodeIt v) {
5.82 + return distance.get(v);
5.83 + }
5.84 +
5.85 +
5.86 + };
5.87 +
5.88 +} // namespace marci
5.89 +
5.90 +#endif //REVERSE_BFS_HH
5.91 +
5.92 +
6.1 --- a/src/work/jacint/reverse_bfs.hh Mon Feb 16 15:57:59 2004 +0000
6.2 +++ b/src/work/jacint/reverse_bfs.hh Mon Feb 16 16:15:58 2004 +0000
6.3 @@ -1,12 +1,12 @@
6.4 /*
6.5 reverse_bfs
6.6 by jacint
6.7 -Performs a bfs on the out edges. It does not count predecessors,
6.8 +Performs a bfs on the out Edges. It does not count predecessors,
6.9 only the distances, but one can easily modify it to know the pred as well.
6.10
6.11 Constructor:
6.12
6.13 -reverse_bfs(graph_type& G, node_iterator t)
6.14 +reverse_bfs(graph_type& G, NodeIt t)
6.15
6.16
6.17
6.18 @@ -16,7 +16,7 @@
6.19
6.20 The following function should be used after run() was already run.
6.21
6.22 -int dist(node_iterator v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
6.23 +int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v.
6.24
6.25 */
6.26 #ifndef REVERSE_BFS_HH
6.27 @@ -25,7 +25,7 @@
6.28 #include <queue>
6.29
6.30 #include <marci_graph_traits.hh>
6.31 -#include <marci_property_vector.hh>
6.32 +#include <marciMap.hh>
6.33
6.34
6.35
6.36 @@ -33,42 +33,42 @@
6.37
6.38 template <typename graph_type>
6.39 class reverse_bfs {
6.40 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
6.41 - //typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
6.42 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
6.43 - typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
6.44 + typedef typename graph_traits<graph_type>::NodeIt NodeIt;
6.45 + //typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
6.46 + typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
6.47 + typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
6.48
6.49
6.50 graph_type& G;
6.51 - node_iterator t;
6.52 -// node_property_vector<graph_type, edge_iterator> pred;
6.53 - node_property_vector<graph_type, int> distance;
6.54 + NodeIt t;
6.55 +// NodeMap<graph_type, EdgeIt> pred;
6.56 + NodeMap<graph_type, int> distance;
6.57
6.58
6.59 public :
6.60
6.61 /*
6.62 - The distance of the nodes is n, except t for which it is 0.
6.63 + The distance of the Nodes is n, except t for which it is 0.
6.64 */
6.65 - reverse_bfs(graph_type& _G, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) {
6.66 + reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) {
6.67 distance.put(t,0);
6.68 }
6.69
6.70 void run() {
6.71
6.72 - node_property_vector<graph_type, bool> reached(G, false);
6.73 + NodeMap<graph_type, bool> reached(G, false);
6.74 reached.put(t, true);
6.75
6.76 - std::queue<node_iterator> bfs_queue;
6.77 + std::queue<NodeIt> bfs_queue;
6.78 bfs_queue.push(t);
6.79
6.80 while (!bfs_queue.empty()) {
6.81
6.82 - node_iterator v=bfs_queue.front();
6.83 + NodeIt v=bfs_queue.front();
6.84 bfs_queue.pop();
6.85
6.86 - for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {
6.87 - node_iterator w=G.tail(e);
6.88 + for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
6.89 + NodeIt w=G.tail(e);
6.90 if (!reached.get(w)) {
6.91 bfs_queue.push(w);
6.92 distance.put(w, distance.get(v)+1);
6.93 @@ -80,7 +80,7 @@
6.94
6.95
6.96
6.97 - int dist(node_iterator v) {
6.98 + int dist(NodeIt v) {
6.99 return distance.get(v);
6.100 }
6.101