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 deleted
16 edited

Legend:

Unmodified
Added
Removed

  • INSTALL

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

  • doc/CMakeLists.txt

    r895 r791  
    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
    3029    COMMAND ${GHOSTSCRIPT_EXECUTABLE} ${GHOSTSCRIPT_OPTIONS} -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps
    3130    COMMAND ${CMAKE_COMMAND} -E remove_directory html

  • doc/Makefile.am

    r895 r791  
    2929        edge_biconnected_components.eps \
    3030        node_biconnected_components.eps \
    31         planar.eps \
    3231        strongly_connected_components.eps
    3332

  • lemon/bellman_ford.h

    r891 r870  
    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.
    179174#ifdef DOXYGEN
    180175  template <typename GR, typename LEN, typename TR>
    … …  
    939934  /// This class should only be used through the \ref bellmanFord()
    940935  /// 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.
    944936  template<class TR>
    945937  class BellmanFordWizard : public TR {

  • lemon/bfs.h

    r891 r835  
    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.
    129124#ifdef DOXYGEN
    130125  template <typename GR,
    … …  
    963958  /// This class should only be used through the \ref bfs() function,
    964959  /// which makes it easier to use the algorithm.
    965   ///
    966   /// \tparam TR The traits class that defines various types used by the
    967   /// algorithm.
    968960  template<class TR>
    969961  class BfsWizard : public TR
    … …  
    13041296  /// does not observe the BFS events. If you want to observe the BFS
    13051297  /// events, you should implement your own visitor 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.
     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.
    13111303#ifdef DOXYGEN
    13121304  template <typename GR, typename VS, typename TR>

  • lemon/capacity_scaling.h

    r899 r898  
    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.
    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.
     82  /// algorithm. By default it is the same as \c V.
    8883  ///
    8984  /// \warning Both number types must be signed and all input data must

  • lemon/circulation.h

    r891 r833  
    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.
    181176  */
    182177#ifdef DOXYGEN

  • lemon/cost_scaling.h

    r899 r898  
    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.
    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.
     109  /// algorithm. By default it is the same as \c V.
    115110  ///
    116111  /// \warning Both number types must be signed and all input data must
    … …  
    142137    ///
    143138    /// The large cost type used for internal computations.
    144     /// By default, it is \c long \c long if the \c Cost type is integer,
     139    /// Using the \ref CostScalingDefaultTraits "default traits class",
     140    /// it is \c long \c long if the \c Cost type is integer,
    145141    /// otherwise it is \c double.
    146142    typedef typename TR::LargeCost LargeCost;

  • lemon/dfs.h

    r891 r835  
    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.
    129124#ifdef DOXYGEN
    130125  template <typename GR,
    … …  
    893888  /// This class should only be used through the \ref dfs() function,
    894889  /// which makes it easier to use the algorithm.
    895   ///
    896   /// \tparam TR The traits class that defines various types used by the
    897   /// algorithm.
    898890  template<class TR>
    899891  class DfsWizard : public TR
    … …  
    12461238  /// does not observe the DFS events. If you want to observe the DFS
    12471239  /// events, you should implement your own visitor 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.
     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.
    12531245#ifdef DOXYGEN
    12541246  template <typename GR, typename VS, typename TR>

  • lemon/dijkstra.h

    r891 r835  
    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.
    200195#ifdef DOXYGEN
    201196  template <typename GR, typename LEN, typename TR>
    … …  
    10981093  /// This class should only be used through the \ref dijkstra() function,
    10991094  /// which makes it easier to use the algorithm.
    1100   ///
    1101   /// \tparam TR The traits class that defines various types used by the
    1102   /// algorithm.
    11031095  template<class TR>
    11041096  class DijkstraWizard : public TR

  • lemon/hartmann_orlin.h

    r891 r859  
    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.
    114109#ifdef DOXYGEN
    115110  template <typename GR, typename LEN, typename TR>
    … …  
    133128    ///
    134129    /// The large value type used for internal computations.
    135     /// By default, it is \c long \c long if the \c Value type is integer,
     130    /// Using the \ref HartmannOrlinDefaultTraits "default traits class",
     131    /// it is \c long \c long if the \c Value type is integer,
    136132    /// otherwise it is \c double.
    137133    typedef typename TR::LargeValue LargeValue;

  • lemon/howard.h

    r891 r818  
    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.
    114109#ifdef DOXYGEN
    115110  template <typename GR, typename LEN, typename TR>
    … …  
    133128    ///
    134129    /// The large value type used for internal computations.
    135     /// By default, it is \c long \c long if the \c Value type is integer,
     130    /// Using the \ref HowardDefaultTraits "default traits class",
     131    /// it is \c long \c long if the \c Value type is integer,
    136132    /// otherwise it is \c double.
    137133    typedef typename TR::LargeValue LargeValue;

  • lemon/karp.h

    r891 r819  
    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.
    112107#ifdef DOXYGEN
    113108  template <typename GR, typename LEN, typename TR>
    … …  
    131126    ///
    132127    /// The large value type used for internal computations.
    133     /// By default, it is \c long \c long if the \c Value type is integer,
     128    /// Using the \ref KarpDefaultTraits "default traits class",
     129    /// it is \c long \c long if the \c Value type is integer,
    134130    /// otherwise it is \c double.
    135131    typedef typename TR::LargeValue LargeValue;

  • lemon/min_cost_arborescence.h

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

  • lemon/planarity.h

    r896 r862  
    519519  ///
    520520  /// This function implements the Boyer-Myrvold algorithm for
    521   /// planarity checking of an undirected simple graph. It is a simplified
     521  /// planarity checking of an undirected graph. It is a simplified
    522522  /// version of the PlanarEmbedding algorithm class because neither
    523   /// the embedding nor the Kuratowski subdivisons are computed.
     523  /// the embedding nor the kuratowski subdivisons are not 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 simple graph. The planar embedding is an
     535  /// embedding of an undirected 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 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.
     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.
    541541  ///
    542542  /// 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$.
    546545  template <typename Graph>
    547546  class PlanarEmbedding {
    … …  
    593592  public:
    594593
    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
    599595    typedef typename Graph::template ArcMap<Arc> EmbeddingMap;
    600596
    601597    /// \brief Constructor
    602598    ///
    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.
    606601    PlanarEmbedding(const Graph& graph)
    607602      : _graph(graph), _embedding(_graph), _kuratowski(graph, false) {}
    608603
    609     /// \brief Run the algorithm.
     604    /// \brief Runs the algorithm.
    610605    ///
    611     /// This function runs the algorithm.
    612     /// \param kuratowski If this parameter is set to \c false, then the
     606    /// Runs the algorithm.
     607    /// \param kuratowski If the parameter is false, then the
    613608    /// algorithm does not compute a Kuratowski subdivision.
    614     /// \return \c true if the graph is planar.
     609    ///\return %True when the graph is planar.
    615610    bool run(bool kuratowski = true) {
    616611      typedef _planarity_bits::PlanarityVisitor<Graph> Visitor;
    … …  
    705700    }
    706701
    707     /// \brief Give back the successor of an arc
     702    /// \brief Gives back the successor of an arc
    708703    ///
    709     /// This function gives back the successor of an arc. It makes
     704    /// Gives back the successor of an arc. This function makes
    710705    /// possible to query the cyclic order of the outgoing arcs from
    711706    /// a node.
    … …  
    714709    }
    715710
    716     /// \brief Give back the calculated embedding map
     711    /// \brief Gives back the calculated embedding map
    717712    ///
    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.
    721715    const EmbeddingMap& embeddingMap() const {
    722716      return _embedding;
    723717    }
    724718
    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
    726723    /// 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) {
    733726      return _kuratowski[edge];
    734727    }
    … …  
    20672060  ///
    20682061  /// The planar drawing algorithm calculates positions for the nodes
    2069   /// in the plane. These coordinates satisfy that if the edges are
    2070   /// represented with straight lines, then they will not intersect
     2062  /// in the plane which coordinates satisfy that if the arcs are
     2063  /// represented with straight lines then they will not intersect
    20712064  /// each other.
    20722065  ///
    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.
    20752068  /// The time complexity of the algorithm is O(n).
    2076   ///
    2077   /// \see PlanarEmbedding
    20782069  template <typename Graph>
    20792070  class PlanarDrawing {
    … …  
    20822073    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    20832074
    2084     /// \brief The point type for storing coordinates
     2075    /// \brief The point type for store coordinates
    20852076    typedef dim2::Point<int> Point;
    2086     /// \brief The map type for storing the coordinates of the nodes
     2077    /// \brief The map type for store coordinates
    20872078    typedef typename Graph::template NodeMap<Point> PointMap;
    20882079
    … …  
    20912082    ///
    20922083    /// 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.
    20952085    PlanarDrawing(const Graph& graph)
    20962086      : _graph(graph), _point_map(graph) {}
    … …  
    23772367  public:
    23782368
    2379     /// \brief Calculate the node positions
     2369    /// \brief Calculates the node positions
    23802370    ///
    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.
    23832373    bool run() {
    23842374      PlanarEmbedding<Graph> pe(_graph);
    … …  
    23892379    }
    23902380
    2391     /// \brief Calculate the node positions according to a
     2381    /// \brief Calculates the node positions according to a
    23922382    /// combinatorical embedding
    23932383    ///
    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.
    23982387    template <typename EmbeddingMap>
    23992388    void run(const EmbeddingMap& embedding) {
    … …  
    24352424    /// \brief The coordinate of the given node
    24362425    ///
    2437     /// This function returns the coordinate of the given node.
     2426    /// The coordinate of the given node.
    24382427    Point operator[](const Node& node) const {
    24392428      return _point_map[node];
    24402429    }
    24412430
    2442     /// \brief Return the grid embedding in a node map
     2431    /// \brief Returns the grid embedding in a \e NodeMap.
    24432432    ///
    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> .
    24462434    const PointMap& coords() const {
    24472435      return _point_map;
    … …  
    24832471  ///
    24842472  /// The graph coloring problem is the coloring of the graph nodes
    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
     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
    24882476  /// time algorithm for four coloring, but it could not be used to
    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
     2477  /// implement efficient algorithm. The five and six coloring can be
     2478  /// made in linear time, but in this class the five coloring has
    24912479  /// quadratic worst case time complexity. The two coloring (if
    24922480  /// possible) is solvable with a graph search algorithm and it is
    24932481  /// 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.
    24952484  ///
    24962485  /// This class contains member functions for calculate colorings
    24972486  /// with five and six colors. The six coloring algorithm is a simple
    24982487  /// greedy coloring on the backward minimum outgoing order of nodes.
    2499   /// This order can be computed by selecting the node with least
    2500   /// outgoing arcs to unprocessed nodes in each phase. This order
     2488  /// This order can be computed as in each phase the node with least
     2489  /// outgoing arcs to unprocessed nodes is chosen. This order
    25012490  /// guarantees that when a node is chosen for coloring it has at
    25022491  /// most five already colored adjacents. The five coloring algorithm
    … …  
    25112500    TEMPLATE_GRAPH_TYPEDEFS(Graph);
    25122501
    2513     /// \brief The map type for storing color indices
     2502    /// \brief The map type for store color indexes
    25142503    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
    25192505    typedef ComposeMap<Palette, IndexMap> ColorMap;
    25202506
    25212507    /// \brief Constructor
    25222508    ///
    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.
    25262511    PlanarColoring(const Graph& graph)
    25272512      : _graph(graph), _color_map(graph), _palette(0) {
    … …  
    25342519    }
    25352520
    2536     /// \brief Return the node map of color indices
     2521    /// \brief Returns the \e NodeMap of color indexes
    25372522    ///
    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.
     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.
    25402525    IndexMap colorIndexMap() const {
    25412526      return _color_map;
    25422527    }
    25432528
    2544     /// \brief Return the node map of colors
     2529    /// \brief Returns the \e NodeMap of colors
    25452530    ///
    2546     /// This function returns the node map of colors. The values are among
    2547     /// five or six distinct \ref lemon::Color "colors".
     2531    /// Returns the \e NodeMap of colors. The values are five or six
     2532    /// distinct \ref lemon::Color "colors".
    25482533    ColorMap colorMap() const {
    25492534      return composeMap(_palette, _color_map);
    25502535    }
    25512536
    2552     /// \brief Return the color index of the node
     2537    /// \brief Returns the color index of the node
    25532538    ///
    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.
     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.
    25562541    int colorIndex(const Node& node) const {
    25572542      return _color_map[node];
    25582543    }
    25592544
    2560     /// \brief Return the color of the node
     2545    /// \brief Returns the color of the node
    25612546    ///
    2562     /// This function returns the color of the given node. The value is among
    2563     /// five or six distinct \ref lemon::Color "colors".
     2547    /// Returns the color of the node. The values are five or six
     2548    /// distinct \ref lemon::Color "colors".
    25642549    Color color(const Node& node) const {
    25652550      return _palette[_color_map[node]];
    … …  
    25672552
    25682553
    2569     /// \brief Calculate a coloring with at most six colors
     2554    /// \brief Calculates a coloring with at most six colors
    25702555    ///
    25712556    /// This function calculates a coloring with at most six colors. The time
    25722557    /// 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 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.
     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.
    25772562    bool runSixColoring() {
    25782563
    … …  
    26762661  public:
    26772662
    2678     /// \brief Calculate a coloring with at most five colors
     2663    /// \brief Calculates a coloring with at most five colors
    26792664    ///
    26802665    /// This function calculates a coloring with at most five
    26812666    /// colors. The worst case time complexity of this variant is
    26822667    /// 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.
    26862668    template <typename EmbeddingMap>
    26872669    void runFiveColoring(const EmbeddingMap& embedding) {
    … …  
    27302712    }
    27312713
    2732     /// \brief Calculate a coloring with at most five colors
     2714    /// \brief Calculates a coloring with at most five colors
    27332715    ///
    27342716    /// This function calculates a coloring with at most five
    27352717    /// colors. The worst case time complexity of this variant is
    27362718    /// quadratic in the size of the graph.
    2737     /// \return \c true if the graph is planar.
     2719    /// \return %True when the graph is planar.
    27382720    bool runFiveColoring() {
    27392721      PlanarEmbedding<Graph> pe(_graph);

  • lemon/preflow.h

    r891 r889  
    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.
    127122#ifdef DOXYGEN
    128123  template <typename GR, typename CAP, typename TR>
Note: See TracChangeset for help on using the changeset viewer.