Changes in / [897:7762cab7f372:892:02109e17027f] in lemon
- Files:
-
- 1 deleted
- 3 edited
-
doc/CMakeLists.txt (modified) (1 diff)
-
doc/Makefile.am (modified) (1 diff)
-
doc/images/planar.eps (deleted)
-
lemon/planarity.h (modified) (17 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/CMakeLists.txt
r895 r791 27 27 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps 28 28 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/planar.png ${CMAKE_CURRENT_SOURCE_DIR}/images/planar.eps30 29 COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps 31 30 COMMAND ${CMAKE_COMMAND} -E remove_directory html -
doc/Makefile.am
r895 r791 29 29 edge_biconnected_components.eps \ 30 30 node_biconnected_components.eps \ 31 planar.eps \32 31 strongly_connected_components.eps 33 32 -
lemon/planarity.h
r896 r862 519 519 /// 520 520 /// This function implements the Boyer-Myrvold algorithm for 521 /// planarity checking of an undirected simplegraph. It is a simplified521 /// planarity checking of an undirected graph. It is a simplified 522 522 /// version of the PlanarEmbedding algorithm class because neither 523 /// the embedding nor the Kuratowski subdivisons arecomputed.523 /// the embedding nor the kuratowski subdivisons are not 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 simplegraph. The planar embedding is an535 /// embedding of an undirected 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 K<sub>5</sub>(full graph539 /// with 5 nodes) or a K<sub>3,3</sub>(complete bipartite graph on540 /// 3 Red and 3 Blue nodes) subdivision.538 /// such ordering then the graph contains a \f$ K_5 \f$ (full graph 539 /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on 540 /// 3 ANode and 3 BNode) subdivision. 541 541 /// 542 542 /// The current implementation calculates either an embedding or a 543 /// Kuratowski subdivision. The running time of the algorithm is O(n). 544 /// 545 /// \see PlanarDrawing, checkPlanarity() 543 /// Kuratowski subdivision. The running time of the algorithm is 544 /// \f$ O(n) \f$. 546 545 template <typename Graph> 547 546 class PlanarEmbedding { … … 593 592 public: 594 593 595 /// \brief The map type for storing the embedding 596 /// 597 /// The map type for storing the embedding. 598 /// \see embeddingMap() 594 /// \brief The map for store of embedding 599 595 typedef typename Graph::template ArcMap<Arc> EmbeddingMap; 600 596 601 597 /// \brief Constructor 602 598 /// 603 /// Constructor. 604 /// \pre The graph must be simple, i.e. it should not 605 /// contain parallel or loop arcs. 599 /// \note The graph should be simple, i.e. parallel and loop arc 600 /// free. 606 601 PlanarEmbedding(const Graph& graph) 607 602 : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {} 608 603 609 /// \brief Run the algorithm.604 /// \brief Runs the algorithm. 610 605 /// 611 /// This function runs the algorithm.612 /// \param kuratowski If th is parameter is set to \cfalse, then the606 /// Runs the algorithm. 607 /// \param kuratowski If the parameter is false, then the 613 608 /// algorithm does not compute a Kuratowski subdivision. 614 /// \return \c true ifthe graph is planar.609 ///\return %True when the graph is planar. 615 610 bool run(bool kuratowski = true) { 616 611 typedef _planarity_bits::PlanarityVisitor<Graph> Visitor; … … 705 700 } 706 701 707 /// \brief Give back the successor of an arc702 /// \brief Gives back the successor of an arc 708 703 /// 709 /// This function gives back the successor of an arc. Itmakes704 /// Gives back the successor of an arc. This function makes 710 705 /// possible to query the cyclic order of the outgoing arcs from 711 706 /// a node. … … 714 709 } 715 710 716 /// \brief Give back the calculated embedding map711 /// \brief Gives back the calculated embedding map 717 712 /// 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. 713 /// The returned map contains the successor of each arc in the 714 /// graph. 721 715 const EmbeddingMap& embeddingMap() const { 722 716 return _embedding; 723 717 } 724 718 725 /// \brief Give back \c true if the given edge is in the Kuratowski 719 /// \brief Gives back true if the undirected arc is in the 720 /// kuratowski subdivision 721 /// 722 /// Gives back true if the undirected arc is in the kuratowski 726 723 /// subdivision 727 /// 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 { 724 /// \note The \c run() had to be called with true value. 725 bool kuratowski(const Edge& edge) { 733 726 return _kuratowski[edge]; 734 727 } … … 2067 2060 /// 2068 2061 /// The planar drawing algorithm calculates positions for the nodes 2069 /// in the plane . These coordinates satisfy that if the edges are2070 /// represented with straight lines ,then they will not intersect2062 /// in the plane which coordinates satisfy that if the arcs are 2063 /// represented with straight lines then they will not intersect 2071 2064 /// each other. 2072 2065 /// 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.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. 2075 2068 /// The time complexity of the algorithm is O(n). 2076 ///2077 /// \see PlanarEmbedding2078 2069 template <typename Graph> 2079 2070 class PlanarDrawing { … … 2082 2073 TEMPLATE_GRAPH_TYPEDEFS(Graph); 2083 2074 2084 /// \brief The point type for stor ingcoordinates2075 /// \brief The point type for store coordinates 2085 2076 typedef dim2::Point<int> Point; 2086 /// \brief The map type for stor ing the coordinates of the nodes2077 /// \brief The map type for store coordinates 2087 2078 typedef typename Graph::template NodeMap<Point> PointMap; 2088 2079 … … 2091 2082 /// 2092 2083 /// Constructor 2093 /// \pre The graph must be simple, i.e. it should not 2094 /// contain parallel or loop arcs. 2084 /// \pre The graph should be simple, i.e. loop and parallel arc free. 2095 2085 PlanarDrawing(const Graph& graph) 2096 2086 : _graph(graph), _point_map(graph) {} … … 2377 2367 public: 2378 2368 2379 /// \brief Calculate the node positions2369 /// \brief Calculates the node positions 2380 2370 /// 2381 /// This function calculates the node positions on the plane.2382 /// \return \c true if the graph is planar.2371 /// This function calculates the node positions. 2372 /// \return %True if the graph is planar. 2383 2373 bool run() { 2384 2374 PlanarEmbedding<Graph> pe(_graph); … … 2389 2379 } 2390 2380 2391 /// \brief Calculate the node positions according to a2381 /// \brief Calculates the node positions according to a 2392 2382 /// combinatorical embedding 2393 2383 /// 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. 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. 2398 2387 template <typename EmbeddingMap> 2399 2388 void run(const EmbeddingMap& embedding) { … … 2435 2424 /// \brief The coordinate of the given node 2436 2425 /// 2437 /// Th is function returns the coordinate of the given node.2426 /// The coordinate of the given node. 2438 2427 Point operator[](const Node& node) const { 2439 2428 return _point_map[node]; 2440 2429 } 2441 2430 2442 /// \brief Return the grid embedding in a node map2431 /// \brief Returns the grid embedding in a \e NodeMap. 2443 2432 /// 2444 /// This function returns the grid embedding in a node map of 2445 /// \c dim2::Point<int> coordinates. 2433 /// Returns the grid embedding in a \e NodeMap of \c dim2::Point<int> . 2446 2434 const PointMap& coords() const { 2447 2435 return _point_map; … … 2483 2471 /// 2484 2472 /// The graph coloring problem is the coloring of the graph nodes 2485 /// so that there are noadjacent nodes with the same color. The2486 /// planar graphs can always be colored with four colors, whichis2487 /// proved by Appel and Haken . Their proofs provide a quadratic2473 /// that there are not adjacent nodes with the same color. The 2474 /// planar graphs can be always colored with four colors, it is 2475 /// proved by Appel and Haken and their proofs provide a quadratic 2488 2476 /// time algorithm for four coloring, but it could not be used to 2489 /// implement anefficient algorithm. The five and six coloring can be2490 /// made in linear time, but in this class ,the five coloring has2477 /// implement efficient algorithm. The five and six coloring can be 2478 /// made in linear time, but in this class the five coloring has 2491 2479 /// quadratic worst case time complexity. The two coloring (if 2492 2480 /// possible) is solvable with a graph search algorithm and it is 2493 2481 /// implemented in \ref bipartitePartitions() function in LEMON. To 2494 /// decide whether a planar graph is three colorable is NP-complete. 2482 /// decide whether the planar graph is three colorable is 2483 /// NP-complete. 2495 2484 /// 2496 2485 /// This class contains member functions for calculate colorings 2497 2486 /// with five and six colors. The six coloring algorithm is a simple 2498 2487 /// greedy coloring on the backward minimum outgoing order of nodes. 2499 /// This order can be computed by selectingthe node with least2500 /// outgoing arcs to unprocessed nodes i n each phase. This order2488 /// This order can be computed as in each phase the node with least 2489 /// outgoing arcs to unprocessed nodes is chosen. This order 2501 2490 /// guarantees that when a node is chosen for coloring it has at 2502 2491 /// most five already colored adjacents. The five coloring algorithm … … 2511 2500 TEMPLATE_GRAPH_TYPEDEFS(Graph); 2512 2501 2513 /// \brief The map type for stor ing color indices2502 /// \brief The map type for store color indexes 2514 2503 typedef typename Graph::template NodeMap<int> IndexMap; 2515 /// \brief The map type for storing colors 2516 /// 2517 /// The map type for storing colors. 2518 /// \see Palette, Color 2504 /// \brief The map type for store colors 2519 2505 typedef ComposeMap<Palette, IndexMap> ColorMap; 2520 2506 2521 2507 /// \brief Constructor 2522 2508 /// 2523 /// Constructor. 2524 /// \pre The graph must be simple, i.e. it should not 2525 /// contain parallel or loop arcs. 2509 /// Constructor 2510 /// \pre The graph should be simple, i.e. loop and parallel arc free. 2526 2511 PlanarColoring(const Graph& graph) 2527 2512 : _graph(graph), _color_map(graph), _palette(0) { … … 2534 2519 } 2535 2520 2536 /// \brief Return the node map of color indices2521 /// \brief Returns the \e NodeMap of color indexes 2537 2522 /// 2538 /// This function returns the node map of color indices. The values are2539 /// in therange \c [0..4] or \c [0..5] according to the coloring method.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 coloring method. 2540 2525 IndexMap colorIndexMap() const { 2541 2526 return _color_map; 2542 2527 } 2543 2528 2544 /// \brief Return the node map of colors2529 /// \brief Returns the \e NodeMap of colors 2545 2530 /// 2546 /// This function returns the node map of colors. The values are among2547 /// five or sixdistinct \ref lemon::Color "colors".2531 /// Returns the \e NodeMap of colors. The values are five or six 2532 /// distinct \ref lemon::Color "colors". 2548 2533 ColorMap colorMap() const { 2549 2534 return composeMap(_palette, _color_map); 2550 2535 } 2551 2536 2552 /// \brief Return the color index of the node2537 /// \brief Returns the color index of the node 2553 2538 /// 2554 /// This function returns the color index of the given node. The value is2555 /// in therange \c [0..4] or \c [0..5] according to the coloring method.2539 /// Returns the color index of the node. The values are in the 2540 /// range \c [0..4] or \c [0..5] according to the coloring method. 2556 2541 int colorIndex(const Node& node) const { 2557 2542 return _color_map[node]; 2558 2543 } 2559 2544 2560 /// \brief Return the color of the node2545 /// \brief Returns the color of the node 2561 2546 /// 2562 /// This function returns the color of the given node. The value is among2563 /// five or sixdistinct \ref lemon::Color "colors".2547 /// Returns the color of the node. The values are five or six 2548 /// distinct \ref lemon::Color "colors". 2564 2549 Color color(const Node& node) const { 2565 2550 return _palette[_color_map[node]]; … … 2567 2552 2568 2553 2569 /// \brief Calculate a coloring with at most six colors2554 /// \brief Calculates a coloring with at most six colors 2570 2555 /// 2571 2556 /// This function calculates a coloring with at most six colors. The time 2572 2557 /// complexity of this variant is linear in the size of the graph. 2573 /// \return \c true if the algorithm could color the graph with six colors.2574 /// If the algorithm fails, then the graph is notplanar.2575 /// \note This function can return \ctrue if the graph is not2576 /// planar , but it can be colored with at most sixcolors.2558 /// \return %True when the algorithm could color the graph with six color. 2559 /// If the algorithm fails, then the graph could not be planar. 2560 /// \note This function can return true if the graph is not 2561 /// planar but it can be colored with 6 colors. 2577 2562 bool runSixColoring() { 2578 2563 … … 2676 2661 public: 2677 2662 2678 /// \brief Calculate a coloring with at most five colors2663 /// \brief Calculates a coloring with at most five colors 2679 2664 /// 2680 2665 /// This function calculates a coloring with at most five 2681 2666 /// colors. The worst case time complexity of this variant is 2682 2667 /// quadratic in the size of the graph. 2683 /// \param embedding This map should contain a valid combinatorical2684 /// embedding, i.e. a valid cyclic order of the arcs.2685 /// It can be computed using PlanarEmbedding.2686 2668 template <typename EmbeddingMap> 2687 2669 void runFiveColoring(const EmbeddingMap& embedding) { … … 2730 2712 } 2731 2713 2732 /// \brief Calculate a coloring with at most five colors2714 /// \brief Calculates a coloring with at most five colors 2733 2715 /// 2734 2716 /// This function calculates a coloring with at most five 2735 2717 /// colors. The worst case time complexity of this variant is 2736 2718 /// quadratic in the size of the graph. 2737 /// \return \c true ifthe graph is planar.2719 /// \return %True when the graph is planar. 2738 2720 bool runFiveColoring() { 2739 2721 PlanarEmbedding<Graph> pe(_graph);
Note: See TracChangeset
for help on using the changeset viewer.
