Changeset 78:ecc1171307be in lemon0.x
 Timestamp:
 02/16/04 17:15:58 (18 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@101
 Location:
 src/work/jacint
 Files:

 2 added
 4 edited
Legend:
 Unmodified
 Added
 Removed

src/work/jacint/dijkstra.hh
r50 r78 2 2 *dijkstra 3 3 *by jacint 4 *Performs Dijkstra's algorithm from node s.4 *Performs Dijkstra's algorithm from Node s. 5 5 * 6 6 *Constructor: 7 7 * 8 *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance)8 *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance) 9 9 * 10 10 * … … 17 17 * 18 18 * 19 *T dist( node_iteratorv) : returns the distance from s to v.19 *T dist(NodeIt v) : returns the distance from s to v. 20 20 * It is 0 if v is not reachable from s. 21 21 * 22 22 * 23 * edge_iterator pred(node_iteratorv)24 * Returns the last edge of a shortest sv path.23 *EdgeIt pred(NodeIt v) 24 * Returns the last Edge of a shortest sv path. 25 25 * Returns an invalid iterator if v=s or v is not 26 26 * reachable from s. 27 27 * 28 28 * 29 *bool reach( node_iteratorv) : true if v is reachable from s29 *bool reach(NodeIt v) : true if v is reachable from s 30 30 * 31 31 * … … 49 49 50 50 #include <marci_graph_traits.hh> 51 #include <marci _property_vector.hh>51 #include <marciMap.hh> 52 52 53 53 … … 61 61 template <typename graph_type, typename T> 62 62 class dijkstra{ 63 typedef typename graph_traits<graph_type>:: node_iterator node_iterator;64 typedef typename graph_traits<graph_type>:: edge_iterator edge_iterator;65 typedef typename graph_traits<graph_type>:: each_node_iterator each_node_iterator;66 typedef typename graph_traits<graph_type>:: in_edge_iterator in_edge_iterator;67 typedef typename graph_traits<graph_type>:: out_edge_iterator out_edge_iterator;63 typedef typename graph_traits<graph_type>::NodeIt NodeIt; 64 typedef typename graph_traits<graph_type>::EdgeIt EdgeIt; 65 typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt; 66 typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt; 67 typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt; 68 68 69 69 70 70 graph_type& G; 71 node_iterators;72 node_property_vector<graph_type, edge_iterator> predecessor;73 node_property_vector<graph_type, T> distance;74 edge_property_vector<graph_type, T> length;75 node_property_vector<graph_type, bool> reached;71 NodeIt s; 72 NodeMap<graph_type, EdgeIt> predecessor; 73 NodeMap<graph_type, T> distance; 74 EdgeMap<graph_type, T> length; 75 NodeMap<graph_type, bool> reached; 76 76 77 77 public : 78 78 79 79 /* 80 The distance of all the nodes is 0.80 The distance of all the Nodes is 0. 81 81 */ 82 dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) :82 dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) : 83 83 G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { } 84 84 … … 86 86 87 87 /*By Misi.*/ 88 struct node_dist_comp88 struct Node_dist_comp 89 89 { 90 node_property_vector<graph_type, T> &d;91 node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {}90 NodeMap<graph_type, T> &d; 91 Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 92 92 93 bool operator()(const node_iterator& u, const node_iterator& v) const93 bool operator()(const NodeIt& u, const NodeIt& v) const 94 94 { return d.get(u) < d.get(v); } 95 95 }; … … 99 99 void run() { 100 100 101 node_property_vector<graph_type, bool> scanned(G, false);102 std::priority_queue< node_iterator, vector<node_iterator>, node_dist_comp>103 heap(( node_dist_comp(distance) ));101 NodeMap<graph_type, bool> scanned(G, false); 102 std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> 103 heap(( Node_dist_comp(distance) )); 104 104 105 105 heap.push(s); … … 108 108 while (!heap.empty()) { 109 109 110 node_iteratorv=heap.top();110 NodeIt v=heap.top(); 111 111 heap.pop(); 112 112 … … 114 114 if (!scanned.get(v)) { 115 115 116 for( out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) {117 node_iteratorw=G.head(e);116 for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) { 117 NodeIt w=G.head(e); 118 118 119 119 if (!scanned.get(w)) { … … 148 148 149 149 /* 150 *Returns the distance of the node v.151 *It is 0 for the root and for the nodes not150 *Returns the distance of the Node v. 151 *It is 0 for the root and for the Nodes not 152 152 *reachable form the root. 153 153 */ 154 T dist( node_iteratorv) {154 T dist(NodeIt v) { 155 155 return distance.get(v); 156 156 } … … 159 159 160 160 /* 161 * Returns the last edge of a shortest sv path.161 * Returns the last Edge of a shortest sv path. 162 162 * Returns an invalid iterator if v=root or v is not 163 163 * reachable from the root. 164 164 */ 165 edge_iterator pred(node_iteratorv) {165 EdgeIt pred(NodeIt v) { 166 166 if (v!=s) { return predecessor.get(v);} 167 else {return edge_iterator();}167 else {return EdgeIt();} 168 168 } 169 169 170 170 171 171 172 bool reach( node_iteratorv) {172 bool reach(NodeIt v) { 173 173 return reached.get(v); 174 174 } 
src/work/jacint/flow_test.cc
r72 r78 3 3 #include <string> 4 4 5 #include <marci_list_graph.hh> 6 #include <marci_graph_traits.hh> 7 #include <marci_property_vector.hh> 8 #include <preflow_push_hl.hh> 9 #include <preflow_push_max_flow.hh> 10 #include <reverse_bfs.hh> 11 //#include <dijkstra.hh> 5 #include <list_graph.hh> 6 #include <preflow_push_hl.h> 7 #include <preflow_push_max_flow.h> 8 #include <reverse_bfs.h> 9 //#include <dijkstra.h> 12 10 13 11 using namespace marci; … … 16 14 int main (int, char*[]) 17 15 { 18 typedef graph_traits<list_graph>::node_iterator node_iterator; 19 typedef graph_traits<list_graph>::edge_iterator edge_iterator; 20 typedef graph_traits<list_graph>::each_node_iterator each_node_iterator; 21 typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator; 22 typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator; 23 typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator; 24 typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator; 25 26 list_graph flow_test; 16 typedef ListGraph::NodeIt NodeIt; 17 typedef ListGraph::EdgeIt EdgeIt; 18 typedef ListGraph::EachNodeIt EachNodeIt; 19 typedef ListGraph::EachEdgeIt EachEdgeIt; 20 typedef ListGraph::OutEdgeIt OutEdgeIt; 21 typedef ListGraph::InEdgeIt InEdgeIt; 22 23 ListGraph flow_test; 27 24 28 25 //Ahuja könyv példája, maxflowvalue=13 29 node_iterator s=flow_test.add_node();30 node_iterator v1=flow_test.add_node();31 node_iterator v2=flow_test.add_node();32 node_iterator v3=flow_test.add_node();33 node_iterator v4=flow_test.add_node();34 node_iterator v5=flow_test.add_node();35 node_iterator t=flow_test.add_node();36 37 node_property_vector<list_graph, std::string> node_name(flow_test);38 node_name.put(s, "s");39 node_name.put(v1, "v1");40 node_name.put(v2, "v2");41 node_name.put(v3, "v3");42 node_name.put(v4, "v4");43 node_name.put(v5, "v5");44 node_name.put(t, "t");45 46 edge_iterator s_v1=flow_test.add_edge(s, v1);47 edge_iterator s_v2=flow_test.add_edge(s, v2);48 edge_iterator s_v3=flow_test.add_edge(s, v3);49 edge_iterator v2_v4=flow_test.add_edge(v2, v4);50 edge_iterator v2_v5=flow_test.add_edge(v2, v5);51 edge_iterator v3_v5=flow_test.add_edge(v3, v5);52 edge_iterator v4_t=flow_test.add_edge(v4, t);53 edge_iterator v5_t=flow_test.add_edge(v5, t);54 edge_iterator v2_s=flow_test.add_edge(v2, s);55 56 edge_property_vector<list_graph,int> cap(flow_test);57 cap. put(s_v1, 0);58 cap. put(s_v2, 10);59 cap. put(s_v3, 10);60 cap. put(v2_v4, 5);61 cap. put(v2_v5, 8);62 cap. put(v3_v5, 5);63 cap. put(v4_t, 8);64 cap. put(v5_t, 8);65 cap. put(v2_s, 0);26 NodeIt s=flow_test.addNode(); 27 NodeIt v1=flow_test.addNode(); 28 NodeIt v2=flow_test.addNode(); 29 NodeIt v3=flow_test.addNode(); 30 NodeIt v4=flow_test.addNode(); 31 NodeIt v5=flow_test.addNode(); 32 NodeIt t=flow_test.addNode(); 33 34 ListGraph::NodeMap<std::string> Node_name(flow_test); 35 Node_name.set(s, "s"); 36 Node_name.set(v1, "v1"); 37 Node_name.set(v2, "v2"); 38 Node_name.set(v3, "v3"); 39 Node_name.set(v4, "v4"); 40 Node_name.set(v5, "v5"); 41 Node_name.set(t, "t"); 42 43 EdgeIt s_v1=flow_test.addEdge(s, v1); 44 EdgeIt s_v2=flow_test.addEdge(s, v2); 45 EdgeIt s_v3=flow_test.addEdge(s, v3); 46 EdgeIt v2_v4=flow_test.addEdge(v2, v4); 47 EdgeIt v2_v5=flow_test.addEdge(v2, v5); 48 EdgeIt v3_v5=flow_test.addEdge(v3, v5); 49 EdgeIt v4_t=flow_test.addEdge(v4, t); 50 EdgeIt v5_t=flow_test.addEdge(v5, t); 51 EdgeIt v2_s=flow_test.addEdge(v2, s); 52 53 ListGraph::EdgeMap<int> cap(flow_test); 54 cap.set(s_v1, 0); 55 cap.set(s_v2, 10); 56 cap.set(s_v3, 10); 57 cap.set(v2_v4, 5); 58 cap.set(v2_v5, 8); 59 cap.set(v3_v5, 5); 60 cap.set(v4_t, 8); 61 cap.set(v5_t, 8); 62 cap.set(v2_s, 0); 66 63 67 64 68 65 69 66 //Marci példája, maxflowvalue=23 70 /* node_iterator s=flow_test.add_node();71 node_iterator v1=flow_test.add_node();72 node_iterator v2=flow_test.add_node();73 node_iterator v3=flow_test.add_node();74 node_iterator v4=flow_test.add_node();75 node_iterator t=flow_test.add_node();76 node_iterator w=flow_test.add_node();77 78 79 node_property_vector<list_graph, std::string> node_name(flow_test);80 node_name.put(s, "s");81 node_name.put(v1, "v1");82 node_name.put(v2, "v2");83 node_name.put(v3, "v3");84 node_name.put(v4, "v4");85 node_name.put(t, "t");86 node_name.put(w, "w");87 88 edge_iterator s_v1=flow_test.add_edge(s, v1);89 edge_iterator s_v2=flow_test.add_edge(s, v2);90 edge_iterator v1_v2=flow_test.add_edge(v1, v2);91 edge_iterator v2_v1=flow_test.add_edge(v2, v1);92 edge_iterator v1_v3=flow_test.add_edge(v1, v3);93 edge_iterator v3_v2=flow_test.add_edge(v3, v2);94 edge_iterator v2_v4=flow_test.add_edge(v2, v4);95 edge_iterator v4_v3=flow_test.add_edge(v4, v3);96 edge_iterator v3_t=flow_test.add_edge(v3, t);97 edge_iterator v4_t=flow_test.add_edge(v4, t);98 edge_iterator v3_v3=flow_test.add_edge(v3, v3);99 edge_iterator s_w=flow_test.add_edge(s, w);100 // edge_iterator v2_s=flow_test.add_edge(v2, s);101 102 103 104 edge_property_vector<list_graph, int> cap(flow_test); //serves as length in dijkstra105 cap. put(s_v1, 16);106 cap. put(s_v2, 13);107 cap. put(v1_v2, 10);108 cap. put(v2_v1, 4);109 cap. put(v1_v3, 12);110 cap. put(v3_v2, 9);111 cap. put(v2_v4, 14);112 cap. put(v4_v3, 7);113 cap. put(v3_t, 20);114 cap. put(v4_t, 4);115 cap. put(v3_v3, 4);116 cap. put(s_w, 4);117 // cap. put(v2_s, 0);67 /* NodeIt s=flow_test.addNode(); 68 NodeIt v1=flow_test.addNode(); 69 NodeIt v2=flow_test.addNode(); 70 NodeIt v3=flow_test.addNode(); 71 NodeIt v4=flow_test.addNode(); 72 NodeIt t=flow_test.addNode(); 73 NodeIt w=flow_test.addNode(); 74 75 76 NodeMap<ListGraph, std::string> Node_name(flow_test); 77 Node_name.set(s, "s"); 78 Node_name.set(v1, "v1"); 79 Node_name.set(v2, "v2"); 80 Node_name.set(v3, "v3"); 81 Node_name.set(v4, "v4"); 82 Node_name.set(t, "t"); 83 Node_name.set(w, "w"); 84 85 EdgeIt s_v1=flow_test.addEdge(s, v1); 86 EdgeIt s_v2=flow_test.addEdge(s, v2); 87 EdgeIt v1_v2=flow_test.addEdge(v1, v2); 88 EdgeIt v2_v1=flow_test.addEdge(v2, v1); 89 EdgeIt v1_v3=flow_test.addEdge(v1, v3); 90 EdgeIt v3_v2=flow_test.addEdge(v3, v2); 91 EdgeIt v2_v4=flow_test.addEdge(v2, v4); 92 EdgeIt v4_v3=flow_test.addEdge(v4, v3); 93 EdgeIt v3_t=flow_test.addEdge(v3, t); 94 EdgeIt v4_t=flow_test.addEdge(v4, t); 95 EdgeIt v3_v3=flow_test.addEdge(v3, v3); 96 EdgeIt s_w=flow_test.addEdge(s, w); 97 // EdgeIt v2_s=flow_test.addEdge(v2, s); 98 99 100 101 EdgeMap<ListGraph, int> cap(flow_test); //serves as length in dijkstra 102 cap.set(s_v1, 16); 103 cap.set(s_v2, 13); 104 cap.set(v1_v2, 10); 105 cap.set(v2_v1, 4); 106 cap.set(v1_v3, 12); 107 cap.set(v3_v2, 9); 108 cap.set(v2_v4, 14); 109 cap.set(v4_v3, 7); 110 cap.set(v3_t, 20); 111 cap.set(v4_t, 4); 112 cap.set(v3_v3, 4); 113 cap.set(s_w, 4); 114 // cap.set(v2_s, 0); 118 115 119 116 */ 120 117 121 118 //pelda 3, maxflowvalue=4 122 /* node_iterator s=flow_test.add_node();123 node_iterator v1=flow_test.add_node();124 node_iterator v2=flow_test.add_node();125 node_iterator t=flow_test.add_node();126 node_iterator w=flow_test.add_node();127 128 node_property_vector<list_graph, std::string> node_name(flow_test);129 node_name.put(s, "s");130 node_name.put(v1, "v1");131 node_name.put(v2, "v2");132 node_name.put(t, "t");133 node_name.put(w, "w");134 135 edge_iterator s_v1=flow_test.add_edge(s, v1);136 edge_iterator v1_v2=flow_test.add_edge(v1, v2);137 edge_iterator v2_t=flow_test.add_edge(v2, t);138 edge_iterator v1_v1=flow_test.add_edge(v1, v1);139 edge_iterator s_w=flow_test.add_edge(s, w);140 141 142 edge_property_vector<list_graph, int> cap(flow_test);119 /* NodeIt s=flow_test.addNode(); 120 NodeIt v1=flow_test.addNode(); 121 NodeIt v2=flow_test.addNode(); 122 NodeIt t=flow_test.addNode(); 123 NodeIt w=flow_test.addNode(); 124 125 NodeMap<ListGraph, std::string> Node_name(flow_test); 126 Node_name.set(s, "s"); 127 Node_name.set(v1, "v1"); 128 Node_name.set(v2, "v2"); 129 Node_name.set(t, "t"); 130 Node_name.set(w, "w"); 131 132 EdgeIt s_v1=flow_test.addEdge(s, v1); 133 EdgeIt v1_v2=flow_test.addEdge(v1, v2); 134 EdgeIt v2_t=flow_test.addEdge(v2, t); 135 EdgeIt v1_v1=flow_test.addEdge(v1, v1); 136 EdgeIt s_w=flow_test.addEdge(s, w); 137 138 139 EdgeMap<ListGraph, int> cap(flow_test); 143 140 144 cap. put(s_v1, 16);145 cap. put(v1_v2, 10);146 cap. put(v2_t, 4);147 cap. put(v1_v1, 3);148 cap. put(s_w, 5);141 cap.set(s_v1, 16); 142 cap.set(v1_v2, 10); 143 cap.set(v2_t, 4); 144 cap.set(v1_v1, 3); 145 cap.set(s_w, 5); 149 146 */ 150 147 … … 154 151 std::cout << "Testing reverse_bfs..." << std::endl; 155 152 156 reverse_bfs< list_graph> bfs_test(flow_test, t);153 reverse_bfs<ListGraph> bfs_test(flow_test, t); 157 154 158 155 bfs_test.run(); 159 156 160 for ( each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {157 for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) { 161 158 std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl; 162 159 } … … 168 165 std::cout << "Testing preflow_push_hl..." << std::endl; 169 166 170 preflow_push_hl< list_graph, int> preflow_push_test(flow_test, s, t, cap);167 preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap); 171 168 172 169 preflow_push_test.run(); … … 174 171 std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl; 175 172 176 std::cout<< "The flow on edge sv1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl;177 178 edge_property_vector<list_graph,int> flow=preflow_push_test.allflow();179 for ( each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) {180 std::cout <<"Flow on edge " << flow_test.tail(e) <<"" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;173 std::cout<< "The flow on Edge sv1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl; 174 175 ListGraph::EdgeMap<int> flow=preflow_push_test.allflow(); 176 for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) { 177 std::cout <<"Flow on Edge " << flow_test.tail(e) <<"" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl; 181 178 } 182 179 183 180 std::cout << "A minimum cut: " <<std::endl; 184 node_property_vector<list_graph,bool> mincut=preflow_push_test.mincut();185 186 for ( each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {187 if (mincut.get(v)) std::cout << node_name.get(v)<< " ";181 ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut(); 182 183 for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) { 184 if (mincut.get(v)) std::cout <<Node_name.get(v)<< " "; 188 185 } 189 186 … … 195 192 std::cout << "Testing preflow_push_max_flow..." << std::endl; 196 193 197 preflow_push_max_flow< list_graph, int> max_flow_test(flow_test, s, t, cap);194 preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap); 198 195 199 196 max_flow_test.run(); … … 202 199 203 200 std::cout << "A minimum cut: " <<std::endl; 204 node_property_vector<list_graph,bool> mincut2=max_flow_test.mincut();205 206 for ( each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {207 if (mincut2.get(v)) std::cout << node_name.get(v)<< " ";201 ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut(); 202 203 for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) { 204 if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " "; 208 205 } 209 206 … … 214 211 std::cout << "Testing dijkstra..." << std::endl; 215 212 216 node_iteratorroot=v2;217 218 dijkstra< list_graph, int> dijkstra_test(flow_test, root, cap);213 NodeIt root=v2; 214 215 dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap); 219 216 220 217 dijkstra_test.run(); 221 218 222 for ( each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {219 for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) { 223 220 if (dijkstra_test.reach(w)) { 224 221 std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w); 225 222 if (dijkstra_test.pred(w).valid()) { 226 std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl;223 std::cout <<", a shortest path from the root ends with Edge " << dijkstra_test.pred(w) <<std::endl; 227 224 } else { 228 225 std::cout <<", this is the root."<<std::endl; } 
src/work/jacint/preflow_push_hl.h
r72 r78 30 30 #include <stack> 31 31 32 #include <reverse_bfs.h h>32 #include <reverse_bfs.h> 33 33 34 34 namespace marci { 35 35 36 template <typename Graph, typename T , typename FlowMap, typename CapacityMap>36 template <typename Graph, typename T> 37 37 class preflow_push_hl { 38 38 … … 48 48 NodeIt s; 49 49 NodeIt t; 50 Graph::EdgeMap<T> flow;51 Graph::EdgeMap<T> capacity;50 typename Graph::EdgeMap<T> flow; 51 typename Graph::EdgeMap<T> capacity; 52 52 T value; 53 Graph::NodeMap<bool> mincutvector;53 typename Graph::NodeMap<bool> mincutvector; 54 54 55 55 … … 57 57 58 58 preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, 59 Graph::EdgeMap<T>& _capacity) :59 typename Graph::EdgeMap<T>& _capacity) : 60 60 G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { } 61 61 … … 69 69 void run() { 70 70 71 Graph::NodeMap<int> level(G); //level of Node72 Graph::NodeMap<T> excess(G); //excess of Node71 typename Graph::NodeMap<int> level(G); //level of Node 72 typename Graph::NodeMap<T> excess(G); //excess of Node 73 73 74 74 int n=G.nodeNum(); //number of Nodes … … 83 83 /*Reverse_bfs from t, to find the starting level.*/ 84 84 85 reverse_bfs< list_graph> bfs(G, t);85 reverse_bfs<Graph> bfs(G, t); 86 86 bfs.run(); 87 87 for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) { … … 269 269 */ 270 270 271 EdgeMap<graph_type,T> allflow() {271 typename Graph::EdgeMap<T> allflow() { 272 272 return flow; 273 273 } … … 279 279 */ 280 280 281 NodeMap<graph_type,bool> mincut() {281 typename Graph::NodeMap<bool> mincut() { 282 282 283 283 std::queue<NodeIt> queue; … … 311 311 312 312 } 313 314 315 313 }; 316 314 }//namespace marci 
src/work/jacint/reverse_bfs.hh
r50 r78 2 2 reverse_bfs 3 3 by jacint 4 Performs a bfs on the out edges. It does not count predecessors,4 Performs a bfs on the out Edges. It does not count predecessors, 5 5 only the distances, but one can easily modify it to know the pred as well. 6 6 7 7 Constructor: 8 8 9 reverse_bfs(graph_type& G, node_iteratort)9 reverse_bfs(graph_type& G, NodeIt t) 10 10 11 11 … … 17 17 The following function should be used after run() was already run. 18 18 19 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.19 int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v. 20 20 21 21 */ … … 26 26 27 27 #include <marci_graph_traits.hh> 28 #include <marci _property_vector.hh>28 #include <marciMap.hh> 29 29 30 30 … … 34 34 template <typename graph_type> 35 35 class reverse_bfs { 36 typedef typename graph_traits<graph_type>:: node_iterator node_iterator;37 //typedef typename graph_traits<graph_type>:: edge_iterator edge_iterator;38 typedef typename graph_traits<graph_type>:: each_node_iterator each_node_iterator;39 typedef typename graph_traits<graph_type>:: in_edge_iterator in_edge_iterator;36 typedef typename graph_traits<graph_type>::NodeIt NodeIt; 37 //typedef typename graph_traits<graph_type>::EdgeIt EdgeIt; 38 typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt; 39 typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt; 40 40 41 41 42 42 graph_type& G; 43 node_iteratort;44 // node_property_vector<graph_type, edge_iterator> pred;45 node_property_vector<graph_type, int> distance;43 NodeIt t; 44 // NodeMap<graph_type, EdgeIt> pred; 45 NodeMap<graph_type, int> distance; 46 46 47 47 … … 49 49 50 50 /* 51 The distance of the nodes is n, except t for which it is 0.51 The distance of the Nodes is n, except t for which it is 0. 52 52 */ 53 reverse_bfs(graph_type& _G, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) {53 reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) { 54 54 distance.put(t,0); 55 55 } … … 57 57 void run() { 58 58 59 node_property_vector<graph_type, bool> reached(G, false);59 NodeMap<graph_type, bool> reached(G, false); 60 60 reached.put(t, true); 61 61 62 std::queue< node_iterator> bfs_queue;62 std::queue<NodeIt> bfs_queue; 63 63 bfs_queue.push(t); 64 64 65 65 while (!bfs_queue.empty()) { 66 66 67 node_iteratorv=bfs_queue.front();67 NodeIt v=bfs_queue.front(); 68 68 bfs_queue.pop(); 69 69 70 for( in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {71 node_iteratorw=G.tail(e);70 for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) { 71 NodeIt w=G.tail(e); 72 72 if (!reached.get(w)) { 73 73 bfs_queue.push(w); … … 81 81 82 82 83 int dist( node_iteratorv) {83 int dist(NodeIt v) { 84 84 return distance.get(v); 85 85 }
Note: See TracChangeset
for help on using the changeset viewer.