NewMapWin has become Dialog instead of Window. Therefore it is created dynamically, when there is need for it, instead of keeping one instance in memory. This solution is slower, but more correct than before.
2 * demo/sub_graph_adaptor_demo.cc - Part of LEMON, a generic C++ optimization
5 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
6 * (Egervary Research Group on Combinatorial Optimization, EGRES).
8 * Permission to use, modify and distribute this software is granted
9 * provided that this copyright notice appears in all copies. For
10 * precise terms see the accompanying LICENSE file.
12 * This software is provided "AS IS" with no warranty of any kind,
13 * express or implied, and with no claim as to its suitability for any
20 ///\brief Computing maximum number of edge-disjoint shortest paths
22 /// This program computes a maximum number of edge-disjoint shortest paths
23 /// between nodes \c s and \c t.
25 /// \include sub_graph_adaptor_demo.cc
27 // Use a DIMACS max flow file as input.
28 // sub_graph_adaptor_demo < dimacs_max_flow_file
29 // Modified to eat lemon graph format!
35 #include <lemon/smart_graph.h>
36 #include <lemon/dijkstra.h>
37 #include <lemon/maps.h>
38 #include <lemon/graph_adaptor.h>
39 #include <lemon/dimacs.h>
40 #include <lemon/preflow.h>
41 #include <tight_edge_filter_map.h>
43 #include <lemon/graph_reader.h>
46 using namespace lemon;
51 int main(int argc, char *argv[])
55 std::cerr << "USAGE: sub_graph_adaptor_demo input_file.lgf" << std::endl;
56 std::cerr << "The file 'input_file.lgf' has to contain a max flow "
57 << "instance in \n LEMON format "
58 << "(e.g. sub_gad_input.lgf is such a file)."
64 //input stream to read the graph from
65 std::ifstream is(argv[1]);
67 typedef SmartGraph Graph;
69 typedef Graph::Edge Edge;
70 typedef Graph::Node Node;
71 typedef Graph::EdgeIt EdgeIt;
72 typedef Graph::NodeIt NodeIt;
73 typedef Graph::EdgeMap<int> LengthMap;
79 //readDimacs(is, g, length, s, t);
82 GraphReader<SmartGraph> reader(is,g);
83 reader.readNode("source",s).readNode("target",t)
84 .readEdgeMap("length",length).run();
86 cout << "edges with lengths (of form id, source--length->target): " << endl;
87 for(EdgeIt e(g); e!=INVALID; ++e)
88 cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--"
89 << length[e] << "->" << g.id(g.target(e)) << endl;
91 cout << "s: " << g.id(s) << " t: " << g.id(t) << endl;
93 typedef Dijkstra<Graph, LengthMap> Dijkstra;
94 Dijkstra dijkstra(g, length);
97 // This map returns true exactly for those edges which are
98 // tight w.r.t the length funcion and the potential
99 // given by the dijkstra algorithm.
100 typedef TightEdgeFilterMap<Graph, const Dijkstra::DistMap, LengthMap>
102 TightEdgeFilter tight_edge_filter(g, dijkstra.distMap(), length);
104 // ConstMap<Node, bool> const_true_map(true);
105 // This graph contains exaclty the tight edges.
106 // typedef SubGraphAdaptor<Graph, ConstMap<Node, bool>, TightEdgeFilter> SubGW;
107 typedef EdgeSubGraphAdaptor<Graph, TightEdgeFilter> SubGW;
108 SubGW gw(g, tight_edge_filter);
110 ConstMap<Edge, int> const_1_map(1);
111 Graph::EdgeMap<int> flow(g, 0);
112 // Max flow between s and t in the graph of tight edges.
113 Preflow<SubGW, int, ConstMap<Edge, int>, Graph::EdgeMap<int> >
114 preflow(gw, s, t, const_1_map, flow);
117 cout << "maximum number of edge-disjoint shortest paths: "
118 << preflow.flowValue() << endl;
119 cout << "edges of the maximum number of edge-disjoint shortest s-t paths: "
121 for(EdgeIt e(g); e!=INVALID; ++e)
123 cout << " " << g.id(e) << ", "
124 << g.id(g.source(e)) << "--"
125 << length[e] << "->" << g.id(g.target(e)) << endl;