# HG changeset patch
# User jacint
# Date 1076948158 0
# Node ID ecc1171307be71581c8e0886acf8507e382fa595
# Parent  69b2d279c8f078b08e8e5e68fbfe250febf98f19
modern valtozat

diff -r 69b2d279c8f0 -r ecc1171307be src/work/jacint/dijkstra.hh
--- a/src/work/jacint/dijkstra.hh	Mon Feb 16 15:57:59 2004 +0000
+++ b/src/work/jacint/dijkstra.hh	Mon Feb 16 16:15:58 2004 +0000
@@ -1,11 +1,11 @@
 /*
  *dijkstra
  *by jacint
- *Performs Dijkstra's algorithm from node s. 
+ *Performs Dijkstra's algorithm from Node s. 
  *
  *Constructor: 
  *
- *dijkstra(graph_type& G, node_iterator s, edge_property_vector& distance)
+ *dijkstra(graph_type& G, NodeIt s, EdgeMap& distance)
  *
  *
  *
@@ -16,17 +16,17 @@
  *  The following function should be used after run() was already run.
  *
  *
- *T dist(node_iterator v) : returns the distance from s to v. 
+ *T dist(NodeIt v) : returns the distance from s to v. 
  *   It is 0 if v is not reachable from s.
  *
  *
- *edge_iterator pred(node_iterator v)
- *   Returns the last edge of a shortest s-v path. 
+ *EdgeIt pred(NodeIt v)
+ *   Returns the last Edge of a shortest s-v path. 
  *   Returns an invalid iterator if v=s or v is not
  *   reachable from s.
  *
  *
- *bool reach(node_iterator v) : true if v is reachable from s
+ *bool reach(NodeIt v) : true if v is reachable from s
  *
  *
  *
@@ -48,7 +48,7 @@
 #include <algorithm>
 
 #include <marci_graph_traits.hh>
-#include <marci_property_vector.hh>
+#include <marciMap.hh>
 
 
 namespace std {
@@ -60,37 +60,37 @@
 
     template <typename graph_type, typename T>
     class dijkstra{
-      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>::in_edge_iterator in_edge_iterator;
-      typedef typename graph_traits<graph_type>::out_edge_iterator out_edge_iterator;
+      typedef typename graph_traits<graph_type>::NodeIt NodeIt;
+      typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
+      typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
+      typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
+      typedef typename graph_traits<graph_type>::OutEdgeIt OutEdgeIt;
       
       
       graph_type& G;
-      node_iterator s;
-      node_property_vector<graph_type, edge_iterator> predecessor;
-      node_property_vector<graph_type, T> distance;
-      edge_property_vector<graph_type, T> length;
-      node_property_vector<graph_type, bool> reached;
+      NodeIt s;
+      NodeMap<graph_type, EdgeIt> predecessor;
+      NodeMap<graph_type, T> distance;
+      EdgeMap<graph_type, T> length;
+      NodeMap<graph_type, bool> reached;
           
   public :
 
     /*
-      The distance of all the nodes is 0.
+      The distance of all the Nodes is 0.
     */
-    dijkstra(graph_type& _G, node_iterator _s, edge_property_vector<graph_type, T>& _length) : 
+    dijkstra(graph_type& _G, NodeIt _s, EdgeMap<graph_type, T>& _length) : 
       G(_G), s(_s), predecessor(G, 0), distance(G, 0), length(_length), reached(G, false) { }
     
 
       
       /*By Misi.*/
-      struct node_dist_comp
+      struct Node_dist_comp
       {
-	node_property_vector<graph_type, T> &d;
-	node_dist_comp(node_property_vector<graph_type, T> &_d) : d(_d) {} 
+	NodeMap<graph_type, T> &d;
+	Node_dist_comp(NodeMap<graph_type, T> &_d) : d(_d) {} 
 	
-	bool operator()(const node_iterator& u, const node_iterator& v) const 
+	bool operator()(const NodeIt& u, const NodeIt& v) const 
 	{ return d.get(u) < d.get(v); }
       };
 
@@ -98,23 +98,23 @@
       
       void run() {
 	
-	node_property_vector<graph_type, bool> scanned(G, false);
-	std::priority_queue<node_iterator, vector<node_iterator>, node_dist_comp> 
-	  heap(( node_dist_comp(distance) ));
+	NodeMap<graph_type, bool> scanned(G, false);
+	std::priority_queue<NodeIt, vector<NodeIt>, Node_dist_comp> 
+	  heap(( Node_dist_comp(distance) ));
       
 	heap.push(s);
 	reached.put(s, true);
 
 	while (!heap.empty()) {
 
-	  node_iterator v=heap.top();	
+	  NodeIt v=heap.top();	
 	  heap.pop();
 
 
 	  if (!scanned.get(v)) {
 	
-	    for(out_edge_iterator e=G.first_out_edge(v); e.valid(); ++e) {
-	      node_iterator w=G.head(e);
+	    for(OutEdgeIt e=G.template first<OutEdgeIt>(v); e.valid(); ++e) {
+	      NodeIt w=G.head(e);
 
 	      if (!scanned.get(w)) {
 		if (!reached.get(w)) {
@@ -147,29 +147,29 @@
 
 
       /*
-       *Returns the distance of the node v.
-       *It is 0 for the root and for the nodes not
+       *Returns the distance of the Node v.
+       *It is 0 for the root and for the Nodes not
        *reachable form the root.
        */      
-      T dist(node_iterator v) {
+      T dist(NodeIt v) {
 	return -distance.get(v);
       }
 
 
 
       /*
-       *  Returns the last edge of a shortest s-v path. 
+       *  Returns the last Edge of a shortest s-v path. 
        *  Returns an invalid iterator if v=root or v is not
        *  reachable from the root.
        */      
-      edge_iterator pred(node_iterator v) {
+      EdgeIt pred(NodeIt v) {
 	if (v!=s) { return predecessor.get(v);}
-	else {return edge_iterator();}
+	else {return EdgeIt();}
       }
      
 
       
-      bool reach(node_iterator v) {
+      bool reach(NodeIt v) {
 	return reached.get(v);
       }
 
diff -r 69b2d279c8f0 -r ecc1171307be src/work/jacint/flow_test.cc
--- a/src/work/jacint/flow_test.cc	Mon Feb 16 15:57:59 2004 +0000
+++ b/src/work/jacint/flow_test.cc	Mon Feb 16 16:15:58 2004 +0000
@@ -2,150 +2,147 @@
 #include <vector>
 #include <string>
 
-#include <marci_list_graph.hh>
-#include <marci_graph_traits.hh>
-#include <marci_property_vector.hh>
-#include <preflow_push_hl.hh>
-#include <preflow_push_max_flow.hh>
-#include <reverse_bfs.hh>
-//#include <dijkstra.hh>
+#include <list_graph.hh>
+#include <preflow_push_hl.h>
+#include <preflow_push_max_flow.h>
+#include <reverse_bfs.h>
+//#include <dijkstra.h>
 
 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 flow_test;
+  typedef ListGraph::NodeIt NodeIt;
+  typedef ListGraph::EdgeIt EdgeIt;
+  typedef ListGraph::EachNodeIt EachNodeIt;
+  typedef ListGraph::EachEdgeIt EachEdgeIt;
+  typedef ListGraph::OutEdgeIt OutEdgeIt;
+  typedef ListGraph::InEdgeIt InEdgeIt;
+  
+  ListGraph flow_test;
  
     //Ahuja könyv példája, maxflowvalue=13
-  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 v5=flow_test.add_node();
-  node_iterator t=flow_test.add_node();
+  NodeIt s=flow_test.addNode();
+  NodeIt v1=flow_test.addNode();
+  NodeIt v2=flow_test.addNode();
+  NodeIt v3=flow_test.addNode();
+  NodeIt v4=flow_test.addNode();
+  NodeIt v5=flow_test.addNode();
+  NodeIt t=flow_test.addNode();
   
-  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(v5, "v5");
-  node_name.put(t, "t");
+  ListGraph::NodeMap<std::string> Node_name(flow_test);
+  Node_name.set(s, "s");
+  Node_name.set(v1, "v1");
+  Node_name.set(v2, "v2");
+  Node_name.set(v3, "v3");
+  Node_name.set(v4, "v4");
+  Node_name.set(v5, "v5");
+  Node_name.set(t, "t");
 
-  edge_iterator s_v1=flow_test.add_edge(s, v1);
-  edge_iterator s_v2=flow_test.add_edge(s, v2);
-  edge_iterator s_v3=flow_test.add_edge(s, v3);
-  edge_iterator v2_v4=flow_test.add_edge(v2, v4);
-  edge_iterator v2_v5=flow_test.add_edge(v2, v5);
-  edge_iterator v3_v5=flow_test.add_edge(v3, v5);
-  edge_iterator v4_t=flow_test.add_edge(v4, t);
-  edge_iterator v5_t=flow_test.add_edge(v5, t);
-  edge_iterator v2_s=flow_test.add_edge(v2, s);
+  EdgeIt s_v1=flow_test.addEdge(s, v1);
+  EdgeIt s_v2=flow_test.addEdge(s, v2);
+  EdgeIt s_v3=flow_test.addEdge(s, v3);
+  EdgeIt v2_v4=flow_test.addEdge(v2, v4);
+  EdgeIt v2_v5=flow_test.addEdge(v2, v5);
+  EdgeIt v3_v5=flow_test.addEdge(v3, v5);
+  EdgeIt v4_t=flow_test.addEdge(v4, t);
+  EdgeIt v5_t=flow_test.addEdge(v5, t);
+  EdgeIt v2_s=flow_test.addEdge(v2, s);
   
-  edge_property_vector<list_graph, int> cap(flow_test);  
-  cap.put(s_v1, 0);
-  cap.put(s_v2, 10);
-  cap.put(s_v3, 10);
-  cap.put(v2_v4, 5);
-  cap.put(v2_v5, 8);
-  cap.put(v3_v5, 5);
-  cap.put(v4_t, 8);
-  cap.put(v5_t, 8);
-  cap.put(v2_s, 0);
+   ListGraph::EdgeMap<int> cap(flow_test);  
+  cap.set(s_v1, 0);
+  cap.set(s_v2, 10);
+  cap.set(s_v3, 10);
+  cap.set(v2_v4, 5);
+  cap.set(v2_v5, 8);
+  cap.set(v3_v5, 5);
+  cap.set(v4_t, 8);
+  cap.set(v5_t, 8);
+  cap.set(v2_s, 0);
 
 
   
   //Marci példája, maxflowvalue=23
-  /*  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_iterator w=flow_test.add_node();
+  /*  NodeIt s=flow_test.addNode();
+  NodeIt v1=flow_test.addNode();
+  NodeIt v2=flow_test.addNode();
+  NodeIt v3=flow_test.addNode();
+  NodeIt v4=flow_test.addNode();
+  NodeIt t=flow_test.addNode();
+  NodeIt w=flow_test.addNode();
 
   
-  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");
-  node_name.put(w, "w");
+  NodeMap<ListGraph, std::string> Node_name(flow_test);
+  Node_name.set(s, "s");
+  Node_name.set(v1, "v1");
+  Node_name.set(v2, "v2");
+  Node_name.set(v3, "v3");
+  Node_name.set(v4, "v4");
+  Node_name.set(t, "t");
+  Node_name.set(w, "w");
 
-  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_iterator v3_v3=flow_test.add_edge(v3, v3);
-  edge_iterator s_w=flow_test.add_edge(s, w);
-  //  edge_iterator v2_s=flow_test.add_edge(v2, s);
+  EdgeIt s_v1=flow_test.addEdge(s, v1);
+  EdgeIt s_v2=flow_test.addEdge(s, v2);
+  EdgeIt v1_v2=flow_test.addEdge(v1, v2);
+  EdgeIt v2_v1=flow_test.addEdge(v2, v1);
+  EdgeIt v1_v3=flow_test.addEdge(v1, v3);
+  EdgeIt v3_v2=flow_test.addEdge(v3, v2);
+  EdgeIt v2_v4=flow_test.addEdge(v2, v4);
+  EdgeIt v4_v3=flow_test.addEdge(v4, v3);
+  EdgeIt v3_t=flow_test.addEdge(v3, t);
+  EdgeIt v4_t=flow_test.addEdge(v4, t);
+  EdgeIt v3_v3=flow_test.addEdge(v3, v3);
+  EdgeIt s_w=flow_test.addEdge(s, w);
+  //  EdgeIt v2_s=flow_test.addEdge(v2, s);
   
 
 
-  edge_property_vector<list_graph, int> cap(flow_test);  //serves as length in dijkstra
-  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);
-  cap.put(v3_v3, 4);
-  cap.put(s_w, 4);
-  //  cap.put(v2_s, 0);
+  EdgeMap<ListGraph, int> cap(flow_test);  //serves as length in dijkstra
+  cap.set(s_v1, 16);
+  cap.set(s_v2, 13);
+  cap.set(v1_v2, 10);
+  cap.set(v2_v1, 4);
+  cap.set(v1_v3, 12);
+  cap.set(v3_v2, 9);
+  cap.set(v2_v4, 14);
+  cap.set(v4_v3, 7);
+  cap.set(v3_t, 20);
+  cap.set(v4_t, 4);
+  cap.set(v3_v3, 4);
+  cap.set(s_w, 4);
+  //  cap.set(v2_s, 0);
 
 */
 
   //pelda 3, maxflowvalue=4
-  /*      node_iterator s=flow_test.add_node();
-  node_iterator v1=flow_test.add_node();
-  node_iterator v2=flow_test.add_node();
-  node_iterator t=flow_test.add_node();
-  node_iterator w=flow_test.add_node();
+  /*      NodeIt s=flow_test.addNode();
+  NodeIt v1=flow_test.addNode();
+  NodeIt v2=flow_test.addNode();
+  NodeIt t=flow_test.addNode();
+  NodeIt w=flow_test.addNode();
   
-  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(t, "t");
-  node_name.put(w, "w");
+  NodeMap<ListGraph, std::string> Node_name(flow_test);
+  Node_name.set(s, "s");
+  Node_name.set(v1, "v1");
+  Node_name.set(v2, "v2");
+  Node_name.set(t, "t");
+  Node_name.set(w, "w");
 
-  edge_iterator s_v1=flow_test.add_edge(s, v1);
-  edge_iterator v1_v2=flow_test.add_edge(v1, v2);
-  edge_iterator v2_t=flow_test.add_edge(v2, t);
-  edge_iterator v1_v1=flow_test.add_edge(v1, v1);
-  edge_iterator s_w=flow_test.add_edge(s, w);
+  EdgeIt s_v1=flow_test.addEdge(s, v1);
+  EdgeIt v1_v2=flow_test.addEdge(v1, v2);
+  EdgeIt v2_t=flow_test.addEdge(v2, t);
+  EdgeIt v1_v1=flow_test.addEdge(v1, v1);
+  EdgeIt s_w=flow_test.addEdge(s, w);
 
 
-  edge_property_vector<list_graph, int> cap(flow_test); 
+  EdgeMap<ListGraph, int> cap(flow_test); 
     
-  cap.put(s_v1, 16);
-  cap.put(v1_v2, 10);
-  cap.put(v2_t, 4);
-  cap.put(v1_v1, 3);
-  cap.put(s_w, 5);
+  cap.set(s_v1, 16);
+  cap.set(v1_v2, 10);
+  cap.set(v2_t, 4);
+  cap.set(v1_v1, 3);
+  cap.set(s_w, 5);
   */
   
 
@@ -153,11 +150,11 @@
   /*
   std::cout << "Testing reverse_bfs..." << std::endl;
   
-  reverse_bfs<list_graph> bfs_test(flow_test, t);
+  reverse_bfs<ListGraph> bfs_test(flow_test, t);
 
   bfs_test.run();
 
-  for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
+  for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
     std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
     }
 
@@ -167,24 +164,24 @@
 
   std::cout << "Testing preflow_push_hl..." << std::endl;
   
-  preflow_push_hl<list_graph, int> preflow_push_test(flow_test, s, t, cap);
+  preflow_push_hl<ListGraph, int> preflow_push_test(flow_test, s, t, cap);
 
   preflow_push_test.run();
 
   std::cout << "Maximum flow value is: " << preflow_push_test.maxflow() << "."<<std::endl;
 
-  std::cout<< "The flow on edge s-v1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl;
+  std::cout<< "The flow on Edge s-v1 is "<< preflow_push_test.flowonEdge(s_v1) << "."<<std::endl;
 
-  edge_property_vector<list_graph, int> flow=preflow_push_test.allflow();  
-  for (each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) {
-    std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
+   ListGraph::EdgeMap<int> flow=preflow_push_test.allflow();  
+  for (EachEdgeIt e=flow_test.template first<EachEdgeIt>(); e.valid(); ++e) {
+    std::cout <<"Flow on Edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
     }
 
   std::cout << "A minimum cut: " <<std::endl;  
-  node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut();
+   ListGraph::NodeMap<bool> mincut=preflow_push_test.mincut();
 
-  for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
-      if (mincut.get(v)) std::cout <<node_name.get(v)<< " ";
+  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
+      if (mincut.get(v)) std::cout <<Node_name.get(v)<< " ";
     }
   
   std::cout<<"\n\n"<<std::endl;
@@ -194,17 +191,17 @@
 
   std::cout << "Testing preflow_push_max_flow..." << std::endl;
  
-  preflow_push_max_flow<list_graph, int> max_flow_test(flow_test, s, t, cap);
+  preflow_push_max_flow<ListGraph, int> max_flow_test(flow_test, s, t, cap);
 
   max_flow_test.run();
 
   std::cout << "Maximum flow value is: " << max_flow_test.maxflow() << "."<< std::endl;
 
   std::cout << "A minimum cut: " <<std::endl;  
-  node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut();
+   ListGraph::NodeMap<bool> mincut2=max_flow_test.mincut();
 
-  for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
-    if (mincut2.get(v)) std::cout <<node_name.get(v)<< " ";
+  for (EachNodeIt v=flow_test.template first<EachNodeIt>(); v.valid(); ++v) {
+    if (mincut2.get(v)) std::cout <<Node_name.get(v)<< " ";
   }
   
   std::cout << std::endl <<std::endl;
@@ -213,17 +210,17 @@
   /*
     std::cout << "Testing dijkstra..." << std::endl;
   
-    node_iterator root=v2;
+    NodeIt root=v2;
 
-    dijkstra<list_graph, int> dijkstra_test(flow_test, root, cap);
+    dijkstra<ListGraph, int> dijkstra_test(flow_test, root, cap);
 
     dijkstra_test.run();
 
-    for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
+    for (EachNodeIt w=flow_test.first_Node(); w.valid(); ++w) {
       if (dijkstra_test.reach(w)) {
       std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w);
       if (dijkstra_test.pred(w).valid()) {
-      std::cout <<", a shortest path from the root ends with edge " << dijkstra_test.pred(w) <<std::endl; 
+      std::cout <<", a shortest path from the root ends with Edge " << dijkstra_test.pred(w) <<std::endl; 
       } else {
        std::cout <<", this is the root."<<std::endl; }
       
diff -r 69b2d279c8f0 -r ecc1171307be src/work/jacint/preflow_push_hl.h
--- a/src/work/jacint/preflow_push_hl.h	Mon Feb 16 15:57:59 2004 +0000
+++ b/src/work/jacint/preflow_push_hl.h	Mon Feb 16 16:15:58 2004 +0000
@@ -29,11 +29,11 @@
 #include <vector>
 #include <stack>
 
-#include <reverse_bfs.hh>
+#include <reverse_bfs.h>
 
 namespace marci {
 
-  template <typename Graph, typename T, typename FlowMap, typename CapacityMap>
+  template <typename Graph, typename T>
   class preflow_push_hl {
     
     typedef typename Graph::NodeIt NodeIt;
@@ -47,16 +47,16 @@
     Graph& G;
     NodeIt s;
     NodeIt t;
-    Graph::EdgeMap<T> flow;
-    Graph::EdgeMap<T> capacity; 
+    typename Graph::EdgeMap<T> flow;
+    typename Graph::EdgeMap<T> capacity; 
     T value;
-    Graph::NodeMap<bool> mincutvector;
+    typename Graph::NodeMap<bool> mincutvector;
 
    
   public:
 
     preflow_push_hl(Graph& _G, NodeIt _s, NodeIt _t, 
-		    Graph::EdgeMap<T>& _capacity) :
+		    typename Graph::EdgeMap<T>& _capacity) :
       G(_G), s(_s), t(_t), flow(_G, 0), capacity(_capacity), mincutvector(_G, true) { }
 
 
@@ -68,8 +68,8 @@
     */
     void run() {
  
-      Graph::NodeMap<int> level(G);         //level of Node
-      Graph::NodeMap<T> excess(G);          //excess of Node
+      typename Graph::NodeMap<int> level(G);         //level of Node
+      typename Graph::NodeMap<T> excess(G);          //excess of Node
             
       int n=G.nodeNum();                        //number of Nodes 
       int b=n; 
@@ -82,7 +82,7 @@
 
       /*Reverse_bfs from t, to find the starting level.*/
 
-      reverse_bfs<list_graph> bfs(G, t);
+      reverse_bfs<Graph> bfs(G, t);
       bfs.run();
       for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
 	level.set(v, bfs.dist(v)); 
@@ -268,7 +268,7 @@
       Returns the maximum flow x found by the algorithm.
     */
 
-    EdgeMap<graph_type, T> allflow() {
+    typename Graph::EdgeMap<T> allflow() {
       return flow;
     }
 
@@ -278,7 +278,7 @@
       Returns a minimum cut by using a reverse bfs from t in the residual graph.
     */
     
-    NodeMap<graph_type, bool> mincut() {
+    typename Graph::NodeMap<bool> mincut() {
     
       std::queue<NodeIt> queue;
       
@@ -310,8 +310,6 @@
       return mincutvector;
     
     }
-
-
   };
 }//namespace marci
 #endif 
diff -r 69b2d279c8f0 -r ecc1171307be src/work/jacint/preflow_push_max_flow.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/preflow_push_max_flow.h	Mon Feb 16 16:15:58 2004 +0000
@@ -0,0 +1,313 @@
+/*
+preflow_push_max_flow_h
+by jacint. 
+Runs a preflow push algorithm with the modification, 
+that we do not push on Nodes with level at least n. 
+Moreover, if a level gets empty, we.set all Nodes above that
+level to level n. Hence, in the end, we arrive at a maximum preflow 
+with value of a max flow value. An empty level gives a minimum cut.
+
+Member functions:
+
+void run() : runs the algorithm
+
+  The following functions should be used after run() was already run.
+
+T maxflow() : returns the value of a maximum flow
+
+NodeMap<Graph, bool> mincut(): returns a 
+     characteristic vector of a minimum cut.
+*/
+
+#ifndef PREFLOW_PUSH_MAX_FLOW_H
+#define PREFLOW_PUSH_MAX_FLOW_H
+
+#include <algorithm>
+#include <vector>
+#include <stack>
+
+#include <list_graph.hh>
+#include <reverse_bfs.h>
+
+
+namespace marci {
+
+  template <typename Graph, typename T>
+  class preflow_push_max_flow {
+    
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EachNodeIt EachNodeIt;
+    typedef typename Graph::OutEdgeIt OutEdgeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
+    
+    Graph& G;
+    NodeIt s;
+    NodeIt t;
+    typename Graph::EdgeMap<T>& capacity; 
+    T value;
+    typename Graph::NodeMap<bool> mincutvector;    
+
+
+     
+  public:
+        
+    preflow_push_max_flow(Graph& _G, NodeIt _s, NodeIt _t, typename Graph::EdgeMap<T>& _capacity) : G(_G), s(_s), t(_t), capacity(_capacity), mincutvector(_G, false) { }
+
+
+    /*
+      The run() function runs a modified version of the highest label preflow-push, which only 
+      finds a maximum preflow, hence giving the value of a maximum flow.
+    */
+    void run() {
+ 
+      typename Graph::EdgeMap<T> flow(G, 0);         //the flow value, 0 everywhere  
+      typename Graph::NodeMap<int> level(G);         //level of Node
+      typename Graph::NodeMap<T> excess(G);          //excess of Node
+            
+      int n=G.nodeNum();                        //number of Nodes 
+      int b=n-2; 
+      /*b is a bound on the highest level of an active Node. In the beginning it is at most n-2.*/
+      
+      std::vector<int> numb(n);                                //The number of Nodes on level i < n.
+
+      std::vector<std::stack<NodeIt> > stack(2*n-1);    //Stack of the active Nodes in level i.
+
+
+
+      /*Reverse_bfs from t, to find the starting level.*/
+
+      reverse_bfs<Graph> bfs(G, t);
+      bfs.run();
+      for(EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) 
+	{
+	  int dist=bfs.dist(v);
+	  level.set(v, dist); 
+	  ++numb[dist];
+	}
+
+      /*The level of s is fixed to n*/ 
+      level.set(s,n);
+
+
+      /* Starting flow. It is everywhere 0 at the moment. */
+     
+      for(OutEdgeIt i=G.template first<OutEdgeIt>(s); i.valid(); ++i) 
+	{
+	  NodeIt w=G.head(i);
+	  flow.set(i, capacity.get(i)); 
+	  stack[bfs.dist(w)].push(w); 
+	  excess.set(w, capacity.get(i));
+	}
+
+
+      /* 
+	 End of preprocessing 
+      */
+
+
+
+
+      /*
+	Push/relabel on the highest level active Nodes.
+      */
+	
+      /*While there exists an active Node.*/
+      while (b) { 
+
+	/*We decrease the bound if there is no active Node of level b.*/
+	if (stack[b].empty()) {
+	  --b;
+	} else {
+
+	  NodeIt w=stack[b].top();    //w is the highest label active Node.
+	  stack[b].pop();                    //We delete w from the stack.
+	
+	  int newlevel=2*n-2;                //In newlevel we maintain the next level of w.
+	
+	  for(OutEdgeIt e=G.template first<OutEdgeIt>(w); e.valid(); ++e) {
+	    NodeIt v=G.head(e);
+	    /*e is the Edge wv.*/
+
+	    if (flow.get(e)<capacity.get(e)) {              
+	      /*e is an Edge of the residual graph */
+
+	      if(level.get(w)==level.get(v)+1) {      
+		/*Push is allowed now*/
+
+		if (capacity.get(e)-flow.get(e) > excess.get(w)) {       
+		  /*A nonsaturating push.*/
+		  
+		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
+		  /*v becomes active.*/
+		  
+		  flow.set(e, flow.get(e)+excess.get(w));
+		  excess.set(v, excess.get(v)+excess.get(w));
+		  excess.set(w,0);
+		  //std::cout << w << " " << v <<" elore elen nonsat pump "  << std::endl;
+		  break; 
+		} else { 
+		  /*A saturating push.*/
+
+		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
+		  /*v becomes active.*/
+
+		  excess.set(v, excess.get(v)+capacity.get(e)-flow.get(e));
+		  excess.set(w, excess.get(w)-capacity.get(e)+flow.get(e));
+		  flow.set(e, capacity.get(e));
+		  //std::cout << w <<" " << v <<" elore elen sat pump "   << std::endl;
+		  if (excess.get(w)==0) break; 
+		  /*If w is not active any more, then we go on to the next Node.*/
+		  
+		} // if (capacity.get(e)-flow.get(e) > excess.get(w))
+	      } // if (level.get(w)==level.get(v)+1)
+	    
+	      else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
+	    
+	    } //if (flow.get(e)<capacity.get(e))
+	 
+	  } //for(OutEdgeIt e=G.first_OutEdge(w); e.valid(); ++e) 
+	  
+
+
+	  for(InEdgeIt e=G.template first<InEdgeIt>(w); e.valid(); ++e) {
+	    NodeIt v=G.tail(e);
+	    /*e is the Edge vw.*/
+
+	    if (excess.get(w)==0) break;
+	    /*It may happen, that w became inactive in the first 'for' cycle.*/		
+  
+	    if(flow.get(e)>0) {             
+	      /*e is an Edge of the residual graph */
+
+	      if(level.get(w)==level.get(v)+1) {  
+		/*Push is allowed now*/
+		
+		if (flow.get(e) > excess.get(w)) { 
+		  /*A nonsaturating push.*/
+		  
+		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
+		  /*v becomes active.*/
+
+		  flow.set(e, flow.get(e)-excess.get(w));
+		  excess.set(v, excess.get(v)+excess.get(w));
+		  excess.set(w,0);
+		  //std::cout << v << " " << w << " vissza elen nonsat pump "     << std::endl;
+		  break; 
+		} else {                                               
+		  /*A saturating push.*/
+		  
+		  if (excess.get(v)==0 && v != s) stack[level.get(v)].push(v); 
+		  /*v becomes active.*/
+		  
+		  flow.set(e,0);
+		  excess.set(v, excess.get(v)+flow.get(e));
+		  excess.set(w, excess.get(w)-flow.get(e));
+		  //std::cout << v <<" " << w << " vissza elen sat pump "     << std::endl;
+		  if (excess.get(w)==0) { break;}
+		} //if (flow.get(e) > excess.get(v)) 
+	      } //if(level.get(w)==level.get(v)+1)
+	      
+	      else {newlevel = newlevel < level.get(v) ? newlevel : level.get(v);}
+	      //std::cout << "Leveldecrease of Node " << w << " to " << newlevel << std::endl; 
+
+	    } //if (flow.get(e)>0)
+
+	  } //for in-Edge
+
+
+
+
+	  /*
+	    Relabel
+	  */
+	  if (excess.get(w)>0) {
+	    /*Now newlevel <= n*/
+
+	    int l=level.get(w);	        //l is the old level of w.
+	    --numb[l];
+	   
+	    if (newlevel == n) {
+	      level.set(w,n);
+	      
+	    } else {
+	      
+	      if (numb[l]) {
+		/*If the level of w remains nonempty.*/
+		
+		level.set(w,++newlevel);
+		++numb[newlevel];
+		stack[newlevel].push(w);
+		b=newlevel;
+	      } else { 
+		/*If the level of w gets empty.*/
+	      
+		for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid() ; ++v) {
+		  if (level.get(v) >= l ) { 
+		    level.set(v,n);  
+		  }
+		}
+		
+		for (int i=l+1 ; i!=n ; ++i) numb[i]=0; 
+	      } //if (numb[l])
+	
+	    } // if (newlevel = n)
+	 
+	  } // if (excess.get(w)>0)
+
+
+	} //else
+       
+      } //while(b)
+
+      value=excess.get(t);
+      /*Max flow value.*/
+      
+
+
+      /*
+	We find an empty level, e. The Nodes above this level give 
+	a minimum cut.
+      */
+      
+      int e=1;
+      
+      while(e) {
+	if(numb[e]) ++e;
+	else break;
+      } 
+      for (EachNodeIt v=G.template first<EachNodeIt>(); v.valid(); ++v) {
+	if (level.get(v) > e) mincutvector.set(v, true);
+      }
+      
+
+    } // void run()
+
+
+
+    /*
+      Returns the maximum value of a flow.
+     */
+
+    T maxflow() {
+      return value;
+    }
+
+
+
+    /*
+      Returns a minimum cut.
+    */
+    
+    typename Graph::NodeMap<bool> mincut() {
+      return mincutvector;
+    }
+    
+
+  };
+}//namespace marci
+#endif 
+
+
+
+
+
diff -r 69b2d279c8f0 -r ecc1171307be src/work/jacint/reverse_bfs.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/work/jacint/reverse_bfs.h	Mon Feb 16 16:15:58 2004 +0000
@@ -0,0 +1,89 @@
+/*
+reverse_bfs
+by jacint
+Performs a bfs on the out Edges. It does not count predecessors, 
+only the distances, but one can easily modify it to know the pred as well.
+
+Constructor: 
+
+reverse_bfs(Graph& G, NodeIt t)
+
+
+
+Member functions:
+
+void run(): runs a reverse bfs from t
+
+  The following function should be used after run() was already run.
+
+int dist(NodeIt v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
+
+*/
+#ifndef REVERSE_BFS_H
+#define REVERSE_BFS_H
+
+#include <queue>
+#include <list_graph.hh>
+
+
+namespace  marci {
+
+  template <typename Graph>
+  class reverse_bfs {
+    typedef typename Graph::NodeIt NodeIt;
+    typedef typename Graph::EachNodeIt EachNodeIt;
+    typedef typename Graph::InEdgeIt InEdgeIt;
+
+
+    Graph& G;
+    NodeIt t;
+    typename Graph::NodeMap<int> distance;
+    
+
+  public :
+
+    /*
+      The distance of the Nodes is n, except t for which it is 0.
+    */
+    reverse_bfs(Graph& _G, NodeIt _t) : G(_G), t(_t), distance(G, G.nodeNum()) {
+      distance.set(t,0);
+    }
+    
+    void run() {
+
+      typename Graph::NodeMap<bool> reached(G, false); 
+      reached.set(t, true);
+
+      std::queue<NodeIt> bfs_queue;
+      bfs_queue.push(t);
+
+      while (!bfs_queue.empty()) {
+
+        NodeIt v=bfs_queue.front();	
+	bfs_queue.pop();
+
+	for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
+	  NodeIt w=G.tail(e);
+	  if (!reached.get(w)) {
+	    bfs_queue.push(w);
+	    distance.set(w, distance.get(v)+1);
+	    reached.set(w, true);
+	  }
+	}
+      }
+    }
+
+
+
+    int dist(NodeIt v) {
+      return distance.get(v);
+    }
+
+
+  };
+
+} // namespace marci
+
+#endif //REVERSE_BFS_HH
+
+
diff -r 69b2d279c8f0 -r ecc1171307be src/work/jacint/reverse_bfs.hh
--- a/src/work/jacint/reverse_bfs.hh	Mon Feb 16 15:57:59 2004 +0000
+++ b/src/work/jacint/reverse_bfs.hh	Mon Feb 16 16:15:58 2004 +0000
@@ -1,12 +1,12 @@
 /*
 reverse_bfs
 by jacint
-Performs a bfs on the out edges. It does not count predecessors, 
+Performs a bfs on the out Edges. It does not count predecessors, 
 only the distances, but one can easily modify it to know the pred as well.
 
 Constructor: 
 
-reverse_bfs(graph_type& G, node_iterator t)
+reverse_bfs(graph_type& G, NodeIt t)
 
 
 
@@ -16,7 +16,7 @@
 
   The following function should be used after run() was already run.
 
-int dist(node_iterator v) : returns the distance from v to t. It is the number of nodes if t is not reachable from v.
+int dist(NodeIt v) : returns the distance from v to t. It is the number of Nodes if t is not reachable from v.
 
 */
 #ifndef REVERSE_BFS_HH
@@ -25,7 +25,7 @@
 #include <queue>
 
 #include <marci_graph_traits.hh>
-#include <marci_property_vector.hh>
+#include <marciMap.hh>
 
 
 
@@ -33,42 +33,42 @@
 
   template <typename graph_type>
   class reverse_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>::in_edge_iterator in_edge_iterator;
+    typedef typename graph_traits<graph_type>::NodeIt NodeIt;
+    //typedef typename graph_traits<graph_type>::EdgeIt EdgeIt;
+    typedef typename graph_traits<graph_type>::EachNodeIt EachNodeIt;
+    typedef typename graph_traits<graph_type>::InEdgeIt InEdgeIt;
 
 
     graph_type& G;
-    node_iterator t;
-//    node_property_vector<graph_type, edge_iterator> pred;
-    node_property_vector<graph_type, int> distance;
+    NodeIt t;
+//    NodeMap<graph_type, EdgeIt> pred;
+    NodeMap<graph_type, int> distance;
     
 
   public :
 
     /*
-      The distance of the nodes is n, except t for which it is 0.
+      The distance of the Nodes is n, except t for which it is 0.
     */
-    reverse_bfs(graph_type& _G, node_iterator _t) : G(_G), t(_t), distance(G, number_of(G.first_node())) {
+    reverse_bfs(graph_type& _G, NodeIt _t) : G(_G), t(_t), distance(G, number_of(G.first_Node())) {
       distance.put(t,0);
     }
     
     void run() {
 
-      node_property_vector<graph_type, bool> reached(G, false); 
+      NodeMap<graph_type, bool> reached(G, false); 
       reached.put(t, true);
 
-      std::queue<node_iterator> bfs_queue;
+      std::queue<NodeIt> bfs_queue;
       bfs_queue.push(t);
 
       while (!bfs_queue.empty()) {
 
-        node_iterator v=bfs_queue.front();	
+        NodeIt v=bfs_queue.front();	
 	bfs_queue.pop();
 
-	for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {
-	  node_iterator w=G.tail(e);
+	for(InEdgeIt e=G.template first<InEdgeIt>(v); e.valid(); ++e) {
+	  NodeIt w=G.tail(e);
 	  if (!reached.get(w)) {
 	    bfs_queue.push(w);
 	    distance.put(w, distance.get(v)+1);
@@ -80,7 +80,7 @@
 
 
 
-    int dist(node_iterator v) {
+    int dist(NodeIt v) {
       return distance.get(v);
     }