# HG changeset patch
# User marci
# Date 1074620353 0
# Node ID 3151a1026db98969f471dbb84f5a59c7e10dfc69
# Parent 7c88989ea45b871511fbd9c2b1bb130c73419bdf
*** empty log message ***
diff -r 7c88989ea45b -r 3151a1026db9 src/work/marci_bfs.hh
--- a/src/work/marci_bfs.hh Tue Jan 20 11:21:42 2004 +0000
+++ b/src/work/marci_bfs.hh Tue Jan 20 17:39:13 2004 +0000
@@ -3,18 +3,16 @@
#include <queue>
-#include <marci_graph_traits.hh>
#include <marci_property_vector.hh>
namespace marci {
template <typename graph_type>
struct bfs {
- typedef typename graph_traits<graph_type>::node_iterator node_iterator;
- typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
- typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
- typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-
+ typedef typename graph_type::node_iterator node_iterator;
+ typedef typename graph_type::edge_iterator edge_iterator;
+ typedef typename graph_type::each_node_iterator each_node_iterator;
+ typedef typename graph_type::out_edge_iterator out_edge_iterator;
graph_type& G;
node_iterator s;
node_property_vector<graph_type, bool> reached;
@@ -23,7 +21,7 @@
std::queue<node_iterator> bfs_queue;
bfs(graph_type& _G, node_iterator _s) : G(_G), s(_s), reached(_G), pred(_G), dist(_G) {
bfs_queue.push(s);
- for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
+ for(each_node_iterator i=G.first_node(); i.valid(); ++i)
reached.put(i, false);
reached.put(s, true);
dist.put(s, 0);
@@ -34,7 +32,7 @@
node_iterator v=bfs_queue.front();
out_edge_iterator e=G.first_out_edge(v);
bfs_queue.pop();
- for( ; e.is_valid(); ++e) {
+ for( ; e.valid(); ++e) {
node_iterator w=G.head(e);
std::cout << "scan node " << G.id(w) << " from node " << G.id(v) << std::endl;
if (!reached.get(w)) {
@@ -53,10 +51,9 @@
template <typename graph_type>
struct bfs_visitor {
- typedef typename graph_traits<graph_type>::node_iterator node_iterator;
- typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
- typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
- typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
+ typedef typename graph_type::node_iterator node_iterator;
+ typedef typename graph_type::edge_iterator edge_iterator;
+ typedef typename graph_type::out_edge_iterator out_edge_iterator;
graph_type& G;
bfs_visitor(graph_type& _G) : G(_G) { }
void at_previously_reached(out_edge_iterator& e) {
@@ -73,17 +70,15 @@
template <typename graph_type, typename reached_type, typename visitor_type>
struct bfs_iterator {
- typedef typename graph_traits<graph_type>::node_iterator node_iterator;
- typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
- typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
- typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-
+ typedef typename graph_type::node_iterator node_iterator;
+ typedef typename graph_type::edge_iterator edge_iterator;
+ typedef typename graph_type::out_edge_iterator out_edge_iterator;
graph_type& G;
std::queue<out_edge_iterator>& bfs_queue;
reached_type& reached;
visitor_type& visitor;
void process() {
- while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
+ while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
if (bfs_queue.empty()) return;
out_edge_iterator e=bfs_queue.front();
//node_iterator v=G.tail(e);
@@ -97,30 +92,30 @@
}
}
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) {
- //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
- is_valid();
+ //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
+ valid();
}
bfs_iterator<graph_type, reached_type, visitor_type>& operator++() {
- //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
+ //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
//if (bfs_queue.empty()) return *this;
- if (!is_valid()) return *this;
+ if (!valid()) return *this;
++(bfs_queue.front());
- //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
- is_valid();
+ //while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
+ valid();
return *this;
}
//void next() {
- // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
+ // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
// if (bfs_queue.empty()) return;
// ++(bfs_queue.front());
- // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
+ // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
//}
- bool is_valid() {
- while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
+ bool valid() {
+ while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
if (bfs_queue.empty()) return false; else return true;
}
//bool finished() {
- // while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
+ // while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
// if (bfs_queue.empty()) return true; else return false;
//}
operator edge_iterator () { return bfs_queue.front(); }
@@ -129,52 +124,50 @@
template <typename graph_type, typename reached_type>
struct bfs_iterator1 {
- typedef typename graph_traits<graph_type>::node_iterator node_iterator;
- typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
- typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
- typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
-
+ typedef typename graph_type::node_iterator node_iterator;
+ typedef typename graph_type::edge_iterator edge_iterator;
+ typedef typename graph_type::out_edge_iterator out_edge_iterator;
graph_type& G;
std::queue<out_edge_iterator>& bfs_queue;
reached_type& reached;
- bool newly_reached;
+ bool _newly_reached;
bfs_iterator1(graph_type& _G, std::queue<out_edge_iterator>& _bfs_queue, reached_type& _reached) : G(_G), bfs_queue(_bfs_queue), reached(_reached) {
- is_valid();
- if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {
+ valid();
+ if (!bfs_queue.empty() && bfs_queue.front().valid()) {
out_edge_iterator e=bfs_queue.front();
node_iterator w=G.head(e);
if (!reached.get(w)) {
bfs_queue.push(G.first_out_edge(w));
reached.put(w, true);
- newly_reached=true;
+ _newly_reached=true;
} else {
- newly_reached=false;
+ _newly_reached=false;
}
}
}
bfs_iterator1<graph_type, reached_type>& operator++() {
- if (!is_valid()) return *this;
+ if (!valid()) return *this;
++(bfs_queue.front());
- is_valid();
- if (!bfs_queue.empty() && bfs_queue.front().is_valid()) {
+ valid();
+ if (!bfs_queue.empty() && bfs_queue.front().valid()) {
out_edge_iterator e=bfs_queue.front();
node_iterator w=G.head(e);
if (!reached.get(w)) {
bfs_queue.push(G.first_out_edge(w));
reached.put(w, true);
- newly_reached=true;
+ _newly_reached=true;
} else {
- newly_reached=false;
+ _newly_reached=false;
}
}
return *this;
}
- bool is_valid() {
- while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); }
+ bool valid() {
+ while ( !bfs_queue.empty() && !bfs_queue.front().valid() ) { bfs_queue.pop(); }
if (bfs_queue.empty()) return false; else return true;
}
operator edge_iterator () { return bfs_queue.front(); }
- bool is_newly_reached() { return newly_reached; }
+ bool newly_reached() { return _newly_reached; }
};
diff -r 7c88989ea45b -r 3151a1026db9 src/work/marci_graph_concept.txt
--- a/src/work/marci_graph_concept.txt Tue Jan 20 11:21:42 2004 +0000
+++ b/src/work/marci_graph_concept.txt Tue Jan 20 17:39:13 2004 +0000
@@ -16,7 +16,6 @@
marci_bfs.hh //bfs, tejesen kiserleti
marci_graph_demo.cc //peldaprogi a lisas graf hasznalatahoz
-marci_graph_traits.hh //alapertelmezett graph_traits
marci_list_graph.hh //list_graph megvalositas
marci_max_flow.hh //folyam, kiserleti
marci_property_vector.hh //property vector megvalosites indexelt grafokhoz
@@ -131,7 +130,7 @@
node_iterator metodusai:
node_iterator();
-bool is_valid();
+bool valid();
void make_invalid();
ezek nem tagfuggvenyek:
friend bool operator==(const node_iterator&, const node_iterator&);
@@ -144,7 +143,7 @@
edge_iterator metodusai:
edge_iterator();
-bool is_valid();
+bool valid();
void make_invalid();
ezek nem tagfvek:
friend bool operator==(const edge_iterator&, const edge_iterator&);
@@ -192,8 +191,8 @@
metodusok:
node_property_vector(graph_type&);
-void put(graph_traits<graph_type>::node_iterator, const T&);
-T get(graph_traits<graph_type>::node_iterator);
+void put(graph_type::node_iterator, const T&);
+T get(graph_type::node_iterator);
Ugyanez edge_property_array-okkal
@@ -201,8 +200,8 @@
class edge_property_vector;
edge_property_vector(graph_type&);
-void put(graph_traits<graph_type>::edge_iterator, const T&);
-get(graph_traits<graph_type>::edge_iterator);
+void put(graph_type::edge_iterator, const T&);
+get(graph_type::edge_iterator);
Ennyi nem javasolas utan, meg nehany szo.
Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen
diff -r 7c88989ea45b -r 3151a1026db9 src/work/marci_graph_demo.cc
--- a/src/work/marci_graph_demo.cc Tue Jan 20 11:21:42 2004 +0000
+++ b/src/work/marci_graph_demo.cc Tue Jan 20 17:39:13 2004 +0000
@@ -3,7 +3,6 @@
#include <string>
#include <marci_list_graph.hh>
-#include <marci_graph_traits.hh>
#include <marci_property_vector.hh>
#include <marci_bfs.hh>
#include <marci_max_flow.hh>
@@ -12,14 +11,13 @@
int main (int, char*[])
{
- typedef graph_traits<list_graph>::node_iterator node_iterator;
- typedef graph_traits<list_graph>::edge_iterator edge_iterator;
- typedef graph_traits<list_graph>::each_node_iterator each_node_iterator;
- typedef graph_traits<list_graph>::each_edge_iterator each_edge_iterator;
- typedef graph_traits<list_graph>::out_edge_iterator out_edge_iterator;
- typedef graph_traits<list_graph>::in_edge_iterator in_edge_iterator;
- typedef graph_traits<list_graph>::sym_edge_iterator sym_edge_iterator;
-
+ typedef list_graph::node_iterator node_iterator;
+ typedef list_graph::edge_iterator edge_iterator;
+ typedef list_graph::each_node_iterator each_node_iterator;
+ typedef list_graph::each_edge_iterator each_edge_iterator;
+ typedef list_graph::out_edge_iterator out_edge_iterator;
+ typedef list_graph::in_edge_iterator in_edge_iterator;
+ typedef list_graph::sym_edge_iterator sym_edge_iterator;
list_graph G;
std::vector<node_iterator> vector_of_node_iterators;
for(int i=0; i!=8; ++i) vector_of_node_iterators.push_back(G.add_node());
@@ -31,42 +29,42 @@
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;
std::cout << "number of nodes: " << number_of(G.first_node()) << std::endl;
- for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
+ for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
std::cout << "node " << G.id(i) << std::endl;
std::cout << " outdegree (out_edge_iterator): " << number_of(G.first_out_edge(i)) << " ";
- for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) {
+ for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(j)) << ") ";
}
std::cout << std::endl;
std::cout<< " ";
- for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j) {
+ for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j) {
std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
std::cout<<std::endl;
std::cout << " indegree: (in_edge_oterator) " << number_of(G.first_in_edge(i)) << " ";
- for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
+ for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
std::cout << j << " "; }
std::cout << std::endl;
std::cout<< " ";
- for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
+ for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
std::cout<<std::endl;
std::cout << " degree: (sym_edge_iterator) " << number_of(G.first_sym_edge(i)) << " ";
- for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) {
+ for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
std::cout << j << " "; }
std::cout<<std::endl;
std::cout<< " ";
- for(sym_edge_iterator j=G.first_sym_edge(i); j.is_valid(); ++j) {
+ for(sym_edge_iterator j=G.first_sym_edge(i); j.valid(); ++j) {
std::cout << G.a_node(j) << "->" << G.b_node(j) << " "; }
std::cout<<std::endl;
}
std::cout << "all edges: ";
- for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {
+ for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
std::cout << i << " ";
}
std::cout << std::endl;
@@ -82,27 +80,27 @@
my_property_vector.put(vector_of_node_iterators[4], 2003);
my_property_vector.put(vector_of_node_iterators[7], 1978);
std::cout << "some node property values..." << std::endl;
- for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
+ for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
std::cout << my_property_vector.get(i) << std::endl;
}
int _i=1;
int _ii=1;
edge_property_vector<list_graph, int> my_edge_property(G);
- for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {
+ for(each_edge_iterator i=G.first_edge(); i.valid(); ++i) {
my_edge_property.put(i, _i);
_i*=_ii; ++_ii;
}
std::cout << "node and edge property values on the tails and heads of edges..." << std::endl;
- for(each_edge_iterator j=G.first_edge(); j.is_valid(); ++j) {
+ for(each_edge_iterator j=G.first_edge(); j.valid(); ++j) {
std::cout << my_property_vector.get(G.tail(j)) << "--" << my_edge_property.get(j) << "-->" << my_property_vector.get(G.head(j)) << " ";
}
std::cout << std::endl;
//std::cout << "the same for inedges of the nodes..." << std::endl;
//k=0;
- //for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
- // for(in_edge_iterator j=G.first_in_edge(i); j.is_valid(); ++j) {
+ //for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
+ // for(in_edge_iterator j=G.first_in_edge(i); j.valid(); ++j) {
// std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";
// }
// std::cout << std::endl;
@@ -112,12 +110,12 @@
bfs<list_graph> bfs_test(G, G.first_node());
bfs_test.run();
std::cout << "reached: ";
- for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
+ for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
std::cout << bfs_test.reached.get(i) << " ";
}
std::cout<<std::endl;
std::cout << "dist: ";
- for(each_node_iterator i=G.first_node(); i.is_valid(); ++i) {
+ for(each_node_iterator i=G.first_node(); i.valid(); ++i) {
std::cout << bfs_test.dist.get(i) << " ";
}
std::cout<<std::endl;
@@ -167,19 +165,19 @@
std::cout << "on directed graph graph" << std::endl; //<< flow_test;
std::cout << "names and capacity values" << std::endl;
- for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) {
+ for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
std::cout << node_name.get(i) << ": ";
std::cout << "out edges: ";
- for(out_edge_iterator j=flow_test.first_out_edge(i); j.is_valid(); ++j)
+ for(out_edge_iterator j=flow_test.first_out_edge(i); j.valid(); ++j)
std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
std::cout << "in edges: ";
- for(in_edge_iterator j=flow_test.first_in_edge(i); j.is_valid(); ++j)
+ for(in_edge_iterator j=flow_test.first_in_edge(i); j.valid(); ++j)
std::cout << node_name.get(flow_test.tail(j)) << "-"<< cap.get(j) << "->" << node_name.get(flow_test.head(j)) << " ";
std::cout << std::endl;
}
- //for(each_node_iterator i=flow_test.first_node(); i.is_valid(); ++i) {
+ //for(each_node_iterator i=flow_test.first_node(); i.valid(); ++i) {
// std::cout << i << " ";
//}
diff -r 7c88989ea45b -r 3151a1026db9 src/work/marci_list_graph.hh
--- a/src/work/marci_list_graph.hh Tue Jan 20 11:21:42 2004 +0000
+++ b/src/work/marci_list_graph.hh Tue Jan 20 17:39:13 2004 +0000
@@ -19,6 +19,8 @@
private:
int node_id;
int edge_id;
+ int _node_num;
+ int _edge_num;
node_item* _first_node;
node_item* _last_node;
@@ -80,6 +82,7 @@
if (_last_node) _last_node->_next_node=p;
_last_node=p;
if (!_first_node) _first_node=p;
+ ++_node_num;
return p;
}
@@ -98,6 +101,7 @@
if (_head->_last_in_edge) (_head->_last_in_edge)->_next_in=e;
_head->_last_in_edge=e;
if (!_head->_first_in_edge) { _head->_first_in_edge=e; }
+ ++_edge_num;
return e;
}
@@ -105,8 +109,11 @@
/* default constructor */
- list_graph() : node_id(0), edge_id(0), _first_node(0), _last_node(0) { }
+ list_graph() : node_id(0), edge_id(0), _node_num(0), _edge_num(0), _first_node(0), _last_node(0) { }
+ int node_num() { return _node_num; }
+ int edge_num() { return _edge_num; }
+
/* functions to construct iterators from the graph, or from each other */
each_node_iterator first_node() { return each_node_iterator(_first_node); }
@@ -209,7 +216,7 @@
public:
node_iterator() : node(0) { }
node_iterator(node_item* _node) : node(_node) { }
- bool is_valid() { return (node!=0); }
+ bool valid() { return (node!=0); }
void make_invalid() { node=0; }
friend bool operator==(const node_iterator& u, const node_iterator& v) {
return v.node==u.node;
@@ -239,7 +246,7 @@
public:
edge_iterator() : edge(0) { }
edge_iterator(edge_item* _edge) : edge(_edge) { }
- bool is_valid() { return (edge!=0); }
+ bool valid() { return (edge!=0); }
void make_invalid() { edge=0; }
friend bool operator==(const edge_iterator& u, const edge_iterator& v) {
return v.edge==u.edge;
diff -r 7c88989ea45b -r 3151a1026db9 src/work/marci_makefile
--- a/src/work/marci_makefile Tue Jan 20 11:21:42 2004 +0000
+++ b/src/work/marci_makefile Tue Jan 20 17:39:13 2004 +0000
@@ -1,5 +1,5 @@
-CCFLAGS = -Wall -ansi
-CC = /opt/experimental/bin/g++
+CXXFLAGS = -Wall -ansi -I.
+CXX = g++-3.0
-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
- $(CC) $(CCFLAGS) -I. marci_graph_demo.cc -o marci_graph_demo
\ No newline at end of file
+marci_graph_demo: marci_graph_demo.cc marci_list_graph.hh marci_property_vector.hh marci_bfs.hh marci_max_flow.hh
+ $(CXX) $(CXXFLAGS) marci_graph_demo.cc -o marci_graph_demo
\ No newline at end of file
diff -r 7c88989ea45b -r 3151a1026db9 src/work/marci_max_flow.hh
--- a/src/work/marci_max_flow.hh Tue Jan 20 11:21:42 2004 +0000
+++ b/src/work/marci_max_flow.hh Tue Jan 20 17:39:13 2004 +0000
@@ -3,7 +3,6 @@
#include <algorithm>
-#include <marci_graph_traits.hh>
#include <marci_property_vector.hh>
#include <marci_bfs.hh>
@@ -11,24 +10,22 @@
template<typename graph_type, typename T>
class res_graph_type {
- typedef typename graph_traits<graph_type>::node_iterator node_iterator;
- typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
- typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
- typedef typename graph_traits<graph_type>::sym_edge_iterator sym_edge_iterator;
-
+ typedef typename graph_type::node_iterator node_iterator;
+ typedef typename graph_type::each_node_iterator each_node_iterator;
+ typedef typename graph_type::sym_edge_iterator old_sym_edge_iterator;
graph_type& G;
edge_property_vector<graph_type, T>& flow;
edge_property_vector<graph_type, T>& capacity;
public:
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) { }
- class res_edge_it {
+ class edge_iterator {
friend class res_graph_type<graph_type, T>;
protected:
res_graph_type<graph_type, T>* resG;
- sym_edge_iterator sym;
+ old_sym_edge_iterator sym;
public:
- res_edge_it() { }
+ edge_iterator() { }
//bool is_free() {
//if (resG->G.a_node(sym)==resG->G.tail(sym)) {
// return (resG->flow.get(sym)<resG->capacity.get(sym));
@@ -43,7 +40,7 @@
return (resG->flow.get(sym));
}
}
- bool is_valid() { return sym.is_valid(); }
+ bool valid() { return sym.valid(); }
void make_invalid() { sym.make_invalid(); }
void augment(T a) {
if (resG->G.a_node(sym)==resG->G.tail(sym)) {
@@ -54,56 +51,45 @@
}
};
- class res_out_edge_it : public res_edge_it {
+ class out_edge_iterator : public edge_iterator {
public:
- res_out_edge_it() { }
- res_out_edge_it(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
+ out_edge_iterator() { }
+ out_edge_iterator(res_graph_type<graph_type, T>& _resG, const node_iterator& v) {
resG=&_resG;
sym=resG->G.first_sym_edge(v);
- while( sym.is_valid() && !(free()>0) ) { ++sym; }
+ while( sym.valid() && !(free()>0) ) { ++sym; }
}
- res_out_edge_it& operator++() {
+ out_edge_iterator& operator++() {
++sym;
- while( sym.is_valid() && !(free()>0) ) { ++sym; }
+ while( sym.valid() && !(free()>0) ) { ++sym; }
return *this;
}
};
- res_out_edge_it first_out_edge(const node_iterator& v) {
- return res_out_edge_it(*this, v);
+ out_edge_iterator first_out_edge(const node_iterator& v) {
+ return out_edge_iterator(*this, v);
}
each_node_iterator first_node() {
return G.first_node();
}
- node_iterator tail(const res_edge_it& e) { return G.a_node(e.sym); }
- node_iterator head(const res_edge_it& e) { return G.b_node(e.sym); }
+ node_iterator tail(const edge_iterator& e) { return G.a_node(e.sym); }
+ node_iterator head(const edge_iterator& e) { return G.b_node(e.sym); }
int id(const node_iterator& v) { return G.id(v); }
//node_iterator invalid_node() { return G.invalid_node(); }
- //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
-
- };
-
- template <typename graph_type, typename T>
- struct graph_traits< res_graph_type<graph_type, T> > {
- typedef typename graph_traits<graph_type>::node_iterator node_iterator;
- typedef typename res_graph_type<graph_type, T>::res_edge_it edge_iterator;
- typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
- typedef typename res_graph_type<graph_type, T>::res_out_edge_it out_edge_iterator;
+ //res_edge_it invalid_edge() { res_edge_it n; n.sym=G.invalid_sym_edge(); return n; }
};
template <typename graph_type, typename T>
struct max_flow_type {
-
- typedef typename graph_traits<graph_type>::node_iterator node_iterator;
- typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
- typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
- typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
- typedef typename graph_traits<graph_type>::in_edge_iterator in_edge_iterator;
-
+ typedef typename graph_type::node_iterator node_iterator;
+ typedef typename graph_type::edge_iterator edge_iterator;
+ typedef typename graph_type::each_node_iterator each_node_iterator;
+ typedef typename graph_type::out_edge_iterator out_edge_iterator;
+ typedef typename graph_type::in_edge_iterator in_edge_iterator;
graph_type& G;
node_iterator s;
node_iterator t;
@@ -111,8 +97,8 @@
edge_property_vector<graph_type, T>& capacity;
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) {
- for(each_node_iterator i=G.first_node(); i.is_valid(); ++i)
- for(out_edge_iterator j=G.first_out_edge(i); j.is_valid(); ++j)
+ for(each_node_iterator i=G.first_node(); i.valid(); ++i)
+ for(out_edge_iterator j=G.first_out_edge(i); j.valid(); ++j)
flow.put(j, 0);
}
void run() {
@@ -123,7 +109,7 @@
do {
augment=false;
- typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
+ typedef std::queue<aug_graph_type::out_edge_iterator> bfs_queue_type;
bfs_queue_type bfs_queue;
bfs_queue.push(res_graph.first_out_edge(s));
@@ -134,9 +120,9 @@
bfs_iterator1< aug_graph_type, reached_type >
res_bfs(res_graph, bfs_queue, reached);
- typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
+ typedef node_property_vector<aug_graph_type, aug_graph_type::edge_iterator> pred_type;
pred_type pred(res_graph);
- graph_traits<aug_graph_type>::edge_iterator a;
+ aug_graph_type::edge_iterator a;
a.make_invalid();
pred.put(s, a);
@@ -144,16 +130,16 @@
free_type free(res_graph);
//searching for augmenting path
- while ( res_bfs.is_valid() ) {
+ while ( res_bfs.valid() ) {
//std::cout<<"KULSO ciklus itt jar: "<<G.id(res_graph.tail(res_bfs))<<"->"<<G.id(res_graph.head(res_bfs))<<std::endl;
- if (res_bfs.is_newly_reached()) {
- graph_traits<aug_graph_type>::edge_iterator e;
+ if (res_bfs.newly_reached()) {
+ aug_graph_type::edge_iterator e;
e=res_bfs;
node_iterator v=res_graph.tail(e);
node_iterator w=res_graph.head(e);
//std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is newly reached";
pred.put(w, e);
- if (pred.get(v).is_valid()) {
+ if (pred.get(v).valid()) {
free.put(w, std::min(free.get(v), e.free()));
//std::cout <<" nem elso csucs: ";
//std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
@@ -173,8 +159,8 @@
node_iterator n=t;
T augment_value=free.get(t);
std::cout<<"augmentation: ";
- while (pred.get(n).is_valid()) {
- graph_traits<aug_graph_type>::edge_iterator e=pred.get(n);
+ while (pred.get(n).valid()) {
+ aug_graph_type::edge_iterator e=pred.get(n);
e.augment(augment_value);
std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
n=res_graph.tail(e);
@@ -183,7 +169,7 @@
}
std::cout << "actual flow: "<< std::endl;
- for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) {
+ for(typename graph_type::each_edge_iterator e=G.first_edge(); e.valid(); ++e) {
std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
}
std::cout<<std::endl;
diff -r 7c88989ea45b -r 3151a1026db9 src/work/marci_property_vector.hh
--- a/src/work/marci_property_vector.hh Tue Jan 20 11:21:42 2004 +0000
+++ b/src/work/marci_property_vector.hh Tue Jan 20 17:39:13 2004 +0000
@@ -3,31 +3,29 @@
#include <vector>
-#include <marci_graph_traits.hh>
-
namespace marci {
template <typename iterator>
int number_of(iterator _it) {
int i=0;
- for( ; _it.is_valid(); ++_it) { ++i; }
+ for( ; _it.valid(); ++_it) { ++i; }
return i;
}
template <typename graph_type, typename T>
class node_property_vector {
- typedef typename graph_traits<graph_type>::node_iterator node_iterator;
- typedef typename graph_traits<graph_type>::each_node_iterator each_node_iterator;
+ typedef typename list_graph::node_iterator node_iterator;
+ typedef typename list_graph::each_node_iterator each_node_iterator;
graph_type& G;
std::vector<T> container;
public:
node_property_vector(graph_type& _G) : G(_G) {
int i=0;
- for(each_node_iterator it=G.first_node(); it.is_valid(); ++it) ++i;
+ for(each_node_iterator it=G.first_node(); it.valid(); ++it) ++i;
container.resize(i);
}
node_property_vector(graph_type& _G, T a) : G(_G) {
- for(each_node_iterator it=G.first_node(); it.is_valid(); ++it) { container.push_back(a); }
+ for(each_node_iterator it=G.first_node(); it.valid(); ++it) { container.push_back(a); }
}
void put(node_iterator nit, const T& a) { container[G.id(nit)]=a; }
T get(node_iterator nit) { return container[G.id(nit)]; }
@@ -35,18 +33,18 @@
template <typename graph_type, typename T>
class edge_property_vector {
- typedef typename graph_traits<graph_type>::edge_iterator edge_iterator;
- typedef typename graph_traits<graph_type>::each_edge_iterator each_edge_iterator;
+ typedef typename graph_type::edge_iterator edge_iterator;
+ typedef typename graph_type::each_edge_iterator each_edge_iterator;
graph_type& G;
std::vector<T> container;
public:
edge_property_vector(graph_type& _G) : G(_G) {
int i=0;
- for(each_edge_iterator it=G.first_edge(); it.is_valid(); ++it) ++i;
+ for(each_edge_iterator it=G.first_edge(); it.valid(); ++it) ++i;
container.resize(i);
}
edge_property_vector(graph_type& _G, T a) : G(_G) {
- for(each_edge_iterator it=G.first_edge(); it.is_valid(); ++it) {
+ for(each_edge_iterator it=G.first_edge(); it.valid(); ++it) {
container.push_back(a);
}
}