Changeset 798:58c330ad0b5c in lemon1.2 for lemon/planarity.h
 Timestamp:
 10/04/09 10:15:32 (10 years ago)
 Branch:
 default
 Phase:
 public
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/planarity.h
r797 r798 138 138 }; 139 139 140 template <typename Graph> 141 class PlanarityChecking { 142 private: 143 144 TEMPLATE_GRAPH_TYPEDEFS(Graph); 145 146 const Graph& _graph; 147 148 private: 149 150 typedef typename Graph::template NodeMap<Arc> PredMap; 151 152 typedef typename Graph::template EdgeMap<bool> TreeMap; 153 154 typedef typename Graph::template NodeMap<int> OrderMap; 155 typedef std::vector<Node> OrderList; 156 157 typedef typename Graph::template NodeMap<int> LowMap; 158 typedef typename Graph::template NodeMap<int> AncestorMap; 159 160 typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode; 161 typedef std::vector<NodeDataNode> NodeData; 162 163 typedef _planarity_bits::ChildListNode<Graph> ChildListNode; 164 typedef typename Graph::template NodeMap<ChildListNode> ChildLists; 165 166 typedef typename Graph::template NodeMap<std::list<int> > MergeRoots; 167 168 typedef typename Graph::template NodeMap<bool> EmbedArc; 169 170 public: 171 172 PlanarityChecking(const Graph& graph) : _graph(graph) {} 173 174 bool run() { 175 typedef _planarity_bits::PlanarityVisitor<Graph> Visitor; 176 177 PredMap pred_map(_graph, INVALID); 178 TreeMap tree_map(_graph, false); 179 180 OrderMap order_map(_graph, 1); 181 OrderList order_list; 182 183 AncestorMap ancestor_map(_graph, 1); 184 LowMap low_map(_graph, 1); 185 186 Visitor visitor(_graph, pred_map, tree_map, 187 order_map, order_list, ancestor_map, low_map); 188 DfsVisit<Graph, Visitor> visit(_graph, visitor); 189 visit.run(); 190 191 ChildLists child_lists(_graph); 192 createChildLists(tree_map, order_map, low_map, child_lists); 193 194 NodeData node_data(2 * order_list.size()); 195 196 EmbedArc embed_arc(_graph, false); 197 198 MergeRoots merge_roots(_graph); 199 200 for (int i = order_list.size()  1; i >= 0; i) { 201 202 Node node = order_list[i]; 203 204 Node source = node; 205 for (OutArcIt e(_graph, node); e != INVALID; ++e) { 206 Node target = _graph.target(e); 207 208 if (order_map[source] < order_map[target] && tree_map[e]) { 209 initFace(target, node_data, order_map, order_list); 210 } 211 } 212 213 for (OutArcIt e(_graph, node); e != INVALID; ++e) { 214 Node target = _graph.target(e); 215 216 if (order_map[source] < order_map[target] && !tree_map[e]) { 217 embed_arc[target] = true; 218 walkUp(target, source, i, pred_map, low_map, 219 order_map, order_list, node_data, merge_roots); 220 } 221 } 222 223 for (typename MergeRoots::Value::iterator it = 224 merge_roots[node].begin(); 225 it != merge_roots[node].end(); ++it) { 226 int rn = *it; 227 walkDown(rn, i, node_data, order_list, child_lists, 228 ancestor_map, low_map, embed_arc, merge_roots); 229 } 230 merge_roots[node].clear(); 231 232 for (OutArcIt e(_graph, node); e != INVALID; ++e) { 233 Node target = _graph.target(e); 234 235 if (order_map[source] < order_map[target] && !tree_map[e]) { 236 if (embed_arc[target]) { 237 return false; 238 } 239 } 240 } 241 } 242 243 return true; 244 } 245 246 private: 247 248 void createChildLists(const TreeMap& tree_map, const OrderMap& order_map, 249 const LowMap& low_map, ChildLists& child_lists) { 250 251 for (NodeIt n(_graph); n != INVALID; ++n) { 252 Node source = n; 253 254 std::vector<Node> targets; 255 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 256 Node target = _graph.target(e); 257 258 if (order_map[source] < order_map[target] && tree_map[e]) { 259 targets.push_back(target); 260 } 261 } 262 263 if (targets.size() == 0) { 264 child_lists[source].first = INVALID; 265 } else if (targets.size() == 1) { 266 child_lists[source].first = targets[0]; 267 child_lists[targets[0]].prev = INVALID; 268 child_lists[targets[0]].next = INVALID; 269 } else { 270 radixSort(targets.begin(), targets.end(), mapToFunctor(low_map)); 271 for (int i = 1; i < int(targets.size()); ++i) { 272 child_lists[targets[i]].prev = targets[i  1]; 273 child_lists[targets[i  1]].next = targets[i]; 274 } 275 child_lists[targets.back()].next = INVALID; 276 child_lists[targets.front()].prev = INVALID; 277 child_lists[source].first = targets.front(); 278 } 279 } 280 } 281 282 void walkUp(const Node& node, Node root, int rorder, 283 const PredMap& pred_map, const LowMap& low_map, 284 const OrderMap& order_map, const OrderList& order_list, 285 NodeData& node_data, MergeRoots& merge_roots) { 286 287 int na, nb; 288 bool da, db; 289 290 na = nb = order_map[node]; 291 da = true; db = false; 292 293 while (true) { 294 295 if (node_data[na].visited == rorder) break; 296 if (node_data[nb].visited == rorder) break; 297 298 node_data[na].visited = rorder; 299 node_data[nb].visited = rorder; 300 301 int rn = 1; 302 303 if (na >= int(order_list.size())) { 304 rn = na; 305 } else if (nb >= int(order_list.size())) { 306 rn = nb; 307 } 308 309 if (rn == 1) { 310 int nn; 311 312 nn = da ? node_data[na].prev : node_data[na].next; 313 da = node_data[nn].prev != na; 314 na = nn; 315 316 nn = db ? node_data[nb].prev : node_data[nb].next; 317 db = node_data[nn].prev != nb; 318 nb = nn; 319 320 } else { 321 322 Node rep = order_list[rn  order_list.size()]; 323 Node parent = _graph.source(pred_map[rep]); 324 325 if (low_map[rep] < rorder) { 326 merge_roots[parent].push_back(rn); 327 } else { 328 merge_roots[parent].push_front(rn); 329 } 330 331 if (parent != root) { 332 na = nb = order_map[parent]; 333 da = true; db = false; 334 } else { 335 break; 336 } 337 } 338 } 339 } 340 341 void walkDown(int rn, int rorder, NodeData& node_data, 342 OrderList& order_list, ChildLists& child_lists, 343 AncestorMap& ancestor_map, LowMap& low_map, 344 EmbedArc& embed_arc, MergeRoots& merge_roots) { 345 346 std::vector<std::pair<int, bool> > merge_stack; 347 348 for (int di = 0; di < 2; ++di) { 349 bool rd = di == 0; 350 int pn = rn; 351 int n = rd ? node_data[rn].next : node_data[rn].prev; 352 353 while (n != rn) { 354 355 Node node = order_list[n]; 356 357 if (embed_arc[node]) { 358 359 // Merging components on the critical path 360 while (!merge_stack.empty()) { 361 362 // Component root 363 int cn = merge_stack.back().first; 364 bool cd = merge_stack.back().second; 365 merge_stack.pop_back(); 366 367 // Parent of component 368 int dn = merge_stack.back().first; 369 bool dd = merge_stack.back().second; 370 merge_stack.pop_back(); 371 372 Node parent = order_list[dn]; 373 374 // Erasing from merge_roots 375 merge_roots[parent].pop_front(); 376 377 Node child = order_list[cn  order_list.size()]; 378 379 // Erasing from child_lists 380 if (child_lists[child].prev != INVALID) { 381 child_lists[child_lists[child].prev].next = 382 child_lists[child].next; 383 } else { 384 child_lists[parent].first = child_lists[child].next; 385 } 386 387 if (child_lists[child].next != INVALID) { 388 child_lists[child_lists[child].next].prev = 389 child_lists[child].prev; 390 } 391 392 // Merging external faces 393 { 394 int en = cn; 395 cn = cd ? node_data[cn].prev : node_data[cn].next; 396 cd = node_data[cn].next == en; 397 398 } 399 400 if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn; 401 if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn; 402 403 } 404 405 bool d = pn == node_data[n].prev; 406 407 if (node_data[n].prev == node_data[n].next && 408 node_data[n].inverted) { 409 d = !d; 410 } 411 412 // Embedding arc into external face 413 if (rd) node_data[rn].next = n; else node_data[rn].prev = n; 414 if (d) node_data[n].prev = rn; else node_data[n].next = rn; 415 pn = rn; 416 417 embed_arc[order_list[n]] = false; 418 } 419 420 if (!merge_roots[node].empty()) { 421 422 bool d = pn == node_data[n].prev; 423 424 merge_stack.push_back(std::make_pair(n, d)); 425 426 int rn = merge_roots[node].front(); 427 428 int xn = node_data[rn].next; 429 Node xnode = order_list[xn]; 430 431 int yn = node_data[rn].prev; 432 Node ynode = order_list[yn]; 433 434 bool rd; 435 if (!external(xnode, rorder, child_lists, 436 ancestor_map, low_map)) { 437 rd = true; 438 } else if (!external(ynode, rorder, child_lists, 439 ancestor_map, low_map)) { 440 rd = false; 441 } else if (pertinent(xnode, embed_arc, merge_roots)) { 442 rd = true; 443 } else { 444 rd = false; 445 } 446 447 merge_stack.push_back(std::make_pair(rn, rd)); 448 449 pn = rn; 450 n = rd ? xn : yn; 451 452 } else if (!external(node, rorder, child_lists, 453 ancestor_map, low_map)) { 454 int nn = (node_data[n].next != pn ? 455 node_data[n].next : node_data[n].prev); 456 457 bool nd = n == node_data[nn].prev; 458 459 if (nd) node_data[nn].prev = pn; 460 else node_data[nn].next = pn; 461 462 if (n == node_data[pn].prev) node_data[pn].prev = nn; 463 else node_data[pn].next = nn; 464 465 node_data[nn].inverted = 466 (node_data[nn].prev == node_data[nn].next && nd != rd); 467 468 n = nn; 469 } 470 else break; 471 472 } 473 474 if (!merge_stack.empty()  n == rn) { 475 break; 476 } 477 } 478 } 479 480 void initFace(const Node& node, NodeData& node_data, 481 const OrderMap& order_map, const OrderList& order_list) { 482 int n = order_map[node]; 483 int rn = n + order_list.size(); 484 485 node_data[n].next = node_data[n].prev = rn; 486 node_data[rn].next = node_data[rn].prev = n; 487 488 node_data[n].visited = order_list.size(); 489 node_data[rn].visited = order_list.size(); 490 491 } 492 493 bool external(const Node& node, int rorder, 494 ChildLists& child_lists, AncestorMap& ancestor_map, 495 LowMap& low_map) { 496 Node child = child_lists[node].first; 497 498 if (child != INVALID) { 499 if (low_map[child] < rorder) return true; 500 } 501 502 if (ancestor_map[node] < rorder) return true; 503 504 return false; 505 } 506 507 bool pertinent(const Node& node, const EmbedArc& embed_arc, 508 const MergeRoots& merge_roots) { 509 return !merge_roots[node].empty()  embed_arc[node]; 510 } 511 512 }; 513 140 514 } 141 515 … … 144 518 /// \brief Planarity checking of an undirected simple graph 145 519 /// 146 /// This class implements the BoyerMyrvold algorithm for planarity147 /// checking of an undirected graph. This classis a simplified520 /// This function implements the BoyerMyrvold algorithm for 521 /// planarity checking of an undirected graph. It is a simplified 148 522 /// version of the PlanarEmbedding algorithm class because neither 149 523 /// the embedding nor the kuratowski subdivisons are not computed. 150 template <typename Graph> 151 class PlanarityChecking { 152 private: 153 154 TEMPLATE_GRAPH_TYPEDEFS(Graph); 155 156 const Graph& _graph; 157 158 private: 159 160 typedef typename Graph::template NodeMap<Arc> PredMap; 161 162 typedef typename Graph::template EdgeMap<bool> TreeMap; 163 164 typedef typename Graph::template NodeMap<int> OrderMap; 165 typedef std::vector<Node> OrderList; 166 167 typedef typename Graph::template NodeMap<int> LowMap; 168 typedef typename Graph::template NodeMap<int> AncestorMap; 169 170 typedef _planarity_bits::NodeDataNode<Graph> NodeDataNode; 171 typedef std::vector<NodeDataNode> NodeData; 172 173 typedef _planarity_bits::ChildListNode<Graph> ChildListNode; 174 typedef typename Graph::template NodeMap<ChildListNode> ChildLists; 175 176 typedef typename Graph::template NodeMap<std::list<int> > MergeRoots; 177 178 typedef typename Graph::template NodeMap<bool> EmbedArc; 179 180 public: 181 182 /// \brief Constructor 183 /// 184 /// \note The graph should be simple, i.e. parallel and loop arc 185 /// free. 186 PlanarityChecking(const Graph& graph) : _graph(graph) {} 187 188 /// \brief Runs the algorithm. 189 /// 190 /// Runs the algorithm. 191 /// \return %True when the graph is planar. 192 bool run() { 193 typedef _planarity_bits::PlanarityVisitor<Graph> Visitor; 194 195 PredMap pred_map(_graph, INVALID); 196 TreeMap tree_map(_graph, false); 197 198 OrderMap order_map(_graph, 1); 199 OrderList order_list; 200 201 AncestorMap ancestor_map(_graph, 1); 202 LowMap low_map(_graph, 1); 203 204 Visitor visitor(_graph, pred_map, tree_map, 205 order_map, order_list, ancestor_map, low_map); 206 DfsVisit<Graph, Visitor> visit(_graph, visitor); 207 visit.run(); 208 209 ChildLists child_lists(_graph); 210 createChildLists(tree_map, order_map, low_map, child_lists); 211 212 NodeData node_data(2 * order_list.size()); 213 214 EmbedArc embed_arc(_graph, false); 215 216 MergeRoots merge_roots(_graph); 217 218 for (int i = order_list.size()  1; i >= 0; i) { 219 220 Node node = order_list[i]; 221 222 Node source = node; 223 for (OutArcIt e(_graph, node); e != INVALID; ++e) { 224 Node target = _graph.target(e); 225 226 if (order_map[source] < order_map[target] && tree_map[e]) { 227 initFace(target, node_data, order_map, order_list); 228 } 229 } 230 231 for (OutArcIt e(_graph, node); e != INVALID; ++e) { 232 Node target = _graph.target(e); 233 234 if (order_map[source] < order_map[target] && !tree_map[e]) { 235 embed_arc[target] = true; 236 walkUp(target, source, i, pred_map, low_map, 237 order_map, order_list, node_data, merge_roots); 238 } 239 } 240 241 for (typename MergeRoots::Value::iterator it = 242 merge_roots[node].begin(); it != merge_roots[node].end(); ++it) { 243 int rn = *it; 244 walkDown(rn, i, node_data, order_list, child_lists, 245 ancestor_map, low_map, embed_arc, merge_roots); 246 } 247 merge_roots[node].clear(); 248 249 for (OutArcIt e(_graph, node); e != INVALID; ++e) { 250 Node target = _graph.target(e); 251 252 if (order_map[source] < order_map[target] && !tree_map[e]) { 253 if (embed_arc[target]) { 254 return false; 255 } 256 } 257 } 258 } 259 260 return true; 261 } 262 263 private: 264 265 void createChildLists(const TreeMap& tree_map, const OrderMap& order_map, 266 const LowMap& low_map, ChildLists& child_lists) { 267 268 for (NodeIt n(_graph); n != INVALID; ++n) { 269 Node source = n; 270 271 std::vector<Node> targets; 272 for (OutArcIt e(_graph, n); e != INVALID; ++e) { 273 Node target = _graph.target(e); 274 275 if (order_map[source] < order_map[target] && tree_map[e]) { 276 targets.push_back(target); 277 } 278 } 279 280 if (targets.size() == 0) { 281 child_lists[source].first = INVALID; 282 } else if (targets.size() == 1) { 283 child_lists[source].first = targets[0]; 284 child_lists[targets[0]].prev = INVALID; 285 child_lists[targets[0]].next = INVALID; 286 } else { 287 radixSort(targets.begin(), targets.end(), mapToFunctor(low_map)); 288 for (int i = 1; i < int(targets.size()); ++i) { 289 child_lists[targets[i]].prev = targets[i  1]; 290 child_lists[targets[i  1]].next = targets[i]; 291 } 292 child_lists[targets.back()].next = INVALID; 293 child_lists[targets.front()].prev = INVALID; 294 child_lists[source].first = targets.front(); 295 } 296 } 297 } 298 299 void walkUp(const Node& node, Node root, int rorder, 300 const PredMap& pred_map, const LowMap& low_map, 301 const OrderMap& order_map, const OrderList& order_list, 302 NodeData& node_data, MergeRoots& merge_roots) { 303 304 int na, nb; 305 bool da, db; 306 307 na = nb = order_map[node]; 308 da = true; db = false; 309 310 while (true) { 311 312 if (node_data[na].visited == rorder) break; 313 if (node_data[nb].visited == rorder) break; 314 315 node_data[na].visited = rorder; 316 node_data[nb].visited = rorder; 317 318 int rn = 1; 319 320 if (na >= int(order_list.size())) { 321 rn = na; 322 } else if (nb >= int(order_list.size())) { 323 rn = nb; 324 } 325 326 if (rn == 1) { 327 int nn; 328 329 nn = da ? node_data[na].prev : node_data[na].next; 330 da = node_data[nn].prev != na; 331 na = nn; 332 333 nn = db ? node_data[nb].prev : node_data[nb].next; 334 db = node_data[nn].prev != nb; 335 nb = nn; 336 337 } else { 338 339 Node rep = order_list[rn  order_list.size()]; 340 Node parent = _graph.source(pred_map[rep]); 341 342 if (low_map[rep] < rorder) { 343 merge_roots[parent].push_back(rn); 344 } else { 345 merge_roots[parent].push_front(rn); 346 } 347 348 if (parent != root) { 349 na = nb = order_map[parent]; 350 da = true; db = false; 351 } else { 352 break; 353 } 354 } 355 } 356 } 357 358 void walkDown(int rn, int rorder, NodeData& node_data, 359 OrderList& order_list, ChildLists& child_lists, 360 AncestorMap& ancestor_map, LowMap& low_map, 361 EmbedArc& embed_arc, MergeRoots& merge_roots) { 362 363 std::vector<std::pair<int, bool> > merge_stack; 364 365 for (int di = 0; di < 2; ++di) { 366 bool rd = di == 0; 367 int pn = rn; 368 int n = rd ? node_data[rn].next : node_data[rn].prev; 369 370 while (n != rn) { 371 372 Node node = order_list[n]; 373 374 if (embed_arc[node]) { 375 376 // Merging components on the critical path 377 while (!merge_stack.empty()) { 378 379 // Component root 380 int cn = merge_stack.back().first; 381 bool cd = merge_stack.back().second; 382 merge_stack.pop_back(); 383 384 // Parent of component 385 int dn = merge_stack.back().first; 386 bool dd = merge_stack.back().second; 387 merge_stack.pop_back(); 388 389 Node parent = order_list[dn]; 390 391 // Erasing from merge_roots 392 merge_roots[parent].pop_front(); 393 394 Node child = order_list[cn  order_list.size()]; 395 396 // Erasing from child_lists 397 if (child_lists[child].prev != INVALID) { 398 child_lists[child_lists[child].prev].next = 399 child_lists[child].next; 400 } else { 401 child_lists[parent].first = child_lists[child].next; 402 } 403 404 if (child_lists[child].next != INVALID) { 405 child_lists[child_lists[child].next].prev = 406 child_lists[child].prev; 407 } 408 409 // Merging external faces 410 { 411 int en = cn; 412 cn = cd ? node_data[cn].prev : node_data[cn].next; 413 cd = node_data[cn].next == en; 414 415 } 416 417 if (cd) node_data[cn].next = dn; else node_data[cn].prev = dn; 418 if (dd) node_data[dn].prev = cn; else node_data[dn].next = cn; 419 420 } 421 422 bool d = pn == node_data[n].prev; 423 424 if (node_data[n].prev == node_data[n].next && 425 node_data[n].inverted) { 426 d = !d; 427 } 428 429 // Embedding arc into external face 430 if (rd) node_data[rn].next = n; else node_data[rn].prev = n; 431 if (d) node_data[n].prev = rn; else node_data[n].next = rn; 432 pn = rn; 433 434 embed_arc[order_list[n]] = false; 435 } 436 437 if (!merge_roots[node].empty()) { 438 439 bool d = pn == node_data[n].prev; 440 441 merge_stack.push_back(std::make_pair(n, d)); 442 443 int rn = merge_roots[node].front(); 444 445 int xn = node_data[rn].next; 446 Node xnode = order_list[xn]; 447 448 int yn = node_data[rn].prev; 449 Node ynode = order_list[yn]; 450 451 bool rd; 452 if (!external(xnode, rorder, child_lists, ancestor_map, low_map)) { 453 rd = true; 454 } else if (!external(ynode, rorder, child_lists, 455 ancestor_map, low_map)) { 456 rd = false; 457 } else if (pertinent(xnode, embed_arc, merge_roots)) { 458 rd = true; 459 } else { 460 rd = false; 461 } 462 463 merge_stack.push_back(std::make_pair(rn, rd)); 464 465 pn = rn; 466 n = rd ? xn : yn; 467 468 } else if (!external(node, rorder, child_lists, 469 ancestor_map, low_map)) { 470 int nn = (node_data[n].next != pn ? 471 node_data[n].next : node_data[n].prev); 472 473 bool nd = n == node_data[nn].prev; 474 475 if (nd) node_data[nn].prev = pn; 476 else node_data[nn].next = pn; 477 478 if (n == node_data[pn].prev) node_data[pn].prev = nn; 479 else node_data[pn].next = nn; 480 481 node_data[nn].inverted = 482 (node_data[nn].prev == node_data[nn].next && nd != rd); 483 484 n = nn; 485 } 486 else break; 487 488 } 489 490 if (!merge_stack.empty()  n == rn) { 491 break; 492 } 493 } 494 } 495 496 void initFace(const Node& node, NodeData& node_data, 497 const OrderMap& order_map, const OrderList& order_list) { 498 int n = order_map[node]; 499 int rn = n + order_list.size(); 500 501 node_data[n].next = node_data[n].prev = rn; 502 node_data[rn].next = node_data[rn].prev = n; 503 504 node_data[n].visited = order_list.size(); 505 node_data[rn].visited = order_list.size(); 506 507 } 508 509 bool external(const Node& node, int rorder, 510 ChildLists& child_lists, AncestorMap& ancestor_map, 511 LowMap& low_map) { 512 Node child = child_lists[node].first; 513 514 if (child != INVALID) { 515 if (low_map[child] < rorder) return true; 516 } 517 518 if (ancestor_map[node] < rorder) return true; 519 520 return false; 521 } 522 523 bool pertinent(const Node& node, const EmbedArc& embed_arc, 524 const MergeRoots& merge_roots) { 525 return !merge_roots[node].empty()  embed_arc[node]; 526 } 527 528 }; 524 template <typename GR> 525 bool checkPlanarity(const GR& graph) { 526 _planarity_bits::PlanarityChecking<GR> pc(graph); 527 return pc.run(); 528 } 529 529 530 530 /// \ingroup planar … … 713 713 /// The returned map contains the successor of each arc in the 714 714 /// graph. 715 const EmbeddingMap& embedding () const {715 const EmbeddingMap& embeddingMap() const { 716 716 return _embedding; 717 717 }
Note: See TracChangeset
for help on using the changeset viewer.