# HG changeset patch
# User jacint
# Date 1074696665 0
# Node ID 10a3f2e0928cb5f606f0c79fcff8378891e690fd
# Parent c7ac1a6fb05cc65f85297fd930eecebe9dd26ea9
is_valid changed to valid
diff -r c7ac1a6fb05c -r 10a3f2e0928c src/work/marci_graph_concept.txt
--- a/src/work/marci_graph_concept.txt Wed Jan 21 08:39:33 2004 +0000
+++ b/src/work/marci_graph_concept.txt Wed Jan 21 14:51:05 2004 +0000
@@ -1,8 +1,8 @@
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.
Megvalositottunk egy graph osztalyt mely listaban tarolja a pontokat,
@@ -26,8 +26,13 @@
class node_iterator;
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;
trivialis edge iterator, csak cimezni lehet vele, pl property vectort
@@ -35,14 +40,30 @@
class each_edge_iterator;
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:
diff -r c7ac1a6fb05c -r 10a3f2e0928c src/work/preflow_push_hl.hh
--- a/src/work/preflow_push_hl.hh Wed Jan 21 08:39:33 2004 +0000
+++ b/src/work/preflow_push_hl.hh Wed Jan 21 14:51:05 2004 +0000
@@ -83,7 +83,7 @@
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);
}
@@ -97,7 +97,7 @@
/* 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);
flow.put(i, capacity.get(i));
@@ -129,7 +129,7 @@
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.*/
@@ -170,11 +170,11 @@
} //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.*/
@@ -288,7 +288,7 @@
node_iterator w=queue.front();
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) ) {
queue.push(v);
@@ -296,7 +296,7 @@
}
} // 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 ) {
queue.push(v);
diff -r c7ac1a6fb05c -r 10a3f2e0928c src/work/preflow_push_max_flow.hh
--- a/src/work/preflow_push_max_flow.hh Wed Jan 21 08:39:33 2004 +0000
+++ b/src/work/preflow_push_max_flow.hh Wed Jan 21 14:51:05 2004 +0000
@@ -80,7 +80,7 @@
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);
level.put(v, dist);
@@ -93,7 +93,7 @@
/* 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);
flow.put(i, capacity.get(i));
@@ -126,7 +126,7 @@
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.*/
@@ -167,11 +167,11 @@
} //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.*/
@@ -243,7 +243,7 @@
} else {
/*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);
}
@@ -277,7 +277,7 @@
if(numb[e]) ++e;
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);
}
diff -r c7ac1a6fb05c -r 10a3f2e0928c src/work/proba.cc
--- a/src/work/proba.cc Wed Jan 21 08:39:33 2004 +0000
+++ b/src/work/proba.cc Wed Jan 21 14:51:05 2004 +0000
@@ -8,6 +8,7 @@
#include <preflow_push_hl.hh>
#include <preflow_push_max_flow.hh>
#include <reverse_bfs.hh>
+//#include <dijkstra.hh>
using namespace marci;
@@ -24,7 +25,7 @@
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();
node_iterator v2=flow_test.add_node();
@@ -45,14 +46,12 @@
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);
edge_property_vector<list_graph, int> cap(flow_test);
cap.put(s_v1, 0);
@@ -63,11 +62,12 @@
cap.put(v3_v5, 5);
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();
node_iterator v3=flow_test.add_node();
@@ -97,6 +97,7 @@
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);
@@ -113,7 +114,7 @@
cap.put(v4_t, 4);
cap.put(v3_v3, 4);
cap.put(s_w, 4);
- */
+ cap.put(v2_s, 0);
//pelda 3, maxflowvalue=4
@@ -155,7 +156,7 @@
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;
}
@@ -174,14 +175,14 @@
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.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;
}
std::cout << "A minimum cut: " <<std::endl;
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)<< " ";
}
@@ -201,7 +202,7 @@
std::cout << "A minimum cut: " <<std::endl;
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)<< " ";
}
@@ -209,6 +210,19 @@
+// 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;
}
diff -r c7ac1a6fb05c -r 10a3f2e0928c src/work/reverse_bfs.hh
--- a/src/work/reverse_bfs.hh Wed Jan 21 08:39:33 2004 +0000
+++ b/src/work/reverse_bfs.hh Wed Jan 21 14:51:05 2004 +0000
@@ -67,7 +67,7 @@
node_iterator v=bfs_queue.front();
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)) {
bfs_queue.push(w);