1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/work/athos/bfs_test.cc Tue Jun 01 11:00:24 2004 +0000
1.3 @@ -0,0 +1,79 @@
1.4 +// -*- c++ -*-
1.5 +#include <iostream>
1.6 +#include <fstream>
1.7 +
1.8 +#include <sage_graph.h>
1.9 +//#include <smart_graph.h>
1.10 +#include <hugo/dimacs.h>
1.11 +#include <hugo/time_measure.h>
1.12 +#include <hugo/for_each_macros.h>
1.13 +#include <bfs_dfs.h>
1.14 +
1.15 +using namespace hugo;
1.16 +
1.17 +int main() {
1.18 + typedef SageGraph Graph;
1.19 + typedef Graph::Node Node;
1.20 + typedef Graph::NodeIt NodeIt;
1.21 + typedef Graph::Edge Edge;
1.22 + typedef Graph::EdgeIt EdgeIt;
1.23 + typedef Graph::OutEdgeIt OutEdgeIt;
1.24 +
1.25 + Graph g;
1.26 + Node s, t;
1.27 + Graph::EdgeMap<int> cap(g);
1.28 + //readDimacsMaxFlow(std::cin, g, s, t, cap);
1.29 + readDimacs(std::cin, g);
1.30 +
1.31 + Graph::NodeMap<OutEdgeIt> pred(g);
1.32 +
1.33 + Timer ts;
1.34 + /*
1.35 + {
1.36 + ts.reset();
1.37 + Graph::NodeMap<bool> reached(g);
1.38 + reached.set(s, true);
1.39 + pred.set(s, INVALID);
1.40 + std::queue<Node> bfs_queue;
1.41 + bfs_queue.push(t);
1.42 + while (!bfs_queue.empty()) {
1.43 + Node v=bfs_queue.front();
1.44 + bfs_queue.pop();
1.45 + OutEdgeIt e;
1.46 + for(g.first(e,v); g.valid(e); g.next(e)) {
1.47 + Node w=g.head(e);
1.48 + if (!reached[w]) {
1.49 + bfs_queue.push(w);
1.50 + reached.set(w, true);
1.51 + pred.set(w, e);
1.52 + }
1.53 + }
1.54 + }
1.55 +
1.56 + std::cout << ts << std::endl;
1.57 + }
1.58 + */
1.59 +
1.60 + {
1.61 + ts.reset();
1.62 + Graph::NodeMap<bool> bfs_reached(g);
1.63 + Graph::NodeMap<Edge> bfs_pred(g);
1.64 + Graph::NodeMap<int> bfs_dist(g);
1.65 +
1.66 + Bfs< Graph, Graph::NodeMap<bool>,
1.67 + Graph::NodeMap<Edge>, Graph::NodeMap<int> >
1.68 + bfs(g,bfs_reached, bfs_pred, bfs_dist );
1.69 + bfs.run(s);
1.70 + /*
1.71 + pred.set(s, INVALID);
1.72 + while (!bfs.finished()) {
1.73 + ++bfs;
1.74 + if (g.valid(bfs) && bfs.isBNodeNewlyReached())
1.75 + pred.set(bfs.bNode(), bfs);
1.76 + }
1.77 + */
1.78 + std::cout << ts << std::endl;
1.79 + }
1.80 +
1.81 + return 0;
1.82 +}
2.1 --- a/src/work/athos/makefile Tue Jun 01 08:30:20 2004 +0000
2.2 +++ b/src/work/athos/makefile Tue Jun 01 11:00:24 2004 +0000
2.3 @@ -1,4 +1,4 @@
2.4 -BINARIES = min_cost_flow
2.5 +BINARIES = bfs_test min_cost_flow
2.6 INCLUDEDIRS= -I../.. -I.. -I../{athos,klao,marci,jacint,alpar,johanna,akos}
2.7 include ../makefile
2.8
3.1 --- a/src/work/athos/mincostflow.h Tue Jun 01 08:30:20 2004 +0000
3.2 +++ b/src/work/athos/mincostflow.h Tue Jun 01 11:00:24 2004 +0000
3.3 @@ -213,8 +213,11 @@
3.4 typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>
3.5 bfs_pred(res_ab_graph);
3.6 NullMap<typename ResAbGraph::Node, int> bfs_dist_dummy;
3.7 + //Teszt celbol:
3.8 + //BfsIterator<ResAbGraph, typename ResAbGraph::template NodeMap<bool> >
3.9 + //izebize(res_ab_graph, bfs_reached);
3.10 //We want to run bfs-es (more) on this graph 'res_ab_graph'
3.11 - Bfs < ResAbGraph ,
3.12 + Bfs < const ResAbGraph ,
3.13 typename ResAbGraph::template NodeMap<bool>,
3.14 typename ResAbGraph::template NodeMap<typename ResAbGraph::Edge>,
3.15 NullMap<typename ResAbGraph::Node, int> >
3.16 @@ -233,6 +236,8 @@
3.17
3.18 Dijkstra<ResGraph, ModCostMap> dijkstra(res_graph, mod_cost);
3.19
3.20 + //We will use the number of the nodes of the graph often
3.21 + int number_of_nodes = graph.nodeNum();
3.22
3.23 while (max_excess > 0){
3.24
3.25 @@ -250,9 +255,9 @@
3.26 SupplyDemand buf=8*number_of_nodes*delta;
3.27 typename std::list<Edge>::iterator i = nonabundant_arcs.begin();
3.28 while ( i != nonabundant_arcs.end() ){
3.29 - if (flow[i]>=buf){
3.30 - Node a = abundant_components.find(res_graph.head(i));
3.31 - Node b = abundant_components.find(res_graph.tail(i));
3.32 + if (flow[*i]>=buf){
3.33 + Node a = abundant_components.find(res_graph.head(*i));
3.34 + Node b = abundant_components.find(res_graph.tail(*i));
3.35 //Merge
3.36 if (a != b){
3.37 abundant_components.join(a,b);
3.38 @@ -269,28 +274,31 @@
3.39 //If the non_root node has excess/deficit at all
3.40 if (qty_to_augment>0){
3.41 //Find path and augment
3.42 - bfs.run(non_root);
3.43 + bfs.run(typename AbundantGraph::Node(non_root));
3.44 //root should be reached
3.45
3.46 //Augmenting on the found path
3.47 Node n=root;
3.48 ResGraphEdge e;
3.49 while (n!=non_root){
3.50 - e = bfs_pred(n);
3.51 + e = bfs_pred[n];
3.52 n = res_graph.tail(e);
3.53 res_graph.augment(e,qty_to_augment);
3.54 }
3.55
3.56 //We know that non_root had positive excess
3.57 - excess_nodes[non_root] -= qty_to_augment;
3.58 + excess_nodes.set(non_root,
3.59 + excess_nodes[non_root] - qty_to_augment);
3.60 //But what about root node
3.61 //It might have been positive and so became larger
3.62 if (excess_deficit[root]>0){
3.63 - excess_nodes[root] += qty_to_augment;
3.64 + excess_nodes.set(root,
3.65 + excess_nodes[root] + qty_to_augment);
3.66 }
3.67 else{
3.68 //Or negative but not turned into positive
3.69 - deficit_nodes[root] -= qty_to_augment;
3.70 + deficit_nodes.set(root,
3.71 + deficit_nodes[root] - qty_to_augment);
3.72 }
3.73
3.74 //Update the excess_deficit map
3.75 @@ -303,7 +311,7 @@
3.76 //What happens to i?
3.77 //Marci and Zsolt says I shouldn't do such things
3.78 nonabundant_arcs.erase(i++);
3.79 - abundant_arcs[i] = true;
3.80 + abundant_arcs[*i] = true;
3.81 }
3.82 else
3.83 ++i;
3.84 @@ -369,7 +377,7 @@
3.85
3.86 }
3.87 else{
3.88 - excess_nodes[s] -= delta;
3.89 + excess_nodes.set(s, excess_nodes[s] - delta);
3.90 }
3.91 //Update the deficit_nodes heap
3.92 if (delta >= deficit_nodes[t]){
3.93 @@ -379,7 +387,7 @@
3.94
3.95 }
3.96 else{
3.97 - deficit_nodes[t] -= delta;
3.98 + deficit_nodes.set(t, deficit_nodes[t] - delta);
3.99 }
3.100 //Dijkstra part ends here
3.101
3.102 @@ -414,7 +422,7 @@
3.103 }//while(max_excess > 0)
3.104
3.105
3.106 - return i;
3.107 + //return i;
3.108 }
3.109
3.110
4.1 --- a/src/work/marci/bfs_dfs.h Tue Jun 01 08:30:20 2004 +0000
4.2 +++ b/src/work/marci/bfs_dfs.h Tue Jun 01 11:00:24 2004 +0000
4.3 @@ -151,7 +151,9 @@
4.4 /// The algorithm will search in a bfs order for
4.5 /// the nodes which are \c false initially.
4.6 /// The constructor makes no initial changes on the maps.
4.7 - Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) : BfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred), dist(&_dist) { }
4.8 + Bfs<Graph, ReachedMap, PredMap, DistMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred, DistMap& _dist) :
4.9 + BfsIterator<Graph, ReachedMap>(_graph, _reached),
4.10 + pred(_pred), dist(_dist) { }
4.11 /// \c s is marked to be reached and pushed in the bfs queue.
4.12 /// If the queue is empty, then the first out-edge is processed.
4.13 /// If \c s was not marked previously, then
4.14 @@ -296,7 +298,7 @@
4.15 /// The algorithm will search in a dfs order for
4.16 /// the nodes which are \c false initially.
4.17 /// The constructor makes no initial changes on the maps.
4.18 - Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(&_pred) { }
4.19 + Dfs<Graph, ReachedMap, PredMap>(const Graph& _graph, ReachedMap& _reached, PredMap& _pred) : DfsIterator<Graph, ReachedMap>(_graph, _reached), pred(_pred) { }
4.20 /// \c s is marked to be reached and pushed in the bfs queue.
4.21 /// If the queue is empty, then the first out-edge is processed.
4.22 /// If \c s was not marked previously, then