COIN-OR::LEMON - Graph Library

Changes in / [206:4e22275a2b52:207:574b963d0275] in lemon-main


Ignore:
Files:
1 added
1 deleted
14 edited

Legend:

Unmodified
Added
Removed
  • demo/arg_parser_demo.cc

    r137 r204  
    3030int main(int argc, const char **argv)
    3131{
    32   ArgParser ap(argc,argv);
     32  // Initialize the argument parser
     33  ArgParser ap(argc, argv);
    3334  int i;
    3435  std::string s;
    35   double d;
    36   bool b,sil;
    37   bool g1,g2,g3;
    38   ap.refOption("n", "An integer input.", i, true)
    39     .refOption("val", "A double input.", d)
    40     .doubleOption("val2", "A double input.", d)
    41     .synonym("vals","val")
    42     .refOption("name", "A string input.", s)
    43     .refOption("f", "A switch.", b)
    44     .refOption("nohelp", "", sil)
    45     .refOption("gra","Choice A",g1)
    46     .refOption("grb","Choice B",g2)
    47     .refOption("grc","Choice C",g3)
    48     .optionGroup("gr","gra")
    49     .optionGroup("gr","grb")
    50     .optionGroup("gr","grc")
    51     .mandatoryGroup("gr")
    52     .onlyOneGroup("gr")
    53     .other("infile","The input file.")
     36  double d = 1.0;
     37  bool b, nh;
     38  bool g1, g2, g3;
     39
     40  // Add a mandatory integer option with storage reference
     41  ap.refOption("n", "An integer input.", i, true);
     42  // Add a double option with storage reference (the default value is 1.0)
     43  ap.refOption("val", "A double input.", d);
     44  // Add a double option without storage reference (the default value is 3.14)
     45  ap.doubleOption("val2", "A double input.", 3.14);
     46  // Set synonym for -val option
     47  ap.synonym("vals", "val");
     48  // Add a string option
     49  ap.refOption("name", "A string input.", s);
     50  // Add bool options
     51  ap.refOption("f", "A switch.", b)
     52    .refOption("nohelp", "", nh)
     53    .refOption("gra", "Choice A", g1)
     54    .refOption("grb", "Choice B", g2)
     55    .refOption("grc", "Choice C", g3);
     56  // Bundle -gr* options into a group
     57  ap.optionGroup("gr", "gra")
     58    .optionGroup("gr", "grb")
     59    .optionGroup("gr", "grc");
     60  // Set the group mandatory
     61  ap.mandatoryGroup("gr");
     62  // Set the options of the group exclusive (only one option can be given)
     63  ap.onlyOneGroup("gr");
     64  // Add non-parsed arguments (e.g. input files)
     65  ap.other("infile", "The input file.")
    5466    .other("...");
    5567 
     68  // Perform the parsing process
     69  // (in case of any error it terminates the program)
    5670  ap.parse();
    5771
     72  // Check each option if it has been given and print its value
    5873  std::cout << "Parameters of '" << ap.commandName() << "':\n";
    5974
    60   if(ap.given("n")) std::cout << "  Value of -n: " << i << std::endl;
     75  std::cout << "  Value of -n: " << i << std::endl;
    6176  if(ap.given("val")) std::cout << "  Value of -val: " << d << std::endl;
     77  if(ap.given("val2")) {
     78    d = ap["val2"];
     79    std::cout << "  Value of -val2: " << d << std::endl;
     80  }
    6281  if(ap.given("name")) std::cout << "  Value of -name: " << s << std::endl;
    6382  if(ap.given("f")) std::cout << "  -f is given\n";
    64   if(ap.given("nohelp")) std::cout << "  Value of -nohelp: " << sil << std::endl;
     83  if(ap.given("nohelp")) std::cout << "  Value of -nohelp: " << nh << std::endl;
    6584  if(ap.given("gra")) std::cout << "  -gra is given\n";
    6685  if(ap.given("grb")) std::cout << "  -grb is given\n";
    6786  if(ap.given("grc")) std::cout << "  -grc is given\n";
    68                                      
     87 
    6988  switch(ap.files().size()) {
    7089  case 0:
     
    81100    std::cout << "    '" << ap.files()[i] << "'\n";
    82101 
     102  return 0;
    83103}
  • demo/lgf_demo.cc

    r164 r193  
    2121///\brief Demonstrating graph input and output
    2222///
    23 /// This program gives an example of how to load a directed graph from
    24 /// an \ref lgf-format "LGF" file with the \ref lemon::DigraphReader
    25 /// "DigraphReader" class.
     23/// This program gives an example of how to read and write a digraph
     24/// and additional maps from/to a stream or a file using the
     25/// \ref lgf-format "LGF" format.
    2626///
    2727/// The \c "digraph.lgf" file:
    2828/// \include digraph.lgf
    2929///
    30 /// And the program which reads it:
     30/// And the program which reads it and prints the digraph to the
     31/// standard output:
    3132/// \include lgf_demo.cc
    3233
     
    3536#include <lemon/lgf_reader.h>
    3637#include <lemon/lgf_writer.h>
    37 #include <lemon/random.h>
    38 
    3938
    4039using namespace lemon;
     
    4443  SmartDigraph::ArcMap<int> cap(g);
    4544  SmartDigraph::Node s, t;
     45 
     46  try {
     47    digraphReader("digraph.lgf", g). // read the directed graph into g
     48      arcMap("capacity", cap).       // read the 'capacity' arc map into cap
     49      node("source", s).             // read 'source' node to s
     50      node("target", t).             // read 'target' node to t
     51      run();
     52  } catch (DataFormatError& error) { // check if there was any error
     53    std::cerr << "Error: " << error.what() << std::endl;
     54    return -1;
     55  }
    4656
    47   digraphReader("digraph.lgf", g). // read the directeg graph into g
    48     arcMap("capacity", cap).       // read the 'capacity' arc map into cap
    49     node("source", s).             // read 'source' node to s
    50     node("target", t).             // read 'target' node to t
    51     run();
    52 
    53   std::cout << "Digraph read from 'digraph.lgf'" << std::endl;
     57  std::cout << "A digraph is read from 'digraph.lgf'." << std::endl;
    5458  std::cout << "Number of nodes: " << countNodes(g) << std::endl;
    5559  std::cout << "Number of arcs: " << countArcs(g) << std::endl;
  • doc/groups.dox

    r156 r192  
    476476@defgroup lemon_io Lemon Input-Output
    477477@ingroup io_group
    478 \brief Reading and writing LEMON format
    479 
    480 This group describes methods for reading and writing LEMON format.
    481 You can find more about this format on the \ref graph-io-page "Graph Input-Output"
    482 tutorial pages.
     478\brief Reading and writing \ref lgf-format "Lemon Graph Format".
     479
     480This group describes methods for reading and writing \ref lgf-format "Lemon Graph Format".
    483481*/
    484482
  • doc/lgf.dox

    r162 r201  
    4747
    4848The \c \@nodes section describes a set of nodes and associated
    49 maps. The first is a header line, it columns are the names of the
     49maps. The first is a header line, its columns are the names of the
    5050maps appearing in the following lines.
    5151One of the maps must be called \c
     
    6565
    6666The \c \@arcs section is very similar to the \c \@nodes section,
    67 it again starts with a header line describing the names of the arc,
     67it again starts with a header line describing the names of the maps,
    6868but the \c "label" map is not obligatory here. The following lines
    6969describe the arcs. The first two tokens of each line are
     
    7979\endcode
    8080
    81 The \c \@edges is just a synonym of \c \@arcs.
     81The \c \@edges is just a synonym of \c \@arcs. The @arcs section can
     82also store the edge set of an undirected graph. In such case there is
     83a conventional method for store arc maps in the file, if two columns
     84has the same caption with \c '+' and \c '-' prefix, then these columns
     85can be regarded as the values of an arc map.
    8286
    8387The \c \@attributes section contains key-value pairs, each line
    84 consists of two tokens, an attribute name, and then an attribute value.
     88consists of two tokens, an attribute name, and then an attribute
     89value. The value of the attribute could be also a label value of a
     90node or an edge, or even an edge label prefixed with \c '+' or \c '-',
     91which regards to the forward or backward directed arc of the
     92corresponding edge.
    8593
    8694\code
  • lemon/Makefile.am

    r166 r195  
    3333        lemon/kruskal.h \
    3434        lemon/lgf_reader.h \
     35        lemon/lgf_writer.h \
    3536        lemon/list_graph.h \
    3637        lemon/maps.h \
     
    6061        lemon/concepts/digraph.h \
    6162        lemon/concepts/graph.h \
     63        lemon/concepts/graph_components.h \
    6264        lemon/concepts/heap.h \
    6365        lemon/concepts/maps.h \
    64         lemon/concepts/path.h \
    65         lemon/concepts/graph_components.h
     66        lemon/concepts/path.h
  • lemon/arg_parser.h

    r108 r204  
    119119  public:
    120120
    121     ///\e
     121    ///Constructor
    122122    ArgParser(int argc, const char **argv);
    123123
    124124    ~ArgParser();
    125125
     126    ///\name Options
     127    ///
     128
     129    ///@{
     130
    126131    ///Add a new integer type option
    127132
     133    ///Add a new integer type option.
    128134    ///\param name The name of the option. The leading '-' must be omitted.
    129135    ///\param help A help string.
     
    136142    ///Add a new floating point type option
    137143
     144    ///Add a new floating point type option.
    138145    ///\param name The name of the option. The leading '-' must be omitted.
    139146    ///\param help A help string.
     
    146153    ///Add a new bool type option
    147154
     155    ///Add a new bool type option.
    148156    ///\param name The name of the option. The leading '-' must be omitted.
    149157    ///\param help A help string.
     
    157165    ///Add a new string type option
    158166
     167    ///Add a new string type option.
    159168    ///\param name The name of the option. The leading '-' must be omitted.
    160169    ///\param help A help string.
     
    165174                      std::string value="", bool obl=false);
    166175
    167     ///\name Options with external storage
     176    ///Give help string for non-parsed arguments.
     177
     178    ///With this function you can give help string for non-parsed arguments.
     179    ///The parameter \c name will be printed in the short usage line, while
     180    ///\c help gives a more detailed description.
     181    ArgParser &other(const std::string &name,
     182                     const std::string &help="");
     183   
     184    ///@}
     185
     186    ///\name Options with External Storage
    168187    ///Using this functions, the value of the option will be directly written
    169188    ///into a variable once the option appears in the command line.
     
    173192    ///Add a new integer type option with a storage reference
    174193
     194    ///Add a new integer type option with a storage reference.
    175195    ///\param name The name of the option. The leading '-' must be omitted.
    176196    ///\param help A help string.
     
    183203    ///Add a new floating type option with a storage reference
    184204
     205    ///Add a new floating type option with a storage reference.
    185206    ///\param name The name of the option. The leading '-' must be omitted.
    186207    ///\param help A help string.
     
    193214    ///Add a new bool type option with a storage reference
    194215
     216    ///Add a new bool type option with a storage reference.
    195217    ///\param name The name of the option. The leading '-' must be omitted.
    196218    ///\param help A help string.
     
    204226    ///Add a new string type option with a storage reference
    205227
     228    ///Add a new string type option with a storage reference.
    206229    ///\param name The name of the option. The leading '-' must be omitted.
    207230    ///\param help A help string.
     
    219242    ///@{
    220243
    221     ///Boundle some options into a group
     244    ///Bundle some options into a group
    222245
    223246    /// You can group some option by calling this function repeatedly for each
     
    231254
    232255    ///If you call this function for a group, than at most one of them can be
    233     ///given at the same time
     256    ///given at the same time.
    234257    ArgParser &onlyOneGroup(const std::string &group);
    235258 
     
    248271   
    249272    ///@}
    250 
    251     ///Give help string for non-parsed arguments.
    252 
    253     ///With this function you can give help string for non-parsed arguments.
    254     ///The parameter \c name will be printed in the short usage line, while
    255     ///\c help gives a more detailed description.
    256     ArgParser &other(const std::string &name,
    257                      const std::string &help="");
    258    
    259     ///Give back the non-option type arguments.
    260 
    261     ///Give back a reference to a vector consisting of the program arguments
    262     ///not starting with a '-' character.
    263     std::vector<std::string> &files() { return _file_args; }
    264 
    265     ///Give back the command name (the 0th argument)
    266     const std::string &commandName() { return _command_name; }
    267273
    268274    void show(std::ostream &os,Opts::iterator i);
     
    287293    }
    288294   
     295    ///Give back the command name (the 0th argument)
     296    const std::string &commandName() { return _command_name; }
     297
    289298    ///Check if an opion has been given to the command.
    290299    bool given(std::string op)
     
    361370      return RefType(*this, n);
    362371    }   
     372
     373    ///Give back the non-option type arguments.
     374
     375    ///Give back a reference to a vector consisting of the program arguments
     376    ///not starting with a '-' character.
     377    std::vector<std::string> &files() { return _file_args; }
    363378 
    364379  };
    365380}
    366381
    367    
    368 
    369 #endif // LEMON_MAIN_PARAMS
     382#endif // LEMON_ARG_PARSER
  • lemon/concepts/heap.h

    r113 r203  
    182182          Item item;
    183183          Prio prio;
    184           State state;
    185184          item=Item();
    186185          prio=Prio();
    187186          ignore_unused_variable_warning(item);
    188187          ignore_unused_variable_warning(prio);
    189           ignore_unused_variable_warning(state);
    190188
    191189          OwnItem own_item;
     
    204202         
    205203          int s = heap.size();
     204          ignore_unused_variable_warning(s);
    206205          bool e = heap.empty();
     206          ignore_unused_variable_warning(e);
    207207
    208208          prio = heap.prio();
     
    228228          heap.clear();
    229229
    230           state = heap.state(item);
    231           heap.state(item, state);
    232           state = heap.state(own_item);
     230          own_state = heap.state(own_item);
    233231          heap.state(own_item, own_state);
    234232
    235           state = _Heap::PRE_HEAP;
    236           state = _Heap::IN_HEAP;
    237           state = _Heap::POST_HEAP;
    238233          own_state = _Heap::PRE_HEAP;
    239234          own_state = _Heap::IN_HEAP;
  • lemon/graph_utils.h

    r169 r199  
    603603        for (typename From::ArcIt it(from); it != INVALID; ++it) {
    604604          arcRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
    605                                           nodeRefMap[from.target(it)]);
     605                                    nodeRefMap[from.target(it)]);
    606606        }
    607607      }
     
    629629        }
    630630        for (typename From::EdgeIt it(from); it != INVALID; ++it) {
    631           edgeRefMap[it] = to.addArc(nodeRefMap[from.source(it)],
    632                                        nodeRefMap[from.target(it)]);
     631          edgeRefMap[it] = to.addEdge(nodeRefMap[from.u(it)],
     632                                      nodeRefMap[from.v(it)]);
    633633        }
    634634      }
     
    926926
    927927      Value operator[](const Key& key) const {
    928         bool forward =
    929           (_from.direction(key) ==
    930            (_node_ref[_from.source(key)] == _to.source(_edge_ref[key])));
     928        bool forward = _from.u(key) != _from.v(key) ?
     929          _node_ref[_from.source(key)] ==
     930          _to.source(_to.direct(_edge_ref[key], true)) :
     931          _from.direction(key);
    931932        return _to.direct(_edge_ref[key], forward);
    932933      }
  • lemon/kruskal.h

    r167 r194  
    3333///\ingroup spantree
    3434///\file
    35 ///\brief Kruskal's algorithm to compute a minimum cost tree
     35///\brief Kruskal's algorithm to compute a minimum cost spanning tree
    3636///
    37 ///Kruskal's algorithm to compute a minimum cost tree.
     37///Kruskal's algorithm to compute a minimum cost spanning tree.
    3838///
    3939
     
    252252  /// \ingroup spantree
    253253  ///
    254   /// \brief Kruskal's algorithm to find a minimum cost tree of a graph.
    255   ///
    256   /// This function runs Kruskal's algorithm to find a minimum cost tree.
     254  /// \brief Kruskal algorithm to find a minimum cost spanning tree of
     255  /// a graph.
     256  ///
     257  /// This function runs Kruskal's algorithm to find a minimum cost
     258  /// spanning tree.
    257259  /// Due to some C++ hacking, it accepts various input and output types.
    258260  ///
     
    263265  /// undirected by disregarding the direction of the arcs.
    264266  ///
    265   /// \param in This object is used to describe the arc costs. It can be one
    266   /// of the following choices.
     267  /// \param in This object is used to describe the arc/edge costs.
     268  /// It can be one of the following choices.
    267269  /// - An STL compatible 'Forward Container' with
    268   /// <tt>std::pair<GR::Edge,X></tt> or
    269   /// <tt>std::pair<GR::Arc,X></tt> as its <tt>value_type</tt>, where
    270   /// \c X is the type of the costs. The pairs indicates the arcs
     270  /// <tt>std::pair<GR::Arc,X></tt> or
     271  /// <tt>std::pair<GR::Edge,X></tt> as its <tt>value_type</tt>, where
     272  /// \c X is the type of the costs. The pairs indicates the arcs/edges
    271273  /// along with the assigned cost. <em>They must be in a
    272274  /// cost-ascending order.</em>
    273   /// - Any readable Arc map. The values of the map indicate the arc costs.
    274   ///
    275   /// \retval out Here we also have a choise.
    276   /// - It can be a writable \c bool arc map.  After running the
    277   /// algorithm this will contain the found minimum cost spanning
    278   /// tree: the value of an arc will be set to \c true if it belongs
     275  /// - Any readable arc/edge map. The values of the map indicate the
     276  /// arc/edge costs.
     277  ///
     278  /// \retval out Here we also have a choice.
     279  /// - It can be a writable \c bool arc/edge map. After running the
     280  /// algorithm it will contain the found minimum cost spanning
     281  /// tree: the value of an arc/edge will be set to \c true if it belongs
    279282  /// to the tree, otherwise it will be set to \c false. The value of
    280   /// each arc will be set exactly once.
     283  /// each arc/edge will be set exactly once.
    281284  /// - It can also be an iteraror of an STL Container with
    282   /// <tt>GR::Edge</tt> or <tt>GR::Arc</tt> as its
     285  /// <tt>GR::Arc</tt> or <tt>GR::Edge</tt> as its
    283286  /// <tt>value_type</tt>.  The algorithm copies the elements of the
    284287  /// found tree into this sequence.  For example, if we know that the
     
    291294  /// Or if we don't know in advance the size of the tree, we can
    292295  /// write this. 
    293   ///\code std::vector<Arc> tree;
     296  ///\code
     297  /// std::vector<Arc> tree;
    294298  /// kruskal(g,cost,std::back_inserter(tree));
    295299  ///\endcode
    296300  ///
    297   /// \return The total cost of the found tree.
    298   ///
    299   /// \warning If kruskal runs on an be consistent of using the same
     301  /// \return The total cost of the found spanning tree.
     302  ///
     303  /// \warning If Kruskal runs on an be consistent of using the same
    300304  /// Arc type for input and output.
    301305  ///
  • lemon/lgf_reader.h

    r190 r201  
    1919///\ingroup lemon_io
    2020///\file
    21 ///\brief Lemon Graph Format reader.
     21///\brief \ref lgf-format "Lemon Graph Format" reader.
    2222
    2323
     
    196196    };
    197197
    198     bool isWhiteSpace(char c) {
     198    inline bool isWhiteSpace(char c) {
    199199      return c == ' ' || c == '\t' || c == '\v' ||
    200200        c == '\n' || c == '\r' || c == '\f';
    201201    }
    202202   
    203     bool isOct(char c) {
     203    inline bool isOct(char c) {
    204204      return '0' <= c && c <='7';
    205205    }
    206206   
    207     int valueOct(char c) {
     207    inline int valueOct(char c) {
    208208      LEMON_ASSERT(isOct(c), "The character is not octal.");
    209209      return c - '0';
    210210    }
    211211
    212     bool isHex(char c) {
     212    inline bool isHex(char c) {
    213213      return ('0' <= c && c <= '9') ||
    214214        ('a' <= c && c <= 'z') ||
     
    216216    }
    217217   
    218     int valueHex(char c) {
     218    inline int valueHex(char c) {
    219219      LEMON_ASSERT(isHex(c), "The character is not hexadecimal.");
    220220      if ('0' <= c && c <= '9') return c - '0';
     
    223223    }
    224224
    225     bool isIdentifierFirstChar(char c) {
     225    inline bool isIdentifierFirstChar(char c) {
    226226      return ('a' <= c && c <= 'z') ||
    227227        ('A' <= c && c <= 'Z') || c == '_';
    228228    }
    229229
    230     bool isIdentifierChar(char c) {
     230    inline bool isIdentifierChar(char c) {
    231231      return isIdentifierFirstChar(c) ||
    232232        ('0' <= c && c <= '9');
    233233    }
    234234
    235     char readEscape(std::istream& is) {
     235    inline char readEscape(std::istream& is) {
    236236      char c;
    237237      if (!is.get(c))
     
    285285    }
    286286   
    287     std::istream& readToken(std::istream& is, std::string& str) {
     287    inline std::istream& readToken(std::istream& is, std::string& str) {
    288288      std::ostringstream os;
    289289
     
    401401  /// \ingroup lemon_io
    402402  /// 
    403   /// \brief LGF reader for directed graphs
     403  /// \brief \ref lgf-format "LGF" reader for directed graphs
    404404  ///
    405405  /// This utility reads an \ref lgf-format "LGF" file.
     
    411411  /// with the \c nodeMap() or \c arcMap() members. An optional
    412412  /// converter parameter can also be added as a standard functor
    413   /// converting from std::string to the value type of the map. If it
     413  /// converting from \c std::string to the value type of the map. If it
    414414  /// is set, it will determine how the tokens in the file should be
    415   /// is converted to the map's value type. If the functor is not set,
     415  /// converted to the value type of the map. If the functor is not set,
    416416  /// then a default conversion will be used. One map can be read into
    417417  /// multiple map objects at the same time. The \c attribute(), \c
     
    420420  ///
    421421  ///\code
    422   ///     DigraphReader<Digraph>(std::cin, digraph).
    423   ///       nodeMap("coordinates", coord_map).
    424   ///       arcMap("capacity", cap_map).
    425   ///       node("source", src).
    426   ///       node("target", trg).
    427   ///       attribute("caption", caption).
    428   ///       run();
     422  /// DigraphReader<Digraph>(std::cin, digraph).
     423  ///   nodeMap("coordinates", coord_map).
     424  ///   arcMap("capacity", cap_map).
     425  ///   node("source", src).
     426  ///   node("target", trg).
     427  ///   attribute("caption", caption).
     428  ///   run();
    429429  ///\endcode
    430430  ///
     
    438438  /// graph) during the reading, but instead the label map of the items
    439439  /// are given as a parameter of these functions. An
    440   /// application of these function is multipass reading, which is
    441   /// important if two \e \@arcs sections must be read from the
    442   /// file. In this example the first phase would read the node set and one
     440  /// application of these functions is multipass reading, which is
     441  /// important if two \c \@arcs sections must be read from the
     442  /// file. In this case the first phase would read the node set and one
    443443  /// of the arc sets, while the second phase would read the second arc
    444444  /// set into an \e ArcSet class (\c SmartArcSet or \c ListArcSet).
    445445  /// The previously read label node map should be passed to the \c
    446446  /// useNodes() functions. Another application of multipass reading when
    447   /// paths are given as a node map or an arc map. It is impossible read this in
     447  /// paths are given as a node map or an arc map. It is impossible to read this in
    448448  /// a single pass, because the arcs are not constructed when the node
    449449  /// maps are read.
     
    736736    /// Use previously constructed node set, and specify the node
    737737    /// label map and a functor which converts the label map values to
    738     /// std::string.
     738    /// \c std::string.
    739739    template <typename Map, typename Converter>
    740740    DigraphReader& useNodes(const Map& map,
     
    769769    /// Use previously constructed arc set, and specify the arc
    770770    /// label map and a functor which converts the label map values to
    771     /// std::string.
     771    /// \c std::string.
    772772    template <typename Map, typename Converter>
    773773    DigraphReader& useArcs(const Map& map,
     
    785785    ///
    786786    /// Omit the reading of the node section. This implies that each node
    787     /// map reading rule will be abanoned, and the nodes of the graph
     787    /// map reading rule will be abandoned, and the nodes of the graph
    788788    /// will not be constructed, which usually cause that the arc set
    789     /// could not be read due to lack of node name
    790     /// resolving. Therefore, the \c skipArcs() should be used too, or
    791     /// the useNodes() member function should be used to specify the
    792     /// label of the nodes.
     789    /// could not be read due to lack of node name resolving.
     790    /// Therefore \c skipArcs() function should also be used, or
     791    /// \c useNodes() should be used to specify the label of the nodes.
    793792    DigraphReader& skipNodes() {
    794793      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
     
    800799    ///
    801800    /// Omit the reading of the arc section. This implies that each arc
    802     /// map reading rule will be abanoned, and the arcs of the graph
     801    /// map reading rule will be abandoned, and the arcs of the graph
    803802    /// will not be constructed.
    804803    DigraphReader& skipArcs() {
     
    11761175  };
    11771176
     1177  /// \brief Return a \ref DigraphReader class
     1178  ///
     1179  /// This function just returns a \ref DigraphReader class.
    11781180  /// \relates DigraphReader
    11791181  template <typename Digraph>
     
    11831185  }
    11841186
     1187  /// \brief Return a \ref DigraphReader class
     1188  ///
     1189  /// This function just returns a \ref DigraphReader class.
    11851190  /// \relates DigraphReader
    11861191  template <typename Digraph>
     
    11911196  }
    11921197
     1198  /// \brief Return a \ref DigraphReader class
     1199  ///
     1200  /// This function just returns a \ref DigraphReader class.
    11931201  /// \relates DigraphReader
    11941202  template <typename Digraph>
     
    12121220  /// \ingroup lemon_io
    12131221  /// 
    1214   /// \brief LGF reader for undirected graphs
     1222  /// \brief \ref lgf-format "LGF" reader for undirected graphs
    12151223  ///
    12161224  /// This utility reads an \ref lgf-format "LGF" file.
     1225  ///
     1226  /// It can be used almost the same way as \c DigraphReader.
     1227  /// The only difference is that this class can handle edges and
     1228  /// edge maps as well as arcs and arc maps.
     1229  ///
     1230  /// The columns in the \c \@edges (or \c \@arcs) section are the
     1231  /// edge maps. However, if there are two maps with the same name
     1232  /// prefixed with \c '+' and \c '-', then these can be read into an
     1233  /// arc map.  Similarly, an attribute can be read into an arc, if
     1234  /// it's value is an edge label prefixed with \c '+' or \c '-'.
    12171235  template <typename _Graph>
    12181236  class GraphReader {
     
    12631281    /// \brief Constructor
    12641282    ///
    1265     /// Construct a undirected graph reader, which reads from the given
     1283    /// Construct an undirected graph reader, which reads from the given
    12661284    /// input stream.
    12671285    GraphReader(std::istream& is, Graph& graph)
     
    12721290    /// \brief Constructor
    12731291    ///
    1274     /// Construct a undirected graph reader, which reads from the given
     1292    /// Construct an undirected graph reader, which reads from the given
    12751293    /// file.
    12761294    GraphReader(const std::string& fn, Graph& graph)
     
    12811299    /// \brief Constructor
    12821300    ///
    1283     /// Construct a undirected graph reader, which reads from the given
     1301    /// Construct an undirected graph reader, which reads from the given
    12841302    /// file.
    12851303    GraphReader(const char* fn, Graph& graph)
     
    14981516    /// \brief Set \c \@nodes section to be read
    14991517    ///
    1500     /// Set \c \@nodes section to be read
     1518    /// Set \c \@nodes section to be read.
    15011519    GraphReader& nodes(const std::string& caption) {
    15021520      _nodes_caption = caption;
     
    15061524    /// \brief Set \c \@edges section to be read
    15071525    ///
    1508     /// Set \c \@edges section to be read
     1526    /// Set \c \@edges section to be read.
    15091527    GraphReader& edges(const std::string& caption) {
    15101528      _edges_caption = caption;
     
    15141532    /// \brief Set \c \@attributes section to be read
    15151533    ///
    1516     /// Set \c \@attributes section to be read
     1534    /// Set \c \@attributes section to be read.
    15171535    GraphReader& attributes(const std::string& caption) {
    15181536      _attributes_caption = caption;
     
    15451563    /// Use previously constructed node set, and specify the node
    15461564    /// label map and a functor which converts the label map values to
    1547     /// std::string.
     1565    /// \c std::string.
    15481566    template <typename Map, typename Converter>
    15491567    GraphReader& useNodes(const Map& map,
     
    15781596    /// Use previously constructed edge set, and specify the edge
    15791597    /// label map and a functor which converts the label map values to
    1580     /// std::string.
     1598    /// \c std::string.
    15811599    template <typename Map, typename Converter>
    15821600    GraphReader& useEdges(const Map& map,
     
    15911609    }
    15921610
    1593     /// \brief Skips the reading of node section
     1611    /// \brief Skip the reading of node section
    15941612    ///
    15951613    /// Omit the reading of the node section. This implies that each node
    1596     /// map reading rule will be abanoned, and the nodes of the graph
     1614    /// map reading rule will be abandoned, and the nodes of the graph
    15971615    /// will not be constructed, which usually cause that the edge set
    15981616    /// could not be read due to lack of node name
    1599     /// resolving. Therefore, the \c skipEdges() should be used too, or
    1600     /// the useNodes() member function should be used to specify the
    1601     /// label of the nodes.
     1617    /// could not be read due to lack of node name resolving.
     1618    /// Therefore \c skipEdges() function should also be used, or
     1619    /// \c useNodes() should be used to specify the label of the nodes.
    16021620    GraphReader& skipNodes() {
    16031621      LEMON_ASSERT(!_skip_nodes, "Skip nodes already set");
     
    16061624    }
    16071625
    1608     /// \brief Skips the reading of edge section
     1626    /// \brief Skip the reading of edge section
    16091627    ///
    16101628    /// Omit the reading of the edge section. This implies that each edge
    1611     /// map reading rule will be abanoned, and the edges of the graph
     1629    /// map reading rule will be abandoned, and the edges of the graph
    16121630    /// will not be constructed.
    16131631    GraphReader& skipEdges() {
     
    19832001  };
    19842002
     2003  /// \brief Return a \ref GraphReader class
     2004  ///
     2005  /// This function just returns a \ref GraphReader class.
    19852006  /// \relates GraphReader
    19862007  template <typename Graph>
     
    19902011  }
    19912012
     2013  /// \brief Return a \ref GraphReader class
     2014  ///
     2015  /// This function just returns a \ref GraphReader class.
    19922016  /// \relates GraphReader
    19932017  template <typename Graph>
     
    19982022  }
    19992023
     2024  /// \brief Return a \ref GraphReader class
     2025  ///
     2026  /// This function just returns a \ref GraphReader class.
    20002027  /// \relates GraphReader
    20012028  template <typename Graph>
     
    20112038  SectionReader sectionReader(const char* fn);
    20122039 
     2040  /// \ingroup lemon_io
     2041  ///
    20132042  /// \brief Section reader class
    20142043  ///
    2015   /// In the \e LGF file extra sections can be placed, which contain
    2016   /// any data in arbitrary format. Such sections can be read with
    2017   /// this class. A reading rule can be added with two different
    2018   /// functions, with the \c sectionLines() function a functor can
    2019   /// process the section line-by-line. While with the \c
     2044  /// In the \ref lgf-format "LGF" file extra sections can be placed,
     2045  /// which contain any data in arbitrary format. Such sections can be
     2046  /// read with this class. A reading rule can be added to the class
     2047  /// with two different functions. With the \c sectionLines() function a
     2048  /// functor can process the section line-by-line, while with the \c
    20202049  /// sectionStream() member the section can be read from an input
    20212050  /// stream.
     
    21062135    ///\endcode
    21072136    ///
    2108     /// The functor is implemented as an struct:
     2137    /// The functor is implemented as a struct:
    21092138    ///\code
    21102139    ///  struct NumberSection {
     
    21242153    template <typename Functor>
    21252154    SectionReader& sectionLines(const std::string& type, Functor functor) {
    2126       LEMON_ASSERT(!type.empty(), "Type is not empty.");
     2155      LEMON_ASSERT(!type.empty(), "Type is empty.");
    21272156      LEMON_ASSERT(_sections.find(type) == _sections.end(),
    21282157                   "Multiple reading of section.");
     
    21362165    ///
    21372166    /// The first parameter is the type of the section, the second is
    2138     /// a functor, which takes an \c std::istream& and an int&
     2167    /// a functor, which takes an \c std::istream& and an \c int&
    21392168    /// parameter, the latter regard to the line number of stream. The
    21402169    /// functor can read the input while the section go on, and the
     
    21422171    template <typename Functor>
    21432172    SectionReader& sectionStream(const std::string& type, Functor functor) {
    2144       LEMON_ASSERT(!type.empty(), "Type is not empty.");
     2173      LEMON_ASSERT(!type.empty(), "Type is empty.");
    21452174      LEMON_ASSERT(_sections.find(type) == _sections.end(),
    21462175                   "Multiple reading of section.");
     
    21872216    /// \brief Start the batch processing
    21882217    ///
    2189     /// This function starts the batch processing
     2218    /// This function starts the batch processing.
    21902219    void run() {
    21912220     
     
    22402269  };
    22412270
     2271  /// \brief Return a \ref SectionReader class
     2272  ///
     2273  /// This function just returns a \ref SectionReader class.
    22422274  /// \relates SectionReader
    22432275  inline SectionReader sectionReader(std::istream& is) {
     
    22462278  }
    22472279
     2280  /// \brief Return a \ref SectionReader class
     2281  ///
     2282  /// This function just returns a \ref SectionReader class.
    22482283  /// \relates SectionReader
    22492284  inline SectionReader sectionReader(const std::string& fn) {
     
    22522287  }
    22532288
     2289  /// \brief Return a \ref SectionReader class
     2290  ///
     2291  /// This function just returns a \ref SectionReader class.
    22542292  /// \relates SectionReader
    22552293  inline SectionReader sectionReader(const char* fn) {
     
    22702308  /// reading the graph.
    22712309  ///
    2272   ///\code LgfContents contents("graph.lgf");
     2310  ///\code
     2311  /// LgfContents contents("graph.lgf");
    22732312  /// contents.run();
    22742313  ///
    2275   /// // does it contain any node section and arc section
     2314  /// // Does it contain any node section and arc section?
    22762315  /// if (contents.nodeSectionNum() == 0 || contents.arcSectionNum()) {
    2277   ///   std::cerr << "Failure, cannot find graph" << std::endl;
     2316  ///   std::cerr << "Failure, cannot find graph." << std::endl;
    22782317  ///   return -1;
    22792318  /// }
    2280   /// std::cout << "The name of the default node section : "
     2319  /// std::cout << "The name of the default node section: "
    22812320  ///           << contents.nodeSection(0) << std::endl;
    2282   /// std::cout << "The number of the arc maps : "
     2321  /// std::cout << "The number of the arc maps: "
    22832322  ///           << contents.arcMaps(0).size() << std::endl;
    2284   /// std::cout << "The name of second arc map : "
     2323  /// std::cout << "The name of second arc map: "
    22852324  ///           << contents.arcMaps(0)[1] << std::endl;
    22862325  ///\endcode
     
    23532392    }
    23542393
    2355     /// \brief Returns the section name at the given position.
    2356     ///
    2357     /// Returns the section name at the given position.
     2394    /// \brief Returns the node section name at the given position.
     2395    ///
     2396    /// Returns the node section name at the given position.
    23582397    const std::string& nodeSection(int i) const {
    23592398      return _node_sections[i];
     
    23802419    }
    23812420
    2382     /// \brief Returns the section name at the given position.
    2383     ///
    2384     /// Returns the section name at the given position.
     2421    /// \brief Returns the arc/edge section name at the given position.
     2422    ///
     2423    /// Returns the arc/edge section name at the given position.
    23852424    /// \note It is synonym of \c edgeSection().
    23862425    const std::string& arcSection(int i) const {
     
    24372476    }
    24382477
    2439     /// \brief Returns the section name at the given position.
    2440     ///
    2441     /// Returns the section name at the given position.
     2478    /// \brief Returns the attribute section name at the given position.
     2479    ///
     2480    /// Returns the attribute section name at the given position.
    24422481    const std::string& attributeSectionNames(int i) const {
    24432482      return _attribute_sections[i];
     
    25302569    /// @{
    25312570
    2532     /// \brief Start the reading
    2533     ///
    2534     /// This function starts the reading
     2571    /// \brief Starts the reading
     2572    ///
     2573    /// This function starts the reading.
    25352574    void run() {
    25362575
  • lemon/lgf_writer.h

    r190 r201  
    1919///\ingroup lemon_io
    2020///\file
    21 ///\brief Lemon Graph Format writer.
     21///\brief \ref lgf-format "Lemon Graph Format" writer.
    2222
    2323
     
    226226    };
    227227
    228     bool isWhiteSpace(char c) {
     228    inline bool isWhiteSpace(char c) {
    229229      return c == ' ' || c == '\t' || c == '\v' ||
    230230        c == '\n' || c == '\r' || c == '\f';
    231231    }
    232232
    233     bool isEscaped(char c) {
     233    inline bool isEscaped(char c) {
    234234      return c == '\\' || c == '\"' || c == '\'' ||
    235235        c == '\a' || c == '\b';
    236236    }
    237237
    238     static void writeEscape(std::ostream& os, char c) {
     238    inline static void writeEscape(std::ostream& os, char c) {
    239239      switch (c) {
    240240      case '\\':
     
    277277    }
    278278
    279     bool requireEscape(const std::string& str) {
     279    inline bool requireEscape(const std::string& str) {
    280280      if (str.empty() || str[0] == '@') return true;
    281281      std::istringstream is(str);
     
    289289    }
    290290   
    291     std::ostream& writeToken(std::ostream& os, const std::string& str) {
     291    inline std::ostream& writeToken(std::ostream& os, const std::string& str) {
    292292
    293293      if (requireEscape(str)) {
     
    323323  /// \ingroup lemon_io
    324324  /// 
    325   /// \brief LGF writer for directed graphs
     325  /// \brief \ref lgf-format "LGF" writer for directed graphs
    326326  ///
    327327  /// This utility writes an \ref lgf-format "LGF" file.
     
    333333  /// with the \c nodeMap() or \c arcMap() members. An optional
    334334  /// converter parameter can also be added as a standard functor
    335   /// converting from the value type of the map to std::string. If it
    336   /// is set, it will determine how the map's value type is written to
     335  /// converting from the value type of the map to \c std::string. If it
     336  /// is set, it will determine how the value type of the map is written to
    337337  /// the output stream. If the functor is not set, then a default
    338338  /// conversion will be used. The \c attribute(), \c node() and \c
     
    340340  ///
    341341  ///\code
    342   ///     DigraphWriter<Digraph>(std::cout, digraph).
    343   ///       nodeMap("coordinates", coord_map).
    344   ///       nodeMap("size", size).
    345   ///       nodeMap("title", title).
    346   ///       arcMap("capacity", cap_map).
    347   ///       node("source", src).
    348   ///       node("target", trg).
    349   ///       attribute("caption", caption).
    350   ///       run();
     342  /// DigraphWriter<Digraph>(std::cout, digraph).
     343  ///   nodeMap("coordinates", coord_map).
     344  ///   nodeMap("size", size).
     345  ///   nodeMap("title", title).
     346  ///   arcMap("capacity", cap_map).
     347  ///   node("source", src).
     348  ///   node("target", trg).
     349  ///   attribute("caption", caption).
     350  ///   run();
    351351  ///\endcode
    352352  ///
     
    487487    /// @{
    488488   
    489     /// \brief Node map reading rule
    490     ///
    491     /// Add a node map reading rule to the writer.
     489    /// \brief Node map writing rule
     490    ///
     491    /// Add a node map writing rule to the writer.
    492492    template <typename Map>
    493493    DigraphWriter& nodeMap(const std::string& caption, const Map& map) {
     
    587587    }
    588588
    589     /// \name Select section by name
     589    /// \name Section captions
    590590    /// @{
    591591
    592     /// \brief Set \c \@nodes section to be read
    593     ///
    594     /// Set \c \@nodes section to be read
     592    /// \brief Add an additional caption to the \c \@nodes section
     593    ///
     594    /// Add an additional caption to the \c \@nodes section.
    595595    DigraphWriter& nodes(const std::string& caption) {
    596596      _nodes_caption = caption;
     
    598598    }
    599599
    600     /// \brief Set \c \@arcs section to be read
    601     ///
    602     /// Set \c \@arcs section to be read
     600    /// \brief Add an additional caption to the \c \@arcs section
     601    ///
     602    /// Add an additional caption to the \c \@arcs section.
    603603    DigraphWriter& arcs(const std::string& caption) {
    604604      _arcs_caption = caption;
     
    606606    }
    607607
    608     /// \brief Set \c \@attributes section to be read
    609     ///
    610     /// Set \c \@attributes section to be read
     608    /// \brief Add an additional caption to the \c \@attributes section
     609    ///
     610    /// Add an additional caption to the \c \@attributes section.
    611611    DigraphWriter& attributes(const std::string& caption) {
    612612      _attributes_caption = caption;
     
    619619    /// \brief Skip writing the node set
    620620    ///
    621     /// The \c \@nodes section will be not written to the stream.
     621    /// The \c \@nodes section will not be written to the stream.
    622622    DigraphWriter& skipNodes() {
    623623      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
     
    628628    /// \brief Skip writing arc set
    629629    ///
    630     /// The \c \@arcs section will be not written to the stream.
     630    /// The \c \@arcs section will not be written to the stream.
    631631    DigraphWriter& skipArcs() {
    632632      LEMON_ASSERT(!_skip_arcs, "Multiple usage of skipArcs() member");
     
    836836    /// \brief Start the batch processing
    837837    ///
    838     /// This function starts the batch processing
     838    /// This function starts the batch processing.
    839839    void run() {
    840840      if (!_skip_nodes) {
     
    851851    }
    852852
    853     /// \brief Gives back the stream of the writer
    854     ///
    855     /// Gives back the stream of the writer
     853    /// \brief Give back the stream of the writer
     854    ///
     855    /// Give back the stream of the writer.
    856856    std::ostream& ostream() {
    857857      return *_os;
     
    861861  };
    862862
     863  /// \brief Return a \ref DigraphWriter class
     864  ///
     865  /// This function just returns a \ref DigraphWriter class.
    863866  /// \relates DigraphWriter
    864867  template <typename Digraph>
     
    869872  }
    870873
     874  /// \brief Return a \ref DigraphWriter class
     875  ///
     876  /// This function just returns a \ref DigraphWriter class.
    871877  /// \relates DigraphWriter
    872878  template <typename Digraph>
     
    877883  }
    878884
     885  /// \brief Return a \ref DigraphWriter class
     886  ///
     887  /// This function just returns a \ref DigraphWriter class.
    879888  /// \relates DigraphWriter
    880889  template <typename Digraph>
     
    899908  /// \ingroup lemon_io
    900909  /// 
    901   /// \brief LGF writer for directed graphs
     910  /// \brief \ref lgf-format "LGF" writer for directed graphs
    902911  ///
    903912  /// This utility writes an \ref lgf-format "LGF" file.
     913  ///
     914  /// It can be used almost the same way as \c DigraphWriter.
     915  /// The only difference is that this class can handle edges and
     916  /// edge maps as well as arcs and arc maps.
     917  ///
     918  /// The arc maps are written into the file as two columns, the
     919  /// caption of the columns are the name of the map prefixed with \c
     920  /// '+' and \c '-'. The arcs are written into the \c \@attributes
     921  /// section as a \c '+' or a \c '-' prefix (depends on the direction
     922  /// of the arc) and the label of corresponding edge.
    904923  template <typename _Graph>
    905924  class GraphWriter {
     
    10241043    /// @{
    10251044   
    1026     /// \brief Node map reading rule
    1027     ///
    1028     /// Add a node map reading rule to the writer.
     1045    /// \brief Node map writing rule
     1046    ///
     1047    /// Add a node map writing rule to the writer.
    10291048    template <typename Map>
    10301049    GraphWriter& nodeMap(const std::string& caption, const Map& map) {
     
    11701189    }
    11711190
    1172     /// \name Select section by name
     1191    /// \name Section captions
    11731192    /// @{
    11741193
    1175     /// \brief Set \c \@nodes section to be read
    1176     ///
    1177     /// Set \c \@nodes section to be read
     1194    /// \brief Add an additional caption to the \c \@nodes section
     1195    ///
     1196    /// Add an additional caption to the \c \@nodes section.
    11781197    GraphWriter& nodes(const std::string& caption) {
    11791198      _nodes_caption = caption;
     
    11811200    }
    11821201
    1183     /// \brief Set \c \@edges section to be read
    1184     ///
    1185     /// Set \c \@edges section to be read
     1202    /// \brief Add an additional caption to the \c \@arcs section
     1203    ///
     1204    /// Add an additional caption to the \c \@arcs section.
    11861205    GraphWriter& edges(const std::string& caption) {
    11871206      _edges_caption = caption;
     
    11891208    }
    11901209
    1191     /// \brief Set \c \@attributes section to be read
    1192     ///
    1193     /// Set \c \@attributes section to be read
     1210    /// \brief Add an additional caption to the \c \@attributes section
     1211    ///
     1212    /// Add an additional caption to the \c \@attributes section.
    11941213    GraphWriter& attributes(const std::string& caption) {
    11951214      _attributes_caption = caption;
     
    12021221    /// \brief Skip writing the node set
    12031222    ///
    1204     /// The \c \@nodes section will be not written to the stream.
     1223    /// The \c \@nodes section will not be written to the stream.
    12051224    GraphWriter& skipNodes() {
    12061225      LEMON_ASSERT(!_skip_nodes, "Multiple usage of skipNodes() member");
     
    12111230    /// \brief Skip writing edge set
    12121231    ///
    1213     /// The \c \@edges section will be not written to the stream.
     1232    /// The \c \@edges section will not be written to the stream.
    12141233    GraphWriter& skipEdges() {
    12151234      LEMON_ASSERT(!_skip_edges, "Multiple usage of skipEdges() member");
     
    14191438    /// \brief Start the batch processing
    14201439    ///
    1421     /// This function starts the batch processing
     1440    /// This function starts the batch processing.
    14221441    void run() {
    14231442      if (!_skip_nodes) {
     
    14341453    }
    14351454
    1436     /// \brief Gives back the stream of the writer
    1437     ///
    1438     /// Gives back the stream of the writer
     1455    /// \brief Give back the stream of the writer
     1456    ///
     1457    /// Give back the stream of the writer
    14391458    std::ostream& ostream() {
    14401459      return *_os;
     
    14441463  };
    14451464
     1465  /// \brief Return a \ref GraphWriter class
     1466  ///
     1467  /// This function just returns a \ref GraphWriter class.
    14461468  /// \relates GraphWriter
    14471469  template <typename Graph>
     
    14511473  }
    14521474
     1475  /// \brief Return a \ref GraphWriter class
     1476  ///
     1477  /// This function just returns a \ref GraphWriter class.
    14531478  /// \relates GraphWriter
    14541479  template <typename Graph>
     
    14581483  }
    14591484
     1485  /// \brief Return a \ref GraphWriter class
     1486  ///
     1487  /// This function just returns a \ref GraphWriter class.
    14601488  /// \relates GraphWriter
    14611489  template <typename Graph>
  • test/CMakeLists.txt

    r171 r203  
    1111  dim_test
    1212  error_test
     13  graph_copy_test
    1314  graph_test
    1415  graph_utils_test
     16  heap_test
    1517  kruskal_test
    1618  maps_test
  • test/Makefile.am

    r171 r203  
    44noinst_HEADERS += \
    55        test/graph_test.h \
    6         test/heap_test.h \
    76        test/graph_maps_test.h \
    87        test/test_tools.h
     
    1615        test/dim_test \
    1716        test/error_test \
     17        test/graph_copy_test \
    1818        test/graph_test \
    1919        test/graph_utils_test \
     20        test/heap_test \
    2021        test/kruskal_test \
    2122        test/maps_test \
     
    3738test_dim_test_SOURCES = test/dim_test.cc
    3839test_error_test_SOURCES = test/error_test.cc
     40test_graph_copy_test_SOURCES = test/graph_copy_test.cc
    3941test_graph_test_SOURCES = test/graph_test.cc
    4042test_graph_utils_test_SOURCES = test/graph_utils_test.cc
    41 # test_heap_test_SOURCES = test/heap_test.cc
     43test_heap_test_SOURCES = test/heap_test.cc
    4244test_kruskal_test_SOURCES = test/kruskal_test.cc
    4345test_maps_test_SOURCES = test/maps_test.cc
  • test/heap_test.cc

    r171 r203  
    2525#include <lemon/concepts/heap.h>
    2626
    27 #include <lemon/list_graph.h>
     27#include <lemon/smart_graph.h>
    2828
    29 #include <lemon/digraph_reader.h>
     29#include <lemon/lgf_reader.h>
     30#include <lemon/dijkstra.h>
     31#include <lemon/maps.h>
    3032
    3133#include <lemon/bin_heap.h>
    32 #include <lemon/fib_heap.h>
    33 #include <lemon/radix_heap.h>
    34 #include <lemon/bucket_heap.h>
    3534
    3635#include "test_tools.h"
    3736
    38 #include "heap_test.h"
    39 
    40 #include <lemon/time_measure.h>
    41 
    4237using namespace lemon;
    4338using namespace lemon::concepts;
     39
     40typedef ListDigraph Digraph;
     41DIGRAPH_TYPEDEFS(Digraph);
     42
     43char test_lgf[] =
     44  "@nodes\n"
     45  "label\n"     
     46  "0\n"
     47  "1\n"
     48  "2\n"
     49  "3\n"
     50  "4\n"
     51  "5\n"
     52  "6\n"
     53  "7\n"
     54  "8\n"
     55  "9\n"
     56  "@arcs\n"
     57  "             label   capacity\n"     
     58  "0    5       0       94\n"   
     59  "3    9       1       11\n"   
     60  "8    7       2       83\n"   
     61  "1    2       3       94\n"   
     62  "5    7       4       35\n"   
     63  "7    4       5       84\n"   
     64  "9    5       6       38\n"   
     65  "0    4       7       96\n"   
     66  "6    7       8       6\n"   
     67  "3    1       9       27\n"   
     68  "5    2       10      77\n"   
     69  "5    6       11      69\n"   
     70  "6    5       12      41\n"   
     71  "4    6       13      70\n"   
     72  "3    2       14      45\n"   
     73  "7    9       15      93\n"   
     74  "5    9       16      50\n"   
     75  "9    0       17      94\n"   
     76  "9    6       18      67\n"   
     77  "0    9       19      86\n"   
     78  "@attributes\n"
     79  "source 3\n";
     80
     81int test_seq[] = { 2, 28, 19, 27, 33, 25, 13, 41, 10, 26,  1,  9,  4, 34};
     82int test_inc[] = {20, 28, 34, 16,  0, 46, 44,  0, 42, 32, 14,  8,  6, 37};
     83
     84int test_len = sizeof(test_seq) / sizeof(test_seq[0]);
     85
     86template <typename Heap>
     87void heapSortTest() {
     88  RangeMap<int> map(test_len, -1);
     89
     90  Heap heap(map);
     91 
     92  std::vector<int> v(test_len);
     93
     94  for (int i = 0; i < test_len; ++i) {
     95    v[i] = test_seq[i];
     96    heap.push(i, v[i]);
     97  }
     98  std::sort(v.begin(), v.end());
     99  for (int i = 0; i < test_len; ++i) {
     100    check(v[i] == heap.prio() ,"Wrong order in heap sort.");
     101    heap.pop();
     102  }
     103}
     104
     105template <typename Heap>
     106void heapIncreaseTest() {
     107  RangeMap<int> map(test_len, -1);
     108
     109  Heap heap(map);
     110 
     111  std::vector<int> v(test_len);
     112
     113  for (int i = 0; i < test_len; ++i) {
     114    v[i] = test_seq[i];
     115    heap.push(i, v[i]);
     116  }
     117  for (int i = 0; i < test_len; ++i) {
     118    v[i] += test_inc[i];
     119    heap.increase(i, v[i]);
     120  }
     121  std::sort(v.begin(), v.end());
     122  for (int i = 0; i < test_len; ++i) {
     123    check(v[i] == heap.prio() ,"Wrong order in heap increase test.");
     124    heap.pop();
     125  }
     126}
     127
     128
     129
     130template <typename Heap>
     131void dijkstraHeapTest(const Digraph& digraph, const IntArcMap& length,
     132                      Node source) {
     133 
     134  typename Dijkstra<Digraph, IntArcMap>::template DefStandardHeap<Heap>::
     135    Create dijkstra(digraph, length);
     136
     137  dijkstra.run(source);
     138
     139  for(ArcIt a(digraph); a != INVALID; ++a) {
     140    Node s = digraph.source(a);
     141    Node t = digraph.target(a);
     142    if (dijkstra.reached(s)) {
     143      check( dijkstra.dist(t) - dijkstra.dist(s) <= length[a],
     144             "Error in a shortest path tree!");
     145    }
     146  }
     147
     148  for(NodeIt n(digraph); n != INVALID; ++n) {
     149    if ( dijkstra.reached(n) && dijkstra.predArc(n) != INVALID ) {
     150      Arc a = dijkstra.predArc(n);
     151      Node s = digraph.source(a);
     152      check( dijkstra.dist(n) - dijkstra.dist(s) == length[a],
     153             "Error in a shortest path tree!");
     154    }
     155  }
     156
     157}
    44158
    45159int main() {
     
    47161  typedef int Item;
    48162  typedef int Prio;
    49   typedef IntIntMap ItemIntMap;
     163  typedef RangeMap<int> ItemIntMap;
     164 
     165  Digraph digraph;
     166  IntArcMap length(digraph);
     167  Node source;
    50168
    51   typedef ListDigraph Digraph;
    52 
    53   typedef Digraph::Arc Arc;
    54   typedef Digraph::Node Node;
    55   typedef Digraph::ArcIt ArcIt;
    56   typedef Digraph::NodeIt NodeIt;
    57   typedef Digraph::ArcMap<int> LengthMap;
    58 
    59   Digraph digraph;
    60   LengthMap length(digraph);
    61   Node start;
    62 
    63   /// \todo create own test digraph
    64 
    65   std::string f_name;
    66   if( getenv("srcdir") )
    67     f_name = std::string(getenv("srcdir"));
    68   else f_name = ".";
    69   f_name += "/test/dijkstra_test.lgf";
    70  
    71   std::ifstream input(f_name.c_str());
    72   check(input, "Input file '" << f_name << "' not found.");
    73   DigraphReader<Digraph>(input, digraph).
    74     readArcMap("capacity", length).
    75     readNode("source", start).
     169  std::istringstream input(test_lgf);
     170  digraphReader(input, digraph).
     171    arcMap("capacity", length).
     172    node("source", source).
    76173    run(); 
    77174 
    78175  {
    79     std::cout << "Checking Bin Heap" << std::endl;
    80 
    81176    typedef BinHeap<Prio, ItemIntMap> IntHeap;
    82177    checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    83     heapSortTest<IntHeap>(100);
    84     heapIncreaseTest<IntHeap>(100);
     178    heapSortTest<IntHeap>();
     179    heapIncreaseTest<IntHeap>();
    85180   
    86     typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
    87     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
    88     Timer timer;
    89     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    90     std::cout << timer << std::endl;
    91   }
    92   {
    93     std::cout << "Checking Fib Heap" << std::endl;
    94 
    95     typedef FibHeap<Prio, ItemIntMap> IntHeap;
    96     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    97     heapSortTest<IntHeap>(100);
    98     heapIncreaseTest<IntHeap>(100);
    99 
    100     typedef FibHeap<Prio, Digraph::NodeMap<int> > NodeHeap;
    101     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
    102     Timer timer;
    103     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    104     std::cout << timer << std::endl;
    105   }
    106   {
    107     std::cout << "Checking Radix Heap" << std::endl;
    108 
    109     typedef RadixHeap<ItemIntMap> IntHeap;
    110     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    111     heapSortTest<IntHeap>(100);
    112     heapIncreaseTest<IntHeap>(100);
    113 
    114     typedef RadixHeap<Digraph::NodeMap<int> > NodeHeap;
    115     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
    116     Timer timer;
    117     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    118     std::cout << timer << std::endl;
    119   }
    120 
    121   {
    122     std::cout << "Checking Bucket Heap" << std::endl;
    123 
    124     typedef BucketHeap<ItemIntMap> IntHeap;
    125     checkConcept<Heap<Prio, ItemIntMap>, IntHeap>();
    126     heapSortTest<IntHeap>(100);
    127     heapIncreaseTest<IntHeap>(100);
    128 
    129     typedef BucketHeap<Digraph::NodeMap<int> > NodeHeap;
    130     checkConcept<Heap<Prio, Digraph::NodeMap<int> >, NodeHeap>();
    131     Timer timer;
    132     dijkstraHeapTest<Digraph, LengthMap, NodeHeap>(digraph, length, start);
    133     std::cout << timer << std::endl;
     181    typedef BinHeap<Prio, IntNodeMap > NodeHeap;
     182    checkConcept<Heap<Prio, IntNodeMap >, NodeHeap>();
     183    dijkstraHeapTest<NodeHeap>(digraph, length, source);
    134184  }
    135185
Note: See TracChangeset for help on using the changeset viewer.