Changeset 19:3151a1026db9 in lemon-0.x for src
- Timestamp:
- 01/20/04 18:39:13 (21 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@32
- Location:
- src/work
- Files:
-
- 7 edited
Legend:
- Unmodified
- Added
- Removed
-
src/work/marci_bfs.hh
r11 r19 4 4 #include <queue> 5 5 6 #include <marci_graph_traits.hh>7 6 #include <marci_property_vector.hh> 8 7 … … 11 10 template <typename graph_type> 12 11 struct bfs { 13 typedef typename graph_traits<graph_type>::node_iterator node_iterator; 14 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; 15 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; 16 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; 17 12 typedef typename graph_type::node_iterator node_iterator; 13 typedef typename graph_type::edge_iterator edge_iterator; 14 typedef typename graph_type::each_node_iterator each_node_iterator; 15 typedef typename graph_type::out_edge_iterator out_edge_iterator; 18 16 graph_type& G; 19 17 node_iterator s; … … 24 22 bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) { 25 23 bfs_queue.push(s); 26 for(each_node_iterator i=G.first_node(); i. is_valid(); ++i)24 for(each_node_iterator i=G.first_node(); i.valid(); ++i) 27 25 reached.put(i, false); 28 26 reached.put(s, true); … … 35 33 out_edge_iterator e=G.first_out_edge(v); 36 34 bfs_queue.pop(); 37 for( ; e. is_valid(); ++e) {35 for( ; e.valid(); ++e) { 38 36 node_iterator w=G.head(e); 39 37 std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl; … … 54 52 template <typename graph_type> 55 53 struct bfs_visitor { 56 typedef typename graph_traits<graph_type>::node_iterator node_iterator; 57 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; 58 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; 59 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; 54 typedef typename graph_type::node_iterator node_iterator; 55 typedef typename graph_type::edge_iterator edge_iterator; 56 typedef typename graph_type::out_edge_iterator out_edge_iterator; 60 57 graph_type& G; 61 58 bfs_visitor(graph_type& _G) : G(_G) { } … … 74 71 template <typename graph_type, typename reached_type, typename visitor_type> 75 72 struct bfs_iterator { 76 typedef typename graph_traits<graph_type>::node_iterator node_iterator; 77 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; 78 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; 79 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; 80 73 typedef typename graph_type::node_iterator node_iterator; 74 typedef typename graph_type::edge_iterator edge_iterator; 75 typedef typename graph_type::out_edge_iterator out_edge_iterator; 81 76 graph_type& G; 82 77 std::queue<out_edge_iterator>& bfs_queue; … … 84 79 visitor_type& visitor; 85 80 void process() { 86 while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }81 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 87 82 if (bfs_queue.empty()) return; 88 83 out_edge_iterator e=bfs_queue.front(); … … 98 93 } 99 94 bfs_iterator(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached, visitor_type& _visitor) : G(_G), bfs_queue(_bfs_queue), reached(_reached), visitor(_visitor) { 100 //while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }101 is_valid();95 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 96 valid(); 102 97 } 103 98 bfs_iterator<graph_type, reached_type, visitor_type>& operator++() { 104 //while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }99 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 105 100 //if (bfs_queue.empty()) return *this; 106 if (! is_valid()) return *this;101 if (!valid()) return *this; 107 102 ++(bfs_queue.front()); 108 //while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }109 is_valid();103 //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 104 valid(); 110 105 return *this; 111 106 } 112 107 //void next() { 113 // while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }108 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 114 109 // if (bfs_queue.empty()) return; 115 110 // ++(bfs_queue.front()); 116 // while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }111 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 117 112 //} 118 bool is_valid() {119 while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }113 bool valid() { 114 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 120 115 if (bfs_queue.empty()) return false; else return true; 121 116 } 122 117 //bool finished() { 123 // while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }118 // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 124 119 // if (bfs_queue.empty()) return true; else return false; 125 120 //} … … 130 125 template <typename graph_type, typename reached_type> 131 126 struct bfs_iterator1 { 132 typedef typename graph_traits<graph_type>::node_iterator node_iterator; 133 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; 134 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; 135 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; 136 127 typedef typename graph_type::node_iterator node_iterator; 128 typedef typename graph_type::edge_iterator edge_iterator; 129 typedef typename graph_type::out_edge_iterator out_edge_iterator; 137 130 graph_type& G; 138 131 std::queue<out_edge_iterator>& bfs_queue; 139 132 reached_type& reached; 140 bool newly_reached;133 bool _newly_reached; 141 134 bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) { 142 is_valid();143 if (!bfs_queue.empty() && bfs_queue.front(). is_valid()) {135 valid(); 136 if (!bfs_queue.empty() && bfs_queue.front().valid()) { 144 137 out_edge_iterator e=bfs_queue.front(); 145 138 node_iterator w=G.head(e); … … 147 140 bfs_queue.push(G.first_out_edge(w)); 148 141 reached.put(w, true); 149 newly_reached=true;142 _newly_reached=true; 150 143 } else { 151 newly_reached=false;144 _newly_reached=false; 152 145 } 153 146 } 154 147 } 155 148 bfs_iterator1<graph_type, reached_type>& operator++() { 156 if (! is_valid()) return *this;149 if (!valid()) return *this; 157 150 ++(bfs_queue.front()); 158 is_valid();159 if (!bfs_queue.empty() && bfs_queue.front(). is_valid()) {151 valid(); 152 if (!bfs_queue.empty() && bfs_queue.front().valid()) { 160 153 out_edge_iterator e=bfs_queue.front(); 161 154 node_iterator w=G.head(e); … … 163 156 bfs_queue.push(G.first_out_edge(w)); 164 157 reached.put(w, true); 165 newly_reached=true;158 _newly_reached=true; 166 159 } else { 167 newly_reached=false;160 _newly_reached=false; 168 161 } 169 162 } 170 163 return *this; 171 164 } 172 bool is_valid() {173 while ( !bfs_queue.empty() && !bfs_queue.front(). is_valid() ) { bfs_queue.pop(); }165 bool valid() { 166 while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); } 174 167 if (bfs_queue.empty()) return false; else return true; 175 168 } 176 169 operator edge_iterator () { return bfs_queue.front(); } 177 bool is_newly_reached() { returnnewly_reached; }170 bool newly_reached() { return _newly_reached; } 178 171 179 172 }; -
src/work/marci_graph_concept.txt
r15 r19 17 17 marci_bfs.hh //bfs, tejesen kiserleti 18 18 marci_graph_demo.cc //peldaprogi a lisas graf hasznalatahoz 19 marci_graph_traits.hh //alapertelmezett graph_traits20 19 marci_list_graph.hh //list_graph megvalositas 21 20 marci_max_flow.hh //folyam, kiserleti … … 132 131 node_iterator metodusai: 133 132 node_iterator(); 134 bool is_valid();133 bool valid(); 135 134 void make_invalid(); 136 135 ezek nem tagfuggvenyek: … … 145 144 edge_iterator metodusai: 146 145 edge_iterator(); 147 bool is_valid();146 bool valid(); 148 147 void make_invalid(); 149 148 ezek nem tagfvek: … … 193 192 194 193 node_property_vector(graph_type&); 195 void put(graph_t raits<graph_type>::node_iterator, const T&);196 T get(graph_t raits<graph_type>::node_iterator);194 void put(graph_type::node_iterator, const T&); 195 T get(graph_type::node_iterator); 197 196 198 197 Ugyanez edge_property_array-okkal … … 202 201 203 202 edge_property_vector(graph_type&); 204 void put(graph_t raits<graph_type>::edge_iterator, const T&);205 get(graph_t raits<graph_type>::edge_iterator);203 void put(graph_type::edge_iterator, const T&); 204 get(graph_type::edge_iterator); 206 205 207 206 Ennyi nem javasolas utan, meg nehany szo. -
src/work/marci_graph_demo.cc
r12 r19 4 4 5 5 #include <marci_list_graph.hh> 6 #include <marci_graph_traits.hh>7 6 #include <marci_property_vector.hh> 8 7 #include <marci_bfs.hh> … … 13 12 int main (int, char*[]) 14 13 { 15 typedef graph_traits<list_graph>::node_iterator node_iterator; 16 typedef graph_traits<list_graph>::edge_iterator edge_iterator; 17 typedef graph_traits<list_graph>::each_node_iterator each_node_iterator; 18 typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator; 19 typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator; 20 typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator; 21 typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator; 22 14 typedef list_graph::node_iterator node_iterator; 15 typedef list_graph::edge_iterator edge_iterator; 16 typedef list_graph::each_node_iterator each_node_iterator; 17 typedef list_graph::each_edge_iterator each_edge_iterator; 18 typedef list_graph::out_edge_iterator out_edge_iterator; 19 typedef list_graph::in_edge_iterator in_edge_iterator; 20 typedef list_graph::sym_edge_iterator sym_edge_iterator; 23 21 list_graph G; 24 22 std::vector<node_iterator> vector_of_node_iterators; … … 32 30 std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl; 33 31 34 for(each_node_iterator i=G.first_node(); i. is_valid(); ++i) {32 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { 35 33 std::cout << "node " << G.id(i) << std::endl; 36 34 std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " "; 37 for(out_edge_iterator j=G.first_out_edge(i); j. is_valid(); ++j) {35 for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { 38 36 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") "; 39 37 } … … 41 39 42 40 std::cout<< " "; 43 for(out_edge_iterator j=G.first_out_edge(i); j. is_valid(); ++j) {41 for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) { 44 42 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } 45 43 std::cout<<std::endl; 46 44 47 45 std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " "; 48 for(in_edge_iterator j=G.first_in_edge(i); j. is_valid(); ++j) {46 for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { 49 47 std::cout << j << " "; } 50 48 std::cout << std::endl; 51 49 52 50 std::cout<< " "; 53 for(in_edge_iterator j=G.first_in_edge(i); j. is_valid(); ++j) {51 for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { 54 52 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } 55 53 std::cout<<std::endl; 56 54 57 55 std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " "; 58 for(sym_edge_iterator j=G.first_sym_edge(i); j. is_valid(); ++j) {56 for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { 59 57 std::cout << j << " "; } 60 58 std::cout<<std::endl; 61 59 62 60 std::cout<< " "; 63 for(sym_edge_iterator j=G.first_sym_edge(i); j. is_valid(); ++j) {61 for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) { 64 62 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; } 65 63 std::cout<<std::endl; … … 67 65 68 66 std::cout << "all edges: "; 69 for(each_edge_iterator i=G.first_edge(); i. is_valid(); ++i) {67 for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) { 70 68 std::cout << i << " "; 71 69 } … … 83 81 my_property_vector.put(vector_of_node_iterators[7], 1978); 84 82 std::cout << "some node property values..." << std::endl; 85 for(each_node_iterator i=G.first_node(); i. is_valid(); ++i) {83 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { 86 84 std::cout << my_property_vector.get(i) << std::endl; 87 85 } … … 89 87 int _ii=1; 90 88 edge_property_vector<list_graph, int> my_edge_property(G); 91 for(each_edge_iterator i=G.first_edge(); i. is_valid(); ++i) {89 for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) { 92 90 my_edge_property.put(i, _i); 93 91 _i*=_ii; ++_ii; … … 95 93 96 94 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl; 97 for(each_edge_iterator j=G.first_edge(); j. is_valid(); ++j) {95 for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) { 98 96 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " "; 99 97 } … … 102 100 //std::cout << "the same for inedges of the nodes..." << std::endl; 103 101 //k=0; 104 //for(each_node_iterator i=G.first_node(); i. is_valid(); ++i) {105 // for(in_edge_iterator j=G.first_in_edge(i); j. is_valid(); ++j) {102 //for(each_node_iterator i=G.first_node(); i.valid(); ++i) { 103 // for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) { 106 104 // std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " "; 107 105 // } … … 113 111 bfs_test.run(); 114 112 std::cout << "reached: "; 115 for(each_node_iterator i=G.first_node(); i. is_valid(); ++i) {113 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { 116 114 std::cout << bfs_test.reached.get(i) << " "; 117 115 } 118 116 std::cout<<std::endl; 119 117 std::cout << "dist: "; 120 for(each_node_iterator i=G.first_node(); i. is_valid(); ++i) {118 for(each_node_iterator i=G.first_node(); i.valid(); ++i) { 121 119 std::cout << bfs_test.dist.get(i) << " "; 122 120 } … … 168 166 std::cout << "on directed graph graph" << std::endl; //<< flow_test; 169 167 std::cout << "names and capacity values" << std::endl; 170 for(each_node_iterator i=flow_test.first_node(); i. is_valid(); ++i) {168 for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { 171 169 std::cout << node_name.get(i) << ": "; 172 170 std::cout << "out edges: "; 173 for(out_edge_iterator j=flow_test.first_out_edge(i); j. is_valid(); ++j)171 for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j) 174 172 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; 175 173 std::cout << "in edges: "; 176 for(in_edge_iterator j=flow_test.first_in_edge(i); j. is_valid(); ++j)174 for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j) 177 175 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " "; 178 176 std::cout << std::endl; … … 180 178 181 179 182 //for(each_node_iterator i=flow_test.first_node(); i. is_valid(); ++i) {180 //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) { 183 181 // std::cout << i << " "; 184 182 //} -
src/work/marci_list_graph.hh
r16 r19 20 20 int node_id; 21 21 int edge_id; 22 int _node_num; 23 int _edge_num; 22 24 23 25 node_item* _first_node; … … 81 83 _last_node=p; 82 84 if (!_first_node) _first_node=p; 85 ++_node_num; 83 86 return p; 84 87 } … … 99 102 _head->_last_in_edge=e; 100 103 if (!_head->_first_in_edge) { _head->_first_in_edge=e; } 104 ++_edge_num; 101 105 return e; 102 106 } … … 106 110 /* default constructor */ 107 111 108 list_graph() : node_id(0), edge_id(0), _first_node(0), _last_node(0) { } 109 112 list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { } 113 114 int node_num() { return _node_num; } 115 int edge_num() { return _edge_num; } 116 110 117 /* functions to construct iterators from the graph, or from each other */ 111 118 … … 210 217 node_iterator() : node(0) { } 211 218 node_iterator(node_item* _node) : node(_node) { } 212 bool is_valid() { return (node!=0); }219 bool valid() { return (node!=0); } 213 220 void make_invalid() { node=0; } 214 221 friend bool operator==(const node_iterator& u, const node_iterator& v) { … … 240 247 edge_iterator() : edge(0) { } 241 248 edge_iterator(edge_item* _edge) : edge(_edge) { } 242 bool is_valid() { return (edge!=0); }249 bool valid() { return (edge!=0); } 243 250 void make_invalid() { edge=0; } 244 251 friend bool operator==(const edge_iterator& u, const edge_iterator& v) { -
src/work/marci_makefile
r9 r19 1 C CFLAGS = -Wall -ansi2 C C = /opt/experimental/bin/g++1 CXXFLAGS = -Wall -ansi -I. 2 CXX = g++-3.0 3 3 4 marci_graph_demo: marci_graph_demo.cc marci_ graph_traits.hh marci_list_graph.hh marci_property_vector.hh marci_bfs.hh marci_max_flow.hh5 $(C C) $(CCFLAGS) -I.marci_graph_demo.cc -o marci_graph_demo4 marci_graph_demo: marci_graph_demo.cc marci_list_graph.hh marci_property_vector.hh marci_bfs.hh marci_max_flow.hh 5 $(CXX) $(CXXFLAGS) marci_graph_demo.cc -o marci_graph_demo -
src/work/marci_max_flow.hh
r17 r19 4 4 #include <algorithm> 5 5 6 #include <marci_graph_traits.hh>7 6 #include <marci_property_vector.hh> 8 7 #include <marci_bfs.hh> … … 12 11 template<typename graph_type, typename T> 13 12 class res_graph_type { 14 typedef typename graph_traits<graph_type>::node_iterator node_iterator; 15 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; 16 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; 17 typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator; 18 13 typedef typename graph_type::node_iterator node_iterator; 14 typedef typename graph_type::each_node_iterator each_node_iterator; 15 typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator; 19 16 graph_type& G; 20 17 edge_property_vector<graph_type, T>& flow; … … 23 20 res_graph_type(graph_type& _G, edge_property_vector<graph_type, T>& _flow, edge_property_vector<graph_type, T>& _capacity) : G(_G), flow(_flow), capacity(_capacity) { } 24 21 25 class res_edge_it{22 class edge_iterator { 26 23 friend class res_graph_type<graph_type, T>; 27 24 protected: 28 25 res_graph_type<graph_type, T>* resG; 29 sym_edge_iterator sym;26 old_sym_edge_iterator sym; 30 27 public: 31 res_edge_it() { }28 edge_iterator() { } 32 29 //bool is_free() { 33 30 //if (resG->G.a_node(sym)==resG->G.tail(sym)) { … … 44 41 } 45 42 } 46 bool is_valid() { return sym.is_valid(); }43 bool valid() { return sym.valid(); } 47 44 void make_invalid() { sym.make_invalid(); } 48 45 void augment(T a) { … … 55 52 }; 56 53 57 class res_out_edge_it : public res_edge_it{54 class out_edge_iterator : public edge_iterator { 58 55 public: 59 res_out_edge_it() { }60 res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {56 out_edge_iterator() { } 57 out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) { 61 58 resG=&_resG; 62 59 sym=resG->G.first_sym_edge(v); 63 while( sym. is_valid() && !(free()>0) ) { ++sym; }60 while( sym.valid() && !(free()>0) ) { ++sym; } 64 61 } 65 res_out_edge_it& operator++() {62 out_edge_iterator& operator++() { 66 63 ++sym; 67 while( sym. is_valid() && !(free()>0) ) { ++sym; }64 while( sym.valid() && !(free()>0) ) { ++sym; } 68 65 return *this; 69 66 } 70 67 }; 71 68 72 res_out_edge_itfirst_out_edge(const node_iterator& v) {73 return res_out_edge_it(*this, v);69 out_edge_iterator first_out_edge(const node_iterator& v) { 70 return out_edge_iterator(*this, v); 74 71 } 75 72 … … 78 75 } 79 76 80 node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }81 node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }77 node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); } 78 node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); } 82 79 83 80 int id(const node_iterator& v) { return G.id(v); } 84 81 85 82 //node_iterator invalid_node() { return G.invalid_node(); } 86 //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } 87 88 }; 89 90 template <typename graph_type, typename T> 91 struct graph_traits< res_graph_type<graph_type, T> > { 92 typedef typename graph_traits<graph_type>::node_iterator node_iterator; 93 typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator; 94 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; 95 typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator; 83 //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; } 96 84 }; 97 85 98 86 template <typename graph_type, typename T> 99 87 struct max_flow_type { 100 101 typedef typename graph_traits<graph_type>::node_iterator node_iterator; 102 typedef typename graph_traits<graph_type>::edge_iterator edge_iterator; 103 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator; 104 typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator; 105 typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator; 106 88 typedef typename graph_type::node_iterator node_iterator; 89 typedef typename graph_type::edge_iterator edge_iterator; 90 typedef typename graph_type::each_node_iterator each_node_iterator; 91 typedef typename graph_type::out_edge_iterator out_edge_iterator; 92 typedef typename graph_type::in_edge_iterator in_edge_iterator; 107 93 graph_type& G; 108 94 node_iterator s; … … 112 98 113 99 max_flow_type(graph_type& _G, node_iterator _s, node_iterator _t, edge_property_vector<graph_type, T>& _capacity) : G(_G), s(_s), t(_t), flow(_G), capacity(_capacity) { 114 for(each_node_iterator i=G.first_node(); i. is_valid(); ++i)115 for(out_edge_iterator j=G.first_out_edge(i); j. is_valid(); ++j)100 for(each_node_iterator i=G.first_node(); i.valid(); ++i) 101 for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) 116 102 flow.put(j, 0); 117 103 } … … 124 110 augment=false; 125 111 126 typedef std::queue< graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;112 typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type; 127 113 bfs_queue_type bfs_queue; 128 114 bfs_queue.push(res_graph.first_out_edge(s)); … … 135 121 res_bfs(res_graph, bfs_queue, reached); 136 122 137 typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;123 typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type; 138 124 pred_type pred(res_graph); 139 graph_traits<aug_graph_type>::edge_iterator a;125 aug_graph_type::edge_iterator a; 140 126 a.make_invalid(); 141 127 pred.put(s, a); … … 145 131 146 132 //searching for augmenting path 147 while ( res_bfs. is_valid() ) {133 while ( res_bfs.valid() ) { 148 134 //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl; 149 if (res_bfs. is_newly_reached()) {150 graph_traits<aug_graph_type>::edge_iterator e;135 if (res_bfs.newly_reached()) { 136 aug_graph_type::edge_iterator e; 151 137 e=res_bfs; 152 138 node_iterator v=res_graph.tail(e); … … 154 140 //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached"; 155 141 pred.put(w, e); 156 if (pred.get(v). is_valid()) {142 if (pred.get(v).valid()) { 157 143 free.put(w, std::min(free.get(v), e.free())); 158 144 //std::cout <<" nem elso csucs: "; … … 174 160 T augment_value=free.get(t); 175 161 std::cout<<"augmentation: "; 176 while (pred.get(n). is_valid()) {177 graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);162 while (pred.get(n).valid()) { 163 aug_graph_type::edge_iterator e=pred.get(n); 178 164 e.augment(augment_value); 179 165 std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") "; … … 184 170 185 171 std::cout << "actual flow: "<< std::endl; 186 for( graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {172 for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) { 187 173 std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") "; 188 174 } -
src/work/marci_property_vector.hh
r9 r19 3 3 4 4 #include <vector> 5 6 #include <marci_graph_traits.hh>7 5 8 6 namespace marci { … … 11 9 int number_of(iterator _it) { 12 10 int i=0; 13 for( ; _it. is_valid(); ++_it) { ++i; }11 for( ; _it.valid(); ++_it) { ++i; } 14 12 return i; 15 13 } … … 17 15 template <typename graph_type, typename T> 18 16 class node_property_vector { 19 typedef typename graph_traits<graph_type>::node_iterator node_iterator;20 typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;17 typedef typename list_graph::node_iterator node_iterator; 18 typedef typename list_graph::each_node_iterator each_node_iterator; 21 19 graph_type& G; 22 20 std::vector<T> container; … … 24 22 node_property_vector(graph_type& _G) : G(_G) { 25 23 int i=0; 26 for(each_node_iterator it=G.first_node(); it. is_valid(); ++it) ++i;24 for(each_node_iterator it=G.first_node(); it.valid(); ++it) ++i; 27 25 container.resize(i); 28 26 } 29 27 node_property_vector(graph_type& _G, T a) : G(_G) { 30 for(each_node_iterator it=G.first_node(); it. is_valid(); ++it) { container.push_back(a); }28 for(each_node_iterator it=G.first_node(); it.valid(); ++it) { container.push_back(a); } 31 29 } 32 30 void put(node_iterator nit, const T& a) { container[G.id(nit)]=a; } … … 36 34 template <typename graph_type, typename T> 37 35 class edge_property_vector { 38 typedef typename graph_t raits<graph_type>::edge_iterator edge_iterator;39 typedef typename graph_t raits<graph_type>::each_edge_iterator each_edge_iterator;36 typedef typename graph_type::edge_iterator edge_iterator; 37 typedef typename graph_type::each_edge_iterator each_edge_iterator; 40 38 graph_type& G; 41 39 std::vector<T> container; … … 43 41 edge_property_vector(graph_type& _G) : G(_G) { 44 42 int i=0; 45 for(each_edge_iterator it=G.first_edge(); it. is_valid(); ++it) ++i;43 for(each_edge_iterator it=G.first_edge(); it.valid(); ++it) ++i; 46 44 container.resize(i); 47 45 } 48 46 edge_property_vector(graph_type& _G, T a) : G(_G) { 49 for(each_edge_iterator it=G.first_edge(); it. is_valid(); ++it) {47 for(each_edge_iterator it=G.first_edge(); it.valid(); ++it) { 50 48 container.push_back(a); 51 49 }
Note: See TracChangeset
for help on using the changeset viewer.