Changeset 2508:c86db0f7f917 in lemon0.x
 Timestamp:
 11/08/07 15:21:28 (12 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@3362
 File:

 1 edited
Legend:
 Unmodified
 Added
 Removed

lemon/planarity.h
r2500 r2508 21 21 /// \ingroup planar 22 22 /// \file 23 /// \brief Planarity checking, embedding 23 /// \brief Planarity checking, embedding, drawing and coloring 24 24 25 25 #include <vector> … … 27 27 28 28 #include <lemon/dfs.h> 29 #include <lemon/bfs.h> 29 30 #include <lemon/radix_sort.h> 30 31 #include <lemon/maps.h> … … 32 33 #include <lemon/iterable_maps.h> 33 34 #include <lemon/edge_set.h> 35 #include <lemon/bucket_heap.h> 36 #include <lemon/ugraph_adaptor.h> 37 #include <lemon/color.h> 34 38 35 39 … … 2439 2443 }; 2440 2444 2445 namespace _planarity_bits { 2446 2447 template <typename ColorMap> 2448 class KempeFilter { 2449 public: 2450 typedef typename ColorMap::Key Key; 2451 typedef bool Value; 2452 2453 KempeFilter(const ColorMap& color_map, 2454 const typename ColorMap::Value& first, 2455 const typename ColorMap::Value& second) 2456 : _color_map(color_map), _first(first), _second(second) {} 2457 2458 Value operator[](const Key& key) const { 2459 return _color_map[key] == _first  _color_map[key] == _second; 2460 } 2461 2462 private: 2463 const ColorMap& _color_map; 2464 typename ColorMap::Value _first, _second; 2465 }; 2466 } 2467 2468 /// \ingroup planar 2469 /// 2470 /// \brief Coloring planar graphs 2471 /// 2472 /// The graph coloring problem is the coloring of the graph nodes 2473 /// such way that there are not adjacent nodes with the same 2474 /// color. The planar graphs can be always colored with four colors, 2475 /// it is proved by Appel and Haken and their proofs provide a 2476 /// quadratic time algorithm for four coloring, but it could not be 2477 /// used to implement efficient algorithm. The five and six coloring 2478 /// can be made in linear time, but in this class the five coloring 2479 /// has quadratic worst case time complexity. The two coloring (if 2480 /// possible) is solvable with a graph search algorithm and it is 2481 /// implemented in \ref bipartitePartitions() function in Lemon. To 2482 /// decide whether the planar graph is three colorable is 2483 /// NPcomplete. 2484 /// 2485 /// This class contains member functions for calculate colorings 2486 /// with five and six colors. The six coloring algorithm is a simple 2487 /// greedy coloring on the backward minimum outgoing order of nodes. 2488 /// This order can be computed such way, that in each phase the node 2489 /// with least outgoing edges to unprocessed nodes is choosen. This 2490 /// order guarantees that at the time of coloring of a node it has 2491 /// at most five already colored adjacents. The five coloring 2492 /// algorithm works in the same way, but if the greedy approach 2493 /// fails to color with five color, ie. the node has five already 2494 /// different colored neighbours, it swaps the colors in one 2495 /// connected two colored set with the Kempe recoloring method. 2496 template <typename UGraph> 2497 class PlanarColoring { 2498 public: 2499 2500 UGRAPH_TYPEDEFS(typename UGraph); 2501 2502 /// \brief The map type for store color indexes 2503 typedef typename UGraph::template NodeMap<int> IndexMap; 2504 /// \brief The map type for store colors 2505 typedef ComposeMap<Palette, IndexMap> ColorMap; 2506 2507 /// \brief Constructor 2508 /// 2509 /// Constructor 2510 /// \pre The ugraph should be simple, ie. loop and parallel edge free. 2511 PlanarColoring(const UGraph& ugraph) 2512 : _ugraph(ugraph), _color_map(ugraph), _palette(0) { 2513 _palette.add(Color(1,0,0)); 2514 _palette.add(Color(0,1,0)); 2515 _palette.add(Color(0,0,1)); 2516 _palette.add(Color(1,1,0)); 2517 _palette.add(Color(1,0,1)); 2518 _palette.add(Color(0,1,1)); 2519 } 2520 2521 /// \brief Returns the \e NodeMap of color indexes 2522 /// 2523 /// Returns the \e NodeMap of color indexes. The values are in the 2524 /// range \c [0..4] or \c [0..5] according to the five coloring or 2525 /// six coloring. 2526 IndexMap colorIndexMap() const { 2527 return _color_map; 2528 } 2529 2530 /// \brief Returns the \e NodeMap of colors 2531 /// 2532 /// Returns the \e NodeMap of colors. The values are five or six 2533 /// distinct \ref lemon::Color "colors". 2534 ColorMap colorMap() const { 2535 return composeMap(_palette, _color_map); 2536 } 2537 2538 /// \brief Returns the color index of the node 2539 /// 2540 /// Returns the color index of the node. The values are in the 2541 /// range \c [0..4] or \c [0..5] according to the five coloring or 2542 /// six coloring. 2543 int colorIndex(const Node& node) const { 2544 return _color_map[node]; 2545 } 2546 2547 /// \brief Returns the color of the node 2548 /// 2549 /// Returns the color of the node. The values are five or six 2550 /// distinct \ref lemon::Color "colors". 2551 int color(const Node& node) const { 2552 return _palette[_color_map[node]]; 2553 } 2554 2555 2556 /// \brief Calculates a coloring with at most six colors 2557 /// 2558 /// This function calculates a coloring with at most six colors. The time 2559 /// complexity of this variant is linear in the size of the graph. 2560 /// \return %True when the algorithm could color the graph with six color. 2561 /// If the algorithm fails, then the graph could not be planar. 2562 bool runSixColoring() { 2563 2564 typename UGraph::template NodeMap<int> heap_index(_ugraph, 1); 2565 BucketHeap<typename UGraph::template NodeMap<int> > heap(heap_index); 2566 2567 for (NodeIt n(_ugraph); n != INVALID; ++n) { 2568 _color_map[n] = 2; 2569 heap.push(n, countOutEdges(_ugraph, n)); 2570 } 2571 2572 std::vector<Node> order; 2573 2574 while (!heap.empty()) { 2575 Node n = heap.top(); 2576 heap.pop(); 2577 _color_map[n] = 1; 2578 order.push_back(n); 2579 for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) { 2580 Node t = _ugraph.runningNode(e); 2581 if (_color_map[t] == 2) { 2582 heap.decrease(t, heap[t]  1); 2583 } 2584 } 2585 } 2586 2587 for (int i = order.size()  1; i >= 0; i) { 2588 std::vector<bool> forbidden(6, false); 2589 for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) { 2590 Node t = _ugraph.runningNode(e); 2591 if (_color_map[t] != 1) { 2592 forbidden[_color_map[t]] = true; 2593 } 2594 } 2595 for (int k = 0; k < 6; ++k) { 2596 if (!forbidden[k]) { 2597 _color_map[order[i]] = k; 2598 break; 2599 } 2600 } 2601 if (_color_map[order[i]] == 1) { 2602 return false; 2603 } 2604 } 2605 return true; 2606 } 2607 2608 private: 2609 2610 bool recolor(const Node& u, const Node& v) { 2611 int ucolor = _color_map[u]; 2612 int vcolor = _color_map[v]; 2613 typedef _planarity_bits::KempeFilter<IndexMap> KempeFilter; 2614 KempeFilter filter(_color_map, ucolor, vcolor); 2615 2616 typedef NodeSubUGraphAdaptor<const UGraph, const KempeFilter> KempeUGraph; 2617 KempeUGraph kempe_ugraph(_ugraph, filter); 2618 2619 std::vector<Node> comp; 2620 Bfs<KempeUGraph> bfs(kempe_ugraph); 2621 bfs.init(); 2622 bfs.addSource(u); 2623 while (!bfs.emptyQueue()) { 2624 Node n = bfs.nextNode(); 2625 if (n == v) return false; 2626 comp.push_back(n); 2627 bfs.processNextNode(); 2628 } 2629 2630 int scolor = ucolor + vcolor; 2631 for (int i = 0; i < static_cast<int>(comp.size()); ++i) { 2632 _color_map[comp[i]] = scolor  _color_map[comp[i]]; 2633 } 2634 2635 return true; 2636 } 2637 2638 template <typename EmbeddingMap> 2639 void kempeRecoloring(const Node& node, const EmbeddingMap& embedding) { 2640 std::vector<Node> nodes; 2641 nodes.reserve(4); 2642 2643 for (Edge e = OutEdgeIt(_ugraph, node); e != INVALID; e = embedding[e]) { 2644 Node t = _ugraph.target(e); 2645 if (_color_map[t] != 1) { 2646 nodes.push_back(t); 2647 if (nodes.size() == 4) break; 2648 } 2649 } 2650 2651 int color = _color_map[nodes[0]]; 2652 if (recolor(nodes[0], nodes[2])) { 2653 _color_map[node] = color; 2654 } else { 2655 color = _color_map[nodes[1]]; 2656 recolor(nodes[1], nodes[3]); 2657 _color_map[node] = color; 2658 } 2659 } 2660 2661 public: 2662 2663 /// \brief Calculates a coloring with at most five colors 2664 /// 2665 /// This function calculates a coloring with at most five 2666 /// colors. The wirst case time complexity of this variant is 2667 /// quadratic in the size of the graph. 2668 template <typename EmbeddingMap> 2669 void runFiveColoring(const EmbeddingMap& embedding) { 2670 2671 typename UGraph::template NodeMap<int> heap_index(_ugraph, 1); 2672 BucketHeap<typename UGraph::template NodeMap<int> > heap(heap_index); 2673 2674 for (NodeIt n(_ugraph); n != INVALID; ++n) { 2675 _color_map[n] = 2; 2676 heap.push(n, countOutEdges(_ugraph, n)); 2677 } 2678 2679 std::vector<Node> order; 2680 2681 while (!heap.empty()) { 2682 Node n = heap.top(); 2683 heap.pop(); 2684 _color_map[n] = 1; 2685 order.push_back(n); 2686 for (OutEdgeIt e(_ugraph, n); e != INVALID; ++e) { 2687 Node t = _ugraph.runningNode(e); 2688 if (_color_map[t] == 2) { 2689 heap.decrease(t, heap[t]  1); 2690 } 2691 } 2692 } 2693 2694 for (int i = order.size()  1; i >= 0; i) { 2695 std::vector<bool> forbidden(5, false); 2696 for (OutEdgeIt e(_ugraph, order[i]); e != INVALID; ++e) { 2697 Node t = _ugraph.runningNode(e); 2698 if (_color_map[t] != 1) { 2699 forbidden[_color_map[t]] = true; 2700 } 2701 } 2702 for (int k = 0; k < 5; ++k) { 2703 if (!forbidden[k]) { 2704 _color_map[order[i]] = k; 2705 break; 2706 } 2707 } 2708 if (_color_map[order[i]] == 1) { 2709 kempeRecoloring(order[i], embedding); 2710 } 2711 } 2712 } 2713 2714 /// \brief Calculates a coloring with at most five colors 2715 /// 2716 /// This function calculates a coloring with at most five 2717 /// colors. The worst case time complexity of this variant is 2718 /// quadratic in the size of the graph, but it most cases it does 2719 /// not have to use Kempe recoloring method, in this case it is 2720 /// equivalent with the runSixColoring() algorithm. 2721 /// \return %True when the graph is planar. 2722 bool runFiveColoring() { 2723 PlanarEmbedding<UGraph> pe(_ugraph); 2724 if (!pe.run()) return false; 2725 2726 runFiveColoring(pe.embeddingMap()); 2727 return true; 2728 } 2729 2730 private: 2731 2732 const UGraph& _ugraph; 2733 IndexMap _color_map; 2734 Palette _palette; 2735 }; 2736 2441 2737 } 2442 2738
Note: See TracChangeset
for help on using the changeset viewer.