1.1 --- a/src/work/marci/bfs_dfs.h Mon May 17 15:11:05 2004 +0000
1.2 +++ b/src/work/marci/bfs_dfs.h Wed May 19 16:06:57 2004 +0000
1.3 @@ -106,19 +106,19 @@
1.4 }
1.5 return *this;
1.6 }
1.7 - /// Guess what?
1.8 + /// Returns true iff the algorithm is finished.
1.9 bool finished() const { return bfs_queue.empty(); }
1.10 /// The conversion operator makes for converting the bfs-iterator
1.11 /// to an \c out-edge-iterator.
1.12 ///\bug Edge have to be in HUGO 0.2
1.13 operator OutEdgeIt() const { return actual_edge; }
1.14 - /// Guess what?
1.15 + /// Returns if b-node has been reached just now.
1.16 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.17 - /// Guess what?
1.18 + /// Returns if a-node is examined.
1.19 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
1.20 - /// Guess what?
1.21 + /// Returns a-node of the actual edge, so does if the edge is invalid.
1.22 Node aNode() const { return bfs_queue.front(); }
1.23 - /// Guess what?
1.24 + /// \pre The actual edge have to be valid.
1.25 Node bNode() const { return graph->bNode(actual_edge); }
1.26 /// Guess what?
1.27 const ReachedMap& getReachedMap() const { return reached; }
1.28 @@ -249,17 +249,20 @@
1.29 }
1.30 return *this;
1.31 }
1.32 - /// Guess what?
1.33 + /// Returns true iff the algorithm is finished.
1.34 bool finished() const { return dfs_stack.empty(); }
1.35 - /// Guess what?
1.36 + /// The conversion operator makes for converting the bfs-iterator
1.37 + /// to an \c out-edge-iterator.
1.38 + ///\bug Edge have to be in HUGO 0.2
1.39 operator OutEdgeIt() const { return actual_edge; }
1.40 - /// Guess what?
1.41 + /// Returns if b-node has been reached just now.
1.42 bool isBNodeNewlyReached() const { return b_node_newly_reached; }
1.43 - /// Guess what?
1.44 + /// Returns if a-node is examined.
1.45 bool isANodeExamined() const { return !(graph->valid(actual_edge)); }
1.46 - /// Guess what?
1.47 + /// Returns a-node of the actual edge, so does if the edge is invalid.
1.48 Node aNode() const { return actual_node; /*FIXME*/}
1.49 - /// Guess what?
1.50 + /// Returns b-node of the actual edge.
1.51 + /// \pre The actual edge have to be valid.
1.52 Node bNode() const { return graph->bNode(actual_edge); }
1.53 /// Guess what?
1.54 const ReachedMap& getReachedMap() const { return reached; }
2.1 --- a/src/work/marci/leda/leda_graph_wrapper.h Mon May 17 15:11:05 2004 +0000
2.2 +++ b/src/work/marci/leda/leda_graph_wrapper.h Wed May 19 16:06:57 2004 +0000
2.3 @@ -40,6 +40,8 @@
2.4
2.5 template <typename T> class NodeMap;
2.6 template <typename T> class EdgeMap;
2.7 + template <typename T> class NodeMapWrapper;
2.8 + template <typename T> class EdgeMapWrapper;
2.9
2.10 class Node;
2.11 class NodeIt;
2.12 @@ -291,6 +293,49 @@
2.13 //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
2.14 };
2.15
2.16 +
2.17 + ///Read/write map from the nodes to type \c T.
2.18 + template<typename T> class NodeMapWrapper
2.19 + {
2.20 + leda_node_map<T>* leda_stuff;
2.21 + public:
2.22 + typedef T ValueType;
2.23 + typedef Node KeyType;
2.24 +
2.25 + NodeMapWrapper(leda_node_map<T>& _leda_stuff) :
2.26 + leda_stuff(&_leda_stuff) { }
2.27 + //NodeMap(leda_node_map& &G, T t) : leda_stuff(*(G.l_graph), t) {}
2.28 +
2.29 + void set(Node i, T t) { (*leda_stuff)[i.l_n]=t; }
2.30 + T get(Node i) const { return (*leda_stuff)[i.l_n]; } //FIXME: Is it necessary
2.31 + T &operator[](Node i) { return (*leda_stuff)[i.l_n]; }
2.32 + const T &operator[](Node i) const { return (*leda_stuff)[i.l_n]; }
2.33 +
2.34 + void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
2.35 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
2.36 + };
2.37 +
2.38 + ///Read/write map from the edges to type \c T.
2.39 + template<typename T> class EdgeMapWrapper
2.40 + {
2.41 + leda_edge_map<T>* leda_stuff;
2.42 + public:
2.43 + typedef T ValueType;
2.44 + typedef Edge KeyType;
2.45 +
2.46 + EdgeMapWrapper(leda_edge_map<T>& _leda_stuff) :
2.47 + leda_stuff(_leda_stuff) { }
2.48 + //EdgeMap(const LedaGraphWrapper &G, T t) : leda_stuff(*(G.l_graph), t) {}
2.49 +
2.50 + void set(Edge i, T t) { (*leda_stuff)[i.l_e]=t; }
2.51 + T get(Edge i) const { return (*leda_stuff)[i.l_e]; } //FIXME: Is it necessary
2.52 + T &operator[](Edge i) { return (*leda_stuff)[i.l_e]; }
2.53 + const T &operator[](Edge i) const { return (*leda_stuff)[i.l_e]; }
2.54 +
2.55 + void update() { /*leda_stuff.init(leda_stuff.get_graph());*/ }
2.56 + //void update(T a) { leda_stuff.init(leda_stuff.get_graph()/**(G.l_graph)*/, a); } //FIXME: Is it necessary
2.57 + };
2.58 +
2.59 };
2.60
2.61
3.1 --- a/src/work/marci/max_flow_demo.cc Mon May 17 15:11:05 2004 +0000
3.2 +++ b/src/work/marci/max_flow_demo.cc Wed May 19 16:06:57 2004 +0000
3.3 @@ -72,6 +72,7 @@
3.4 Graph::EdgeMap<int> flow(g); //0 flow
3.5 MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
3.6 max_flow_test(g, s, t, cap, flow);
3.7 + Graph::NodeMap<bool> cut(g);
3.8
3.9 {
3.10 std::cout << "preflow ..." << std::endl;
3.11 @@ -79,6 +80,14 @@
3.12 max_flow_test.run();
3.13 std::cout << "elapsed time: " << ts << std::endl;
3.14 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.15 + max_flow_test.actMinCut(cut);
3.16 +
3.17 + FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.18 + if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
3.19 + std::cout << "Slackness does not hold!" << std::endl;
3.20 + if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
3.21 + std::cout << "Slackness does not hold!" << std::endl;
3.22 + }
3.23 }
3.24
3.25 {
3.26 @@ -88,6 +97,13 @@
3.27 max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
3.28 std::cout << "elapsed time: " << ts << std::endl;
3.29 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.30 +
3.31 + FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.32 + if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
3.33 + std::cout << "Slackness does not hold!" << std::endl;
3.34 + if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
3.35 + std::cout << "Slackness does not hold!" << std::endl;
3.36 + }
3.37 }
3.38
3.39 // {
3.40 @@ -108,6 +124,13 @@
3.41 std::cout << "elapsed time: " << ts << std::endl;
3.42 std::cout << "number of augmentation phases: " << i << std::endl;
3.43 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.44 +
3.45 + FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.46 + if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
3.47 + std::cout << "Slackness does not hold!" << std::endl;
3.48 + if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
3.49 + std::cout << "Slackness does not hold!" << std::endl;
3.50 + }
3.51 }
3.52
3.53 // {
3.54 @@ -130,6 +153,13 @@
3.55 std::cout << "elapsed time: " << ts << std::endl;
3.56 std::cout << "number of augmentation phases: " << i << std::endl;
3.57 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.58 +
3.59 + FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.60 + if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
3.61 + std::cout << "Slackness does not hold!" << std::endl;
3.62 + if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
3.63 + std::cout << "Slackness does not hold!" << std::endl;
3.64 + }
3.65 }
3.66
3.67 {
3.68 @@ -141,8 +171,32 @@
3.69 std::cout << "elapsed time: " << ts << std::endl;
3.70 std::cout << "number of augmentation phases: " << i << std::endl;
3.71 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.72 +
3.73 + FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.74 + if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
3.75 + std::cout << "Slackness does not hold!" << std::endl;
3.76 + if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
3.77 + std::cout << "Slackness does not hold!" << std::endl;
3.78 + }
3.79 }
3.80
3.81 + {
3.82 + std::cout << "on-the-fly shortest path augmentation ..." << std::endl;
3.83 + FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
3.84 + ts.reset();
3.85 + int i=0;
3.86 + while (max_flow_test.augmentOnShortestPath2()) { ++i; }
3.87 + std::cout << "elapsed time: " << ts << std::endl;
3.88 + std::cout << "number of augmentation phases: " << i << std::endl;
3.89 + std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
3.90 +
3.91 + FOR_EACH_LOC(Graph::EdgeIt, e, g) {
3.92 + if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
3.93 + std::cout << "Slackness does not hold!" << std::endl;
3.94 + if (!cut[g.tail(e)] && cut[g.head(e)] && flow[e]>0)
3.95 + std::cout << "Slackness does not hold!" << std::endl;
3.96 + }
3.97 + }
3.98
3.99 return 0;
3.100 }