COIN-OR::LEMON - Graph Library

Changeset 896:5fd7fafc4470 in lemon


Ignore:
Timestamp:
02/11/10 07:40:29 (9 years ago)
Author:
Peter Kovacs <kpeter@…>
Branch:
default
Message:

Doc improvements for planarity related tools (#62)

File:
1 edited

Legend:

Unmodified
Added
Removed
  • lemon/planarity.h

    r862 r896  
    519519  /// 
    520520  /// 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 
    522522  /// 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. 
    524524  template <typename GR> 
    525525  bool checkPlanarity(const GR& graph) { 
     
    533533  /// 
    534534  /// 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 
    536536  /// ordering of the outgoing edges of the nodes, which is a possible 
    537537  /// 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 
    539   /// with 5 nodes) or a \f$ K_{3,3} \f$ (complete bipartite graph on 
    540   /// 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. 
    541541  /// 
    542542  /// 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() 
    545546  template <typename Graph> 
    546547  class PlanarEmbedding { 
     
    592593  public: 
    593594 
    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() 
    595599    typedef typename Graph::template ArcMap<Arc> EmbeddingMap; 
    596600 
    597601    /// \brief Constructor 
    598602    /// 
    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. 
    601606    PlanarEmbedding(const Graph& graph) 
    602607      : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {} 
    603608 
    604     /// \brief Runs the algorithm. 
     609    /// \brief Run the algorithm. 
    605610    /// 
    606     /// Runs the algorithm. 
    607     /// \param kuratowski If the parameter is false, then the 
     611    /// This function runs the algorithm. 
     612    /// \param kuratowski If this parameter is set to \c false, then the 
    608613    /// algorithm does not compute a Kuratowski subdivision. 
    609     ///\return %True when the graph is planar. 
     614    /// \return \c true if the graph is planar. 
    610615    bool run(bool kuratowski = true) { 
    611616      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor; 
     
    700705    } 
    701706 
    702     /// \brief Gives back the successor of an arc 
     707    /// \brief Give back the successor of an arc 
    703708    /// 
    704     /// Gives back the successor of an arc. This function makes 
     709    /// This function gives back the successor of an arc. It makes 
    705710    /// possible to query the cyclic order of the outgoing arcs from 
    706711    /// a node. 
     
    709714    } 
    710715 
    711     /// \brief Gives back the calculated embedding map 
     716    /// \brief Give back the calculated embedding map 
    712717    /// 
    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. 
    715721    const EmbeddingMap& embeddingMap() const { 
    716722      return _embedding; 
    717723    } 
    718724 
    719     /// \brief Gives back true if the undirected arc is in the 
    720     /// kuratowski subdivision 
     725    /// \brief Give back \c true if the given edge is in the Kuratowski 
     726    /// subdivision 
    721727    /// 
    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 { 
    726733      return _kuratowski[edge]; 
    727734    } 
     
    20602067  /// 
    20612068  /// The planar drawing algorithm calculates positions for the nodes 
    2062   /// in the plane which coordinates satisfy that if the arcs are 
    2063   /// represented with straight lines then they will not intersect 
     2069  /// in the plane. These coordinates satisfy that if the edges are 
     2070  /// represented with straight lines, then they will not intersect 
    20642071  /// each other. 
    20652072  /// 
    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. 
    20682075  /// The time complexity of the algorithm is O(n). 
     2076  /// 
     2077  /// \see PlanarEmbedding 
    20692078  template <typename Graph> 
    20702079  class PlanarDrawing { 
     
    20732082    TEMPLATE_GRAPH_TYPEDEFS(Graph); 
    20742083 
    2075     /// \brief The point type for store coordinates 
     2084    /// \brief The point type for storing coordinates 
    20762085    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 
    20782087    typedef typename Graph::template NodeMap<Point> PointMap; 
    20792088 
     
    20822091    /// 
    20832092    /// 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. 
    20852095    PlanarDrawing(const Graph& graph) 
    20862096      : _graph(graph), _point_map(graph) {} 
     
    23672377  public: 
    23682378 
    2369     /// \brief Calculates the node positions 
     2379    /// \brief Calculate the node positions 
    23702380    /// 
    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. 
    23732383    bool run() { 
    23742384      PlanarEmbedding<Graph> pe(_graph); 
     
    23792389    } 
    23802390 
    2381     /// \brief Calculates the node positions according to a 
     2391    /// \brief Calculate the node positions according to a 
    23822392    /// combinatorical embedding 
    23832393    /// 
    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. 
    23872398    template <typename EmbeddingMap> 
    23882399    void run(const EmbeddingMap& embedding) { 
     
    24242435    /// \brief The coordinate of the given node 
    24252436    /// 
    2426     /// The coordinate of the given node. 
     2437    /// This function returns the coordinate of the given node. 
    24272438    Point operator[](const Node& node) const { 
    24282439      return _point_map[node]; 
    24292440    } 
    24302441 
    2431     /// \brief Returns the grid embedding in a \e NodeMap. 
     2442    /// \brief Return the grid embedding in a node map 
    24322443    /// 
    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. 
    24342446    const PointMap& coords() const { 
    24352447      return _point_map; 
     
    24712483  /// 
    24722484  /// The graph coloring problem is the coloring of the graph nodes 
    2473   /// 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 
     2485  /// 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 
    24762488  /// time algorithm for four coloring, but it could not be used to 
    2477   /// implement efficient algorithm. The five and six coloring can be 
    2478   /// made in linear time, but in this class the five coloring has 
     2489  /// implement an efficient algorithm. The five and six coloring can be 
     2490  /// made in linear time, but in this class, the five coloring has 
    24792491  /// quadratic worst case time complexity. The two coloring (if 
    24802492  /// possible) is solvable with a graph search algorithm and it is 
    24812493  /// 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. 
    24842495  /// 
    24852496  /// This class contains member functions for calculate colorings 
    24862497  /// with five and six colors. The six coloring algorithm is a simple 
    24872498  /// greedy coloring on the backward minimum outgoing order of nodes. 
    2488   /// This order can be computed as in each phase the node with least 
    2489   /// outgoing arcs to unprocessed nodes is chosen. This order 
     2499  /// This order can be computed by selecting the node with least 
     2500  /// outgoing arcs to unprocessed nodes in each phase. This order 
    24902501  /// guarantees that when a node is chosen for coloring it has at 
    24912502  /// most five already colored adjacents. The five coloring algorithm 
     
    25002511    TEMPLATE_GRAPH_TYPEDEFS(Graph); 
    25012512 
    2502     /// \brief The map type for store color indexes 
     2513    /// \brief The map type for storing color indices 
    25032514    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 
    25052519    typedef ComposeMap<Palette, IndexMap> ColorMap; 
    25062520 
    25072521    /// \brief Constructor 
    25082522    /// 
    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. 
    25112526    PlanarColoring(const Graph& graph) 
    25122527      : _graph(graph), _color_map(graph), _palette(0) { 
     
    25192534    } 
    25202535 
    2521     /// \brief Returns the \e NodeMap of color indexes 
     2536    /// \brief Return the node map of color indices 
    25222537    /// 
    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. 
     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. 
    25252540    IndexMap colorIndexMap() const { 
    25262541      return _color_map; 
    25272542    } 
    25282543 
    2529     /// \brief Returns the \e NodeMap of colors 
     2544    /// \brief Return the node map of colors 
    25302545    /// 
    2531     /// Returns the \e NodeMap of colors. The values are five or six 
    2532     /// 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". 
    25332548    ColorMap colorMap() const { 
    25342549      return composeMap(_palette, _color_map); 
    25352550    } 
    25362551 
    2537     /// \brief Returns the color index of the node 
     2552    /// \brief Return the color index of the node 
    25382553    /// 
    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. 
     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. 
    25412556    int colorIndex(const Node& node) const { 
    25422557      return _color_map[node]; 
    25432558    } 
    25442559 
    2545     /// \brief Returns the color of the node 
     2560    /// \brief Return the color of the node 
    25462561    /// 
    2547     /// Returns the color of the node. The values are five or six 
    2548     /// 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". 
    25492564    Color color(const Node& node) const { 
    25502565      return _palette[_color_map[node]]; 
     
    25522567 
    25532568 
    2554     /// \brief Calculates a coloring with at most six colors 
     2569    /// \brief Calculate a coloring with at most six colors 
    25552570    /// 
    25562571    /// This function calculates a coloring with at most six colors. The time 
    25572572    /// 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 be planar. 
    2560     /// \note This function can return true if the graph is not 
    2561     /// planar but it can be colored with 6 colors. 
     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. 
    25622577    bool runSixColoring() { 
    25632578 
     
    26612676  public: 
    26622677 
    2663     /// \brief Calculates a coloring with at most five colors 
     2678    /// \brief Calculate a coloring with at most five colors 
    26642679    /// 
    26652680    /// This function calculates a coloring with at most five 
    26662681    /// colors. The worst case time complexity of this variant is 
    26672682    /// 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. 
    26682686    template <typename EmbeddingMap> 
    26692687    void runFiveColoring(const EmbeddingMap& embedding) { 
     
    27122730    } 
    27132731 
    2714     /// \brief Calculates a coloring with at most five colors 
     2732    /// \brief Calculate a coloring with at most five colors 
    27152733    /// 
    27162734    /// This function calculates a coloring with at most five 
    27172735    /// colors. The worst case time complexity of this variant is 
    27182736    /// quadratic in the size of the graph. 
    2719     /// \return %True when the graph is planar. 
     2737    /// \return \c true if the graph is planar. 
    27202738    bool runFiveColoring() { 
    27212739      PlanarEmbedding<Graph> pe(_graph); 
Note: See TracChangeset for help on using the changeset viewer.