1.1 --- a/src/hugo/graph_wrapper.h Tue Sep 14 09:53:57 2004 +0000
1.2 +++ b/src/hugo/graph_wrapper.h Tue Sep 14 10:09:24 2004 +0000
1.3 @@ -229,6 +229,9 @@
1.4 public:
1.5 NodeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
1.6 NodeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
1.7 +// NodeMap(const NodeMap<T>& map) : Parent(map) { }
1.8 +// template<typename Map>
1.9 +// NodeMap(const Map& map) : Parent(map) { }
1.10 };
1.11
1.12 template<typename T> class EdgeMap : public Graph::template EdgeMap<T> {
1.13 @@ -236,6 +239,9 @@
1.14 public:
1.15 EdgeMap(const GraphWrapper<Graph>& gw) : Parent(*(gw.graph)) { }
1.16 EdgeMap(const GraphWrapper<Graph>& gw, T a) : Parent(*(gw.graph), a) { }
1.17 +// EdgeMap(const EdgeMap<T>& map) : Parent(map) { }
1.18 +// template<typename Map>
1.19 +// EdgeMap(const Map& map) : Parent(map) { }
1.20 };
1.21 };
1.22
2.1 --- a/src/hugo/preflow.h Tue Sep 14 09:53:57 2004 +0000
2.2 +++ b/src/hugo/preflow.h Tue Sep 14 10:09:24 2004 +0000
2.3 @@ -344,7 +344,7 @@
2.4 ///Sets \c M to the characteristic vector of a minimum value
2.5 ///cut. This method can be called both after running \ref
2.6 ///phase1 and \ref phase2. It is much faster after
2.7 - ///\ref phase1. \pre M should be a node map of bools. \pre
2.8 + ///\ref phase1. \pre M should be a bool-valued node-map. \pre
2.9 ///If \ref mincut is called after \ref phase2 then M should
2.10 ///be initialized to false.
2.11 template<typename _CutMap>
3.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
3.2 +++ b/src/test/graph_wrapper_test.cc Tue Sep 14 10:09:24 2004 +0000
3.3 @@ -0,0 +1,138 @@
3.4 +#include<iostream>
3.5 +#include<hugo/smart_graph.h>
3.6 +#include<hugo/skeletons/graph.h>
3.7 +#include<hugo/list_graph.h>
3.8 +#include<hugo/full_graph.h>
3.9 +#include<hugo/graph_wrapper.h>
3.10 +
3.11 +#include"test_tools.h"
3.12 +#include"graph_test.h"
3.13 +
3.14 +/**
3.15 +\file
3.16 +This test makes consistency checks of list graph structures.
3.17 +
3.18 +G.addNode(), G.addEdge(), G.tail(), G.head()
3.19 +
3.20 +\todo Checks for empty graphs and isolated points.
3.21 +conversion.
3.22 +*/
3.23 +
3.24 +using namespace hugo;
3.25 +
3.26 +template<class Graph> void bidirPetersen(Graph &G)
3.27 +{
3.28 + typedef typename Graph::Edge Edge;
3.29 + typedef typename Graph::EdgeIt EdgeIt;
3.30 +
3.31 + checkGraphEdgeList(G,15);
3.32 +
3.33 + std::vector<Edge> ee;
3.34 +
3.35 + for(EdgeIt e(G);e!=INVALID;++e) ee.push_back(e);
3.36 +
3.37 + for(typename std::vector<Edge>::iterator p=ee.begin();p!=ee.end();p++)
3.38 + G.addEdge(G.head(*p),G.tail(*p));
3.39 +}
3.40 +
3.41 +template<class Graph> void checkPetersen(Graph &G)
3.42 +{
3.43 + typedef typename Graph::Node Node;
3.44 +
3.45 + typedef typename Graph::EdgeIt EdgeIt;
3.46 + typedef typename Graph::NodeIt NodeIt;
3.47 +
3.48 + checkGraphNodeList(G,10);
3.49 + checkGraphEdgeList(G,30);
3.50 +
3.51 + for(NodeIt n(G);n!=INVALID;++n) {
3.52 + checkGraphInEdgeList(G,n,3);
3.53 + checkGraphOutEdgeList(G,n,3);
3.54 + ++n;
3.55 + }
3.56 +}
3.57 +
3.58 +//Compile GraphSkeleton
3.59 +template void checkCompileStaticGraph<skeleton::StaticGraphSkeleton>
3.60 +(skeleton::StaticGraphSkeleton &);
3.61 +
3.62 +template void checkCompileGraph<skeleton::GraphSkeleton>
3.63 +(skeleton::GraphSkeleton &);
3.64 +
3.65 +template void checkCompileErasableGraph<skeleton::ErasableGraphSkeleton>
3.66 +(skeleton::ErasableGraphSkeleton &);
3.67 +
3.68 +//Compile SmartGraph
3.69 +typedef SmartGraph Graph;
3.70 +typedef GraphWrapper<Graph> GW;
3.71 +template void checkCompileStaticGraph<GW>(GW &);
3.72 +//template void checkCompileGraphFindEdge<SmartGraph>(SmartGraph &);
3.73 +
3.74 +//Compile SymSmartGraph
3.75 +typedef RevGraphWrapper<Graph> RevGW;
3.76 +template void checkCompileStaticGraph<RevGW>(RevGW &);
3.77 +//template void checkCompileGraphFindEdge<SymSmartGraph>(SymSmartGraph &);
3.78 +
3.79 +// //Compile ListGraph
3.80 +// template void checkCompileGraph<ListGraph>(ListGraph &);
3.81 +// template void checkCompileErasableGraph<ListGraph>(ListGraph &);
3.82 +// template void checkCompileGraphFindEdge<ListGraph>(ListGraph &);
3.83 +
3.84 +
3.85 +// //Compile SymListGraph
3.86 +// template void checkCompileGraph<SymListGraph>(SymListGraph &);
3.87 +// template void checkCompileErasableGraph<SymListGraph>(SymListGraph &);
3.88 +// template void checkCompileGraphFindEdge<SymListGraph>(SymListGraph &);
3.89 +
3.90 +// //Compile FullGraph
3.91 +// template void checkCompileStaticGraph<FullGraph>(FullGraph &);
3.92 +// template void checkCompileGraphFindEdge<FullGraph>(FullGraph &);
3.93 +
3.94 +// //Compile EdgeSet <ListGraph>
3.95 +// template void checkCompileGraph<EdgeSet <ListGraph> >(EdgeSet <ListGraph> &);
3.96 +// template void checkCompileGraphEraseEdge<EdgeSet <ListGraph> >
3.97 +// (EdgeSet <ListGraph> &);
3.98 +// template void checkCompileGraphFindEdge<EdgeSet <ListGraph> >
3.99 +// (EdgeSet <ListGraph> &);
3.100 +
3.101 +// //Compile EdgeSet <NodeSet>
3.102 +// template void checkCompileGraph<EdgeSet <NodeSet> >(EdgeSet <NodeSet> &);
3.103 +// template void checkCompileGraphEraseEdge<EdgeSet <NodeSet> >
3.104 +// (EdgeSet <NodeSet> &);
3.105 +// template void checkCompileGraphFindEdge<EdgeSet <NodeSet> >
3.106 +// (EdgeSet <NodeSet> &);
3.107 +
3.108 +
3.109 +int main()
3.110 +{
3.111 + // {
3.112 +// SmartGraph G;
3.113 +// addPetersen(G);
3.114 +// bidirPetersen(G);
3.115 +// checkPetersen(G);
3.116 +// }
3.117 +// {
3.118 +// ListGraph G;
3.119 +// addPetersen(G);
3.120 +// bidirPetersen(G);
3.121 +// checkPetersen(G);
3.122 +// }
3.123 +// {
3.124 +// SymSmartGraph G;
3.125 +// addPetersen(G);
3.126 +// checkPetersen(G);
3.127 +// }
3.128 +// {
3.129 +// SymListGraph G;
3.130 +// addPetersen(G);
3.131 +// checkPetersen(G);
3.132 +// }
3.133 +
3.134 + ///\file
3.135 + ///\todo map tests.
3.136 + ///\todo copy constr tests.
3.137 +
3.138 + std::cout << __FILE__ ": All tests passed.\n";
3.139 +
3.140 + return 0;
3.141 +}
4.1 --- a/src/work/marci/graph_wrapper_time.cc Tue Sep 14 09:53:57 2004 +0000
4.2 +++ b/src/work/marci/graph_wrapper_time.cc Tue Sep 14 10:09:24 2004 +0000
4.3 @@ -10,7 +10,7 @@
4.4 #include <hugo/invalid.h>
4.5 #include <hugo/time_measure.h>
4.6 #include <hugo/graph_wrapper.h>
4.7 -#include <hugo/max_flow.h>
4.8 +#include <hugo/preflow.h>
4.9 #include <hugo/dimacs.h>
4.10 #include <hugo/list_graph.h>
4.11
4.12 @@ -32,9 +32,9 @@
4.13 Timer ts;
4.14 ts.reset();
4.15
4.16 - typedef MaxFlow<Graph, int, FlowMap, FlowMap> MyMaxFlow;
4.17 - MyMaxFlow max_flow(g, s, t, cap, flow);
4.18 - max_flow.run(MyMaxFlow::NO_FLOW);
4.19 + typedef Preflow<Graph, int, FlowMap, FlowMap> MyPreflow;
4.20 + MyPreflow max_flow(g, s, t, cap, flow);
4.21 + max_flow.run(MyPreflow::NO_FLOW);
4.22 cout << "flow value: " << max_flow.flowValue() << endl;
4.23 cout << ts << endl;
4.24 }
5.1 --- a/src/work/marci/max_flow_demo.cc Tue Sep 14 09:53:57 2004 +0000
5.2 +++ b/src/work/marci/max_flow_demo.cc Tue Sep 14 10:09:24 2004 +0000
5.3 @@ -12,7 +12,7 @@
5.4 #include <hugo/dimacs.h>
5.5 #include <hugo/time_measure.h>
5.6 //#include <graph_wrapper.h>
5.7 -#include <hugo/max_flow.h>
5.8 +#include <hugo/preflow.h>
5.9 #include <augmenting_flow.h>
5.10 //#include <preflow_res.h>
5.11 #include <for_each_macros.h>
5.12 @@ -38,7 +38,7 @@
5.13 readDimacs(std::cin, g, cap, s, t);
5.14 Timer ts;
5.15 Graph::EdgeMap<int> flow(g); //0 flow
5.16 - MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
5.17 + Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
5.18 max_flow_test(g, s, t, cap, flow);
5.19 AugmentingFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >
5.20 augmenting_flow_test(g, s, t, cap, flow);
5.21 @@ -51,7 +51,7 @@
5.22 max_flow_test.run();
5.23 std::cout << "elapsed time: " << ts << std::endl;
5.24 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
5.25 - max_flow_test.actMinCut(cut);
5.26 + max_flow_test.minCut(cut);
5.27
5.28 FOR_EACH_LOC(Graph::EdgeIt, e, g) {
5.29 if (cut[g.tail(e)] && !cut[g.head(e)] && !flow[e]==cap[e])
5.30 @@ -65,7 +65,7 @@
5.31 std::cout << "preflow ..." << std::endl;
5.32 FOR_EACH_LOC(Graph::EdgeIt, e, g) flow.set(e, 0);
5.33 ts.reset();
5.34 - max_flow_test.preflow(MaxFlow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
5.35 + max_flow_test.preflow(Preflow<Graph, int, Graph::EdgeMap<int>, Graph::EdgeMap<int> >::GEN_FLOW);
5.36 std::cout << "elapsed time: " << ts << std::endl;
5.37 std::cout << "flow value: "<< max_flow_test.flowValue() << std::endl;
5.38