Changeset 896:5fd7fafc4470 in lemon
- Timestamp:
- 02/11/10 07:40:29 (15 years ago)
- Branch:
- default
- Phase:
- public
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/planarity.h
r862 r896 519 519 /// 520 520 /// This function implements the Boyer-Myrvold algorithm for 521 /// planarity checking of an undirected graph. It is a simplified521 /// planarity checking of an undirected simple graph. It is a simplified 522 522 /// version of the PlanarEmbedding algorithm class because neither 523 /// the embedding nor the kuratowski subdivisons are notcomputed.523 /// the embedding nor the Kuratowski subdivisons are computed. 524 524 template <typename GR> 525 525 bool checkPlanarity(const GR& graph) { … … 533 533 /// 534 534 /// This class implements the Boyer-Myrvold algorithm for planar 535 /// embedding of an undirected graph. The planar embedding is an535 /// embedding of an undirected simple graph. The planar embedding is an 536 536 /// ordering of the outgoing edges of the nodes, which is a possible 537 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 graph539 /// with 5 nodes) or a \f$ K_{3,3} \f$(complete bipartite graph on540 /// 3 ANode and 3 BNode) subdivision.538 /// such ordering then the graph contains a K<sub>5</sub> (full graph 539 /// with 5 nodes) or a K<sub>3,3</sub> (complete bipartite graph on 540 /// 3 Red and 3 Blue nodes) subdivision. 541 541 /// 542 542 /// The current implementation calculates either an embedding or a 543 /// Kuratowski subdivision. The running time of the algorithm is 544 /// \f$ O(n) \f$. 543 /// Kuratowski subdivision. The running time of the algorithm is O(n). 544 /// 545 /// \see PlanarDrawing, checkPlanarity() 545 546 template <typename Graph> 546 547 class PlanarEmbedding { … … 592 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 599 typedef typename Graph::template ArcMap<Arc> EmbeddingMap; 596 600 597 601 /// \brief Constructor 598 602 /// 599 /// \note The graph should be simple, i.e. parallel and loop arc 600 /// free. 603 /// Constructor. 604 /// \pre The graph must be simple, i.e. it should not 605 /// contain parallel or loop arcs. 601 606 PlanarEmbedding(const Graph& graph) 602 607 : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {} 603 608 604 /// \brief Run sthe algorithm.609 /// \brief Run the algorithm. 605 610 /// 606 /// Runs the algorithm.607 /// \param kuratowski If th e parameter isfalse, then the611 /// This function runs the algorithm. 612 /// \param kuratowski If this parameter is set to \c false, then the 608 613 /// algorithm does not compute a Kuratowski subdivision. 609 /// \return %True whenthe graph is planar.614 /// \return \c true if the graph is planar. 610 615 bool run(bool kuratowski = true) { 611 616 typedef _planarity_bits::PlanarityVisitor<Graph> Visitor; … … 700 705 } 701 706 702 /// \brief Give sback the successor of an arc707 /// \brief Give back the successor of an arc 703 708 /// 704 /// Gives back the successor of an arc. This functionmakes709 /// This function gives back the successor of an arc. It makes 705 710 /// possible to query the cyclic order of the outgoing arcs from 706 711 /// a node. … … 709 714 } 710 715 711 /// \brief Give sback the calculated embedding map716 /// \brief Give back the calculated embedding map 712 717 /// 713 /// The returned map contains the successor of each arc in the 714 /// graph. 718 /// This function gives back the calculated embedding map, which 719 /// contains the successor of each arc in the cyclic order of the 720 /// outgoing arcs of its source node. 715 721 const EmbeddingMap& embeddingMap() const { 716 722 return _embedding; 717 723 } 718 724 719 /// \brief Give s back true if the undirected arc is in the720 /// kuratowskisubdivision725 /// \brief Give back \c true if the given edge is in the Kuratowski 726 /// subdivision 721 727 /// 722 /// Gives back true if the undirected arc is in the kuratowski 723 /// subdivision 724 /// \note The \c run() had to be called with true value. 725 bool kuratowski(const Edge& edge) { 728 /// This function gives back \c true if the given edge is in the found 729 /// Kuratowski subdivision. 730 /// \pre The \c run() function must be called with \c true parameter 731 /// before using this function. 732 bool kuratowski(const Edge& edge) const { 726 733 return _kuratowski[edge]; 727 734 } … … 2060 2067 /// 2061 2068 /// The planar drawing algorithm calculates positions for the nodes 2062 /// in the plane which coordinates satisfy that if the arcs are2063 /// represented with straight lines then they will not intersect2069 /// in the plane. These coordinates satisfy that if the edges are 2070 /// represented with straight lines, then they will not intersect 2064 2071 /// each other. 2065 2072 /// 2066 /// Scnyder's algorithm embeds the graph on \c (n-2,n-2) size grid,2067 /// i.e. each node will be located in the \c [0 ,n-2]x[0,n-2] square.2073 /// Scnyder's algorithm embeds the graph on an \c (n-2)x(n-2) size grid, 2074 /// i.e. each node will be located in the \c [0..n-2]x[0..n-2] square. 2068 2075 /// The time complexity of the algorithm is O(n). 2076 /// 2077 /// \see PlanarEmbedding 2069 2078 template <typename Graph> 2070 2079 class PlanarDrawing { … … 2073 2082 TEMPLATE_GRAPH_TYPEDEFS(Graph); 2074 2083 2075 /// \brief The point type for stor ecoordinates2084 /// \brief The point type for storing coordinates 2076 2085 typedef dim2::Point<int> Point; 2077 /// \brief The map type for stor e coordinates2086 /// \brief The map type for storing the coordinates of the nodes 2078 2087 typedef typename Graph::template NodeMap<Point> PointMap; 2079 2088 … … 2082 2091 /// 2083 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 2095 PlanarDrawing(const Graph& graph) 2086 2096 : _graph(graph), _point_map(graph) {} … … 2367 2377 public: 2368 2378 2369 /// \brief Calculate sthe node positions2379 /// \brief Calculate the node positions 2370 2380 /// 2371 /// This function calculates the node positions .2372 /// \return %True if the graph is planar.2381 /// This function calculates the node positions on the plane. 2382 /// \return \c true if the graph is planar. 2373 2383 bool run() { 2374 2384 PlanarEmbedding<Graph> pe(_graph); … … 2379 2389 } 2380 2390 2381 /// \brief Calculate sthe node positions according to a2391 /// \brief Calculate the node positions according to a 2382 2392 /// combinatorical embedding 2383 2393 /// 2384 /// This function calculates the node locations. The \c embedding 2385 /// parameter should contain a valid combinatorical embedding, i.e. 2386 /// a valid cyclic order of the arcs. 2394 /// This function calculates the node positions on the plane. 2395 /// The given \c embedding map should contain a valid combinatorical 2396 /// embedding, i.e. a valid cyclic order of the arcs. 2397 /// It can be computed using PlanarEmbedding. 2387 2398 template <typename EmbeddingMap> 2388 2399 void run(const EmbeddingMap& embedding) { … … 2424 2435 /// \brief The coordinate of the given node 2425 2436 /// 2426 /// Th e coordinate of the given node.2437 /// This function returns the coordinate of the given node. 2427 2438 Point operator[](const Node& node) const { 2428 2439 return _point_map[node]; 2429 2440 } 2430 2441 2431 /// \brief Return s 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 2446 const PointMap& coords() const { 2435 2447 return _point_map; … … 2471 2483 /// 2472 2484 /// The graph coloring problem is the coloring of the graph nodes 2473 /// that there are notadjacent nodes with the same color. The2474 /// planar graphs can be always colored with four colors, itis2475 /// proved by Appel and Haken and their proofs provide a quadratic2485 /// so that there are no adjacent nodes with the same color. The 2486 /// planar graphs can always be colored with four colors, which is 2487 /// proved by Appel and Haken. Their proofs provide a quadratic 2476 2488 /// time algorithm for four coloring, but it could not be used to 2477 /// implement efficient algorithm. The five and six coloring can be2478 /// made in linear time, but in this class the five coloring has2489 /// implement an efficient algorithm. The five and six coloring can be 2490 /// made in linear time, but in this class, the five coloring has 2479 2491 /// quadratic worst case time complexity. The two coloring (if 2480 2492 /// possible) is solvable with a graph search algorithm and it is 2481 2493 /// implemented in \ref bipartitePartitions() function in LEMON. To 2482 /// decide whether the planar graph is three colorable is 2483 /// NP-complete. 2494 /// decide whether a planar graph is three colorable is NP-complete. 2484 2495 /// 2485 2496 /// This class contains member functions for calculate colorings 2486 2497 /// with five and six colors. The six coloring algorithm is a simple 2487 2498 /// greedy coloring on the backward minimum outgoing order of nodes. 2488 /// This order can be computed as in each phasethe node with least2489 /// outgoing arcs to unprocessed nodes i s chosen. This order2499 /// This order can be computed by selecting the node with least 2500 /// outgoing arcs to unprocessed nodes in each phase. This order 2490 2501 /// guarantees that when a node is chosen for coloring it has at 2491 2502 /// most five already colored adjacents. The five coloring algorithm … … 2500 2511 TEMPLATE_GRAPH_TYPEDEFS(Graph); 2501 2512 2502 /// \brief The map type for stor e color indexes2513 /// \brief The map type for storing color indices 2503 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 2519 typedef ComposeMap<Palette, IndexMap> ColorMap; 2506 2520 2507 2521 /// \brief Constructor 2508 2522 /// 2509 /// Constructor 2510 /// \pre The graph should be simple, i.e. loop and parallel arc free. 2523 /// Constructor. 2524 /// \pre The graph must be simple, i.e. it should not 2525 /// contain parallel or loop arcs. 2511 2526 PlanarColoring(const Graph& graph) 2512 2527 : _graph(graph), _color_map(graph), _palette(0) { … … 2519 2534 } 2520 2535 2521 /// \brief Return s the \e NodeMap of color indexes2536 /// \brief Return the node map of color indices 2522 2537 /// 2523 /// Returns the \e NodeMap of color indexes. The values are in the2524 /// range \c [0..4] or \c [0..5] according to the coloring method.2538 /// This function returns the node map of color indices. The values are 2539 /// in the range \c [0..4] or \c [0..5] according to the coloring method. 2525 2540 IndexMap colorIndexMap() const { 2526 2541 return _color_map; 2527 2542 } 2528 2543 2529 /// \brief Return s the \e NodeMap of colors2544 /// \brief Return the node map of colors 2530 2545 /// 2531 /// Returns the \e NodeMap of colors. The values are five or six2532 /// distinct \ref lemon::Color "colors".2546 /// This function returns the node map of colors. The values are among 2547 /// five or six distinct \ref lemon::Color "colors". 2533 2548 ColorMap colorMap() const { 2534 2549 return composeMap(_palette, _color_map); 2535 2550 } 2536 2551 2537 /// \brief Return sthe color index of the node2552 /// \brief Return the color index of the node 2538 2553 /// 2539 /// Returns the color index of the node. The values are in the2540 /// range \c [0..4] or \c [0..5] according to the coloring method.2554 /// This function returns the color index of the given node. The value is 2555 /// in the range \c [0..4] or \c [0..5] according to the coloring method. 2541 2556 int colorIndex(const Node& node) const { 2542 2557 return _color_map[node]; 2543 2558 } 2544 2559 2545 /// \brief Return sthe color of the node2560 /// \brief Return the color of the node 2546 2561 /// 2547 /// Returns the color of the node. The values are five or six2548 /// distinct \ref lemon::Color "colors".2562 /// This function returns the color of the given node. The value is among 2563 /// five or six distinct \ref lemon::Color "colors". 2549 2564 Color color(const Node& node) const { 2550 2565 return _palette[_color_map[node]]; … … 2552 2567 2553 2568 2554 /// \brief Calculate sa coloring with at most six colors2569 /// \brief Calculate a coloring with at most six colors 2555 2570 /// 2556 2571 /// This function calculates a coloring with at most six colors. The time 2557 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.2559 /// If the algorithm fails, then the graph could not beplanar.2560 /// \note This function can return true if the graph is not2561 /// planar but it can be colored with 6colors.2573 /// \return \c true if the algorithm could color the graph with six colors. 2574 /// If the algorithm fails, then the graph is not planar. 2575 /// \note This function can return \c true if the graph is not 2576 /// planar, but it can be colored with at most six colors. 2562 2577 bool runSixColoring() { 2563 2578 … … 2661 2676 public: 2662 2677 2663 /// \brief Calculate sa coloring with at most five colors2678 /// \brief Calculate a coloring with at most five colors 2664 2679 /// 2665 2680 /// This function calculates a coloring with at most five 2666 2681 /// colors. The worst case time complexity of this variant is 2667 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 2686 template <typename EmbeddingMap> 2669 2687 void runFiveColoring(const EmbeddingMap& embedding) { … … 2712 2730 } 2713 2731 2714 /// \brief Calculate sa coloring with at most five colors2732 /// \brief Calculate a coloring with at most five colors 2715 2733 /// 2716 2734 /// This function calculates a coloring with at most five 2717 2735 /// colors. The worst case time complexity of this variant is 2718 2736 /// quadratic in the size of the graph. 2719 /// \return %True whenthe graph is planar.2737 /// \return \c true if the graph is planar. 2720 2738 bool runFiveColoring() { 2721 2739 PlanarEmbedding<Graph> pe(_graph);
Note: See TracChangeset
for help on using the changeset viewer.