COIN-OR::LEMON - Graph Library

Changes in / [826:02109e17027f:829:7762cab7f372] in lemon-main


Ignore:
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • doc/CMakeLists.txt

    r744 r827  
    2727    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps
    2828    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.eps
    2930    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    3031    COMMAND ${CMAKE_COMMAND} -E remove_directory html
  • doc/Makefile.am

    r744 r827  
    2929        edge_biconnected_components.eps \
    3030        node_biconnected_components.eps \
     31        planar.eps \
    3132        strongly_connected_components.eps
    3233
  • lemon/planarity.h

    r798 r828  
    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.