lemon/planarity.h
changeset 843 81f7e910060b
parent 798 58c330ad0b5c
child 877 141f9c0db4a3
equal deleted inserted replaced
1:dc25a8fbeaef 2:29265c806571
   516   /// \ingroup planar
   516   /// \ingroup planar
   517   ///
   517   ///
   518   /// \brief Planarity checking of an undirected simple graph
   518   /// \brief Planarity checking of an undirected simple graph
   519   ///
   519   ///
   520   /// This function implements the Boyer-Myrvold algorithm for
   520   /// This function implements the Boyer-Myrvold algorithm for
   521   /// planarity checking of an undirected graph. It is a simplified
   521   /// planarity checking of an undirected simple graph. It is a simplified
   522   /// version of the PlanarEmbedding algorithm class because neither
   522   /// version of the PlanarEmbedding algorithm class because neither
   523   /// the embedding nor the kuratowski subdivisons are not computed.
   523   /// the embedding nor the Kuratowski subdivisons are computed.
   524   template <typename GR>
   524   template <typename GR>
   525   bool checkPlanarity(const GR& graph) {
   525   bool checkPlanarity(const GR& graph) {
   526     _planarity_bits::PlanarityChecking<GR> pc(graph);
   526     _planarity_bits::PlanarityChecking<GR> pc(graph);
   527     return pc.run();
   527     return pc.run();
   528   }
   528   }
   530   /// \ingroup planar
   530   /// \ingroup planar
   531   ///
   531   ///
   532   /// \brief Planar embedding of an undirected simple graph
   532   /// \brief Planar embedding of an undirected simple graph
   533   ///
   533   ///
   534   /// This class implements the Boyer-Myrvold algorithm for planar
   534   /// This class implements the Boyer-Myrvold algorithm for planar
   535   /// embedding of an undirected graph. The planar embedding is an
   535   /// embedding of an undirected simple graph. The planar embedding is an
   536   /// ordering of the outgoing edges of the nodes, which is a possible
   536   /// ordering of the outgoing edges of the nodes, which is a possible
   537   /// configuration to draw the graph in the plane. If there is not
   537   /// configuration to draw the graph in the plane. If there is not
   538   /// such ordering then the graph contains a \f$ K_5 \f$ (full graph
   538   /// such ordering then the graph contains a K<sub>5</sub> (full graph
   539   /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on
   539   /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on
   540   /// 3 ANode and 3 BNode) subdivision.
   540   /// 3 Red and 3 Blue nodes) subdivision.
   541   ///
   541   ///
   542   /// The current implementation calculates either an embedding or a
   542   /// The current implementation calculates either an embedding or a
   543   /// Kuratowski subdivision. The running time of the algorithm is 
   543   /// Kuratowski subdivision. The running time of the algorithm is O(n).
   544   /// \f$ O(n) \f$.
   544   ///
       
   545   /// \see PlanarDrawing, checkPlanarity()
   545   template <typename Graph>
   546   template <typename Graph>
   546   class PlanarEmbedding {
   547   class PlanarEmbedding {
   547   private:
   548   private:
   548 
   549 
   549     TEMPLATE_GRAPH_TYPEDEFS(Graph);
   550     TEMPLATE_GRAPH_TYPEDEFS(Graph);
   589       INTERNAL = 12
   590       INTERNAL = 12
   590     };
   591     };
   591 
   592 
   592   public:
   593   public:
   593 
   594 
   594     /// \brief The map for store of embedding
   595     /// \brief The map type for storing the embedding
       
   596     ///
       
   597     /// The map type for storing the embedding.
       
   598     /// \see embeddingMap()
   595     typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
   599     typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
   596 
   600 
   597     /// \brief Constructor
   601     /// \brief Constructor
   598     ///
   602     ///
   599     /// \note The graph should be simple, i.e. parallel and loop arc
   603     /// Constructor.
   600     /// free.
   604     /// \pre The graph must be simple, i.e. it should not
       
   605     /// contain parallel or loop arcs.
   601     PlanarEmbedding(const Graph& graph)
   606     PlanarEmbedding(const Graph& graph)
   602       : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
   607       : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
   603 
   608 
   604     /// \brief Runs the algorithm.
   609     /// \brief Run the algorithm.
   605     ///
   610     ///
   606     /// Runs the algorithm.
   611     /// This function runs the algorithm.
   607     /// \param kuratowski If the parameter is false, then the
   612     /// \param kuratowski If this parameter is set to \c false, then the
   608     /// algorithm does not compute a Kuratowski subdivision.
   613     /// algorithm does not compute a Kuratowski subdivision.
   609     ///\return %True when the graph is planar.
   614     /// \return \c true if the graph is planar.
   610     bool run(bool kuratowski = true) {
   615     bool run(bool kuratowski = true) {
   611       typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
   616       typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
   612 
   617 
   613       PredMap pred_map(_graph, INVALID);
   618       PredMap pred_map(_graph, INVALID);
   614       TreeMap tree_map(_graph, false);
   619       TreeMap tree_map(_graph, false);
   697       }
   702       }
   698 
   703 
   699       return true;
   704       return true;
   700     }
   705     }
   701 
   706 
   702     /// \brief Gives back the successor of an arc
   707     /// \brief Give back the successor of an arc
   703     ///
   708     ///
   704     /// Gives back the successor of an arc. This function makes
   709     /// This function gives back the successor of an arc. It makes
   705     /// possible to query the cyclic order of the outgoing arcs from
   710     /// possible to query the cyclic order of the outgoing arcs from
   706     /// a node.
   711     /// a node.
   707     Arc next(const Arc& arc) const {
   712     Arc next(const Arc& arc) const {
   708       return _embedding[arc];
   713       return _embedding[arc];
   709     }
   714     }
   710 
   715 
   711     /// \brief Gives back the calculated embedding map
   716     /// \brief Give back the calculated embedding map
   712     ///
   717     ///
   713     /// The returned map contains the successor of each arc in the
   718     /// This function gives back the calculated embedding map, which
   714     /// graph.
   719     /// contains the successor of each arc in the cyclic order of the
       
   720     /// outgoing arcs of its source node.
   715     const EmbeddingMap& embeddingMap() const {
   721     const EmbeddingMap& embeddingMap() const {
   716       return _embedding;
   722       return _embedding;
   717     }
   723     }
   718 
   724 
   719     /// \brief Gives back true if the undirected arc is in the
   725     /// \brief Give back \c true if the given edge is in the Kuratowski
   720     /// kuratowski subdivision
   726     /// subdivision
   721     ///
   727     ///
   722     /// Gives back true if the undirected arc is in the kuratowski
   728     /// This function gives back \c true if the given edge is in the found
   723     /// subdivision
   729     /// Kuratowski subdivision.
   724     /// \note The \c run() had to be called with true value.
   730     /// \pre The \c run() function must be called with \c true parameter
   725     bool kuratowski(const Edge& edge) {
   731     /// before using this function.
       
   732     bool kuratowski(const Edge& edge) const {
   726       return _kuratowski[edge];
   733       return _kuratowski[edge];
   727     }
   734     }
   728 
   735 
   729   private:
   736   private:
   730 
   737 
  2057   /// \ingroup planar
  2064   /// \ingroup planar
  2058   ///
  2065   ///
  2059   /// \brief Schnyder's planar drawing algorithm
  2066   /// \brief Schnyder's planar drawing algorithm
  2060   ///
  2067   ///
  2061   /// The planar drawing algorithm calculates positions for the nodes
  2068   /// The planar drawing algorithm calculates positions for the nodes
  2062   /// in the plane which coordinates satisfy that if the arcs are
  2069   /// in the plane. These coordinates satisfy that if the edges are
  2063   /// represented with straight lines then they will not intersect
  2070   /// represented with straight lines, then they will not intersect
  2064   /// each other.
  2071   /// each other.
  2065   ///
  2072   ///
  2066   /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,
  2073   /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid,
  2067   /// i.e. each node will be located in the \c [0,n-2]x[0,n-2] square.
  2074   /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square.
  2068   /// The time complexity of the algorithm is O(n).
  2075   /// The time complexity of the algorithm is O(n).
       
  2076   ///
       
  2077   /// \see PlanarEmbedding
  2069   template <typename Graph>
  2078   template <typename Graph>
  2070   class PlanarDrawing {
  2079   class PlanarDrawing {
  2071   public:
  2080   public:
  2072 
  2081 
  2073     TEMPLATE_GRAPH_TYPEDEFS(Graph);
  2082     TEMPLATE_GRAPH_TYPEDEFS(Graph);
  2074 
  2083 
  2075     /// \brief The point type for store coordinates
  2084     /// \brief The point type for storing coordinates
  2076     typedef dim2::Point<int> Point;
  2085     typedef dim2::Point<int> Point;
  2077     /// \brief The map type for store coordinates
  2086     /// \brief The map type for storing the coordinates of the nodes
  2078     typedef typename Graph::template NodeMap<Point> PointMap;
  2087     typedef typename Graph::template NodeMap<Point> PointMap;
  2079 
  2088 
  2080 
  2089 
  2081     /// \brief Constructor
  2090     /// \brief Constructor
  2082     ///
  2091     ///
  2083     /// Constructor
  2092     /// Constructor
  2084     /// \pre The graph should be simple, i.e. loop and parallel arc free.
  2093     /// \pre The graph must be simple, i.e. it should not
       
  2094     /// contain parallel or loop arcs.
  2085     PlanarDrawing(const Graph& graph)
  2095     PlanarDrawing(const Graph& graph)
  2086       : _graph(graph), _point_map(graph) {}
  2096       : _graph(graph), _point_map(graph) {}
  2087 
  2097 
  2088   private:
  2098   private:
  2089 
  2099 
  2364 
  2374 
  2365     }
  2375     }
  2366 
  2376 
  2367   public:
  2377   public:
  2368 
  2378 
  2369     /// \brief Calculates the node positions
  2379     /// \brief Calculate the node positions
  2370     ///
  2380     ///
  2371     /// This function calculates the node positions.
  2381     /// This function calculates the node positions on the plane.
  2372     /// \return %True if the graph is planar.
  2382     /// \return \c true if the graph is planar.
  2373     bool run() {
  2383     bool run() {
  2374       PlanarEmbedding<Graph> pe(_graph);
  2384       PlanarEmbedding<Graph> pe(_graph);
  2375       if (!pe.run()) return false;
  2385       if (!pe.run()) return false;
  2376 
  2386 
  2377       run(pe);
  2387       run(pe);
  2378       return true;
  2388       return true;
  2379     }
  2389     }
  2380 
  2390 
  2381     /// \brief Calculates the node positions according to a
  2391     /// \brief Calculate the node positions according to a
  2382     /// combinatorical embedding
  2392     /// combinatorical embedding
  2383     ///
  2393     ///
  2384     /// This function calculates the node locations. The \c embedding
  2394     /// This function calculates the node positions on the plane.
  2385     /// parameter should contain a valid combinatorical embedding, i.e.
  2395     /// The given \c embedding map should contain a valid combinatorical
  2386     /// a valid cyclic order of the arcs.
  2396     /// embedding, i.e. a valid cyclic order of the arcs.
       
  2397     /// It can be computed using PlanarEmbedding.
  2387     template <typename EmbeddingMap>
  2398     template <typename EmbeddingMap>
  2388     void run(const EmbeddingMap& embedding) {
  2399     void run(const EmbeddingMap& embedding) {
  2389       typedef SmartEdgeSet<Graph> AuxGraph;
  2400       typedef SmartEdgeSet<Graph> AuxGraph;
  2390 
  2401 
  2391       if (3 * countNodes(_graph) - 6 == countEdges(_graph)) {
  2402       if (3 * countNodes(_graph) - 6 == countEdges(_graph)) {
  2421       drawing(aux_graph, aux_embedding, _point_map);
  2432       drawing(aux_graph, aux_embedding, _point_map);
  2422     }
  2433     }
  2423 
  2434 
  2424     /// \brief The coordinate of the given node
  2435     /// \brief The coordinate of the given node
  2425     ///
  2436     ///
  2426     /// The coordinate of the given node.
  2437     /// This function returns the coordinate of the given node.
  2427     Point operator[](const Node& node) const {
  2438     Point operator[](const Node& node) const {
  2428       return _point_map[node];
  2439       return _point_map[node];
  2429     }
  2440     }
  2430 
  2441 
  2431     /// \brief Returns the grid embedding in a \e NodeMap.
  2442     /// \brief Return the grid embedding in a node map
  2432     ///
  2443     ///
  2433     /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> .
  2444     /// This function returns the grid embedding in a node map of
       
  2445     /// \c dim2::Point<int> coordinates.
  2434     const PointMap& coords() const {
  2446     const PointMap& coords() const {
  2435       return _point_map;
  2447       return _point_map;
  2436     }
  2448     }
  2437 
  2449 
  2438   private:
  2450   private:
  2468   /// \ingroup planar
  2480   /// \ingroup planar
  2469   ///
  2481   ///
  2470   /// \brief Coloring planar graphs
  2482   /// \brief Coloring planar graphs
  2471   ///
  2483   ///
  2472   /// The graph coloring problem is the coloring of the graph nodes
  2484   /// The graph coloring problem is the coloring of the graph nodes
  2473   /// that there are not adjacent nodes with the same color. The
  2485   /// so that there are no adjacent nodes with the same color. The
  2474   /// planar graphs can be always colored with four colors, it is
  2486   /// planar graphs can always be colored with four colors, which is
  2475   /// proved by Appel and Haken and their proofs provide a quadratic
  2487   /// proved by Appel and Haken. Their proofs provide a quadratic
  2476   /// time algorithm for four coloring, but it could not be used to
  2488   /// time algorithm for four coloring, but it could not be used to
  2477   /// implement efficient algorithm. The five and six coloring can be
  2489   /// implement an efficient algorithm. The five and six coloring can be
  2478   /// made in linear time, but in this class the five coloring has
  2490   /// made in linear time, but in this class, the five coloring has
  2479   /// quadratic worst case time complexity. The two coloring (if
  2491   /// quadratic worst case time complexity. The two coloring (if
  2480   /// possible) is solvable with a graph search algorithm and it is
  2492   /// possible) is solvable with a graph search algorithm and it is
  2481   /// implemented in \ref bipartitePartitions() function in LEMON. To
  2493   /// implemented in \ref bipartitePartitions() function in LEMON. To
  2482   /// decide whether the planar graph is three colorable is
  2494   /// decide whether a planar graph is three colorable is NP-complete.
  2483   /// NP-complete.
       
  2484   ///
  2495   ///
  2485   /// This class contains member functions for calculate colorings
  2496   /// This class contains member functions for calculate colorings
  2486   /// with five and six colors. The six coloring algorithm is a simple
  2497   /// with five and six colors. The six coloring algorithm is a simple
  2487   /// greedy coloring on the backward minimum outgoing order of nodes.
  2498   /// greedy coloring on the backward minimum outgoing order of nodes.
  2488   /// This order can be computed as in each phase the node with least
  2499   /// This order can be computed by selecting the node with least
  2489   /// outgoing arcs to unprocessed nodes is chosen. This order
  2500   /// outgoing arcs to unprocessed nodes in each phase. This order
  2490   /// guarantees that when a node is chosen for coloring it has at
  2501   /// guarantees that when a node is chosen for coloring it has at
  2491   /// most five already colored adjacents. The five coloring algorithm
  2502   /// most five already colored adjacents. The five coloring algorithm
  2492   /// use the same method, but if the greedy approach fails to color
  2503   /// use the same method, but if the greedy approach fails to color
  2493   /// with five colors, i.e. the node has five already different
  2504   /// with five colors, i.e. the node has five already different
  2494   /// colored neighbours, it swaps the colors in one of the connected
  2505   /// colored neighbours, it swaps the colors in one of the connected
  2497   class PlanarColoring {
  2508   class PlanarColoring {
  2498   public:
  2509   public:
  2499 
  2510 
  2500     TEMPLATE_GRAPH_TYPEDEFS(Graph);
  2511     TEMPLATE_GRAPH_TYPEDEFS(Graph);
  2501 
  2512 
  2502     /// \brief The map type for store color indexes
  2513     /// \brief The map type for storing color indices
  2503     typedef typename Graph::template NodeMap<int> IndexMap;
  2514     typedef typename Graph::template NodeMap<int> IndexMap;
  2504     /// \brief The map type for store colors
  2515     /// \brief The map type for storing colors
       
  2516     ///
       
  2517     /// The map type for storing colors.
       
  2518     /// \see Palette, Color
  2505     typedef ComposeMap<Palette, IndexMap> ColorMap;
  2519     typedef ComposeMap<Palette, IndexMap> ColorMap;
  2506 
  2520 
  2507     /// \brief Constructor
  2521     /// \brief Constructor
  2508     ///
  2522     ///
  2509     /// Constructor
  2523     /// Constructor.
  2510     /// \pre The graph should be simple, i.e. loop and parallel arc free.
  2524     /// \pre The graph must be simple, i.e. it should not
       
  2525     /// contain parallel or loop arcs.
  2511     PlanarColoring(const Graph& graph)
  2526     PlanarColoring(const Graph& graph)
  2512       : _graph(graph), _color_map(graph), _palette(0) {
  2527       : _graph(graph), _color_map(graph), _palette(0) {
  2513       _palette.add(Color(1,0,0));
  2528       _palette.add(Color(1,0,0));
  2514       _palette.add(Color(0,1,0));
  2529       _palette.add(Color(0,1,0));
  2515       _palette.add(Color(0,0,1));
  2530       _palette.add(Color(0,0,1));
  2516       _palette.add(Color(1,1,0));
  2531       _palette.add(Color(1,1,0));
  2517       _palette.add(Color(1,0,1));
  2532       _palette.add(Color(1,0,1));
  2518       _palette.add(Color(0,1,1));
  2533       _palette.add(Color(0,1,1));
  2519     }
  2534     }
  2520 
  2535 
  2521     /// \brief Returns the \e NodeMap of color indexes
  2536     /// \brief Return the node map of color indices
  2522     ///
  2537     ///
  2523     /// Returns the \e NodeMap of color indexes. The values are in the
  2538     /// This function returns the node map of color indices. The values are
  2524     /// range \c [0..4] or \c [0..5] according to the coloring method.
  2539     /// in the range \c [0..4] or \c [0..5] according to the coloring method.
  2525     IndexMap colorIndexMap() const {
  2540     IndexMap colorIndexMap() const {
  2526       return _color_map;
  2541       return _color_map;
  2527     }
  2542     }
  2528 
  2543 
  2529     /// \brief Returns the \e NodeMap of colors
  2544     /// \brief Return the node map of colors
  2530     ///
  2545     ///
  2531     /// Returns the \e NodeMap of colors. The values are five or six
  2546     /// This function returns the node map of colors. The values are among
  2532     /// distinct \ref lemon::Color "colors".
  2547     /// five or six distinct \ref lemon::Color "colors".
  2533     ColorMap colorMap() const {
  2548     ColorMap colorMap() const {
  2534       return composeMap(_palette, _color_map);
  2549       return composeMap(_palette, _color_map);
  2535     }
  2550     }
  2536 
  2551 
  2537     /// \brief Returns the color index of the node
  2552     /// \brief Return the color index of the node
  2538     ///
  2553     ///
  2539     /// Returns the color index of the node. The values are in the
  2554     /// This function returns the color index of the given node. The value is
  2540     /// range \c [0..4] or \c [0..5] according to the coloring method.
  2555     /// in the range \c [0..4] or \c [0..5] according to the coloring method.
  2541     int colorIndex(const Node& node) const {
  2556     int colorIndex(const Node& node) const {
  2542       return _color_map[node];
  2557       return _color_map[node];
  2543     }
  2558     }
  2544 
  2559 
  2545     /// \brief Returns the color of the node
  2560     /// \brief Return the color of the node
  2546     ///
  2561     ///
  2547     /// Returns the color of the node. The values are five or six
  2562     /// This function returns the color of the given node. The value is among
  2548     /// distinct \ref lemon::Color "colors".
  2563     /// five or six distinct \ref lemon::Color "colors".
  2549     Color color(const Node& node) const {
  2564     Color color(const Node& node) const {
  2550       return _palette[_color_map[node]];
  2565       return _palette[_color_map[node]];
  2551     }
  2566     }
  2552 
  2567 
  2553 
  2568 
  2554     /// \brief Calculates a coloring with at most six colors
  2569     /// \brief Calculate a coloring with at most six colors
  2555     ///
  2570     ///
  2556     /// This function calculates a coloring with at most six colors. The time
  2571     /// This function calculates a coloring with at most six colors. The time
  2557     /// complexity of this variant is linear in the size of the graph.
  2572     /// complexity of this variant is linear in the size of the graph.
  2558     /// \return %True when the algorithm could color the graph with six color.
  2573     /// \return \c true if the algorithm could color the graph with six colors.
  2559     /// If the algorithm fails, then the graph could not be planar.
  2574     /// If the algorithm fails, then the graph is not planar.
  2560     /// \note This function can return true if the graph is not
  2575     /// \note This function can return \c true if the graph is not
  2561     /// planar but it can be colored with 6 colors.
  2576     /// planar, but it can be colored with at most six colors.
  2562     bool runSixColoring() {
  2577     bool runSixColoring() {
  2563 
  2578 
  2564       typename Graph::template NodeMap<int> heap_index(_graph, -1);
  2579       typename Graph::template NodeMap<int> heap_index(_graph, -1);
  2565       BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
  2580       BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
  2566 
  2581 
  2658       }
  2673       }
  2659     }
  2674     }
  2660 
  2675 
  2661   public:
  2676   public:
  2662 
  2677 
  2663     /// \brief Calculates a coloring with at most five colors
  2678     /// \brief Calculate a coloring with at most five colors
  2664     ///
  2679     ///
  2665     /// This function calculates a coloring with at most five
  2680     /// This function calculates a coloring with at most five
  2666     /// colors. The worst case time complexity of this variant is
  2681     /// colors. The worst case time complexity of this variant is
  2667     /// quadratic in the size of the graph.
  2682     /// quadratic in the size of the graph.
       
  2683     /// \param embedding This map should contain a valid combinatorical
       
  2684     /// embedding, i.e. a valid cyclic order of the arcs.
       
  2685     /// It can be computed using PlanarEmbedding.
  2668     template <typename EmbeddingMap>
  2686     template <typename EmbeddingMap>
  2669     void runFiveColoring(const EmbeddingMap& embedding) {
  2687     void runFiveColoring(const EmbeddingMap& embedding) {
  2670 
  2688 
  2671       typename Graph::template NodeMap<int> heap_index(_graph, -1);
  2689       typename Graph::template NodeMap<int> heap_index(_graph, -1);
  2672       BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
  2690       BucketHeap<typename Graph::template NodeMap<int> > heap(heap_index);
  2709           kempeRecoloring(order[i], embedding);
  2727           kempeRecoloring(order[i], embedding);
  2710         }
  2728         }
  2711       }
  2729       }
  2712     }
  2730     }
  2713 
  2731 
  2714     /// \brief Calculates a coloring with at most five colors
  2732     /// \brief Calculate a coloring with at most five colors
  2715     ///
  2733     ///
  2716     /// This function calculates a coloring with at most five
  2734     /// This function calculates a coloring with at most five
  2717     /// colors. The worst case time complexity of this variant is
  2735     /// colors. The worst case time complexity of this variant is
  2718     /// quadratic in the size of the graph.
  2736     /// quadratic in the size of the graph.
  2719     /// \return %True when the graph is planar.
  2737     /// \return \c true if the graph is planar.
  2720     bool runFiveColoring() {
  2738     bool runFiveColoring() {
  2721       PlanarEmbedding<Graph> pe(_graph);
  2739       PlanarEmbedding<Graph> pe(_graph);
  2722       if (!pe.run()) return false;
  2740       if (!pe.run()) return false;
  2723 
  2741 
  2724       runFiveColoring(pe.embeddingMap());
  2742       runFiveColoring(pe.embeddingMap());