Ticket #4292: pl.2.cpp

File pl.2.cpp, 12.3 KB (added by Mike Douglass, 12 years ago)

pl.cpp with comments

Line 
1
2// Distributed under the Boost Software License, Version 1.0.
3// (See accompanying file LICENSE_1_0.txt or copy at
4// http://www.boost.org/LICENSE_1_0.txt)
5
6
7#include "Declarations.cpp"
8#include "Utilities.cpp"
9
10
11 // Each edge e of the graph contains a set of pairs of type pair< Color, int >, it's ePColors.
12 // Let e's ePColors contain for example (Red, 5). This is intended to indicate that e is
13 // potentially the 5_th edge of a free alternating chain where e is colored Red.
14 // We find a succession of free alternating chains.
15
16 template < typename Graph >
17 bool examine_edges(Graph & g)
18 { // Mark light conflicted edges first. One of these edges will be the first edge of any free alternating chain we find.
19
20 typename graph_traits<Graph>::edge_iterator ei, ei_end;
21 bool Colored = false, Conflicted = false;
22
23 Color_List::iterator color_iter;
24
25 // Determine valid edge colors.
26 get_eValidColors(g);
27
28 // For each color *color_iter in the list (Red, Green, Blue, Yellow)
29 for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
30 // For each edge *ei
31 for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
32 // If *ei is light and *ei is conflicted (ie. has the same color vertices at both ends)
33 if( g[*ei].eWeight == "Heavy" ) continue;
34 if( g[source(*ei,g)].vColor != g[target(*ei,g)].vColor ) continue;
35 Conflicted = true;
36 // and *color_iter is not the same color as the vertex on the end of the edge,
37 if( *color_iter == g[target(*ei,g)].vColor ) continue;
38 // and *color_iter is a valid color for *ei
39 if( g[*ei].eValidColors.find(*color_iter) == g[*ei].eValidColors.end() ) continue;
40 // then insert the pair (*color_iter, 1) in the ePColors of *out_iter.
41 g[*ei].ePColors.insert(make_pair(*color_iter,1));
42
43 // Check to see if this yields a free alternating chain of length 1.
44 // If so apply the chain to the graph
45 // (ie. make heavy (darken) this edge and change the vertex color at the end of the chain in accordance with the
46 // coloring found in the function "has_chainA", so that this edge is no longer conflicted).
47 // Then return, and look for the next free alternating chain.
48 if( has_chainA(*ei, *color_iter, g) ) return true;
49 Colored = true;
50 }
51 }
52
53
54 if( !Conflicted ) { result = 0; return false; } // If !Conflicted the graph is properly four colored, algorithm succeeds, we are done.
55 if( !Colored ) { result = 1; return false; } // If !Colored, graph is conflicted but not colorable (no new pair can be put in any edge's ePColors) - algorithm fails.
56
57 // If no free alternating chain of length one has been found we must look for a free alternating chain of lenght two ( then 3,4, ... ) by going to function dotted.
58 return dotted(g);
59
60 }
61
62 template < typename Graph >
63 bool dotted(Graph & g)
64 { // Mark Heavy edges.
65 // We look for a free alternating chain of length two (then three, four ...).
66
67 typename graph_traits<Graph>::edge_iterator ei, ei_end;
68 typename graph_traits<Graph>::out_edge_iterator out_iter, out_end;
69
70 Color_List::iterator color_iter, colorr_iter;
71
72 bool inserted;
73 int i = 0;
74
75 do {
76 inserted = false;
77 i++; // i will become 1 for the first iteration through the loop, when we are looking for a free alternating chain of length 2.
78 // We assume that i is 1 in the comments that follow.
79 // For each color *color_iter in the list (Red, Green, Blue, Yellow)
80 for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
81 // For each edge *ei
82 for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
83 // Let Pin_color_set be *ei's ePColors.
84 ColorPSet & Pin_color_set = g[*ei].ePColors;
85 // If we are trying to find a free alternating chain of length two, then we need to find a pair, (*color_iter, 1), in Pin_color_set ( notice the 1).
86 // If Pin_color_set does not contain such a pair continue.
87 if( Pin_color_set.find(make_pair(*color_iter,i)) == Pin_color_set.end() ) continue;
88 // Now considering all possible colors
89 for(colorr_iter=ColorList.begin(); colorr_iter != ColorList.end(); ++colorr_iter) {
90 // look at all edges outgoing from the target of *ei.
91 for (tie(out_iter, out_end) = out_edges(target(*ei,g), g); out_iter != out_end; ++out_iter) {
92 // If the edges *ei and *out_iter satisfy certain conditions,
93 if( target(*out_iter,g) == source(*ei,g) ) continue;
94 if( g[*out_iter].eWeight == "Light" ) continue;
95 if( *color_iter != g[target(*out_iter,g)].vColor ) continue;
96 ColorPSet & Pout_color_set = g[*out_iter].ePColors;
97 ColorSet & eValid_out_color_set = g[*out_iter].eValidColors;
98 if( *colorr_iter == g[target(*out_iter,g)].vColor ) continue;
99 if( eValid_out_color_set.find(*colorr_iter) == eValid_out_color_set.end() ) continue;
100 if( PColorsFind(*out_iter, *colorr_iter, g) ) continue;
101
102 // then insert the pair (*colorr_iter, 2) in the ePColors of *out_iter.
103 Pout_color_set.insert(make_pair(*colorr_iter,i+1));
104 inserted = true; // Keep track that a new pair was inserted.
105
106 // Check to see if this yields a free alternating chain.
107 // If so apply the chain to the graph, return true, and look for the next free alternating chain.
108 if( has_chain(i+1, *ei, *out_iter, *colorr_iter, g) ) return true;
109
110 }
111 }
112 }
113 }
114
115 // If inserted = true and no free alternating chain of length two (three, four ...) has been found we must look for a
116 // free alternating chain of length three (four, five ...) by going through this while loop again.
117 } while ( inserted );
118
119 // If we get here then the function "has_chain(i+1, *ei, *out_iter, *colorr_iter, g)" above has not returned true, and "inserted" has not been set to true because no new
120 // pair can be put in any edge's ePColors. The algorithm has failed to find a four coloring. Set result to 2 (Failure) and return false (end program).
121
122 result = 2;
123
124 return false;
125
126 }
127
128 template < typename Edge, typename Graph >
129 bool has_chainA(Edge out, Color color, Graph & g)
130 { // Determine if a free alternating chain of length 1 has been found.
131
132 typename graph_traits<Graph>::out_edge_iterator out_iter, out_end;
133
134 for(tie(out_iter, out_end) = out_edges(target(out,g),g); out_iter != out_end; ++out_iter) {
135 if( target(*out_iter,g) == source(out,g) ) continue;
136 if( g[*out_iter].eWeight == "Heavy" && g[target(*out_iter,g)].vColor == color ) return false;
137 }
138
139 g[out].eArrow = aColour_map[color];
140 // If so apply the chain to the graph
141 if( do_chain(out, g) ) return true;
142
143 return false;
144
145 }
146
147
148 template < typename Edge, typename Graph >
149 bool has_chain(int len, Edge ei, Edge out, Color color, Graph & g)
150 { // Determine if a free alternating chain of length greater than 1 has been found.
151 // (This is basically a setup function for the recursive function get_chain(int len, Edge out, Graph & g).)
152
153 typename graph_traits<Graph>::out_edge_iterator out_iter, out_end;
154
155 for(tie(out_iter, out_end) = out_edges(target(out,g),g); out_iter != out_end; ++out_iter) {
156 if( target(*out_iter,g) == source(out,g) ) continue;
157 if( g[*out_iter].eWeight == "Heavy" && color == g[target(*out_iter,g)].vColor ) return false;
158 }
159
160 g[out].eArrow = aColour_map[color];
161 g[target(out,g)].vNewColor = color;
162 if( !get_chain(len, out, g) ) return false;
163 // If so apply the chain to the graph.
164 do_chain(out, g);
165
166 return true;
167
168 }
169
170
171 template < typename Edge, typename Graph >
172 bool get_chain(int len, Edge out, Graph & g)
173 { // Recursively call this function to get the free alternating chain.
174
175 typename graph_traits<Graph>::in_edge_iterator in_iter, in_end;
176 Color_List::iterator color_iter;
177
178
179 if( g[out].eWeight == "Light" ) {
180 g[out].ePredecessor = out;
181 return true;
182 }
183
184
185 for (tie(in_iter, in_end) = in_edges(source(out,g), g); in_iter != in_end; ++in_iter) {
186 if( source(*in_iter,g) == target(out,g) ) continue;
187 if( g[*in_iter].eWeight != "Heavy" && g[source(*in_iter,g)].vColor != g[target(*in_iter,g)].vColor ) continue;
188 ColorPSet & Pcolor_set = g[*in_iter].ePColors;
189 for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
190 if( Pcolor_set.find(make_pair(*color_iter,len-1)) == Pcolor_set.end() ) continue;
191 if( *color_iter == g[source(out,g)].vColor ) continue;
192 if( *color_iter != g[target(out,g)].vColor ) continue;
193 if( !valid(*in_iter, *color_iter, g) ) continue;
194
195 g[out].ePredecessor = *in_iter;
196 g[*in_iter].eArrow = aColour_map[*color_iter];
197 g[target(*in_iter,g)].vNewColor = *color_iter;
198 if( get_chain(len-1, *in_iter, g) ) return true; // recursive call
199 }
200 }
201
202 g[out].ePredecessor = out;
203 g[out].eArrow = "nil";
204 g[target(out,g)].vNewColor = "nil";
205
206 return false;
207
208 }
209
210 template < typename Edge, typename Graph >
211 bool valid(Edge in, Color color, Graph & g)
212 { // Determine if Edge "in" can have it's Color correctly set to "color" in the formation of a free alternating chain .
213 // (This is NOT the same as eValidColors.)
214
215 typename graph_traits<Graph>::in_edge_iterator in_iter, in_end;
216
217 // in's source vertex must not yet (in the current attempt to get a free alternating chain) have been set to a color, so is still "nil".
218 if( g[source(in,g)].vNewColor != "nil" ) { return false; }
219
220 // No other heavy edge pointing to in's target vertex can have had it's source vertex colored "color".
221 for (tie(in_iter, in_end) = in_edges(target(in,g), g); in_iter != in_end; ++in_iter) {
222 if( source(*in_iter,g) == source(in,g) ) continue;
223 if( g[*in_iter].eWeight == "Light" ) continue;
224 if( color == g[source(*in_iter,g)].vNewColor ) { return false; }
225 }
226
227
228 return true;
229
230 }
231
232
233 template < typename Edge, typename Graph >
234 bool do_chain(Edge in, Graph & g)
235 { // Apply the chain to the graph.
236 // Make the first edge heavy (dark), recolor al vertices along the chain except the first in accordance with the coloring found in the function "has_chain", or "has_chainA".
237 // The resulting graph will have one more heavy edge and be properly colored wrt. it's heavy edges.
238
239 g[target(in,g)].vColor = inverse_aColour_map[g[in].eArrow];
240
241 if( g[in].eWeight == "Light" ) {
242 make_heavy(in, g);
243 initialize_arrows(g);
244 initialize_ePColors(g);
245 initialize_vNewColors(g);
246 numChains++;
247 return true;
248 }
249 else do_chain(g[in].ePredecessor, g);
250
251 return false;
252 }
253
254
255 template < typename Graph >
256 void fill_eValidColors(Graph & g)
257 { // Insert all colors in each edges set of valid colors - eValidColors. Then erase invalid colors in get_eValidColors(Graph & g) below.
258
259 typename graph_traits<Graph>::edge_iterator ei, ei_end;
260
261 for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
262 ColorSet & csr = g[*ei].eValidColors;
263 for (Color_List::iterator color_iter = ColorList.begin(); color_iter != ColorList.end(); ++color_iter)
264 csr.insert(*color_iter);
265 }
266
267 }
268
269
270
271
272 template < typename Graph >
273 void get_eValidColors(Graph & g)
274 { // Erase invalid colors from each edges set of valid colors - eValidColors.
275
276 typename graph_traits<Graph>::vertex_iterator vi, vi_end;
277 typename graph_traits<Graph>::in_edge_iterator in_iter, in_end, in1_iter, in1_end, in2_iter, in2_end;
278
279 fill_eValidColors(g);
280
281 for (tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
282 for (tie(in_iter, in_end) = in_edges(*vi, g); in_iter != in_end; ++in_iter) {
283 // Consider the set of valid colors of in_iter, e_valid_colors.
284 ColorSet & e_valid_colors = g[*in_iter].eValidColors;
285 for (tie(in1_iter, in1_end) = in_edges(*vi, g); in1_iter != in1_end; ++in1_iter) {
286 if( in1_iter == in_iter ) continue;
287 if( g[*in1_iter].eWeight == "Light" ) continue;
288 for (tie(in2_iter, in2_end) = in_edges(*vi, g); in2_iter != in2_end; ++in2_iter) {
289 if( in2_iter == in_iter ) continue;
290 if( g[*in2_iter].eWeight == "Light" ) continue;
291 if( in2_iter == in1_iter ) continue;
292 // If we arive at this point we have found two heavy edges incident with *vi
293 // other than in_iter, namely *in1_iter and *in2_iter.
294 // If *in1_iter and *in2_iter have the same color at their other vertex ( not *vi )
295 // then that color must be erased from the set of valid colors of in_iter ( e_valid_colors ).
296 if( g[source(*in2_iter,g)].vColor == g[source(*in1_iter,g)].vColor )
297 e_valid_colors.erase(g[source(*in1_iter,g)].vColor);
298 }
299 }
300 }
301 }
302
303 }
304
305
306
307
308 graph_t g;
309
310 int main()
311 {
312
313 read_graphml(cin, g, dpp);
314
315 while( examine_edges(g) );
316
317 return result; // Failure or Success
318
319 }
320
321