COIN-OR::LEMON - Graph Library

About

Downloads

Documentation

Development

Issue Tracker

Browse Tickets

Custom Query

Roadmap

Browse Source

Local Info

Mailing Lists

Search


Ignore:
Files:
7 added
13 edited

Legend:

Unmodified
Added
Removed

  • doc/CMakeLists.txt

    r225 r347  
    1414      COMMAND rm -rf gen-images
    1515      COMMAND mkdir gen-images
     16      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps
    1617      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps
    1718      COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps

  • doc/Makefile.am

    r317 r349  
    1515
    1616DOC_EPS_IMAGES18 = \
     17        grid_graph.eps \
    1718        nodeshape_0.eps \
    1819        nodeshape_1.eps \

  • doc/migration.dox

    r314 r355  
    2626
    2727Many of these changes adjusted automatically by the
    28 <tt>script/lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
     28<tt>lemon-0.x-to-1.x.sh</tt> tool. Those requiring manual
    2929update are typeset <b>boldface</b>.
    3030
    … …  
    5454
    5555\warning
    56 <b>The <tt>script/lemon-0.x-to-1.x.sh</tt> tool replaces all instances of
    57 the words \c graph, \c digraph, \c edge and \c arc, so it replaces them
    58 in strings, comments etc. as well as in all identifiers.</b>
     56<b>The <tt>lemon-0.x-to-1.x.sh</tt> script replaces the words \c graph,
     57\c ugraph, \c edge and \c uedge in your own identifiers and in
     58strings, comments etc. as well as in all LEMON specific identifiers.
     59So use the script carefully and make a backup copy of your source files
     60before applying the script to them.</b>
    5961
    6062\section migration-lgf LGF tools

  • lemon/Makefile.am

    r360 r361  
    3030        lemon/error.h \
    3131        lemon/graph_to_eps.h \
     32        lemon/grid_graph.h \
    3233        lemon/kruskal.h \
    3334        lemon/lgf_reader.h \
    … …  
    3637        lemon/maps.h \
    3738        lemon/math.h \
     39        lemon/max_matching.h \
    3840        lemon/nauty_reader.h \
    3941        lemon/path.h \
    4042        lemon/random.h \
    4143        lemon/smart_graph.h \
     44        lemon/suurballe.h \
    4245        lemon/time_measure.h \
    4346        lemon/tolerance.h \

  • lemon/bfs.h

    r301 r341  
    5252    ///Instantiates a PredMap.
    5353
    54     ///This function instantiates a PredMap.
     54    ///This function instantiates a PredMap. 
    5555    ///\param g is the digraph, to which we would like to define the
    5656    ///PredMap.
    … …  
    8181    ///The type of the map that indicates which nodes are reached.
    8282
    83     ///The type of the map that indicates which nodes are reached.
    84     ///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
     83    ///The type of the map that indicates which nodes are reached.///It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
    8584    typedef typename Digraph::template NodeMap<bool> ReachedMap;
    8685    ///Instantiates a ReachedMap.

  • lemon/list_graph.h

    r313 r341  
    841841
    842842    public:
    843       operator Edge() const { 
    844         return id != -1 ? edgeFromId(id / 2) : INVALID; 
     843      operator Edge() const {
     844        return id != -1 ? edgeFromId(id / 2) : INVALID;
    845845      }
    846846

  • lemon/random.h

    r280 r352  
    541541    /// @{
    542542
    543     ///\name Initialization
    544     ///
    545     /// @{
    546 
    547543    /// \brief Default constructor
    548544    ///
    … …  
    709705    }
    710706
    711     /// @}
    712 
    713     ///\name Uniform distributions
    714     ///
    715     /// @{
    716 
    717707    /// \brief Returns a random real number from the range [0, 1)
    718708    ///
    … …  
    771761      return _random_bits::IntConversion<Number, Word>::convert(core);
    772762    }
    773 
    774     /// @}
    775763
    776764    unsigned int uinteger() {
    … …  
    807795    ///\name Non-uniform distributions
    808796    ///
    809 
    810797    ///@{
    811798
    812     /// \brief Returns a random bool
     799    /// \brief Returns a random bool with given probability of true result.
    813800    ///
    814801    /// It returns a random bool with given probability of true result.
    … …  
    817804    }
    818805
    819     /// Standard Gauss distribution
    820 
    821     /// Standard Gauss distribution.
     806    /// Standard normal (Gauss) distribution
     807
     808    /// Standard normal (Gauss) distribution.
    822809    /// \note The Cartesian form of the Box-Muller
    823810    /// transformation is used to generate a random normal distribution.
    … …  
    832819      return std::sqrt(-2*std::log(S)/S)*V1;
    833820    }
    834     /// Gauss distribution with given mean and standard deviation
    835 
    836     /// Gauss distribution with given mean and standard deviation.
     821    /// Normal (Gauss) distribution with given mean and standard deviation
     822
     823    /// Normal (Gauss) distribution with given mean and standard deviation.
    837824    /// \sa gauss()
    838825    double gauss(double mean,double std_dev)
    839826    {
    840827      return gauss()*std_dev+mean;
     828    }
     829
     830    /// Lognormal distribution
     831
     832    /// Lognormal distribution. The parameters are the mean and the standard
     833    /// deviation of <tt>exp(X)</tt>.
     834    ///
     835    double lognormal(double n_mean,double n_std_dev)
     836    {
     837      return std::exp(gauss(n_mean,n_std_dev));
     838    }
     839    /// Lognormal distribution
     840
     841    /// Lognormal distribution. The parameter is an <tt>std::pair</tt> of
     842    /// the mean and the standard deviation of <tt>exp(X)</tt>.
     843    ///
     844    double lognormal(const std::pair<double,double> &params)
     845    {
     846      return std::exp(gauss(params.first,params.second));
     847    }
     848    /// Compute the lognormal parameters from mean and standard deviation
     849
     850    /// This function computes the lognormal parameters from mean and
     851    /// standard deviation. The return value can direcly be passed to
     852    /// lognormal().
     853    std::pair<double,double> lognormalParamsFromMD(double mean,
     854                                                   double std_dev)
     855    {
     856      double fr=std_dev/mean;
     857      fr*=fr;
     858      double lg=std::log(1+fr);
     859      return std::pair<double,double>(std::log(mean)-lg/2.0,std::sqrt(lg));
     860    }
     861    /// Lognormal distribution with given mean and standard deviation
     862
     863    /// Lognormal distribution with given mean and standard deviation.
     864    ///
     865    double lognormalMD(double mean,double std_dev)
     866    {
     867      return lognormal(lognormalParamsFromMD(mean,std_dev));
    841868    }
    842869
    … …  
    944971    ///\name Two dimensional distributions
    945972    ///
    946 
    947973    ///@{
    948974
    … …  
    961987      return dim2::Point<double>(V1,V2);
    962988    }
    963     /// A kind of two dimensional Gauss distribution
     989    /// A kind of two dimensional normal (Gauss) distribution
    964990
    965991    /// This function provides a turning symmetric two-dimensional distribution.

  • lemon/smart_graph.h

    r313 r341  
    465465
    466466    public:
    467       operator Edge() const { 
    468         return _id != -1 ? edgeFromId(_id / 2) : INVALID; 
     467      operator Edge() const {
     468        return _id != -1 ? edgeFromId(_id / 2) : INVALID;
    469469      }
    470470

  • scripts/unify-sources.sh

    r208 r353  
    44HGROOT=`hg root`
    55
    6 function update_header() {
     6# file enumaration modes
     7
     8function all_files() {
     9    hg status -a -m -c |
     10    cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |
     11    while read file; do echo $HGROOT/$file; done
     12}
     13
     14function modified_files() {
     15    hg status -a -m |
     16    cut -d ' ' -f 2 | grep -E  '(\.(cc|h|dox)$|Makefile\.am$)' |
     17    while read file; do echo $HGROOT/$file; done
     18}
     19
     20function changed_files() {
     21    {
     22        if [ -n "$HG_PARENT1" ]
     23        then
     24            hg status --rev $HG_PARENT1:$HG_NODE -a -m
     25        fi
     26        if [ -n "$HG_PARENT2" ]
     27        then
     28            hg status --rev $HG_PARENT2:$HG_NODE -a -m
     29        fi
     30    } | cut -d ' ' -f 2 | grep -E '(\.(cc|h|dox)$|Makefile\.am$)' |
     31    sort | uniq |
     32    while read file; do echo $HGROOT/$file; done
     33}
     34
     35function given_files() {
     36    for file in $GIVEN_FILES
     37    do
     38        echo $file
     39    done
     40}
     41
     42# actions
     43
     44function update_action() {
     45    if ! diff -q $1 $2 >/dev/null
     46    then
     47        echo -n " [$3 updated]"
     48        rm $2
     49        mv $1 $2
     50        CHANGED=YES
     51    fi
     52}
     53
     54function update_warning() {
     55    echo -n " [$2 warning]"
     56    WARNED=YES
     57}
     58
     59function update_init() {
     60    echo Update source files...
     61    TOTAL_FILES=0
     62    CHANGED_FILES=0
     63    WARNED_FILES=0
     64}
     65
     66function update_done() {
     67    echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
     68    echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
     69}
     70
     71function update_begin() {
     72    ((TOTAL_FILES++))
     73    CHANGED=NO
     74    WARNED=NO
     75}
     76
     77function update_end() {
     78    if [ $CHANGED == YES ]
     79    then
     80        ((++CHANGED_FILES))
     81    fi
     82    if [ $WARNED == YES ]
     83    then
     84        ((++WARNED_FILES))
     85    fi
     86}
     87
     88function check_action() {
     89    if [ "$3" == 'tabs' ]
     90    then
     91        PATTERN=$(echo -e '\t')
     92    elif [ "$3" == 'trailing spaces' ]
     93    then
     94        PATTERN='\ +$'
     95    else
     96        PATTERN='*'
     97    fi
     98
     99    if ! diff -q $1 $2 >/dev/null
     100    then
     101        if [ "$PATTERN" == '*' ]
     102        then
     103            diff $1 $2 | grep '^[0-9]' | sed "s|^\(.*\)c.*$|$2:\1: check failed: $3|g" |
     104              sed "s/:\([0-9]*\),\([0-9]*\):\(.*\)$/:\1:\3 (until line \2)/g"
     105        else
     106            grep -n -E "$PATTERN" $2 | sed "s|^\([0-9]*\):.*$|$2:\1: check failed: $3|g"
     107        fi
     108        FAILED=YES
     109    fi
     110}
     111
     112function check_warning() {
     113    if [ "$2" == 'long lines' ]
     114    then
     115        grep -n -E '.{81,}' $1 | sed "s|^\([0-9]*\):.*$|$1:\1: warning: $2|g"
     116    else
     117        echo "$1: warning: $2"
     118    fi
     119    WARNED=YES
     120}
     121
     122function check_init() {
     123    echo Check source files...
     124    FAILED_FILES=0
     125    WARNED_FILES=0
     126    TOTAL_FILES=0
     127}
     128
     129function check_done() {
     130    echo $FAILED_FILES out of $TOTAL_FILES files has been failed.
     131    echo $WARNED_FILES out of $TOTAL_FILES files triggered warnings.
     132
     133    if [ $FAILED_FILES -gt 0 ]
     134    then
     135        return 1
     136    elif [ $WARNED_FILES -gt 0 ]
     137    then
     138        if [ "$WARNING" == 'INTERACTIVE' ]
     139        then
     140            echo -n "Are the files with warnings acceptable? (yes/no) "
     141            while read answer
     142            do
     143                if [ "$answer" == 'yes' ]
     144                then
     145                    return 0
     146                elif [ "$answer" == 'no' ]
     147                then
     148                    return 1
     149                fi
     150                echo -n "Are the files with warnings acceptable? (yes/no) "
     151            done
     152        elif [ "$WARNING" == 'WERROR' ]
     153        then
     154            return 1
     155        fi
     156    fi
     157}
     158
     159function check_begin() {
     160    ((TOTAL_FILES++))
     161    FAILED=NO
     162    WARNED=NO
     163}
     164
     165function check_end() {
     166    if [ $FAILED == YES ]
     167    then
     168        ((++FAILED_FILES))
     169    fi
     170    if [ $WARNED == YES ]
     171    then
     172        ((++WARNED_FILES))
     173    fi
     174}
     175
     176
     177
     178# checks
     179
     180function header_check() {
     181    if echo $1 | grep -q -E 'Makefile\.am$'
     182    then
     183        return
     184    fi
     185
    7186    TMP_FILE=`mktemp`
    8     FILE_NAME=$1
    9187
    10188    (echo "/* -*- mode: C++; indent-tabs-mode: nil; -*-
    … …  
    26204 */
    27205"
    28         awk 'BEGIN { pm=0; }
     206    awk 'BEGIN { pm=0; }
    29207     pm==3 { print }
    30208     /\/\* / && pm==0 { pm=1;}
    … …  
    32210     /\*\// && pm==1 { pm=2;}
    33211    ' $1
    34         ) >$TMP_FILE
    35 
    36     HEADER_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
    37 
    38     rm $FILE_NAME
    39     mv $TMP_FILE $FILE_NAME
    40 }
    41 
    42 function update_tabs() {
     212    ) >$TMP_FILE
     213
     214    "$ACTION"_action "$TMP_FILE" "$1" header
     215}
     216
     217function tabs_check() {
     218    if echo $1 | grep -q -v -E 'Makefile\.am$'
     219    then
     220        OLD_PATTERN=$(echo -e '\t')
     221        NEW_PATTERN='        '
     222    else
     223        OLD_PATTERN='        '
     224        NEW_PATTERN=$(echo -e '\t')
     225    fi
    43226    TMP_FILE=`mktemp`
    44     FILE_NAME=$1
    45 
    46     cat $1 |
    47     sed -e 's/\t/        /g' >$TMP_FILE
    48 
    49     TABS_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
    50 
    51     rm $FILE_NAME
    52     mv $TMP_FILE $FILE_NAME
    53 }
    54 
    55 function remove_trailing_space() {
     227    cat $1 | sed -e "s/$OLD_PATTERN/$NEW_PATTERN/g" >$TMP_FILE
     228
     229    "$ACTION"_action "$TMP_FILE" "$1" 'tabs'
     230}
     231
     232function spaces_check() {
    56233    TMP_FILE=`mktemp`
    57     FILE_NAME=$1
    58 
    59     cat $1 |
    60     sed -e 's/ \+$//g' >$TMP_FILE
    61 
    62     SPACES_CH=`diff -q $TMP_FILE $FILE_NAME >/dev/null&&echo NO||echo YES`
    63 
    64     rm $FILE_NAME
    65     mv $TMP_FILE $FILE_NAME
    66 }
    67 
    68 function long_line_test() {
    69     cat $1 |grep -q -E '.{81,}'
    70 }
    71 
    72 function update_file() {
    73     echo -n '    update' $i ...
    74 
    75     update_header $1
    76     update_tabs $1
    77     remove_trailing_space $1
    78 
    79     CHANGED=NO;
    80     if [[ $HEADER_CH = YES ]];
    81     then
    82         echo -n '  [header updated]'
    83         CHANGED=YES;
    84     fi
    85     if [[ $TABS_CH = YES ]];
    86     then
    87         echo -n ' [tabs removed]'
    88         CHANGED=YES;
    89     fi
    90     if [[ $SPACES_CH = YES ]];
    91     then
    92         echo -n ' [trailing spaces removed]'
    93         CHANGED=YES;
    94     fi
    95     if long_line_test $1 ;
    96     then
    97         echo -n ' [LONG LINES]'
    98         ((LONG_LINE_FILES++))
    99     fi
    100     echo
    101     if [[ $CHANGED = YES ]];
    102     then
    103         ((CHANGED_FILES++))
    104     fi
    105 }
    106 
    107 CHANGED_FILES=0
    108 TOTAL_FILES=0
    109 LONG_LINE_FILES=0
    110 if [ $# == 0 ]; then
    111     echo Update all source files...
    112     for i in `hg manifest|grep -E  '\.(cc|h|dox)$'`
     234    cat $1 | sed -e 's/ \+$//g' >$TMP_FILE
     235
     236    "$ACTION"_action "$TMP_FILE" "$1" 'trailing spaces'
     237}
     238
     239function long_lines_check() {
     240    if cat $1 | grep -q -E '.{81,}'
     241    then
     242        "$ACTION"_warning $1 'long lines'
     243    fi
     244}
     245
     246# process the file
     247
     248function process_file() {
     249    if [ "$ACTION" == 'update' ]
     250    then
     251        echo -n "    $ACTION $1..."
     252    else
     253        echo "    $ACTION $1..."
     254    fi
     255
     256    CHECKING="header tabs spaces long_lines"
     257
     258    "$ACTION"_begin $1
     259    for check in $CHECKING
    113260    do
    114         update_file $HGROOT/$i
    115         ((TOTAL_FILES++))
     261        "$check"_check $1
    116262    done
    117     echo '  done.'
    118 else
    119     for i in $*
     263    "$ACTION"_end $1
     264    if [ "$ACTION" == 'update' ]
     265    then
     266        echo
     267    fi
     268}
     269
     270function process_all {
     271    "$ACTION"_init
     272    while read file
    120273    do
    121         update_file $i
    122         ((TOTAL_FILES++))
    123     done
     274        process_file $file
     275    done < <($FILES)
     276    "$ACTION"_done
     277}
     278
     279while [ $# -gt 0 ]
     280do
     281   
     282    if [ "$1" == '--help' ] || [ "$1" == '-h' ]
     283    then
     284        echo -n \
     285"Usage:
     286  $0 [OPTIONS] [files]
     287Options:
     288  --dry-run|-n
     289     Check the files, but do not modify them.
     290  --interactive|-i
     291     If --dry-run is specified and the checker emits warnings,
     292     then the user is asked if the warnings should be considered
     293     errors.
     294  --werror|-w
     295     Make all warnings into errors.
     296  --all|-a
     297     Check all source files in the repository.
     298  --modified|-m
     299     Check only the modified (and new) source files. This option is
     300     useful to check the modification before making a commit.
     301  --changed|-c
     302     Check only the changed source files compared to the parent(s) of
     303     the current hg node.  This option is useful as hg hook script.
     304     To automatically check all your changes before making a commit,
     305     add the following section to the appropriate .hg/hgrc file.
     306
     307       [hooks]
     308       pretxncommit.checksources = scripts/unify-sources.sh -c -n -i
     309
     310  --help|-h
     311     Print this help message.
     312  files
     313     The files to check/unify. If no file names are given, the modified
     314     source files will be checked/unified (just like using the
     315     --modified|-m option).
     316"
     317        exit 0
     318    elif [ "$1" == '--dry-run' ] || [ "$1" == '-n' ]
     319    then
     320        [ -n "$ACTION" ] && echo "Conflicting action options" >&2 && exit 1
     321        ACTION=check
     322    elif [ "$1" == "--all" ] || [ "$1" == '-a' ]
     323    then
     324        [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
     325        FILES=all_files
     326    elif [ "$1" == "--changed" ] || [ "$1" == '-c' ]
     327    then
     328        [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
     329        FILES=changed_files
     330    elif [ "$1" == "--modified" ] || [ "$1" == '-m' ]
     331    then
     332        [ -n "$FILES" ] && echo "Conflicting target options" >&2 && exit 1
     333        FILES=modified_files
     334    elif [ "$1" == "--interactive" ] || [ "$1" == "-i" ]
     335    then
     336        [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
     337        WARNING='INTERACTIVE'
     338    elif [ "$1" == "--werror" ] || [ "$1" == "-w" ]
     339    then
     340        [ -n "$WARNING" ] && echo "Conflicting warning options" >&2 && exit 1
     341        WARNING='WERROR'
     342    elif [ $(echo x$1 | cut -c 2) == '-' ]
     343    then
     344        echo "Invalid option $1" >&2 && exit 1
     345    else
     346        [ -n "$FILES" ] && echo "Invalid option $1" >&2 && exit 1
     347        GIVEN_FILES=$@
     348        FILES=given_files
     349        break
     350    fi
     351   
     352    shift
     353done
     354
     355if [ -z $FILES ]
     356then
     357    FILES=modified_files
    124358fi
    125 echo $CHANGED_FILES out of $TOTAL_FILES files has been changed.
    126 if [[ $LONG_LINE_FILES -gt 1 ]]; then
    127     echo
    128     echo WARNING: $LONG_LINE_FILES files contains long lines!   
    129     echo
    130 elif [[ $LONG_LINE_FILES -gt 0 ]]; then
    131     echo
    132     echo WARNING: a file contains long lines!
    133     echo
     359
     360if [ -z $ACTION ]
     361then
     362    ACTION=update
    134363fi
     364
     365process_all

  • test/CMakeLists.txt

    r225 r339  
    1717  kruskal_test
    1818  maps_test
     19  max_matching_test
    1920  random_test
    2021  path_test

  • test/Makefile.am

    r228 r357  
    11EXTRA_DIST += \
    2         test/CMakeLists.txt
     2        test/CMakeLists.txt \
     3        test/min_cost_flow_test.lgf
    34
    45noinst_HEADERS += \
    … …  
    2021        test/kruskal_test \
    2122        test/maps_test \
     23        test/max_matching_test \
    2224        test/random_test \
    2325        test/path_test \
     26        test/suurballe_test \
    2427        test/test_tools_fail \
    2528        test/test_tools_pass \
    … …  
    4346test_kruskal_test_SOURCES = test/kruskal_test.cc
    4447test_maps_test_SOURCES = test/maps_test.cc
     48test_max_matching_test_SOURCES = test/max_matching_test.cc
    4549test_path_test_SOURCES = test/path_test.cc
     50test_suurballe_test_SOURCES = test/suurballe_test.cc
    4651test_random_test_SOURCES = test/random_test.cc
    4752test_test_tools_fail_SOURCES = test/test_tools_fail.cc

  • test/graph_test.cc

    r228 r348  
    2121#include <lemon/smart_graph.h>
    2222// #include <lemon/full_graph.h>
    23 // #include <lemon/grid_graph.h>
     23#include <lemon/grid_graph.h>
    2424
    2525#include "test_tools.h"
    … …  
    129129//    checkGraphIterators<FullGraph>();
    130130//  }
    131 //  { // Checking GridGraph
    132 //    checkConcept<Graph, GridGraph>();
    133 //    checkGraphIterators<GridGraph>();
    134 //  }
     131  { // Checking GridGraph
     132    checkConcept<Graph, GridGraph>();
     133  }
    135134}
    136135
    … …  
    189188}
    190189
    191 // void checkGridGraph(const GridGraph& g, int w, int h) {
    192 //   check(g.width() == w, "Wrong width");
    193 //   check(g.height() == h, "Wrong height");
    194 
    195 //   for (int i = 0; i < w; ++i) {
    196 //     for (int j = 0; j < h; ++j) {
    197 //       check(g.col(g(i, j)) == i, "Wrong col");
    198 //       check(g.row(g(i, j)) == j, "Wrong row");
    199 //     }
    200 //   }
    201 
    202 //   for (int i = 0; i < w; ++i) {
    203 //     for (int j = 0; j < h - 1; ++j) {
    204 //       check(g.source(g.down(g(i, j))) == g(i, j), "Wrong down");
    205 //       check(g.target(g.down(g(i, j))) == g(i, j + 1), "Wrong down");
    206 //     }
    207 //     check(g.down(g(i, h - 1)) == INVALID, "Wrong down");
    208 //   }
    209 
    210 //   for (int i = 0; i < w; ++i) {
    211 //     for (int j = 1; j < h; ++j) {
    212 //       check(g.source(g.up(g(i, j))) == g(i, j), "Wrong up");
    213 //       check(g.target(g.up(g(i, j))) == g(i, j - 1), "Wrong up");
    214 //     }
    215 //     check(g.up(g(i, 0)) == INVALID, "Wrong up");
    216 //   }
    217 
    218 //   for (int j = 0; j < h; ++j) {
    219 //     for (int i = 0; i < w - 1; ++i) {
    220 //       check(g.source(g.right(g(i, j))) == g(i, j), "Wrong right");
    221 //       check(g.target(g.right(g(i, j))) == g(i + 1, j), "Wrong right");
    222 //     }
    223 //     check(g.right(g(w - 1, j)) == INVALID, "Wrong right");
    224 //   }
    225 
    226 //   for (int j = 0; j < h; ++j) {
    227 //     for (int i = 1; i < w; ++i) {
    228 //       check(g.source(g.left(g(i, j))) == g(i, j), "Wrong left");
    229 //       check(g.target(g.left(g(i, j))) == g(i - 1, j), "Wrong left");
    230 //     }
    231 //     check(g.left(g(0, j)) == INVALID, "Wrong left");
    232 //   }
    233 // }
     190void checkGridGraph(int width, int height) {
     191  typedef GridGraph Graph;
     192  GRAPH_TYPEDEFS(Graph);
     193  Graph G(width, height);
     194
     195  check(G.width() == width, "Wrong column number");
     196  check(G.height() == height, "Wrong row number");
     197
     198  for (int i = 0; i < width; ++i) {
     199    for (int j = 0; j < height; ++j) {
     200      check(G.col(G(i, j)) == i, "Wrong column");
     201      check(G.row(G(i, j)) == j, "Wrong row");
     202      check(G.pos(G(i, j)).x == i, "Wrong column");
     203      check(G.pos(G(i, j)).y == j, "Wrong row");
     204    }
     205  }
     206
     207  for (int j = 0; j < height; ++j) {
     208    for (int i = 0; i < width - 1; ++i) {
     209      check(G.source(G.right(G(i, j))) == G(i, j), "Wrong right");
     210      check(G.target(G.right(G(i, j))) == G(i + 1, j), "Wrong right");
     211    }
     212    check(G.right(G(width - 1, j)) == INVALID, "Wrong right");
     213  }
     214
     215  for (int j = 0; j < height; ++j) {
     216    for (int i = 1; i < width; ++i) {
     217      check(G.source(G.left(G(i, j))) == G(i, j), "Wrong left");
     218      check(G.target(G.left(G(i, j))) == G(i - 1, j), "Wrong left");
     219    }
     220    check(G.left(G(0, j)) == INVALID, "Wrong left");
     221  }
     222
     223  for (int i = 0; i < width; ++i) {
     224    for (int j = 0; j < height - 1; ++j) {
     225      check(G.source(G.up(G(i, j))) == G(i, j), "Wrong up");
     226      check(G.target(G.up(G(i, j))) == G(i, j + 1), "Wrong up");
     227    }
     228    check(G.up(G(i, height - 1)) == INVALID, "Wrong up");
     229  }
     230
     231  for (int i = 0; i < width; ++i) {
     232    for (int j = 1; j < height; ++j) {
     233      check(G.source(G.down(G(i, j))) == G(i, j), "Wrong down");
     234      check(G.target(G.down(G(i, j))) == G(i, j - 1), "Wrong down");
     235    }
     236    check(G.down(G(i, 0)) == INVALID, "Wrong down");
     237  }
     238
     239  checkGraphNodeList(G, width * height);
     240  checkGraphEdgeList(G, width * (height - 1) + (width - 1) * height);
     241  checkGraphArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
     242
     243  for (NodeIt n(G); n != INVALID; ++n) {
     244    int nb = 4;
     245    if (G.col(n) == 0) --nb;
     246    if (G.col(n) == width - 1) --nb;
     247    if (G.row(n) == 0) --nb;
     248    if (G.row(n) == height - 1) --nb;
     249
     250    checkGraphOutArcList(G, n, nb);
     251    checkGraphInArcList(G, n, nb);
     252    checkGraphIncEdgeList(G, n, nb);
     253  }
     254
     255  checkArcDirections(G);
     256
     257  checkGraphConArcList(G, 2 * (width * (height - 1) + (width - 1) * height));
     258  checkGraphConEdgeList(G, width * (height - 1) + (width - 1) * height);
     259
     260  checkNodeIds(G);
     261  checkArcIds(G);
     262  checkEdgeIds(G);
     263  checkGraphNodeMap(G);
     264  checkGraphArcMap(G);
     265  checkGraphEdgeMap(G);
     266
     267}
    234268
    235269void checkGraphs() {
    … …  
    247281//     checkGraphEdgeList(g, 10);
    248282//   }
    249 //   { // Checking GridGraph
    250 //     GridGraph g(5, 6);
    251 //     checkGraphNodeList(g, 30);
    252 //     checkGraphEdgeList(g, 49);
    253 //     checkGridGraph(g, 5, 6);
    254 //   }
     283  { // Checking GridGraph
     284    checkGridGraph(5, 8);
     285    checkGridGraph(8, 5);
     286    checkGridGraph(5, 5);
     287    checkGridGraph(0, 0);
     288    checkGridGraph(1, 1);
     289  }
    255290}
    256291

  • tools/lemon-0.x-to-1.x.sh

    r310 r356  
    44
    55if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then
    6         echo "Usage:"
    7         echo "  $0 source-file"
    8         exit
     6    echo "Usage:"
     7    echo "  $0 source-file(s)"
     8    exit
    99fi
    1010
    11 TMP=`mktemp`
    12 
    13 sed     -e "s/undirected graph/_gr_aph_label_/g"\
    14         -e "s/undirected edge/_ed_ge_label_/g"\
    15         -e "s/graph_/_gr_aph_label__/g"\
    16         -e "s/_graph/__gr_aph_label_/g"\
    17         -e "s/UGraph/_Gr_aph_label_/g"\
    18         -e "s/uGraph/_gr_aph_label_/g"\
    19         -e "s/ugraph/_gr_aph_label_/g"\
    20         -e "s/Graph/_Digr_aph_label_/g"\
    21         -e "s/graph/_digr_aph_label_/g"\
    22         -e "s/UEdge/_Ed_ge_label_/g"\
    23         -e "s/uEdge/_ed_ge_label_/g"\
    24         -e "s/uedge/_ed_ge_label_/g"\
    25         -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
    26         -e "s/Edge/_Ar_c_label_/g"\
    27         -e "s/edge/_ar_c_label_/g"\
    28         -e "s/ANode/_Re_d_label_/g"\
    29         -e "s/BNode/_Blu_e_label_/g"\
    30         -e "s/A-Node/_Re_d_label_/g"\
    31         -e "s/B-Node/_Blu_e_label_/g"\
    32         -e "s/anode/_re_d_label_/g"\
    33         -e "s/bnode/_blu_e_label_/g"\
    34         -e "s/aNode/_re_d_label_/g"\
    35         -e "s/bNode/_blu_e_label_/g"\
    36         -e "s/_Digr_aph_label_/Digraph/g"\
    37         -e "s/_digr_aph_label_/digraph/g"\
    38         -e "s/_Gr_aph_label_/Graph/g"\
    39         -e "s/_gr_aph_label_/graph/g"\
    40         -e "s/_Ar_c_label_/Arc/g"\
    41         -e "s/_ar_c_label_/arc/g"\
    42         -e "s/_Ed_ge_label_/Edge/g"\
    43         -e "s/_ed_ge_label_/edge/g"\
    44         -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
    45         -e "s/_Re_d_label_/Red/g"\
    46         -e "s/_Blu_e_label_/Blue/g"\
    47         -e "s/_re_d_label_/red/g"\
    48         -e "s/_blu_e_label_/blue/g"\
    49         -e "s/\(\W\)DefPredMap\(\W\)/\1SetPredMap\2/g"\
    50         -e "s/\(\W\)DefPredMap$/\1SetPredMap/g"\
    51         -e "s/^DefPredMap\(\W\)/SetPredMap\1/g"\
    52         -e "s/^DefPredMap$/SetPredMap/g"\
    53         -e "s/\(\W\)DefDistMap\(\W\)/\1SetDistMap\2/g"\
    54         -e "s/\(\W\)DefDistMap$/\1SetDistMap/g"\
    55         -e "s/^DefDistMap\(\W\)/SetDistMap\1/g"\
    56         -e "s/^DefDistMap$/SetDistMap/g"\
    57         -e "s/\(\W\)DefReachedMap\(\W\)/\1SetReachedMap\2/g"\
    58         -e "s/\(\W\)DefReachedMap$/\1SetReachedMap/g"\
    59         -e "s/^DefReachedMap\(\W\)/SetReachedMap\1/g"\
    60         -e "s/^DefReachedMap$/SetReachedMap/g"\
    61         -e "s/\(\W\)DefProcessedMap\(\W\)/\1SetProcessedMap\2/g"\
    62         -e "s/\(\W\)DefProcessedMap$/\1SetProcessedMap/g"\
    63         -e "s/^DefProcessedMap\(\W\)/SetProcessedMap\1/g"\
    64         -e "s/^DefProcessedMap$/SetProcessedMap/g"\
    65         -e "s/\(\W\)DefHeap\(\W\)/\1SetHeap\2/g"\
    66         -e "s/\(\W\)DefHeap$/\1SetHeap/g"\
    67         -e "s/^DefHeap\(\W\)/SetHeap\1/g"\
    68         -e "s/^DefHeap$/SetHeap/g"\
    69         -e "s/\(\W\)DefStandardHeap\(\W\)/\1SetStandradHeap\2/g"\
    70         -e "s/\(\W\)DefStandardHeap$/\1SetStandradHeap/g"\
    71         -e "s/^DefStandardHeap\(\W\)/SetStandradHeap\1/g"\
    72         -e "s/^DefStandardHeap$/SetStandradHeap/g"\
    73         -e "s/\(\W\)DefOperationTraits\(\W\)/\1SetOperationTraits\2/g"\
    74         -e "s/\(\W\)DefOperationTraits$/\1SetOperationTraits/g"\
    75         -e "s/^DefOperationTraits\(\W\)/SetOperationTraits\1/g"\
    76         -e "s/^DefOperationTraits$/SetOperationTraits/g"\
    77         -e "s/\(\W\)DefProcessedMapToBeDefaultMap\(\W\)/\1SetStandardProcessedMap\2/g"\
    78         -e "s/\(\W\)DefProcessedMapToBeDefaultMap$/\1SetStandardProcessedMap/g"\
    79         -e "s/^DefProcessedMapToBeDefaultMap\(\W\)/SetStandardProcessedMap\1/g"\
    80         -e "s/^DefProcessedMapToBeDefaultMap$/SetStandardProcessedMap/g"\
    81         -e "s/\(\W\)IntegerMap\(\W\)/\1RangeMap\2/g"\
    82         -e "s/\(\W\)IntegerMap$/\1RangeMap/g"\
    83         -e "s/^IntegerMap\(\W\)/RangeMap\1/g"\
    84         -e "s/^IntegerMap$/RangeMap/g"\
    85         -e "s/\(\W\)integerMap\(\W\)/\1rangeMap\2/g"\
    86         -e "s/\(\W\)integerMap$/\1rangeMap/g"\
    87         -e "s/^integerMap\(\W\)/rangeMap\1/g"\
    88         -e "s/^integerMap$/rangeMap/g"\
    89         -e "s/\(\W\)copyGraph\(\W\)/\1graphCopy\2/g"\
    90         -e "s/\(\W\)copyGraph$/\1graphCopy/g"\
    91         -e "s/^copyGraph\(\W\)/graphCopy\1/g"\
    92         -e "s/^copyGraph$/graphCopy/g"\
    93         -e "s/\(\W\)copyDigraph\(\W\)/\1digraphCopy\2/g"\
    94         -e "s/\(\W\)copyDigraph$/\1digraphCopy/g"\
    95         -e "s/^copyDigraph\(\W\)/digraphCopy\1/g"\
    96         -e "s/^copyDigraph$/digraphCopy/g"\
    97         -e "s/\(\W\)\([sS]\)tdMap\(\W\)/\1\2parseMap\3/g"\
    98         -e "s/\(\W\)\([sS]\)tdMap$/\1\2parseMap/g"\
    99         -e "s/^\([sS]\)tdMap\(\W\)/\1parseMap\2/g"\
    100         -e "s/^\([sS]\)tdMap$/\1parseMap/g"\
    101         -e "s/\(\W\)\([Ff]\)unctorMap\(\W\)/\1\2unctorToMap\3/g"\
    102         -e "s/\(\W\)\([Ff]\)unctorMap$/\1\2unctorToMap/g"\
    103         -e "s/^\([Ff]\)unctorMap\(\W\)/\1unctorToMap\2/g"\
    104         -e "s/^\([Ff]\)unctorMap$/\1unctorToMap/g"\
    105         -e "s/\(\W\)\([Mm]\)apFunctor\(\W\)/\1\2apToFunctor\3/g"\
    106         -e "s/\(\W\)\([Mm]\)apFunctor$/\1\2apToFunctor/g"\
    107         -e "s/^\([Mm]\)apFunctor\(\W\)/\1apToFunctor\2/g"\
    108         -e "s/^\([Mm]\)apFunctor$/\1apToFunctor/g"\
    109         -e "s/\(\W\)\([Ff]\)orkWriteMap\(\W\)/\1\2orkMap\3/g"\
    110         -e "s/\(\W\)\([Ff]\)orkWriteMap$/\1\2orkMap/g"\
    111         -e "s/^\([Ff]\)orkWriteMap\(\W\)/\1orkMap\2/g"\
    112         -e "s/^\([Ff]\)orkWriteMap$/\1orkMap/g"\
    113         -e "s/\(\W\)StoreBoolMap\(\W\)/\1LoggerBoolMap\2/g"\
    114         -e "s/\(\W\)StoreBoolMap$/\1LoggerBoolMap/g"\
    115         -e "s/^StoreBoolMap\(\W\)/LoggerBoolMap\1/g"\
    116         -e "s/^StoreBoolMap$/LoggerBoolMap/g"\
    117         -e "s/\(\W\)storeBoolMap\(\W\)/\1loggerBoolMap\2/g"\
    118         -e "s/\(\W\)storeBoolMap$/\1loggerBoolMap/g"\
    119         -e "s/^storeBoolMap\(\W\)/loggerBoolMap\1/g"\
    120         -e "s/^storeBoolMap$/loggerBoolMap/g"\
    121         -e "s/\(\W\)BoundingBox\(\W\)/\1Box\2/g"\
    122         -e "s/\(\W\)BoundingBox$/\1Box/g"\
    123         -e "s/^BoundingBox\(\W\)/Box\1/g"\
    124         -e "s/^BoundingBox$/Box/g"\
    125 <$1 > $TMP
    126 
    127 mv $TMP $1
     11for i in $@
     12do
     13    echo Update $i...
     14    TMP=`mktemp`
     15    sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\
     16        -e "s/\<undirected graphs\>/_gr_aph_label_s/g"\
     17        -e "s/\<undirected edge\>/_ed_ge_label_/g"\
     18        -e "s/\<undirected edges\>/_ed_ge_label_s/g"\
     19        -e "s/\<directed graph\>/_digr_aph_label_/g"\
     20        -e "s/\<directed graphs\>/_digr_aph_label_s/g"\
     21        -e "s/\<directed edge\>/_ar_c_label_/g"\
     22        -e "s/\<directed edges\>/_ar_c_label_s/g"\
     23        -e "s/UGraph/_Gr_aph_label_/g"\
     24        -e "s/u[Gg]raph/_gr_aph_label_/g"\
     25        -e "s/\<Graph\>/_Digr_aph_label_/g"\
     26        -e "s/\<graph\>/_digr_aph_label_/g"\
     27        -e "s/\<Graphs\>/_Digr_aph_label_s/g"\
     28        -e "s/\<graphs\>/_digr_aph_label_s/g"\
     29        -e "s/_Graph/__Gr_aph_label_/g"\
     30        -e "s/\([Gg]\)raph\([a-z_]\)/_\1r_aph_label_\2/g"\
     31        -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\
     32        -e "s/Graph/_Digr_aph_label_/g"\
     33        -e "s/graph/_digr_aph_label_/g"\
     34        -e "s/UEdge/_Ed_ge_label_/g"\
     35        -e "s/u[Ee]dge/_ed_ge_label_/g"\
     36        -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
     37        -e "s/\<Edge\>/_Ar_c_label_/g"\
     38        -e "s/\<edge\>/_ar_c_label_/g"\
     39        -e "s/\<Edges\>/_Ar_c_label_s/g"\
     40        -e "s/\<edges\>/_ar_c_label_s/g"\
     41        -e "s/_Edge/__Ed_ge_label_/g"\
     42        -e "s/Edge\([a-z_]\)/_Ed_ge_label_\1/g"\
     43        -e "s/edge\([a-z_]\)/_ed_ge_label_\1/g"\
     44        -e "s/\([a-z_]\)edge/\1_ed_ge_label_/g"\
     45        -e "s/Edge/_Ar_c_label_/g"\
     46        -e "s/edge/_ar_c_label_/g"\
     47        -e "s/A[Nn]ode/_Re_d_label_/g"\
     48        -e "s/B[Nn]ode/_Blu_e_label_/g"\
     49        -e "s/A-[Nn]ode/_Re_d_label_/g"\
     50        -e "s/B-[Nn]ode/_Blu_e_label_/g"\
     51        -e "s/a[Nn]ode/_re_d_label_/g"\
     52        -e "s/b[Nn]ode/_blu_e_label_/g"\
     53        -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\
     54        -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\
     55        -e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\
     56        -e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\
     57        -e "s/_Digr_aph_label_/Digraph/g"\
     58        -e "s/_digr_aph_label_/digraph/g"\
     59        -e "s/_Gr_aph_label_/Graph/g"\
     60        -e "s/_gr_aph_label_/graph/g"\
     61        -e "s/_Ar_c_label_/Arc/g"\
     62        -e "s/_ar_c_label_/arc/g"\
     63        -e "s/_Ed_ge_label_/Edge/g"\
     64        -e "s/_ed_ge_label_/edge/g"\
     65        -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
     66        -e "s/_Re_d_label_/Red/g"\
     67        -e "s/_Blu_e_label_/Blue/g"\
     68        -e "s/_re_d_label_/red/g"\
     69        -e "s/_blu_e_label_/blue/g"\
     70        -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
     71        -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
     72        -e "s/DigraphToEps/GraphToEps/g"\
     73        -e "s/digraphToEps/graphToEps/g"\
     74        -e "s/\<DefPredMap\>/SetPredMap/g"\
     75        -e "s/\<DefDistMap\>/SetDistMap/g"\
     76        -e "s/\<DefReachedMap\>/SetReachedMap/g"\
     77        -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\
     78        -e "s/\<DefHeap\>/SetHeap/g"\
     79        -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\
     80        -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\
     81        -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\
     82        -e "s/\<copyGraph\>/graphCopy/g"\
     83        -e "s/\<copyDigraph\>/digraphCopy/g"\
     84        -e "s/\<IntegerMap\>/RangeMap/g"\
     85        -e "s/\<integerMap\>/rangeMap/g"\
     86        -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\
     87        -e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\
     88        -e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\
     89        -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\
     90        -e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\
     91        -e "s/\<storeBoolMap\>/loggerBoolMap/g"\
     92        -e "s/\<BoundingBox\>/Box/g"\
     93    <$i > $TMP
     94    mv $TMP $i
     95done
Note: See TracChangeset for help on using the changeset viewer.