equal
deleted
inserted
replaced
181 PlanarityChecking(const UGraph& ugraph) : _ugraph(ugraph) {} |
181 PlanarityChecking(const UGraph& ugraph) : _ugraph(ugraph) {} |
182 |
182 |
183 /// \brief Runs the algorithm. |
183 /// \brief Runs the algorithm. |
184 /// |
184 /// |
185 /// Runs the algorithm. |
185 /// Runs the algorithm. |
186 /// \param kuratowski If the parameter is false, then the |
|
187 /// algorithm does not calculate the isolate Kuratowski |
|
188 /// subdivisions. |
|
189 /// \return %True when the graph is planar. |
186 /// \return %True when the graph is planar. |
190 bool run(bool kuratowski = true) { |
187 bool run() { |
191 typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor; |
188 typedef _planarity_bits::PlanarityVisitor<UGraph> Visitor; |
192 |
189 |
193 PredMap pred_map(_ugraph, INVALID); |
190 PredMap pred_map(_ugraph, INVALID); |
194 TreeMap tree_map(_ugraph, false); |
191 TreeMap tree_map(_ugraph, false); |
195 |
192 |
220 Node source = node; |
217 Node source = node; |
221 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
218 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
222 Node target = _ugraph.target(e); |
219 Node target = _ugraph.target(e); |
223 |
220 |
224 if (order_map[source] < order_map[target] && tree_map[e]) { |
221 if (order_map[source] < order_map[target] && tree_map[e]) { |
225 initFace(target, node_data, pred_map, order_map, order_list); |
222 initFace(target, node_data, order_map, order_list); |
226 } |
223 } |
227 } |
224 } |
228 |
225 |
229 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
226 for (OutEdgeIt e(_ugraph, node); e != INVALID; ++e) { |
230 Node target = _ugraph.target(e); |
227 Node target = _ugraph.target(e); |
490 } |
487 } |
491 } |
488 } |
492 } |
489 } |
493 |
490 |
494 void initFace(const Node& node, NodeData& node_data, |
491 void initFace(const Node& node, NodeData& node_data, |
495 const PredMap& pred_map, const OrderMap& order_map, |
492 const OrderMap& order_map, const OrderList& order_list) { |
496 const OrderList& order_list) { |
|
497 int n = order_map[node]; |
493 int n = order_map[node]; |
498 int rn = n + order_list.size(); |
494 int rn = n + order_list.size(); |
499 |
495 |
500 node_data[n].next = node_data[n].prev = rn; |
496 node_data[n].next = node_data[n].prev = rn; |
501 node_data[rn].next = node_data[rn].prev = n; |
497 node_data[rn].next = node_data[rn].prev = n; |