Demo file for SubGraphWrapper<Graph>. Documentation will be added later.
The purpose of this graph is to have an easy and short demo for the above class.
1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/demo/sub_graph_wrapper_demo.cc Thu Sep 16 13:59:36 2004 +0000
1.3 @@ -0,0 +1,71 @@
1.4 +// -*- c++ -*-
1.5 +
1.6 +// Use a DIMACS max flow file as stdin.
1.7 +// sub_graph_wrapper_demo < dimacs_max_flow_file
1.8 +
1.9 +#include <iostream>
1.10 +#include <fstream>
1.11 +
1.12 +#include <hugo/smart_graph.h>
1.13 +#include <hugo/dijkstra.h>
1.14 +#include <hugo/maps.h>
1.15 +#include <hugo/graph_wrapper.h>
1.16 +#include <hugo/dimacs.h>
1.17 +#include <hugo/preflow.h>
1.18 +#include <tight_edge_filter_map.h>
1.19 +
1.20 +using namespace hugo;
1.21 +
1.22 +using std::cout;
1.23 +using std::endl;
1.24 +
1.25 +int main()
1.26 +{
1.27 + typedef SmartGraph Graph;
1.28 +
1.29 + typedef Graph::Edge Edge;
1.30 + typedef Graph::Node Node;
1.31 + typedef Graph::EdgeIt EdgeIt;
1.32 + typedef Graph::NodeIt NodeIt;
1.33 + typedef Graph::EdgeMap<int> LengthMap;
1.34 +
1.35 + Graph g;
1.36 + Node s, t;
1.37 + LengthMap length(g);
1.38 +
1.39 + readDimacs(std::cin, g, length, s, t);
1.40 +
1.41 + cout << "edges with lengths (of form tail--length->head): " << endl;
1.42 + for(EdgeIt e(g); e!=INVALID; ++e)
1.43 + cout << " " << g.id(g.tail(e)) << "--"
1.44 + << length[e] << "->" << g.id(g.head(e)) << endl;
1.45 +
1.46 + cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
1.47 +
1.48 + typedef Dijkstra<Graph, LengthMap> Dijkstra;
1.49 + Dijkstra dijkstra(g, length);
1.50 + dijkstra.run(s);
1.51 +
1.52 + typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
1.53 + TightEdgeFilter;
1.54 + TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
1.55 +
1.56 + ConstMap<Node, bool> const_true_map(true);
1.57 + typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
1.58 + SubGW gw(g, const_true_map, tight_edge_filter);
1.59 +
1.60 + ConstMap<Edge, int> const_1_map(1);
1.61 + Graph::EdgeMap<int> flow(g, 0);
1.62 + Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
1.63 + preflow(gw, s, t, const_1_map, flow);
1.64 + preflow.run();
1.65 +
1.66 + cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
1.67 + << endl;
1.68 + for(EdgeIt e(g); e!=INVALID; ++e)
1.69 + if (flow[e])
1.70 + cout << " " << g.id(g.tail(e)) << "--"
1.71 + << length[e] << "->" << g.id(g.head(e)) << endl;
1.72 +
1.73 + return 0;
1.74 +}
2.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
2.2 +++ b/src/demo/sub_graph_wrapper_demo.dim Thu Sep 16 13:59:36 2004 +0000
2.3 @@ -0,0 +1,14 @@
2.4 +c HUGO max flow problem
2.5 +p max 7 9
2.6 +n 1 s
2.7 +n 7 t
2.8 +a 1 2 3
2.9 +a 1 3 2
2.10 +a 1 4 1
2.11 +a 2 5 3
2.12 +a 3 5 2
2.13 +a 3 7 5
2.14 +a 3 6 3
2.15 +a 4 6 1
2.16 +a 5 7 2
2.17 +a 6 7 4
3.1 --- a/src/work/makefile Thu Sep 16 13:57:41 2004 +0000
3.2 +++ b/src/work/makefile Thu Sep 16 13:59:36 2004 +0000
3.3 @@ -1,5 +1,5 @@
3.4 INCLUDEDIRS ?= -I.. -I. -I./{marci,jacint,alpar,klao,akos}
3.5 -CXXFLAGS = -g -O0 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
3.6 +CXXFLAGS = -g -O3 -W -Wall $(INCLUDEDIRS) -ansi -pedantic
3.7
3.8 BINARIES ?= bin_heap_demo
3.9
4.1 --- a/src/work/marci/sub_graph_wrapper_demo.cc Thu Sep 16 13:57:41 2004 +0000
4.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
4.3 @@ -1,71 +0,0 @@
4.4 -// -*- c++ -*-
4.5 -
4.6 -// Use a DIMACS max flow file as stdin.
4.7 -// sub_graph_wrapper_demo < dimacs_max_flow_file
4.8 -
4.9 -#include <iostream>
4.10 -#include <fstream>
4.11 -
4.12 -#include <hugo/smart_graph.h>
4.13 -#include <hugo/dijkstra.h>
4.14 -#include <hugo/maps.h>
4.15 -#include <hugo/graph_wrapper.h>
4.16 -#include <hugo/dimacs.h>
4.17 -#include <hugo/preflow.h>
4.18 -#include <tight_edge_filter_map.h>
4.19 -
4.20 -using namespace hugo;
4.21 -
4.22 -using std::cout;
4.23 -using std::endl;
4.24 -
4.25 -int main()
4.26 -{
4.27 - typedef SmartGraph Graph;
4.28 -
4.29 - typedef Graph::Edge Edge;
4.30 - typedef Graph::Node Node;
4.31 - typedef Graph::EdgeIt EdgeIt;
4.32 - typedef Graph::NodeIt NodeIt;
4.33 - typedef Graph::EdgeMap<int> LengthMap;
4.34 -
4.35 - Graph g;
4.36 - Node s, t;
4.37 - LengthMap length(g);
4.38 -
4.39 - readDimacs(std::cin, g, length, s, t);
4.40 -
4.41 - cout << "edges with lengths (of form tail--length->head): " << endl;
4.42 - for(EdgeIt e(g); e!=INVALID; ++e)
4.43 - cout << " " << g.id(g.tail(e)) << "--"
4.44 - << length[e] << "->" << g.id(g.head(e)) << endl;
4.45 -
4.46 - cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
4.47 -
4.48 - typedef Dijkstra<Graph, LengthMap> Dijkstra;
4.49 - Dijkstra dijkstra(g, length);
4.50 - dijkstra.run(s);
4.51 -
4.52 - typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
4.53 - TightEdgeFilter;
4.54 - TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
4.55 -
4.56 - ConstMap<Node, bool> const_true_map(true);
4.57 - typedef SubGraphWrapper<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
4.58 - SubGW gw(g, const_true_map, tight_edge_filter);
4.59 -
4.60 - ConstMap<Edge, int> const_1_map(1);
4.61 - Graph::EdgeMap<int> flow(g, 0);
4.62 - Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
4.63 - preflow(gw, s, t, const_1_map, flow);
4.64 - preflow.run();
4.65 -
4.66 - cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
4.67 - << endl;
4.68 - for(EdgeIt e(g); e!=INVALID; ++e)
4.69 - if (flow[e])
4.70 - cout << " " << g.id(g.tail(e)) << "--"
4.71 - << length[e] << "->" << g.id(g.head(e)) << endl;
4.72 -
4.73 - return 0;
4.74 -}
5.1 --- a/src/work/marci/sub_graph_wrapper_demo.dim Thu Sep 16 13:57:41 2004 +0000
5.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
5.3 @@ -1,14 +0,0 @@
5.4 -c HUGO max flow problem
5.5 -p max 7 9
5.6 -n 1 s
5.7 -n 7 t
5.8 -a 1 2 3
5.9 -a 1 3 2
5.10 -a 1 4 1
5.11 -a 2 5 3
5.12 -a 3 5 2
5.13 -a 3 7 5
5.14 -a 3 6 3
5.15 -a 4 6 1
5.16 -a 5 7 2
5.17 -a 6 7 4