1.1 --- a/src/work/marci_graph_concept.txt Wed Jan 21 08:39:33 2004 +0000
1.2 +++ b/src/work/marci_graph_concept.txt Wed Jan 21 14:51:05 2004 +0000
1.3 @@ -1,8 +1,8 @@
1.4 ETIK-OL-NOLIB-NEGRES graph concept-ek.
1.5
1.6 - Ebben a dokumentacioban graph concept tervek es azok megvalositastarol irok.
1.7 + Ebben a dokumentacioban graph concept tervek es azok megvalositasarol irok.
1.8 A felsorolt rutinok, osztalyok egyaltalan nem kikristalyosodottak, 1-1 elemi
1.9 -operacio elegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen
1.10 +operacio elvegzesere gyakran tobb mod is rendelkezesre all. A tervezesi fazisban pont annak kell kiderulnie, hogy milyen metodusok tavolithatok el, s milyen
1.11 ujakra van szukseg.
1.12
1.13 Megvalositottunk egy graph osztalyt mely listaban tarolja a pontokat,
1.14 @@ -26,8 +26,13 @@
1.15 class node_iterator;
1.16 trivialis node iterator, csak cimezni lehet vele, pl property vectort
1.17
1.18 +<<<<<<< marci_graph_concept.txt
1.19 +class each_node_iterator
1.20 +node iterator a graf pontjainak bejarasara, node_iterator-ra konvertalhato
1.21 +=======
1.22 class each_node_iterator;
1.23 node iterator a graf pontjainak bejarasara, node_iterator-a konvertalhato
1.24 +>>>>>>> 1.3
1.25
1.26 class edge_iterator;
1.27 trivialis edge iterator, csak cimezni lehet vele, pl property vectort
1.28 @@ -35,14 +40,30 @@
1.29 class each_edge_iterator;
1.30 edge iterator a graf osszes elenek bejarasara
1.31
1.32 +<<<<<<< marci_graph_concept.txt
1.33 +class out_edge_iterator
1.34 +edge iterator 1 pont ki eleinek bejarasara, edge_iterator-ra konvertalhato
1.35 +=======
1.36 class out_edge_iterator;
1.37 edge iterator 1 pont ki eleinek bejarasara, edge_iterator-a konvertalhato
1.38 +>>>>>>> 1.3
1.39
1.40 +<<<<<<< marci_graph_concept.txt
1.41 +class in_edge_iterator
1.42 +edge iterator 1 pont be eleinek bejarasara, edge_iterator-ra konvertalhato
1.43 +=======
1.44 class in_edge_iterator;
1.45 edge iterator 1 pont be eleinek bejarasara, edge_iterator-a konvertalhato
1.46 +>>>>>>> 1.3
1.47
1.48 +<<<<<<< marci_graph_concept.txt
1.49 +class sym_edge_iterator
1.50 +edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-ra
1.51 +konvertalhato
1.52 +=======
1.53 class sym_edge_iterator;
1.54 edge iterator 1 pont be es ki eleinek bejarasara, edge_iterator-a konvertalhato
1.55 +>>>>>>> 1.3
1.56
1.57 default constructor:
1.58
2.1 --- a/src/work/preflow_push_hl.hh Wed Jan 21 08:39:33 2004 +0000
2.2 +++ b/src/work/preflow_push_hl.hh Wed Jan 21 14:51:05 2004 +0000
2.3 @@ -83,7 +83,7 @@
2.4
2.5 reverse_bfs<list_graph> bfs(G, t);
2.6 bfs.run();
2.7 - for(each_node_iterator v=G.first_node(); v.is_valid(); ++v) {
2.8 + for(each_node_iterator v=G.first_node(); v.valid(); ++v) {
2.9 level.put(v, bfs.dist(v));
2.10 //std::cout << "the level of " << v << " is " << bfs.dist(v);
2.11 }
2.12 @@ -97,7 +97,7 @@
2.13
2.14 /* Starting flow. It is everywhere 0 at the moment. */
2.15
2.16 - for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i)
2.17 + for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i)
2.18 {
2.19 node_iterator w=G.head(i);
2.20 flow.put(i, capacity.get(i));
2.21 @@ -129,7 +129,7 @@
2.22
2.23 int newlevel=2*n-2; //In newlevel we maintain the next level of w.
2.24
2.25 - for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) {
2.26 + for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
2.27 node_iterator v=G.head(e);
2.28 /*e is the edge wv.*/
2.29
2.30 @@ -170,11 +170,11 @@
2.31
2.32 } //if (flow.get(e)<capacity.get(e))
2.33
2.34 - } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e)
2.35 + } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e)
2.36
2.37
2.38
2.39 - for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) {
2.40 + for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
2.41 node_iterator v=G.tail(e);
2.42 /*e is the edge vw.*/
2.43
2.44 @@ -288,7 +288,7 @@
2.45 node_iterator w=queue.front();
2.46 queue.pop();
2.47
2.48 - for(in_edge_iterator e=G.first_in_edge(w) ; e.is_valid(); ++e) {
2.49 + for(in_edge_iterator e=G.first_in_edge(w) ; e.valid(); ++e) {
2.50 node_iterator v=G.tail(e);
2.51 if (mincutvector.get(v) && flow.get(e) < capacity.get(e) ) {
2.52 queue.push(v);
2.53 @@ -296,7 +296,7 @@
2.54 }
2.55 } // for
2.56
2.57 - for(out_edge_iterator e=G.first_out_edge(w) ; e.is_valid(); ++e) {
2.58 + for(out_edge_iterator e=G.first_out_edge(w) ; e.valid(); ++e) {
2.59 node_iterator v=G.head(e);
2.60 if (mincutvector.get(v) && flow.get(e) > 0 ) {
2.61 queue.push(v);
3.1 --- a/src/work/preflow_push_max_flow.hh Wed Jan 21 08:39:33 2004 +0000
3.2 +++ b/src/work/preflow_push_max_flow.hh Wed Jan 21 14:51:05 2004 +0000
3.3 @@ -80,7 +80,7 @@
3.4
3.5 reverse_bfs<list_graph> bfs(G, t);
3.6 bfs.run();
3.7 - for(each_node_iterator v=G.first_node(); v.is_valid(); ++v)
3.8 + for(each_node_iterator v=G.first_node(); v.valid(); ++v)
3.9 {
3.10 int dist=bfs.dist(v);
3.11 level.put(v, dist);
3.12 @@ -93,7 +93,7 @@
3.13
3.14 /* Starting flow. It is everywhere 0 at the moment. */
3.15
3.16 - for(out_edge_iterator i=G.first_out_edge(s); i.is_valid(); ++i)
3.17 + for(out_edge_iterator i=G.first_out_edge(s); i.valid(); ++i)
3.18 {
3.19 node_iterator w=G.head(i);
3.20 flow.put(i, capacity.get(i));
3.21 @@ -126,7 +126,7 @@
3.22
3.23 int newlevel=2*n-2; //In newlevel we maintain the next level of w.
3.24
3.25 - for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e) {
3.26 + for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e) {
3.27 node_iterator v=G.head(e);
3.28 /*e is the edge wv.*/
3.29
3.30 @@ -167,11 +167,11 @@
3.31
3.32 } //if (flow.get(e)<capacity.get(e))
3.33
3.34 - } //for(out_edge_iterator e=G.first_out_edge(w); e.is_valid(); ++e)
3.35 + } //for(out_edge_iterator e=G.first_out_edge(w); e.valid(); ++e)
3.36
3.37
3.38
3.39 - for(in_edge_iterator e=G.first_in_edge(w); e.is_valid(); ++e) {
3.40 + for(in_edge_iterator e=G.first_in_edge(w); e.valid(); ++e) {
3.41 node_iterator v=G.tail(e);
3.42 /*e is the edge vw.*/
3.43
3.44 @@ -243,7 +243,7 @@
3.45 } else {
3.46 /*If the level of w gets empty.*/
3.47
3.48 - for (each_node_iterator v=G.first_node() ; v.is_valid() ; ++v) {
3.49 + for (each_node_iterator v=G.first_node() ; v.valid() ; ++v) {
3.50 if (level.get(v) >= l ) {
3.51 level.put(v,n);
3.52 }
3.53 @@ -277,7 +277,7 @@
3.54 if(numb[e]) ++e;
3.55 else break;
3.56 }
3.57 - for (each_node_iterator v=G.first_node(); v.is_valid(); ++v) {
3.58 + for (each_node_iterator v=G.first_node(); v.valid(); ++v) {
3.59 if (level.get(v) > e) mincutvector.put(v, true);
3.60 }
3.61
4.1 --- a/src/work/proba.cc Wed Jan 21 08:39:33 2004 +0000
4.2 +++ b/src/work/proba.cc Wed Jan 21 14:51:05 2004 +0000
4.3 @@ -8,6 +8,7 @@
4.4 #include <preflow_push_hl.hh>
4.5 #include <preflow_push_max_flow.hh>
4.6 #include <reverse_bfs.hh>
4.7 +//#include <dijkstra.hh>
4.8
4.9 using namespace marci;
4.10
4.11 @@ -24,7 +25,7 @@
4.12
4.13 list_graph flow_test;
4.14
4.15 - //Ahuja könyv példája, maxflowvalue=13
4.16 + /* //Ahuja könyv példája, maxflowvalue=13
4.17 node_iterator s=flow_test.add_node();
4.18 node_iterator v1=flow_test.add_node();
4.19 node_iterator v2=flow_test.add_node();
4.20 @@ -45,14 +46,12 @@
4.21 edge_iterator s_v1=flow_test.add_edge(s, v1);
4.22 edge_iterator s_v2=flow_test.add_edge(s, v2);
4.23 edge_iterator s_v3=flow_test.add_edge(s, v3);
4.24 -
4.25 edge_iterator v2_v4=flow_test.add_edge(v2, v4);
4.26 edge_iterator v2_v5=flow_test.add_edge(v2, v5);
4.27 -
4.28 edge_iterator v3_v5=flow_test.add_edge(v3, v5);
4.29 -
4.30 edge_iterator v4_t=flow_test.add_edge(v4, t);
4.31 edge_iterator v5_t=flow_test.add_edge(v5, t);
4.32 + edge_iterator v2_s=flow_test.add_edge(v2, s);
4.33
4.34 edge_property_vector<list_graph, int> cap(flow_test);
4.35 cap.put(s_v1, 0);
4.36 @@ -63,11 +62,12 @@
4.37 cap.put(v3_v5, 5);
4.38 cap.put(v4_t, 8);
4.39 cap.put(v5_t, 8);
4.40 -
4.41 + cap.put(v2_s, 0);
4.42 +*/
4.43
4.44
4.45 //Marci példája, maxflowvalue=23
4.46 - /* node_iterator s=flow_test.add_node();
4.47 + node_iterator s=flow_test.add_node();
4.48 node_iterator v1=flow_test.add_node();
4.49 node_iterator v2=flow_test.add_node();
4.50 node_iterator v3=flow_test.add_node();
4.51 @@ -97,6 +97,7 @@
4.52 edge_iterator v4_t=flow_test.add_edge(v4, t);
4.53 edge_iterator v3_v3=flow_test.add_edge(v3, v3);
4.54 edge_iterator s_w=flow_test.add_edge(s, w);
4.55 + edge_iterator v2_s=flow_test.add_edge(v2, s);
4.56
4.57
4.58
4.59 @@ -113,7 +114,7 @@
4.60 cap.put(v4_t, 4);
4.61 cap.put(v3_v3, 4);
4.62 cap.put(s_w, 4);
4.63 - */
4.64 + cap.put(v2_s, 0);
4.65
4.66
4.67 //pelda 3, maxflowvalue=4
4.68 @@ -155,7 +156,7 @@
4.69
4.70 bfs_test.run();
4.71
4.72 - for (each_node_iterator w=flow_test.first_node(); w.is_valid(); ++w) {
4.73 + for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
4.74 std::cout <<"The distance of " << w << " is " << bfs_test.dist(w) <<std::endl;
4.75 }
4.76
4.77 @@ -174,14 +175,14 @@
4.78 std::cout<< "The flow on edge s-v1 is "<< preflow_push_test.flowonedge(s_v1) << "."<<std::endl;
4.79
4.80 edge_property_vector<list_graph, int> flow=preflow_push_test.allflow();
4.81 - for (each_edge_iterator e=flow_test.first_edge(); e.is_valid(); ++e) {
4.82 + for (each_edge_iterator e=flow_test.first_edge(); e.valid(); ++e) {
4.83 std::cout <<"Flow on edge " << flow_test.tail(e) <<"-" << flow_test.head(e)<< " is " <<flow.get(e) <<std::endl;
4.84 }
4.85
4.86 std::cout << "A minimum cut: " <<std::endl;
4.87 node_property_vector<list_graph, bool> mincut=preflow_push_test.mincut();
4.88
4.89 - for (each_node_iterator v=flow_test.first_node(); v.is_valid(); ++v) {
4.90 + for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
4.91 if (mincut.get(v)) std::cout <<node_name.get(v)<< " ";
4.92 }
4.93
4.94 @@ -201,7 +202,7 @@
4.95 std::cout << "A minimum cut: " <<std::endl;
4.96 node_property_vector<list_graph, bool> mincut2=max_flow_test.mincut();
4.97
4.98 - for (each_node_iterator v=flow_test.first_node(); v.is_valid(); ++v) {
4.99 + for (each_node_iterator v=flow_test.first_node(); v.valid(); ++v) {
4.100 if (mincut2.get(v)) std::cout <<node_name.get(v)<< " ";
4.101 }
4.102
4.103 @@ -209,6 +210,19 @@
4.104
4.105
4.106
4.107 +// std::cout << "Testing dijkstra..." << std::endl;
4.108 +
4.109 +// dijkstra<list_graph, int> dijkstra_test(flow_test, s, cap);
4.110 +
4.111 +// dijkstra_test.run();
4.112 +
4.113 +// for (each_node_iterator w=flow_test.first_node(); w.valid(); ++w) {
4.114 +// std::cout <<"The distance of " << w << " is " << dijkstra_test.dist(w) <<std::endl;
4.115 +// }
4.116 +
4.117 +
4.118 +
4.119 +
4.120 return 0;
4.121 }
4.122
5.1 --- a/src/work/reverse_bfs.hh Wed Jan 21 08:39:33 2004 +0000
5.2 +++ b/src/work/reverse_bfs.hh Wed Jan 21 14:51:05 2004 +0000
5.3 @@ -67,7 +67,7 @@
5.4 node_iterator v=bfs_queue.front();
5.5 bfs_queue.pop();
5.6
5.7 - for(in_edge_iterator e=G.first_in_edge(v); e.is_valid(); ++e) {
5.8 + for(in_edge_iterator e=G.first_in_edge(v); e.valid(); ++e) {
5.9 node_iterator w=G.tail(e);
5.10 if (!reached.get(w)) {
5.11 bfs_queue.push(w);