Ticket #4292: pl.cpp

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

principal file

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 template < typename Graph >
12 bool examine_edges(Graph & g)
13 {
14
15 typename graph_traits<Graph>::edge_iterator ei, ei_end;
16 bool Colored = false, Conflicted = false;
17
18 Color_List::iterator color_iter;
19
20 get_eValidColors(g);
21
22 for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
23 for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
24 if( g[*ei].eWeight == "Heavy" ) continue;
25 if( g[source(*ei,g)].vColor != g[target(*ei,g)].vColor ) continue;
26 Conflicted = true;
27 if( *color_iter == g[target(*ei,g)].vColor ) continue;
28 if( g[*ei].eValidColors.find(*color_iter) == g[*ei].eValidColors.end() ) continue;
29 g[*ei].ePColors.insert(make_pair(*color_iter,1));
30 if( has_chainA(*ei, *color_iter, g) ) return true;
31 Colored = true;
32 }
33 }
34
35
36 if( !Conflicted ) { result = 0; return false; }
37 if( !Colored ) { result = 1; return false; }
38
39 return dotted(g);
40
41 }
42
43 template < typename Graph >
44 bool dotted(Graph & g)
45 {
46
47 typename graph_traits<Graph>::edge_iterator ei, ei_end;
48 typename graph_traits<Graph>::out_edge_iterator out_iter, out_end;
49
50 Color_List::iterator color_iter, colorr_iter;
51
52 bool inserted;
53 int i = 0;
54
55 do {
56 inserted = false;
57 i++;
58 for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
59 for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
60 ColorPSet & Pin_color_set = g[*ei].ePColors;
61 if( Pin_color_set.find(make_pair(*color_iter,i)) == Pin_color_set.end() ) continue;
62 for(colorr_iter=ColorList.begin(); colorr_iter != ColorList.end(); ++colorr_iter) {
63 for (tie(out_iter, out_end) = out_edges(target(*ei,g), g); out_iter != out_end; ++out_iter) {
64 if( target(*out_iter,g) == source(*ei,g) ) continue;
65 if( g[*out_iter].eWeight == "Light" ) continue;
66 if( *color_iter != g[target(*out_iter,g)].vColor ) continue;
67 ColorPSet & Pout_color_set = g[*out_iter].ePColors;
68 ColorSet & eValid_out_color_set = g[*out_iter].eValidColors;
69 if( *colorr_iter == g[target(*out_iter,g)].vColor ) continue;
70 if( eValid_out_color_set.find(*colorr_iter) == eValid_out_color_set.end() ) continue;
71 if( PColorsFind(*out_iter, *colorr_iter, g) ) continue;
72
73 Pout_color_set.insert(make_pair(*colorr_iter,i+1));
74 inserted = true;
75 if( has_chain(i+1, *ei, *out_iter, *colorr_iter, g) ) return true;
76
77 }
78 }
79 }
80 }
81
82 } while ( inserted );
83
84 result = 2;
85
86 return false;
87
88 }
89
90 template < typename Edge, typename Graph >
91 bool has_chainA(Edge out, Color color, Graph & g)
92 {
93
94 typename graph_traits<Graph>::out_edge_iterator out_iter, out_end;
95
96 for(tie(out_iter, out_end) = out_edges(target(out,g),g); out_iter != out_end; ++out_iter) {
97 if( target(*out_iter,g) == source(out,g) ) continue;
98 if( g[*out_iter].eWeight == "Heavy" && g[target(*out_iter,g)].vColor == color ) return false;
99 }
100
101 g[out].eArrow = aColour_map[color];
102 if( do_chain(out, g) ) return true;
103
104 return false;
105
106 }
107
108
109 template < typename Edge, typename Graph >
110 bool has_chain(int len, Edge ei, Edge out, Color color, Graph & g)
111 {
112
113 typename graph_traits<Graph>::out_edge_iterator out_iter, out_end;
114
115 for(tie(out_iter, out_end) = out_edges(target(out,g),g); out_iter != out_end; ++out_iter) {
116 if( target(*out_iter,g) == source(out,g) ) continue;
117 if( g[*out_iter].eWeight == "Heavy" && color == g[target(*out_iter,g)].vColor ) return false;
118 }
119
120 g[out].eArrow = aColour_map[color];
121 g[target(out,g)].vNewColor = color;
122 if( !get_chain(len, out, g) ) return false;
123 do_chain(out, g);
124
125 return true;
126
127 }
128
129
130 template < typename Edge, typename Graph >
131 bool get_chain(int len, Edge out, Graph & g)
132 {
133
134 typename graph_traits<Graph>::in_edge_iterator in_iter, in_end;
135 Color_List::iterator color_iter;
136
137
138 if( g[out].eWeight == "Light" ) {
139 g[out].ePredecessor = out;
140 return true;
141 }
142
143
144 for (tie(in_iter, in_end) = in_edges(source(out,g), g); in_iter != in_end; ++in_iter) {
145 if( source(*in_iter,g) == target(out,g) ) continue;
146 if( g[*in_iter].eWeight != "Heavy" && g[source(*in_iter,g)].vColor != g[target(*in_iter,g)].vColor ) continue;
147 ColorPSet & Pcolor_set = g[*in_iter].ePColors;
148 for(color_iter=ColorList.begin(); color_iter != ColorList.end(); ++color_iter) {
149 if( Pcolor_set.find(make_pair(*color_iter,len-1)) == Pcolor_set.end() ) continue;
150 if( *color_iter == g[source(out,g)].vColor ) continue;
151 if( *color_iter != g[target(out,g)].vColor ) continue;
152 if( !valid(*in_iter, *color_iter, g) ) continue;
153
154 g[out].ePredecessor = *in_iter;
155 g[*in_iter].eArrow = aColour_map[*color_iter];
156 g[target(*in_iter,g)].vNewColor = *color_iter;
157 if( get_chain(len-1, *in_iter, g) ) return true;
158 }
159 }
160
161 g[out].ePredecessor = out;
162 g[out].eArrow = "nil";
163 g[target(out,g)].vNewColor = "nil";
164
165 return false;
166
167 }
168
169 template < typename Edge, typename Graph >
170 bool valid(Edge in, Color color, Graph & g)
171 {
172
173 typename graph_traits<Graph>::in_edge_iterator in_iter, in_end;
174
175 if( g[source(in,g)].vNewColor != "nil" ) { return false; }
176
177 for (tie(in_iter, in_end) = in_edges(target(in,g), g); in_iter != in_end; ++in_iter) {
178 if( source(*in_iter,g) == source(in,g) ) continue;
179 if( g[*in_iter].eWeight == "Light" ) continue;
180 if( color == g[source(*in_iter,g)].vNewColor ) { return false; }
181 }
182
183
184 return true;
185
186 }
187
188
189 template < typename Edge, typename Graph >
190 bool do_chain(Edge in, Graph & g)
191 {
192
193 g[target(in,g)].vColor = inverse_aColour_map[g[in].eArrow];
194
195 if( g[in].eWeight == "Light" ) {
196 make_heavy(in, g);
197 initialize_arrows(g);
198 initialize_ePColors(g);
199 initialize_vNewColors(g);
200 numChains++;
201 return true;
202 }
203 else do_chain(g[in].ePredecessor, g);
204
205 return false;
206 }
207
208
209 graph_t g;
210
211 int main()
212 {
213
214 read_graphml(cin, g, dpp);
215
216 while( examine_edges(g) );
217
218 return result;
219
220 }
221
222