COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search

Changeset 209:765619b7cbb2 in lemon-main


Ignore:
Timestamp:
07/13/08 20:51:02 (16 years ago)
Author:
Alpar Juttner <alpar@…>
Branch:
default
Phase:
public
Message:

Apply unify-sources.sh to the source tree

Files:
80 edited

Legend:

Unmodified
Added
Removed

  • demo/arg_parser_demo.cc

    r204 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    6565  ap.other("infile", "The input file.")
    6666    .other("...");
    67  
     67
    6868  // Perform the parsing process
    6969  // (in case of any error it terminates the program)
    … …  
    8585  if(ap.given("grb")) std::cout << "  -grb is given\n";
    8686  if(ap.given("grc")) std::cout << "  -grc is given\n";
    87  
     87
    8888  switch(ap.files().size()) {
    8989  case 0:
    … …  
    9595  default:
    9696    std::cout << "  "
    97               << ap.files().size() << " file arguments were given. They are:\n";
     97              << ap.files().size() << " file arguments were given. They are:\n";
    9898  }
    9999  for(unsigned int i=0;i<ap.files().size();++i)
    100100    std::cout << "    '" << ap.files()[i] << "'\n";
    101  
     101
    102102  return 0;
    103103}

  • demo/graph_to_eps_demo.cc

    r206 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    5050  typedef ListDigraph::Arc Arc;
    5151  typedef dim2::Point<int> Point;
    52  
     52
    5353  Node n1=g.addNode();
    5454  Node n2=g.addNode();
    … …  
    6363  ListDigraph::ArcMap<int> acolors(g);
    6464  ListDigraph::ArcMap<int> widths(g);
    65  
     65
    6666  coords[n1]=Point(50,50);  sizes[n1]=1; colors[n1]=1; shapes[n1]=0;
    6767  coords[n2]=Point(50,70);  sizes[n2]=2; colors[n2]=2; shapes[n2]=2;
    … …  
    6969  coords[n4]=Point(70,50);  sizes[n4]=2; colors[n4]=4; shapes[n4]=1;
    7070  coords[n5]=Point(85,60);  sizes[n5]=3; colors[n5]=5; shapes[n5]=2;
    71  
     71
    7272  Arc a;
    7373
    … …  
    7979  a=g.addArc(n2,n4); acolors[a]=1; widths[a]=2;
    8080  a=g.addArc(n3,n4); acolors[a]=2; widths[a]=1;
    81  
     81
    8282  IdMap<ListDigraph,Node> id(g);
    8383
    … …  
    183183  ListDigraph::NodeMap<int> hcolors(h);
    184184  ListDigraph::NodeMap<Point> hcoords(h);
    185  
     185
    186186  int cols=int(sqrt(double(palette.size())));
    187187  for(int i=0;i<int(paletteW.size());i++) {
    … …  
    190190    hcolors[n]=i;
    191191  }
    192  
     192
    193193  cout << "Create 'graph_to_eps_demo_out_6_colors.eps'" << endl;
    194194  graphToEps(h,"graph_to_eps_demo_out_6_colors.eps").
    … …  
    203203    nodeColors(composeMap(paletteW,hcolors)).
    204204    run();
    205    
     205
    206206  return 0;
    207207}

  • demo/lgf_demo.cc

    r193 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    2222///
    2323/// 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 
     24/// and additional maps from/to a stream or a file using the
    2525/// \ref lgf-format "LGF" format.
    2626///
    … …  
    4343  SmartDigraph::ArcMap<int> cap(g);
    4444  SmartDigraph::Node s, t;
    45  
     45
    4646  try {
    4747    digraphReader("digraph.lgf", g). // read the directed graph into g

  • doc/coding_style.dox

    r41 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    1919/*!
    2020
    21 \page coding_style LEMON Coding Style 
     21\page coding_style LEMON Coding Style
    2222
    2323\section naming_conv Naming Conventions
    … …  
    6969
    7070\code
    71 AllWordsCapitalizedWithoutUnderscores 
     71AllWordsCapitalizedWithoutUnderscores
    7272\endcode
    7373
    … …  
    7777
    7878\code
    79 firstWordLowerCaseRestCapitalizedWithoutUnderscores 
     79firstWordLowerCaseRestCapitalizedWithoutUnderscores
    8080\endcode
    8181
    … …  
    8585
    8686\code
    87 ALL_UPPER_CASE_WITH_UNDERSCORES 
     87ALL_UPPER_CASE_WITH_UNDERSCORES
    8888\endcode
    8989
    90 \subsection cs-loc-var Class and instance member variables, auto variables 
     90\subsection cs-loc-var Class and instance member variables, auto variables
    9191
    9292The names of class and instance member variables and auto variables (=variables used locally in methods) should look like the following.
    9393
    9494\code
    95 all_lower_case_with_underscores 
     95all_lower_case_with_underscores
    9696\endcode
    9797

  • doc/dirs.dox

    r40 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    7575
    7676This directory contains some helper classes to implement graphs, maps and
    77 some other classes. As a user you typically don't have to deal with these 
     77some other classes. As a user you typically don't have to deal with these
    7878files.
    7979*/

  • doc/groups.dox

    r192 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    2727\brief Graph structures implemented in LEMON.
    2828
    29 The implementation of combinatorial algorithms heavily relies on 
    30 efficient graph implementations. LEMON offers data structures which are 
    31 planned to be easily used in an experimental phase of implementation studies, 
    32 and thereafter the program code can be made efficient by small modifications. 
     29The implementation of combinatorial algorithms heavily relies on
     30efficient graph implementations. LEMON offers data structures which are
     31planned to be easily used in an experimental phase of implementation studies,
     32and thereafter the program code can be made efficient by small modifications.
    3333
    3434The most efficient implementation of diverse applications require the
    … …  
    4141some graph features like arc/edge or node deletion.
    4242
    43 Alteration of standard containers need a very limited number of 
    44 operations, these together satisfy the everyday requirements. 
    45 In the case of graph structures, different operations are needed which do 
    46 not alter the physical graph, but gives another view. If some nodes or 
     43Alteration of standard containers need a very limited number of
     44operations, these together satisfy the everyday requirements.
     45In the case of graph structures, different operations are needed which do
     46not alter the physical graph, but gives another view. If some nodes or
    4747arcs have to be hidden or the reverse oriented graph have to be used, then
    48 this is the case. It also may happen that in a flow implementation 
    49 the residual graph can be accessed by another algorithm, or a node-set 
    50 is to be shrunk for another algorithm. 
    51 LEMON also provides a variety of graphs for these requirements called 
    52 \ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only 
    53 in conjunction with other graph representations. 
     48this is the case. It also may happen that in a flow implementation
     49the residual graph can be accessed by another algorithm, or a node-set
     50is to be shrunk for another algorithm.
     51LEMON also provides a variety of graphs for these requirements called
     52\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
     53in conjunction with other graph representations.
    5454
    5555You are free to use the graph structure that fit your requirements
    5656the best, most graph algorithms and auxiliary data structures can be used
    57 with any graph structures. 
     57with any graph structures.
    5858*/
    5959
    … …  
    6464
    6565This group describes some graph types between real graphs and graph adaptors.
    66 These classes wrap graphs to give new functionality as the adaptors do it. 
     66These classes wrap graphs to give new functionality as the adaptors do it.
    6767On the other hand they are not light-weight structures as the adaptors.
    6868*/
    6969
    7070/**
    71 @defgroup maps Maps 
     71@defgroup maps Maps
    7272@ingroup datas
    7373\brief Map structures implemented in LEMON.
    … …  
    8080
    8181/**
    82 @defgroup graph_maps Graph Maps 
     82@defgroup graph_maps Graph Maps
    8383@ingroup maps
    8484\brief Special graph-related maps.
    … …  
    116116    }
    117117  }
    118  
     118
    119119  Digraph::NodeMap<int> degree_map(graph);
    120  
     120
    121121  digraphToEps(graph, "graph.eps")
    122122    .coords(coords).scaleToA4().undirected()
    123123    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
    124124    .run();
    125 \endcode 
     125\endcode
    126126The \c functorToMap() function makes an \c int to \c Color map from the
    127127\e nodeColor() function. The \c composeMap() compose the \e degree_map
    … …  
    141141  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
    142142  TimeMap time(length, speed);
    143  
     143
    144144  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
    145145  dijkstra.run(source, target);
    … …  
    153153
    154154/**
    155 @defgroup matrices Matrices 
     155@defgroup matrices Matrices
    156156@ingroup datas
    157157\brief Two dimensional data storages implemented in LEMON.
    … …  
    201201\brief Common graph search algorithms.
    202202
    203 This group describes the common graph search algorithms like 
     203This group describes the common graph search algorithms like
    204204Breadth-first search (Bfs) and Depth-first search (Dfs).
    205205*/
    … …  
    213213*/
    214214
    215 /** 
    216 @defgroup max_flow Maximum Flow algorithms 
    217 @ingroup algs 
     215/**
     216@defgroup max_flow Maximum Flow algorithms
     217@ingroup algs
    218218\brief Algorithms for finding maximum flows.
    219219
    … …  
    232232
    233233LEMON contains several algorithms for solving maximum flow problems:
    234 - \ref lemon::EdmondsKarp "Edmonds-Karp" 
     234- \ref lemon::EdmondsKarp "Edmonds-Karp"
    235235- \ref lemon::Preflow "Goldberg's Preflow algorithm"
    236236- \ref lemon::DinitzSleatorTarjan "Dinitz's blocking flow algorithm with dynamic trees"
    … …  
    251251
    252252This group describes the algorithms for finding minimum cost flows and
    253 circulations. 
    254 */
    255 
    256 /**
    257 @defgroup min_cut Minimum Cut algorithms 
    258 @ingroup algs 
     253circulations.
     254*/
     255
     256/**
     257@defgroup min_cut Minimum Cut algorithms
     258@ingroup algs
    259259
    260260\brief Algorithms for finding minimum cut in graphs.
    … …  
    273273
    274274- \ref lemon::HaoOrlin "Hao-Orlin algorithm" to calculate minimum cut
    275   in directed graphs 
     275  in directed graphs
    276276- \ref lemon::NagamochiIbaraki "Nagamochi-Ibaraki algorithm" to
    277277  calculate minimum cut in undirected graphs
    … …  
    308308
    309309/**
    310 @defgroup matching Matching algorithms 
     310@defgroup matching Matching algorithms
    311311@ingroup algs
    312312\brief Algorithms for finding matchings in graphs and bipartite graphs.
    … …  
    315315matchings in graphs and bipartite graphs. The general matching problem is
    316316finding a subset of the arcs which does not shares common endpoints.
    317  
     317
    318318There are several different algorithms for calculate matchings in
    319319graphs.  The matching problems in bipartite graphs are generally
    … …  
    324324
    325325Lemon contains the next algorithms:
    326 - \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp 
    327   augmenting path algorithm for calculate maximum cardinality matching in 
     326- \ref lemon::MaxBipartiteMatching "MaxBipartiteMatching" Hopcroft-Karp
     327  augmenting path algorithm for calculate maximum cardinality matching in
    328328  bipartite graphs
    329 - \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel 
    330   algorithm for calculate maximum cardinality matching in bipartite graphs 
    331 - \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching" 
    332   Successive shortest path algorithm for calculate maximum weighted matching 
     329- \ref lemon::PrBipartiteMatching "PrBipartiteMatching" Push-Relabel
     330  algorithm for calculate maximum cardinality matching in bipartite graphs
     331- \ref lemon::MaxWeightedBipartiteMatching "MaxWeightedBipartiteMatching"
     332  Successive shortest path algorithm for calculate maximum weighted matching
    333333  and maximum weighted bipartite matching in bipartite graph
    334 - \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching" 
    335   Successive shortest path algorithm for calculate minimum cost maximum 
     334- \ref lemon::MinCostMaxBipartiteMatching "MinCostMaxBipartiteMatching"
     335  Successive shortest path algorithm for calculate minimum cost maximum
    336336  matching in bipartite graph
    337337- \ref lemon::MaxMatching "MaxMatching" Edmond's blossom shrinking algorithm
    … …  
    397397*/
    398398
    399 /** 
    400 @defgroup lp_utils Tools for Lp and Mip solvers 
     399/**
     400@defgroup lp_utils Tools for Lp and Mip solvers
    401401@ingroup lp_group
    402402\brief Helper tools to the Lp and Mip solvers.
    … …  
    415415
    416416/**
    417 @defgroup utils Tools and Utilities 
     417@defgroup utils Tools and Utilities
    418418\brief Tools and utilities for programming in LEMON
    419419
    … …  
    468468\brief Graph Input-Output methods
    469469
    470 This group describes the tools for importing and exporting graphs 
     470This group describes the tools for importing and exporting graphs
    471471and graph related data. Now it supports the LEMON format, the
    472472\c DIMACS format and the encapsulated postscript (EPS) format.
    … …  
    487487
    488488This group describes general \c EPS drawing methods and special
    489 graph exporting tools. 
     489graph exporting tools.
    490490*/
    491491
    … …  
    499499
    500500The purpose of the classes in this group is fourfold.
    501  
     501
    502502- These classes contain the documentations of the concepts. In order
    503503  to avoid document multiplications, an implementation of a concept
    … …  
    552552@defgroup tools Standalone utility applications
    553553
    554 Some utility applications are listed here. 
     554Some utility applications are listed here.
    555555
    556556The standard compilation procedure (<tt>./configure;make</tt>) will compile
    557 them, as well. 
    558 */
    559 
     557them, as well.
     558*/
     559

  • doc/lgf.dox

    r201 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    4444while a quoted token is a
    4545character sequence surrounded by double quotes, and it can also
    46 contain whitespaces and escape sequences. 
     46contain whitespaces and escape sequences.
    4747
    4848The \c \@nodes section describes a set of nodes and associated
    … …  
    7373\code
    7474 @arcs
    75               capacity
     75               capacity
    7676 1   2   16
    7777 1   3   12

  • doc/license.dox

    r40 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008

  • doc/mainpage.dox

    r40 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    4242\subsection howtoread How to read the documentation
    4343
    44 If you want to get a quick start and see the most important features then 
     44If you want to get a quick start and see the most important features then
    4545take a look at our \ref quicktour
    4646"Quick Tour to LEMON" which will guide you along.
    4747
    48 If you already feel like using our library, see the page that tells you 
     48If you already feel like using our library, see the page that tells you
    4949\ref getstart "How to start using LEMON".
    5050
    51 If you 
    52 want to see how LEMON works, see 
     51If you
     52want to see how LEMON works, see
    5353some \ref demoprograms "demo programs"!
    5454

  • doc/namespaces.dox

    r40 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008

  • doc/template.h

    r40 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008

  • lemon/arg_parser.cc

    r137 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    3939    for(Opts::iterator i=_opts.begin();i!=_opts.end();++i)
    4040      if(i->second.self_delete)
    41         switch(i->second.type) {
    42         case BOOL:
    43           delete i->second.bool_p;
    44           break;
    45         case STRING:
    46           delete i->second.string_p;
    47           break;
    48         case DOUBLE:
    49           delete i->second.double_p;
    50           break;
    51         case INTEGER:
    52           delete i->second.int_p;
    53           break;
    54         case UNKNOWN:
    55           break;
    56         case FUNC:
    57           break;
    58         }
    59   }
    60  
     41        switch(i->second.type) {
     42        case BOOL:
     43          delete i->second.bool_p;
     44          break;
     45        case STRING:
     46          delete i->second.string_p;
     47          break;
     48        case DOUBLE:
     49          delete i->second.double_p;
     50          break;
     51        case INTEGER:
     52          delete i->second.int_p;
     53          break;
     54        case UNKNOWN:
     55          break;
     56        case FUNC:
     57          break;
     58        }
     59  }
     60
    6161
    6262  ArgParser &ArgParser::intOption(const std::string &name,
    63                                const std::string &help,
    64                                int value, bool obl)
     63                               const std::string &help,
     64                               int value, bool obl)
    6565  {
    6666    ParData p;
    … …  
    7575
    7676  ArgParser &ArgParser::doubleOption(const std::string &name,
    77                                const std::string &help,
    78                                double value, bool obl)
     77                               const std::string &help,
     78                               double value, bool obl)
    7979  {
    8080    ParData p;
    … …  
    8989
    9090  ArgParser &ArgParser::boolOption(const std::string &name,
    91                                const std::string &help,
    92                                bool value, bool obl)
     91                               const std::string &help,
     92                               bool value, bool obl)
    9393  {
    9494    ParData p;
    … …  
    103103
    104104  ArgParser &ArgParser::stringOption(const std::string &name,
    105                                const std::string &help,
    106                                std::string value, bool obl)
     105                               const std::string &help,
     106                               std::string value, bool obl)
    107107  {
    108108    ParData p;
    … …  
    117117
    118118  ArgParser &ArgParser::refOption(const std::string &name,
    119                                const std::string &help,
    120                                int &ref, bool obl)
     119                               const std::string &help,
     120                               int &ref, bool obl)
    121121  {
    122122    ParData p;
    … …  
    162162
    163163  ArgParser &ArgParser::refOption(const std::string &name,
    164                                const std::string &help,
    165                                std::string &ref, bool obl)
     164                               const std::string &help,
     165                               std::string &ref, bool obl)
    166166  {
    167167    ParData p;
    … …  
    176176
    177177  ArgParser &ArgParser::funcOption(const std::string &name,
    178                                const std::string &help,
    179                                void (*func)(void *),void *data)
     178                               const std::string &help,
     179                               void (*func)(void *),void *data)
    180180  {
    181181    ParData p;
    … …  
    191191
    192192  ArgParser &ArgParser::optionGroup(const std::string &group,
    193                                     const std::string &opt)
     193                                    const std::string &opt)
    194194  {
    195195    Opts::iterator i = _opts.find(opt);
    196196    LEMON_ASSERT(i!=_opts.end(), "Unknown option: '"+opt+"'");
    197     LEMON_ASSERT(!(i->second.ingroup), 
     197    LEMON_ASSERT(!(i->second.ingroup),
    198198                 "Option already in option group: '"+opt+"'");
    199199    GroupData &g=_groups[group];
    … …  
    211211
    212212  ArgParser &ArgParser::synonym(const std::string &syn,
    213                                 const std::string &opt)
     213                                const std::string &opt)
    214214  {
    215215    Opts::iterator o = _opts.find(opt);
    … …  
    234234
    235235  ArgParser &ArgParser::other(const std::string &name,
    236                               const std::string &help)
     236                              const std::string &help)
    237237  {
    238238    _others_help.push_back(OtherArg(name,help));
    … …  
    245245    if(i->second.has_syn)
    246246      for(Opts::iterator j=_opts.begin();j!=_opts.end();++j)
    247         if(j->second.syn&&j->second.help==i->first)
    248           os << "|-" << j->first;
     247        if(j->second.syn&&j->second.help==i->first)
     248          os << "|-" << j->first;
    249249    switch(i->second.type) {
    250250    case STRING:
    … …  
    271271    }
    272272  }
    273    
     273
    274274  void ArgParser::showHelp(Opts::iterator i)
    275275  {
    … …  
    284284    if(i->help.size()==0) return;
    285285    std::cerr << "  " << i->name << std::endl
    286               << "     " << i->help << std::endl;
    287   }
    288    
     286              << "     " << i->help << std::endl;
     287  }
     288
    289289  void ArgParser::shortHelp()
    290290  {
    … …  
    300300      if(!g->second.mandatory) cstr << ']';
    301301      if(pos+cstr.str().size()>LINE_LEN) {
    302         std::cerr << std::endl << indent;
    303         pos=indent.size();
     302        std::cerr << std::endl << indent;
     303        pos=indent.size();
    304304      }
    305305      std::cerr << cstr.str();
    … …  
    308308    for(Opts::iterator i=_opts.begin();i!=_opts.end();++i)
    309309      if(!i->second.ingroup&&!i->second.syn) {
    310         std::ostringstream cstr;
    311         cstr << ' ';
    312         if(!i->second.mandatory) cstr << '[';
    313         show(cstr,i);
    314         if(!i->second.mandatory) cstr << ']';
    315         if(pos+cstr.str().size()>LINE_LEN) {
    316           std::cerr << std::endl << indent;
    317           pos=indent.size();
    318         }
    319         std::cerr << cstr.str();
    320         pos+=cstr.str().size();
     310        std::ostringstream cstr;
     311        cstr << ' ';
     312        if(!i->second.mandatory) cstr << '[';
     313        show(cstr,i);
     314        if(!i->second.mandatory) cstr << ']';
     315        if(pos+cstr.str().size()>LINE_LEN) {
     316          std::cerr << std::endl << indent;
     317          pos=indent.size();
     318        }
     319        std::cerr << cstr.str();
     320        pos+=cstr.str().size();
    321321      }
    322322    for(std::vector<OtherArg>::iterator i=_others_help.begin();
    323         i!=_others_help.end();++i)
     323        i!=_others_help.end();++i)
    324324      {
    325         std::ostringstream cstr;
    326         cstr << ' ' << i->name;
    327      
    328         if(pos+cstr.str().size()>LINE_LEN) {
    329           std::cerr << std::endl << indent;
    330           pos=indent.size();
    331         }
    332         std::cerr << cstr.str();
    333         pos+=cstr.str().size();
     325        std::ostringstream cstr;
     326        cstr << ' ' << i->name;
     327
     328        if(pos+cstr.str().size()>LINE_LEN) {
     329          std::cerr << std::endl << indent;
     330          pos=indent.size();
     331        }
     332        std::cerr << cstr.str();
     333        pos+=cstr.str().size();
    334334      }
    335335    std::cerr << std::endl;
    336336  }
    337    
     337
    338338  void ArgParser::showHelp()
    339339  {
    … …  
    341341    std::cerr << "Where:\n";
    342342    for(std::vector<OtherArg>::iterator i=_others_help.begin();
    343         i!=_others_help.end();++i) showHelp(i);
     343        i!=_others_help.end();++i) showHelp(i);
    344344    for(Opts::iterator i=_opts.begin();i!=_opts.end();++i) showHelp(i);
    345345    exit(1);
    346346  }
    347    
    348      
    349   void ArgParser::unknownOpt(std::string arg) 
     347
     348
     349  void ArgParser::unknownOpt(std::string arg)
    350350  {
    351351    std::cerr << "\nUnknown option: " << arg << "\n";
    … …  
    354354    exit(1);
    355355  }
    356    
    357   void ArgParser::requiresValue(std::string arg, OptType t) 
     356
     357  void ArgParser::requiresValue(std::string arg, OptType t)
    358358  {
    359359    std::cerr << "Argument '" << arg << "' requires a";
    … …  
    374374    showHelp();
    375375  }
    376    
     376
    377377
    378378  void ArgParser::checkMandatories()
    … …  
    380380    bool ok=true;
    381381    for(Opts::iterator i=_opts.begin();i!=_opts.end();++i)
    382       if(i->second.mandatory&&!i->second.set) 
    383         {
    384           if(ok)
    385             std::cerr << _command_name
    386                       << ": The following mandatory arguments are missing.\n";
    387           ok=false;
    388           showHelp(i);
    389         }
     382      if(i->second.mandatory&&!i->second.set)
     383        {
     384          if(ok)
     385            std::cerr << _command_name
     386                      << ": The following mandatory arguments are missing.\n";
     387          ok=false;
     388          showHelp(i);
     389        }
    390390    for(Groups::iterator i=_groups.begin();i!=_groups.end();++i)
    391391      if(i->second.mandatory||i->second.only_one)
    392         {
    393           int set=0;
    394           for(GroupData::Opts::iterator o=i->second.opts.begin();
    395               o!=i->second.opts.end();++o)
    396             if(_opts.find(*o)->second.set) ++set;
    397           if(i->second.mandatory&&!set) {
    398             std::cerr << _command_name
    399                       << ": At least one of the following arguments is mandatory.\n";
    400             ok=false;
    401             for(GroupData::Opts::iterator o=i->second.opts.begin();
    402                 o!=i->second.opts.end();++o)
    403               showHelp(_opts.find(*o));
    404           }
    405           if(i->second.only_one&&set>1) {
    406             std::cerr << _command_name
    407                       << ": At most one of the following arguments can be given.\n";
    408             ok=false;
    409             for(GroupData::Opts::iterator o=i->second.opts.begin();
    410                 o!=i->second.opts.end();++o)
    411               showHelp(_opts.find(*o));
    412           }
    413         }
     392        {
     393          int set=0;
     394          for(GroupData::Opts::iterator o=i->second.opts.begin();
     395              o!=i->second.opts.end();++o)
     396            if(_opts.find(*o)->second.set) ++set;
     397          if(i->second.mandatory&&!set) {
     398            std::cerr << _command_name
     399                      << ": At least one of the following arguments is mandatory.\n";
     400            ok=false;
     401            for(GroupData::Opts::iterator o=i->second.opts.begin();
     402                o!=i->second.opts.end();++o)
     403              showHelp(_opts.find(*o));
     404          }
     405          if(i->second.only_one&&set>1) {
     406            std::cerr << _command_name
     407                      << ": At most one of the following arguments can be given.\n";
     408            ok=false;
     409            for(GroupData::Opts::iterator o=i->second.opts.begin();
     410                o!=i->second.opts.end();++o)
     411              showHelp(_opts.find(*o));
     412          }
     413        }
    414414    if(!ok) {
    415415      std::cerr << "\nType '" << _command_name <<
    416         " --help' to obtain a short summary on the usage.\n\n";
     416        " --help' to obtain a short summary on the usage.\n\n";
    417417      exit(1);
    418418    }
    … …  
    424424      std::string arg(_argv[ar]);
    425425      if (arg[0] != '-' || arg.size() == 1) {
    426         _file_args.push_back(arg);
     426        _file_args.push_back(arg);
    427427      }
    428428      else {
    429         Opts::iterator i = _opts.find(arg.substr(1));
    430         if(i==_opts.end()) unknownOpt(arg);
    431         else {
    432           if(i->second.syn) i=_opts.find(i->second.help);
    433           ParData &p(i->second);
    434           if (p.type==BOOL) *p.bool_p=true;
    435           else if (p.type==FUNC) p.func_p.p(p.func_p.data);
    436           else if(++ar==_argc) requiresValue(arg, p.type);
    437           else {
    438             std::string val(_argv[ar]);
    439             std::istringstream vals(val);
    440             switch(p.type) {
    441             case STRING:
    442               *p.string_p=val;
    443               break;
    444             case INTEGER:
    445               vals >> *p.int_p;
    446               break;
    447             case DOUBLE:
    448               vals >> *p.double_p;
    449               break;
    450             default:
    451               break;
    452             }
    453             if(p.type!=STRING&&(!vals||!vals.eof()))
    454               requiresValue(arg, p.type);
    455           }
    456           p.set = true;
    457         }
     429        Opts::iterator i = _opts.find(arg.substr(1));
     430        if(i==_opts.end()) unknownOpt(arg);
     431        else {
     432          if(i->second.syn) i=_opts.find(i->second.help);
     433          ParData &p(i->second);
     434          if (p.type==BOOL) *p.bool_p=true;
     435          else if (p.type==FUNC) p.func_p.p(p.func_p.data);
     436          else if(++ar==_argc) requiresValue(arg, p.type);
     437          else {
     438            std::string val(_argv[ar]);
     439            std::istringstream vals(val);
     440            switch(p.type) {
     441            case STRING:
     442              *p.string_p=val;
     443              break;
     444            case INTEGER:
     445              vals >> *p.int_p;
     446              break;
     447            case DOUBLE:
     448              vals >> *p.double_p;
     449              break;
     450            default:
     451              break;
     452            }
     453            if(p.type!=STRING&&(!vals||!vals.eof()))
     454              requiresValue(arg, p.type);
     455          }
     456          p.set = true;
     457        }
    458458      }
    459459    }
    … …  
    461461
    462462    return *this;
    463   } 
     463  }
    464464
    465465}

  • lemon/arg_parser.h

    r204 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    4242  ///For a complete example see the \ref arg_parser_demo.cc demo file.
    4343  class ArgParser {
    44    
     44
    4545    static void _showHelp(void *p);
    4646  protected:
    47    
     47
    4848    int _argc;
    4949    const char **_argv;
    50    
     50
    5151    enum OptType { UNKNOWN=0, BOOL=1, STRING=2, DOUBLE=3, INTEGER=4, FUNC=5 };
    52    
     52
    5353    class ParData {
    5454    public:
    5555      union {
    56         bool *bool_p;
    57         int *int_p;
    58         double *double_p;
    59         std::string *string_p;
    60         struct {
    61           void (*p)(void *);
    62           void *data;
    63         } func_p;
    64          
     56        bool *bool_p;
     57        int *int_p;
     58        double *double_p;
     59        std::string *string_p;
     60        struct {
     61          void (*p)(void *);
     62          void *data;
     63        } func_p;
     64
    6565      };
    6666      std::string help;
    … …  
    7373      bool self_delete;
    7474      ParData() : mandatory(false), type(UNKNOWN), set(false), ingroup(false),
    75                   has_syn(false), syn(false), self_delete(false) {}
     75                  has_syn(false), syn(false), self_delete(false) {}
    7676    };
    7777
    … …  
    7979    Opts _opts;
    8080
    81     class GroupData 
     81    class GroupData
    8282    {
    8383    public:
    … …  
    8888      GroupData() :only_one(false), mandatory(false) {}
    8989    };
    90      
     90
    9191    typedef std::map<std::string,GroupData> Groups;
    9292    Groups _groups;
    … …  
    9999
    100100    };
    101      
     101
    102102    std::vector<OtherArg> _others_help;
    103103    std::vector<std::string> _file_args;
    104104    std::string _command_name;
    105105
    106    
     106
    107107  private:
    108108    //Bind a function to an option.
    … …  
    114114    //\param data Data to be passed to \c func
    115115    ArgParser &funcOption(const std::string &name,
    116                     const std::string &help,
    117                     void (*func)(void *),void *data);
    118    
     116                    const std::string &help,
     117                    void (*func)(void *),void *data);
     118
    119119  public:
    120120
    … …  
    137137    ///\param obl Indicate if the option is mandatory.
    138138    ArgParser &intOption(const std::string &name,
    139                     const std::string &help,
    140                     int value=0, bool obl=false);
     139                    const std::string &help,
     140                    int value=0, bool obl=false);
    141141
    142142    ///Add a new floating point type option
    … …  
    148148    ///\param obl Indicate if the option is mandatory.
    149149    ArgParser &doubleOption(const std::string &name,
    150                       const std::string &help,
    151                       double value=0, bool obl=false);
     150                      const std::string &help,
     151                      double value=0, bool obl=false);
    152152
    153153    ///Add a new bool type option
    … …  
    160160    ///\note A mandatory bool obtion is of very little use.
    161161    ArgParser &boolOption(const std::string &name,
    162                       const std::string &help,
    163                       bool value=false, bool obl=false);
     162                      const std::string &help,
     163                      bool value=false, bool obl=false);
    164164
    165165    ///Add a new string type option
    … …  
    171171    ///\param obl Indicate if the option is mandatory.
    172172    ArgParser &stringOption(const std::string &name,
    173                       const std::string &help,
    174                       std::string value="", bool obl=false);
     173                      const std::string &help,
     174                      std::string value="", bool obl=false);
    175175
    176176    ///Give help string for non-parsed arguments.
    … …  
    180180    ///\c help gives a more detailed description.
    181181    ArgParser &other(const std::string &name,
    182                      const std::string &help="");
    183    
     182                     const std::string &help="");
     183
    184184    ///@}
    185185
    … …  
    198198    ///\retval ref The value of the argument will be written to this variable.
    199199    ArgParser &refOption(const std::string &name,
    200                     const std::string &help,
    201                     int &ref, bool obl=false);
     200                    const std::string &help,
     201                    int &ref, bool obl=false);
    202202
    203203    ///Add a new floating type option with a storage reference
    … …  
    209209    ///\retval ref The value of the argument will be written to this variable.
    210210    ArgParser &refOption(const std::string &name,
    211                       const std::string &help,
    212                       double &ref, bool obl=false);
     211                      const std::string &help,
     212                      double &ref, bool obl=false);
    213213
    214214    ///Add a new bool type option with a storage reference
    … …  
    221221    ///\note A mandatory bool obtion is of very little use.
    222222    ArgParser &refOption(const std::string &name,
    223                       const std::string &help,
    224                       bool &ref, bool obl=false);
     223                      const std::string &help,
     224                      bool &ref, bool obl=false);
    225225
    226226    ///Add a new string type option with a storage reference
    … …  
    232232    ///\retval ref The value of the argument will be written to this variable.
    233233    ArgParser &refOption(const std::string &name,
    234                       const std::string &help,
    235                       std::string &ref, bool obl=false);
    236    
     234                      const std::string &help,
     235                      std::string &ref, bool obl=false);
     236
    237237    ///@}
    238238
    239239    ///\name Option Groups and Synonyms
    240240    ///
    241    
     241
    242242    ///@{
    243243
    … …  
    249249    ///\param opt The option name.
    250250    ArgParser &optionGroup(const std::string &group,
    251                            const std::string &opt);
     251                           const std::string &opt);
    252252
    253253    ///Make the members of a group exclusive
    … …  
    256256    ///given at the same time.
    257257    ArgParser &onlyOneGroup(const std::string &group);
    258  
     258
    259259    ///Make a group mandatory
    260260
    … …  
    262262    ///must be given.
    263263    ArgParser &mandatoryGroup(const std::string &group);
    264    
     264
    265265    ///Create synonym to an option
    266266
    … …  
    268268    ///option \c opt.
    269269    ArgParser &synonym(const std::string &syn,
    270                            const std::string &opt);
    271    
     270                           const std::string &opt);
     271
    272272    ///@}
    273273
    … …  
    283283    void requiresValue(std::string arg, OptType t);
    284284    void checkMandatories();
    285    
     285
    286286    ///Start the parsing process
    287287    ArgParser &parse();
    288288
    289289    /// Synonym for parse()
    290     ArgParser &run() 
     290    ArgParser &run()
    291291    {
    292292      return parse();
    293293    }
    294    
     294
    295295    ///Give back the command name (the 0th argument)
    296296    const std::string &commandName() { return _command_name; }
    297297
    298298    ///Check if an opion has been given to the command.
    299     bool given(std::string op) 
     299    bool given(std::string op)
    300300    {
    301301      Opts::iterator i = _opts.find(op);
    … …  
    305305
    306306    ///Magic type for operator[]
    307    
     307
    308308    ///This is the type of the return value of ArgParser::operator[]().
    309309    ///It automatically converts to \c int, \c double, \c bool or
    310310    ///\c std::string if the type of the option matches, otherwise it
    311311    ///throws an exception (i.e. it performs runtime type checking).
    312     class RefType 
     312    class RefType
    313313    {
    314314      ArgParser &_parser;
    … …  
    318318      RefType(ArgParser &p,const std::string &n) :_parser(p),_name(n) {}
    319319      ///\e
    320       operator bool() 
     320      operator bool()
    321321      {
    322         Opts::iterator i = _parser._opts.find(_name);
    323         LEMON_ASSERT(i!=_parser._opts.end(),
    324                      std::string()+"Unkown option: '"+_name+"'");
    325         LEMON_ASSERT(i->second.type==ArgParser::BOOL,
    326                      std::string()+"'"+_name+"' is a bool option");
    327         return *(i->second.bool_p);
     322        Opts::iterator i = _parser._opts.find(_name);
     323        LEMON_ASSERT(i!=_parser._opts.end(),
     324                     std::string()+"Unkown option: '"+_name+"'");
     325        LEMON_ASSERT(i->second.type==ArgParser::BOOL,
     326                     std::string()+"'"+_name+"' is a bool option");
     327        return *(i->second.bool_p);
    328328      }
    329329      ///\e
    330330      operator std::string()
    331331      {
    332         Opts::iterator i = _parser._opts.find(_name);
    333         LEMON_ASSERT(i!=_parser._opts.end(),
    334                      std::string()+"Unkown option: '"+_name+"'");
    335         LEMON_ASSERT(i->second.type==ArgParser::STRING,
    336                      std::string()+"'"+_name+"' is a string option");
    337         return *(i->second.string_p);
     332        Opts::iterator i = _parser._opts.find(_name);
     333        LEMON_ASSERT(i!=_parser._opts.end(),
     334                     std::string()+"Unkown option: '"+_name+"'");
     335        LEMON_ASSERT(i->second.type==ArgParser::STRING,
     336                     std::string()+"'"+_name+"' is a string option");
     337        return *(i->second.string_p);
    338338      }
    339339      ///\e
    340       operator double() 
     340      operator double()
    341341      {
    342         Opts::iterator i = _parser._opts.find(_name);
    343         LEMON_ASSERT(i!=_parser._opts.end(),
    344                      std::string()+"Unkown option: '"+_name+"'");
    345         LEMON_ASSERT(i->second.type==ArgParser::DOUBLE ||
    346                      i->second.type==ArgParser::INTEGER,
    347                      std::string()+"'"+_name+"' is a floating point option");
    348         return i->second.type==ArgParser::DOUBLE ?
    349           *(i->second.double_p) : *(i->second.int_p);
     342        Opts::iterator i = _parser._opts.find(_name);
     343        LEMON_ASSERT(i!=_parser._opts.end(),
     344                     std::string()+"Unkown option: '"+_name+"'");
     345        LEMON_ASSERT(i->second.type==ArgParser::DOUBLE ||
     346                     i->second.type==ArgParser::INTEGER,
     347                     std::string()+"'"+_name+"' is a floating point option");
     348        return i->second.type==ArgParser::DOUBLE ?
     349          *(i->second.double_p) : *(i->second.int_p);
    350350      }
    351351      ///\e
    352       operator int() 
     352      operator int()
    353353      {
    354         Opts::iterator i = _parser._opts.find(_name);
    355         LEMON_ASSERT(i!=_parser._opts.end(),
    356                      std::string()+"Unkown option: '"+_name+"'");
    357         LEMON_ASSERT(i->second.type==ArgParser::INTEGER,
    358                      std::string()+"'"+_name+"' is an integer option");
    359         return *(i->second.int_p);
     354        Opts::iterator i = _parser._opts.find(_name);
     355        LEMON_ASSERT(i!=_parser._opts.end(),
     356                     std::string()+"Unkown option: '"+_name+"'");
     357        LEMON_ASSERT(i->second.type==ArgParser::INTEGER,
     358                     std::string()+"'"+_name+"' is an integer option");
     359        return *(i->second.int_p);
    360360      }
    361361
    … …  
    363363
    364364    ///Give back the value of an option
    365    
     365
    366366    ///Give back the value of an option.
    367367    ///\sa RefType
    … …  
    369369    {
    370370      return RefType(*this, n);
    371     }   
     371    }
    372372
    373373    ///Give back the non-option type arguments.
    … …  
    376376    ///not starting with a '-' character.
    377377    std::vector<std::string> &files() { return _file_args; }
    378  
     378
    379379  };
    380380}

  • lemon/assert.h

    r142 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    2929
    3030  inline void assert_fail_log(const char *file, int line, const char *function,
    31                               const char *message, const char *assertion)
     31                              const char *message, const char *assertion)
    3232  {
    3333    std::cerr << file << ":" << line << ": ";
    … …  
    4141
    4242  inline void assert_fail_abort(const char *file, int line,
    43                                 const char *function, const char* message,
    44                                 const char *assertion)
     43                                const char *function, const char* message,
     44                                const char *assertion)
    4545  {
    4646    assert_fail_log(file, line, function, message, assertion);
    … …  
    4949
    5050  namespace _assert_bits {
    51    
    52    
     51
     52
    5353    inline const char* cstringify(const std::string& str) {
    5454      return str.c_str();
    … …  
    5757    inline const char* cstringify(const char* str) {
    5858      return str;
    59     }   
     59    }
    6060  }
    6161}
    … …  
    6767#undef LEMON_DEBUG
    6868
    69 #if (defined(LEMON_ASSERT_LOG) ? 1 : 0) +               \
    70   (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +               \
     69#if (defined(LEMON_ASSERT_LOG) ? 1 : 0) +                \
     70  (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +                \
    7171  (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) > 1
    7272#error "LEMON assertion system is not set properly"
    7373#endif
    7474
    75 #if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) +              \
    76      (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +            \
    77      (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 ||     \
    78      defined(LEMON_ENABLE_ASSERTS)) &&                  \
    79   (defined(LEMON_DISABLE_ASSERTS) ||                    \
     75#if ((defined(LEMON_ASSERT_LOG) ? 1 : 0) +                \
     76     (defined(LEMON_ASSERT_ABORT) ? 1 : 0) +                \
     77     (defined(LEMON_ASSERT_CUSTOM) ? 1 : 0) == 1 ||        \
     78     defined(LEMON_ENABLE_ASSERTS)) &&                        \
     79  (defined(LEMON_DISABLE_ASSERTS) ||                        \
    8080   defined(NDEBUG))
    8181#error "LEMON assertion system is not set properly"
    … …  
    137137/// \endcode
    138138/// The checking is also disabled when the standard macro \c NDEBUG is defined.
    139 /// 
     139///
    140140/// The LEMON assertion system has a wide range of customization
    141141/// properties. As a default behaviour the failed assertion prints a
    142142/// short log message to the standard error and aborts the execution.
    143143///
    144 /// The following modes can be used in the assertion system: 
     144/// The following modes can be used in the assertion system:
    145145///
    146146/// - \c LEMON_ASSERT_LOG The failed assertion prints a short log
    … …  
    156156///   \endcode
    157157///   The name of the function should be defined as the \c
    158 ///   LEMON_CUSTOM_ASSERT_HANDLER macro name. 
     158///   LEMON_CUSTOM_ASSERT_HANDLER macro name.
    159159///   \code
    160160///     #define LEMON_CUSTOM_ASSERT_HANDLER custom_assert_handler
    … …  
    167167/// \ref lemon/assert.h "assert.h" file is reincluded, then the
    168168/// behaviour is changed appropiately to the new settings.
    169 #  define LEMON_ASSERT(exp, msg)                                        \
    170   (static_cast<void> (!!(exp) ? 0 : (                                   \
    171     LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                            \
    172                          LEMON_FUNCTION_NAME,                           \
    173                         ::lemon::_assert_bits::cstringify(msg), #exp), 0)))
     169#  define LEMON_ASSERT(exp, msg)                                        \
     170  (static_cast<void> (!!(exp) ? 0 : (                                        \
     171    LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                                \
     172                         LEMON_FUNCTION_NAME,                                \
     173                        ::lemon::_assert_bits::cstringify(msg), #exp), 0)))
    174174
    175175/// \ingroup exceptions
    … …  
    183183/// \endcode
    184184///
    185 /// \see LEMON_ASSERT 
    186 #  define LEMON_FIXME(msg)                                              \
    187   (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \
    188                         ::lemon::_assert_bits::cstringify(msg),         \
    189                         static_cast<const char*>(0)))
     185/// \see LEMON_ASSERT
     186#  define LEMON_FIXME(msg)                                                \
     187  (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \
     188                        ::lemon::_assert_bits::cstringify(msg),                \
     189                        static_cast<const char*>(0)))
    190190
    191191/// \ingroup exceptions
    … …  
    211211/// macro.
    212212///
    213 /// \see LEMON_ASSERT 
    214 #  define LEMON_DEBUG(exp, msg)                                         \
    215   (static_cast<void> (!!(exp) ? 0 : (                                   \
     213/// \see LEMON_ASSERT
     214#  define LEMON_DEBUG(exp, msg)                                                \
     215  (static_cast<void> (!!(exp) ? 0 : (                                        \
    216216    LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                            \
    217                          LEMON_FUNCTION_NAME,                           \
    218                         ::lemon::_assert_bits::cstringify(msg), #exp), 0)))
     217                         LEMON_FUNCTION_NAME,                                \
     218                        ::lemon::_assert_bits::cstringify(msg), #exp), 0)))
    219219
    220220#else
    … …  
    225225#    define LEMON_DEBUG(exp, msg) (static_cast<void>(0))
    226226#  else
    227 #    define LEMON_ASSERT(exp, msg)                                      \
    228        (static_cast<void> (!!(exp) ? 0 : (                              \
     227#    define LEMON_ASSERT(exp, msg)                                        \
     228       (static_cast<void> (!!(exp) ? 0 : (                                \
    229229        LEMON_ASSERT_HANDLER(__FILE__, __LINE__,                        \
    230                              LEMON_FUNCTION_NAME,                       \
    231                              ::lemon::_assert_bits::cstringify(msg),    \
    232                              #exp), 0)))
    233 #    define LEMON_FIXME(msg)                                            \
    234        (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,   \
    235                              ::lemon::_assert_bits::cstringify(msg),    \
    236                              static_cast<const char*>(0)))
     230                             LEMON_FUNCTION_NAME,                        \
     231                             ::lemon::_assert_bits::cstringify(msg),        \
     232                             #exp), 0)))
     233#    define LEMON_FIXME(msg)                                                \
     234       (LEMON_ASSERT_HANDLER(__FILE__, __LINE__, LEMON_FUNCTION_NAME,        \
     235                             ::lemon::_assert_bits::cstringify(msg),        \
     236                             static_cast<const char*>(0)))
    237237
    238238#    if LEMON_ENABLE_DEBUG
    … …  
    241241           LEMON_ASSERT_HANDLER(__FILE__, __LINE__,  \
    242242                                LEMON_FUNCTION_NAME, \
    243                                 ::lemon::_assert_bits::cstringify(msg), \
    244                                 #exp), 0)))
     243                                ::lemon::_assert_bits::cstringify(msg),        \
     244                                #exp), 0)))
    245245#    else
    246246#      define LEMON_DEBUG(exp, msg) (static_cast<void>(0))

  • lemon/base.cc

    r49 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008

  • lemon/bfs.h

    r158 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    3434
    3535
    36  
     36
    3737  ///Default traits class of Bfs class.
    3838
    … …  
    4242  struct BfsDefaultTraits
    4343  {
    44     ///The digraph type the algorithm runs on. 
     44    ///The digraph type the algorithm runs on.
    4545    typedef GR Digraph;
    4646    ///\brief The type of the map that stores the last
    4747    ///arcs of the shortest paths.
    48     /// 
     48    ///
    4949    ///The type of the map that stores the last
    5050    ///arcs of the shortest paths.
    … …  
    5353    typedef typename Digraph::template NodeMap<typename GR::Arc> PredMap;
    5454    ///Instantiates a PredMap.
    55  
    56     ///This function instantiates a \ref PredMap. 
     55
     56    ///This function instantiates a \ref PredMap.
    5757    ///\param G is the digraph, to which we would like to define the PredMap.
    5858    ///\todo The digraph alone may be insufficient to initialize
    59     static PredMap *createPredMap(const GR &G) 
     59    static PredMap *createPredMap(const GR &G)
    6060    {
    6161      return new PredMap(G);
    6262    }
    6363    ///The type of the map that indicates which nodes are processed.
    64  
     64
    6565    ///The type of the map that indicates which nodes are processed.
    6666    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    6868    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    6969    ///Instantiates a ProcessedMap.
    70  
    71     ///This function instantiates a \ref ProcessedMap. 
     70
     71    ///This function instantiates a \ref ProcessedMap.
    7272    ///\param g is the digraph, to which
    7373    ///we would like to define the \ref ProcessedMap
    … …  
    8181    }
    8282    ///The type of the map that indicates which nodes are reached.
    83  
     83
    8484    ///The type of the map that indicates which nodes are reached.
    8585    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    8787    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8888    ///Instantiates a ReachedMap.
    89  
    90     ///This function instantiates a \ref ReachedMap. 
     89
     90    ///This function instantiates a \ref ReachedMap.
    9191    ///\param G is the digraph, to which
    9292    ///we would like to define the \ref ReachedMap.
    … …  
    9696    }
    9797    ///The type of the map that stores the dists of the nodes.
    98  
     98
    9999    ///The type of the map that stores the dists of the nodes.
    100100    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    102102    typedef typename Digraph::template NodeMap<int> DistMap;
    103103    ///Instantiates a DistMap.
    104  
    105     ///This function instantiates a \ref DistMap. 
     104
     105    ///This function instantiates a \ref DistMap.
    106106    ///\param G is the digraph, to which we would like to define the \ref DistMap
    107107    static DistMap *createDistMap(const GR &G)
    … …  
    110110    }
    111111  };
    112  
     112
    113113  ///%BFS algorithm class.
    114  
     114
    115115  ///\ingroup search
    116116  ///This class provides an efficient implementation of the %BFS algorithm.
    … …  
    127127#ifdef DOXYGEN
    128128  template <typename GR,
    129             typename TR>
     129            typename TR>
    130130#else
    131131  template <typename GR=ListDigraph,
    132             typename TR=BfsDefaultTraits<GR> >
     132            typename TR=BfsDefaultTraits<GR> >
    133133#endif
    134134  class Bfs {
    … …  
    143143    public:
    144144      virtual const char* what() const throw() {
    145         return "lemon::Bfs::UninitializedParameter";
     145        return "lemon::Bfs::UninitializedParameter";
    146146      }
    147147    };
    … …  
    150150    ///The type of the underlying digraph.
    151151    typedef typename TR::Digraph Digraph;
    152    
     152
    153153    ///\brief The type of the map that stores the last
    154154    ///arcs of the shortest paths.
    … …  
    191191
    192192    ///Creates the maps if necessary.
    193    
     193
    194194    ///\todo Better memory allocation (instead of new).
    195     void create_maps() 
     195    void create_maps()
    196196    {
    197197      if(!_pred) {
    198         local_pred = true;
    199         _pred = Traits::createPredMap(*G);
     198        local_pred = true;
     199        _pred = Traits::createPredMap(*G);
    200200      }
    201201      if(!_dist) {
    202         local_dist = true;
    203         _dist = Traits::createDistMap(*G);
     202        local_dist = true;
     203        _dist = Traits::createDistMap(*G);
    204204      }
    205205      if(!_reached) {
    206         local_reached = true;
    207         _reached = Traits::createReachedMap(*G);
     206        local_reached = true;
     207        _reached = Traits::createReachedMap(*G);
    208208      }
    209209      if(!_processed) {
    210         local_processed = true;
    211         _processed = Traits::createProcessedMap(*G);
     210        local_processed = true;
     211        _processed = Traits::createProcessedMap(*G);
    212212      }
    213213    }
    214214
    215215  protected:
    216    
     216
    217217    Bfs() {}
    218    
     218
    219219  public:
    220  
     220
    221221    typedef Bfs Create;
    222222
    … …  
    228228    struct DefPredMapTraits : public Traits {
    229229      typedef T PredMap;
    230       static PredMap *createPredMap(const Digraph &) 
     230      static PredMap *createPredMap(const Digraph &)
    231231      {
    232         throw UninitializedParameter();
     232        throw UninitializedParameter();
    233233      }
    234234    };
    … …  
    239239    ///
    240240    template <class T>
    241     struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > { 
     241    struct DefPredMap : public Bfs< Digraph, DefPredMapTraits<T> > {
    242242      typedef Bfs< Digraph, DefPredMapTraits<T> > Create;
    243243    };
    244    
     244
    245245    template <class T>
    246246    struct DefDistMapTraits : public Traits {
    247247      typedef T DistMap;
    248       static DistMap *createDistMap(const Digraph &) 
     248      static DistMap *createDistMap(const Digraph &)
    249249      {
    250         throw UninitializedParameter();
     250        throw UninitializedParameter();
    251251      }
    252252    };
    … …  
    257257    ///
    258258    template <class T>
    259     struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > { 
     259    struct DefDistMap : public Bfs< Digraph, DefDistMapTraits<T> > {
    260260      typedef Bfs< Digraph, DefDistMapTraits<T> > Create;
    261261    };
    262    
     262
    263263    template <class T>
    264264    struct DefReachedMapTraits : public Traits {
    265265      typedef T ReachedMap;
    266       static ReachedMap *createReachedMap(const Digraph &) 
     266      static ReachedMap *createReachedMap(const Digraph &)
    267267      {
    268         throw UninitializedParameter();
     268        throw UninitializedParameter();
    269269      }
    270270    };
    … …  
    275275    ///
    276276    template <class T>
    277     struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > { 
     277    struct DefReachedMap : public Bfs< Digraph, DefReachedMapTraits<T> > {
    278278      typedef Bfs< Digraph, DefReachedMapTraits<T> > Create;
    279279    };
    280    
     280
    281281    template <class T>
    282282    struct DefProcessedMapTraits : public Traits {
    283283      typedef T ProcessedMap;
    284       static ProcessedMap *createProcessedMap(const Digraph &) 
     284      static ProcessedMap *createProcessedMap(const Digraph &)
    285285      {
    286         throw UninitializedParameter();
     286        throw UninitializedParameter();
    287287      }
    288288    };
    … …  
    296296      typedef Bfs< Digraph, DefProcessedMapTraits<T> > Create;
    297297    };
    298    
     298
    299299    struct DefDigraphProcessedMapTraits : public Traits {
    300300      typedef typename Digraph::template NodeMap<bool> ProcessedMap;
    301       static ProcessedMap *createProcessedMap(const Digraph &G) 
     301      static ProcessedMap *createProcessedMap(const Digraph &G)
    302302      {
    303         return new ProcessedMap(G);
     303        return new ProcessedMap(G);
    304304      }
    305305    };
    … …  
    312312    template <class T>
    313313    struct DefProcessedMapToBeDefaultMap :
    314       public Bfs< Digraph, DefDigraphProcessedMapTraits> { 
     314      public Bfs< Digraph, DefDigraphProcessedMapTraits> {
    315315      typedef Bfs< Digraph, DefDigraphProcessedMapTraits> Create;
    316316    };
    317    
     317
    318318    ///@}
    319319
    320   public:     
    321    
     320  public:
     321
    322322    ///Constructor.
    323    
     323
    324324    ///\param _G the digraph the algorithm will run on.
    325325    ///
    … …  
    331331      _processed(NULL), local_processed(false)
    332332    { }
    333    
     333
    334334    ///Destructor.
    335     ~Bfs() 
     335    ~Bfs()
    336336    {
    337337      if(local_pred) delete _pred;
    … …  
    348348    ///automatically allocated map, of course.
    349349    ///\return <tt> (*this) </tt>
    350     Bfs &predMap(PredMap &m) 
     350    Bfs &predMap(PredMap &m)
    351351    {
    352352      if(local_pred) {
    353         delete _pred;
    354         local_pred=false;
     353        delete _pred;
     354        local_pred=false;
    355355      }
    356356      _pred = &m;
    … …  
    365365    ///automatically allocated map, of course.
    366366    ///\return <tt> (*this) </tt>
    367     Bfs &reachedMap(ReachedMap &m) 
     367    Bfs &reachedMap(ReachedMap &m)
    368368    {
    369369      if(local_reached) {
    370         delete _reached;
    371         local_reached=false;
     370        delete _reached;
     371        local_reached=false;
    372372      }
    373373      _reached = &m;
    … …  
    382382    ///automatically allocated map, of course.
    383383    ///\return <tt> (*this) </tt>
    384     Bfs &processedMap(ProcessedMap &m) 
     384    Bfs &processedMap(ProcessedMap &m)
    385385    {
    386386      if(local_processed) {
    387         delete _processed;
    388         local_processed=false;
     387        delete _processed;
     388        local_processed=false;
    389389      }
    390390      _processed = &m;
    … …  
    399399    ///automatically allocated map, of course.
    400400    ///\return <tt> (*this) </tt>
    401     Bfs &distMap(DistMap &m) 
     401    Bfs &distMap(DistMap &m)
    402402    {
    403403      if(local_dist) {
    404         delete _dist;
    405         local_dist=false;
     404        delete _dist;
     405        local_dist=false;
    406406      }
    407407      _dist = &m;
    … …  
    433433      _curr_dist=1;
    434434      for ( NodeIt u(*G) ; u!=INVALID ; ++u ) {
    435         _pred->set(u,INVALID);
    436         _reached->set(u,false);
    437         _processed->set(u,false);
    438       }
    439     }
    440    
     435        _pred->set(u,INVALID);
     436        _reached->set(u,false);
     437        _processed->set(u,false);
     438      }
     439    }
     440
    441441    ///Adds a new source node.
    442442
    … …  
    446446    {
    447447      if(!(*_reached)[s])
    448         {
    449           _reached->set(s,true);
    450           _pred->set(s,INVALID);
    451           _dist->set(s,0);
    452           _queue[_queue_head++]=s;
    453           _queue_next_dist=_queue_head;
    454         }
    455     }
    456    
     448        {
     449          _reached->set(s,true);
     450          _pred->set(s,INVALID);
     451          _dist->set(s,0);
     452          _queue[_queue_head++]=s;
     453          _queue_next_dist=_queue_head;
     454        }
     455    }
     456
    457457    ///Processes the next node.
    458458
    … …  
    465465    {
    466466      if(_queue_tail==_queue_next_dist) {
    467         _curr_dist++;
    468         _queue_next_dist=_queue_head;
     467        _curr_dist++;
     468        _queue_next_dist=_queue_head;
    469469      }
    470470      Node n=_queue[_queue_tail++];
    … …  
    472472      Node m;
    473473      for(OutArcIt e(*G,n);e!=INVALID;++e)
    474         if(!(*_reached)[m=G->target(e)]) {
    475           _queue[_queue_head++]=m;
    476           _reached->set(m,true);
    477           _pred->set(m,e);
    478           _dist->set(m,_curr_dist);
    479         }
     474        if(!(*_reached)[m=G->target(e)]) {
     475          _queue[_queue_head++]=m;
     476          _reached->set(m,true);
     477          _pred->set(m,e);
     478          _dist->set(m,_curr_dist);
     479        }
    480480      return n;
    481481    }
    … …  
    496496    {
    497497      if(_queue_tail==_queue_next_dist) {
    498         _curr_dist++;
    499         _queue_next_dist=_queue_head;
     498        _curr_dist++;
     499        _queue_next_dist=_queue_head;
    500500      }
    501501      Node n=_queue[_queue_tail++];
    … …  
    503503      Node m;
    504504      for(OutArcIt e(*G,n);e!=INVALID;++e)
    505         if(!(*_reached)[m=G->target(e)]) {
    506           _queue[_queue_head++]=m;
    507           _reached->set(m,true);
    508           _pred->set(m,e);
    509           _dist->set(m,_curr_dist);
     505        if(!(*_reached)[m=G->target(e)]) {
     506          _queue[_queue_head++]=m;
     507          _reached->set(m,true);
     508          _pred->set(m,e);
     509          _dist->set(m,_curr_dist);
    510510          reach = reach || (target == m);
    511         }
     511        }
    512512      return n;
    513513    }
    … …  
    529529    {
    530530      if(_queue_tail==_queue_next_dist) {
    531         _curr_dist++;
    532         _queue_next_dist=_queue_head;
     531        _curr_dist++;
     532        _queue_next_dist=_queue_head;
    533533      }
    534534      Node n=_queue[_queue_tail++];
    … …  
    536536      Node m;
    537537      for(OutArcIt e(*G,n);e!=INVALID;++e)
    538         if(!(*_reached)[m=G->target(e)]) {
    539           _queue[_queue_head++]=m;
    540           _reached->set(m,true);
    541           _pred->set(m,e);
    542           _dist->set(m,_curr_dist);
    543           if (nm[m] && rnode == INVALID) rnode = m;
    544         }
     538        if(!(*_reached)[m=G->target(e)]) {
     539          _queue[_queue_head++]=m;
     540          _reached->set(m,true);
     541          _pred->set(m,e);
     542          _dist->set(m,_curr_dist);
     543          if (nm[m] && rnode == INVALID) rnode = m;
     544        }
    545545      return n;
    546546    }
    547      
     547
    548548    ///Next node to be processed.
    549549
    … …  
    553553    /// empty.
    554554    Node nextNode()
    555     { 
     555    {
    556556      return _queue_tail<_queue_head?_queue[_queue_tail]:INVALID;
    557557    }
    558  
     558
    559559    ///\brief Returns \c false if there are nodes
    560560    ///to be processed in the queue
    … …  
    564564    bool emptyQueue() { return _queue_tail==_queue_head; }
    565565    ///Returns the number of the nodes to be processed.
    566    
     566
    567567    ///Returns the number of the nodes to be processed in the queue.
    568568    int queueSize() { return _queue_head-_queue_tail; }
    569    
     569
    570570    ///Executes the algorithm.
    571571
    … …  
    585585      while ( !emptyQueue() ) processNextNode();
    586586    }
    587    
     587
    588588    ///Executes the algorithm until \c dest is reached.
    589589
    … …  
    603603      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
    604604    }
    605    
     605
    606606    ///Executes the algorithm until a condition is met.
    607607
    … …  
    622622      Node rnode = INVALID;
    623623      while ( !emptyQueue() && rnode == INVALID ) {
    624         processNextNode(nm, rnode);
     624        processNextNode(nm, rnode);
    625625      }
    626626      return rnode;
    627627    }
    628    
     628
    629629    ///Runs %BFS algorithm from node \c s.
    630    
     630
    631631    ///This method runs the %BFS algorithm from a root node \c s
    632632    ///in order to
    … …  
    647647      start();
    648648    }
    649    
     649
    650650    ///Finds the shortest path between \c s and \c t.
    651    
     651
    652652    ///Finds the shortest path between \c s and \c t.
    653653    ///
    … …  
    667667      return reached(t) ? _curr_dist : 0;
    668668    }
    669    
     669
    670670    ///@}
    671671
    … …  
    675675    ///Before the use of these functions,
    676676    ///either run() or start() must be calleb.
    677    
     677
    678678    ///@{
    679679
    … …  
    681681
    682682    ///Gives back the shortest path.
    683    
     683
    684684    ///Gives back the shortest path.
    685685    ///\pre The \c t should be reachable from the source.
    686     Path path(Node t) 
     686    Path path(Node t)
    687687    {
    688688      return Path(*G, *_pred, t);
    … …  
    723723    ///using this function.
    724724    Node predNode(Node v) const { return (*_pred)[v]==INVALID ? INVALID:
    725                                   G->source((*_pred)[v]); }
    726    
     725                                  G->source((*_pred)[v]); }
     726
    727727    ///Returns a reference to the NodeMap of distances.
    728728
    … …  
    731731    ///be called before using this function.
    732732    const DistMap &distMap() const { return *_dist;}
    733  
     733
    734734    ///Returns a reference to the shortest path tree map.
    735735
    … …  
    739739    ///must be called before using this function.
    740740    const PredMap &predMap() const { return *_pred;}
    741  
     741
    742742    ///Checks if a node is reachable from the root.
    743743
    … …  
    748748    ///
    749749    bool reached(Node v) { return (*_reached)[v]; }
    750    
     750
    751751    ///@}
    752752  };
    … …  
    759759  struct BfsWizardDefaultTraits
    760760  {
    761     ///The digraph type the algorithm runs on. 
     761    ///The digraph type the algorithm runs on.
    762762    typedef GR Digraph;
    763763    ///\brief The type of the map that stores the last
    764764    ///arcs of the shortest paths.
    765     /// 
     765    ///
    766766    ///The type of the map that stores the last
    767767    ///arcs of the shortest paths.
    … …  
    770770    typedef NullMap<typename Digraph::Node,typename GR::Arc> PredMap;
    771771    ///Instantiates a PredMap.
    772  
    773     ///This function instantiates a \ref PredMap. 
     772
     773    ///This function instantiates a \ref PredMap.
    774774    ///\param g is the digraph, to which we would like to define the PredMap.
    775775    ///\todo The digraph alone may be insufficient to initialize
    776776#ifdef DOXYGEN
    777     static PredMap *createPredMap(const GR &g) 
     777    static PredMap *createPredMap(const GR &g)
    778778#else
    779     static PredMap *createPredMap(const GR &) 
     779    static PredMap *createPredMap(const GR &)
    780780#endif
    781781    {
    … …  
    784784
    785785    ///The type of the map that indicates which nodes are processed.
    786  
     786
    787787    ///The type of the map that indicates which nodes are processed.
    788788    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    790790    typedef NullMap<typename Digraph::Node,bool> ProcessedMap;
    791791    ///Instantiates a ProcessedMap.
    792  
    793     ///This function instantiates a \ref ProcessedMap. 
     792
     793    ///This function instantiates a \ref ProcessedMap.
    794794    ///\param g is the digraph, to which
    795795    ///we would like to define the \ref ProcessedMap
    … …  
    803803    }
    804804    ///The type of the map that indicates which nodes are reached.
    805  
     805
    806806    ///The type of the map that indicates which nodes are reached.
    807807    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    809809    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    810810    ///Instantiates a ReachedMap.
    811  
    812     ///This function instantiates a \ref ReachedMap. 
     811
     812    ///This function instantiates a \ref ReachedMap.
    813813    ///\param G is the digraph, to which
    814814    ///we would like to define the \ref ReachedMap.
    … …  
    818818    }
    819819    ///The type of the map that stores the dists of the nodes.
    820  
     820
    821821    ///The type of the map that stores the dists of the nodes.
    822822    ///It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    824824    typedef NullMap<typename Digraph::Node,int> DistMap;
    825825    ///Instantiates a DistMap.
    826  
    827     ///This function instantiates a \ref DistMap. 
     826
     827    ///This function instantiates a \ref DistMap.
    828828    ///\param g is the digraph, to which we would like to define the \ref DistMap
    829829#ifdef DOXYGEN
    … …  
    836836    }
    837837  };
    838  
     838
    839839  /// Default traits used by \ref BfsWizard
    840840
    … …  
    866866    ///Pointer to the source node.
    867867    Node _source;
    868    
     868
    869869    public:
    870870    /// Constructor.
    871    
     871
    872872    /// This constructor does not require parameters, therefore it initiates
    873873    /// all of the attributes to default values (0, INVALID).
    874874    BfsWizardBase() : _g(0), _reached(0), _processed(0), _pred(0),
    875                            _dist(0), _source(INVALID) {}
     875                           _dist(0), _source(INVALID) {}
    876876
    877877    /// Constructor.
    878    
     878
    879879    /// This constructor requires some parameters,
    880880    /// listed in the parameters list.
    … …  
    883883    /// \param s is the initial value of  \ref _source
    884884    BfsWizardBase(const GR &g, Node s=INVALID) :
    885       _g(reinterpret_cast<void*>(const_cast<GR*>(&g))), 
     885      _g(reinterpret_cast<void*>(const_cast<GR*>(&g))),
    886886      _reached(0), _processed(0), _pred(0), _dist(0), _source(s) {}
    887887
    888888  };
    889  
     889
    890890  /// A class to make the usage of Bfs algorithm easier
    891891
    … …  
    922922    //\e
    923923    typedef typename Digraph::OutArcIt OutArcIt;
    924    
     924
    925925    ///\brief The type of the map that stores
    926926    ///the reached nodes
    … …  
    952952
    953953    ///Runs Bfs algorithm from a given node.
    954    
     954
    955955    ///Runs Bfs algorithm from a given node.
    956956    ///The node can be given by the \ref source function.
    … …  
    960960      Bfs<Digraph,TR> alg(*reinterpret_cast<const Digraph*>(Base::_g));
    961961      if(Base::_reached)
    962         alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
    963       if(Base::_processed) 
     962        alg.reachedMap(*reinterpret_cast<ReachedMap*>(Base::_reached));
     963      if(Base::_processed)
    964964        alg.processedMap(*reinterpret_cast<ProcessedMap*>(Base::_processed));
    965       if(Base::_pred) 
     965      if(Base::_pred)
    966966        alg.predMap(*reinterpret_cast<PredMap*>(Base::_pred));
    967       if(Base::_dist) 
     967      if(Base::_dist)
    968968        alg.distMap(*reinterpret_cast<DistMap*>(Base::_dist));
    969969      alg.run(Base::_source);
    … …  
    986986      DefPredMapBase(const TR &b) : TR(b) {}
    987987    };
    988    
     988
    989989    ///\brief \ref named-templ-param "Named parameter"
    990990    ///function for setting PredMap
    … …  
    994994    ///
    995995    template<class T>
    996     BfsWizard<DefPredMapBase<T> > predMap(const T &t) 
     996    BfsWizard<DefPredMapBase<T> > predMap(const T &t)
    997997    {
    998998      Base::_pred=reinterpret_cast<void*>(const_cast<T*>(&t));
    999999      return BfsWizard<DefPredMapBase<T> >(*this);
    10001000    }
    1001    
    1002  
     1001
     1002
    10031003    template<class T>
    10041004    struct DefReachedMapBase : public Base {
    … …  
    10071007      DefReachedMapBase(const TR &b) : TR(b) {}
    10081008    };
    1009    
     1009
    10101010    ///\brief \ref named-templ-param "Named parameter"
    10111011    ///function for setting ReachedMap
    … …  
    10151015    ///
    10161016    template<class T>
    1017     BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t) 
     1017    BfsWizard<DefReachedMapBase<T> > reachedMap(const T &t)
    10181018    {
    10191019      Base::_reached=reinterpret_cast<void*>(const_cast<T*>(&t));
    10201020      return BfsWizard<DefReachedMapBase<T> >(*this);
    10211021    }
    1022    
     1022
    10231023
    10241024    template<class T>
    … …  
    10281028      DefProcessedMapBase(const TR &b) : TR(b) {}
    10291029    };
    1030    
     1030
    10311031    ///\brief \ref named-templ-param "Named parameter"
    10321032    ///function for setting ProcessedMap
    … …  
    10361036    ///
    10371037    template<class T>
    1038     BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t) 
     1038    BfsWizard<DefProcessedMapBase<T> > processedMap(const T &t)
    10391039    {
    10401040      Base::_processed=reinterpret_cast<void*>(const_cast<T*>(&t));
    10411041      return BfsWizard<DefProcessedMapBase<T> >(*this);
    10421042    }
    1043    
    1044    
     1043
     1044
    10451045    template<class T>
    10461046    struct DefDistMapBase : public Base {
    … …  
    10491049      DefDistMapBase(const TR &b) : TR(b) {}
    10501050    };
    1051    
     1051
    10521052    ///\brief \ref named-templ-param "Named parameter"
    10531053    ///function for setting DistMap type
    … …  
    10571057    ///
    10581058    template<class T>
    1059     BfsWizard<DefDistMapBase<T> > distMap(const T &t) 
     1059    BfsWizard<DefDistMapBase<T> > distMap(const T &t)
    10601060    {
    10611061      Base::_dist=reinterpret_cast<void*>(const_cast<T*>(&t));
    10621062      return BfsWizard<DefDistMapBase<T> >(*this);
    10631063    }
    1064    
     1064
    10651065    /// Sets the source node, from which the Bfs algorithm runs.
    10661066
    10671067    /// Sets the source node, from which the Bfs algorithm runs.
    10681068    /// \param s is the source node.
    1069     BfsWizard<TR> &source(Node s) 
     1069    BfsWizard<TR> &source(Node s)
    10701070    {
    10711071      Base::_source=s;
    10721072      return *this;
    10731073    }
    1074    
     1074
    10751075  };
    1076  
     1076
    10771077  ///Function type interface for Bfs algorithm.
    10781078
    … …  
    11011101#ifdef DOXYGEN
    11021102  /// \brief Visitor class for bfs.
    1103   /// 
     1103  ///
    11041104  /// This class defines the interface of the BfsVisit events, and
    11051105  /// it could be the base of a real Visitor class.
    … …  
    11101110    typedef typename Digraph::Node Node;
    11111111    /// \brief Called when the arc reach a node.
    1112     /// 
     1112    ///
    11131113    /// It is called when the bfs find an arc which target is not
    11141114    /// reached yet.
    11151115    void discover(const Arc& arc) {}
    11161116    /// \brief Called when the node reached first time.
    1117     /// 
     1117    ///
    11181118    /// It is Called when the node reached first time.
    11191119    void reach(const Node& node) {}
    1120     /// \brief Called when the arc examined but target of the arc 
     1120    /// \brief Called when the arc examined but target of the arc
    11211121    /// already discovered.
    1122     /// 
    1123     /// It called when the arc examined but the target of the arc 
     1122    ///
     1123    /// It called when the arc examined but the target of the arc
    11241124    /// already discovered.
    11251125    void examine(const Arc& arc) {}
    11261126    /// \brief Called for the source node of the bfs.
    1127     /// 
     1127    ///
    11281128    /// It is called for the source node of the bfs.
    11291129    void start(const Node& node) {}
    11301130    /// \brief Called when the node processed.
    1131     /// 
     1131    ///
    11321132    /// It is Called when the node processed.
    11331133    void process(const Node& node) {}
    … …  
    11481148    struct Constraints {
    11491149      void constraints() {
    1150         Arc arc;
    1151         Node node;
    1152         visitor.discover(arc);
    1153         visitor.reach(node);
    1154         visitor.examine(arc);
    1155         visitor.start(node);
     1150        Arc arc;
     1151        Node node;
     1152        visitor.discover(arc);
     1153        visitor.reach(node);
     1154        visitor.examine(arc);
     1155        visitor.start(node);
    11561156        visitor.process(node);
    11571157      }
    … …  
    11681168  struct BfsVisitDefaultTraits {
    11691169
    1170     /// \brief The digraph type the algorithm runs on. 
     1170    /// \brief The digraph type the algorithm runs on.
    11711171    typedef _Digraph Digraph;
    11721172
    11731173    /// \brief The type of the map that indicates which nodes are reached.
    1174     /// 
     1174    ///
    11751175    /// The type of the map that indicates which nodes are reached.
    11761176    /// It must meet the \ref concepts::WriteMap "WriteMap" concept.
    … …  
    11801180    /// \brief Instantiates a ReachedMap.
    11811181    ///
    1182     /// This function instantiates a \ref ReachedMap. 
     1182    /// This function instantiates a \ref ReachedMap.
    11831183    /// \param digraph is the digraph, to which
    11841184    /// we would like to define the \ref ReachedMap.
    … …  
    11901190
    11911191  /// \ingroup search
    1192   /// 
     1192  ///
    11931193  /// \brief %BFS Visit algorithm class.
    1194   /// 
     1194  ///
    11951195  /// This class provides an efficient implementation of the %BFS algorithm
    11961196  /// with visitor interface.
    … …  
    11981198  /// The %BfsVisit class provides an alternative interface to the Bfs
    11991199  /// class. It works with callback mechanism, the BfsVisit object calls
    1200   /// on every bfs event the \c Visitor class member functions. 
     1200  /// on every bfs event the \c Visitor class member functions.
    12011201  ///
    12021202  /// \tparam _Digraph The digraph type the algorithm runs on. The default value is
    12031203  /// \ref ListDigraph. The value of _Digraph is not used directly by Bfs, it
    12041204  /// is only passed to \ref BfsDefaultTraits.
    1205   /// \tparam _Visitor The Visitor object for the algorithm. The 
     1205  /// \tparam _Visitor The Visitor object for the algorithm. The
    12061206  /// \ref BfsVisitor "BfsVisitor<_Digraph>" is an empty Visitor which
    12071207  /// does not observe the Bfs events. If you want to observe the bfs
    12081208  /// events you should implement your own Visitor class.
    1209   /// \tparam _Traits Traits class to set various data types used by the 
     1209  /// \tparam _Traits Traits class to set various data types used by the
    12101210  /// algorithm. The default traits class is
    12111211  /// \ref BfsVisitDefaultTraits "BfsVisitDefaultTraits<_Digraph>".
    … …  
    12161216#else
    12171217  template <typename _Digraph = ListDigraph,
    1218             typename _Visitor = BfsVisitor<_Digraph>,
    1219             typename _Traits = BfsDefaultTraits<_Digraph> >
     1218            typename _Visitor = BfsVisitor<_Digraph>,
     1219            typename _Traits = BfsDefaultTraits<_Digraph> >
    12201220#endif
    12211221  class BfsVisit {
    12221222  public:
    1223    
     1223
    12241224    /// \brief \ref Exception for uninitialized parameters.
    12251225    ///
    … …  
    12281228    class UninitializedParameter : public lemon::UninitializedParameter {
    12291229    public:
    1230       virtual const char* what() const throw() 
     1230      virtual const char* what() const throw()
    12311231      {
    1232         return "lemon::BfsVisit::UninitializedParameter";
     1232        return "lemon::BfsVisit::UninitializedParameter";
    12331233      }
    12341234    };
    … …  
    12671267    void create_maps() {
    12681268      if(!_reached) {
    1269         local_reached = true;
    1270         _reached = Traits::createReachedMap(*_digraph);
     1269        local_reached = true;
     1270        _reached = Traits::createReachedMap(*_digraph);
    12711271      }
    12721272    }
    … …  
    12751275
    12761276    BfsVisit() {}
    1277    
     1277
    12781278  public:
    12791279
    … …  
    12871287      typedef T ReachedMap;
    12881288      static ReachedMap *createReachedMap(const Digraph &digraph) {
    1289         throw UninitializedParameter();
    1290       }
    1291     };
    1292     /// \brief \ref named-templ-param "Named parameter" for setting 
     1289        throw UninitializedParameter();
     1290      }
     1291    };
     1292    /// \brief \ref named-templ-param "Named parameter" for setting
    12931293    /// ReachedMap type
    12941294    ///
    … …  
    12961296    template <class T>
    12971297    struct DefReachedMap : public BfsVisit< Digraph, Visitor,
    1298                                             DefReachedMapTraits<T> > {
     1298                                            DefReachedMapTraits<T> > {
    12991299      typedef BfsVisit< Digraph, Visitor, DefReachedMapTraits<T> > Create;
    13001300    };
    13011301    ///@}
    13021302
    1303   public:     
    1304    
     1303  public:
     1304
    13051305    /// \brief Constructor.
    13061306    ///
    … …  
    13101310    /// \param visitor The visitor of the algorithm.
    13111311    ///
    1312     BfsVisit(const Digraph& digraph, Visitor& visitor) 
     1312    BfsVisit(const Digraph& digraph, Visitor& visitor)
    13131313      : _digraph(&digraph), _visitor(&visitor),
    1314         _reached(0), local_reached(false) {}
    1315    
     1314        _reached(0), local_reached(false) {}
     1315
    13161316    /// \brief Destructor.
    13171317    ///
    … …  
    13301330    BfsVisit &reachedMap(ReachedMap &m) {
    13311331      if(local_reached) {
    1332         delete _reached;
    1333         local_reached = false;
     1332        delete _reached;
     1333        local_reached = false;
    13341334      }
    13351335      _reached = &m;
    … …  
    13581358      _list_front = _list_back = -1;
    13591359      for (NodeIt u(*_digraph) ; u != INVALID ; ++u) {
    1360         _reached->set(u, false);
    1361       }
    1362     }
    1363    
     1360        _reached->set(u, false);
     1361      }
     1362    }
     1363
    13641364    /// \brief Adds a new source node.
    13651365    ///
    … …  
    13671367    void addSource(Node s) {
    13681368      if(!(*_reached)[s]) {
    1369           _reached->set(s,true);
    1370           _visitor->start(s);
    1371           _visitor->reach(s);
     1369          _reached->set(s,true);
     1370          _visitor->start(s);
     1371          _visitor->reach(s);
    13721372          _list[++_list_back] = s;
    1373         }
    1374     }
    1375    
     1373        }
     1374    }
     1375
    13761376    /// \brief Processes the next node.
    13771377    ///
    … …  
    13811381    ///
    13821382    /// \pre The queue must not be empty!
    1383     Node processNextNode() { 
     1383    Node processNextNode() {
    13841384      Node n = _list[++_list_front];
    13851385      _visitor->process(n);
    … …  
    14681468    /// \return The next node to be processed or INVALID if the stack is
    14691469    /// empty.
    1470     Node nextNode() { 
     1470    Node nextNode() {
    14711471      return _list_front != _list_back ? _list[_list_front + 1] : INVALID;
    14721472    }
    … …  
    14831483    /// Returns the number of the nodes to be processed in the queue.
    14841484    int queueSize() { return _list_back - _list_front; }
    1485    
     1485
    14861486    /// \brief Executes the algorithm.
    14871487    ///
    … …  
    14931493      while ( !emptyQueue() ) processNextNode();
    14941494    }
    1495    
     1495
    14961496    /// \brief Executes the algorithm until \c dest is reached.
    14971497    ///
    … …  
    15041504      while ( !emptyQueue() && !reach ) processNextNode(dest, reach);
    15051505    }
    1506    
     1506
    15071507    /// \brief Executes the algorithm until a condition is met.
    15081508    ///
    … …  
    15221522      Node rnode = INVALID;
    15231523      while ( !emptyQueue() && rnode == INVALID ) {
    1524         processNextNode(nm, rnode);
     1524        processNextNode(nm, rnode);
    15251525      }
    15261526      return rnode;
    … …  
    15431543
    15441544    /// \brief Runs %BFSVisit algorithm to visit all nodes in the digraph.
    1545     ///   
     1545    ///
    15461546    /// This method runs the %BFS algorithm in order to
    15471547    /// compute the %BFS path to each node. The algorithm computes

  • lemon/bin_heap.h

    r157 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    4949  ///\sa Dijkstra
    5050  template <typename _Prio, typename _ItemIntMap,
    51             typename _Compare = std::less<_Prio> >
     51            typename _Compare = std::less<_Prio> >
    5252  class BinHeap {
    5353
    … …  
    9191    /// should be PRE_HEAP (-1) for each element.
    9292    explicit BinHeap(ItemIntMap &_iim) : iim(_iim) {}
    93    
     93
    9494    /// \brief The constructor.
    9595    ///
    … …  
    100100    ///
    101101    /// \param _comp The comparator function object.
    102     BinHeap(ItemIntMap &_iim, const Compare &_comp) 
     102    BinHeap(ItemIntMap &_iim, const Compare &_comp)
    103103      : iim(_iim), comp(_comp) {}
    104104
    … …  
    108108    /// \brief Returns the number of items stored in the heap.
    109109    int size() const { return data.size(); }
    110    
     110
    111111    /// \brief Checks if the heap stores no items.
    112112    ///
    … …  
    115115
    116116    /// \brief Make empty this heap.
    117     /// 
     117    ///
    118118    /// Make empty this heap. It does not change the cross reference map.
    119119    /// If you want to reuse what is not surely empty you should first clear
    120120    /// the heap and after that you should set the cross reference map for
    121121    /// each item to \c PRE_HEAP.
    122     void clear() { 
    123       data.clear(); 
     122    void clear() {
     123      data.clear();
    124124    }
    125125
    … …  
    135135      int par = parent(hole);
    136136      while( hole>0 && less(p,data[par]) ) {
    137         move(data[par],hole);
    138         hole = par;
    139         par = parent(hole);
     137        move(data[par],hole);
     138        hole = par;
     139        par = parent(hole);
    140140      }
    141141      move(p, hole);
    … …  
    146146      int child = second_child(hole);
    147147      while(child < length) {
    148         if( less(data[child-1], data[child]) ) {
    149           --child;
    150         }
    151         if( !less(data[child], p) )
    152           goto ok;
    153         move(data[child], hole);
    154         hole = child;
    155         child = second_child(hole);
     148        if( less(data[child-1], data[child]) ) {
     149          --child;
     150        }
     151        if( !less(data[child], p) )
     152          goto ok;
     153        move(data[child], hole);
     154        hole = child;
     155        child = second_child(hole);
    156156      }
    157157      child--;
    158158      if( child<length && less(data[child], p) ) {
    159         move(data[child], hole);
    160         hole=child;
     159        move(data[child], hole);
     160        hole=child;
    161161      }
    162162    ok:
    … …  
    182182
    183183    /// \brief Insert an item into the heap with the given heap.
    184     ///   
    185     /// Adds \c i to the heap with priority \c p. 
     184    ///
     185    /// Adds \c i to the heap with priority \c p.
    186186    /// \param i The item to insert.
    187187    /// \param p The priority of the item.
    … …  
    191191    ///
    192192    /// This method returns the item with minimum priority relative to \c
    193     /// Compare. 
    194     /// \pre The heap must be nonempty. 
     193    /// Compare.
     194    /// \pre The heap must be nonempty.
    195195    Item top() const {
    196196      return data[0].first;
    … …  
    208208    ///
    209209    /// This method deletes the item with minimum priority relative to \c
    210     /// Compare from the heap. 
    211     /// \pre The heap must be non-empty. 
     210    /// Compare from the heap.
     211    /// \pre The heap must be non-empty.
    212212    void pop() {
    213213      int n = data.size()-1;
    214214      iim.set(data[0].first, POST_HEAP);
    215215      if (n > 0) {
    216         bubble_down(0, data[n], n);
     216        bubble_down(0, data[n], n);
    217217      }
    218218      data.pop_back();
    … …  
    229229      iim.set(data[h].first, POST_HEAP);
    230230      if( h < n ) {
    231         if ( bubble_up(h, data[n]) == h) {
    232           bubble_down(h, data[n], n);
    233         }
     231        if ( bubble_up(h, data[n]) == h) {
     232          bubble_down(h, data[n], n);
     233        }
    234234      }
    235235      data.pop_back();
    236236    }
    237237
    238    
     238
    239239    /// \brief Returns the priority of \c i.
    240240    ///
    241     /// This function returns the priority of item \c i. 
     241    /// This function returns the priority of item \c i.
    242242    /// \pre \c i must be in the heap.
    243243    /// \param i The item.
    … …  
    247247    }
    248248
    249     /// \brief \c i gets to the heap with priority \c p independently 
     249    /// \brief \c i gets to the heap with priority \c p independently
    250250    /// if \c i was already there.
    251251    ///
    … …  
    257257      int idx = iim[i];
    258258      if( idx < 0 ) {
    259         push(i,p);
     259        push(i,p);
    260260      }
    261261      else if( comp(p, data[idx].second) ) {
    262         bubble_up(idx, Pair(i,p));
     262        bubble_up(idx, Pair(i,p));
    263263      }
    264264      else {
    265         bubble_down(idx, Pair(i,p), data.size());
     265        bubble_down(idx, Pair(i,p), data.size());
    266266      }
    267267    }
    … …  
    278278      bubble_up(idx, Pair(i,p));
    279279    }
    280    
     280
    281281    /// \brief Increases the priority of \c i to \c p.
    282282    ///
    283     /// This method sets the priority of item \c i to \c p. 
     283    /// This method sets the priority of item \c i to \c p.
    284284    /// \pre \c i must be stored in the heap with priority at most \c
    285285    /// p relative to \c Compare.
    … …  
    291291    }
    292292
    293     /// \brief Returns if \c item is in, has already been in, or has 
     293    /// \brief Returns if \c item is in, has already been in, or has
    294294    /// never been in the heap.
    295295    ///
    … …  
    302302      int s = iim[i];
    303303      if( s>=0 )
    304         s=0;
     304        s=0;
    305305      return State(s);
    306306    }
    … …  
    312312    /// better time complexity.
    313313    /// \param i The item.
    314     /// \param st The state. It should not be \c IN_HEAP. 
     314    /// \param st The state. It should not be \c IN_HEAP.
    315315    void state(const Item& i, State st) {
    316316      switch (st) {
    … …  
    341341
    342342  }; // class BinHeap
    343  
     343
    344344} // namespace lemon
    345345

  • lemon/bits/alteration_notifier.h

    r157 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    3333  /// \ingroup graphbits
    3434  ///
    35   /// \brief Notifier class to notify observes about alterations in 
     35  /// \brief Notifier class to notify observes about alterations in
    3636  /// a container.
    3737  ///
    … …  
    5050  /// alteration of the graph.
    5151  ///
    52   /// This class provides an interface to the container. The \e first() and \e 
     52  /// This class provides an interface to the container. The \e first() and \e
    5353  /// next() member functions make possible to iterate on the keys of the
    5454  /// container. The \e id() function returns an integer id for each key.
    … …  
    6161  /// from the graph. If all items are erased from the graph or from an empty
    6262  /// graph a new graph is builded then it can be signaled with the
    63   /// clear() and build() members. Important rule that if we erase items 
     63  /// clear() and build() members. Important rule that if we erase items
    6464  /// from graph we should first signal the alteration and after that erase
    6565  /// them from the container, on the other way on item addition we should
    … …  
    6969  /// \e ObserverBase nested class. The signals can be handled with
    7070  /// overriding the virtual functions defined in the base class.  The
    71   /// observer base can be attached to the notifier with the 
     71  /// observer base can be attached to the notifier with the
    7272  /// \e attach() member and can be detached with detach() function. The
    7373  /// alteration handlers should not call any function which signals
    … …  
    8080  /// be rolled back by calling the \e erase() or \e clear()
    8181  /// functions. Thence the \e erase() and \e clear() should not throw
    82   /// exception. Actullay, it can be throw only 
     82  /// exception. Actullay, it can be throw only
    8383  /// \ref AlterationObserver::ImmediateDetach ImmediateDetach
    8484  /// exception which detach the observer from the notifier.
    … …  
    8686  /// There are some place when the alteration observing is not completly
    8787  /// reliable. If we want to carry out the node degree in the graph
    88   /// as in the \ref InDegMap and we use the reverseEdge that cause 
     88  /// as in the \ref InDegMap and we use the reverseEdge that cause
    8989  /// unreliable functionality. Because the alteration observing signals
    9090  /// only erasing and adding but not the reversing it will stores bad
    … …  
    105105    typedef _Item Item;
    106106
    107     /// \brief Exception which can be called from \e clear() and 
     107    /// \brief Exception which can be called from \e clear() and
    108108    /// \e erase().
    109109    ///
    … …  
    128128    /// The build() and clear() members are to notify the observer
    129129    /// about the container is built from an empty container or
    130     /// is cleared to an empty container. 
     130    /// is cleared to an empty container.
    131131
    132132    class ObserverBase {
    … …  
    139139      ///
    140140      /// Default constructor for ObserverBase.
    141       /// 
     141      ///
    142142      ObserverBase() : _notifier(0) {}
    143143
    … …  
    152152      ///
    153153      /// Constructor which attach the obserever to the same notifier as
    154       /// the other observer is attached to. 
     154      /// the other observer is attached to.
    155155      ObserverBase(const ObserverBase& copy) {
    156         if (copy.attached()) {
     156        if (copy.attached()) {
    157157          attach(*copy.notifier());
    158         }
    159       }
    160        
     158        }
     159      }
     160
    161161      /// \brief Destructor
    162162      virtual ~ObserverBase() {
    … …  
    171171      ///
    172172      void attach(AlterationNotifier& nf) {
    173         nf.attach(*this);
    174       }
    175      
     173        nf.attach(*this);
     174      }
     175
    176176      /// \brief Detaches the observer into an AlterationNotifier.
    177177      ///
    … …  
    181181        _notifier->detach(*this);
    182182      }
    183      
    184       /// \brief Gives back a pointer to the notifier which the map 
     183
     184      /// \brief Gives back a pointer to the notifier which the map
    185185      /// attached into.
    186186      ///
    … …  
    189189      ///
    190190      Notifier* notifier() const { return const_cast<Notifier*>(_notifier); }
    191      
     191
    192192      /// Gives back true when the observer is attached into a notifier.
    193193      bool attached() const { return _notifier != 0; }
    … …  
    198198
    199199    protected:
    200      
     200
    201201      Notifier* _notifier;
    202202      typename std::list<ObserverBase*>::iterator _index;
    … …  
    210210      virtual void add(const Item&) = 0;
    211211
    212       /// \brief The member function to notificate the observer about 
     212      /// \brief The member function to notificate the observer about
    213213      /// more item is added to the container.
    214214      ///
    … …  
    223223      /// The erase() member function notificates the observer about an
    224224      /// item is erased from the container. It have to be overrided in
    225       /// the subclasses.       
     225      /// the subclasses.
    226226      virtual void erase(const Item&) = 0;
    227227
    228       /// \brief The member function to notificate the observer about 
     228      /// \brief The member function to notificate the observer about
    229229      /// more item is erased from the container.
    230230      ///
    … …  
    248248      /// The clear() member function notificates the observer about all
    249249      /// items are erased from the container. It have to be overrided in
    250       /// the subclasses.     
     250      /// the subclasses.
    251251      virtual void clear() = 0;
    252252
    253253    };
    254        
     254
    255255  protected:
    256256
    257257    const Container* container;
    258258
    259     typedef std::list<ObserverBase*> Observers; 
     259    typedef std::list<ObserverBase*> Observers;
    260260    Observers _observers;
    261261
    262                
     262
    263263  public:
    264264
    265265    /// \brief Default constructor.
    266266    ///
    267     /// The default constructor of the AlterationNotifier. 
     267    /// The default constructor of the AlterationNotifier.
    268268    /// It creates an empty notifier.
    269     AlterationNotifier() 
     269    AlterationNotifier()
    270270      : container(0) {}
    271271
    … …  
    273273    ///
    274274    /// Constructor with the observed container parameter.
    275     AlterationNotifier(const Container& _container) 
     275    AlterationNotifier(const Container& _container)
    276276      : container(&_container) {}
    277277
    278     /// \brief Copy Constructor of the AlterationNotifier. 
    279     ///
    280     /// Copy constructor of the AlterationNotifier. 
     278    /// \brief Copy Constructor of the AlterationNotifier.
     279    ///
     280    /// Copy constructor of the AlterationNotifier.
    281281    /// It creates only an empty notifier because the copiable
    282282    /// notifier's observers have to be registered still into that notifier.
    283     AlterationNotifier(const AlterationNotifier& _notifier) 
     283    AlterationNotifier(const AlterationNotifier& _notifier)
    284284      : container(_notifier.container) {}
    285285
    286286    /// \brief Destructor.
    287     ///         
     287    ///
    288288    /// Destructor of the AlterationNotifier.
    289289    ///
    … …  
    291291      typename Observers::iterator it;
    292292      for (it = _observers.begin(); it != _observers.end(); ++it) {
    293         (*it)->_notifier = 0;
     293        (*it)->_notifier = 0;
    294294      }
    295295    }
    … …  
    339339      return container->maxId(Item());
    340340    }
    341                
     341
    342342  protected:
    343343
    … …  
    345345      observer._index = _observers.insert(_observers.begin(), &observer);
    346346      observer._notifier = this;
    347     } 
     347    }
    348348
    349349    void detach(ObserverBase& observer) {
    … …  
    354354
    355355  public:
    356        
    357     /// \brief Notifies all the registed observers about an item added to 
    358     /// the container.
    359     ///
    360     /// It notifies all the registed observers about an item added to 
    361     /// the container.
    362     /// 
     356
     357    /// \brief Notifies all the registed observers about an item added to
     358    /// the container.
     359    ///
     360    /// It notifies all the registed observers about an item added to
     361    /// the container.
     362    ///
    363363    void add(const Item& item) {
    364364      typename Observers::reverse_iterator it;
    … …  
    374374        throw;
    375375      }
    376     }   
    377 
    378     /// \brief Notifies all the registed observers about more item added to 
    379     /// the container.
    380     ///
    381     /// It notifies all the registed observers about more item added to 
    382     /// the container.
    383     /// 
     376    }
     377
     378    /// \brief Notifies all the registed observers about more item added to
     379    /// the container.
     380    ///
     381    /// It notifies all the registed observers about more item added to
     382    /// the container.
     383    ///
    384384    void add(const std::vector<Item>& items) {
    385385      typename Observers::reverse_iterator it;
    … …  
    395395        throw;
    396396      }
    397     }   
    398 
    399     /// \brief Notifies all the registed observers about an item erased from 
    400     /// the container.
    401     /// 
    402     /// It notifies all the registed observers about an item erased from 
    403     /// the container.
    404     /// 
     397    }
     398
     399    /// \brief Notifies all the registed observers about an item erased from
     400    /// the container.
     401    ///
     402    /// It notifies all the registed observers about an item erased from
     403    /// the container.
     404    ///
    405405    void erase(const Item& item) throw() {
    406406      typename Observers::iterator it = _observers.begin();
    … …  
    417417    }
    418418
    419     /// \brief Notifies all the registed observers about more item erased 
     419    /// \brief Notifies all the registed observers about more item erased
    420420    /// from the container.
    421     /// 
    422     /// It notifies all the registed observers about more item erased from 
    423     /// the container.
    424     /// 
     421    ///
     422    /// It notifies all the registed observers about more item erased from
     423    /// the container.
     424    ///
    425425    void erase(const std::vector<Item>& items) {
    426426      typename Observers::iterator it = _observers.begin();
    … …  
    437437    }
    438438
    439     /// \brief Notifies all the registed observers about the container is 
     439    /// \brief Notifies all the registed observers about the container is
    440440    /// built.
    441     ///         
     441    ///
    442442    /// Notifies all the registed observers about the container is built
    443443    /// from an empty container.
    … …  
    457457    }
    458458
    459     /// \brief Notifies all the registed observers about all items are 
     459    /// \brief Notifies all the registed observers about all items are
    460460    /// erased.
    461461    ///

  • lemon/bits/array_map.h

    r107 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    3939  /// The ArrayMap template class is graph map structure what
    4040  /// automatically updates the map when a key is added to or erased from
    41   /// the map. This map uses the allocators to implement 
     41  /// the map. This map uses the allocators to implement
    4242  /// the container functionality.
    4343  ///
    … …  
    4545  /// the Value type of the map.
    4646  template <typename _Graph, typename _Item, typename _Value>
    47   class ArrayMap 
     47  class ArrayMap
    4848    : public ItemSetTraits<_Graph, _Item>::ItemNotifier::ObserverBase {
    4949  public:
    50     /// The graph type of the maps. 
     50    /// The graph type of the maps.
    5151    typedef _Graph Graph;
    5252    /// The item type of the map.
    … …  
    7070    /// The MapBase of the Map which imlements the core regisitry function.
    7171    typedef typename Notifier::ObserverBase Parent;
    72                
     72
    7373  private:
    7474    typedef std::allocator<Value> Allocator;
    … …  
    8585      Item it;
    8686      for (nf->first(it); it != INVALID; nf->next(it)) {
    87         int id = nf->id(it);;
    88         allocator.construct(&(values[id]), Value());
    89       }                                                         
    90     }
    91 
    92     /// \brief Constructor to use default value to initialize the map. 
    93     ///
    94     /// It constructs a map and initialize all of the the map. 
     87        int id = nf->id(it);;
     88        allocator.construct(&(values[id]), Value());
     89      }
     90    }
     91
     92    /// \brief Constructor to use default value to initialize the map.
     93    ///
     94    /// It constructs a map and initialize all of the the map.
    9595    ArrayMap(const Graph& graph, const Value& value) {
    9696      Parent::attach(graph.notifier(Item()));
    … …  
    9999      Item it;
    100100      for (nf->first(it); it != INVALID; nf->next(it)) {
    101         int id = nf->id(it);;
    102         allocator.construct(&(values[id]), value);
    103       }                                                         
     101        int id = nf->id(it);;
     102        allocator.construct(&(values[id]), value);
     103      }
    104104    }
    105105
    106106    /// \brief Constructor to copy a map of the same map type.
    107107    ///
    108     /// Constructor to copy a map of the same map type.     
     108    /// Constructor to copy a map of the same map type.
    109109    ArrayMap(const ArrayMap& copy) : Parent() {
    110110      if (copy.attached()) {
    111         attach(*copy.notifier());
     111        attach(*copy.notifier());
    112112      }
    113113      capacity = copy.capacity;
    … …  
    117117      Item it;
    118118      for (nf->first(it); it != INVALID; nf->next(it)) {
    119         int id = nf->id(it);;
    120         allocator.construct(&(values[id]), copy.values[id]);
     119        int id = nf->id(it);;
     120        allocator.construct(&(values[id]), copy.values[id]);
    121121      }
    122122    }
    … …  
    125125    ///
    126126    /// This operator assigns for each item in the map the
    127     /// value mapped to the same item in the copied map. 
     127    /// value mapped to the same item in the copied map.
    128128    /// The parameter map should be indiced with the same
    129129    /// itemset because this assign operator does not change
    130     /// the container of the map. 
     130    /// the container of the map.
    131131    ArrayMap& operator=(const ArrayMap& cmap) {
    132132      return operator=<ArrayMap>(cmap);
    … …  
    139139    /// concecpt and could be indiced by the current item set of
    140140    /// the NodeMap. In this case the value for each item
    141     /// is assigned by the value of the given ReadMap. 
     141    /// is assigned by the value of the given ReadMap.
    142142    template <typename CMap>
    143143    ArrayMap& operator=(const CMap& cmap) {
    … …  
    152152
    153153    /// \brief The destructor of the map.
    154     ///     
     154    ///
    155155    /// The destructor of the map.
    156     virtual ~ArrayMap() {     
     156    virtual ~ArrayMap() {
    157157      if (attached()) {
    158         clear();
    159         detach();
    160       }
    161     }
    162                
     158        clear();
     159        detach();
     160      }
     161    }
     162
    163163  protected:
    164164
    … …  
    169169  public:
    170170
    171     /// \brief The subscript operator. 
     171    /// \brief The subscript operator.
    172172    ///
    173173    /// The subscript operator. The map can be subscripted by the
    174     /// actual keys of the graph. 
     174    /// actual keys of the graph.
    175175    Value& operator[](const Key& key) {
    176176      int id = Parent::notifier()->id(key);
    177177      return values[id];
    178     } 
    179                
     178    }
     179
    180180    /// \brief The const subscript operator.
    181181    ///
    182182    /// The const subscript operator. The map can be subscripted by the
    183     /// actual keys of the graph. 
     183    /// actual keys of the graph.
    184184    const Value& operator[](const Key& key) const {
    185185      int id = Parent::notifier()->id(key);
    … …  
    188188
    189189    /// \brief Setter function of the map.
    190     /// 
     190    ///
    191191    /// Setter function of the map. Equivalent with map[key] = val.
    192192    /// This is a compatibility feature with the not dereferable maps.
    … …  
    198198
    199199    /// \brief Adds a new key to the map.
    200     ///         
     200    ///
    201201    /// It adds a new key to the map. It called by the observer notifier
    202     /// and it overrides the add() member function of the observer base.     
     202    /// and it overrides the add() member function of the observer base.
    203203    virtual void add(const Key& key) {
    204204      Notifier* nf = Parent::notifier();
    205205      int id = nf->id(key);
    206206      if (id >= capacity) {
    207         int new_capacity = (capacity == 0 ? 1 : capacity);
    208         while (new_capacity <= id) {
    209           new_capacity <<= 1;
    210         }
    211         Value* new_values = allocator.allocate(new_capacity);
    212         Item it;
    213         for (nf->first(it); it != INVALID; nf->next(it)) {
    214           int jd = nf->id(it);;
    215           if (id != jd) {
    216             allocator.construct(&(new_values[jd]), values[jd]);
    217             allocator.destroy(&(values[jd]));
    218           }
    219         }
    220         if (capacity != 0) allocator.deallocate(values, capacity);
    221         values = new_values;
    222         capacity = new_capacity;
     207        int new_capacity = (capacity == 0 ? 1 : capacity);
     208        while (new_capacity <= id) {
     209          new_capacity <<= 1;
     210        }
     211        Value* new_values = allocator.allocate(new_capacity);
     212        Item it;
     213        for (nf->first(it); it != INVALID; nf->next(it)) {
     214          int jd = nf->id(it);;
     215          if (id != jd) {
     216            allocator.construct(&(new_values[jd]), values[jd]);
     217            allocator.destroy(&(values[jd]));
     218          }
     219        }
     220        if (capacity != 0) allocator.deallocate(values, capacity);
     221        values = new_values;
     222        capacity = new_capacity;
    223223      }
    224224      allocator.construct(&(values[id]), Value());
    … …  
    226226
    227227    /// \brief Adds more new keys to the map.
    228     ///         
     228    ///
    229229    /// It adds more new keys to the map. It called by the observer notifier
    230     /// and it overrides the add() member function of the observer base.     
     230    /// and it overrides the add() member function of the observer base.
    231231    virtual void add(const std::vector<Key>& keys) {
    232232      Notifier* nf = Parent::notifier();
    233233      int max_id = -1;
    234234      for (int i = 0; i < int(keys.size()); ++i) {
    235         int id = nf->id(keys[i]);
    236         if (id > max_id) {
    237           max_id = id;
    238         }
     235        int id = nf->id(keys[i]);
     236        if (id > max_id) {
     237          max_id = id;
     238        }
    239239      }
    240240      if (max_id >= capacity) {
    241         int new_capacity = (capacity == 0 ? 1 : capacity);
    242         while (new_capacity <= max_id) {
    243           new_capacity <<= 1;
    244         }
    245         Value* new_values = allocator.allocate(new_capacity);
    246         Item it;
    247         for (nf->first(it); it != INVALID; nf->next(it)) {
    248           int id = nf->id(it);
    249           bool found = false;
    250           for (int i = 0; i < int(keys.size()); ++i) {
    251             int jd = nf->id(keys[i]);
    252             if (id == jd) {
    253               found = true;
    254               break;
    255             }
    256           }
    257           if (found) continue;
    258           allocator.construct(&(new_values[id]), values[id]);
    259           allocator.destroy(&(values[id]));
    260         }
    261         if (capacity != 0) allocator.deallocate(values, capacity);
    262         values = new_values;
    263         capacity = new_capacity;
     241        int new_capacity = (capacity == 0 ? 1 : capacity);
     242        while (new_capacity <= max_id) {
     243          new_capacity <<= 1;
     244        }
     245        Value* new_values = allocator.allocate(new_capacity);
     246        Item it;
     247        for (nf->first(it); it != INVALID; nf->next(it)) {
     248          int id = nf->id(it);
     249          bool found = false;
     250          for (int i = 0; i < int(keys.size()); ++i) {
     251            int jd = nf->id(keys[i]);
     252            if (id == jd) {
     253              found = true;
     254              break;
     255            }
     256          }
     257          if (found) continue;
     258          allocator.construct(&(new_values[id]), values[id]);
     259          allocator.destroy(&(values[id]));
     260        }
     261        if (capacity != 0) allocator.deallocate(values, capacity);
     262        values = new_values;
     263        capacity = new_capacity;
    264264      }
    265265      for (int i = 0; i < int(keys.size()); ++i) {
    266         int id = nf->id(keys[i]);
    267         allocator.construct(&(values[id]), Value());
    268       }
    269     }
    270                
     266        int id = nf->id(keys[i]);
     267        allocator.construct(&(values[id]), Value());
     268      }
     269    }
     270
    271271    /// \brief Erase a key from the map.
    272272    ///
    273273    /// Erase a key from the map. It called by the observer notifier
    274     /// and it overrides the erase() member function of the observer base.     
     274    /// and it overrides the erase() member function of the observer base.
    275275    virtual void erase(const Key& key) {
    276276      int id = Parent::notifier()->id(key);
    … …  
    281281    ///
    282282    /// Erase more keys from the map. It called by the observer notifier
    283     /// and it overrides the erase() member function of the observer base.     
     283    /// and it overrides the erase() member function of the observer base.
    284284    virtual void erase(const std::vector<Key>& keys) {
    285285      for (int i = 0; i < int(keys.size()); ++i) {
    286         int id = Parent::notifier()->id(keys[i]);
    287         allocator.destroy(&(values[id]));
     286        int id = Parent::notifier()->id(keys[i]);
     287        allocator.destroy(&(values[id]));
    288288      }
    289289    }
    290290
    291291    /// \brief Buildes the map.
    292     /// 
     292    ///
    293293    /// It buildes the map. It called by the observer notifier
    294     /// and it overrides the build() member function of the observer base. 
     294    /// and it overrides the build() member function of the observer base.
    295295    virtual void build() {
    296296      Notifier* nf = Parent::notifier();
    … …  
    298298      Item it;
    299299      for (nf->first(it); it != INVALID; nf->next(it)) {
    300         int id = nf->id(it);;
    301         allocator.construct(&(values[id]), Value());
    302       }                                                         
     300        int id = nf->id(it);;
     301        allocator.construct(&(values[id]), Value());
     302      }
    303303    }
    304304
    … …  
    306306    ///
    307307    /// It erase all items from the map. It called by the observer notifier
    308     /// and it overrides the clear() member function of the observer base.     
    309     virtual void clear() {     
     308    /// and it overrides the clear() member function of the observer base.
     309    virtual void clear() {
    310310      Notifier* nf = Parent::notifier();
    311311      if (capacity != 0) {
    312         Item it;
    313         for (nf->first(it); it != INVALID; nf->next(it)) {
    314           int id = nf->id(it);
    315           allocator.destroy(&(values[id]));
    316         }                                                               
    317         allocator.deallocate(values, capacity);
    318         capacity = 0;
     312        Item it;
     313        for (nf->first(it); it != INVALID; nf->next(it)) {
     314          int id = nf->id(it);
     315          allocator.destroy(&(values[id]));
     316        }
     317        allocator.deallocate(values, capacity);
     318        capacity = 0;
    319319      }
    320320    }
    321321
    322322  private:
    323      
     323
    324324    void allocate_memory() {
    325325      int max_id = Parent::notifier()->maxId();
    326326      if (max_id == -1) {
    327         capacity = 0;
    328         values = 0;
    329         return;
     327        capacity = 0;
     328        values = 0;
     329        return;
    330330      }
    331331      capacity = 1;
    332332      while (capacity <= max_id) {
    333         capacity <<= 1;
    334       }
    335       values = allocator.allocate(capacity);   
    336     }     
     333        capacity <<= 1;
     334      }
     335      values = allocator.allocate(capacity);
     336    }
    337337
    338338    int capacity;
    … …  
    340340    Allocator allocator;
    341341
    342   };           
     342  };
    343343
    344344}
    345345
    346 #endif 
     346#endif

  • lemon/bits/base_extender.h

    r107 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    6464
    6565      bool operator==(const Arc &that) const {
    66         return forward==that.forward && Edge(*this)==Edge(that);
     66        return forward==that.forward && Edge(*this)==Edge(that);
    6767      }
    6868      bool operator!=(const Arc &that) const {
    69         return forward!=that.forward || Edge(*this)!=Edge(that);
     69        return forward!=that.forward || Edge(*this)!=Edge(that);
    7070      }
    7171      bool operator<(const Arc &that) const {
    72         return forward<that.forward ||
    73           (!(that.forward<forward) && Edge(*this)<Edge(that));
     72        return forward<that.forward ||
     73          (!(that.forward<forward) && Edge(*this)<Edge(that));
    7474      }
    7575    };
    … …  
    118118    void next(Arc &e) const {
    119119      if( e.forward ) {
    120         e.forward = false;
     120        e.forward = false;
    121121      }
    122122      else {
    123         Parent::next(e);
    124         e.forward = true;
     123        Parent::next(e);
     124        e.forward = true;
    125125      }
    126126    }
    … …  
    129129      Parent::firstIn(e,n);
    130130      if( Edge(e) != INVALID ) {
    131         e.forward = false;
     131        e.forward = false;
    132132      }
    133133      else {
    134         Parent::firstOut(e,n);
    135         e.forward = true;
     134        Parent::firstOut(e,n);
     135        e.forward = true;
    136136      }
    137137    }
    138138    void nextOut(Arc &e) const {
    139139      if( ! e.forward ) {
    140         Node n = Parent::target(e);
    141         Parent::nextIn(e);
    142         if( Edge(e) == INVALID ) {
    143           Parent::firstOut(e, n);
    144           e.forward = true;
    145         }
     140        Node n = Parent::target(e);
     141        Parent::nextIn(e);
     142        if( Edge(e) == INVALID ) {
     143          Parent::firstOut(e, n);
     144          e.forward = true;
     145        }
    146146      }
    147147      else {
    148         Parent::nextOut(e);
     148        Parent::nextOut(e);
    149149      }
    150150    }
    … …  
    153153      Parent::firstOut(e,n);
    154154      if( Edge(e) != INVALID ) {
    155         e.forward = false;
     155        e.forward = false;
    156156      }
    157157      else {
    158         Parent::firstIn(e,n);
    159         e.forward = true;
     158        Parent::firstIn(e,n);
     159        e.forward = true;
    160160      }
    161161    }
    162162    void nextIn(Arc &e) const {
    163163      if( ! e.forward ) {
    164         Node n = Parent::source(e);
    165         Parent::nextOut(e);
    166         if( Edge(e) == INVALID ) {
    167           Parent::firstIn(e, n);
    168           e.forward = true;
    169         }
     164        Node n = Parent::source(e);
     165        Parent::nextOut(e);
     166        if( Edge(e) == INVALID ) {
     167          Parent::firstIn(e, n);
     168          e.forward = true;
     169        }
    170170      }
    171171      else {
    172         Parent::nextIn(e);
     172        Parent::nextIn(e);
    173173      }
    174174    }
    … …  
    184184    void nextInc(Edge &e, bool &d) const {
    185185      if (d) {
    186         Node s = Parent::source(e);
    187         Parent::nextOut(e);
    188         if (e != INVALID) return;
    189         d = false;
    190         Parent::firstIn(e, s);
    191       } else {
    192         Parent::nextIn(e);
     186        Node s = Parent::source(e);
     187        Parent::nextOut(e);
     188        if (e != INVALID) return;
     189        d = false;
     190        Parent::firstIn(e, s);
     191      } else {
     192        Parent::nextIn(e);
    193193      }
    194194    }
    … …  
    241241    Arc findArc(Node s, Node t, Arc p = INVALID) const {
    242242      if (p == INVALID) {
    243         Edge arc = Parent::findArc(s, t);
    244         if (arc != INVALID) return direct(arc, true);
    245         arc = Parent::findArc(t, s);
    246         if (arc != INVALID) return direct(arc, false);
     243        Edge arc = Parent::findArc(s, t);
     244        if (arc != INVALID) return direct(arc, true);
     245        arc = Parent::findArc(t, s);
     246        if (arc != INVALID) return direct(arc, false);
    247247      } else if (direction(p)) {
    248         Edge arc = Parent::findArc(s, t, p);
    249         if (arc != INVALID) return direct(arc, true);
    250         arc = Parent::findArc(t, s);
    251         if (arc != INVALID) return direct(arc, false); 
    252       } else {
    253         Edge arc = Parent::findArc(t, s, p);
    254         if (arc != INVALID) return direct(arc, false);       
     248        Edge arc = Parent::findArc(s, t, p);
     249        if (arc != INVALID) return direct(arc, true);
     250        arc = Parent::findArc(t, s);
     251        if (arc != INVALID) return direct(arc, false);
     252      } else {
     253        Edge arc = Parent::findArc(t, s, p);
     254        if (arc != INVALID) return direct(arc, false);
    255255      }
    256256      return INVALID;
    … …  
    268268          if (arc != INVALID) return arc;
    269269          arc = Parent::findArc(t, s);
    270           if (arc != INVALID) return arc;       
     270          if (arc != INVALID) return arc;
    271271        } else {
    272272          Edge arc = Parent::findArc(t, s, p);
    273           if (arc != INVALID) return arc;             
     273          if (arc != INVALID) return arc;
    274274        }
    275275      } else {
    … …  
    300300      Red() {}
    301301      Red(const Node& node) : Node(node) {
    302         LEMON_ASSERT(Parent::red(node) || node == INVALID,
    303                      typename Parent::NodeSetError());
     302        LEMON_ASSERT(Parent::red(node) || node == INVALID,
     303                     typename Parent::NodeSetError());
    304304      }
    305305      Red& operator=(const Node& node) {
    306         LEMON_ASSERT(Parent::red(node) || node == INVALID,
    307                      typename Parent::NodeSetError());
     306        LEMON_ASSERT(Parent::red(node) || node == INVALID,
     307                     typename Parent::NodeSetError());
    308308        Node::operator=(node);
    309309        return *this;
    … …  
    332332      Blue() {}
    333333      Blue(const Node& node) : Node(node) {
    334         LEMON_ASSERT(Parent::blue(node) || node == INVALID,
    335                      typename Parent::NodeSetError());
     334        LEMON_ASSERT(Parent::blue(node) || node == INVALID,
     335                     typename Parent::NodeSetError());
    336336      }
    337337      Blue& operator=(const Node& node) {
    338         LEMON_ASSERT(Parent::blue(node) || node == INVALID,
    339                      typename Parent::NodeSetError());
     338        LEMON_ASSERT(Parent::blue(node) || node == INVALID,
     339                     typename Parent::NodeSetError());
    340340        Node::operator=(node);
    341341        return *this;
    … …  
    354354      Parent::nextBlue(static_cast<Node&>(node));
    355355    }
    356  
     356
    357357    int id(const Blue& node) const {
    358358      return Parent::redId(node);
    … …  
    368368    void firstInc(Edge& arc, bool& dir, const Node& node) const {
    369369      if (Parent::red(node)) {
    370         Parent::firstFromRed(arc, node);
    371         dir = true;
    372       } else {
    373         Parent::firstFromBlue(arc, node);
    374         dir = static_cast<Edge&>(arc) == INVALID;
     370        Parent::firstFromRed(arc, node);
     371        dir = true;
     372      } else {
     373        Parent::firstFromBlue(arc, node);
     374        dir = static_cast<Edge&>(arc) == INVALID;
    375375      }
    376376    }
    377377    void nextInc(Edge& arc, bool& dir) const {
    378378      if (dir) {
    379         Parent::nextFromRed(arc);
    380       } else {
    381         Parent::nextFromBlue(arc);
    382         if (arc == INVALID) dir = true;
     379        Parent::nextFromRed(arc);
     380      } else {
     381        Parent::nextFromBlue(arc);
     382        if (arc == INVALID) dir = true;
    383383      }
    384384    }
    … …  
    390390
    391391      Arc(const Edge& arc, bool _forward)
    392         : Edge(arc), forward(_forward) {}
     392        : Edge(arc), forward(_forward) {}
    393393
    394394    public:
    … …  
    396396      Arc (Invalid) : Edge(INVALID), forward(true) {}
    397397      bool operator==(const Arc& i) const {
    398         return Edge::operator==(i) && forward == i.forward;
     398        return Edge::operator==(i) && forward == i.forward;
    399399      }
    400400      bool operator!=(const Arc& i) const {
    401         return Edge::operator!=(i) || forward != i.forward;
     401        return Edge::operator!=(i) || forward != i.forward;
    402402      }
    403403      bool operator<(const Arc& i) const {
    404         return Edge::operator<(i) ||
    405           (!(i.forward<forward) && Edge(*this)<Edge(i));
     404        return Edge::operator<(i) ||
     405          (!(i.forward<forward) && Edge(*this)<Edge(i));
    406406      }
    407407    };
    … …  
    414414    void next(Arc& arc) const {
    415415      if (!arc.forward) {
    416         Parent::next(static_cast<Edge&>(arc));
     416        Parent::next(static_cast<Edge&>(arc));
    417417      }
    418418      arc.forward = !arc.forward;
    … …  
    421421    void firstOut(Arc& arc, const Node& node) const {
    422422      if (Parent::red(node)) {
    423         Parent::firstFromRed(arc, node);
    424         arc.forward = true;
    425       } else {
    426         Parent::firstFromBlue(arc, node);
    427         arc.forward = static_cast<Edge&>(arc) == INVALID;
     423        Parent::firstFromRed(arc, node);
     424        arc.forward = true;
     425      } else {
     426        Parent::firstFromBlue(arc, node);
     427        arc.forward = static_cast<Edge&>(arc) == INVALID;
    428428      }
    429429    }
    430430    void nextOut(Arc& arc) const {
    431431      if (arc.forward) {
    432         Parent::nextFromRed(arc);
    433       } else {
    434         Parent::nextFromBlue(arc);
     432        Parent::nextFromRed(arc);
     433      } else {
     434        Parent::nextFromBlue(arc);
    435435        arc.forward = static_cast<Edge&>(arc) == INVALID;
    436436      }
    … …  
    439439    void firstIn(Arc& arc, const Node& node) const {
    440440      if (Parent::blue(node)) {
    441         Parent::firstFromBlue(arc, node);
    442         arc.forward = true;     
    443       } else {
    444         Parent::firstFromRed(arc, node);
    445         arc.forward = static_cast<Edge&>(arc) == INVALID;
     441        Parent::firstFromBlue(arc, node);
     442        arc.forward = true;
     443      } else {
     444        Parent::firstFromRed(arc, node);
     445        arc.forward = static_cast<Edge&>(arc) == INVALID;
    446446      }
    447447    }
    448448    void nextIn(Arc& arc) const {
    449449      if (arc.forward) {
    450         Parent::nextFromBlue(arc);
    451       } else {
    452         Parent::nextFromRed(arc);
    453         arc.forward = static_cast<Edge&>(arc) == INVALID;
     450        Parent::nextFromBlue(arc);
     451      } else {
     452        Parent::nextFromRed(arc);
     453        arc.forward = static_cast<Edge&>(arc) == INVALID;
    454454      }
    455455    }
    … …  
    463463
    464464    int id(const Arc& arc) const {
    465       return (Parent::id(static_cast<const Edge&>(arc)) << 1) + 
     465      return (Parent::id(static_cast<const Edge&>(arc)) << 1) +
    466466        (arc.forward ? 0 : 1);
    467467    }

  • lemon/bits/bezier.h

    r184 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    4545  Bezier1() {}
    4646  Bezier1(Point _p1, Point _p2) :p1(_p1), p2(_p2) {}
    47  
     47
    4848  Point operator()(double t) const
    4949  {
    … …  
    5555    return Bezier1(p1,conv(p1,p2,t));
    5656  }
    57  
     57
    5858  Bezier1 after(double t) const
    5959  {
    … …  
    8888    return Bezier2(p1,q,conv(q,r,t));
    8989  }
    90  
     90
    9191  Bezier2 after(double t) const
    9292  {
    … …  
    111111  Bezier3(Point _p1, Point _p2, Point _p3, Point _p4)
    112112    : p1(_p1), p2(_p2), p3(_p3), p4(_p4) {}
    113   Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)), 
    114                               p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}
     113  Bezier3(const Bezier1 &b) : p1(b.p1), p2(conv(b.p1,b.p2,1.0/3.0)),
     114                              p3(conv(b.p1,b.p2,2.0/3.0)), p4(b.p2) {}
    115115  Bezier3(const Bezier2 &b) : p1(b.p1), p2(conv(b.p1,b.p2,2.0/3.0)),
    116                               p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}
    117  
    118   Point operator()(double t) const 
     116                              p3(conv(b.p2,b.p3,1.0/3.0)), p4(b.p3) {}
     117
     118  Point operator()(double t) const
    119119    {
    120120      //    return Bezier2(conv(p1,p2,t),conv(p2,p3,t),conv(p3,p4,t))(t);
    121121      return ((1-t)*(1-t)*(1-t))*p1+(3*t*(1-t)*(1-t))*p2+
    122         (3*t*t*(1-t))*p3+(t*t*t)*p4;
     122        (3*t*t*(1-t))*p3+(t*t*t)*p4;
    123123    }
    124124  Bezier3 before(double t) const
    … …  
    132132      return Bezier3(p1,p,a,c);
    133133    }
    134  
     134
    135135  Bezier3 after(double t) const
    136136    {
    … …  
    147147  Bezier2 grad() const { return Bezier2(3.0*(p2-p1),3.0*(p3-p2),3.0*(p4-p3)); }
    148148  Bezier2 norm() const { return Bezier2(3.0*rot90(p2-p1),
    149                                   3.0*rot90(p3-p2),
    150                                   3.0*rot90(p4-p3)); }
     149                                  3.0*rot90(p3-p2),
     150                                  3.0*rot90(p4-p3)); }
    151151  Point grad(double t) const { return grad()(t); }
    152152  Point norm(double t) const { return rot90(grad(t)); }
    153153
    154154  template<class R,class F,class S,class D>
    155   R recSplit(F &_f,const S &_s,D _d) const 
     155  R recSplit(F &_f,const S &_s,D _d) const
    156156  {
    157157    const Point a=(p1+p2)/2;
    … …  
    165165    return _s(f1,f2);
    166166  }
    167  
     167
    168168};
    169169

  • lemon/bits/default_map.h

    r107 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    3030
    3131namespace lemon {
    32  
    33  
     32
     33
    3434  //#ifndef LEMON_USE_DEBUG_MAP
    3535
    … …  
    141141  };
    142142
    143 // #else 
     143// #else
    144144
    145145//   template <typename _Graph, typename _Item, typename _Value>
    … …  
    148148//   };
    149149
    150 // #endif 
     150// #endif
    151151
    152152  /// \e
    153153  template <typename _Graph, typename _Item, typename _Value>
    154   class DefaultMap 
     154  class DefaultMap
    155155    : public DefaultMapSelector<_Graph, _Item, _Value>::Map {
    156156  public:
    157157    typedef typename DefaultMapSelector<_Graph, _Item, _Value>::Map Parent;
    158158    typedef DefaultMap<_Graph, _Item, _Value> Map;
    159    
     159
    160160    typedef typename Parent::Graph Graph;
    161161    typedef typename Parent::Value Value;
    162162
    163163    explicit DefaultMap(const Graph& graph) : Parent(graph) {}
    164     DefaultMap(const Graph& graph, const Value& value) 
     164    DefaultMap(const Graph& graph, const Value& value)
    165165      : Parent(graph, value) {}
    166166

  • lemon/bits/graph_extender.h

    r125 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    6767    Node oppositeNode(const Node &node, const Arc &arc) const {
    6868      if (node == Parent::source(arc))
    69         return Parent::target(arc);
     69        return Parent::target(arc);
    7070      else if(node == Parent::target(arc))
    71         return Parent::source(arc);
     71        return Parent::source(arc);
    7272      else
    73         return INVALID;
     73        return INVALID;
    7474    }
    7575
    … …  
    9090      return node_notifier;
    9191    }
    92    
     92
    9393    ArcNotifier& notifier(Arc) const {
    9494      return arc_notifier;
    9595    }
    9696
    97     class NodeIt : public Node { 
     97    class NodeIt : public Node {
    9898      const Digraph* _digraph;
    9999    public:
    … …  
    104104
    105105      explicit NodeIt(const Digraph& digraph) : _digraph(&digraph) {
    106         _digraph->first(static_cast<Node&>(*this));
    107       }
    108 
    109       NodeIt(const Digraph& digraph, const Node& node) 
    110         : Node(node), _digraph(&digraph) {}
    111 
    112       NodeIt& operator++() { 
    113         _digraph->next(*this);
    114         return *this;
    115       }
    116 
    117     };
    118 
    119 
    120     class ArcIt : public Arc { 
     106        _digraph->first(static_cast<Node&>(*this));
     107      }
     108
     109      NodeIt(const Digraph& digraph, const Node& node)
     110        : Node(node), _digraph(&digraph) {}
     111
     112      NodeIt& operator++() {
     113        _digraph->next(*this);
     114        return *this;
     115      }
     116
     117    };
     118
     119
     120    class ArcIt : public Arc {
    121121      const Digraph* _digraph;
    122122    public:
    … …  
    127127
    128128      explicit ArcIt(const Digraph& digraph) : _digraph(&digraph) {
    129         _digraph->first(static_cast<Arc&>(*this));
    130       }
    131 
    132       ArcIt(const Digraph& digraph, const Arc& arc) : 
    133         Arc(arc), _digraph(&digraph) { }
    134 
    135       ArcIt& operator++() { 
    136         _digraph->next(*this);
    137         return *this;
    138       }
    139 
    140     };
    141 
    142 
    143     class OutArcIt : public Arc { 
     129        _digraph->first(static_cast<Arc&>(*this));
     130      }
     131
     132      ArcIt(const Digraph& digraph, const Arc& arc) :
     133        Arc(arc), _digraph(&digraph) { }
     134
     135      ArcIt& operator++() {
     136        _digraph->next(*this);
     137        return *this;
     138      }
     139
     140    };
     141
     142
     143    class OutArcIt : public Arc {
    144144      const Digraph* _digraph;
    145145    public:
    … …  
    149149      OutArcIt(Invalid i) : Arc(i) { }
    150150
    151       OutArcIt(const Digraph& digraph, const Node& node) 
    152         : _digraph(&digraph) {
    153         _digraph->firstOut(*this, node);
    154       }
    155 
    156       OutArcIt(const Digraph& digraph, const Arc& arc) 
    157         : Arc(arc), _digraph(&digraph) {}
    158 
    159       OutArcIt& operator++() { 
    160         _digraph->nextOut(*this);
    161         return *this;
    162       }
    163 
    164     };
    165 
    166 
    167     class InArcIt : public Arc { 
     151      OutArcIt(const Digraph& digraph, const Node& node)
     152        : _digraph(&digraph) {
     153        _digraph->firstOut(*this, node);
     154      }
     155
     156      OutArcIt(const Digraph& digraph, const Arc& arc)
     157        : Arc(arc), _digraph(&digraph) {}
     158
     159      OutArcIt& operator++() {
     160        _digraph->nextOut(*this);
     161        return *this;
     162      }
     163
     164    };
     165
     166
     167    class InArcIt : public Arc {
    168168      const Digraph* _digraph;
    169169    public:
    … …  
    173173      InArcIt(Invalid i) : Arc(i) { }
    174174
    175       InArcIt(const Digraph& digraph, const Node& node) 
    176         : _digraph(&digraph) {
    177         _digraph->firstIn(*this, node);
    178       }
    179 
    180       InArcIt(const Digraph& digraph, const Arc& arc) : 
    181         Arc(arc), _digraph(&digraph) {}
    182 
    183       InArcIt& operator++() { 
    184         _digraph->nextIn(*this);
    185         return *this;
     175      InArcIt(const Digraph& digraph, const Node& node)
     176        : _digraph(&digraph) {
     177        _digraph->firstIn(*this, node);
     178      }
     179
     180      InArcIt(const Digraph& digraph, const Arc& arc) :
     181        Arc(arc), _digraph(&digraph) {}
     182
     183      InArcIt& operator++() {
     184        _digraph->nextIn(*this);
     185        return *this;
    186186      }
    187187
    … …  
    216216    }
    217217
    218    
     218
    219219    template <typename _Value>
    220     class NodeMap 
     220    class NodeMap
    221221      : public MapExtender<DefaultMap<Digraph, Node, _Value> > {
    222222    public:
    … …  
    224224      typedef MapExtender<DefaultMap<Digraph, Node, _Value> > Parent;
    225225
    226       explicit NodeMap(const Digraph& digraph) 
    227         : Parent(digraph) {}
    228       NodeMap(const Digraph& digraph, const _Value& value) 
    229         : Parent(digraph, value) {}
     226      explicit NodeMap(const Digraph& digraph)
     227        : Parent(digraph) {}
     228      NodeMap(const Digraph& digraph, const _Value& value)
     229        : Parent(digraph, value) {}
    230230
    231231      NodeMap& operator=(const NodeMap& cmap) {
    232         return operator=<NodeMap>(cmap);
     232        return operator=<NodeMap>(cmap);
    233233      }
    234234
    … …  
    236236      NodeMap& operator=(const CMap& cmap) {
    237237        Parent::operator=(cmap);
    238         return *this;
     238        return *this;
    239239      }
    240240
    … …  
    242242
    243243    template <typename _Value>
    244     class ArcMap 
     244    class ArcMap
    245245      : public MapExtender<DefaultMap<Digraph, Arc, _Value> > {
    246246    public:
    … …  
    248248      typedef MapExtender<DefaultMap<Digraph, Arc, _Value> > Parent;
    249249
    250       explicit ArcMap(const Digraph& digraph) 
    251         : Parent(digraph) {}
    252       ArcMap(const Digraph& digraph, const _Value& value) 
    253         : Parent(digraph, value) {}
     250      explicit ArcMap(const Digraph& digraph)
     251        : Parent(digraph) {}
     252      ArcMap(const Digraph& digraph, const _Value& value)
     253        : Parent(digraph, value) {}
    254254
    255255      ArcMap& operator=(const ArcMap& cmap) {
    256         return operator=<ArcMap>(cmap);
     256        return operator=<ArcMap>(cmap);
    257257      }
    258258
    … …  
    260260      ArcMap& operator=(const CMap& cmap) {
    261261        Parent::operator=(cmap);
    262         return *this;
     262        return *this;
    263263      }
    264264    };
    … …  
    270270      return node;
    271271    }
    272    
     272
    273273    Arc addArc(const Node& from, const Node& to) {
    274274      Arc arc = Parent::addArc(from, to);
    … …  
    294294      Parent::firstOut(arc, node);
    295295      while (arc != INVALID ) {
    296         erase(arc);
    297         Parent::firstOut(arc, node);
    298       } 
     296        erase(arc);
     297        Parent::firstOut(arc, node);
     298      }
    299299
    300300      Parent::firstIn(arc, node);
    301301      while (arc != INVALID ) {
    302         erase(arc);
    303         Parent::firstIn(arc, node);
     302        erase(arc);
     303        Parent::firstIn(arc, node);
    304304      }
    305305
    … …  
    307307      Parent::erase(node);
    308308    }
    309    
     309
    310310    void erase(const Arc& arc) {
    311311      notifier(Arc()).erase(arc);
    … …  
    316316      node_notifier.setContainer(*this);
    317317      arc_notifier.setContainer(*this);
    318     } 
    319    
     318    }
     319
    320320
    321321    ~DigraphExtender() {
    … …  
    328328  ///
    329329  /// \brief Extender for the Graphs
    330   template <typename Base> 
     330  template <typename Base>
    331331  class GraphExtender : public Base {
    332332  public:
    333    
     333
    334334    typedef Base Parent;
    335335    typedef GraphExtender Graph;
    … …  
    341341    typedef typename Parent::Edge Edge;
    342342
    343     // Graph extension   
     343    // Graph extension
    344344
    345345    int maxId(Node) const {
    … …  
    369369    Node oppositeNode(const Node &n, const Edge &e) const {
    370370      if( n == Parent::u(e))
    371         return Parent::v(e);
     371        return Parent::v(e);
    372372      else if( n == Parent::v(e))
    373         return Parent::u(e);
     373        return Parent::u(e);
    374374      else
    375         return INVALID;
     375        return INVALID;
    376376    }
    377377
    … …  
    403403      return node_notifier;
    404404    }
    405    
     405
    406406    ArcNotifier& notifier(Arc) const {
    407407      return arc_notifier;
    … …  
    414414
    415415
    416     class NodeIt : public Node { 
     416    class NodeIt : public Node {
    417417      const Graph* _graph;
    418418    public:
    … …  
    423423
    424424      explicit NodeIt(const Graph& graph) : _graph(&graph) {
    425         _graph->first(static_cast<Node&>(*this));
    426       }
    427 
    428       NodeIt(const Graph& graph, const Node& node) 
    429         : Node(node), _graph(&graph) {}
    430 
    431       NodeIt& operator++() { 
    432         _graph->next(*this);
    433         return *this;
    434       }
    435 
    436     };
    437 
    438 
    439     class ArcIt : public Arc { 
     425        _graph->first(static_cast<Node&>(*this));
     426      }
     427
     428      NodeIt(const Graph& graph, const Node& node)
     429        : Node(node), _graph(&graph) {}
     430
     431      NodeIt& operator++() {
     432        _graph->next(*this);
     433        return *this;
     434      }
     435
     436    };
     437
     438
     439    class ArcIt : public Arc {
    440440      const Graph* _graph;
    441441    public:
    … …  
    446446
    447447      explicit ArcIt(const Graph& graph) : _graph(&graph) {
    448         _graph->first(static_cast<Arc&>(*this));
    449       }
    450 
    451       ArcIt(const Graph& graph, const Arc& arc) : 
    452         Arc(arc), _graph(&graph) { }
    453 
    454       ArcIt& operator++() { 
    455         _graph->next(*this);
    456         return *this;
    457       }
    458 
    459     };
    460 
    461 
    462     class OutArcIt : public Arc { 
     448        _graph->first(static_cast<Arc&>(*this));
     449      }
     450
     451      ArcIt(const Graph& graph, const Arc& arc) :
     452        Arc(arc), _graph(&graph) { }
     453
     454      ArcIt& operator++() {
     455        _graph->next(*this);
     456        return *this;
     457      }
     458
     459    };
     460
     461
     462    class OutArcIt : public Arc {
    463463      const Graph* _graph;
    464464    public:
    … …  
    468468      OutArcIt(Invalid i) : Arc(i) { }
    469469
    470       OutArcIt(const Graph& graph, const Node& node) 
    471         : _graph(&graph) {
    472         _graph->firstOut(*this, node);
    473       }
    474 
    475       OutArcIt(const Graph& graph, const Arc& arc) 
    476         : Arc(arc), _graph(&graph) {}
    477 
    478       OutArcIt& operator++() { 
    479         _graph->nextOut(*this);
    480         return *this;
    481       }
    482 
    483     };
    484 
    485 
    486     class InArcIt : public Arc { 
     470      OutArcIt(const Graph& graph, const Node& node)
     471        : _graph(&graph) {
     472        _graph->firstOut(*this, node);
     473      }
     474
     475      OutArcIt(const Graph& graph, const Arc& arc)
     476        : Arc(arc), _graph(&graph) {}
     477
     478      OutArcIt& operator++() {
     479        _graph->nextOut(*this);
     480        return *this;
     481      }
     482
     483    };
     484
     485
     486    class InArcIt : public Arc {
    487487      const Graph* _graph;
    488488    public:
    … …  
    492492      InArcIt(Invalid i) : Arc(i) { }
    493493
    494       InArcIt(const Graph& graph, const Node& node) 
    495         : _graph(&graph) {
    496         _graph->firstIn(*this, node);
    497       }
    498 
    499       InArcIt(const Graph& graph, const Arc& arc) : 
    500         Arc(arc), _graph(&graph) {}
    501 
    502       InArcIt& operator++() { 
    503         _graph->nextIn(*this);
    504         return *this;
    505       }
    506 
    507     };
    508 
    509 
    510     class EdgeIt : public Parent::Edge { 
     494      InArcIt(const Graph& graph, const Node& node)
     495        : _graph(&graph) {
     496        _graph->firstIn(*this, node);
     497      }
     498
     499      InArcIt(const Graph& graph, const Arc& arc) :
     500        Arc(arc), _graph(&graph) {}
     501
     502      InArcIt& operator++() {
     503        _graph->nextIn(*this);
     504        return *this;
     505      }
     506
     507    };
     508
     509
     510    class EdgeIt : public Parent::Edge {
    511511      const Graph* _graph;
    512512    public:
    … …  
    517517
    518518      explicit EdgeIt(const Graph& graph) : _graph(&graph) {
    519         _graph->first(static_cast<Edge&>(*this));
    520       }
    521 
    522       EdgeIt(const Graph& graph, const Edge& edge) : 
    523         Edge(edge), _graph(&graph) { }
    524 
    525       EdgeIt& operator++() { 
    526         _graph->next(*this);
    527         return *this;
     519        _graph->first(static_cast<Edge&>(*this));
     520      }
     521
     522      EdgeIt(const Graph& graph, const Edge& edge) :
     523        Edge(edge), _graph(&graph) { }
     524
     525      EdgeIt& operator++() {
     526        _graph->next(*this);
     527        return *this;
    528528      }
    529529
    … …  
    541541
    542542      IncEdgeIt(const Graph& graph, const Node &node) : _graph(&graph) {
    543         _graph->firstInc(*this, _direction, node);
     543        _graph->firstInc(*this, _direction, node);
    544544      }
    545545
    546546      IncEdgeIt(const Graph& graph, const Edge &edge, const Node &node)
    547         : _graph(&graph), Edge(edge) {
    548         _direction = (_graph->source(edge) == node);
     547        : _graph(&graph), Edge(edge) {
     548        _direction = (_graph->source(edge) == node);
    549549      }
    550550
    551551      IncEdgeIt& operator++() {
    552         _graph->nextInc(*this, _direction);
    553         return *this;
     552        _graph->nextInc(*this, _direction);
     553        return *this;
    554554      }
    555555    };
    … …  
    599599
    600600    template <typename _Value>
    601     class NodeMap 
     601    class NodeMap
    602602      : public MapExtender<DefaultMap<Graph, Node, _Value> > {
    603603    public:
    … …  
    605605      typedef MapExtender<DefaultMap<Graph, Node, _Value> > Parent;
    606606
    607       NodeMap(const Graph& graph) 
    608         : Parent(graph) {}
    609       NodeMap(const Graph& graph, const _Value& value) 
    610         : Parent(graph, value) {}
     607      NodeMap(const Graph& graph)
     608        : Parent(graph) {}
     609      NodeMap(const Graph& graph, const _Value& value)
     610        : Parent(graph, value) {}
    611611
    612612      NodeMap& operator=(const NodeMap& cmap) {
    613         return operator=<NodeMap>(cmap);
     613        return operator=<NodeMap>(cmap);
    614614      }
    615615
    … …  
    617617      NodeMap& operator=(const CMap& cmap) {
    618618        Parent::operator=(cmap);
    619         return *this;
     619        return *this;
    620620      }
    621621
    … …  
    623623
    624624    template <typename _Value>
    625     class ArcMap 
     625    class ArcMap
    626626      : public MapExtender<DefaultMap<Graph, Arc, _Value> > {
    627627    public:
    … …  
    629629      typedef MapExtender<DefaultMap<Graph, Arc, _Value> > Parent;
    630630
    631       ArcMap(const Graph& graph) 
    632         : Parent(graph) {}
    633       ArcMap(const Graph& graph, const _Value& value) 
    634         : Parent(graph, value) {}
     631      ArcMap(const Graph& graph)
     632        : Parent(graph) {}
     633      ArcMap(const Graph& graph, const _Value& value)
     634        : Parent(graph, value) {}
    635635
    636636      ArcMap& operator=(const ArcMap& cmap) {
    637         return operator=<ArcMap>(cmap);
     637        return operator=<ArcMap>(cmap);
    638638      }
    639639
    … …  
    641641      ArcMap& operator=(const CMap& cmap) {
    642642        Parent::operator=(cmap);
    643         return *this;
     643        return *this;
    644644      }
    645645    };
    … …  
    647647
    648648    template <typename _Value>
    649     class EdgeMap 
     649    class EdgeMap
    650650      : public MapExtender<DefaultMap<Graph, Edge, _Value> > {
    651651    public:
    … …  
    653653      typedef MapExtender<DefaultMap<Graph, Edge, _Value> > Parent;
    654654
    655       EdgeMap(const Graph& graph) 
    656         : Parent(graph) {}
    657 
    658       EdgeMap(const Graph& graph, const _Value& value) 
    659         : Parent(graph, value) {}
     655      EdgeMap(const Graph& graph)
     656        : Parent(graph) {}
     657
     658      EdgeMap(const Graph& graph, const _Value& value)
     659        : Parent(graph, value) {}
    660660
    661661      EdgeMap& operator=(const EdgeMap& cmap) {
    662         return operator=<EdgeMap>(cmap);
     662        return operator=<EdgeMap>(cmap);
    663663      }
    664664
    … …  
    666666      EdgeMap& operator=(const CMap& cmap) {
    667667        Parent::operator=(cmap);
    668         return *this;
     668        return *this;
    669669      }
    670670
    … …  
    684684      std::vector<Arc> ev;
    685685      ev.push_back(Parent::direct(edge, true));
    686       ev.push_back(Parent::direct(edge, false));     
     686      ev.push_back(Parent::direct(edge, false));
    687687      notifier(Arc()).add(ev);
    688688      return edge;
    689689    }
    690    
     690
    691691    void clear() {
    692692      notifier(Arc()).clear();
    … …  
    697697
    698698    template <typename Graph, typename NodeRefMap, typename EdgeRefMap>
    699     void build(const Graph& graph, NodeRefMap& nodeRef, 
     699    void build(const Graph& graph, NodeRefMap& nodeRef,
    700700               EdgeRefMap& edgeRef) {
    701701      Parent::build(graph, nodeRef, edgeRef);
    … …  
    709709      Parent::firstOut(arc, node);
    710710      while (arc != INVALID ) {
    711         erase(arc);
    712         Parent::firstOut(arc, node);
    713       } 
     711        erase(arc);
     712        Parent::firstOut(arc, node);
     713      }
    714714
    715715      Parent::firstIn(arc, node);
    716716      while (arc != INVALID ) {
    717         erase(arc);
    718         Parent::firstIn(arc, node);
     717        erase(arc);
     718        Parent::firstIn(arc, node);
    719719      }
    720720
    … …  
    726726      std::vector<Arc> av;
    727727      av.push_back(Parent::direct(edge, true));
    728       av.push_back(Parent::direct(edge, false));     
     728      av.push_back(Parent::direct(edge, false));
    729729      notifier(Arc()).erase(av);
    730730      notifier(Edge()).erase(edge);
    … …  
    733733
    734734    GraphExtender() {
    735       node_notifier.setContainer(*this); 
     735      node_notifier.setContainer(*this);
    736736      arc_notifier.setContainer(*this);
    737737      edge_notifier.setContainer(*this);
    738     } 
     738    }
    739739
    740740    ~GraphExtender() {
    741741      edge_notifier.clear();
    742742      arc_notifier.clear();
    743       node_notifier.clear(); 
    744     } 
     743      node_notifier.clear();
     744    }
    745745
    746746  };

  • lemon/bits/invalid.h

    r49 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    3535    bool operator< (Invalid) { return false; }
    3636  };
    37  
     37
    3838  /// \brief Invalid iterators.
    3939  ///
    … …  
    5353
    5454#endif
    55  
     55

  • lemon/bits/map_extender.h

    r107 r209  
    1 /* -*- C++ -*-
    2  *
    3  * This file is a part of LEMON, a generic C++ optimization library
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
     2 *
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    3333
    3434  /// \ingroup graphbits
    35   /// 
     35  ///
    3636  /// \brief Extender for maps
    3737  template <typename _Map>
    … …  
    5757  public:
    5858
    59     MapExtender(const Graph& graph) 
     59    MapExtender(const Graph& graph)
    6060      : Parent(graph) {}
    6161
    62     MapExtender(const Graph& graph, const Value& value) 
     62    MapExtender(const Graph& graph, const Value& value)
    6363      : Parent(graph, value) {}
    6464
    … …  
    7171      Parent::operator=(cmap);
    7272      return *this;
    73     } 
     73    }
    7474
    7575    class MapIt : public Item {
    7676    public:
    77      
     77
    7878      typedef Item Parent;
    7979      typedef typename Map::Value Value;
    80      
     80
    8181      MapIt() {}
    8282
    … …  
    8787      }
    8888
    89       MapIt(const Map& _map, const Item& item) 
    90         : Parent(item), map(_map) {}
    91 
    92       MapIt& operator++() { 
    93         map.notifier()->next(*this);
    94         return *this;
    95       }
    96      
     89      MapIt(const Map& _map, const Item& item)
     90        : Parent(item), map(_map) {}
     91
     92      MapIt& operator++() {
     93        map.notifier()->next(*this);
     94        return *this;
     95      }
     96
    9797      typename MapTraits<Map>::ConstReturnValue operator*() const {
    98         return map[*this];
     98        return map[*this];
    9999      }
    100100
    101101      typename MapTraits<Map>::ReturnValue operator*() {
    102         return map[*this];
    103       }
    104      
     102        return map[*this];
     103      }
     104
    105105      void set(const Value& value) {
    106         map.set(*this, value);
    107       }
    108      
     106        map.set(*this, value);
     107      }
     108
    109109    protected:
    110110      Map& map;
    111      
     111
    112112    };
    113113
    … …  
    118118
    119119      typedef typename Map::Value Value;
    120      
     120
    121121      ConstMapIt() {}
    122122
    … …  
    127127      }
    128128
    129       ConstMapIt(const Map& _map, const Item& item) 
    130         : Parent(item), map(_map) {}
    131 
    132       ConstMapIt& operator++() { 
    133         map.notifier()->next(*this);
    134         return *this;
     129      ConstMapIt(const Map& _map, const Item& item)
     130        : Parent(item), map(_map) {}
     131
     132      ConstMapIt& operator++() {
     133        map.notifier()->next(*this);
     134        return *this;
    135135      }
    136136
    137137      typename MapTraits<Map>::ConstReturnValue operator*() const {
    138         return map[*this];
     138        return map[*this];
    139139      }
    140140
    … …  
    145145    class ItemIt : public Item {
    146146    public:
    147      
    148       typedef Item Parent;
    149      
     147
     148      typedef Item Parent;
     149
    150150      ItemIt() {}
    151151
    … …  
    156156      }
    157157
    158       ItemIt(const Map& _map, const Item& item) 
    159         : Parent(item), map(_map) {}
    160 
    161       ItemIt& operator++() { 
    162         map.notifier()->next(*this);
    163         return *this;
     158      ItemIt(const Map& _map, const Item& item)
     159        : Parent(item), map(_map) {}
     160
     161      ItemIt& operator++() {
     162        map.notifier()->next(*this);
     163        return *this;
    164164      }
    165165
    166166    protected:
    167167      const Map& map;
    168      
     168
    169169    };
    170170  };
    171171
    172172  /// \ingroup graphbits
    173   /// 
     173  ///
    174174  /// \brief Extender for maps which use a subset of the items.
    175175  template <typename _Graph, typename _Map>
    … …  
    195195  public:
    196196
    197     SubMapExtender(const Graph& _graph) 
     197    SubMapExtender(const Graph& _graph)
    198198      : Parent(_graph), graph(_graph) {}
    199199
    200     SubMapExtender(const Graph& _graph, const Value& _value) 
     200    SubMapExtender(const Graph& _graph, const Value& _value)
    201201      : Parent(_graph, _value), graph(_graph) {}
    202202
    … …  
    213213      }
    214214      return *this;
    215     } 
     215    }
    216216
    217217    class MapIt : public Item {
    218218    public:
    219      
     219
    220220      typedef Item Parent;
    221221      typedef typename Map::Value Value;
    222      
     222
    223223      MapIt() {}
    224224
    … …  
    229229      }
    230230
    231       MapIt(const Map& _map, const Item& item) 
    232         : Parent(item), map(_map) {}
    233 
    234       MapIt& operator++() { 
    235         map.graph.next(*this);
    236         return *this;
    237       }
    238      
     231      MapIt(const Map& _map, const Item& item)
     232        : Parent(item), map(_map) {}
     233
     234      MapIt& operator++() {
     235        map.graph.next(*this);
     236        return *this;
     237      }
     238
    239239      typename MapTraits<Map>::ConstReturnValue operator*() const {
    240         return map[*this];
     240        return map[*this];
    241241      }
    242242
    243243      typename MapTraits<Map>::ReturnValue operator*() {
    244         return map[*this];
    245       }
    246      
     244        return map[*this];
     245      }
     246
    247247      void set(const Value& value) {
    248         map.set(*this, value);
    249       }
    250      
     248        map.set(*this, value);
     249      }
     250
    251251    protected:
    252252      Map& map;
    253      
     253
    254254    };
    255255
    … …  
    260260
    261261      typedef typename Map::Value Value;
    262      
     262
    263263      ConstMapIt() {}
    264264
    … …  
    269269      }
    270270
    271       ConstMapIt(const Map& _map, const Item& item) 
    272         : Parent(item), map(_map) {}
    273 
    274       ConstMapIt& operator++() { 
    275         map.graph.next(*this);
    276         return *this;
     271      ConstMapIt(const Map& _map, const Item& item)
     272        : Parent(item), map(_map) {}
     273
     274      ConstMapIt& operator++() {
     275        map.graph.next(*this);
     276        return *this;
    277277      }
    278278
    279279      typename MapTraits<Map>::ConstReturnValue operator*() const {
    280         return map[*this];
     280        return map[*this];
    281281      }
    282282
    … …  
    287287    class ItemIt : public Item {
    288288    public:
    289      
    290       typedef Item Parent;
    291      
     289
     290      typedef Item Parent;
     291
    292292      ItemIt() {}
    293293
    … …  
    298298      }
    299299
    300       ItemIt(const Map& _map, const Item& item) 
    301         : Parent(item), map(_map) {}
    302 
    303       ItemIt& operator++() { 
    304         map.graph.next(*this);
    305         return *this;
     300      ItemIt(const Map& _map, const Item& item)
     301        : Parent(item), map(_map) {}
     302
     303      ItemIt& operator++() {
     304        map.graph.next(*this);
     305        return *this;
    306306      }
    307307
    308308    protected:
    309309      const Map& map;
    310      
    311     };
    312    
     310
     311    };
     312
    313313  private:
    314314
    315315    const Graph& graph;
    316    
     316
    317317  };
    318318

  • lemon/bits/path_dump.h

    r100 r209  
    1 /* -*- C++ -*-
     1/* -*- mode: C++; indent-tabs-mode: nil; -*-
    22 *
    3  * This file is a part of LEMON, a generic C++ optimization library
     3 * This file is a part of LEMON, a generic C++ optimization library.
    44 *
    55 * Copyright (C) 2003-2008
    … …  
    5454      RevArcIt() {}
    5555      RevArcIt(Invalid) : path(0), current(INVALID) {}
    56       RevArcIt(const PredMapPath& _path) 
     56      RevArcIt(const PredMapPath& _path)
    5757        : path(&_path), current(_path.target) {
    5858        if (path->predMap[current] == INVALID) current = INVALID;
    … …  
    6969      }
    7070
    71       bool operator==(const RevArcIt& e) const { 
    72         return current == e.current; 
     71      bool operator==(const RevArcIt& e) const {
     72        return current == e.current;
    7373      }
    7474
    7575      bool operator!=(const RevArcIt& e) const {
    76         return current != e.current; 
     76        return current != e.current;
    7777      }
    7878
    79       bool operator<(const RevArcIt& e) const { 
    80         return current < e.current; 
     79      bool operator<(const RevArcIt& e) const {
     80        return current < e.current;
    8181      }
    82      
     82
    8383    private:
    8484      const PredMapPath* path;
    … …  
    102102    typedef _PredMatrixMap PredMatrixMap;
    103103
    104     PredMatrixMapPath(const Digraph& _digraph, 
     104    PredMatrixMapPath(const Digraph& _digraph,
    105105                      const PredMatrixMap& _predMatrixMap,
    106                       typename Digraph::Node _source, 
     106                      typename Digraph::Node _source,
    107107                      typename Digraph::Node _target)
    108       : digraph(_digraph), predMatrixMap(_predMatrixMap), 
     108      : digraph(_digraph), predMatrixMap(_predMatrixMap),
    109109        source(_source), target(_target) {}
    110110
    … …  
    128128      RevArcIt() {}
    129129      RevArcIt(Invalid) : path(0), current(INVALID) {}
    130       RevArcIt(const PredMatrixMapPath& _path) 
     130      RevArcIt(const PredMatrixMapPath& _path)
    131131        : path(&_path), current(_path.target) {
    132         if (path->predMatrixMap(path->source, current) == INVALID) 
     132        if (path->predMatrixMap(path->source, current) == INVALID)
    133133          current = INVALID;
    134134      }
    … …  
    139139
    140140      RevArcIt& operator++() {
    141         current = 
     141        current =
    142142          path->digraph.source(path->predMatrixMap(path->source, current));
    143         if (path->predMatrixMap(path->source, current) == INVALID) 
     143        if (path->predMatrixMap(path->source, current) == INVALID)
    144144          current = INVALID;
    145145        return *this;
    146146      }
    147147
    148       bool operator==(const RevArcIt& e) const { 
    149         return current == e.current; 
     148      bool operator==(const RevArcIt& e) const {
     149        return current == e.current;
    150150      }
    151151
    152152      bool operator!=(const RevArcIt& e) const {
    153         return current != e.current; 
     153    &nbs