1.1 --- a/src/work/marci_bfs.hh Tue Jan 20 11:21:42 2004 +0000
1.2 +++ b/src/work/marci_bfs.hh Tue Jan 20 17:39:13 2004 +0000
1.3 @@ -3,18 +3,16 @@
1.4
1.5 #include <queue>
1.6
1.7 -#include <marci_graph_traits.hh>
1.8 #include <marci_property_vector.hh>
1.9
1.10 namespace marci {
1.11
1.12 template <typename graph_type>
1.13 struct bfs {
1.14 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.15 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.16 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.17 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.18 -
1.19 + typedef typename graph_type::node_iterator node_iterator;
1.20 + typedef typename graph_type::edge_iterator edge_iterator;
1.21 + typedef typename graph_type::each_node_iterator each_node_iterator;
1.22 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
1.23 graph_type& G;
1.24 node_iterator s;
1.25 node_property_vector<graph_type, bool> reached;
1.26 @@ -23,7 +21,7 @@
1.27 std::queue<node_iterator> bfs_queue;
1.28 bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
1.29 bfs_queue.push(s);
1.30 - for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
1.31 + for(each_node_iterator i=G.first_node(); i.valid(); ++i)
1.32 reached.put(i, false);
1.33 reached.put(s, true);
1.34 dist.put(s, 0);
1.35 @@ -34,7 +32,7 @@
1.36 node_iterator v=bfs_queue.front();
1.37 out_edge_iterator e=G.first_out_edge(v);
1.38 bfs_queue.pop();
1.39 - for( ; e.is_valid(); ++e) {
1.40 + for( ; e.valid(); ++e) {
1.41 node_iterator w=G.head(e);
1.42 std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
1.43 if (!reached.get(w)) {
1.44 @@ -53,10 +51,9 @@
1.45
1.46 template <typename graph_type>
1.47 struct bfs_visitor {
1.48 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.49 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.50 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.51 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.52 + typedef typename graph_type::node_iterator node_iterator;
1.53 + typedef typename graph_type::edge_iterator edge_iterator;
1.54 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
1.55 graph_type& G;
1.56 bfs_visitor(graph_type& _G) : G(_G) { }
1.57 void at_previously_reached(out_edge_iterator& e) {
1.58 @@ -73,17 +70,15 @@
1.59
1.60 template <typename graph_type, typename reached_type, typename visitor_type>
1.61 struct bfs_iterator {
1.62 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.63 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.64 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.65 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.66 -
1.67 + typedef typename graph_type::node_iterator node_iterator;
1.68 + typedef typename graph_type::edge_iterator edge_iterator;
1.69 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
1.70 graph_type& G;
1.71 std::queue<out_edge_iterator>& bfs_queue;
1.72 reached_type& reached;
1.73 visitor_type& visitor;
1.74 void process() {
1.75 - while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.76 + while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.77 if (bfs_queue.empty()) return;
1.78 out_edge_iterator e=bfs_queue.front();
1.79 //node_iterator v=G.tail(e);
1.80 @@ -97,30 +92,30 @@
1.81 }
1.82 }
1.83 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) {
1.84 - //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.85 - is_valid();
1.86 + //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.87 + valid();
1.88 }
1.89 bfs_iterator<graph_type, reached_type, visitor_type>& operator++() {
1.90 - //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.91 + //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.92 //if (bfs_queue.empty()) return *this;
1.93 - if (!is_valid()) return *this;
1.94 + if (!valid()) return *this;
1.95 ++(bfs_queue.front());
1.96 - //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.97 - is_valid();
1.98 + //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.99 + valid();
1.100 return *this;
1.101 }
1.102 //void next() {
1.103 - // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.104 + // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.105 // if (bfs_queue.empty()) return;
1.106 // ++(bfs_queue.front());
1.107 - // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.108 + // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.109 //}
1.110 - bool is_valid() {
1.111 - while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.112 + bool valid() {
1.113 + while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.114 if (bfs_queue.empty()) return false; else return true;
1.115 }
1.116 //bool finished() {
1.117 - // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.118 + // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.119 // if (bfs_queue.empty()) return true; else return false;
1.120 //}
1.121 operator edge_iterator () { return bfs_queue.front(); }
1.122 @@ -129,52 +124,50 @@
1.123
1.124 template <typename graph_type, typename reached_type>
1.125 struct bfs_iterator1 {
1.126 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
1.127 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
1.128 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
1.129 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
1.130 -
1.131 + typedef typename graph_type::node_iterator node_iterator;
1.132 + typedef typename graph_type::edge_iterator edge_iterator;
1.133 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
1.134 graph_type& G;
1.135 std::queue<out_edge_iterator>& bfs_queue;
1.136 reached_type& reached;
1.137 - bool newly_reached;
1.138 + bool _newly_reached;
1.139 bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
1.140 - is_valid();
1.141 - if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {
1.142 + valid();
1.143 + if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.144 out_edge_iterator e=bfs_queue.front();
1.145 node_iterator w=G.head(e);
1.146 if (!reached.get(w)) {
1.147 bfs_queue.push(G.first_out_edge(w));
1.148 reached.put(w, true);
1.149 - newly_reached=true;
1.150 + _newly_reached=true;
1.151 } else {
1.152 - newly_reached=false;
1.153 + _newly_reached=false;
1.154 }
1.155 }
1.156 }
1.157 bfs_iterator1<graph_type, reached_type>& operator++() {
1.158 - if (!is_valid()) return *this;
1.159 + if (!valid()) return *this;
1.160 ++(bfs_queue.front());
1.161 - is_valid();
1.162 - if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {
1.163 + valid();
1.164 + if (!bfs_queue.empty() && bfs_queue.front().valid()) {
1.165 out_edge_iterator e=bfs_queue.front();
1.166 node_iterator w=G.head(e);
1.167 if (!reached.get(w)) {
1.168 bfs_queue.push(G.first_out_edge(w));
1.169 reached.put(w, true);
1.170 - newly_reached=true;
1.171 + _newly_reached=true;
1.172 } else {
1.173 - newly_reached=false;
1.174 + _newly_reached=false;
1.175 }
1.176 }
1.177 return *this;
1.178 }
1.179 - bool is_valid() {
1.180 - while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
1.181 + bool valid() {
1.182 + while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
1.183 if (bfs_queue.empty()) return false; else return true;
1.184 }
1.185 operator edge_iterator () { return bfs_queue.front(); }
1.186 - bool is_newly_reached() { return newly_reached; }
1.187 + bool newly_reached() { return _newly_reached; }
1.188
1.189 };
1.190
2.1 --- a/src/work/marci_graph_concept.txt Tue Jan 20 11:21:42 2004 +0000
2.2 +++ b/src/work/marci_graph_concept.txt Tue Jan 20 17:39:13 2004 +0000
2.3 @@ -16,7 +16,6 @@
2.4
2.5 marci_bfs.hh //bfs, tejesen kiserleti
2.6 marci_graph_demo.cc //peldaprogi a lisas graf hasznalatahoz
2.7 -marci_graph_traits.hh //alapertelmezett graph_traits
2.8 marci_list_graph.hh //list_graph megvalositas
2.9 marci_max_flow.hh //folyam, kiserleti
2.10 marci_property_vector.hh //property vector megvalosites indexelt grafokhoz
2.11 @@ -131,7 +130,7 @@
2.12
2.13 node_iterator metodusai:
2.14 node_iterator();
2.15 -bool is_valid();
2.16 +bool valid();
2.17 void make_invalid();
2.18 ezek nem tagfuggvenyek:
2.19 friend bool operator==(const node_iterator&, const node_iterator&);
2.20 @@ -144,7 +143,7 @@
2.21
2.22 edge_iterator metodusai:
2.23 edge_iterator();
2.24 -bool is_valid();
2.25 +bool valid();
2.26 void make_invalid();
2.27 ezek nem tagfvek:
2.28 friend bool operator==(const edge_iterator&, const edge_iterator&);
2.29 @@ -192,8 +191,8 @@
2.30 metodusok:
2.31
2.32 node_property_vector(graph_type&);
2.33 -void put(graph_traits<graph_type>::node_iterator, const T&);
2.34 -T get(graph_traits<graph_type>::node_iterator);
2.35 +void put(graph_type::node_iterator, const T&);
2.36 +T get(graph_type::node_iterator);
2.37
2.38 Ugyanez edge_property_array-okkal
2.39
2.40 @@ -201,8 +200,8 @@
2.41 class edge_property_vector;
2.42
2.43 edge_property_vector(graph_type&);
2.44 -void put(graph_traits<graph_type>::edge_iterator, const T&);
2.45 -get(graph_traits<graph_type>::edge_iterator);
2.46 +void put(graph_type::edge_iterator, const T&);
2.47 +get(graph_type::edge_iterator);
2.48
2.49 Ennyi nem javasolas utan, meg nehany szo.
2.50 Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
3.1 --- a/src/work/marci_graph_demo.cc Tue Jan 20 11:21:42 2004 +0000
3.2 +++ b/src/work/marci_graph_demo.cc Tue Jan 20 17:39:13 2004 +0000
3.3 @@ -3,7 +3,6 @@
3.4 #include <string>
3.5
3.6 #include <marci_list_graph.hh>
3.7 -#include <marci_graph_traits.hh>
3.8 #include <marci_property_vector.hh>
3.9 #include <marci_bfs.hh>
3.10 #include <marci_max_flow.hh>
3.11 @@ -12,14 +11,13 @@
3.12
3.13 int main (int, char*[])
3.14 {
3.15 - typedef graph_traits<list_graph>::node_iterator node_iterator;
3.16 - typedef graph_traits<list_graph>::edge_iterator edge_iterator;
3.17 - typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
3.18 - typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
3.19 - typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
3.20 - typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
3.21 - typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
3.22 -
3.23 + typedef list_graph::node_iterator node_iterator;
3.24 + typedef list_graph::edge_iterator edge_iterator;
3.25 + typedef list_graph::each_node_iterator each_node_iterator;
3.26 + typedef list_graph::each_edge_iterator each_edge_iterator;
3.27 + typedef list_graph::out_edge_iterator out_edge_iterator;
3.28 + typedef list_graph::in_edge_iterator in_edge_iterator;
3.29 + typedef list_graph::sym_edge_iterator sym_edge_iterator;
3.30 list_graph G;
3.31 std::vector<node_iterator> vector_of_node_iterators;
3.32 for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node());
3.33 @@ -31,42 +29,42 @@
3.34 std::cout << "We construct a directed graph on the node set {0,1,2,...,7}," <<std::endl << "i-->j is arc iff i<j and (i+j)%3." << std::endl;
3.35 std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl;
3.36
3.37 - for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.38 + for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
3.39 std::cout << "node " << G.id(i) << std::endl;
3.40 std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " ";
3.41 - for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) {
3.42 + for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
3.43 std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
3.44 }
3.45 std::cout << std::endl;
3.46
3.47 std::cout<< " ";
3.48 - for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) {
3.49 + for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
3.50 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
3.51 std::cout<<std::endl;
3.52
3.53 std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";
3.54 - for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
3.55 + for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
3.56 std::cout << j << " "; }
3.57 std::cout << std::endl;
3.58
3.59 std::cout<< " ";
3.60 - for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
3.61 + for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
3.62 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
3.63 std::cout<<std::endl;
3.64
3.65 std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";
3.66 - for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) {
3.67 + for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
3.68 std::cout << j << " "; }
3.69 std::cout<<std::endl;
3.70
3.71 std::cout<< " ";
3.72 - for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) {
3.73 + for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
3.74 std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
3.75 std::cout<<std::endl;
3.76 }
3.77
3.78 std::cout << "all edges: ";
3.79 - for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {
3.80 + for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
3.81 std::cout << i << " ";
3.82 }
3.83 std::cout << std::endl;
3.84 @@ -82,27 +80,27 @@
3.85 my_property_vector.put(vector_of_node_iterators[4], 2003);
3.86 my_property_vector.put(vector_of_node_iterators[7], 1978);
3.87 std::cout << "some node property values..." << std::endl;
3.88 - for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.89 + for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
3.90 std::cout << my_property_vector.get(i) << std::endl;
3.91 }
3.92 int _i=1;
3.93 int _ii=1;
3.94 edge_property_vector<list_graph, int> my_edge_property(G);
3.95 - for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {
3.96 + for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
3.97 my_edge_property.put(i, _i);
3.98 _i*=_ii; ++_ii;
3.99 }
3.100
3.101 std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
3.102 - for(each_edge_iterator j=G.first_edge(); j.is_valid(); ++j) {
3.103 + for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) {
3.104 std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
3.105 }
3.106 std::cout << std::endl;
3.107
3.108 //std::cout << "the same for inedges of the nodes..." << std::endl;
3.109 //k=0;
3.110 - //for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.111 - // for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
3.112 + //for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
3.113 + // for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
3.114 // std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";
3.115 // }
3.116 // std::cout << std::endl;
3.117 @@ -112,12 +110,12 @@
3.118 bfs<list_graph> bfs_test(G, G.first_node());
3.119 bfs_test.run();
3.120 std::cout << "reached: ";
3.121 - for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.122 + for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
3.123 std::cout << bfs_test.reached.get(i) << " ";
3.124 }
3.125 std::cout<<std::endl;
3.126 std::cout << "dist: ";
3.127 - for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
3.128 + for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
3.129 std::cout << bfs_test.dist.get(i) << " ";
3.130 }
3.131 std::cout<<std::endl;
3.132 @@ -167,19 +165,19 @@
3.133
3.134 std::cout << "on directed graph graph" << std::endl; //<< flow_test;
3.135 std::cout << "names and capacity values" << std::endl;
3.136 - for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) {
3.137 + for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
3.138 std::cout << node_name.get(i) << ": ";
3.139 std::cout << "out edges: ";
3.140 - for(out_edge_iterator j=flow_test.first_out_edge(i); j.is_valid(); ++j)
3.141 + for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
3.142 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
3.143 std::cout << "in edges: ";
3.144 - for(in_edge_iterator j=flow_test.first_in_edge(i); j.is_valid(); ++j)
3.145 + for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
3.146 std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
3.147 std::cout << std::endl;
3.148 }
3.149
3.150
3.151 - //for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) {
3.152 + //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
3.153 // std::cout << i << " ";
3.154 //}
3.155
4.1 --- a/src/work/marci_list_graph.hh Tue Jan 20 11:21:42 2004 +0000
4.2 +++ b/src/work/marci_list_graph.hh Tue Jan 20 17:39:13 2004 +0000
4.3 @@ -19,6 +19,8 @@
4.4 private:
4.5 int node_id;
4.6 int edge_id;
4.7 + int _node_num;
4.8 + int _edge_num;
4.9
4.10 node_item* _first_node;
4.11 node_item* _last_node;
4.12 @@ -80,6 +82,7 @@
4.13 if (_last_node) _last_node->_next_node=p;
4.14 _last_node=p;
4.15 if (!_first_node) _first_node=p;
4.16 + ++_node_num;
4.17 return p;
4.18 }
4.19
4.20 @@ -98,6 +101,7 @@
4.21 if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
4.22 _head->_last_in_edge=e;
4.23 if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
4.24 + ++_edge_num;
4.25 return e;
4.26 }
4.27
4.28 @@ -105,8 +109,11 @@
4.29
4.30 /* default constructor */
4.31
4.32 - list_graph() : node_id(0), edge_id(0), _first_node(0), _last_node(0) { }
4.33 + list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
4.34
4.35 + int node_num() { return _node_num; }
4.36 + int edge_num() { return _edge_num; }
4.37 +
4.38 /* functions to construct iterators from the graph, or from each other */
4.39
4.40 each_node_iterator first_node() { return each_node_iterator(_first_node); }
4.41 @@ -209,7 +216,7 @@
4.42 public:
4.43 node_iterator() : node(0) { }
4.44 node_iterator(node_item* _node) : node(_node) { }
4.45 - bool is_valid() { return (node!=0); }
4.46 + bool valid() { return (node!=0); }
4.47 void make_invalid() { node=0; }
4.48 friend bool operator==(const node_iterator& u, const node_iterator& v) {
4.49 return v.node==u.node;
4.50 @@ -239,7 +246,7 @@
4.51 public:
4.52 edge_iterator() : edge(0) { }
4.53 edge_iterator(edge_item* _edge) : edge(_edge) { }
4.54 - bool is_valid() { return (edge!=0); }
4.55 + bool valid() { return (edge!=0); }
4.56 void make_invalid() { edge=0; }
4.57 friend bool operator==(const edge_iterator& u, const edge_iterator& v) {
4.58 return v.edge==u.edge;
5.1 --- a/src/work/marci_makefile Tue Jan 20 11:21:42 2004 +0000
5.2 +++ b/src/work/marci_makefile Tue Jan 20 17:39:13 2004 +0000
5.3 @@ -1,5 +1,5 @@
5.4 -CCFLAGS = -Wall -ansi
5.5 -CC = /opt/experimental/bin/g++
5.6 +CXXFLAGS = -Wall -ansi -I.
5.7 +CXX = g++-3.0
5.8
5.9 -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.hh
5.10 - $(CC) $(CCFLAGS) -I. marci_graph_demo.cc -o marci_graph_demo
5.11 \ No newline at end of file
5.12 +marci_graph_demo: marci_graph_demo.cc marci_list_graph.hh marci_property_vector.hh marci_bfs.hh marci_max_flow.hh
5.13 + $(CXX) $(CXXFLAGS) marci_graph_demo.cc -o marci_graph_demo
5.14 \ No newline at end of file
6.1 --- a/src/work/marci_max_flow.hh Tue Jan 20 11:21:42 2004 +0000
6.2 +++ b/src/work/marci_max_flow.hh Tue Jan 20 17:39:13 2004 +0000
6.3 @@ -3,7 +3,6 @@
6.4
6.5 #include <algorithm>
6.6
6.7 -#include <marci_graph_traits.hh>
6.8 #include <marci_property_vector.hh>
6.9 #include <marci_bfs.hh>
6.10
6.11 @@ -11,24 +10,22 @@
6.12
6.13 template<typename graph_type, typename T>
6.14 class res_graph_type {
6.15 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
6.16 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
6.17 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
6.18 - typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
6.19 -
6.20 + typedef typename graph_type::node_iterator node_iterator;
6.21 + typedef typename graph_type::each_node_iterator each_node_iterator;
6.22 + typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;
6.23 graph_type& G;
6.24 edge_property_vector<graph_type, T>& flow;
6.25 edge_property_vector<graph_type, T>& capacity;
6.26 public:
6.27 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) { }
6.28
6.29 - class res_edge_it {
6.30 + class edge_iterator {
6.31 friend class res_graph_type<graph_type, T>;
6.32 protected:
6.33 res_graph_type<graph_type, T>* resG;
6.34 - sym_edge_iterator sym;
6.35 + old_sym_edge_iterator sym;
6.36 public:
6.37 - res_edge_it() { }
6.38 + edge_iterator() { }
6.39 //bool is_free() {
6.40 //if (resG->G.a_node(sym)==resG->G.tail(sym)) {
6.41 // return (resG->flow.get(sym)<resG->capacity.get(sym));
6.42 @@ -43,7 +40,7 @@
6.43 return (resG->flow.get(sym));
6.44 }
6.45 }
6.46 - bool is_valid() { return sym.is_valid(); }
6.47 + bool valid() { return sym.valid(); }
6.48 void make_invalid() { sym.make_invalid(); }
6.49 void augment(T a) {
6.50 if (resG->G.a_node(sym)==resG->G.tail(sym)) {
6.51 @@ -54,56 +51,45 @@
6.52 }
6.53 };
6.54
6.55 - class res_out_edge_it : public res_edge_it {
6.56 + class out_edge_iterator : public edge_iterator {
6.57 public:
6.58 - res_out_edge_it() { }
6.59 - res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
6.60 + out_edge_iterator() { }
6.61 + out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
6.62 resG=&_resG;
6.63 sym=resG->G.first_sym_edge(v);
6.64 - while( sym.is_valid() && !(free()>0) ) { ++sym; }
6.65 + while( sym.valid() && !(free()>0) ) { ++sym; }
6.66 }
6.67 - res_out_edge_it& operator++() {
6.68 + out_edge_iterator& operator++() {
6.69 ++sym;
6.70 - while( sym.is_valid() && !(free()>0) ) { ++sym; }
6.71 + while( sym.valid() && !(free()>0) ) { ++sym; }
6.72 return *this;
6.73 }
6.74 };
6.75
6.76 - res_out_edge_it first_out_edge(const node_iterator& v) {
6.77 - return res_out_edge_it(*this, v);
6.78 + out_edge_iterator first_out_edge(const node_iterator& v) {
6.79 + return out_edge_iterator(*this, v);
6.80 }
6.81
6.82 each_node_iterator first_node() {
6.83 return G.first_node();
6.84 }
6.85
6.86 - node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
6.87 - node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
6.88 + node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }
6.89 + node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }
6.90
6.91 int id(const node_iterator& v) { return G.id(v); }
6.92
6.93 //node_iterator invalid_node() { return G.invalid_node(); }
6.94 - //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
6.95 -
6.96 - };
6.97 -
6.98 - template <typename graph_type, typename T>
6.99 - struct graph_traits< res_graph_type<graph_type, T> > {
6.100 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
6.101 - typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
6.102 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
6.103 - typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
6.104 + //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
6.105 };
6.106
6.107 template <typename graph_type, typename T>
6.108 struct max_flow_type {
6.109 -
6.110 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
6.111 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
6.112 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
6.113 - typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
6.114 - typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
6.115 -
6.116 + typedef typename graph_type::node_iterator node_iterator;
6.117 + typedef typename graph_type::edge_iterator edge_iterator;
6.118 + typedef typename graph_type::each_node_iterator each_node_iterator;
6.119 + typedef typename graph_type::out_edge_iterator out_edge_iterator;
6.120 + typedef typename graph_type::in_edge_iterator in_edge_iterator;
6.121 graph_type& G;
6.122 node_iterator s;
6.123 node_iterator t;
6.124 @@ -111,8 +97,8 @@
6.125 edge_property_vector<graph_type, T>& capacity;
6.126
6.127 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) {
6.128 - for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
6.129 - for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
6.130 + for(each_node_iterator i=G.first_node(); i.valid(); ++i)
6.131 + for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
6.132 flow.put(j, 0);
6.133 }
6.134 void run() {
6.135 @@ -123,7 +109,7 @@
6.136 do {
6.137 augment=false;
6.138
6.139 - typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
6.140 + typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type;
6.141 bfs_queue_type bfs_queue;
6.142 bfs_queue.push(res_graph.first_out_edge(s));
6.143
6.144 @@ -134,9 +120,9 @@
6.145 bfs_iterator1< aug_graph_type, reached_type >
6.146 res_bfs(res_graph, bfs_queue, reached);
6.147
6.148 - typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
6.149 + typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type;
6.150 pred_type pred(res_graph);
6.151 - graph_traits<aug_graph_type>::edge_iterator a;
6.152 + aug_graph_type::edge_iterator a;
6.153 a.make_invalid();
6.154 pred.put(s, a);
6.155
6.156 @@ -144,16 +130,16 @@
6.157 free_type free(res_graph);
6.158
6.159 //searching for augmenting path
6.160 - while ( res_bfs.is_valid() ) {
6.161 + while ( res_bfs.valid() ) {
6.162 //std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
6.163 - if (res_bfs.is_newly_reached()) {
6.164 - graph_traits<aug_graph_type>::edge_iterator e;
6.165 + if (res_bfs.newly_reached()) {
6.166 + aug_graph_type::edge_iterator e;
6.167 e=res_bfs;
6.168 node_iterator v=res_graph.tail(e);
6.169 node_iterator w=res_graph.head(e);
6.170 //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
6.171 pred.put(w, e);
6.172 - if (pred.get(v).is_valid()) {
6.173 + if (pred.get(v).valid()) {
6.174 free.put(w, std::min(free.get(v), e.free()));
6.175 //std::cout <<" nem elso csucs: ";
6.176 //std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
6.177 @@ -173,8 +159,8 @@
6.178 node_iterator n=t;
6.179 T augment_value=free.get(t);
6.180 std::cout<<"augmentation: ";
6.181 - while (pred.get(n).is_valid()) {
6.182 - graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
6.183 + while (pred.get(n).valid()) {
6.184 + aug_graph_type::edge_iterator e=pred.get(n);
6.185 e.augment(augment_value);
6.186 std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
6.187 n=res_graph.tail(e);
6.188 @@ -183,7 +169,7 @@
6.189 }
6.190
6.191 std::cout << "actual flow: "<< std::endl;
6.192 - for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
6.193 + for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) {
6.194 std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
6.195 }
6.196 std::cout<<std::endl;
7.1 --- a/src/work/marci_property_vector.hh Tue Jan 20 11:21:42 2004 +0000
7.2 +++ b/src/work/marci_property_vector.hh Tue Jan 20 17:39:13 2004 +0000
7.3 @@ -3,31 +3,29 @@
7.4
7.5 #include <vector>
7.6
7.7 -#include <marci_graph_traits.hh>
7.8 -
7.9 namespace marci {
7.10
7.11 template <typename iterator>
7.12 int number_of(iterator _it) {
7.13 int i=0;
7.14 - for( ; _it.is_valid(); ++_it) { ++i; }
7.15 + for( ; _it.valid(); ++_it) { ++i; }
7.16 return i;
7.17 }
7.18
7.19 template <typename graph_type, typename T>
7.20 class node_property_vector {
7.21 - typedef typename graph_traits<graph_type>::node_iterator node_iterator;
7.22 - typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
7.23 + typedef typename list_graph::node_iterator node_iterator;
7.24 + typedef typename list_graph::each_node_iterator each_node_iterator;
7.25 graph_type& G;
7.26 std::vector<T> container;
7.27 public:
7.28 node_property_vector(graph_type& _G) : G(_G) {
7.29 int i=0;
7.30 - for(each_node_iterator it=G.first_node(); it.is_valid(); ++it) ++i;
7.31 + for(each_node_iterator it=G.first_node(); it.valid(); ++it) ++i;
7.32 container.resize(i);
7.33 }
7.34 node_property_vector(graph_type& _G, T a) : G(_G) {
7.35 - for(each_node_iterator it=G.first_node(); it.is_valid(); ++it) { container.push_back(a); }
7.36 + for(each_node_iterator it=G.first_node(); it.valid(); ++it) { container.push_back(a); }
7.37 }
7.38 void put(node_iterator nit, const T& a) { container[G.id(nit)]=a; }
7.39 T get(node_iterator nit) { return container[G.id(nit)]; }
7.40 @@ -35,18 +33,18 @@
7.41
7.42 template <typename graph_type, typename T>
7.43 class edge_property_vector {
7.44 - typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
7.45 - typedef typename graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
7.46 + typedef typename graph_type::edge_iterator edge_iterator;
7.47 + typedef typename graph_type::each_edge_iterator each_edge_iterator;
7.48 graph_type& G;
7.49 std::vector<T> container;
7.50 public:
7.51 edge_property_vector(graph_type& _G) : G(_G) {
7.52 int i=0;
7.53 - for(each_edge_iterator it=G.first_edge(); it.is_valid(); ++it) ++i;
7.54 + for(each_edge_iterator it=G.first_edge(); it.valid(); ++it) ++i;
7.55 container.resize(i);
7.56 }
7.57 edge_property_vector(graph_type& _G, T a) : G(_G) {
7.58 - for(each_edge_iterator it=G.first_edge(); it.is_valid(); ++it) {
7.59 + for(each_edge_iterator it=G.first_edge(); it.valid(); ++it) {
7.60 container.push_back(a);
7.61 }
7.62 }