# HG changeset patch
# User marci
# Date 1072792748 0
# Node ID a9ed3f1c2c637d50ad05a84c994c2d9f3838e3c1
# Parent  cd54905012bc1e220aac07da08c5ddc847dd7d25
marci

diff -r cd54905012bc -r a9ed3f1c2c63 src/work/marci_bfs.hh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci_bfs.hh	Tue Dec 30 13:59:08 2003 +0000
@@ -0,0 +1,133 @@
+#ifndef MARCI_BFS_HH
+#define MARCI_BFS_HH
+
+#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;
+
+    graph_type& G;
+    node_iterator s;
+    node_property_vector<graph_type, bool> reached;
+    node_property_vector<graph_type, edge_iterator> pred;
+    node_property_vector<graph_type, int> dist;
+    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) 
+	reached.put(i, false);
+      reached.put(s, true);
+      dist.put(s, 0); 
+    }
+    
+    void run() {
+      while (!bfs_queue.empty()) {
+	node_iterator v=bfs_queue.front();
+	out_edge_iterator e=G.first_out_edge(v);
+	bfs_queue.pop();
+	for( ; e.is_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)) {
+	    std::cout << G.id(w) << " is newly reached :-)" << std::endl;
+	    bfs_queue.push(w);
+	    dist.put(w, dist.get(v)+1);
+	    pred.put(w, e);
+	    reached.put(w, true);
+	  } else {
+	    std::cout << G.id(w) << " is already reached" << std::endl;
+	  }
+	}
+      }
+    }
+  };
+
+  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;
+    graph_type& G;
+    bfs_visitor(graph_type& _G) : G(_G) { }
+    void at_previously_reached(out_edge_iterator& e) { 
+      //node_iterator v=G.tail(e);
+      node_iterator w=G.head(e);
+      std::cout << G.id(w) << " is already reached" << std::endl;
+   }
+    void at_newly_reached(out_edge_iterator& e) { 
+      //node_iterator v=G.tail(e);
+      node_iterator w=G.head(e);
+      std::cout << G.id(w) << " is newly reached :-)" << std::endl;
+    }
+  };
+
+  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;
+
+    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(); } 
+      if (bfs_queue.empty()) return;
+      out_edge_iterator e=bfs_queue.front();
+      //node_iterator v=G.tail(e);
+      node_iterator w=G.head(e);
+      if (!reached.get(w)) {
+	visitor.at_newly_reached(e);
+	bfs_queue.push(G.first_out_edge(w));
+	reached.put(w, true);
+      } else {
+	visitor.at_previously_reached(e);
+      }
+    }
+    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();
+    }
+    bfs_iterator<graph_type, reached_type, visitor_type>& operator++() { 
+      //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+      //if (bfs_queue.empty()) return *this;
+      if (!is_valid()) return *this;
+      ++(bfs_queue.front());
+      //while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+      is_valid();
+      return *this;
+    }
+    //void next() { 
+    //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+    //  if (bfs_queue.empty()) return;
+    //  ++(bfs_queue.front());
+    //  while ( !bfs_queue.empty() && !bfs_queue.front().is_valid() ) { bfs_queue.pop(); } 
+    //}
+    bool is_valid() { 
+      while ( !bfs_queue.empty() && !bfs_queue.front().is_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(); } 
+    //  if (bfs_queue.empty()) return true; else return false;
+    //}
+    operator edge_iterator () { return bfs_queue.front(); }
+
+  };
+
+
+} // namespace marci
+
+#endif //MARCI_BFS_HH
diff -r cd54905012bc -r a9ed3f1c2c63 src/work/marci_graph_concept.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci_graph_concept.txt	Tue Dec 30 13:59:08 2003 +0000
@@ -0,0 +1,215 @@
+ETIK-OL-NOLIB-NEGRES graph concept-ek.
+
+ Ebben a dokumentacioban graph concept tervek es azok megvalositastarol irok. 
+A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi 
+operacio elegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen 
+ujakra van szukseg. 
+
+ Megvalositottunk egy graph osztalyt mely listaban tarolja a pontokat, 
+az 1 pontbol kiindulo eleket, s az 1 pontba bemeno eleket. Konstrualni lehet 
+ures grafot, hozzaadni pontokat, eleket. Az incidenciat node_iteratorok-kal 
+ill. edge_iteratorokkal lehet megfigyelni. Adott tovabba 1 template osztaly, 
+a graf pontjaihoz vagy eleihez tetszoleges tipusu property hozzarendelesere, 
+a jelen megvalositas ezeket vektorben tarolja. Fontos azonban, hogy ezen 
+property_vector csak azokra a graf-objektumokra ervenyes, melyek 
+letrehozasanak pillanataban a grafhoz tartoznak. 
+
+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	
+graf es iterator tipusok:
+
+class list_graph	 
+
+class node_iterator      
+trivialis node iterator, csak cimezni lehet vele, pl property vectort
+
+class each_node_iterator
+node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
+
+class edge_iterator
+trivialis edge iterator, csak cimezni lehet vele, pl property vectort
+
+class each_edge_iterator
+edge iterator a graf osszes elenek bejarasara
+
+class out_edge_iterator
+edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
+
+class in_edge_iterator
+edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
+      
+class sym_edge_iterator
+edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
+
+default constructor:
+
+list_graph() 
+    
+A graf osztaly fobb publikus metodusai, az alapveto hasznalathoz:
+Hasonlo funkciok megvalosithatok 1 kesobb leirt modon, illetve 
+ezek kozul nehany az iteratorok metodusaival, megis azt javasolnam, hogy az 
+iteratorok metodusait ne hasznaljuk. Miert? Azt  szeretnenk, ha 1 ponthalmazon 
+van 2 graf, es csak az elhalmazhoz keszitunk uj iteratorokat, akkor pl 1 pont 
+out-edge-iteratora megkaphato legyen a grafbol es a node_iteratorbol. Ezert 
+out_edge_iterator(const node_iterator&) hasznalata nem javasolt, 
+esetleg majd szamuzzuk a concept-bol, s akkor nem nesz baj. 
+
+each_node_iterator first_node()
+each_edge_iterator first_edge()
+out_edge_iterator first_out_edge(const node_iterator&)
+in_edge_iterator first_in_edge(const node_iterator&)
+sym_edge_iterator first_sym_edge(const node_iterator&)
+
+node_iterator tail(const edge_iterator&)
+node_iterator head(const edge_iterator&)
+
+node_iterator a_node(const out_edge_iterator&)
+node_iterator a_node(const in_edge_iterator&)
+node_iterator a_node(const sym_edge_iterator&)
+//az out, in or sym edge iterator rogzitett pontjara ad 1 node_iterator-t
+
+node_iterator b_node(const out_edge_iterator&)
+node_iterator b_node(const in_edge_iterator&)
+node_iterator b_node(const sym_edge_iterator&)
+//az out, in or sym edge iterator nem rogzitett pontjara ad 1 node_iterator-t
+
+node_iterator invalid_node()
+edge_iterator invalid_edge()
+out_edge_iterator invalid_out_edge()
+in_edge_iterator invalid_in_edge()
+sym_edge_iterator invalid_sym_edge()
+
+//az iteratorok ures konstruktorai meghatarozatlan 
+tartalmu konstruktort adnak vissza, ezekkel a matodusokkal 
+lehet ervenytelent csinalni.
+Lehet hogy ezt az ures konstruktorral kellene, tessek vitatkozni.
+
+Kiserleti cellal ugyanezen fv-ek mas stilusu megvalositasai:
+
+void get_first(each_node_iterator&)
+void get_first(each_edge_iterator&)
+void get_first(out_edge_iterator&, const node_iterator&)
+void get_first(in_edge_iterator&, const node_iterator&)
+void get_first(sym_edge_iterator&, const node_iterator&)
+
+void get_tail(node_iterator&, const edge_iterator&)
+void get_head(node_iterator&, const edge_iterator&)
+
+void get_a_node(node_iterator&, const out_edge_iterator&)
+void get_a_node(node_iterator&, const in_edge_iterator&)
+void get_a_node(node_iterator&, const sym_edge_iterator&)
+   
+void get_b_node(node_iterator&, const out_edge_iterator&)
+void get_b_node(node_iterator&, const in_edge_iterator&)
+void get_b_node(node_iterator&, const sym_edge_iterator&)
+ 
+void get_invalid(node_iterator&)
+void get_invalid(edge_iterator&)
+void get_invalid(out_edge_iterator&)
+void get_invalid(in_edge_iterator&)
+void get_invalid(sym_edge_iterator&)
+ 
+Pontok azonositasara de meginkabb property vectorokhoz:
+
+int id(const node_iterator&)
+int id(const edge_iterator&)
+
+Pontok es elek hozzaadasanak metodusai:
+
+node_iterator add_node()
+edge_iterator add_edge(const node_iterator&, const node_iterator&)
+
+Hogy konnyebb legyen a progikat tesztelni, nehany stream utasitas:
+ezek nem a list_graph metodusai
+
+friend std::ostream& operator<<(std::ostream&, const node_iterator&)
+friend std::ostream& operator<<(std::ostream&, const edge_iterator&)
+
+node_iterator metodusai:
+node_iterator()
+bool is_valid()
+ezek nem tagfuggvenyek:
+friend bool operator==(const node_iterator&, const node_iterator&)
+friend bool operator!=(const node_iterator& u, const node_iterator& v)
+    
+each_node_iterator metodusai:
+ez publikusan szarmazik a node_iterator-bol, tehat a fentiek is.
+each_node_iterator()
+each_node_iterator& operator++()
+
+edge_iterator metodusai:
+edge_iterator()
+bool is_valid()
+ezek nem tagfvek:
+friend bool operator==(const edge_iterator&, const edge_iterator&)
+friend bool operator!=(const edge_iterator&, const edge_iterator&)
+ujra tagfv-ek.
+//node_iterator tail_node() const		nem javasolt
+//node_iterator head_node() const		nem javasolt
+   
+each_edge_iterator metodusai:
+edge_iterator-bol szarmazik
+each_edge_iterator()
+each_edge_iterator& operator++()
+ 
+out_edge_iterator metodusai:
+edge_iterator-bol szarmazik
+out_edge_iterator()
+//out_edge_iterator(const node_iterator&)	nem javasolt
+out_edge_iterator& operator++()
+//node_iterator a_node() const		nem javasolt
+//node_iterator b_node() const 
+    
+ 
+in_edge_iterator metodusai: 
+edge_iterator-bol szarmazik
+in_edge_iterator()
+//in_edge_iterator(const node_iterator&)	nem javasolt
+in_edge_iterator& operator++()
+//node_iterator a_node() const		nem javasolt
+//node_iterator b_node() const 
+
+
+sym_edge_iterator metodusai:
+edge_iterator-bol szarmazik
+sym_edge_iterator()
+//sym_edge_iterator(const node_iterator&)	nem javasolt
+sym_edge_iterator& operator++()
+//node_iterator a_node() const		nem javasolt
+//node_iterator b_node() const 
+		
+Node propery array-okrol:
+
+template <typename graph_type, typename T>
+class node_property_vector 
+
+metodusok:
+
+node_property_vector(graph_type&)
+void put(graph_traits<graph_type>::node_iterator, const T&)
+T get(graph_traits<graph_type>::node_iterator)
+
+Ugyanez edge_property_array-okkal
+
+template <typename graph_type, typename T>
+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)
+
+ Ennyi nem javasolas utan, meg nehany szo.
+ Alparral ugy gondoltuk, hogy az iterator 1 olyan egyszeru objetum legyen 
+csak, mellyel, ha ervenyes, akkor lehet tovabblepni 1 pont vagy ellistaban. 
+Az hogy valamilyen pont-iteratorbeol el-iteratort csinalunk, igenis legyen a 
+graf objektum feladata, hiszen igy lehet csinelni ugyanazon a ponthalmazon
+tobb grafot ugyanazon pont-iteratorokkal.
+ Sokkal komolyabb kerdesek merultek fel azzal kapcsolatban, hogy hogyan adjuk 
+at a propertyket az algoritmusoknak, algoritmus-objektumoknak. 
+Errol majd kesobb.
+
+marci@cs.elte.hu
\ No newline at end of file
diff -r cd54905012bc -r a9ed3f1c2c63 src/work/marci_graph_demo.cc
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci_graph_demo.cc	Tue Dec 30 13:59:08 2003 +0000
@@ -0,0 +1,173 @@
+#include <iostream>
+#include <vector>
+#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>
+
+using namespace marci;
+
+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;
+
+  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());
+  for(int i=0; i!=8; ++i)
+    for(int j=0; j!=8; ++j) {
+      if ((i<j)&&(i+j)%3) G.add_edge(vector_of_node_iterators[i], vector_of_node_iterators[j]);
+    }  
+
+  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<each_node_iterator>(G.first_node()) << std::endl;
+
+  for(each_node_iterator i=G.first_node(); i.is_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) { 
+      std::cout << "(" << G.id(G.tail(j)) << "--" << G.id(j) << "->" << G.id(G.head(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) { 
+      std::cout << 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) { 
+      std::cout << j << " "; } 
+    std::cout<<std::endl;
+  }
+
+  std::cout << "all edges: ";
+  for(each_edge_iterator i=G.first_edge(); i.is_valid(); ++i) {
+    std::cout << i << " ";
+  }
+  std::cout << std::endl;
+
+  std::cout << "node property array test" << std::endl;
+  node_property_vector<list_graph, int> my_property_vector(G);
+  each_node_iterator v;
+  G.get_first(v);
+  my_property_vector.put(v, 42);
+  my_property_vector.put(++G.first_node(), 314);
+  my_property_vector.put(++++G.first_node(), 1956);
+  my_property_vector.put(vector_of_node_iterators[3], 1989);
+  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) {
+    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) {
+    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) {
+    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) {
+  //    std::cout << my_property_vector.get(G.tail(j)) << "-->" << my_property_vector.get(G.head(j)) << " ";
+  //  }
+  //  std::cout << std::endl;
+  //}
+
+  std::cout << "bfs from the first node" << std::endl;
+  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) {
+    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) {
+    std::cout << bfs_test.dist.get(i) << " ";
+  }
+  std::cout<<std::endl;
+
+
+  std::cout << "augmenting path flow algorithm test..." << std::endl;
+  list_graph flow_test;
+
+  node_iterator s=flow_test.add_node();
+  node_iterator v1=flow_test.add_node();
+  node_iterator v2=flow_test.add_node();
+  node_iterator v3=flow_test.add_node();
+  node_iterator v4=flow_test.add_node();
+  node_iterator t=flow_test.add_node();
+  
+  node_property_vector<list_graph, std::string> node_name(flow_test);
+  node_name.put(s, "s");
+  node_name.put(v1, "v1");
+  node_name.put(v2, "v2");
+  node_name.put(v3, "v3");
+  node_name.put(v4, "v4");
+  node_name.put(t, "t");
+
+  edge_iterator s_v1=flow_test.add_edge(s, v1);
+  edge_iterator s_v2=flow_test.add_edge(s, v2);
+  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
+  edge_iterator v2_v1=flow_test.add_edge(v2, v1);
+  edge_iterator v1_v3=flow_test.add_edge(v1, v3);
+  edge_iterator v3_v2=flow_test.add_edge(v3, v2);
+  edge_iterator v2_v4=flow_test.add_edge(v2, v4);
+  edge_iterator v4_v3=flow_test.add_edge(v4, v3);
+  edge_iterator v3_t=flow_test.add_edge(v3, t);
+  edge_iterator v4_t=flow_test.add_edge(v4, t);
+
+  edge_property_vector<list_graph, int> cap(flow_test);
+
+  cap.put(s_v1, 16);
+  cap.put(s_v2, 13);
+  cap.put(v1_v2, 10);
+  cap.put(v2_v1, 4);
+  cap.put(v1_v3, 12);
+  cap.put(v3_v2, 9);
+  cap.put(v2_v4, 14);
+  cap.put(v4_v3, 7);
+  cap.put(v3_t, 20);
+  cap.put(v4_t, 4);
+
+  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) { 
+    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) 
+      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) 
+      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) { 
+  //  std::cout << i << " ";
+  //}
+  
+  max_flow_type<list_graph, int> max_flow_test(flow_test, s, t, cap);
+  max_flow_test.run();
+
+  return 0;
+}
diff -r cd54905012bc -r a9ed3f1c2c63 src/work/marci_graph_traits.hh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci_graph_traits.hh	Tue Dec 30 13:59:08 2003 +0000
@@ -0,0 +1,19 @@
+#ifndef MARCI_GRAPH_TRAITS_HH
+#define MARCI_GRAPH_TRAITS_HH
+
+namespace marci {
+
+  template <typename graph_type>
+  struct graph_traits {
+    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::each_edge_iterator each_edge_iterator;
+    typedef typename graph_type::out_edge_iterator out_edge_iterator;
+    typedef typename graph_type::in_edge_iterator in_edge_iterator;
+    typedef typename graph_type::sym_edge_iterator sym_edge_iterator;
+  };
+
+} // namespace marci
+
+#endif //MARCI_GRAPH_TRAITS_HH
diff -r cd54905012bc -r a9ed3f1c2c63 src/work/marci_list_graph.hh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci_list_graph.hh	Tue Dec 30 13:59:08 2003 +0000
@@ -0,0 +1,334 @@
+#ifndef MARCI_LIST_GRAPH_HH
+#define MARCI_LIST_GRAPH_HH
+
+#include <iostream>
+
+namespace marci {
+
+  class list_graph {
+    class node_item;
+    class edge_item;
+  public:
+    class node_iterator;
+    class each_node_iterator;
+    class edge_iterator;
+    class each_edge_iterator;
+    class out_edge_iterator;
+    class in_edge_iterator;
+    class sym_edge_iterator;
+  private:
+    int node_id;
+    int edge_id;
+
+    node_item* _first_node;
+    node_item* _last_node;
+
+    class node_item {
+      friend class list_graph;
+      friend class node_iterator;
+      friend class each_node_iterator;
+      friend class edge_iterator;
+      friend class each_edge_iterator;
+      friend class out_edge_iterator;
+      friend class in_edge_iterator;
+      friend class sym_edge_iterator;
+      friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
+      friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
+      list_graph* G;
+      int id;
+      edge_item* _first_out_edge;
+      edge_item* _last_out_edge;
+      edge_item* _first_in_edge;
+      edge_item* _last_in_edge;
+      node_item* _next_node;
+      node_item* _prev_node;
+    public:
+      node_item() { }
+    };
+
+    class edge_item {
+      friend class list_graph;
+      friend class node_iterator;
+      friend class each_node_iterator;
+      friend class edge_iterator;
+      friend class each_edge_iterator;
+      friend class out_edge_iterator;
+      friend class in_edge_iterator;
+      friend class sym_edge_iterator;
+      friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
+      list_graph* G;
+      int id;
+      node_item* _tail;
+      node_item* _head;
+      edge_item* _next_out;
+      edge_item* _prev_out;
+      edge_item* _next_in;
+      edge_item* _prev_in;
+    public:
+      edge_item() { }
+    };
+
+    node_item* _add_node() { 
+      node_item* p=new node_item;
+      p->id=node_id++;
+      p->_first_out_edge=0;
+      p->_last_out_edge=0;
+      p->_first_in_edge=0;
+      p->_last_in_edge=0;
+      p->_prev_node=_last_node;
+      p->_next_node=0;
+      if (_last_node) _last_node->_next_node=p;
+      _last_node=p;
+      if (!_first_node) _first_node=p;
+      return p;
+    }
+
+    edge_item* _add_edge(node_item* _tail, node_item* _head) {
+      edge_item* e=new edge_item;
+      e->id=edge_id++;
+      e->_tail=_tail;
+      e->_head=_head;
+      
+      e->_prev_out=_tail->_last_out_edge;
+      if (_tail->_last_out_edge) (_tail->_last_out_edge)->_next_out=e;
+      _tail->_last_out_edge=e;
+      if (!_tail->_first_out_edge) _tail->_first_out_edge=e; 
+       
+      e->_prev_in=_head->_last_in_edge;
+      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; } 
+      return e;
+    }
+
+  public:
+
+    /* default constructor */
+
+    list_graph() : node_id(0), edge_id(0), _first_node(0), _last_node(0) { }
+    
+    /* functions to construct iterators from the graph, or from each other */
+
+    each_node_iterator first_node() { return each_node_iterator(_first_node); }
+    each_edge_iterator first_edge() { 
+      node_item* v=_first_node;
+      edge_item* edge=v->_first_out_edge;
+      while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
+      return each_edge_iterator(v, edge); 
+    }
+    
+    out_edge_iterator first_out_edge(const node_iterator& v) { 
+      return out_edge_iterator(v); 
+    }
+    in_edge_iterator first_in_edge(const node_iterator& v) { 
+      return in_edge_iterator(v); 
+    }
+    sym_edge_iterator first_sym_edge(const node_iterator& v) { 
+      return sym_edge_iterator(v); 
+    }
+    node_iterator tail(const edge_iterator& e) { return e.tail_node(); }
+    node_iterator head(const edge_iterator& e) { return e.head_node(); }
+
+    node_iterator a_node(const out_edge_iterator& e) { return e.a_node(); }
+    node_iterator a_node(const in_edge_iterator& e) { return e.a_node(); }
+    node_iterator a_node(const sym_edge_iterator& e) { return e.a_node(); }
+
+    node_iterator b_node(const out_edge_iterator& e) { return e.b_node(); }
+    node_iterator b_node(const in_edge_iterator& e) { return e.b_node(); }
+    node_iterator b_node(const sym_edge_iterator& e) { return e.b_node(); }
+
+    node_iterator invalid_node() { return node_iterator(); }
+    edge_iterator invalid_edge() { return edge_iterator(); }
+    out_edge_iterator invalid_out_edge() { return out_edge_iterator(); }
+    in_edge_iterator invalid_in_edge() { return in_edge_iterator(); }
+    sym_edge_iterator invalid_sym_edge() { return sym_edge_iterator(); }
+
+    /* same methods in other style */
+    /* for experimental purpose */
+
+    void get_first(each_node_iterator& v) { v=each_node_iterator(_first_node); }
+    void get_first(each_edge_iterator& e) { e=first_edge(); }
+    void get_first(out_edge_iterator& e, const node_iterator& v) { 
+      e=out_edge_iterator(v); 
+    }
+    void get_first(in_edge_iterator& e, const node_iterator& v) { 
+      e=in_edge_iterator(v); 
+    }
+    void get_first(sym_edge_iterator& e, const node_iterator& v) { 
+      e=sym_edge_iterator(v); 
+    }
+    void get_tail(node_iterator& n, const edge_iterator& e) { n=tail(e); }
+    void get_head(node_iterator& n, const edge_iterator& e) { n=head(e); }
+
+    void get_a_node(node_iterator& n, const out_edge_iterator& e) { n=e.a_node(); }
+    void get_a_node(node_iterator& n, const in_edge_iterator& e) { n=e.a_node(); }
+    void get_a_node(node_iterator& n, const sym_edge_iterator& e) { n=e.a_node(); }
+    void get_b_node(node_iterator& n, const out_edge_iterator& e) { n=e.b_node(); }
+    void get_b_node(node_iterator& n, const in_edge_iterator& e) { n=e.b_node(); }
+    void get_b_node(node_iterator& n, const sym_edge_iterator& e) { n=e.b_node(); }
+    void get_invalid(node_iterator& n) { n=node_iterator(); }
+    void get_invalid(edge_iterator& e) { e=edge_iterator(); }
+    void get_invalid(out_edge_iterator& e) { e=out_edge_iterator(); }
+    void get_invalid(in_edge_iterator& e) { e=in_edge_iterator(); }
+    void get_invalid(sym_edge_iterator& e) { e=sym_edge_iterator(); }
+
+
+    /* for getting id's of graph objects */
+    /* these are important for the implementation of property vectors */
+
+    int id(const node_iterator& v) { return v.node->id; }
+    int id(const edge_iterator& e) { return e.edge->id; }
+
+    /* adding nodes and edges */
+
+    node_iterator add_node() { return node_iterator(_add_node()); }
+    edge_iterator add_edge(const node_iterator& u, const node_iterator& v) {
+      return edge_iterator(_add_edge(u.node, v.node)); 
+    }
+
+    /* stream operations, for testing purpose */
+
+    friend std::ostream& operator<<(std::ostream& os, const node_iterator& i) { 
+      os << i.node->id; return os; 
+    }
+    friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i) { 
+      os << "(" << i.edge->_tail->id << "--" << i.edge->id << "->" << i.edge->_head->id << ")"; 
+      return os; 
+    }
+
+    class node_iterator {
+      friend class list_graph;
+
+      friend class edge_iterator;
+      friend class out_edge_iterator;
+      friend class in_edge_iterator;
+      friend class sym_edge_iterator;
+    protected:
+      node_item* node;
+      friend int list_graph::id(const node_iterator& v); 
+    public:
+      node_iterator() : node(0) { }
+      node_iterator(node_item* _node) : node(_node) { }
+      bool is_valid() { return (node!=0); }
+      friend bool operator==(const node_iterator& u, const node_iterator& v) { 
+	return v.node==u.node; 
+      } 
+      friend bool operator!=(const node_iterator& u, const node_iterator& v) { 
+	return v.node!=u.node; 
+      } 
+      friend std::ostream& operator<<(std::ostream& os, const node_iterator& i);
+    };
+    
+    class each_node_iterator : public node_iterator {
+      friend class list_graph;
+    public:
+      each_node_iterator() : node_iterator() { }
+      each_node_iterator(node_item* v) : node_iterator(v) { }
+      each_node_iterator& operator++() { node=node->_next_node; return *this; }
+    };
+
+    class edge_iterator {
+      friend class list_graph;
+      
+      friend class node_iterator;
+      friend class each_node_iterator;
+    protected:
+      edge_item* edge;
+      friend int list_graph::id(const edge_iterator& e);
+    public:
+      edge_iterator() : edge(0) { }
+      edge_iterator(edge_item* _edge) : edge(_edge) { }
+      bool is_valid() { return (edge!=0); }
+      friend bool operator==(const edge_iterator& u, const edge_iterator& v) { 
+	return v.edge==u.edge; 
+      } 
+      friend bool operator!=(const edge_iterator& u, const edge_iterator& v) { 
+	return v.edge!=u.edge; 
+      } 
+    protected:
+      node_iterator tail_node() const { return node_iterator(edge->_tail); }
+      node_iterator head_node() const { return node_iterator(edge->_head); }
+    public:
+      friend std::ostream& operator<<(std::ostream& os, const edge_iterator& i);
+    };
+    
+    class each_edge_iterator : public edge_iterator {
+      friend class list_graph;
+      node_item* v;
+    public:
+      each_edge_iterator() : edge_iterator(), v(0) { }
+      each_edge_iterator(node_item* _v, edge_item* _e) : edge_iterator(_e), v(_v) { }
+      each_edge_iterator& operator++() { 
+	edge=edge->_next_out; 
+	while (v && !edge) { v=v->_next_node; if (v) edge=v->_first_out_edge; }
+	return *this;
+      }
+    };
+    
+    class out_edge_iterator : public edge_iterator {
+      friend class list_graph;
+      node_item* v;
+    public:
+      out_edge_iterator() : edge_iterator(), v(0) { }
+    protected:
+      out_edge_iterator(const node_iterator& _v) : v(_v.node) { edge=v->_first_out_edge; }
+    public:
+      out_edge_iterator& operator++() { edge=edge->_next_out; return *this; }
+    protected:
+      node_iterator a_node() const { return node_iterator(v); }
+      node_iterator b_node() const { 
+	return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(v); }
+    };
+    
+    class in_edge_iterator : public edge_iterator {
+      friend class list_graph;
+      node_item* v;
+    public:
+      in_edge_iterator() : edge_iterator(), v(0) { }
+    protected:
+      in_edge_iterator(const node_iterator& _v) : v(_v.node) { 
+	edge=v->_first_in_edge; 
+      }
+    public:
+      in_edge_iterator& operator++() { edge=edge->_next_in; return *this; }
+    protected:
+      node_iterator a_node() const { return node_iterator(v); }
+      node_iterator b_node() const { 
+	return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(v); }
+    };
+
+    class sym_edge_iterator : public edge_iterator {
+      friend class list_graph;
+      bool out_or_in; //1 iff out, 0 iff in
+      node_item* v;
+    public:
+      sym_edge_iterator() : edge_iterator(), v(0) { }
+    protected:
+      sym_edge_iterator(const node_iterator& _v) : v(_v.node) { 
+	out_or_in=1;
+	edge=v->_first_out_edge; 
+	if (!edge) { edge=v->_first_in_edge; out_or_in=0; }
+      }
+    public:
+      sym_edge_iterator& operator++() { 
+	if (out_or_in) { 
+	  edge=edge->_next_out; 
+	  if (!edge) { out_or_in=0; edge=v->_first_in_edge; }
+	} else {
+	  edge=edge->_next_in; 
+	}
+	return *this;
+      }
+    protected:
+      node_iterator a_node() const { return node_iterator(v); }
+      node_iterator b_node() const { 
+	return (edge->_tail==v) ? node_iterator(edge->_head) : node_iterator(v); }
+    };
+
+  };
+
+
+
+} //namespace marci
+
+#endif //MARCI_LIST_GRAPH_HH
diff -r cd54905012bc -r a9ed3f1c2c63 src/work/marci_makefile
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci_makefile	Tue Dec 30 13:59:08 2003 +0000
@@ -0,0 +1,5 @@
+CCFLAGS = -Wall -ansi
+CC = /opt/experimental/bin/g++
+
+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
diff -r cd54905012bc -r a9ed3f1c2c63 src/work/marci_max_flow.hh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci_max_flow.hh	Tue Dec 30 13:59:08 2003 +0000
@@ -0,0 +1,230 @@
+#ifndef MARCI_MAX_FLOW_HH
+#define MARCI_MAX_FLOW_HH
+
+#include <algorithm>
+
+#include <marci_graph_traits.hh>
+#include <marci_property_vector.hh>
+#include <marci_bfs.hh>
+
+namespace marci {
+
+  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;
+
+    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 {
+      friend class res_graph_type<graph_type, T>;
+    protected:
+      res_graph_type<graph_type, T>* resG;
+      sym_edge_iterator sym;
+    public:
+      res_edge_it() { }
+      //bool is_free() {  
+      //if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
+      //  return (resG->flow.get(sym)<resG->capacity.get(sym)); 
+      //} else { 
+      //  return (resG->flow.get(sym)>0); 
+      //}
+      //}
+      T free() { 
+	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
+	  return (resG->capacity.get(sym)-resG->flow.get(sym)); 
+	} else { 
+	  return (resG->flow.get(sym)); 
+	}
+      }
+      bool is_valid() { return sym.is_valid(); }
+      void augment(T a) {
+	if (resG->G.a_node(sym)==resG->G.tail(sym)) { 
+	  resG->flow.put(sym, resG->flow.get(sym)+a);
+	} else { 
+	  resG->flow.put(sym, resG->flow.get(sym)-a);
+	}
+      }
+    };
+
+    class res_out_edge_it : public res_edge_it {
+    public:
+      res_out_edge_it() { }
+      res_out_edge_it(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; }
+      }
+      res_out_edge_it& operator++() { 
+	++sym; 
+	while( sym.is_valid() && !(free()>0) ) { ++sym; }
+	return *this; 
+      }
+    };
+
+    res_out_edge_it first_out_edge(const node_iterator& v) {
+      return res_out_edge_it(*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); }
+
+    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;
+  };
+
+  template <typename graph_type, typename pred_type, typename free_type>
+  struct flow_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;
+    graph_type& G;
+    pred_type& pred;
+    free_type& free;
+    flow_visitor(graph_type& _G, pred_type& _pred, free_type& _free) : G(_G), pred(_pred), free(_free) { }
+    void at_previously_reached(out_edge_iterator& e) { 
+      //node_iterator v=G.tail(e);
+      //node_iterator w=G.head(e);
+      //std::cout<<G.id(v)<<"->"<<G.id(w)<<", "<<G.id(w)<<" is already reached";
+      //std::cout<<std::endl;
+   }
+    void at_newly_reached(out_edge_iterator& e) { 
+      node_iterator v=G.tail(e);
+      node_iterator w=G.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()) {
+	free.put(w, std::min(free.get(v), e.free()));
+	//std::cout <<" nem elso csucs: ";
+	//std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
+      } else {
+	free.put(w, e.free()); 
+	//std::cout <<" elso csucs: ";
+	//std::cout <<"szabad kap eddig: "<< free.get(w) << " ";
+      }
+      //std::cout<<std::endl;
+    }
+  };
+
+  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;
+
+    graph_type& G;
+    node_iterator s;
+    node_iterator t;
+    edge_property_vector<graph_type, T> flow;
+    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) 
+	  flow.put(j, 0);
+    }
+    void run() {
+      typedef res_graph_type<graph_type, T> aug_graph_type;
+      aug_graph_type res_graph(G, flow, capacity);
+
+      typedef std::queue<graph_traits<aug_graph_type>::out_edge_iterator> bfs_queue_type;
+      bfs_queue_type bfs_queue;
+      //bfs_queue.push(res_graph.first_out_edge(s));
+
+      typedef node_property_vector<aug_graph_type, bool> reached_type;
+      //reached_type reached(res_graph, false);
+      reached_type reached(res_graph);
+      //reached.put(s, true);
+
+      typedef node_property_vector<aug_graph_type, graph_traits<aug_graph_type>::edge_iterator> pred_type;
+      pred_type pred(res_graph);
+      pred.put(s, res_graph.invalid_edge());
+      
+      typedef node_property_vector<aug_graph_type, int> free_type;
+      free_type free(res_graph);
+
+      typedef flow_visitor<aug_graph_type, pred_type, free_type> visitor_type;
+      visitor_type vis(res_graph, pred, free);
+      
+      bfs_iterator< aug_graph_type, reached_type, visitor_type > 
+	res_bfs(res_graph, bfs_queue, reached, vis);
+
+      //for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { 
+      //for(graph_traits<aug_graph_type>::out_edge_iterator j=res_graph.first_out_edge(i); j.is_valid(); ++j) {
+      //  std::cout<<"("<<res_graph.tail(j)<< "->"<<res_graph.head(j)<<") ";
+      //}
+      //}
+      //std::cout<<std::endl;
+
+      //char c; 
+      bool augment;
+      do {
+	augment=false;
+	
+	while (!bfs_queue.empty()) { bfs_queue.pop(); }
+	bfs_queue.push(res_graph.first_out_edge(s));
+	
+	for(graph_traits<aug_graph_type>::each_node_iterator i=res_graph.first_node(); i.is_valid(); ++i) { reached.put(i, false); }
+	reached.put(s, true); 
+	
+	//searching for augmenting path
+	while ( /*std::cin>>c &&*/ res_bfs.is_valid() ) { 
+	  res_bfs.process(); 
+	  //if (res_graph.head(graph_traits<aug_graph_type>::out_edge_iterator(res_bfs))==t) break;
+	  if (res_graph.head(res_bfs)==t) break;
+	  //res_bfs.next();
+	  ++res_bfs;
+	}
+	//for (; std::cin>>c && !res_bfs.finished() && res_graph.head(res_bfs.current())!=t; res_bfs.next()) { res_bfs.process(); } 
+	if (reached.get(t)) {
+	  augment=true;
+	  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);
+	    e.augment(augment_value); 
+	    std::cout<<"("<<res_graph.tail(e)<< "->"<<res_graph.head(e)<<") ";
+	    n=res_graph.tail(e);
+	  }
+	  std::cout<<std::endl;
+	}
+
+	std::cout << "max flow:"<< std::endl;
+	for(graph_traits<graph_type>::each_edge_iterator e=G.first_edge(); e.is_valid(); ++e) { 
+	  std::cout<<"("<<G.tail(e)<< "-"<<flow.get(e)<<"->"<<G.head(e)<<") ";
+	}
+	std::cout<<std::endl;
+
+      } while (augment);
+    }
+  };
+
+} // namespace marci
+
+#endif //MARCI_MAX_FLOW_HH
diff -r cd54905012bc -r a9ed3f1c2c63 src/work/marci_property_vector.hh
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/marci_property_vector.hh	Tue Dec 30 13:59:08 2003 +0000
@@ -0,0 +1,59 @@
+#ifndef MARCI_PROPERTY_VECTOR_HH
+#define MARCI_PROPERTY_VECTOR_HH
+
+#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; } 
+    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;
+    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;
+      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); }
+    }
+    void put(node_iterator nit, const T& a) { container[G.id(nit)]=a; }
+    T get(node_iterator nit) { return container[G.id(nit)]; }
+  };
+
+  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;
+    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;
+      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) { 
+	container.push_back(a); 
+      }
+    }
+    void put(edge_iterator eit, const T& a) { container[G.id(eit)]=a; }
+    T get(edge_iterator eit) { return container[G.id(eit)]; }
+  };
+
+} // namespace marci
+
+#endif //MARCI_PROPERTY_VECTOR_HH