Changeset 30:10a3f2e0928c in lemon-0.x

Timestamp:

01/21/04 15:51:05 (20 years ago)

Author:

jacint

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@43

Message:

is_valid changed to valid

Location:

src/work

Files:

• marci_graph_concept.txt (modified) (3 diffs)
• preflow_push_hl.hh (modified) (6 diffs)
• preflow_push_max_flow.hh (modified) (6 diffs)
• proba.cc (modified) (11 diffs)
• reverse_bfs.hh (modified) (1 diff)

src/work/marci_graph_concept.txt

@@ -1 +1 @@
 ETIK-OL-NOLIB-NEGRES graph concept-ek.
 
- Ebben a dokumentacioban graph concept tervek es azok megvalositastarol irok. 
+ Ebben a dokumentacioban graph concept tervek es azok megvalositasarol 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 
+operacio elvegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen 
 ujakra van szukseg. 
 
@@ -27 +27 @@
 trivialis node iterator, csak cimezni lehet vele, pl property vectort
 
+<<<<<<< marci_graph_concept.txt
+class each_node_iterator
+node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
+=======
 class each_node_iterator;
 node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
+>>>>>>> 1.3
 
 class edge_iterator;
@@ -36 +41 @@
 edge iterator a graf osszes elenek bejarasara
 
+<<<<<<< marci_graph_concept.txt
+class out_edge_iterator
+edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
+=======
 class out_edge_iterator;
 edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
-
+>>>>>>> 1.3
+
+<<<<<<< marci_graph_concept.txt
+class in_edge_iterator
+edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
+=======
 class in_edge_iterator;
 edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
+>>>>>>> 1.3
       
+<<<<<<< marci_graph_concept.txt
+class sym_edge_iterator
+edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
+konvertalhato 
+=======
 class sym_edge_iterator;
 edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
+>>>>>>> 1.3
 
 default constructor:

src/work/preflow_push_hl.hh

@@ -84 +84 @@
       reverse_bfs<list_graph> bfs(G, t);
       bfs.run();
-      for(each_node_iterator v=G.first_node(); v.is_valid(); ++v) {
+      for(each_node_iterator v=G.first_node(); v.valid(); ++v) {
         level.put(v, bfs.dist(v)); 
         //std::cout << "the level of " << v << " is " << bfs.dist(v);
@@ -98 +98 @@
       /* Starting flow. It is everywhere 0 at the moment. */
      
-      for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i) 
+      for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) 
         {
           node_iterator w=G.head(i);
@@ -130 +130 @@
           int newlevel=2*n-2;                   //In newlevel we maintain the next level of w.
         
-          for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) {
+          for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
             node_iterator v=G.head(e);
             /*e is the edge wv.*/
@@ -171 +171 @@
             } //if (flow.get(e)<capacity.get(e))
          
-          } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) 
+          } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) 
           
 
 
-          for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) {
+          for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
             node_iterator v=G.tail(e);
             /*e is the edge vw.*/
@@ -289 +289 @@
         queue.pop();
 
-        for(in_edge_iterator e=G.first_in_edge(w) ; e.is_valid(); ++e) {
+        for(in_edge_iterator e=G.first_in_edge(w) ; e.valid(); ++e) {
           node_iterator v=G.tail(e);
           if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
@@ -297 +297 @@
         } // for
 
-        for(out_edge_iterator e=G.first_out_edge(w) ; e.is_valid(); ++e) {
+        for(out_edge_iterator e=G.first_out_edge(w) ; e.valid(); ++e) {
           node_iterator v=G.head(e);
           if (mincutvector.get(v) && flow.get(e) > 0 ) {

src/work/preflow_push_max_flow.hh

@@ -81 +81 @@
       reverse_bfs<list_graph> bfs(G, t);
       bfs.run();
-      for(each_node_iterator v=G.first_node(); v.is_valid(); ++v) 
+      for(each_node_iterator v=G.first_node(); v.valid(); ++v) 
         {
           int dist=bfs.dist(v);
@@ -94 +94 @@
       /* Starting flow. It is everywhere 0 at the moment. */
      
-      for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i) 
+      for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i) 
         {
           node_iterator w=G.head(i);
@@ -127 +127 @@
           int newlevel=2*n-2;                //In newlevel we maintain the next level of w.
         
-          for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) {
+          for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
             node_iterator v=G.head(e);
             /*e is the edge wv.*/
@@ -168 +168 @@
             } //if (flow.get(e)<capacity.get(e))
          
-          } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) 
+          } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) 
           
 
 
-          for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) {
+          for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
             node_iterator v=G.tail(e);
             /*e is the edge vw.*/
@@ -244 +244 @@
                 /*If the level of w gets empty.*/
               
-                for (each_node_iterator v=G.first_node() ; v.is_valid() ; ++v) {
+                for (each_node_iterator v=G.first_node() ; v.valid() ; ++v) {
                   if (level.get(v) >= l ) { 
                     level.put(v,n);  
@@ -278 +278 @@
         else break;
       } 
-      for (each_node_iterator v=G.first_node(); v.is_valid(); ++v) {
+      for (each_node_iterator v=G.first_node(); v.valid(); ++v) {
         if (level.get(v) > e) mincutvector.put(v, true);
       }

src/work/proba.cc

@@ -9 +9 @@
 #include <preflow_push_max_flow.hh>
 #include <reverse_bfs.hh>
+//#include <dijkstra.hh>
 
 using namespace marci;
@@ -25 +26 @@
   list_graph flow_test;
  
-  //Ahuja könyv példája, maxflowvalue=13
+  /*  //Ahuja könyv példája, maxflowvalue=13
   node_iterator s=flow_test.add_node();
   node_iterator v1=flow_test.add_node();
@@ -46 +47 @@
   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);
   
   edge_property_vector<list_graph, int> cap(flow_test);  
@@ -64 +63 @@
   cap.put(v4_t, 8);
   cap.put(v5_t, 8);
-
+  cap.put(v2_s, 0);
+*/
 
   
   //Marci példája, maxflowvalue=23
-  /*   node_iterator s=flow_test.add_node();
+     node_iterator s=flow_test.add_node();
   node_iterator v1=flow_test.add_node();
   node_iterator v2=flow_test.add_node();
@@ -98 +98 @@
   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);
   
 
@@ -114 +115 @@
   cap.put(v3_v3, 4);
   cap.put(s_w, 4);
-  */
+  cap.put(v2_s, 0);
 
 
@@ -156 +157 @@
   bfs_test.run();
 
-  for (each_node_iterator w=flow_test.first_node(); w.is_valid(); ++w) {
+  for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
     std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
     }
@@ -175 +176 @@
 
   edge_property_vector<list_graph, int> flow=preflow_push_test.allflow();  
-  for (each_edge_iterator e=flow_test.first_edge(); e.is_valid(); ++e) {
+  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;
     }
@@ -182 +183 @@
   node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut();
 
-  for (each_node_iterator v=flow_test.first_node(); v.is_valid(); ++v) {
+  for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
       if (mincut.get(v)) std::cout <<node_name.get(v)<< " ";
     }
@@ -202 +203 @@
   node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut();
 
-  for (each_node_iterator v=flow_test.first_node(); v.is_valid(); ++v) {
+  for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
     if (mincut2.get(v)) std::cout <<node_name.get(v)<< " ";
   }
@@ -210 +211 @@
 
 
+//    std::cout << "Testing dijkstra..." << std::endl;
+  
+//    dijkstra<list_graph, int> dijkstra_test(flow_test, s, cap);
+
+//    dijkstra_test.run();
+
+//    for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
+//      std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w) <<std::endl;
+//      }
+
+
+
+
   return 0;
 }

src/work/reverse_bfs.hh

@@ -68 +68 @@
         bfs_queue.pop();
 
-        for(in_edge_iterator e=G.first_in_edge(v); e.is_valid(); ++e) {
+        for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {
           node_iterator w=G.tail(e);
           if (!reached.get(w)) {