24 |
25 |
25 template <typename Graph> |
26 template <typename Graph> |
26 void printGraph(const Graph& g) { |
27 void printGraph(const Graph& g) { |
27 cout << " nodes:" << endl; |
28 cout << " nodes:" << endl; |
28 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { |
29 for (typename Graph::NodeIt n(g); n!=INVALID; ++n) { |
29 cout << " " << g.id(n) << endl; |
30 cout << " " << g.id(n) << ": out edges:" << endl; |
|
31 for (typename Graph::OutEdgeIt e(g, n); e!=INVALID; ++e) |
|
32 cout << " " << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl; |
30 } |
33 } |
31 cout << " edges:" << endl; |
34 cout << " edges:" << endl; |
32 for (typename Graph::EdgeIt n(g); n!=INVALID; ++n) { |
35 for (typename Graph::EdgeIt e(g); e!=INVALID; ++e) { |
33 cout << " " << g.id(n) << ": " |
36 cout << " " << g.id(e) << ": " |
34 << g.id(g.source(n)) << "->" << g.id(g.target(n)) << endl; |
37 << g.id(g.source(e)) << "->" << g.id(g.target(e)) << endl; |
35 } |
38 } |
36 } |
39 } |
37 |
40 |
38 int main() { |
41 int main() { |
39 { |
42 { |
40 cout << "FIRST TEST" << endl; |
43 cout << "FIRST TEST" << endl; |
41 typedef SmartGraph Graph1; |
44 //typedef SmartGraph Graph1; |
|
45 typedef ListGraph Graph1; |
42 typedef ListGraph Graph2; |
46 typedef ListGraph Graph2; |
|
47 typedef SmartGraph Graph3; |
43 |
48 |
44 { |
49 // { |
45 checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >(); |
50 // checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph2> >(); |
46 MergeEdgeGraphWrapper<Graph1, Graph2>::printNode(); |
51 // MergeEdgeGraphWrapper<Graph1, Graph2>::printNode(); |
47 MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge(); |
52 // MergeEdgeGraphWrapper<Graph1, Graph2>::printEdge(); |
48 checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >(); |
53 // checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph1> >(); |
49 MergeEdgeGraphWrapper<Graph1, Graph1>::printNode(); |
54 // MergeEdgeGraphWrapper<Graph1, Graph1>::printNode(); |
50 MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge(); |
55 // MergeEdgeGraphWrapper<Graph1, Graph1>::printEdge(); |
51 typedef ResGraphWrapper<Graph1, int, |
56 // typedef ResGraphWrapper<Graph1, int, |
52 ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4; |
57 // ConstMap<Graph1, int>, ConstMap<Graph1, int> > Graph4; |
53 checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >(); |
58 // checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph1, Graph4> >(); |
54 MergeEdgeGraphWrapper<Graph1, Graph4>::printNode(); |
59 // MergeEdgeGraphWrapper<Graph1, Graph4>::printNode(); |
55 MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge(); |
60 // MergeEdgeGraphWrapper<Graph1, Graph4>::printEdge(); |
56 checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >(); |
61 // checkConcept<StaticGraph, MergeEdgeGraphWrapper<Graph4, Graph1> >(); |
57 MergeEdgeGraphWrapper<Graph4, Graph1>::printNode(); |
62 // MergeEdgeGraphWrapper<Graph4, Graph1>::printNode(); |
58 MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge(); |
63 // MergeEdgeGraphWrapper<Graph4, Graph1>::printEdge(); |
59 } |
64 // } |
60 |
65 |
61 Graph1 g1; |
66 Graph1 g1; |
62 Graph2 g2; |
67 Graph2 g2; |
63 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW; |
68 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW; |
64 GW gw(g1, g2); |
69 GW gw(g1, g2); |
|
70 Graph1::Node s1, t1; |
|
71 Graph2::Node s2, t2; |
|
72 Graph1::EdgeMap<int> cap1(g1); |
|
73 Graph2::EdgeMap<int> cap2(g2); |
65 |
74 |
66 std::ifstream f1("graph1.dim"); |
75 std::ifstream f1("graph1.dim"); |
67 std::ifstream f2("graph2.dim"); |
76 std::ifstream f2("graph2.dim"); |
68 readDimacs(f1, g1); |
77 readDimacs(f1, g1); |
69 readDimacs(f2, g2); |
78 readDimacs(f2, g2); |
|
79 |
|
80 // GW::NodeMap<int> ize(gw, 8); |
|
81 // for (GW::NodeIt n(gw); n!=INVALID; ++n) ize.set(n, 9); |
|
82 // GW::EdgeMap<int> mize(gw, 8); |
|
83 // for (GW::EdgeIt n(gw); n!=INVALID; ++n) mize.set(n, 7); |
|
84 |
|
85 // std::ifstream f1("flow-1.dim"); |
|
86 // std::ifstream f2("flow2.dim"); |
|
87 // readDimacs(f1, g1, cap1, s1, t1); |
|
88 // readDimacs(f2, g2, cap2, s2, t2); |
70 |
89 |
71 cout << "1st graph" << endl; |
90 // GW::EdgeMap<int> cap(gw); |
72 printGraph(g1); |
91 // for (GW::EdgeIt e(gw); e!=INVALID; ++e) { |
73 |
92 // if (gw.forward(e)) cap.set(e, cap1[e]); |
74 cout << "2nd graph" << endl; |
93 // if (gw.backward(e)) cap.set(e, cap2[e]); |
75 printGraph(g2); |
94 // } |
76 |
95 |
77 cout << "merged graph" << endl; |
96 // { |
78 printGraph(gw); |
97 // GW::EdgeMap<int> flow(gw, 0); |
79 |
98 // Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false), |
|
99 // GW::Node(t1, INVALID, false), cap, flow); |
|
100 // preflow.run(); |
|
101 // std::cout << "s1->t1: " << preflow.flowValue() << std::endl; |
|
102 // } |
|
103 // { |
|
104 // GW::EdgeMap<int> flow(gw, 0); |
|
105 // Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true), |
|
106 // GW::Node(INVALID, t2, true), cap, flow); |
|
107 // preflow.run(); |
|
108 // std::cout << "s2->t2: " << preflow.flowValue() << std::endl; |
|
109 // } |
|
110 // { |
|
111 // GW::EdgeMap<int> flow(gw, 0); |
|
112 // Preflow<GW, int> preflow(gw, GW::Node(s1, INVALID, false), |
|
113 // GW::Node(INVALID, t2, true), cap, flow); |
|
114 // preflow.run(); |
|
115 // std::cout << "s1->t2: " << preflow.flowValue() << std::endl; |
|
116 // } |
|
117 // { |
|
118 // GW::EdgeMap<int> flow(gw, 0); |
|
119 // Preflow<GW, int> preflow(gw, GW::Node(INVALID, s2, true), |
|
120 // GW::Node(s1, INVALID, false), cap, flow); |
|
121 // preflow.run(); |
|
122 // std::cout << "s2->t1: " << preflow.flowValue() << std::endl; |
|
123 // } |
|
124 cout << "1st graph" << endl; |
|
125 printGraph(g1); |
|
126 |
|
127 cout << "2nd graph" << endl; |
|
128 printGraph(g2); |
|
129 |
|
130 cout << "merged graph" << endl; |
|
131 printGraph(gw); |
|
132 |
|
133 // for (GW::NodeIt n(gw); n!=INVALID; ++n) |
|
134 // std::cout << ize[n] << std::endl; |
|
135 // for (GW::EdgeIt n(gw); n!=INVALID; ++n) |
|
136 // std::cout << mize[n] << std::endl; |
|
137 |
|
138 typedef NewEdgeSetGraphWrapper2<GW, Graph3> GWW; |
|
139 // { |
|
140 // checkConcept<StaticGraph, GWW>(); |
|
141 // } |
|
142 |
|
143 GWW gww(gw); |
|
144 |
|
145 cout << "new edges graph" << endl; |
|
146 printGraph(gww); |
|
147 |
|
148 GWW::NodeIt n(gww); |
|
149 GWW::Node n1=n; |
|
150 ++n; |
|
151 GWW::Node n2=n; |
|
152 gww.addEdge(n1, n2); |
|
153 // gww.addNode(); |
|
154 // gww.addNode(); |
|
155 |
|
156 cout << "new edges graph" << endl; |
|
157 printGraph(gww); |
|
158 |
|
159 typedef AugmentingGraphWrapper<GW, GWW> GWWW; |
|
160 // { |
|
161 // checkConcept<StaticGraph, GWWW>(); |
|
162 // } |
|
163 GWWW gwww(gw, gww); |
|
164 |
|
165 cout << "fully merged graph" << endl; |
|
166 printGraph(gwww); |
80 } |
167 } |
81 |
168 |
82 |
169 |
83 { |
170 { |
84 cout << "SECOND TEST" << endl; |
171 cout << "SECOND TEST" << endl; |
85 typedef SmartGraph Graph1; |
172 typedef SmartGraph Graph1; |
86 { |
173 // { |
87 checkConcept<StaticGraph, Graph1>(); |
174 // checkConcept<StaticGraph, Graph1>(); |
88 } |
175 // } |
89 |
176 |
90 Graph1 g1; |
177 Graph1 g1; |
91 |
178 |
92 FullGraph pre_g2(2); |
179 FullGraph pre_g2(2); |
93 ConstMap<FullGraph::Edge, bool> const_false_map(false); |
180 ConstMap<FullGraph::Edge, bool> const_false_map(false); |
94 typedef EdgeSubGraphWrapper<FullGraph, ConstMap<FullGraph::Edge, bool> > |
181 typedef EdgeSubGraphWrapper<FullGraph, ConstMap<FullGraph::Edge, bool> > |
95 Graph2; |
182 Graph2; |
96 { |
183 // { |
97 checkConcept<StaticGraph, Graph2>(); |
184 // checkConcept<StaticGraph, Graph2>(); |
98 } |
185 // } |
99 |
186 |
100 Graph2 g2(pre_g2, const_false_map); |
187 Graph2 g2(pre_g2, const_false_map); |
101 |
188 |
102 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW; |
189 typedef MergeEdgeGraphWrapper<Graph1, Graph2> GW; |
103 { |
190 // { |
104 checkConcept<StaticGraph, GW>(); |
191 // checkConcept<StaticGraph, GW>(); |
105 } |
192 // } |
106 GW gw(g1, g2); |
193 GW gw(g1, g2); |
107 GW::Node sw; |
194 GW::Node sw; |
108 GW::Node tw; |
195 GW::Node tw; |
109 { |
196 { |
110 Graph2::NodeIt k(g2); |
197 Graph2::NodeIt k(g2); |