1 // -*- c++ -*- |
1 /* -*- C++ -*- |
|
2 * demo/lp_maxflow_demo.cc - Part of LEMON, a generic C++ optimization library |
|
3 * |
|
4 * Copyright (C) 2005 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport |
|
5 * (Egervary Research Group on Combinatorial Optimization, EGRES). |
|
6 * |
|
7 * Permission to use, modify and distribute this software is granted |
|
8 * provided that this copyright notice appears in all copies. For |
|
9 * precise terms see the accompanying LICENSE file. |
|
10 * |
|
11 * This software is provided "AS IS" with no warranty of any kind, |
|
12 * express or implied, and with no claim as to its suitability for any |
|
13 * purpose. |
|
14 * |
|
15 */ |
|
16 |
|
17 ///\ingroup demos |
|
18 ///\file |
|
19 ///\brief Computing maximum number of edge-disjoint shortest paths |
|
20 /// |
|
21 /// This program computes a maximum number of edge-disjoint shortest paths |
|
22 /// between nodes \c s and \c t. |
|
23 |
2 |
24 |
3 // Use a DIMACS max flow file as input. |
25 // Use a DIMACS max flow file as input. |
4 // sub_graph_adaptor_demo < dimacs_max_flow_file |
26 // sub_graph_adaptor_demo < dimacs_max_flow_file |
5 // This program computes a maximum number of edge-disjoint shortest paths |
27 // Modified to eat lemon graph format! |
6 // between s and t. |
28 |
7 |
29 |
8 #include <iostream> |
30 #include <iostream> |
9 #include <fstream> |
31 #include <fstream> |
10 |
32 |
11 #include <lemon/smart_graph.h> |
33 #include <lemon/smart_graph.h> |
14 #include <lemon/graph_adaptor.h> |
36 #include <lemon/graph_adaptor.h> |
15 #include <lemon/dimacs.h> |
37 #include <lemon/dimacs.h> |
16 #include <lemon/preflow.h> |
38 #include <lemon/preflow.h> |
17 #include <tight_edge_filter_map.h> |
39 #include <tight_edge_filter_map.h> |
18 |
40 |
|
41 #include <lemon/graph_reader.h> |
19 |
42 |
20 |
|
21 //#include <lemon/graph_reader.h> |
|
22 //#include <lemon/graph_writer.h> |
|
23 |
43 |
24 using namespace lemon; |
44 using namespace lemon; |
25 |
45 |
26 using std::cout; |
46 using std::cout; |
27 using std::endl; |
47 using std::endl; |
28 |
48 |
29 int main(int argc, char *argv[]) |
49 int main(int argc, char *argv[]) |
30 { |
50 { |
31 if(argc<2) |
51 if(argc<2) |
32 { |
52 { |
33 std::cerr << "USAGE: sub_graph_adaptor_demo input_file.dim" << std::endl; |
53 std::cerr << "USAGE: sub_graph_adaptor_demo input_file.lgf" << std::endl; |
34 std::cerr << "The file 'input_file.dim' has to contain a max flow instance in DIMACS format (e.g. sub_graph_adaptor_demo.dim is such a file)." << std::endl; |
54 std::cerr << "The file 'input_file.lgf' has to contain a max flow " |
|
55 << "instance in \n LEMON format " |
|
56 << "(e.g. sub_gad_input.lgf is such a file)." |
|
57 << std::endl; |
35 return 0; |
58 return 0; |
36 } |
59 } |
37 |
60 |
38 |
61 |
39 //input stream to read the graph from |
62 //input stream to read the graph from |
49 |
72 |
50 Graph g; |
73 Graph g; |
51 Node s, t; |
74 Node s, t; |
52 LengthMap length(g); |
75 LengthMap length(g); |
53 |
76 |
54 readDimacs(is, g, length, s, t); |
77 //readDimacs(is, g, length, s, t); |
55 |
78 |
56 // GraphWriter<SmartGraph> writer(std::cout, g); |
|
57 // writer.writeEdgeMap("length", length); |
|
58 // writer.writeNode("source",s); |
|
59 // writer.writeNode("target",t); |
|
60 // writer.run(); |
|
61 |
79 |
62 // GraphReader<ListGraph> reader(is,g); |
80 GraphReader<SmartGraph> reader(is,g); |
63 // reader.readNode("source",s).readNode("target",t) |
81 reader.readNode("source",s).readNode("target",t) |
64 // .readEdgeMap("length",length).run(); |
82 .readEdgeMap("length",length).run(); |
65 |
83 |
66 cout << "edges with lengths (of form id, source--length->target): " << endl; |
84 cout << "edges with lengths (of form id, source--length->target): " << endl; |
67 for(EdgeIt e(g); e!=INVALID; ++e) |
85 for(EdgeIt e(g); e!=INVALID; ++e) |
68 cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--" |
86 cout << " " << g.id(e) << ", " << g.id(g.source(e)) << "--" |
69 << length[e] << "->" << g.id(g.target(e)) << endl; |
87 << length[e] << "->" << g.id(g.target(e)) << endl; |