,
+ entrycont = {}
+ entry = []
+ entrytype = pubtype_rex.sub('\g<1>',line)
+ entrytype = string.lower(entrytype)
+ entryid = pubtype_rex.sub('\g<2>', line)
+
+ # end entry if just a }
+ elif endtype_rex.match(line):
+ # generate doxygen code for the entry
+
+ # enty type related formattings
+ if entrytype in ('book', 'inbook'):
+ entrycont['title'] = '' + entrycont['title'] + ''
+ if not entrycont.has_key('author'):
+ entrycont['author'] = entrycont['editor']
+ entrycont['author']['text'] += ', editors'
+ elif entrytype == 'article':
+ entrycont['journal'] = '' + entrycont['journal'] + ''
+ elif entrytype in ('inproceedings', 'incollection', 'conference'):
+ entrycont['booktitle'] = '' + entrycont['booktitle'] + ''
+ elif entrytype == 'techreport':
+ if not entrycont.has_key('type'):
+ entrycont['type'] = 'Technical report'
+ elif entrytype == 'mastersthesis':
+ entrycont['type'] = 'Master\'s thesis'
+ elif entrytype == 'phdthesis':
+ entrycont['type'] = 'PhD thesis'
+
+ for eline in entrycont:
+ if eline != '':
+ eline = latexreplacements(eline)
+
+ if entrycont.has_key('pages') and (entrycont['pages'] != ''):
+ entrycont['pages'] = string.replace(entrycont['pages'], '--', '-')
+
+ if entrycont.has_key('author') and (entrycont['author'] != ''):
+ entry.append(entrycont['author']['text'] + '.')
+ if entrycont.has_key('title') and (entrycont['title'] != ''):
+ entry.append(entrycont['title'] + '.')
+ if entrycont.has_key('journal') and (entrycont['journal'] != ''):
+ entry.append(entrycont['journal'] + ',')
+ if entrycont.has_key('booktitle') and (entrycont['booktitle'] != ''):
+ entry.append('In ' + entrycont['booktitle'] + ',')
+ if entrycont.has_key('type') and (entrycont['type'] != ''):
+ eline = entrycont['type']
+ if entrycont.has_key('number') and (entrycont['number'] != ''):
+ eline += ' ' + entrycont['number']
+ eline += ','
+ entry.append(eline)
+ if entrycont.has_key('institution') and (entrycont['institution'] != ''):
+ entry.append(entrycont['institution'] + ',')
+ if entrycont.has_key('publisher') and (entrycont['publisher'] != ''):
+ entry.append(entrycont['publisher'] + ',')
+ if entrycont.has_key('school') and (entrycont['school'] != ''):
+ entry.append(entrycont['school'] + ',')
+ if entrycont.has_key('address') and (entrycont['address'] != ''):
+ entry.append(entrycont['address'] + ',')
+ if entrycont.has_key('edition') and (entrycont['edition'] != ''):
+ entry.append(entrycont['edition'] + ' edition,')
+ if entrycont.has_key('howpublished') and (entrycont['howpublished'] != ''):
+ entry.append(entrycont['howpublished'] + ',')
+ if entrycont.has_key('volume') and (entrycont['volume'] != ''):
+ eline = entrycont['volume'];
+ if entrycont.has_key('number') and (entrycont['number'] != ''):
+ eline += '(' + entrycont['number'] + ')'
+ if entrycont.has_key('pages') and (entrycont['pages'] != ''):
+ eline += ':' + entrycont['pages']
+ eline += ','
+ entry.append(eline)
+ else:
+ if entrycont.has_key('pages') and (entrycont['pages'] != ''):
+ entry.append('pages ' + entrycont['pages'] + ',')
+ if entrycont.has_key('year') and (entrycont['year'] != ''):
+ if entrycont.has_key('month') and (entrycont['month'] != ''):
+ entry.append(entrycont['month'] + ' ' + entrycont['year'] + '.')
+ else:
+ entry.append(entrycont['year'] + '.')
+ if entrycont.has_key('note') and (entrycont['note'] != ''):
+ entry.append(entrycont['note'] + '.')
+ if entrycont.has_key('url') and (entrycont['url'] != ''):
+ entry.append(entrycont['url'] + '.')
+
+ # generate keys for sorting and for the output
+ sortkey = ''
+ bibkey = ''
+ if entrycont.has_key('author'):
+ for author in entrycont['author']['list']:
+ sortkey += copychars(author, author.rfind(' ')+1, len(author))
+ bibkey = entrycont['author']['abbrev']
+ else:
+ bibkey = 'x'
+ if entrycont.has_key('year'):
+ sortkey += entrycont['year']
+ bibkey += entrycont['year'][-2:]
+ if entrycont.has_key('title'):
+ sortkey += entrycont['title']
+ if entrycont.has_key('key'):
+ sortkey = entrycont['key'] + sortkey
+ bibkey = entrycont['key']
+ entry.insert(0, sortkey)
+ entry.insert(1, bibkey)
+ entry.insert(2, entryid)
+
+ # add the entry to the file contents
+ filecont.append(entry)
+
+ else:
+ # field, publication info
+ field = ''
+ data = ''
+
+ # field = {data} entries
+ if bracedata_rex.match(line):
+ field = bracefield_rex.sub('\g<1>', line)
+ field = string.lower(field)
+ data = bracedata_rex.sub('\g<2>', line)
+
+ # field = "data" entries
+ elif quotedata_rex.match(line):
+ field = quotefield_rex.sub('\g<1>', line)
+ field = string.lower(field)
+ data = quotedata_rex.sub('\g<2>', line)
+
+ # field = data entries
+ elif data_rex.match(line):
+ field = field_rex.sub('\g<1>', line)
+ field = string.lower(field)
+ data = data_rex.sub('\g<2>', line)
+
+ if field == 'url':
+ data = '\\url{' + data.strip() + '}'
+
+ if field in ('author', 'editor'):
+ entrycont[field] = bibtexauthor(data)
+ line = ''
+ elif field == 'title':
+ line = bibtextitle(data, entrytype)
+ elif field != '':
+ line = removebraces(transformurls(data.strip()))
+
+ if line != '':
+ line = latexreplacements(line)
+ entrycont[field] = line
+
+
+ # sort entries
+ filecont.sort(entry_cmp)
+
+ # count the bibtex keys
+ keytable = {}
+ counttable = {}
+ for entry in filecont:
+ bibkey = entry[1]
+ if not keytable.has_key(bibkey):
+ keytable[bibkey] = 1
+ else:
+ keytable[bibkey] += 1
+
+ for bibkey in keytable.keys():
+ counttable[bibkey] = 0
+
+ # generate output
+ for entry in filecont:
+ # generate output key form the bibtex key
+ bibkey = entry[1]
+ entryid = entry[2]
+ if keytable[bibkey] == 1:
+ outkey = bibkey
+ else:
+ outkey = bibkey + chr(97 + counttable[bibkey])
+ counttable[bibkey] += 1
+
+ # append the entry code to the output
+ file.append('\\section ' + entryid + ' [' + outkey + ']')
+ file.append('')
+ for line in entry[3:]:
+ file.append(line)
+ file.append('
')
+ file.append('')
+
+ return file
+
+
+#
+# return 1 iff abbr is in line but not inside braces or quotes
+# assumes that abbr appears only once on the line (out of braces and quotes)
+#
+def verify_out_of_braces(line, abbr):
+
+ phrase_split = delimiter_rex.split(line)
+
+ abbr_rex = re.compile( '\\b' + abbr + '\\b', re.I)
+
+ open_brace = 0
+ open_quote = 0
+
+ for phrase in phrase_split:
+ if phrase == "{":
+ open_brace = open_brace + 1
+ elif phrase == "}":
+ open_brace = open_brace - 1
+ elif phrase == '"':
+ if open_quote == 1:
+ open_quote = 0
+ else:
+ open_quote = 1
+ elif abbr_rex.search(phrase):
+ if open_brace == 0 and open_quote == 0:
+ return 1
+
+ return 0
+
+
+#
+# a line in the form phrase1 # phrase2 # ... # phrasen
+# is returned as phrase1 phrase2 ... phrasen
+# with the correct punctuation
+# Bug: Doesn't always work with multiple abbreviations plugged in
+#
+def concat_line(line):
+ # only look at part after equals
+ field = field_rex.sub('\g<1>',line)
+ rest = field_rex.sub('\g<2>',line)
+
+ concat_line = field + ' ='
+
+ pound_split = concatsplit_rex.split(rest)
+
+ phrase_count = 0
+ length = len(pound_split)
+
+ for phrase in pound_split:
+ phrase = phrase.strip()
+ if phrase_count != 0:
+ if phrase.startswith('"') or phrase.startswith('{'):
+ phrase = phrase[1:]
+ elif phrase.startswith('"'):
+ phrase = phrase.replace('"','{',1)
+
+ if phrase_count != length-1:
+ if phrase.endswith('"') or phrase.endswith('}'):
+ phrase = phrase[:-1]
+ else:
+ if phrase.endswith('"'):
+ phrase = phrase[:-1]
+ phrase = phrase + "}"
+ elif phrase.endswith('",'):
+ phrase = phrase[:-2]
+ phrase = phrase + "},"
+
+ # if phrase did have \#, add the \# back
+ if phrase.endswith('\\'):
+ phrase = phrase + "#"
+ concat_line = concat_line + ' ' + phrase
+
+ phrase_count = phrase_count + 1
+
+ return concat_line
+
+
+#
+# substitute abbreviations into filecont
+# @param filecont_source - string of data from file
+#
+def bibtex_replace_abbreviations(filecont_source):
+ filecont = filecont_source.splitlines()
+
+ # These are defined in bibtex, so we'll define them too
+ abbr_list = ['jan','feb','mar','apr','may','jun',
+ 'jul','aug','sep','oct','nov','dec']
+ value_list = ['January','February','March','April',
+ 'May','June','July','August','September',
+ 'October','November','December']
+
+ abbr_rex = []
+ total_abbr_count = 0
+
+ front = '\\b'
+ back = '(,?)\\b'
+
+ for x in abbr_list:
+ abbr_rex.append( re.compile( front + abbr_list[total_abbr_count] + back, re.I ) )
+ total_abbr_count = total_abbr_count + 1
+
+
+ abbrdef_rex = re.compile('\s*@string\s*{\s*('+ valid_name_chars +'*)\s*=(.*)',
+ re.I)
+
+ comment_rex = re.compile('@comment\s*{',re.I)
+ preamble_rex = re.compile('@preamble\s*{',re.I)
+
+ waiting_for_end_string = 0
+ i = 0
+ filecont2 = ''
+
+ for line in filecont:
+ if line == ' ' or line == '':
+ continue
+
+ if waiting_for_end_string:
+ if re.search('}',line):
+ waiting_for_end_string = 0
+ continue
+
+ if abbrdef_rex.search(line):
+ abbr = abbrdef_rex.sub('\g<1>', line)
+
+ if abbr_list.count(abbr) == 0:
+ val = abbrdef_rex.sub('\g<2>', line)
+ abbr_list.append(abbr)
+ value_list.append(string.strip(val))
+ abbr_rex.append( re.compile( front + abbr_list[total_abbr_count] + back, re.I ) )
+ total_abbr_count = total_abbr_count + 1
+ waiting_for_end_string = 1
+ continue
+
+ if comment_rex.search(line):
+ waiting_for_end_string = 1
+ continue
+
+ if preamble_rex.search(line):
+ waiting_for_end_string = 1
+ continue
+
+
+ # replace subsequent abbreviations with the value
+ abbr_count = 0
+
+ for x in abbr_list:
+
+ if abbr_rex[abbr_count].search(line):
+ if verify_out_of_braces(line,abbr_list[abbr_count]) == 1:
+ line = abbr_rex[abbr_count].sub( value_list[abbr_count] + '\g<1>', line)
+ # Check for # concatenations
+ if concatsplit_rex.search(line):
+ line = concat_line(line)
+ abbr_count = abbr_count + 1
+
+
+ filecont2 = filecont2 + line + '\n'
+ i = i+1
+
+
+ # Do one final pass over file
+
+ # make sure that didn't end up with {" or }" after the substitution
+ filecont2 = filecont2.replace('{"','{{')
+ filecont2 = filecont2.replace('"}','}}')
+
+ afterquotevalue_rex = re.compile('"\s*,\s*')
+ afterbrace_rex = re.compile('"\s*}')
+ afterbracevalue_rex = re.compile('(=\s*{[^=]*)},\s*')
+
+ # add new lines to data that changed because of abbreviation substitutions
+ filecont2 = afterquotevalue_rex.sub('",\n', filecont2)
+ filecont2 = afterbrace_rex.sub('"\n}', filecont2)
+ filecont2 = afterbracevalue_rex.sub('\g<1>},\n', filecont2)
+
+ return filecont2
+
+#
+# convert @type( ... ) to @type{ ... }
+#
+def no_outer_parens(filecont):
+
+ # do checking for open parens
+ # will convert to braces
+ paren_split = re.split('([(){}])',filecont)
+
+ open_paren_count = 0
+ open_type = 0
+ look_next = 0
+
+ # rebuild filecont
+ filecont = ''
+
+ at_rex = re.compile('@\w*')
+
+ for phrase in paren_split:
+ if look_next == 1:
+ if phrase == '(':
+ phrase = '{'
+ open_paren_count = open_paren_count + 1
+ else:
+ open_type = 0
+ look_next = 0
+
+ if phrase == '(':
+ open_paren_count = open_paren_count + 1
+
+ elif phrase == ')':
+ open_paren_count = open_paren_count - 1
+ if open_type == 1 and open_paren_count == 0:
+ phrase = '}'
+ open_type = 0
+
+ elif at_rex.search( phrase ):
+ open_type = 1
+ look_next = 1
+
+ filecont = filecont + phrase
+
+ return filecont
+
+
+#
+# make all whitespace into just one space
+# format the bibtex file into a usable form.
+#
+def bibtexwasher(filecont_source):
+
+ space_rex = re.compile('\s+')
+ comment_rex = re.compile('\s*%')
+
+ filecont = []
+
+ # remove trailing and excessive whitespace
+ # ignore comments
+ for line in filecont_source:
+ line = string.strip(line)
+ line = space_rex.sub(' ', line)
+ # ignore comments
+ if not comment_rex.match(line) and line != '':
+ filecont.append(' '+ line)
+
+ filecont = string.join(filecont, '')
+
+ # the file is in one long string
+
+ filecont = no_outer_parens(filecont)
+
+ #
+ # split lines according to preferred syntax scheme
+ #
+ filecont = re.sub('(=\s*{[^=]*)},', '\g<1>},\n', filecont)
+
+ # add new lines after commas that are after values
+ filecont = re.sub('"\s*,', '",\n', filecont)
+ filecont = re.sub('=\s*([\w\d]+)\s*,', '= \g<1>,\n', filecont)
+ filecont = re.sub('(@\w*)\s*({(\s*)[^,\s]*)\s*,',
+ '\n\n\g<1>\g<2>,\n', filecont)
+
+ # add new lines after }
+ filecont = re.sub('"\s*}','"\n}\n', filecont)
+ filecont = re.sub('}\s*,','},\n', filecont)
+
+
+ filecont = re.sub('@(\w*)', '\n@\g<1>', filecont)
+
+ # character encoding, reserved latex characters
+ filecont = re.sub('{\\\&}', '&', filecont)
+ filecont = re.sub('\\\&', '&', filecont)
+
+ # do checking for open braces to get format correct
+ open_brace_count = 0
+ brace_split = re.split('([{}])',filecont)
+
+ # rebuild filecont
+ filecont = ''
+
+ for phrase in brace_split:
+ if phrase == '{':
+ open_brace_count = open_brace_count + 1
+ elif phrase == '}':
+ open_brace_count = open_brace_count - 1
+ if open_brace_count == 0:
+ filecont = filecont + '\n'
+
+ filecont = filecont + phrase
+
+ filecont2 = bibtex_replace_abbreviations(filecont)
+
+ # gather
+ filecont = filecont2.splitlines()
+ i=0
+ j=0 # count the number of blank lines
+ for line in filecont:
+ # ignore blank lines
+ if line == '' or line == ' ':
+ j = j+1
+ continue
+ filecont[i] = line + '\n'
+ i = i+1
+
+ # get rid of the extra stuff at the end of the array
+ # (The extra stuff are duplicates that are in the array because
+ # blank lines were removed.)
+ length = len( filecont)
+ filecont[length-j:length] = []
+
+ return filecont
+
+
+def filehandler(filepath):
+ try:
+ fd = open(filepath, 'r')
+ filecont_source = fd.readlines()
+ fd.close()
+ except:
+ print 'Could not open file:', filepath
+ washeddata = bibtexwasher(filecont_source)
+ outdata = bibtexdecoder(washeddata)
+ print '/**'
+ print '\page references References'
+ print
+ for line in outdata:
+ print line
+ print '*/'
+
+
+# main program
+
+def main():
+ import sys
+ if sys.argv[1:]:
+ filepath = sys.argv[1]
+ else:
+ print "No input file"
+ sys.exit()
+ filehandler(filepath)
+
+if __name__ == "__main__": main()
+
+
+# end python script
diff --git a/scripts/bootstrap.sh b/scripts/bootstrap.sh
new file mode 100755
--- /dev/null
+++ b/scripts/bootstrap.sh
@@ -0,0 +1,134 @@
+#!/bin/bash
+#
+# This file is a part of LEMON, a generic C++ optimization library.
+#
+# Copyright (C) 2003-2009
+# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+# (Egervary Research Group on Combinatorial Optimization, EGRES).
+#
+# Permission to use, modify and distribute this software is granted
+# provided that this copyright notice appears in all copies. For
+# precise terms see the accompanying LICENSE file.
+#
+# This software is provided "AS IS" with no warranty of any kind,
+# express or implied, and with no claim as to its suitability for any
+# purpose.
+
+
+if [ ! -f ~/.lemon-bootstrap ]; then
+ echo 'Create ~/.lemon-bootstrap'.
+ cat >~/.lemon-bootstrap <>~/.lemon-bootstrap
+ echo $3 >>~/.lemon-bootstrap
+ echo $1=$2 >>~/.lemon-bootstrap
+ fi
+}
+
+augment_config LEMON_INSTALL_PREFIX /usr/local \
+ "# LEMON installation prefix"
+
+augment_config COIN_OR_PREFIX /usr/local/coin-or \
+ "# COIN-OR installation root prefix (used for CLP/CBC)"
+
+augment_config SOPLEX_PREFIX /usr/local/soplex \
+ "# Soplex build prefix"
+
+
+function ask() {
+echo -n "$1 [$2]? "
+read _an
+if [ "x$_an" == "x" ]; then
+ ret="$2"
+else
+ ret=$_an
+fi
+}
+
+function yesorno() {
+ ret='rossz'
+ while [ "$ret" != "y" -a "$ret" != "n" -a "$ret" != "yes" -a "$ret" != "no" ]; do
+ ask "$1" "$2"
+ done
+ if [ "$ret" != "y" -a "$ret" != "yes" ]; then
+ return 1
+ else
+ return 0
+ fi
+}
+
+if yesorno "External build" "n"
+then
+ CONFIGURE_PATH=".."
+else
+ CONFIGURE_PATH="."
+ if yesorno "Autoreconf" "y"
+ then
+ AUTORE=yes
+ else
+ AUTORE=no
+ fi
+fi
+
+if yesorno "Optimize" "n"
+then
+ opt_flags=' -O2'
+else
+ opt_flags=''
+fi
+
+if yesorno "Stop on warning" "y"
+then
+ werror_flags=' -Werror'
+else
+ werror_flags=''
+fi
+
+cxx_flags="CXXFLAGS=-ggdb$opt_flags$werror_flags"
+
+if [ -f ${COIN_OR_PREFIX}/include/coin/config_coinutils.h ]; then
+ if yesorno "Use COIN-OR (CBC/CLP)" "n"
+ then
+ coin_flag="--with-coin=$COIN_OR_PREFIX"
+ else
+ coin_flag=""
+ fi
+else
+ coin_flag=""
+fi
+
+if [ -f ${SOPLEX_PREFIX}/src/soplex.h ]; then
+ if yesorno "Use Soplex" "n"
+ then
+ soplex_flag="--with-soplex=$SOPLEX_PREFIX"
+ else
+ soplex_flag=""
+ fi
+else
+ soplex_flag=""
+fi
+
+if [ "x$AUTORE" == "xyes" ]; then
+ autoreconf -vif;
+fi
+${CONFIGURE_PATH}/configure --prefix=$LEMON_INSTALL_PREFIX \
+"$cxx_flags" \
+$coin_flag \
+$soplex_flag \
+$*
diff --git a/scripts/chg-len.py b/scripts/chg-len.py
--- a/scripts/chg-len.py
+++ b/scripts/chg-len.py
@@ -1,4 +1,18 @@
#! /usr/bin/env python
+#
+# This file is a part of LEMON, a generic C++ optimization library.
+#
+# Copyright (C) 2003-2009
+# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+# (Egervary Research Group on Combinatorial Optimization, EGRES).
+#
+# Permission to use, modify and distribute this software is granted
+# provided that this copyright notice appears in all copies. For
+# precise terms see the accompanying LICENSE file.
+#
+# This software is provided "AS IS" with no warranty of any kind,
+# express or implied, and with no claim as to its suitability for any
+# purpose.
import sys
diff --git a/scripts/mk-release.sh b/scripts/mk-release.sh
--- a/scripts/mk-release.sh
+++ b/scripts/mk-release.sh
@@ -1,4 +1,18 @@
#!/bin/bash
+#
+# This file is a part of LEMON, a generic C++ optimization library.
+#
+# Copyright (C) 2003-2009
+# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+# (Egervary Research Group on Combinatorial Optimization, EGRES).
+#
+# Permission to use, modify and distribute this software is granted
+# provided that this copyright notice appears in all copies. For
+# precise terms see the accompanying LICENSE file.
+#
+# This software is provided "AS IS" with no warranty of any kind,
+# express or implied, and with no claim as to its suitability for any
+# purpose.
set -e
diff --git a/scripts/unify-sources.sh b/scripts/unify-sources.sh
--- a/scripts/unify-sources.sh
+++ b/scripts/unify-sources.sh
@@ -1,4 +1,18 @@
#!/bin/bash
+#
+# This file is a part of LEMON, a generic C++ optimization library.
+#
+# Copyright (C) 2003-2009
+# Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+# (Egervary Research Group on Combinatorial Optimization, EGRES).
+#
+# Permission to use, modify and distribute this software is granted
+# provided that this copyright notice appears in all copies. For
+# precise terms see the accompanying LICENSE file.
+#
+# This software is provided "AS IS" with no warranty of any kind,
+# express or implied, and with no claim as to its suitability for any
+# purpose.
YEAR=`date +%Y`
HGROOT=`hg root`
diff --git a/test/CMakeLists.txt b/test/CMakeLists.txt
--- a/test/CMakeLists.txt
+++ b/test/CMakeLists.txt
@@ -32,6 +32,7 @@
matching_test
min_cost_arborescence_test
min_cost_flow_test
+ min_mean_cycle_test
path_test
preflow_test
radix_sort_test
diff --git a/test/Makefile.am b/test/Makefile.am
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -30,6 +30,7 @@
test/matching_test \
test/min_cost_arborescence_test \
test/min_cost_flow_test \
+ test/min_mean_cycle_test \
test/path_test \
test/preflow_test \
test/radix_sort_test \
@@ -78,6 +79,7 @@
test_matching_test_SOURCES = test/matching_test.cc
test_min_cost_arborescence_test_SOURCES = test/min_cost_arborescence_test.cc
test_min_cost_flow_test_SOURCES = test/min_cost_flow_test.cc
+test_min_mean_cycle_test_SOURCES = test/min_mean_cycle_test.cc
test_path_test_SOURCES = test/path_test.cc
test_preflow_test_SOURCES = test/preflow_test.cc
test_radix_sort_test_SOURCES = test/radix_sort_test.cc
diff --git a/test/digraph_test.cc b/test/digraph_test.cc
--- a/test/digraph_test.cc
+++ b/test/digraph_test.cc
@@ -19,6 +19,7 @@
#include
#include
#include
+#include
#include
#include "test_tools.h"
@@ -35,6 +36,9 @@
checkGraphNodeList(G, 0);
checkGraphArcList(G, 0);
+ G.reserveNode(3);
+ G.reserveArc(4);
+
Node
n1 = G.addNode(),
n2 = G.addNode(),
@@ -283,6 +287,14 @@
G.addArc(G.addNode(), G.addNode());
snapshot.restore();
+ snapshot.save(G);
+
+ checkGraphNodeList(G, 4);
+ checkGraphArcList(G, 4);
+
+ G.addArc(G.addNode(), G.addNode());
+
+ snapshot.restore();
checkGraphNodeList(G, 4);
checkGraphArcList(G, 4);
@@ -317,6 +329,10 @@
checkConcept, SmartDigraph>();
checkConcept, SmartDigraph>();
}
+ { // Checking StaticDigraph
+ checkConcept();
+ checkConcept, StaticDigraph>();
+ }
{ // Checking FullDigraph
checkConcept();
}
@@ -372,10 +388,122 @@
check(!g.valid(g.arcFromId(-1)), "Wrong validity check");
}
+void checkStaticDigraph() {
+ SmartDigraph g;
+ SmartDigraph::NodeMap nref(g);
+ SmartDigraph::ArcMap aref(g);
+
+ StaticDigraph G;
+
+ checkGraphNodeList(G, 0);
+ checkGraphArcList(G, 0);
+
+ G.build(g, nref, aref);
+
+ checkGraphNodeList(G, 0);
+ checkGraphArcList(G, 0);
+
+ SmartDigraph::Node
+ n1 = g.addNode(),
+ n2 = g.addNode(),
+ n3 = g.addNode();
+
+ G.build(g, nref, aref);
+
+ checkGraphNodeList(G, 3);
+ checkGraphArcList(G, 0);
+
+ SmartDigraph::Arc a1 = g.addArc(n1, n2);
+
+ G.build(g, nref, aref);
+
+ check(G.source(aref[a1]) == nref[n1] && G.target(aref[a1]) == nref[n2],
+ "Wrong arc or wrong references");
+ checkGraphNodeList(G, 3);
+ checkGraphArcList(G, 1);
+
+ checkGraphOutArcList(G, nref[n1], 1);
+ checkGraphOutArcList(G, nref[n2], 0);
+ checkGraphOutArcList(G, nref[n3], 0);
+
+ checkGraphInArcList(G, nref[n1], 0);
+ checkGraphInArcList(G, nref[n2], 1);
+ checkGraphInArcList(G, nref[n3], 0);
+
+ checkGraphConArcList(G, 1);
+
+ SmartDigraph::Arc
+ a2 = g.addArc(n2, n1),
+ a3 = g.addArc(n2, n3),
+ a4 = g.addArc(n2, n3);
+
+ digraphCopy(g, G).nodeRef(nref).run();
+
+ checkGraphNodeList(G, 3);
+ checkGraphArcList(G, 4);
+
+ checkGraphOutArcList(G, nref[n1], 1);
+ checkGraphOutArcList(G, nref[n2], 3);
+ checkGraphOutArcList(G, nref[n3], 0);
+
+ checkGraphInArcList(G, nref[n1], 1);
+ checkGraphInArcList(G, nref[n2], 1);
+ checkGraphInArcList(G, nref[n3], 2);
+
+ checkGraphConArcList(G, 4);
+
+ std::vector > arcs;
+ arcs.push_back(std::make_pair(0,1));
+ arcs.push_back(std::make_pair(0,2));
+ arcs.push_back(std::make_pair(1,3));
+ arcs.push_back(std::make_pair(1,2));
+ arcs.push_back(std::make_pair(3,0));
+ arcs.push_back(std::make_pair(3,3));
+ arcs.push_back(std::make_pair(4,2));
+ arcs.push_back(std::make_pair(4,3));
+ arcs.push_back(std::make_pair(4,1));
+
+ G.build(6, arcs.begin(), arcs.end());
+
+ checkGraphNodeList(G, 6);
+ checkGraphArcList(G, 9);
+
+ checkGraphOutArcList(G, G.node(0), 2);
+ checkGraphOutArcList(G, G.node(1), 2);
+ checkGraphOutArcList(G, G.node(2), 0);
+ checkGraphOutArcList(G, G.node(3), 2);
+ checkGraphOutArcList(G, G.node(4), 3);
+ checkGraphOutArcList(G, G.node(5), 0);
+
+ checkGraphInArcList(G, G.node(0), 1);
+ checkGraphInArcList(G, G.node(1), 2);
+ checkGraphInArcList(G, G.node(2), 3);
+ checkGraphInArcList(G, G.node(3), 3);
+ checkGraphInArcList(G, G.node(4), 0);
+ checkGraphInArcList(G, G.node(5), 0);
+
+ checkGraphConArcList(G, 9);
+
+ checkNodeIds(G);
+ checkArcIds(G);
+ checkGraphNodeMap(G);
+ checkGraphArcMap(G);
+
+ int n = G.nodeNum();
+ int m = G.arcNum();
+ check(G.index(G.node(n-1)) == n-1, "Wrong index.");
+ check(G.index(G.arc(m-1)) == m-1, "Wrong index.");
+}
+
void checkFullDigraph(int num) {
typedef FullDigraph Digraph;
DIGRAPH_TYPEDEFS(Digraph);
+
Digraph G(num);
+ check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
+
+ G.resize(num);
+ check(G.nodeNum() == num && G.arcNum() == num * num, "Wrong size");
checkGraphNodeList(G, num);
checkGraphArcList(G, num * num);
@@ -419,6 +547,9 @@
checkDigraphSnapshot();
checkDigraphValidity();
}
+ { // Checking StaticDigraph
+ checkStaticDigraph();
+ }
{ // Checking FullDigraph
checkFullDigraph(8);
}
diff --git a/test/graph_test.cc b/test/graph_test.cc
--- a/test/graph_test.cc
+++ b/test/graph_test.cc
@@ -38,6 +38,9 @@
checkGraphEdgeList(G, 0);
checkGraphArcList(G, 0);
+ G.reserveNode(3);
+ G.reserveEdge(3);
+
Node
n1 = G.addNode(),
n2 = G.addNode(),
@@ -256,6 +259,15 @@
G.addEdge(G.addNode(), G.addNode());
snapshot.restore();
+ snapshot.save(G);
+
+ checkGraphNodeList(G, 4);
+ checkGraphEdgeList(G, 3);
+ checkGraphArcList(G, 6);
+
+ G.addEdge(G.addNode(), G.addNode());
+
+ snapshot.restore();
checkGraphNodeList(G, 4);
checkGraphEdgeList(G, 3);
@@ -267,6 +279,13 @@
GRAPH_TYPEDEFS(Graph);
Graph G(num);
+ check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
+ "Wrong size");
+
+ G.resize(num);
+ check(G.nodeNum() == num && G.edgeNum() == num * (num - 1) / 2,
+ "Wrong size");
+
checkGraphNodeList(G, num);
checkGraphEdgeList(G, num * (num - 1) / 2);
@@ -411,6 +430,10 @@
check(G.width() == width, "Wrong column number");
check(G.height() == height, "Wrong row number");
+ G.resize(width, height);
+ check(G.width() == width, "Wrong column number");
+ check(G.height() == height, "Wrong row number");
+
for (int i = 0; i < width; ++i) {
for (int j = 0; j < height; ++j) {
check(G.col(G(i, j)) == i, "Wrong column");
@@ -486,6 +509,11 @@
GRAPH_TYPEDEFS(HypercubeGraph);
HypercubeGraph G(dim);
+ check(G.dimension() == dim, "Wrong dimension");
+
+ G.resize(dim);
+ check(G.dimension() == dim, "Wrong dimension");
+
checkGraphNodeList(G, 1 << dim);
checkGraphEdgeList(G, dim * (1 << (dim-1)));
checkGraphArcList(G, dim * (1 << dim));
diff --git a/test/min_mean_cycle_test.cc b/test/min_mean_cycle_test.cc
new file mode 100644
--- /dev/null
+++ b/test/min_mean_cycle_test.cc
@@ -0,0 +1,216 @@
+/* -*- mode: C++; indent-tabs-mode: nil; -*-
+ *
+ * This file is a part of LEMON, a generic C++ optimization library.
+ *
+ * Copyright (C) 2003-2009
+ * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
+ * (Egervary Research Group on Combinatorial Optimization, EGRES).
+ *
+ * Permission to use, modify and distribute this software is granted
+ * provided that this copyright notice appears in all copies. For
+ * precise terms see the accompanying LICENSE file.
+ *
+ * This software is provided "AS IS" with no warranty of any kind,
+ * express or implied, and with no claim as to its suitability for any
+ * purpose.
+ *
+ */
+
+#include
+#include
+
+#include
+#include
+#include
+#include
+#include
+
+#include
+#include
+#include
+
+#include "test_tools.h"
+
+using namespace lemon;
+
+char test_lgf[] =
+ "@nodes\n"
+ "label\n"
+ "1\n"
+ "2\n"
+ "3\n"
+ "4\n"
+ "5\n"
+ "6\n"
+ "7\n"
+ "@arcs\n"
+ " len1 len2 len3 len4 c1 c2 c3 c4\n"
+ "1 2 1 1 1 1 0 0 0 0\n"
+ "2 4 5 5 5 5 1 0 0 0\n"
+ "2 3 8 8 8 8 0 0 0 0\n"
+ "3 2 -2 0 0 0 1 0 0 0\n"
+ "3 4 4 4 4 4 0 0 0 0\n"
+ "3 7 -4 -4 -4 -4 0 0 0 0\n"
+ "4 1 2 2 2 2 0 0 0 0\n"
+ "4 3 3 3 3 3 1 0 0 0\n"
+ "4 4 3 3 0 0 0 0 1 0\n"
+ "5 2 4 4 4 4 0 0 0 0\n"
+ "5 6 3 3 3 3 0 1 0 0\n"
+ "6 5 2 2 2 2 0 1 0 0\n"
+ "6 4 -1 -1 -1 -1 0 0 0 0\n"
+ "6 7 1 1 1 1 0 0 0 0\n"
+ "7 7 4 4 4 -1 0 0 0 1\n";
+
+
+// Check the interface of an MMC algorithm
+template
+struct MmcClassConcept
+{
+ template
+ struct Constraints {
+ void constraints() {
+ const Constraints& me = *this;
+
+ typedef typename MMC
+ ::template SetPath >
+ ::template SetLargeValue
+ ::Create MmcAlg;
+ MmcAlg mmc(me.g, me.length);
+ const MmcAlg& const_mmc = mmc;
+
+ typename MmcAlg::Tolerance tol = const_mmc.tolerance();
+ mmc.tolerance(tol);
+
+ b = mmc.cycle(p).run();
+ b = mmc.findMinMean();
+ b = mmc.findCycle();
+
+ v = const_mmc.cycleLength();
+ i = const_mmc.cycleArcNum();
+ d = const_mmc.cycleMean();
+ p = const_mmc.cycle();
+ }
+
+ typedef concepts::ReadMap LM;
+
+ GR g;
+ LM length;
+ ListPath p;
+ Value v;
+ int i;
+ double d;
+ bool b;
+ };
+};
+
+// Perform a test with the given parameters
+template
+void checkMmcAlg(const SmartDigraph& gr,
+ const SmartDigraph::ArcMap& lm,
+ const SmartDigraph::ArcMap& cm,
+ int length, int size) {
+ MMC alg(gr, lm);
+ alg.findMinMean();
+ check(alg.cycleMean() == static_cast(length) / size,
+ "Wrong cycle mean");
+ alg.findCycle();
+ check(alg.cycleLength() == length && alg.cycleArcNum() == size,
+ "Wrong path");
+ SmartDigraph::ArcMap cycle(gr, 0);
+ for (typename MMC::Path::ArcIt a(alg.cycle()); a != INVALID; ++a) {
+ ++cycle[a];
+ }
+ for (SmartDigraph::ArcIt a(gr); a != INVALID; ++a) {
+ check(cm[a] == cycle[a], "Wrong path");
+ }
+}
+
+// Class for comparing types
+template
+struct IsSameType {
+ static const int result = 0;
+};
+
+template
+struct IsSameType {
+ static const int result = 1;
+};
+
+
+int main() {
+ #ifdef LEMON_HAVE_LONG_LONG
+ typedef long long long_int;
+ #else
+ typedef long long_int;
+ #endif
+
+ // Check the interface
+ {
+ typedef concepts::Digraph GR;
+
+ // Karp
+ checkConcept< MmcClassConcept,
+ Karp > >();
+ checkConcept< MmcClassConcept,
+ Karp > >();
+
+ // HartmannOrlin
+ checkConcept< MmcClassConcept,
+ HartmannOrlin > >();
+ checkConcept< MmcClassConcept,
+ HartmannOrlin > >();
+
+ // Howard
+ checkConcept< MmcClassConcept,
+ Howard > >();
+ checkConcept< MmcClassConcept,
+ Howard > >();
+
+ if (IsSameType >::LargeValue,
+ long_int>::result == 0) check(false, "Wrong LargeValue type");
+ if (IsSameType >::LargeValue,
+ double>::result == 0) check(false, "Wrong LargeValue type");
+ }
+
+ // Run various tests
+ {
+ typedef SmartDigraph GR;
+ DIGRAPH_TYPEDEFS(GR);
+
+ GR gr;
+ IntArcMap l1(gr), l2(gr), l3(gr), l4(gr);
+ IntArcMap c1(gr), c2(gr), c3(gr), c4(gr);
+
+ std::istringstream input(test_lgf);
+ digraphReader(gr, input).
+ arcMap("len1", l1).
+ arcMap("len2", l2).
+ arcMap("len3", l3).
+ arcMap("len4", l4).
+ arcMap("c1", c1).
+ arcMap("c2", c2).
+ arcMap("c3", c3).
+ arcMap("c4", c4).
+ run();
+
+ // Karp
+ checkMmcAlg >(gr, l1, c1, 6, 3);
+ checkMmcAlg >(gr, l2, c2, 5, 2);
+ checkMmcAlg >(gr, l3, c3, 0, 1);
+ checkMmcAlg >(gr, l4, c4, -1, 1);
+
+ // HartmannOrlin
+ checkMmcAlg >(gr, l1, c1, 6, 3);
+ checkMmcAlg >(gr, l2, c2, 5, 2);
+ checkMmcAlg >(gr, l3, c3, 0, 1);
+ checkMmcAlg >(gr, l4, c4, -1, 1);
+
+ // Howard
+ checkMmcAlg >(gr, l1, c1, 6, 3);
+ checkMmcAlg >(gr, l2, c2, 5, 2);
+ checkMmcAlg >(gr, l3, c3, 0, 1);
+ checkMmcAlg >(gr, l4, c4, -1, 1);
+ }
+
+ return 0;
+}
diff --git a/test/mip_test.cc b/test/mip_test.cc
--- a/test/mip_test.cc
+++ b/test/mip_test.cc
@@ -50,7 +50,8 @@
if (stat == MipSolver::OPTIMAL) {
std::ostringstream sbuf;
- buf << "Wrong optimal value: the right optimum is " << exp_opt;
+ sbuf << "Wrong optimal value ("<< mip.solValue()
+ <<" instead of " << exp_opt << ")";
check(std::abs(mip.solValue()-exp_opt) < 1e-3, sbuf.str());
//+ecvt(exp_opt,2)
}
diff --git a/test/test_tools.h b/test/test_tools.h
--- a/test/test_tools.h
+++ b/test/test_tools.h
@@ -37,10 +37,14 @@
///\code check(0==1,"This is obviously false.");\endcode will
///print something like this (and then exits).
///\verbatim file_name.cc:123: error: This is obviously false. \endverbatim
-#define check(rc, msg) \
- if(!(rc)) { \
- std::cerr << __FILE__ ":" << __LINE__ << ": error: " << msg << std::endl; \
- abort(); \
- } else { } \
+#define check(rc, msg) \
+ { \
+ if(!(rc)) { \
+ std::cerr << __FILE__ ":" << __LINE__ << ": error: " \
+ << msg << std::endl; \
+ abort(); \
+ } else { } \
+ } \
+
#endif