tools/lemon-0.x-to-1.x.sh
author Peter Kovacs <kpeter@inf.elte.hu>
Thu, 12 Nov 2009 23:26:13 +0100
changeset 806 fa6f37d7a25b
parent 574 003367ffe66e
permissions -rwxr-xr-x
Entirely rework CapacityScaling (#180)

- Use the new interface similarly to NetworkSimplex.
- Rework the implementation using an efficient internal structure
for handling the residual network. This improvement made the
code much faster (up to 2-5 times faster on large graphs).
- Handle GEQ supply type (LEQ is not supported).
- Handle negative costs for arcs of finite capacity.
(Note that this algorithm cannot handle arcs of negative cost
and infinite upper bound, thus it returns UNBOUNDED if such
an arc exists.)
- Extend the documentation.
alpar@305
     1
#!/bin/bash
alpar@305
     2
alpar@305
     3
set -e
alpar@305
     4
alpar@305
     5
if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then
kpeter@323
     6
    echo "Usage:"
kpeter@323
     7
    echo "  $0 source-file(s)"
kpeter@323
     8
    exit
alpar@305
     9
fi
alpar@305
    10
kpeter@323
    11
for i in $@
kpeter@323
    12
do
kpeter@323
    13
    echo Update $i...
kpeter@323
    14
    TMP=`mktemp`
kpeter@344
    15
    sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\
kpeter@344
    16
        -e "s/\<undirected graphs\>/_gr_aph_label_s/g"\
kpeter@344
    17
        -e "s/\<undirected edge\>/_ed_ge_label_/g"\
kpeter@344
    18
        -e "s/\<undirected edges\>/_ed_ge_label_s/g"\
kpeter@344
    19
        -e "s/\<directed graph\>/_digr_aph_label_/g"\
kpeter@344
    20
        -e "s/\<directed graphs\>/_digr_aph_label_s/g"\
kpeter@344
    21
        -e "s/\<directed edge\>/_ar_c_label_/g"\
kpeter@344
    22
        -e "s/\<directed edges\>/_ar_c_label_s/g"\
kpeter@323
    23
        -e "s/UGraph/_Gr_aph_label_/g"\
kpeter@343
    24
        -e "s/u[Gg]raph/_gr_aph_label_/g"\
kpeter@555
    25
        -e "s/Graph\>/_Digr_aph_label_/g"\
kpeter@343
    26
        -e "s/\<graph\>/_digr_aph_label_/g"\
kpeter@555
    27
        -e "s/Graphs\>/_Digr_aph_label_s/g"\
kpeter@343
    28
        -e "s/\<graphs\>/_digr_aph_label_s/g"\
kpeter@555
    29
        -e "s/\([Gg]\)raph\([a-z]\)/_\1r_aph_label_\2/g"\
kpeter@343
    30
        -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\
kpeter@323
    31
        -e "s/Graph/_Digr_aph_label_/g"\
kpeter@323
    32
        -e "s/graph/_digr_aph_label_/g"\
kpeter@323
    33
        -e "s/UEdge/_Ed_ge_label_/g"\
kpeter@343
    34
        -e "s/u[Ee]dge/_ed_ge_label_/g"\
kpeter@323
    35
        -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\
kpeter@555
    36
        -e "s/Edge\>/_Ar_c_label_/g"\
kpeter@343
    37
        -e "s/\<edge\>/_ar_c_label_/g"\
kpeter@691
    38
        -e "s/_edge\>/__ar_c_label_/g"\
kpeter@555
    39
        -e "s/Edges\>/_Ar_c_label_s/g"\
kpeter@343
    40
        -e "s/\<edges\>/_ar_c_label_s/g"\
kpeter@691
    41
        -e "s/_edges\>/__ar_c_label_s/g"\
kpeter@555
    42
        -e "s/\([Ee]\)dge\([a-z]\)/_\1d_ge_label_\2/g"\
kpeter@555
    43
        -e "s/\([a-z]\)edge/\1_ed_ge_label_/g"\
kpeter@323
    44
        -e "s/Edge/_Ar_c_label_/g"\
kpeter@323
    45
        -e "s/edge/_ar_c_label_/g"\
kpeter@343
    46
        -e "s/A[Nn]ode/_Re_d_label_/g"\
kpeter@343
    47
        -e "s/B[Nn]ode/_Blu_e_label_/g"\
kpeter@343
    48
        -e "s/A-[Nn]ode/_Re_d_label_/g"\
kpeter@343
    49
        -e "s/B-[Nn]ode/_Blu_e_label_/g"\
kpeter@343
    50
        -e "s/a[Nn]ode/_re_d_label_/g"\
kpeter@343
    51
        -e "s/b[Nn]ode/_blu_e_label_/g"\
kpeter@344
    52
        -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\
kpeter@344
    53
        -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\
kpeter@344
    54
        -e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\
kpeter@344
    55
        -e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\
kpeter@323
    56
        -e "s/_Digr_aph_label_/Digraph/g"\
kpeter@323
    57
        -e "s/_digr_aph_label_/digraph/g"\
kpeter@323
    58
        -e "s/_Gr_aph_label_/Graph/g"\
kpeter@323
    59
        -e "s/_gr_aph_label_/graph/g"\
kpeter@323
    60
        -e "s/_Ar_c_label_/Arc/g"\
kpeter@323
    61
        -e "s/_ar_c_label_/arc/g"\
kpeter@323
    62
        -e "s/_Ed_ge_label_/Edge/g"\
kpeter@323
    63
        -e "s/_ed_ge_label_/edge/g"\
kpeter@323
    64
        -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\
kpeter@323
    65
        -e "s/_Re_d_label_/Red/g"\
kpeter@323
    66
        -e "s/_Blu_e_label_/Blue/g"\
kpeter@323
    67
        -e "s/_re_d_label_/red/g"\
kpeter@323
    68
        -e "s/_blu_e_label_/blue/g"\
kpeter@344
    69
        -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\
kpeter@344
    70
        -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\
kpeter@691
    71
        -e "s/\<digraph_adaptor\.h\>/adaptors.h/g"\
kpeter@691
    72
        -e "s/\<digraph_utils\.h\>/core.h/g"\
kpeter@691
    73
        -e "s/\<digraph_reader\.h\>/lgf_reader.h/g"\
kpeter@691
    74
        -e "s/\<digraph_writer\.h\>/lgf_writer.h/g"\
kpeter@691
    75
        -e "s/\<topology\.h\>/connectivity.h/g"\
kpeter@343
    76
        -e "s/DigraphToEps/GraphToEps/g"\
kpeter@343
    77
        -e "s/digraphToEps/graphToEps/g"\
kpeter@323
    78
        -e "s/\<DefPredMap\>/SetPredMap/g"\
kpeter@323
    79
        -e "s/\<DefDistMap\>/SetDistMap/g"\
kpeter@323
    80
        -e "s/\<DefReachedMap\>/SetReachedMap/g"\
kpeter@323
    81
        -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\
kpeter@323
    82
        -e "s/\<DefHeap\>/SetHeap/g"\
kpeter@323
    83
        -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\
kpeter@323
    84
        -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\
kpeter@323
    85
        -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\
kpeter@323
    86
        -e "s/\<copyGraph\>/graphCopy/g"\
kpeter@323
    87
        -e "s/\<copyDigraph\>/digraphCopy/g"\
kpeter@365
    88
        -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\
kpeter@323
    89
        -e "s/\<IntegerMap\>/RangeMap/g"\
kpeter@323
    90
        -e "s/\<integerMap\>/rangeMap/g"\
kpeter@323
    91
        -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\
kpeter@323
    92
        -e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\
kpeter@323
    93
        -e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\
kpeter@323
    94
        -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\
kpeter@323
    95
        -e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\
kpeter@323
    96
        -e "s/\<storeBoolMap\>/loggerBoolMap/g"\
kpeter@574
    97
        -e "s/\<InvertableMap\>/CrossRefMap/g"\
kpeter@574
    98
        -e "s/\<invertableMap\>/crossRefMap/g"\
kpeter@574
    99
        -e "s/\<DescriptorMap\>/RangeIdMap/g"\
kpeter@574
   100
        -e "s/\<descriptorMap\>/rangeIdMap/g"\
kpeter@323
   101
        -e "s/\<BoundingBox\>/Box/g"\
kpeter@359
   102
        -e "s/\<readNauty\>/readNautyGraph/g"\
kpeter@466
   103
        -e "s/\<RevDigraphAdaptor\>/ReverseDigraph/g"\
kpeter@466
   104
        -e "s/\<revDigraphAdaptor\>/reverseDigraph/g"\
kpeter@466
   105
        -e "s/\<SubDigraphAdaptor\>/SubDigraph/g"\
kpeter@466
   106
        -e "s/\<subDigraphAdaptor\>/subDigraph/g"\
kpeter@466
   107
        -e "s/\<SubGraphAdaptor\>/SubGraph/g"\
kpeter@466
   108
        -e "s/\<subGraphAdaptor\>/subGraph/g"\
kpeter@466
   109
        -e "s/\<NodeSubDigraphAdaptor\>/FilterNodes/g"\
kpeter@466
   110
        -e "s/\<nodeSubDigraphAdaptor\>/filterNodes/g"\
kpeter@466
   111
        -e "s/\<ArcSubDigraphAdaptor\>/FilterArcs/g"\
kpeter@466
   112
        -e "s/\<arcSubDigraphAdaptor\>/filterArcs/g"\
kpeter@466
   113
        -e "s/\<UndirDigraphAdaptor\>/Undirector/g"\
kpeter@466
   114
        -e "s/\<undirDigraphAdaptor\>/undirector/g"\
kpeter@466
   115
        -e "s/\<ResDigraphAdaptor\>/ResidualDigraph/g"\
kpeter@466
   116
        -e "s/\<resDigraphAdaptor\>/residualDigraph/g"\
kpeter@466
   117
        -e "s/\<SplitDigraphAdaptor\>/SplitNodes/g"\
kpeter@466
   118
        -e "s/\<splitDigraphAdaptor\>/splitNodes/g"\
kpeter@466
   119
        -e "s/\<SubGraphAdaptor\>/SubGraph/g"\
kpeter@466
   120
        -e "s/\<subGraphAdaptor\>/subGraph/g"\
kpeter@466
   121
        -e "s/\<NodeSubGraphAdaptor\>/FilterNodes/g"\
kpeter@466
   122
        -e "s/\<nodeSubGraphAdaptor\>/filterNodes/g"\
kpeter@466
   123
        -e "s/\<ArcSubGraphAdaptor\>/FilterEdges/g"\
kpeter@466
   124
        -e "s/\<arcSubGraphAdaptor\>/filterEdges/g"\
kpeter@466
   125
        -e "s/\<DirGraphAdaptor\>/Orienter/g"\
kpeter@466
   126
        -e "s/\<dirGraphAdaptor\>/orienter/g"\
kpeter@555
   127
        -e "s/\<LpCplex\>/CplexLp/g"\
kpeter@555
   128
        -e "s/\<MipCplex\>/CplexMip/g"\
kpeter@555
   129
        -e "s/\<LpGlpk\>/GlpkLp/g"\
kpeter@555
   130
        -e "s/\<MipGlpk\>/GlpkMip/g"\
kpeter@555
   131
        -e "s/\<LpSoplex\>/SoplexLp/g"\
kpeter@323
   132
    <$i > $TMP
kpeter@323
   133
    mv $TMP $i
kpeter@323
   134
done