COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
1 added
16 edited

Legend:

Unmodified
Added
Removed

  • INSTALL

    r615 r890  
    174174
    175175   Disable COIN-OR support.
     176
     177
     178Makefile Variables
     179==================
     180
     181Some Makefile variables are reserved by the GNU Coding Standards for
     182the use of the "user" - the person building the package. For instance,
     183CXX and CXXFLAGS are such variables, and have the same meaning as
     184explained in the previous section. These variables can be set on the
     185command line when invoking `make' like this:
     186`make [VARIABLE=VALUE]...'
     187
     188WARNINGCXXFLAGS is a non-standard Makefile variable introduced by us
     189to hold several compiler flags related to warnings. Its default value
     190can be overridden when invoking `make'. For example to disable all
     191warning flags use `make WARNINGCXXFLAGS='.
     192
     193In order to turn off a single flag from the default set of warning
     194flags, you can use the CXXFLAGS variable, since this is passed after
     195WARNINGCXXFLAGS. For example to turn off `-Wold-style-cast' (which is
     196used by default when g++ is detected) you can use
     197`make CXXFLAGS="-g -O2 -Wno-old-style-cast"'.

  • doc/CMakeLists.txt

    r791 r895  
    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

    r791 r895  
    2929        edge_biconnected_components.eps \
    3030        node_biconnected_components.eps \
     31        planar.eps \
    3132        strongly_connected_components.eps
    3233

  • lemon/bellman_ford.h

    r870 r891  
    172172  /// the lengths of the arcs. The default map type is
    173173  /// \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     174  /// \tparam TR The traits class that defines various types used by the
     175  /// algorithm. By default, it is \ref BellmanFordDefaultTraits
     176  /// "BellmanFordDefaultTraits<GR, LEN>".
     177  /// In most cases, this parameter should not be set directly,
     178  /// consider to use the named template parameters instead.
    174179#ifdef DOXYGEN
    175180  template <typename GR, typename LEN, typename TR>
    … …  
    934939  /// This class should only be used through the \ref bellmanFord()
    935940  /// function, which makes it easier to use the algorithm.
     941  ///
     942  /// \tparam TR The traits class that defines various types used by the
     943  /// algorithm.
    936944  template<class TR>
    937945  class BellmanFordWizard : public TR {

  • lemon/bfs.h

    r835 r891  
    122122  ///\tparam GR The type of the digraph the algorithm runs on.
    123123  ///The default type is \ref ListDigraph.
     124  ///\tparam TR The traits class that defines various types used by the
     125  ///algorithm. By default, it is \ref BfsDefaultTraits
     126  ///"BfsDefaultTraits<GR>".
     127  ///In most cases, this parameter should not be set directly,
     128  ///consider to use the named template parameters instead.
    124129#ifdef DOXYGEN
    125130  template <typename GR,
    … …  
    958963  /// This class should only be used through the \ref bfs() function,
    959964  /// which makes it easier to use the algorithm.
     965  ///
     966  /// \tparam TR The traits class that defines various types used by the
     967  /// algorithm.
    960968  template<class TR>
    961969  class BfsWizard : public TR
    … …  
    12961304  /// does not observe the BFS events. If you want to observe the BFS
    12971305  /// events, you should implement your own visitor class.
    1298   /// \tparam TR Traits class to set various data types used by the
    1299   /// algorithm. The default traits class is
    1300   /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<GR>".
    1301   /// See \ref BfsVisitDefaultTraits for the documentation of
    1302   /// a BFS visit traits class.
     1306  /// \tparam TR The traits class that defines various types used by the
     1307  /// algorithm. By default, it is \ref BfsVisitDefaultTraits
     1308  /// "BfsVisitDefaultTraits<GR>".
     1309  /// In most cases, this parameter should not be set directly,
     1310  /// consider to use the named template parameters instead.
    13031311#ifdef DOXYGEN
    13041312  template <typename GR, typename VS, typename TR>

  • lemon/capacity_scaling.h

    r898 r899  
    7878  /// \tparam GR The digraph type the algorithm runs on.
    7979  /// \tparam V The number type used for flow amounts, capacity bounds
    80   /// and supply values in the algorithm. By default it is \c int.
     80  /// and supply values in the algorithm. By default, it is \c int.
    8181  /// \tparam C The number type used for costs and potentials in the
    82   /// algorithm. By default it is the same as \c V.
     82  /// algorithm. By default, it is the same as \c V.
     83  /// \tparam TR The traits class that defines various types used by the
     84  /// algorithm. By default, it is \ref CapacityScalingDefaultTraits
     85  /// "CapacityScalingDefaultTraits<GR, V, C>".
     86  /// In most cases, this parameter should not be set directly,
     87  /// consider to use the named template parameters instead.
    8388  ///
    8489  /// \warning Both number types must be signed and all input data must

  • lemon/circulation.h

    r833 r891  
    174174     \tparam SM The type of the supply map. The default map type is
    175175     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
     176     \tparam TR The traits class that defines various types used by the
     177     algorithm. By default, it is \ref CirculationDefaultTraits
     178     "CirculationDefaultTraits<GR, LM, UM, SM>".
     179     In most cases, this parameter should not be set directly,
     180     consider to use the named template parameters instead.
    176181  */
    177182#ifdef DOXYGEN

  • lemon/cost_scaling.h

    r898 r899  
    105105  /// \tparam GR The digraph type the algorithm runs on.
    106106  /// \tparam V The number type used for flow amounts, capacity bounds
    107   /// and supply values in the algorithm. By default it is \c int.
     107  /// and supply values in the algorithm. By default, it is \c int.
    108108  /// \tparam C The number type used for costs and potentials in the
    109   /// algorithm. By default it is the same as \c V.
     109  /// algorithm. By default, it is the same as \c V.
     110  /// \tparam TR The traits class that defines various types used by the
     111  /// algorithm. By default, it is \ref CostScalingDefaultTraits
     112  /// "CostScalingDefaultTraits<GR, V, C>".
     113  /// In most cases, this parameter should not be set directly,
     114  /// consider to use the named template parameters instead.
    110115  ///
    111116  /// \warning Both number types must be signed and all input data must
    … …  
    137142    ///
    138143    /// The large cost type used for internal computations.
    139     /// Using the \ref CostScalingDefaultTraits "default traits class",
    140     /// it is \c long \c long if the \c Cost type is integer,
     144    /// By default, it is \c long \c long if the \c Cost type is integer,
    141145    /// otherwise it is \c double.
    142146    typedef typename TR::LargeCost LargeCost;

  • lemon/dfs.h

    r835 r891  
    122122  ///\tparam GR The type of the digraph the algorithm runs on.
    123123  ///The default type is \ref ListDigraph.
     124  ///\tparam TR The traits class that defines various types used by the
     125  ///algorithm. By default, it is \ref DfsDefaultTraits
     126  ///"DfsDefaultTraits<GR>".
     127  ///In most cases, this parameter should not be set directly,
     128  ///consider to use the named template parameters instead.
    124129#ifdef DOXYGEN
    125130  template <typename GR,
    … …  
    888893  /// This class should only be used through the \ref dfs() function,
    889894  /// which makes it easier to use the algorithm.
     895  ///
     896  /// \tparam TR The traits class that defines various types used by the
     897  /// algorithm.
    890898  template<class TR>
    891899  class DfsWizard : public TR
    … …  
    12381246  /// does not observe the DFS events. If you want to observe the DFS
    12391247  /// events, you should implement your own visitor class.
    1240   /// \tparam TR Traits class to set various data types used by the
    1241   /// algorithm. The default traits class is
    1242   /// \ref DfsVisitDefaultTraits "DfsVisitDefaultTraits<GR>".
    1243   /// See \ref DfsVisitDefaultTraits for the documentation of
    1244   /// a DFS visit traits class.
     1248  /// \tparam TR The traits class that defines various types used by the
     1249  /// algorithm. By default, it is \ref DfsVisitDefaultTraits
     1250  /// "DfsVisitDefaultTraits<GR>".
     1251  /// In most cases, this parameter should not be set directly,
     1252  /// consider to use the named template parameters instead.
    12451253#ifdef DOXYGEN
    12461254  template <typename GR, typename VS, typename TR>

  • lemon/dijkstra.h

    r835 r891  
    193193  ///it is necessary. The default map type is \ref
    194194  ///concepts::Digraph::ArcMap "GR::ArcMap<int>".
     195  ///\tparam TR The traits class that defines various types used by the
     196  ///algorithm. By default, it is \ref DijkstraDefaultTraits
     197  ///"DijkstraDefaultTraits<GR, LEN>".
     198  ///In most cases, this parameter should not be set directly,
     199  ///consider to use the named template parameters instead.
    195200#ifdef DOXYGEN
    196201  template <typename GR, typename LEN, typename TR>
    … …  
    10931098  /// This class should only be used through the \ref dijkstra() function,
    10941099  /// which makes it easier to use the algorithm.
     1100  ///
     1101  /// \tparam TR The traits class that defines various types used by the
     1102  /// algorithm.
    10951103  template<class TR>
    10961104  class DijkstraWizard : public TR

  • lemon/hartmann_orlin.h

    r859 r891  
    107107  /// \tparam LEN The type of the length map. The default
    108108  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     109  /// \tparam TR The traits class that defines various types used by the
     110  /// algorithm. By default, it is \ref HartmannOrlinDefaultTraits
     111  /// "HartmannOrlinDefaultTraits<GR, LEN>".
     112  /// In most cases, this parameter should not be set directly,
     113  /// consider to use the named template parameters instead.
    109114#ifdef DOXYGEN
    110115  template <typename GR, typename LEN, typename TR>
    … …  
    128133    ///
    129134    /// The large value type used for internal computations.
    130     /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
    131     /// it is \c long \c long if the \c Value type is integer,
     135    /// By default, it is \c long \c long if the \c Value type is integer,
    132136    /// otherwise it is \c double.
    133137    typedef typename TR::LargeValue LargeValue;

  • lemon/howard.h

    r818 r891  
    107107  /// \tparam LEN The type of the length map. The default
    108108  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     109  /// \tparam TR The traits class that defines various types used by the
     110  /// algorithm. By default, it is \ref HowardDefaultTraits
     111  /// "HowardDefaultTraits<GR, LEN>".
     112  /// In most cases, this parameter should not be set directly,
     113  /// consider to use the named template parameters instead.
    109114#ifdef DOXYGEN
    110115  template <typename GR, typename LEN, typename TR>
    … …  
    128133    ///
    129134    /// The large value type used for internal computations.
    130     /// Using the \ref HowardDefaultTraits "default traits class",
    131     /// it is \c long \c long if the \c Value type is integer,
     135    /// By default, it is \c long \c long if the \c Value type is integer,
    132136    /// otherwise it is \c double.
    133137    typedef typename TR::LargeValue LargeValue;

  • lemon/karp.h

    r819 r891  
    105105  /// \tparam LEN The type of the length map. The default
    106106  /// map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     107  /// \tparam TR The traits class that defines various types used by the
     108  /// algorithm. By default, it is \ref KarpDefaultTraits
     109  /// "KarpDefaultTraits<GR, LEN>".
     110  /// In most cases, this parameter should not be set directly,
     111  /// consider to use the named template parameters instead.
    107112#ifdef DOXYGEN
    108113  template <typename GR, typename LEN, typename TR>
    … …  
    126131    ///
    127132    /// The large value type used for internal computations.
    128     /// Using the \ref KarpDefaultTraits "default traits class",
    129     /// it is \c long \c long if the \c Value type is integer,
     133    /// By default, it is \c long \c long if the \c Value type is integer,
    130134    /// otherwise it is \c double.
    131135    typedef typename TR::LargeValue LargeValue;

  • lemon/min_cost_arborescence.h

    r760 r891  
    113113  /// it is necessary. The default map type is \ref
    114114  /// concepts::Digraph::ArcMap "Digraph::ArcMap<int>".
    115   /// \param TR Traits class to set various data types used
    116   /// by the algorithm. The default traits class is
    117   /// \ref MinCostArborescenceDefaultTraits
     115  /// \tparam TR The traits class that defines various types used by the
     116  /// algorithm. By default, it is \ref MinCostArborescenceDefaultTraits
    118117  /// "MinCostArborescenceDefaultTraits<GR, CM>".
     118  /// In most cases, this parameter should not be set directly,
     119  /// consider to use the named template parameters instead.
    119120#ifndef DOXYGEN
    120121  template <typename GR,
    … …  
    123124              MinCostArborescenceDefaultTraits<GR, CM> >
    124125#else
    125   template <typename GR, typename CM, typedef TR>
     126  template <typename GR, typename CM, typename TR>
    126127#endif
    127128  class MinCostArborescence {

  • 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);

  • lemon/preflow.h

    r889 r891  
    120120  /// \tparam CAP The type of the capacity map. The default map
    121121  /// type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
     122  /// \tparam TR The traits class that defines various types used by the
     123  /// algorithm. By default, it is \ref PreflowDefaultTraits
     124  /// "PreflowDefaultTraits<GR, CAP>".
     125  /// In most cases, this parameter should not be set directly,
     126  /// consider to use the named template parameters instead.
    122127#ifdef DOXYGEN
    123128  template <typename GR, typename CAP, typename TR>
Note: See TracChangeset for help on using the changeset viewer.