1.1 --- a/src/work/makefile Fri May 07 10:57:31 2004 +0000
1.2 +++ b/src/work/makefile Fri May 07 11:57:34 2004 +0000
1.3 @@ -1,5 +1,5 @@
1.4 INCLUDEDIRS ?= -I../include -I. -I./{marci,jacint,alpar,klao,akos}
1.5 -CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
1.6 +CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
1.7
1.8 BINARIES ?= bin_heap_demo
1.9
2.1 --- a/src/work/marci/bfs_dfs_misc.h Fri May 07 10:57:31 2004 +0000
2.2 +++ b/src/work/marci/bfs_dfs_misc.h Fri May 07 11:57:34 2004 +0000
2.3 @@ -39,24 +39,47 @@
2.4 /// experimental topsort,
2.5 /// I think the final version will work as an iterator
2.6 /// if the graph is not a acyclic, the na pre-topological order is obtained
2.7 - /// (see Schrijver's book)
2.8 - template<typename Graph>
2.9 - void topSort(const Graph& g, std::list<typename Graph::Node>& l) {
2.10 + /// (see Schrijver's book).
2.11 + /// PredMap have to be a writtable node-map.
2.12 + /// If the graph is directed and not acyclic,
2.13 + /// then going back from the returned node via the pred information, a
2.14 + /// cycle is obtained.
2.15 + template<typename Graph, typename PredMap>
2.16 + typename Graph::Node
2.17 + topSort(const Graph& g, std::list<typename Graph::Node>& l,
2.18 + PredMap& pred) {
2.19 l.clear();
2.20 typedef typename Graph::template NodeMap<bool> ReachedMap;
2.21 + typedef typename Graph::template NodeMap<bool> ExaminedMap;
2.22 ReachedMap reached(g/*, false*/);
2.23 + ExaminedMap examined(g/*, false*/);
2.24 DfsIterator<Graph, ReachedMap> dfs(g, reached);
2.25 FOR_EACH_LOC(typename Graph::NodeIt, n, g) {
2.26 if (!reached[n]) {
2.27 dfs.pushAndSetReached(n);
2.28 + pred.set(n, INVALID);
2.29 while (!dfs.finished()) {
2.30 ++dfs;
2.31 + if (dfs.isBNodeNewlyReached()) {
2.32 + ///\bug hugo 0.2-ben Edge kell
2.33 + pred.set(dfs.aNode(), typename Graph::OutEdgeIt(dfs));
2.34 + } else {
2.35 + ///\bug ugyanaz
2.36 + if (g.valid(typename Graph::OutEdgeIt(dfs)) &&
2.37 + !examined[dfs.bNode()]) {
2.38 + ///\bug hugo 0.2-ben Edge kell
2.39 + pred.set(dfs.bNode(), typename Graph::OutEdgeIt(dfs));
2.40 + return dfs.aNode();
2.41 + }
2.42 + }
2.43 if (dfs.isANodeExamined()) {
2.44 l.push_back(dfs.aNode());
2.45 + examined.set(dfs.aNode(), true);
2.46 }
2.47 }
2.48 }
2.49 }
2.50 + return INVALID;
2.51 }
2.52 } //namespace hugo
2.53
3.1 --- a/src/work/marci/bfsit_vs_byhand.cc Fri May 07 10:57:31 2004 +0000
3.2 +++ b/src/work/marci/bfsit_vs_byhand.cc Fri May 07 11:57:34 2004 +0000
3.3 @@ -19,15 +19,17 @@
3.4 typedef Graph::EdgeIt EdgeIt;
3.5 typedef Graph::OutEdgeIt OutEdgeIt;
3.6
3.7 - Graph G;
3.8 + Graph g;
3.9 Node s, t;
3.10 - Graph::EdgeMap<int> cap(G);
3.11 - readDimacsMaxFlow(std::cin, G, s, t, cap);
3.12 - Graph::NodeMap<OutEdgeIt> pred(G);
3.13 + Graph::EdgeMap<int> cap(g);
3.14 + //readDimacsMaxFlow(std::cin, g, s, t, cap);
3.15 + readDimacs(std::cin, g);
3.16 +
3.17 + Graph::NodeMap<OutEdgeIt> pred(g);
3.18 Timer ts;
3.19 {
3.20 ts.reset();
3.21 - Graph::NodeMap<bool> reached(G);
3.22 + Graph::NodeMap<bool> reached(g);
3.23 reached.set(s, true);
3.24 pred.set(s, INVALID);
3.25 std::queue<Node> bfs_queue;
3.26 @@ -36,8 +38,8 @@
3.27 Node v=bfs_queue.front();
3.28 bfs_queue.pop();
3.29 OutEdgeIt e;
3.30 - for(G.first(e,v); G.valid(e); G.next(e)) {
3.31 - Node w=G.head(e);
3.32 + for(g.first(e,v); g.valid(e); g.next(e)) {
3.33 + Node w=g.head(e);
3.34 if (!reached[w]) {
3.35 bfs_queue.push(w);
3.36 reached.set(w, true);
3.37 @@ -51,12 +53,12 @@
3.38
3.39 {
3.40 ts.reset();
3.41 - BfsIterator< Graph, Graph::NodeMap<bool> > bfs(G);
3.42 + BfsIterator< Graph, Graph::NodeMap<bool> > bfs(g);
3.43 bfs.pushAndSetReached(s);
3.44 pred.set(s, INVALID);
3.45 while (!bfs.finished()) {
3.46 ++bfs;
3.47 - if (G.valid(bfs) && bfs.isBNodeNewlyReached())
3.48 + if (g.valid(bfs) && bfs.isBNodeNewlyReached())
3.49 pred.set(bfs.bNode(), bfs);
3.50 }
3.51 std::cout << ts << std::endl;
4.1 --- a/src/work/marci/lg_vs_sg.cc Fri May 07 10:57:31 2004 +0000
4.2 +++ b/src/work/marci/lg_vs_sg.cc Fri May 07 11:57:34 2004 +0000
4.3 @@ -25,16 +25,17 @@
4.4 typedef Graph::Node Node;
4.5 typedef Graph::EdgeIt EdgeIt;
4.6
4.7 - Graph G;
4.8 + Graph g;
4.9 Node s, t;
4.10 - Graph::EdgeMap<int> cap(G);
4.11 + Graph::EdgeMap<int> cap(g);
4.12 std::ifstream ins(in.c_str());
4.13 - readDimacsMaxFlow(ins, G, s, t, cap);
4.14 + //readDimacsMaxFlow(ins, g, s, t, cap);
4.15 + readDimacs(ins, g, cap, s, t);
4.16
4.17 Timer ts;
4.18 - Graph::EdgeMap<int> flow(G); //0 flow
4.19 + Graph::EdgeMap<int> flow(g); //0 flow
4.20 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
4.21 - max_flow_test(G, s, t, cap, flow/*, true*/);
4.22 + max_flow_test(g, s, t, cap, flow/*, true*/);
4.23
4.24 std::cout << "ListGraph ..." << std::endl;
4.25
4.26 @@ -48,7 +49,7 @@
4.27
4.28 {
4.29 std::cout << "physical blocking flow augmentation ..." << std::endl;
4.30 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
4.31 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.32 ts.reset();
4.33 int i=0;
4.34 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
4.35 @@ -59,7 +60,7 @@
4.36
4.37 // {
4.38 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
4.39 -// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
4.40 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.41 // ts.reset();
4.42 // int i=0;
4.43 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
4.44 @@ -70,7 +71,7 @@
4.45
4.46 {
4.47 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
4.48 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
4.49 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.50 ts.reset();
4.51 int i=0;
4.52 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
4.53 @@ -81,7 +82,7 @@
4.54
4.55 {
4.56 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
4.57 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
4.58 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.59 ts.reset();
4.60 int i=0;
4.61 while (max_flow_test.augmentOnShortestPath()) { ++i; }
4.62 @@ -97,24 +98,25 @@
4.63 typedef Graph::Node Node;
4.64 typedef Graph::EdgeIt EdgeIt;
4.65
4.66 - Graph G;
4.67 + Graph g;
4.68 Node s, t;
4.69 - Graph::EdgeMap<int> cap(G);
4.70 + Graph::EdgeMap<int> cap(g);
4.71 std::ifstream ins(in.c_str());
4.72 - readDimacsMaxFlow(ins, G, s, t, cap);
4.73 + //readDimacsMaxFlow(ins, g, s, t, cap);
4.74 + readDimacs(ins, g, cap, s, t);
4.75
4.76 Timer ts;
4.77 - Graph::EdgeMap<int> flow(G); //0 flow
4.78 + Graph::EdgeMap<int> flow(g); //0 flow
4.79 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
4.80 - max_flow_test(G, s, t, cap, flow/*, true*/);
4.81 + max_flow_test(g, s, t, cap, flow/*, true*/);
4.82 // MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
4.83 - // max_flow_test(G, s, t, cap, flow);
4.84 + // max_flow_test(g, s, t, cap, flow);
4.85
4.86 std::cout << "SmatrGraph ..." << std::endl;
4.87
4.88 {
4.89 std::cout << "preflow ..." << std::endl;
4.90 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
4.91 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.92 ts.reset();
4.93 max_flow_test.run();
4.94 std::cout << "elapsed time: " << ts << std::endl;
4.95 @@ -123,7 +125,7 @@
4.96
4.97 {
4.98 std::cout << "physical blocking flow augmentation ..." << std::endl;
4.99 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
4.100 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.101 ts.reset();
4.102 int i=0;
4.103 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
4.104 @@ -134,7 +136,7 @@
4.105
4.106 // {
4.107 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
4.108 -// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
4.109 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.110 // ts.reset();
4.111 // int i=0;
4.112 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
4.113 @@ -145,7 +147,7 @@
4.114
4.115 {
4.116 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
4.117 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
4.118 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.119 ts.reset();
4.120 int i=0;
4.121 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
4.122 @@ -156,7 +158,7 @@
4.123
4.124 {
4.125 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
4.126 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
4.127 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
4.128 ts.reset();
4.129 int i=0;
4.130 while (max_flow_test.augmentOnShortestPath()) { ++i; }
5.1 --- a/src/work/marci/max_flow_demo.cc Fri May 07 10:57:31 2004 +0000
5.2 +++ b/src/work/marci/max_flow_demo.cc Fri May 07 11:57:34 2004 +0000
5.3 @@ -63,14 +63,15 @@
5.4 // std::cout << sizeof(Bumm) << std::endl;
5.5
5.6
5.7 - Graph G;
5.8 + Graph g;
5.9 Node s, t;
5.10 - Graph::EdgeMap<int> cap(G);
5.11 - readDimacsMaxFlow(std::cin, G, s, t, cap);
5.12 + Graph::EdgeMap<int> cap(g);
5.13 + //readDimacsMaxFlow(std::cin, g, s, t, cap);
5.14 + readDimacs(std::cin, g, cap, s, t);
5.15 Timer ts;
5.16 - Graph::EdgeMap<int> flow(G); //0 flow
5.17 + Graph::EdgeMap<int> flow(g); //0 flow
5.18 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
5.19 - max_flow_test(G, s, t, cap, flow);
5.20 + max_flow_test(g, s, t, cap, flow);
5.21
5.22 {
5.23 std::cout << "preflow ..." << std::endl;
5.24 @@ -82,7 +83,7 @@
5.25
5.26 {
5.27 std::cout << "preflow ..." << std::endl;
5.28 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
5.29 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
5.30 ts.reset();
5.31 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
5.32 std::cout << "elapsed time: " << ts << std::endl;
5.33 @@ -91,7 +92,7 @@
5.34
5.35 // {
5.36 // std::cout << "wrapped preflow ..." << std::endl;
5.37 -// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
5.38 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
5.39 // ts.reset();
5.40 // pre_flow_res.run();
5.41 // std::cout << "elapsed time: " << ts << std::endl;
5.42 @@ -100,7 +101,7 @@
5.43
5.44 {
5.45 std::cout << "physical blocking flow augmentation ..." << std::endl;
5.46 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
5.47 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
5.48 ts.reset();
5.49 int i=0;
5.50 while (max_flow_test.augmentOnBlockingFlow<MutableGraph>()) { ++i; }
5.51 @@ -111,7 +112,7 @@
5.52
5.53 // {
5.54 // std::cout << "faster physical blocking flow augmentation ..." << std::endl;
5.55 -// FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
5.56 +// FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
5.57 // ts.reset();
5.58 // int i=0;
5.59 // while (max_flow_test.augmentOnBlockingFlow1<MutableGraph>()) { ++i; }
5.60 @@ -122,7 +123,7 @@
5.61
5.62 {
5.63 std::cout << "on-the-fly blocking flow augmentation ..." << std::endl;
5.64 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
5.65 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
5.66 ts.reset();
5.67 int i=0;
5.68 while (max_flow_test.augmentOnBlockingFlow2()) { ++i; }
5.69 @@ -133,7 +134,7 @@
5.70
5.71 {
5.72 std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
5.73 - FOR_EACH_LOC(Graph::EdgeIt, e, G) flow.set(e, 0);
5.74 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
5.75 ts.reset();
5.76 int i=0;
5.77 while (max_flow_test.augmentOnShortestPath()) { ++i; }
6.1 --- a/src/work/marci/top_sort.dim Fri May 07 10:57:31 2004 +0000
6.2 +++ b/src/work/marci/top_sort.dim Fri May 07 11:57:34 2004 +0000
6.3 @@ -2,5 +2,5 @@
6.4 a 1 3
6.5 a 2 3
6.6 a 3 5
6.7 -a 3 4
6.8 +a 4 3
6.9 a 5 4
6.10 \ No newline at end of file
7.1 --- a/src/work/marci/top_sort_test.cc Fri May 07 10:57:31 2004 +0000
7.2 +++ b/src/work/marci/top_sort_test.cc Fri May 07 11:57:34 2004 +0000
7.3 @@ -7,6 +7,7 @@
7.4 #include <bfs_dfs_misc.h>
7.5 #include <list_graph.h>
7.6 #include <hugo/graph_wrapper.h>
7.7 +#include <hugo/maps.h>
7.8
7.9 using namespace hugo;
7.10
7.11 @@ -16,7 +17,8 @@
7.12 readDimacs(std::cin, g);
7.13 {
7.14 std::list<Graph::Node> l;
7.15 - topSort(g, l);
7.16 + NullMap<Graph::Node, Graph::Edge> pred;
7.17 + topSort(g, l, pred);
7.18 std::cout << "Leaving order of dfs which is pretopological..." << std::endl;
7.19 for(std::list<Graph::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) {
7.20 std::cout << *i << " ";
7.21 @@ -28,7 +30,8 @@
7.22 typedef RevGraphWrapper<Graph> GW;
7.23 GW gw(g);
7.24 std::list<GW::Node> l;
7.25 - topSort(gw, l);
7.26 + NullMap<GW::Node, GW::Edge> pred;
7.27 + topSort(gw, l, pred);
7.28 std::cout << "Same in the revered oriented graph..." << std::endl;
7.29 for(std::list<GW::Node>::const_iterator i=l.begin(); i!=l.end(); ++i) {
7.30 std::cout << *i << " ";