# 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 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) 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 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)= 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 #include #include +//#include 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 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) < 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 " < 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 < 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 < 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) <