diff options
Diffstat (limited to 'lemon/tools')
| -rw-r--r-- | lemon/tools/.deps/.dirstamp | 0 | ||||
| -rw-r--r-- | lemon/tools/.deps/dimacs-solver.Po | 543 | ||||
| -rw-r--r-- | lemon/tools/.deps/dimacs-to-lgf.Po | 439 | ||||
| -rw-r--r-- | lemon/tools/.deps/lgf-gen.Po | 567 | ||||
| -rw-r--r-- | lemon/tools/.dirstamp | 0 | ||||
| -rw-r--r-- | lemon/tools/CMakeLists.txt | 31 | ||||
| -rw-r--r-- | lemon/tools/Makefile.am | 17 | ||||
| -rw-r--r-- | lemon/tools/dimacs-solver.cc | 280 | ||||
| -rw-r--r-- | lemon/tools/dimacs-to-lgf.cc | 148 | ||||
| -rwxr-xr-x | lemon/tools/lemon-0.x-to-1.x.sh | 134 | ||||
| -rw-r--r-- | lemon/tools/lgf-gen.cc | 834 |
11 files changed, 2993 insertions, 0 deletions
diff --git a/lemon/tools/.deps/.dirstamp b/lemon/tools/.deps/.dirstamp new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/lemon/tools/.deps/.dirstamp diff --git a/lemon/tools/.deps/dimacs-solver.Po b/lemon/tools/.deps/dimacs-solver.Po new file mode 100644 index 0000000..f8eb074 --- /dev/null +++ b/lemon/tools/.deps/dimacs-solver.Po @@ -0,0 +1,543 @@ +tools/dimacs-solver.o: tools/dimacs-solver.cc \ + /usr/include/c++/4.7/iostream \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++config.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/os_defines.h \ + /usr/include/features.h /usr/include/x86_64-linux-gnu/bits/predefs.h \ + /usr/include/x86_64-linux-gnu/sys/cdefs.h \ + /usr/include/x86_64-linux-gnu/bits/wordsize.h \ + /usr/include/x86_64-linux-gnu/gnu/stubs.h \ + /usr/include/x86_64-linux-gnu/gnu/stubs-64.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/cpu_defines.h \ + /usr/include/c++/4.7/ostream /usr/include/c++/4.7/ios \ + /usr/include/c++/4.7/iosfwd /usr/include/c++/4.7/bits/stringfwd.h \ + /usr/include/c++/4.7/bits/postypes.h /usr/include/c++/4.7/cwchar \ + /usr/include/wchar.h /usr/include/stdio.h \ + /usr/lib/gcc/x86_64-linux-gnu/4.7/include/stdarg.h \ + /usr/include/x86_64-linux-gnu/bits/wchar.h \ + /usr/lib/gcc/x86_64-linux-gnu/4.7/include/stddef.h \ + /usr/include/xlocale.h /usr/include/c++/4.7/exception \ + /usr/include/c++/4.7/bits/atomic_lockfree_defines.h \ + /usr/include/c++/4.7/bits/char_traits.h \ + /usr/include/c++/4.7/bits/stl_algobase.h \ + /usr/include/c++/4.7/bits/functexcept.h \ + /usr/include/c++/4.7/bits/exception_defines.h \ + /usr/include/c++/4.7/bits/cpp_type_traits.h \ + /usr/include/c++/4.7/ext/type_traits.h \ + /usr/include/c++/4.7/ext/numeric_traits.h \ + /usr/include/c++/4.7/bits/stl_pair.h /usr/include/c++/4.7/bits/move.h \ + /usr/include/c++/4.7/bits/concept_check.h \ + /usr/include/c++/4.7/bits/stl_iterator_base_types.h \ + /usr/include/c++/4.7/bits/stl_iterator_base_funcs.h \ + /usr/include/c++/4.7/bits/stl_iterator.h \ + /usr/include/c++/4.7/debug/debug.h /usr/include/c++/4.7/bits/localefwd.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++locale.h \ + /usr/include/c++/4.7/clocale /usr/include/locale.h \ + /usr/include/x86_64-linux-gnu/bits/locale.h /usr/include/c++/4.7/cctype \ + /usr/include/ctype.h /usr/include/x86_64-linux-gnu/bits/types.h \ + /usr/include/x86_64-linux-gnu/bits/typesizes.h /usr/include/endian.h \ + /usr/include/x86_64-linux-gnu/bits/endian.h \ + /usr/include/x86_64-linux-gnu/bits/byteswap.h \ + /usr/include/c++/4.7/bits/ios_base.h \ + /usr/include/c++/4.7/ext/atomicity.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr-default.h \ + /usr/include/pthread.h /usr/include/sched.h /usr/include/time.h \ + /usr/include/x86_64-linux-gnu/bits/sched.h \ + /usr/include/x86_64-linux-gnu/bits/time.h \ + /usr/include/x86_64-linux-gnu/bits/pthreadtypes.h \ + /usr/include/x86_64-linux-gnu/bits/setjmp.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/atomic_word.h \ + /usr/include/c++/4.7/bits/locale_classes.h /usr/include/c++/4.7/string \ + /usr/include/c++/4.7/bits/allocator.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++allocator.h \ + /usr/include/c++/4.7/ext/new_allocator.h /usr/include/c++/4.7/new \ + /usr/include/c++/4.7/bits/ostream_insert.h \ + /usr/include/c++/4.7/bits/cxxabi_forced.h \ + /usr/include/c++/4.7/bits/stl_function.h \ + /usr/include/c++/4.7/backward/binders.h \ + /usr/include/c++/4.7/bits/range_access.h \ + /usr/include/c++/4.7/bits/basic_string.h \ + /usr/include/c++/4.7/bits/basic_string.tcc \ + /usr/include/c++/4.7/bits/locale_classes.tcc \ + /usr/include/c++/4.7/streambuf /usr/include/c++/4.7/bits/streambuf.tcc \ + /usr/include/c++/4.7/bits/basic_ios.h \ + /usr/include/c++/4.7/bits/locale_facets.h /usr/include/c++/4.7/cwctype \ + /usr/include/wctype.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_base.h \ + /usr/include/c++/4.7/bits/streambuf_iterator.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_inline.h \ + /usr/include/c++/4.7/bits/locale_facets.tcc \ + /usr/include/c++/4.7/bits/basic_ios.tcc \ + /usr/include/c++/4.7/bits/ostream.tcc /usr/include/c++/4.7/istream \ + /usr/include/c++/4.7/bits/istream.tcc /usr/include/c++/4.7/fstream \ + /usr/include/c++/4.7/bits/codecvt.h /usr/include/c++/4.7/cstdio \ + /usr/include/libio.h /usr/include/_G_config.h \ + /usr/include/x86_64-linux-gnu/bits/stdio_lim.h \ + /usr/include/x86_64-linux-gnu/bits/sys_errlist.h \ + /usr/include/x86_64-linux-gnu/bits/stdio.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/basic_file.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++io.h \ + /usr/include/c++/4.7/bits/fstream.tcc /usr/include/c++/4.7/cstring \ + /usr/include/string.h lemon/smart_graph.h /usr/include/c++/4.7/vector \ + /usr/include/c++/4.7/bits/stl_construct.h \ + /usr/include/c++/4.7/ext/alloc_traits.h \ + /usr/include/c++/4.7/bits/stl_uninitialized.h \ + /usr/include/c++/4.7/bits/stl_vector.h \ + /usr/include/c++/4.7/bits/stl_bvector.h \ + /usr/include/c++/4.7/bits/vector.tcc lemon/core.h \ + /usr/include/c++/4.7/algorithm /usr/include/c++/4.7/utility \ + /usr/include/c++/4.7/bits/stl_relops.h \ + /usr/include/c++/4.7/bits/stl_algo.h /usr/include/c++/4.7/cstdlib \ + /usr/include/stdlib.h /usr/include/x86_64-linux-gnu/bits/waitflags.h \ + /usr/include/x86_64-linux-gnu/bits/waitstatus.h \ + /usr/include/x86_64-linux-gnu/sys/types.h \ + /usr/include/x86_64-linux-gnu/sys/select.h \ + /usr/include/x86_64-linux-gnu/bits/select.h \ + /usr/include/x86_64-linux-gnu/bits/sigset.h \ + /usr/include/x86_64-linux-gnu/sys/sysmacros.h /usr/include/alloca.h \ + /usr/include/c++/4.7/bits/algorithmfwd.h \ + /usr/include/c++/4.7/bits/stl_heap.h \ + /usr/include/c++/4.7/bits/stl_tempbuf.h lemon/config.h \ + lemon/bits/enable_if.h lemon/bits/traits.h lemon/assert.h lemon/error.h \ + /usr/include/c++/4.7/sstream /usr/include/c++/4.7/bits/sstream.tcc \ + /usr/include/c++/4.7/memory \ + /usr/include/c++/4.7/bits/stl_raw_storage_iter.h \ + /usr/include/c++/4.7/backward/auto_ptr.h lemon/bits/graph_extender.h \ + lemon/bits/map_extender.h /usr/include/c++/4.7/iterator \ + /usr/include/c++/4.7/bits/stream_iterator.h lemon/concept_check.h \ + lemon/concepts/maps.h lemon/bits/default_map.h lemon/bits/array_map.h \ + lemon/bits/alteration_notifier.h /usr/include/c++/4.7/list \ + /usr/include/c++/4.7/bits/stl_list.h /usr/include/c++/4.7/bits/list.tcc \ + lemon/bits/vector_map.h lemon/dimacs.h /usr/include/c++/4.7/limits \ + lemon/maps.h /usr/include/c++/4.7/functional /usr/include/c++/4.7/map \ + /usr/include/c++/4.7/bits/stl_tree.h /usr/include/c++/4.7/bits/stl_map.h \ + /usr/include/c++/4.7/bits/stl_multimap.h lemon/lgf_writer.h \ + lemon/time_measure.h /usr/include/unistd.h \ + /usr/include/x86_64-linux-gnu/bits/posix_opt.h \ + /usr/include/x86_64-linux-gnu/bits/environments.h \ + /usr/include/x86_64-linux-gnu/bits/confname.h /usr/include/getopt.h \ + /usr/include/x86_64-linux-gnu/sys/times.h \ + /usr/include/x86_64-linux-gnu/sys/time.h lemon/arg_parser.h \ + lemon/dijkstra.h lemon/list_graph.h lemon/bin_heap.h \ + lemon/bits/path_dump.h lemon/path.h lemon/concepts/path.h \ + lemon/preflow.h lemon/tolerance.h lemon/elevator.h lemon/matching.h \ + /usr/include/c++/4.7/queue /usr/include/c++/4.7/deque \ + /usr/include/c++/4.7/bits/stl_deque.h \ + /usr/include/c++/4.7/bits/deque.tcc \ + /usr/include/c++/4.7/bits/stl_queue.h /usr/include/c++/4.7/set \ + /usr/include/c++/4.7/bits/stl_set.h \ + /usr/include/c++/4.7/bits/stl_multiset.h lemon/unionfind.h \ + lemon/fractional_matching.h lemon/network_simplex.h lemon/math.h \ + /usr/include/c++/4.7/cmath /usr/include/math.h \ + /usr/include/x86_64-linux-gnu/bits/huge_val.h \ + /usr/include/x86_64-linux-gnu/bits/huge_valf.h \ + /usr/include/x86_64-linux-gnu/bits/huge_vall.h \ + /usr/include/x86_64-linux-gnu/bits/inf.h \ + /usr/include/x86_64-linux-gnu/bits/nan.h \ + /usr/include/x86_64-linux-gnu/bits/mathdef.h \ + /usr/include/x86_64-linux-gnu/bits/mathcalls.h \ + /usr/include/x86_64-linux-gnu/bits/mathinline.h + +/usr/include/c++/4.7/iostream: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++config.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/os_defines.h: + +/usr/include/features.h: + +/usr/include/x86_64-linux-gnu/bits/predefs.h: + +/usr/include/x86_64-linux-gnu/sys/cdefs.h: + +/usr/include/x86_64-linux-gnu/bits/wordsize.h: + +/usr/include/x86_64-linux-gnu/gnu/stubs.h: + +/usr/include/x86_64-linux-gnu/gnu/stubs-64.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/cpu_defines.h: + +/usr/include/c++/4.7/ostream: + +/usr/include/c++/4.7/ios: + +/usr/include/c++/4.7/iosfwd: + +/usr/include/c++/4.7/bits/stringfwd.h: + +/usr/include/c++/4.7/bits/postypes.h: + +/usr/include/c++/4.7/cwchar: + +/usr/include/wchar.h: + +/usr/include/stdio.h: + +/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stdarg.h: + +/usr/include/x86_64-linux-gnu/bits/wchar.h: + +/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stddef.h: + +/usr/include/xlocale.h: + +/usr/include/c++/4.7/exception: + +/usr/include/c++/4.7/bits/atomic_lockfree_defines.h: + +/usr/include/c++/4.7/bits/char_traits.h: + +/usr/include/c++/4.7/bits/stl_algobase.h: + +/usr/include/c++/4.7/bits/functexcept.h: + +/usr/include/c++/4.7/bits/exception_defines.h: + +/usr/include/c++/4.7/bits/cpp_type_traits.h: + +/usr/include/c++/4.7/ext/type_traits.h: + +/usr/include/c++/4.7/ext/numeric_traits.h: + +/usr/include/c++/4.7/bits/stl_pair.h: + +/usr/include/c++/4.7/bits/move.h: + +/usr/include/c++/4.7/bits/concept_check.h: + +/usr/include/c++/4.7/bits/stl_iterator_base_types.h: + +/usr/include/c++/4.7/bits/stl_iterator_base_funcs.h: + +/usr/include/c++/4.7/bits/stl_iterator.h: + +/usr/include/c++/4.7/debug/debug.h: + +/usr/include/c++/4.7/bits/localefwd.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++locale.h: + +/usr/include/c++/4.7/clocale: + +/usr/include/locale.h: + +/usr/include/x86_64-linux-gnu/bits/locale.h: + +/usr/include/c++/4.7/cctype: + +/usr/include/ctype.h: + +/usr/include/x86_64-linux-gnu/bits/types.h: + +/usr/include/x86_64-linux-gnu/bits/typesizes.h: + +/usr/include/endian.h: + +/usr/include/x86_64-linux-gnu/bits/endian.h: + +/usr/include/x86_64-linux-gnu/bits/byteswap.h: + +/usr/include/c++/4.7/bits/ios_base.h: + +/usr/include/c++/4.7/ext/atomicity.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr-default.h: + +/usr/include/pthread.h: + +/usr/include/sched.h: + +/usr/include/time.h: + +/usr/include/x86_64-linux-gnu/bits/sched.h: + +/usr/include/x86_64-linux-gnu/bits/time.h: + +/usr/include/x86_64-linux-gnu/bits/pthreadtypes.h: + +/usr/include/x86_64-linux-gnu/bits/setjmp.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/atomic_word.h: + +/usr/include/c++/4.7/bits/locale_classes.h: + +/usr/include/c++/4.7/string: + +/usr/include/c++/4.7/bits/allocator.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++allocator.h: + +/usr/include/c++/4.7/ext/new_allocator.h: + +/usr/include/c++/4.7/new: + +/usr/include/c++/4.7/bits/ostream_insert.h: + +/usr/include/c++/4.7/bits/cxxabi_forced.h: + +/usr/include/c++/4.7/bits/stl_function.h: + +/usr/include/c++/4.7/backward/binders.h: + +/usr/include/c++/4.7/bits/range_access.h: + +/usr/include/c++/4.7/bits/basic_string.h: + +/usr/include/c++/4.7/bits/basic_string.tcc: + +/usr/include/c++/4.7/bits/locale_classes.tcc: + +/usr/include/c++/4.7/streambuf: + +/usr/include/c++/4.7/bits/streambuf.tcc: + +/usr/include/c++/4.7/bits/basic_ios.h: + +/usr/include/c++/4.7/bits/locale_facets.h: + +/usr/include/c++/4.7/cwctype: + +/usr/include/wctype.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_base.h: + +/usr/include/c++/4.7/bits/streambuf_iterator.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_inline.h: + +/usr/include/c++/4.7/bits/locale_facets.tcc: + +/usr/include/c++/4.7/bits/basic_ios.tcc: + +/usr/include/c++/4.7/bits/ostream.tcc: + +/usr/include/c++/4.7/istream: + +/usr/include/c++/4.7/bits/istream.tcc: + +/usr/include/c++/4.7/fstream: + +/usr/include/c++/4.7/bits/codecvt.h: + +/usr/include/c++/4.7/cstdio: + +/usr/include/libio.h: + +/usr/include/_G_config.h: + +/usr/include/x86_64-linux-gnu/bits/stdio_lim.h: + +/usr/include/x86_64-linux-gnu/bits/sys_errlist.h: + +/usr/include/x86_64-linux-gnu/bits/stdio.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/basic_file.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++io.h: + +/usr/include/c++/4.7/bits/fstream.tcc: + +/usr/include/c++/4.7/cstring: + +/usr/include/string.h: + +lemon/smart_graph.h: + +/usr/include/c++/4.7/vector: + +/usr/include/c++/4.7/bits/stl_construct.h: + +/usr/include/c++/4.7/ext/alloc_traits.h: + +/usr/include/c++/4.7/bits/stl_uninitialized.h: + +/usr/include/c++/4.7/bits/stl_vector.h: + +/usr/include/c++/4.7/bits/stl_bvector.h: + +/usr/include/c++/4.7/bits/vector.tcc: + +lemon/core.h: + +/usr/include/c++/4.7/algorithm: + +/usr/include/c++/4.7/utility: + +/usr/include/c++/4.7/bits/stl_relops.h: + +/usr/include/c++/4.7/bits/stl_algo.h: + +/usr/include/c++/4.7/cstdlib: + +/usr/include/stdlib.h: + +/usr/include/x86_64-linux-gnu/bits/waitflags.h: + +/usr/include/x86_64-linux-gnu/bits/waitstatus.h: + +/usr/include/x86_64-linux-gnu/sys/types.h: + +/usr/include/x86_64-linux-gnu/sys/select.h: + +/usr/include/x86_64-linux-gnu/bits/select.h: + +/usr/include/x86_64-linux-gnu/bits/sigset.h: + +/usr/include/x86_64-linux-gnu/sys/sysmacros.h: + +/usr/include/alloca.h: + +/usr/include/c++/4.7/bits/algorithmfwd.h: + +/usr/include/c++/4.7/bits/stl_heap.h: + +/usr/include/c++/4.7/bits/stl_tempbuf.h: + +lemon/config.h: + +lemon/bits/enable_if.h: + +lemon/bits/traits.h: + +lemon/assert.h: + +lemon/error.h: + +/usr/include/c++/4.7/sstream: + +/usr/include/c++/4.7/bits/sstream.tcc: + +/usr/include/c++/4.7/memory: + +/usr/include/c++/4.7/bits/stl_raw_storage_iter.h: + +/usr/include/c++/4.7/backward/auto_ptr.h: + +lemon/bits/graph_extender.h: + +lemon/bits/map_extender.h: + +/usr/include/c++/4.7/iterator: + +/usr/include/c++/4.7/bits/stream_iterator.h: + +lemon/concept_check.h: + +lemon/concepts/maps.h: + +lemon/bits/default_map.h: + +lemon/bits/array_map.h: + +lemon/bits/alteration_notifier.h: + +/usr/include/c++/4.7/list: + +/usr/include/c++/4.7/bits/stl_list.h: + +/usr/include/c++/4.7/bits/list.tcc: + +lemon/bits/vector_map.h: + +lemon/dimacs.h: + +/usr/include/c++/4.7/limits: + +lemon/maps.h: + +/usr/include/c++/4.7/functional: + +/usr/include/c++/4.7/map: + +/usr/include/c++/4.7/bits/stl_tree.h: + +/usr/include/c++/4.7/bits/stl_map.h: + +/usr/include/c++/4.7/bits/stl_multimap.h: + +lemon/lgf_writer.h: + +lemon/time_measure.h: + +/usr/include/unistd.h: + +/usr/include/x86_64-linux-gnu/bits/posix_opt.h: + +/usr/include/x86_64-linux-gnu/bits/environments.h: + +/usr/include/x86_64-linux-gnu/bits/confname.h: + +/usr/include/getopt.h: + +/usr/include/x86_64-linux-gnu/sys/times.h: + +/usr/include/x86_64-linux-gnu/sys/time.h: + +lemon/arg_parser.h: + +lemon/dijkstra.h: + +lemon/list_graph.h: + +lemon/bin_heap.h: + +lemon/bits/path_dump.h: + +lemon/path.h: + +lemon/concepts/path.h: + +lemon/preflow.h: + +lemon/tolerance.h: + +lemon/elevator.h: + +lemon/matching.h: + +/usr/include/c++/4.7/queue: + +/usr/include/c++/4.7/deque: + +/usr/include/c++/4.7/bits/stl_deque.h: + +/usr/include/c++/4.7/bits/deque.tcc: + +/usr/include/c++/4.7/bits/stl_queue.h: + +/usr/include/c++/4.7/set: + +/usr/include/c++/4.7/bits/stl_set.h: + +/usr/include/c++/4.7/bits/stl_multiset.h: + +lemon/unionfind.h: + +lemon/fractional_matching.h: + +lemon/network_simplex.h: + +lemon/math.h: + +/usr/include/c++/4.7/cmath: + +/usr/include/math.h: + +/usr/include/x86_64-linux-gnu/bits/huge_val.h: + +/usr/include/x86_64-linux-gnu/bits/huge_valf.h: + +/usr/include/x86_64-linux-gnu/bits/huge_vall.h: + +/usr/include/x86_64-linux-gnu/bits/inf.h: + +/usr/include/x86_64-linux-gnu/bits/nan.h: + +/usr/include/x86_64-linux-gnu/bits/mathdef.h: + +/usr/include/x86_64-linux-gnu/bits/mathcalls.h: + +/usr/include/x86_64-linux-gnu/bits/mathinline.h: diff --git a/lemon/tools/.deps/dimacs-to-lgf.Po b/lemon/tools/.deps/dimacs-to-lgf.Po new file mode 100644 index 0000000..f4f3a75 --- /dev/null +++ b/lemon/tools/.deps/dimacs-to-lgf.Po @@ -0,0 +1,439 @@ +tools/dimacs-to-lgf.o: tools/dimacs-to-lgf.cc \ + /usr/include/c++/4.7/iostream \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++config.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/os_defines.h \ + /usr/include/features.h /usr/include/x86_64-linux-gnu/bits/predefs.h \ + /usr/include/x86_64-linux-gnu/sys/cdefs.h \ + /usr/include/x86_64-linux-gnu/bits/wordsize.h \ + /usr/include/x86_64-linux-gnu/gnu/stubs.h \ + /usr/include/x86_64-linux-gnu/gnu/stubs-64.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/cpu_defines.h \ + /usr/include/c++/4.7/ostream /usr/include/c++/4.7/ios \ + /usr/include/c++/4.7/iosfwd /usr/include/c++/4.7/bits/stringfwd.h \ + /usr/include/c++/4.7/bits/postypes.h /usr/include/c++/4.7/cwchar \ + /usr/include/wchar.h /usr/include/stdio.h \ + /usr/lib/gcc/x86_64-linux-gnu/4.7/include/stdarg.h \ + /usr/include/x86_64-linux-gnu/bits/wchar.h \ + /usr/lib/gcc/x86_64-linux-gnu/4.7/include/stddef.h \ + /usr/include/xlocale.h /usr/include/c++/4.7/exception \ + /usr/include/c++/4.7/bits/atomic_lockfree_defines.h \ + /usr/include/c++/4.7/bits/char_traits.h \ + /usr/include/c++/4.7/bits/stl_algobase.h \ + /usr/include/c++/4.7/bits/functexcept.h \ + /usr/include/c++/4.7/bits/exception_defines.h \ + /usr/include/c++/4.7/bits/cpp_type_traits.h \ + /usr/include/c++/4.7/ext/type_traits.h \ + /usr/include/c++/4.7/ext/numeric_traits.h \ + /usr/include/c++/4.7/bits/stl_pair.h /usr/include/c++/4.7/bits/move.h \ + /usr/include/c++/4.7/bits/concept_check.h \ + /usr/include/c++/4.7/bits/stl_iterator_base_types.h \ + /usr/include/c++/4.7/bits/stl_iterator_base_funcs.h \ + /usr/include/c++/4.7/bits/stl_iterator.h \ + /usr/include/c++/4.7/debug/debug.h /usr/include/c++/4.7/bits/localefwd.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++locale.h \ + /usr/include/c++/4.7/clocale /usr/include/locale.h \ + /usr/include/x86_64-linux-gnu/bits/locale.h /usr/include/c++/4.7/cctype \ + /usr/include/ctype.h /usr/include/x86_64-linux-gnu/bits/types.h \ + /usr/include/x86_64-linux-gnu/bits/typesizes.h /usr/include/endian.h \ + /usr/include/x86_64-linux-gnu/bits/endian.h \ + /usr/include/x86_64-linux-gnu/bits/byteswap.h \ + /usr/include/c++/4.7/bits/ios_base.h \ + /usr/include/c++/4.7/ext/atomicity.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr-default.h \ + /usr/include/pthread.h /usr/include/sched.h /usr/include/time.h \ + /usr/include/x86_64-linux-gnu/bits/sched.h \ + /usr/include/x86_64-linux-gnu/bits/time.h \ + /usr/include/x86_64-linux-gnu/bits/pthreadtypes.h \ + /usr/include/x86_64-linux-gnu/bits/setjmp.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/atomic_word.h \ + /usr/include/c++/4.7/bits/locale_classes.h /usr/include/c++/4.7/string \ + /usr/include/c++/4.7/bits/allocator.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++allocator.h \ + /usr/include/c++/4.7/ext/new_allocator.h /usr/include/c++/4.7/new \ + /usr/include/c++/4.7/bits/ostream_insert.h \ + /usr/include/c++/4.7/bits/cxxabi_forced.h \ + /usr/include/c++/4.7/bits/stl_function.h \ + /usr/include/c++/4.7/backward/binders.h \ + /usr/include/c++/4.7/bits/range_access.h \ + /usr/include/c++/4.7/bits/basic_string.h \ + /usr/include/c++/4.7/bits/basic_string.tcc \ + /usr/include/c++/4.7/bits/locale_classes.tcc \ + /usr/include/c++/4.7/streambuf /usr/include/c++/4.7/bits/streambuf.tcc \ + /usr/include/c++/4.7/bits/basic_ios.h \ + /usr/include/c++/4.7/bits/locale_facets.h /usr/include/c++/4.7/cwctype \ + /usr/include/wctype.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_base.h \ + /usr/include/c++/4.7/bits/streambuf_iterator.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_inline.h \ + /usr/include/c++/4.7/bits/locale_facets.tcc \ + /usr/include/c++/4.7/bits/basic_ios.tcc \ + /usr/include/c++/4.7/bits/ostream.tcc /usr/include/c++/4.7/istream \ + /usr/include/c++/4.7/bits/istream.tcc /usr/include/c++/4.7/fstream \ + /usr/include/c++/4.7/bits/codecvt.h /usr/include/c++/4.7/cstdio \ + /usr/include/libio.h /usr/include/_G_config.h \ + /usr/include/x86_64-linux-gnu/bits/stdio_lim.h \ + /usr/include/x86_64-linux-gnu/bits/sys_errlist.h \ + /usr/include/x86_64-linux-gnu/bits/stdio.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/basic_file.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++io.h \ + /usr/include/c++/4.7/bits/fstream.tcc /usr/include/c++/4.7/cstring \ + /usr/include/string.h lemon/smart_graph.h /usr/include/c++/4.7/vector \ + /usr/include/c++/4.7/bits/stl_construct.h \ + /usr/include/c++/4.7/ext/alloc_traits.h \ + /usr/include/c++/4.7/bits/stl_uninitialized.h \ + /usr/include/c++/4.7/bits/stl_vector.h \ + /usr/include/c++/4.7/bits/stl_bvector.h \ + /usr/include/c++/4.7/bits/vector.tcc lemon/core.h \ + /usr/include/c++/4.7/algorithm /usr/include/c++/4.7/utility \ + /usr/include/c++/4.7/bits/stl_relops.h \ + /usr/include/c++/4.7/bits/stl_algo.h /usr/include/c++/4.7/cstdlib \ + /usr/include/stdlib.h /usr/include/x86_64-linux-gnu/bits/waitflags.h \ + /usr/include/x86_64-linux-gnu/bits/waitstatus.h \ + /usr/include/x86_64-linux-gnu/sys/types.h \ + /usr/include/x86_64-linux-gnu/sys/select.h \ + /usr/include/x86_64-linux-gnu/bits/select.h \ + /usr/include/x86_64-linux-gnu/bits/sigset.h \ + /usr/include/x86_64-linux-gnu/sys/sysmacros.h /usr/include/alloca.h \ + /usr/include/c++/4.7/bits/algorithmfwd.h \ + /usr/include/c++/4.7/bits/stl_heap.h \ + /usr/include/c++/4.7/bits/stl_tempbuf.h lemon/config.h \ + lemon/bits/enable_if.h lemon/bits/traits.h lemon/assert.h lemon/error.h \ + /usr/include/c++/4.7/sstream /usr/include/c++/4.7/bits/sstream.tcc \ + /usr/include/c++/4.7/memory \ + /usr/include/c++/4.7/bits/stl_raw_storage_iter.h \ + /usr/include/c++/4.7/backward/auto_ptr.h lemon/bits/graph_extender.h \ + lemon/bits/map_extender.h /usr/include/c++/4.7/iterator \ + /usr/include/c++/4.7/bits/stream_iterator.h lemon/concept_check.h \ + lemon/concepts/maps.h lemon/bits/default_map.h lemon/bits/array_map.h \ + lemon/bits/alteration_notifier.h /usr/include/c++/4.7/list \ + /usr/include/c++/4.7/bits/stl_list.h /usr/include/c++/4.7/bits/list.tcc \ + lemon/bits/vector_map.h lemon/dimacs.h /usr/include/c++/4.7/limits \ + lemon/maps.h /usr/include/c++/4.7/functional /usr/include/c++/4.7/map \ + /usr/include/c++/4.7/bits/stl_tree.h /usr/include/c++/4.7/bits/stl_map.h \ + /usr/include/c++/4.7/bits/stl_multimap.h lemon/lgf_writer.h \ + lemon/arg_parser.h + +/usr/include/c++/4.7/iostream: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++config.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/os_defines.h: + +/usr/include/features.h: + +/usr/include/x86_64-linux-gnu/bits/predefs.h: + +/usr/include/x86_64-linux-gnu/sys/cdefs.h: + +/usr/include/x86_64-linux-gnu/bits/wordsize.h: + +/usr/include/x86_64-linux-gnu/gnu/stubs.h: + +/usr/include/x86_64-linux-gnu/gnu/stubs-64.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/cpu_defines.h: + +/usr/include/c++/4.7/ostream: + +/usr/include/c++/4.7/ios: + +/usr/include/c++/4.7/iosfwd: + +/usr/include/c++/4.7/bits/stringfwd.h: + +/usr/include/c++/4.7/bits/postypes.h: + +/usr/include/c++/4.7/cwchar: + +/usr/include/wchar.h: + +/usr/include/stdio.h: + +/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stdarg.h: + +/usr/include/x86_64-linux-gnu/bits/wchar.h: + +/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stddef.h: + +/usr/include/xlocale.h: + +/usr/include/c++/4.7/exception: + +/usr/include/c++/4.7/bits/atomic_lockfree_defines.h: + +/usr/include/c++/4.7/bits/char_traits.h: + +/usr/include/c++/4.7/bits/stl_algobase.h: + +/usr/include/c++/4.7/bits/functexcept.h: + +/usr/include/c++/4.7/bits/exception_defines.h: + +/usr/include/c++/4.7/bits/cpp_type_traits.h: + +/usr/include/c++/4.7/ext/type_traits.h: + +/usr/include/c++/4.7/ext/numeric_traits.h: + +/usr/include/c++/4.7/bits/stl_pair.h: + +/usr/include/c++/4.7/bits/move.h: + +/usr/include/c++/4.7/bits/concept_check.h: + +/usr/include/c++/4.7/bits/stl_iterator_base_types.h: + +/usr/include/c++/4.7/bits/stl_iterator_base_funcs.h: + +/usr/include/c++/4.7/bits/stl_iterator.h: + +/usr/include/c++/4.7/debug/debug.h: + +/usr/include/c++/4.7/bits/localefwd.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++locale.h: + +/usr/include/c++/4.7/clocale: + +/usr/include/locale.h: + +/usr/include/x86_64-linux-gnu/bits/locale.h: + +/usr/include/c++/4.7/cctype: + +/usr/include/ctype.h: + +/usr/include/x86_64-linux-gnu/bits/types.h: + +/usr/include/x86_64-linux-gnu/bits/typesizes.h: + +/usr/include/endian.h: + +/usr/include/x86_64-linux-gnu/bits/endian.h: + +/usr/include/x86_64-linux-gnu/bits/byteswap.h: + +/usr/include/c++/4.7/bits/ios_base.h: + +/usr/include/c++/4.7/ext/atomicity.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr-default.h: + +/usr/include/pthread.h: + +/usr/include/sched.h: + +/usr/include/time.h: + +/usr/include/x86_64-linux-gnu/bits/sched.h: + +/usr/include/x86_64-linux-gnu/bits/time.h: + +/usr/include/x86_64-linux-gnu/bits/pthreadtypes.h: + +/usr/include/x86_64-linux-gnu/bits/setjmp.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/atomic_word.h: + +/usr/include/c++/4.7/bits/locale_classes.h: + +/usr/include/c++/4.7/string: + +/usr/include/c++/4.7/bits/allocator.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++allocator.h: + +/usr/include/c++/4.7/ext/new_allocator.h: + +/usr/include/c++/4.7/new: + +/usr/include/c++/4.7/bits/ostream_insert.h: + +/usr/include/c++/4.7/bits/cxxabi_forced.h: + +/usr/include/c++/4.7/bits/stl_function.h: + +/usr/include/c++/4.7/backward/binders.h: + +/usr/include/c++/4.7/bits/range_access.h: + +/usr/include/c++/4.7/bits/basic_string.h: + +/usr/include/c++/4.7/bits/basic_string.tcc: + +/usr/include/c++/4.7/bits/locale_classes.tcc: + +/usr/include/c++/4.7/streambuf: + +/usr/include/c++/4.7/bits/streambuf.tcc: + +/usr/include/c++/4.7/bits/basic_ios.h: + +/usr/include/c++/4.7/bits/locale_facets.h: + +/usr/include/c++/4.7/cwctype: + +/usr/include/wctype.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_base.h: + +/usr/include/c++/4.7/bits/streambuf_iterator.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_inline.h: + +/usr/include/c++/4.7/bits/locale_facets.tcc: + +/usr/include/c++/4.7/bits/basic_ios.tcc: + +/usr/include/c++/4.7/bits/ostream.tcc: + +/usr/include/c++/4.7/istream: + +/usr/include/c++/4.7/bits/istream.tcc: + +/usr/include/c++/4.7/fstream: + +/usr/include/c++/4.7/bits/codecvt.h: + +/usr/include/c++/4.7/cstdio: + +/usr/include/libio.h: + +/usr/include/_G_config.h: + +/usr/include/x86_64-linux-gnu/bits/stdio_lim.h: + +/usr/include/x86_64-linux-gnu/bits/sys_errlist.h: + +/usr/include/x86_64-linux-gnu/bits/stdio.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/basic_file.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++io.h: + +/usr/include/c++/4.7/bits/fstream.tcc: + +/usr/include/c++/4.7/cstring: + +/usr/include/string.h: + +lemon/smart_graph.h: + +/usr/include/c++/4.7/vector: + +/usr/include/c++/4.7/bits/stl_construct.h: + +/usr/include/c++/4.7/ext/alloc_traits.h: + +/usr/include/c++/4.7/bits/stl_uninitialized.h: + +/usr/include/c++/4.7/bits/stl_vector.h: + +/usr/include/c++/4.7/bits/stl_bvector.h: + +/usr/include/c++/4.7/bits/vector.tcc: + +lemon/core.h: + +/usr/include/c++/4.7/algorithm: + +/usr/include/c++/4.7/utility: + +/usr/include/c++/4.7/bits/stl_relops.h: + +/usr/include/c++/4.7/bits/stl_algo.h: + +/usr/include/c++/4.7/cstdlib: + +/usr/include/stdlib.h: + +/usr/include/x86_64-linux-gnu/bits/waitflags.h: + +/usr/include/x86_64-linux-gnu/bits/waitstatus.h: + +/usr/include/x86_64-linux-gnu/sys/types.h: + +/usr/include/x86_64-linux-gnu/sys/select.h: + +/usr/include/x86_64-linux-gnu/bits/select.h: + +/usr/include/x86_64-linux-gnu/bits/sigset.h: + +/usr/include/x86_64-linux-gnu/sys/sysmacros.h: + +/usr/include/alloca.h: + +/usr/include/c++/4.7/bits/algorithmfwd.h: + +/usr/include/c++/4.7/bits/stl_heap.h: + +/usr/include/c++/4.7/bits/stl_tempbuf.h: + +lemon/config.h: + +lemon/bits/enable_if.h: + +lemon/bits/traits.h: + +lemon/assert.h: + +lemon/error.h: + +/usr/include/c++/4.7/sstream: + +/usr/include/c++/4.7/bits/sstream.tcc: + +/usr/include/c++/4.7/memory: + +/usr/include/c++/4.7/bits/stl_raw_storage_iter.h: + +/usr/include/c++/4.7/backward/auto_ptr.h: + +lemon/bits/graph_extender.h: + +lemon/bits/map_extender.h: + +/usr/include/c++/4.7/iterator: + +/usr/include/c++/4.7/bits/stream_iterator.h: + +lemon/concept_check.h: + +lemon/concepts/maps.h: + +lemon/bits/default_map.h: + +lemon/bits/array_map.h: + +lemon/bits/alteration_notifier.h: + +/usr/include/c++/4.7/list: + +/usr/include/c++/4.7/bits/stl_list.h: + +/usr/include/c++/4.7/bits/list.tcc: + +lemon/bits/vector_map.h: + +lemon/dimacs.h: + +/usr/include/c++/4.7/limits: + +lemon/maps.h: + +/usr/include/c++/4.7/functional: + +/usr/include/c++/4.7/map: + +/usr/include/c++/4.7/bits/stl_tree.h: + +/usr/include/c++/4.7/bits/stl_map.h: + +/usr/include/c++/4.7/bits/stl_multimap.h: + +lemon/lgf_writer.h: + +lemon/arg_parser.h: diff --git a/lemon/tools/.deps/lgf-gen.Po b/lemon/tools/.deps/lgf-gen.Po new file mode 100644 index 0000000..81a1657 --- /dev/null +++ b/lemon/tools/.deps/lgf-gen.Po @@ -0,0 +1,567 @@ +tools/lgf-gen.o: tools/lgf-gen.cc /usr/include/c++/4.7/algorithm \ + /usr/include/c++/4.7/utility \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++config.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/os_defines.h \ + /usr/include/features.h /usr/include/x86_64-linux-gnu/bits/predefs.h \ + /usr/include/x86_64-linux-gnu/sys/cdefs.h \ + /usr/include/x86_64-linux-gnu/bits/wordsize.h \ + /usr/include/x86_64-linux-gnu/gnu/stubs.h \ + /usr/include/x86_64-linux-gnu/gnu/stubs-64.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/cpu_defines.h \ + /usr/include/c++/4.7/bits/stl_relops.h \ + /usr/include/c++/4.7/bits/stl_pair.h /usr/include/c++/4.7/bits/move.h \ + /usr/include/c++/4.7/bits/concept_check.h \ + /usr/include/c++/4.7/bits/stl_algobase.h \ + /usr/include/c++/4.7/bits/functexcept.h \ + /usr/include/c++/4.7/bits/exception_defines.h \ + /usr/include/c++/4.7/bits/cpp_type_traits.h \ + /usr/include/c++/4.7/ext/type_traits.h \ + /usr/include/c++/4.7/ext/numeric_traits.h \ + /usr/include/c++/4.7/bits/stl_iterator_base_types.h \ + /usr/include/c++/4.7/bits/stl_iterator_base_funcs.h \ + /usr/include/c++/4.7/bits/stl_iterator.h \ + /usr/include/c++/4.7/debug/debug.h /usr/include/c++/4.7/bits/stl_algo.h \ + /usr/include/c++/4.7/cstdlib /usr/include/stdlib.h \ + /usr/lib/gcc/x86_64-linux-gnu/4.7/include/stddef.h \ + /usr/include/x86_64-linux-gnu/bits/waitflags.h \ + /usr/include/x86_64-linux-gnu/bits/waitstatus.h /usr/include/endian.h \ + /usr/include/x86_64-linux-gnu/bits/endian.h \ + /usr/include/x86_64-linux-gnu/bits/byteswap.h /usr/include/xlocale.h \ + /usr/include/x86_64-linux-gnu/sys/types.h \ + /usr/include/x86_64-linux-gnu/bits/types.h \ + /usr/include/x86_64-linux-gnu/bits/typesizes.h /usr/include/time.h \ + /usr/include/x86_64-linux-gnu/sys/select.h \ + /usr/include/x86_64-linux-gnu/bits/select.h \ + /usr/include/x86_64-linux-gnu/bits/sigset.h \ + /usr/include/x86_64-linux-gnu/bits/time.h \ + /usr/include/x86_64-linux-gnu/sys/sysmacros.h \ + /usr/include/x86_64-linux-gnu/bits/pthreadtypes.h /usr/include/alloca.h \ + /usr/include/c++/4.7/bits/algorithmfwd.h \ + /usr/include/c++/4.7/bits/stl_heap.h \ + /usr/include/c++/4.7/bits/stl_tempbuf.h \ + /usr/include/c++/4.7/bits/stl_construct.h /usr/include/c++/4.7/new \ + /usr/include/c++/4.7/exception \ + /usr/include/c++/4.7/bits/atomic_lockfree_defines.h \ + /usr/include/c++/4.7/ext/alloc_traits.h \ + /usr/include/c++/4.7/bits/allocator.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++allocator.h \ + /usr/include/c++/4.7/ext/new_allocator.h /usr/include/c++/4.7/set \ + /usr/include/c++/4.7/bits/stl_tree.h \ + /usr/include/c++/4.7/bits/stl_function.h \ + /usr/include/c++/4.7/backward/binders.h \ + /usr/include/c++/4.7/bits/stl_set.h \ + /usr/include/c++/4.7/bits/stl_multiset.h \ + /usr/include/c++/4.7/bits/range_access.h /usr/include/c++/4.7/ctime \ + lemon/list_graph.h lemon/core.h /usr/include/c++/4.7/vector \ + /usr/include/c++/4.7/bits/stl_uninitialized.h \ + /usr/include/c++/4.7/bits/stl_vector.h \ + /usr/include/c++/4.7/bits/stl_bvector.h \ + /usr/include/c++/4.7/bits/vector.tcc lemon/config.h \ + lemon/bits/enable_if.h lemon/bits/traits.h lemon/assert.h lemon/error.h \ + /usr/include/c++/4.7/string /usr/include/c++/4.7/bits/stringfwd.h \ + /usr/include/c++/4.7/bits/char_traits.h \ + /usr/include/c++/4.7/bits/postypes.h /usr/include/c++/4.7/cwchar \ + /usr/include/wchar.h /usr/include/stdio.h \ + /usr/lib/gcc/x86_64-linux-gnu/4.7/include/stdarg.h \ + /usr/include/x86_64-linux-gnu/bits/wchar.h \ + /usr/include/c++/4.7/bits/localefwd.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++locale.h \ + /usr/include/c++/4.7/clocale /usr/include/locale.h \ + /usr/include/x86_64-linux-gnu/bits/locale.h /usr/include/c++/4.7/iosfwd \ + /usr/include/c++/4.7/cctype /usr/include/ctype.h \ + /usr/include/c++/4.7/bits/ostream_insert.h \ + /usr/include/c++/4.7/bits/cxxabi_forced.h \ + /usr/include/c++/4.7/bits/basic_string.h \ + /usr/include/c++/4.7/ext/atomicity.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr-default.h \ + /usr/include/pthread.h /usr/include/sched.h \ + /usr/include/x86_64-linux-gnu/bits/sched.h \ + /usr/include/x86_64-linux-gnu/bits/setjmp.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/atomic_word.h \ + /usr/include/c++/4.7/bits/basic_string.tcc /usr/include/c++/4.7/sstream \ + /usr/include/c++/4.7/istream /usr/include/c++/4.7/ios \ + /usr/include/c++/4.7/bits/ios_base.h \ + /usr/include/c++/4.7/bits/locale_classes.h \ + /usr/include/c++/4.7/bits/locale_classes.tcc \ + /usr/include/c++/4.7/streambuf /usr/include/c++/4.7/bits/streambuf.tcc \ + /usr/include/c++/4.7/bits/basic_ios.h \ + /usr/include/c++/4.7/bits/locale_facets.h /usr/include/c++/4.7/cwctype \ + /usr/include/wctype.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_base.h \ + /usr/include/c++/4.7/bits/streambuf_iterator.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_inline.h \ + /usr/include/c++/4.7/bits/locale_facets.tcc \ + /usr/include/c++/4.7/bits/basic_ios.tcc /usr/include/c++/4.7/ostream \ + /usr/include/c++/4.7/bits/ostream.tcc \ + /usr/include/c++/4.7/bits/istream.tcc \ + /usr/include/c++/4.7/bits/sstream.tcc /usr/include/c++/4.7/iostream \ + /usr/include/c++/4.7/memory \ + /usr/include/c++/4.7/bits/stl_raw_storage_iter.h \ + /usr/include/c++/4.7/backward/auto_ptr.h lemon/bits/graph_extender.h \ + lemon/bits/map_extender.h /usr/include/c++/4.7/iterator \ + /usr/include/c++/4.7/bits/stream_iterator.h lemon/concept_check.h \ + lemon/concepts/maps.h lemon/bits/default_map.h lemon/bits/array_map.h \ + lemon/bits/alteration_notifier.h /usr/include/c++/4.7/list \ + /usr/include/c++/4.7/bits/stl_list.h /usr/include/c++/4.7/bits/list.tcc \ + lemon/bits/vector_map.h lemon/random.h /usr/include/c++/4.7/limits \ + /usr/include/c++/4.7/fstream /usr/include/c++/4.7/bits/codecvt.h \ + /usr/include/c++/4.7/cstdio /usr/include/libio.h \ + /usr/include/_G_config.h /usr/include/x86_64-linux-gnu/bits/stdio_lim.h \ + /usr/include/x86_64-linux-gnu/bits/sys_errlist.h \ + /usr/include/x86_64-linux-gnu/bits/stdio.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/basic_file.h \ + /usr/include/c++/4.7/x86_64-linux-gnu/bits/c++io.h \ + /usr/include/c++/4.7/bits/fstream.tcc lemon/math.h \ + /usr/include/c++/4.7/cmath /usr/include/math.h \ + /usr/include/x86_64-linux-gnu/bits/huge_val.h \ + /usr/include/x86_64-linux-gnu/bits/huge_valf.h \ + /usr/include/x86_64-linux-gnu/bits/huge_vall.h \ + /usr/include/x86_64-linux-gnu/bits/inf.h \ + /usr/include/x86_64-linux-gnu/bits/nan.h \ + /usr/include/x86_64-linux-gnu/bits/mathdef.h \ + /usr/include/x86_64-linux-gnu/bits/mathcalls.h \ + /usr/include/x86_64-linux-gnu/bits/mathinline.h lemon/dim2.h \ + /usr/include/x86_64-linux-gnu/sys/time.h /usr/include/unistd.h \ + /usr/include/x86_64-linux-gnu/bits/posix_opt.h \ + /usr/include/x86_64-linux-gnu/bits/environments.h \ + /usr/include/x86_64-linux-gnu/bits/confname.h /usr/include/getopt.h \ + lemon/bfs.h lemon/bits/path_dump.h lemon/maps.h \ + /usr/include/c++/4.7/functional /usr/include/c++/4.7/map \ + /usr/include/c++/4.7/bits/stl_map.h \ + /usr/include/c++/4.7/bits/stl_multimap.h lemon/path.h \ + lemon/concepts/path.h lemon/counter.h lemon/suurballe.h lemon/bin_heap.h \ + lemon/dijkstra.h lemon/graph_to_eps.h lemon/color.h lemon/bits/bezier.h \ + lemon/lgf_writer.h lemon/arg_parser.h lemon/euler.h lemon/adaptors.h \ + lemon/bits/variant.h lemon/bits/graph_adaptor_extender.h \ + lemon/tolerance.h lemon/connectivity.h lemon/dfs.h \ + lemon/concepts/digraph.h lemon/concepts/graph_components.h \ + lemon/concepts/graph.h /usr/include/c++/4.7/stack \ + /usr/include/c++/4.7/deque /usr/include/c++/4.7/bits/stl_deque.h \ + /usr/include/c++/4.7/bits/deque.tcc \ + /usr/include/c++/4.7/bits/stl_stack.h lemon/kruskal.h lemon/unionfind.h \ + lemon/time_measure.h /usr/include/x86_64-linux-gnu/sys/times.h + +/usr/include/c++/4.7/algorithm: + +/usr/include/c++/4.7/utility: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++config.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/os_defines.h: + +/usr/include/features.h: + +/usr/include/x86_64-linux-gnu/bits/predefs.h: + +/usr/include/x86_64-linux-gnu/sys/cdefs.h: + +/usr/include/x86_64-linux-gnu/bits/wordsize.h: + +/usr/include/x86_64-linux-gnu/gnu/stubs.h: + +/usr/include/x86_64-linux-gnu/gnu/stubs-64.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/cpu_defines.h: + +/usr/include/c++/4.7/bits/stl_relops.h: + +/usr/include/c++/4.7/bits/stl_pair.h: + +/usr/include/c++/4.7/bits/move.h: + +/usr/include/c++/4.7/bits/concept_check.h: + +/usr/include/c++/4.7/bits/stl_algobase.h: + +/usr/include/c++/4.7/bits/functexcept.h: + +/usr/include/c++/4.7/bits/exception_defines.h: + +/usr/include/c++/4.7/bits/cpp_type_traits.h: + +/usr/include/c++/4.7/ext/type_traits.h: + +/usr/include/c++/4.7/ext/numeric_traits.h: + +/usr/include/c++/4.7/bits/stl_iterator_base_types.h: + +/usr/include/c++/4.7/bits/stl_iterator_base_funcs.h: + +/usr/include/c++/4.7/bits/stl_iterator.h: + +/usr/include/c++/4.7/debug/debug.h: + +/usr/include/c++/4.7/bits/stl_algo.h: + +/usr/include/c++/4.7/cstdlib: + +/usr/include/stdlib.h: + +/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stddef.h: + +/usr/include/x86_64-linux-gnu/bits/waitflags.h: + +/usr/include/x86_64-linux-gnu/bits/waitstatus.h: + +/usr/include/endian.h: + +/usr/include/x86_64-linux-gnu/bits/endian.h: + +/usr/include/x86_64-linux-gnu/bits/byteswap.h: + +/usr/include/xlocale.h: + +/usr/include/x86_64-linux-gnu/sys/types.h: + +/usr/include/x86_64-linux-gnu/bits/types.h: + +/usr/include/x86_64-linux-gnu/bits/typesizes.h: + +/usr/include/time.h: + +/usr/include/x86_64-linux-gnu/sys/select.h: + +/usr/include/x86_64-linux-gnu/bits/select.h: + +/usr/include/x86_64-linux-gnu/bits/sigset.h: + +/usr/include/x86_64-linux-gnu/bits/time.h: + +/usr/include/x86_64-linux-gnu/sys/sysmacros.h: + +/usr/include/x86_64-linux-gnu/bits/pthreadtypes.h: + +/usr/include/alloca.h: + +/usr/include/c++/4.7/bits/algorithmfwd.h: + +/usr/include/c++/4.7/bits/stl_heap.h: + +/usr/include/c++/4.7/bits/stl_tempbuf.h: + +/usr/include/c++/4.7/bits/stl_construct.h: + +/usr/include/c++/4.7/new: + +/usr/include/c++/4.7/exception: + +/usr/include/c++/4.7/bits/atomic_lockfree_defines.h: + +/usr/include/c++/4.7/ext/alloc_traits.h: + +/usr/include/c++/4.7/bits/allocator.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++allocator.h: + +/usr/include/c++/4.7/ext/new_allocator.h: + +/usr/include/c++/4.7/set: + +/usr/include/c++/4.7/bits/stl_tree.h: + +/usr/include/c++/4.7/bits/stl_function.h: + +/usr/include/c++/4.7/backward/binders.h: + +/usr/include/c++/4.7/bits/stl_set.h: + +/usr/include/c++/4.7/bits/stl_multiset.h: + +/usr/include/c++/4.7/bits/range_access.h: + +/usr/include/c++/4.7/ctime: + +lemon/list_graph.h: + +lemon/core.h: + +/usr/include/c++/4.7/vector: + +/usr/include/c++/4.7/bits/stl_uninitialized.h: + +/usr/include/c++/4.7/bits/stl_vector.h: + +/usr/include/c++/4.7/bits/stl_bvector.h: + +/usr/include/c++/4.7/bits/vector.tcc: + +lemon/config.h: + +lemon/bits/enable_if.h: + +lemon/bits/traits.h: + +lemon/assert.h: + +lemon/error.h: + +/usr/include/c++/4.7/string: + +/usr/include/c++/4.7/bits/stringfwd.h: + +/usr/include/c++/4.7/bits/char_traits.h: + +/usr/include/c++/4.7/bits/postypes.h: + +/usr/include/c++/4.7/cwchar: + +/usr/include/wchar.h: + +/usr/include/stdio.h: + +/usr/lib/gcc/x86_64-linux-gnu/4.7/include/stdarg.h: + +/usr/include/x86_64-linux-gnu/bits/wchar.h: + +/usr/include/c++/4.7/bits/localefwd.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++locale.h: + +/usr/include/c++/4.7/clocale: + +/usr/include/locale.h: + +/usr/include/x86_64-linux-gnu/bits/locale.h: + +/usr/include/c++/4.7/iosfwd: + +/usr/include/c++/4.7/cctype: + +/usr/include/ctype.h: + +/usr/include/c++/4.7/bits/ostream_insert.h: + +/usr/include/c++/4.7/bits/cxxabi_forced.h: + +/usr/include/c++/4.7/bits/basic_string.h: + +/usr/include/c++/4.7/ext/atomicity.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/gthr-default.h: + +/usr/include/pthread.h: + +/usr/include/sched.h: + +/usr/include/x86_64-linux-gnu/bits/sched.h: + +/usr/include/x86_64-linux-gnu/bits/setjmp.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/atomic_word.h: + +/usr/include/c++/4.7/bits/basic_string.tcc: + +/usr/include/c++/4.7/sstream: + +/usr/include/c++/4.7/istream: + +/usr/include/c++/4.7/ios: + +/usr/include/c++/4.7/bits/ios_base.h: + +/usr/include/c++/4.7/bits/locale_classes.h: + +/usr/include/c++/4.7/bits/locale_classes.tcc: + +/usr/include/c++/4.7/streambuf: + +/usr/include/c++/4.7/bits/streambuf.tcc: + +/usr/include/c++/4.7/bits/basic_ios.h: + +/usr/include/c++/4.7/bits/locale_facets.h: + +/usr/include/c++/4.7/cwctype: + +/usr/include/wctype.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_base.h: + +/usr/include/c++/4.7/bits/streambuf_iterator.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/ctype_inline.h: + +/usr/include/c++/4.7/bits/locale_facets.tcc: + +/usr/include/c++/4.7/bits/basic_ios.tcc: + +/usr/include/c++/4.7/ostream: + +/usr/include/c++/4.7/bits/ostream.tcc: + +/usr/include/c++/4.7/bits/istream.tcc: + +/usr/include/c++/4.7/bits/sstream.tcc: + +/usr/include/c++/4.7/iostream: + +/usr/include/c++/4.7/memory: + +/usr/include/c++/4.7/bits/stl_raw_storage_iter.h: + +/usr/include/c++/4.7/backward/auto_ptr.h: + +lemon/bits/graph_extender.h: + +lemon/bits/map_extender.h: + +/usr/include/c++/4.7/iterator: + +/usr/include/c++/4.7/bits/stream_iterator.h: + +lemon/concept_check.h: + +lemon/concepts/maps.h: + +lemon/bits/default_map.h: + +lemon/bits/array_map.h: + +lemon/bits/alteration_notifier.h: + +/usr/include/c++/4.7/list: + +/usr/include/c++/4.7/bits/stl_list.h: + +/usr/include/c++/4.7/bits/list.tcc: + +lemon/bits/vector_map.h: + +lemon/random.h: + +/usr/include/c++/4.7/limits: + +/usr/include/c++/4.7/fstream: + +/usr/include/c++/4.7/bits/codecvt.h: + +/usr/include/c++/4.7/cstdio: + +/usr/include/libio.h: + +/usr/include/_G_config.h: + +/usr/include/x86_64-linux-gnu/bits/stdio_lim.h: + +/usr/include/x86_64-linux-gnu/bits/sys_errlist.h: + +/usr/include/x86_64-linux-gnu/bits/stdio.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/basic_file.h: + +/usr/include/c++/4.7/x86_64-linux-gnu/bits/c++io.h: + +/usr/include/c++/4.7/bits/fstream.tcc: + +lemon/math.h: + +/usr/include/c++/4.7/cmath: + +/usr/include/math.h: + +/usr/include/x86_64-linux-gnu/bits/huge_val.h: + +/usr/include/x86_64-linux-gnu/bits/huge_valf.h: + +/usr/include/x86_64-linux-gnu/bits/huge_vall.h: + +/usr/include/x86_64-linux-gnu/bits/inf.h: + +/usr/include/x86_64-linux-gnu/bits/nan.h: + +/usr/include/x86_64-linux-gnu/bits/mathdef.h: + +/usr/include/x86_64-linux-gnu/bits/mathcalls.h: + +/usr/include/x86_64-linux-gnu/bits/mathinline.h: + +lemon/dim2.h: + +/usr/include/x86_64-linux-gnu/sys/time.h: + +/usr/include/unistd.h: + +/usr/include/x86_64-linux-gnu/bits/posix_opt.h: + +/usr/include/x86_64-linux-gnu/bits/environments.h: + +/usr/include/x86_64-linux-gnu/bits/confname.h: + +/usr/include/getopt.h: + +lemon/bfs.h: + +lemon/bits/path_dump.h: + +lemon/maps.h: + +/usr/include/c++/4.7/functional: + +/usr/include/c++/4.7/map: + +/usr/include/c++/4.7/bits/stl_map.h: + +/usr/include/c++/4.7/bits/stl_multimap.h: + +lemon/path.h: + +lemon/concepts/path.h: + +lemon/counter.h: + +lemon/suurballe.h: + +lemon/bin_heap.h: + +lemon/dijkstra.h: + +lemon/graph_to_eps.h: + +lemon/color.h: + +lemon/bits/bezier.h: + +lemon/lgf_writer.h: + +lemon/arg_parser.h: + +lemon/euler.h: + +lemon/adaptors.h: + +lemon/bits/variant.h: + +lemon/bits/graph_adaptor_extender.h: + +lemon/tolerance.h: + +lemon/connectivity.h: + +lemon/dfs.h: + +lemon/concepts/digraph.h: + +lemon/concepts/graph_components.h: + +lemon/concepts/graph.h: + +/usr/include/c++/4.7/stack: + +/usr/include/c++/4.7/deque: + +/usr/include/c++/4.7/bits/stl_deque.h: + +/usr/include/c++/4.7/bits/deque.tcc: + +/usr/include/c++/4.7/bits/stl_stack.h: + +lemon/kruskal.h: + +lemon/unionfind.h: + +lemon/time_measure.h: + +/usr/include/x86_64-linux-gnu/sys/times.h: diff --git a/lemon/tools/.dirstamp b/lemon/tools/.dirstamp new file mode 100644 index 0000000..e69de29 --- /dev/null +++ b/lemon/tools/.dirstamp diff --git a/lemon/tools/CMakeLists.txt b/lemon/tools/CMakeLists.txt new file mode 100644 index 0000000..64b7df7 --- /dev/null +++ b/lemon/tools/CMakeLists.txt @@ -0,0 +1,31 @@ +INCLUDE_DIRECTORIES( + ${PROJECT_SOURCE_DIR} + ${PROJECT_BINARY_DIR} +) + +LINK_DIRECTORIES( + ${PROJECT_BINARY_DIR}/lemon +) + +ADD_EXECUTABLE(lgf-gen lgf-gen.cc) +TARGET_LINK_LIBRARIES(lgf-gen lemon) + +ADD_EXECUTABLE(dimacs-to-lgf dimacs-to-lgf.cc) +TARGET_LINK_LIBRARIES(dimacs-to-lgf lemon) + +ADD_EXECUTABLE(dimacs-solver dimacs-solver.cc) +TARGET_LINK_LIBRARIES(dimacs-solver lemon) + +INSTALL( + TARGETS lgf-gen dimacs-to-lgf dimacs-solver + RUNTIME DESTINATION bin + COMPONENT bin +) + +IF(NOT WIN32) + INSTALL( + PROGRAMS ${CMAKE_CURRENT_SOURCE_DIR}/lemon-0.x-to-1.x.sh + DESTINATION bin + COMPONENT bin + ) +ENDIF() diff --git a/lemon/tools/Makefile.am b/lemon/tools/Makefile.am new file mode 100644 index 0000000..9bcca89 --- /dev/null +++ b/lemon/tools/Makefile.am @@ -0,0 +1,17 @@ +EXTRA_DIST += \ + tools/CMakeLists.txt + +if WANT_TOOLS + +bin_PROGRAMS += \ + tools/dimacs-solver \ + tools/dimacs-to-lgf \ + tools/lgf-gen + +dist_bin_SCRIPTS += tools/lemon-0.x-to-1.x.sh + +endif WANT_TOOLS + +tools_dimacs_solver_SOURCES = tools/dimacs-solver.cc +tools_dimacs_to_lgf_SOURCES = tools/dimacs-to-lgf.cc +tools_lgf_gen_SOURCES = tools/lgf-gen.cc diff --git a/lemon/tools/dimacs-solver.cc b/lemon/tools/dimacs-solver.cc new file mode 100644 index 0000000..dc99cae --- /dev/null +++ b/lemon/tools/dimacs-solver.cc @@ -0,0 +1,280 @@ +/* -*- mode: C++; indent-tabs-mode: nil; -*- + * + * This file is a part of LEMON, a generic C++ optimization library. + * + * Copyright (C) 2003-2010 + * 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. + * + */ + +///\ingroup tools +///\file +///\brief DIMACS problem solver. +/// +/// This program solves various problems given in DIMACS format. +/// +/// See +/// \code +/// dimacs-solver --help +/// \endcode +/// for more info on usage. + +#include <iostream> +#include <fstream> +#include <cstring> + +#include <lemon/smart_graph.h> +#include <lemon/dimacs.h> +#include <lemon/lgf_writer.h> +#include <lemon/time_measure.h> + +#include <lemon/arg_parser.h> +#include <lemon/error.h> + +#include <lemon/dijkstra.h> +#include <lemon/preflow.h> +#include <lemon/matching.h> +#include <lemon/network_simplex.h> + +using namespace lemon; +typedef SmartDigraph Digraph; +DIGRAPH_TYPEDEFS(Digraph); +typedef SmartGraph Graph; + +template<class Value> +void solve_sp(ArgParser &ap, std::istream &is, std::ostream &, + DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Digraph g; + Node s; + Digraph::ArcMap<Value> len(g); + Timer t; + t.restart(); + readDimacsSp(is, g, len, s, desc); + if(report) std::cerr << "Read the file: " << t << '\n'; + t.restart(); + Dijkstra<Digraph, Digraph::ArcMap<Value> > dij(g,len); + if(report) std::cerr << "Setup Dijkstra class: " << t << '\n'; + t.restart(); + dij.run(s); + if(report) std::cerr << "Run Dijkstra: " << t << '\n'; +} + +template<class Value> +void solve_max(ArgParser &ap, std::istream &is, std::ostream &, + Value infty, DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Digraph g; + Node s,t; + Digraph::ArcMap<Value> cap(g); + Timer ti; + ti.restart(); + readDimacsMax(is, g, cap, s, t, infty, desc); + if(report) std::cerr << "Read the file: " << ti << '\n'; + ti.restart(); + Preflow<Digraph, Digraph::ArcMap<Value> > pre(g,cap,s,t); + if(report) std::cerr << "Setup Preflow class: " << ti << '\n'; + ti.restart(); + pre.run(); + if(report) std::cerr << "Run Preflow: " << ti << '\n'; + if(report) std::cerr << "\nMax flow value: " << pre.flowValue() << '\n'; +} + +template<class Value, class LargeValue> +void solve_min(ArgParser &ap, std::istream &is, std::ostream &, + Value infty, DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Digraph g; + Digraph::ArcMap<Value> lower(g), cap(g), cost(g); + Digraph::NodeMap<Value> sup(g); + Timer ti; + + ti.restart(); + readDimacsMin(is, g, lower, cap, cost, sup, infty, desc); + ti.stop(); + Value sum_sup = 0; + for (Digraph::NodeIt n(g); n != INVALID; ++n) { + sum_sup += sup[n]; + } + if (report) { + std::cerr << "Sum of supply values: " << sum_sup << "\n"; + if (sum_sup <= 0) + std::cerr << "GEQ supply contraints are used for NetworkSimplex\n\n"; + else + std::cerr << "LEQ supply contraints are used for NetworkSimplex\n\n"; + } + if (report) std::cerr << "Read the file: " << ti << '\n'; + + ti.restart(); + NetworkSimplex<Digraph, Value> ns(g); + ns.lowerMap(lower).upperMap(cap).costMap(cost).supplyMap(sup); + if (sum_sup > 0) ns.supplyType(ns.LEQ); + if (report) std::cerr << "Setup NetworkSimplex class: " << ti << '\n'; + ti.restart(); + bool res = ns.run(); + if (report) { + std::cerr << "Run NetworkSimplex: " << ti << "\n\n"; + std::cerr << "Feasible flow: " << (res ? "found" : "not found") << '\n'; + if (res) std::cerr << "Min flow cost: " + << ns.template totalCost<LargeValue>() << '\n'; + } +} + +void solve_mat(ArgParser &ap, std::istream &is, std::ostream &, + DimacsDescriptor &desc) +{ + bool report = !ap.given("q"); + Graph g; + Timer ti; + ti.restart(); + readDimacsMat(is, g, desc); + if(report) std::cerr << "Read the file: " << ti << '\n'; + ti.restart(); + MaxMatching<Graph> mat(g); + if(report) std::cerr << "Setup MaxMatching class: " << ti << '\n'; + ti.restart(); + mat.run(); + if(report) std::cerr << "Run MaxMatching: " << ti << '\n'; + if(report) std::cerr << "\nCardinality of max matching: " + << mat.matchingSize() << '\n'; +} + + +template<class Value, class LargeValue> +void solve(ArgParser &ap, std::istream &is, std::ostream &os, + DimacsDescriptor &desc) +{ + std::stringstream iss(static_cast<std::string>(ap["infcap"])); + Value infty; + iss >> infty; + if(iss.fail()) + { + std::cerr << "Cannot interpret '" + << static_cast<std::string>(ap["infcap"]) << "' as infinite" + << std::endl; + exit(1); + } + + switch(desc.type) + { + case DimacsDescriptor::MIN: + solve_min<Value, LargeValue>(ap,is,os,infty,desc); + break; + case DimacsDescriptor::MAX: + solve_max<Value>(ap,is,os,infty,desc); + break; + case DimacsDescriptor::SP: + solve_sp<Value>(ap,is,os,desc); + break; + case DimacsDescriptor::MAT: + solve_mat(ap,is,os,desc); + break; + default: + break; + } +} + +int main(int argc, const char *argv[]) { + typedef SmartDigraph Digraph; + + typedef Digraph::Arc Arc; + + std::string inputName; + std::string outputName; + + ArgParser ap(argc, argv); + ap.other("[INFILE [OUTFILE]]", + "If either the INFILE or OUTFILE file is missing the standard\n" + " input/output will be used instead.") + .boolOption("q", "Do not print any report") + .boolOption("int","Use 'int' for capacities, costs etc. (default)") + .optionGroup("datatype","int") +#ifdef LEMON_HAVE_LONG_LONG + .boolOption("long","Use 'long long' for capacities, costs etc.") + .optionGroup("datatype","long") +#endif + .boolOption("double","Use 'double' for capacities, costs etc.") + .optionGroup("datatype","double") + .boolOption("ldouble","Use 'long double' for capacities, costs etc.") + .optionGroup("datatype","ldouble") + .onlyOneGroup("datatype") + .stringOption("infcap","Value used for 'very high' capacities","0") + .run(); + + std::ifstream input; + std::ofstream output; + + switch(ap.files().size()) + { + case 2: + output.open(ap.files()[1].c_str()); + if (!output) { + throw IoError("Cannot open the file for writing", ap.files()[1]); + } + case 1: + input.open(ap.files()[0].c_str()); + if (!input) { + throw IoError("File cannot be found", ap.files()[0]); + } + case 0: + break; + default: + std::cerr << ap.commandName() << ": too many arguments\n"; + return 1; + } + std::istream& is = (ap.files().size()<1 ? std::cin : input); + std::ostream& os = (ap.files().size()<2 ? std::cout : output); + + DimacsDescriptor desc = dimacsType(is); + + if(!ap.given("q")) + { + std::cout << "Problem type: "; + switch(desc.type) + { + case DimacsDescriptor::MIN: + std::cout << "min"; + break; + case DimacsDescriptor::MAX: + std::cout << "max"; + break; + case DimacsDescriptor::SP: + std::cout << "sp"; + case DimacsDescriptor::MAT: + std::cout << "mat"; + break; + default: + exit(1); + break; + } + std::cout << "\nNum of nodes: " << desc.nodeNum; + std::cout << "\nNum of arcs: " << desc.edgeNum; + std::cout << "\n\n"; + } + + if(ap.given("double")) + solve<double, double>(ap,is,os,desc); + else if(ap.given("ldouble")) + solve<long double, long double>(ap,is,os,desc); +#ifdef LEMON_HAVE_LONG_LONG + else if(ap.given("long")) + solve<long long, long long>(ap,is,os,desc); + else solve<int, long long>(ap,is,os,desc); +#else + else solve<int, long>(ap,is,os,desc); +#endif + + return 0; +} diff --git a/lemon/tools/dimacs-to-lgf.cc b/lemon/tools/dimacs-to-lgf.cc new file mode 100644 index 0000000..3968645 --- /dev/null +++ b/lemon/tools/dimacs-to-lgf.cc @@ -0,0 +1,148 @@ +/* -*- 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. + * + */ + +///\ingroup tools +///\file +///\brief DIMACS to LGF converter. +/// +/// This program converts various DIMACS formats to the LEMON Digraph Format +/// (LGF). +/// +/// See +/// \code +/// dimacs-to-lgf --help +/// \endcode +/// for more info on the usage. + +#include <iostream> +#include <fstream> +#include <cstring> + +#include <lemon/smart_graph.h> +#include <lemon/dimacs.h> +#include <lemon/lgf_writer.h> + +#include <lemon/arg_parser.h> +#include <lemon/error.h> + +using namespace std; +using namespace lemon; + + +int main(int argc, const char *argv[]) { + typedef SmartDigraph Digraph; + + typedef Digraph::Arc Arc; + typedef Digraph::Node Node; + typedef Digraph::ArcIt ArcIt; + typedef Digraph::NodeIt NodeIt; + typedef Digraph::ArcMap<double> DoubleArcMap; + typedef Digraph::NodeMap<double> DoubleNodeMap; + + std::string inputName; + std::string outputName; + + ArgParser ap(argc, argv); + ap.other("[INFILE [OUTFILE]]", + "If either the INFILE or OUTFILE file is missing the standard\n" + " input/output will be used instead.") + .run(); + + ifstream input; + ofstream output; + + switch(ap.files().size()) + { + case 2: + output.open(ap.files()[1].c_str()); + if (!output) { + throw IoError("Cannot open the file for writing", ap.files()[1]); + } + case 1: + input.open(ap.files()[0].c_str()); + if (!input) { + throw IoError("File cannot be found", ap.files()[0]); + } + case 0: + break; + default: + cerr << ap.commandName() << ": too many arguments\n"; + return 1; + } + istream& is = (ap.files().size()<1 ? cin : input); + ostream& os = (ap.files().size()<2 ? cout : output); + + DimacsDescriptor desc = dimacsType(is); + switch(desc.type) + { + case DimacsDescriptor::MIN: + { + Digraph digraph; + DoubleArcMap lower(digraph), capacity(digraph), cost(digraph); + DoubleNodeMap supply(digraph); + readDimacsMin(is, digraph, lower, capacity, cost, supply, 0, desc); + DigraphWriter<Digraph>(digraph, os). + nodeMap("supply", supply). + arcMap("lower", lower). + arcMap("capacity", capacity). + arcMap("cost", cost). + attribute("problem","min"). + run(); + } + break; + case DimacsDescriptor::MAX: + { + Digraph digraph; + Node s, t; + DoubleArcMap capacity(digraph); + readDimacsMax(is, digraph, capacity, s, t, 0, desc); + DigraphWriter<Digraph>(digraph, os). + arcMap("capacity", capacity). + node("source", s). + node("target", t). + attribute("problem","max"). + run(); + } + break; + case DimacsDescriptor::SP: + { + Digraph digraph; + Node s; + DoubleArcMap capacity(digraph); + readDimacsSp(is, digraph, capacity, s, desc); + DigraphWriter<Digraph>(digraph, os). + arcMap("capacity", capacity). + node("source", s). + attribute("problem","sp"). + run(); + } + break; + case DimacsDescriptor::MAT: + { + Digraph digraph; + readDimacsMat(is, digraph,desc); + DigraphWriter<Digraph>(digraph, os). + attribute("problem","mat"). + run(); + } + break; + default: + break; + } + return 0; +} diff --git a/lemon/tools/lemon-0.x-to-1.x.sh b/lemon/tools/lemon-0.x-to-1.x.sh new file mode 100755 index 0000000..1dac1be --- /dev/null +++ b/lemon/tools/lemon-0.x-to-1.x.sh @@ -0,0 +1,134 @@ +#!/bin/bash + +set -e + +if [ $# -eq 0 -o x$1 = "x-h" -o x$1 = "x-help" -o x$1 = "x--help" ]; then + echo "Usage:" + echo " $0 source-file(s)" + exit +fi + +for i in $@ +do + echo Update $i... + TMP=`mktemp` + sed -e "s/\<undirected graph\>/_gr_aph_label_/g"\ + -e "s/\<undirected graphs\>/_gr_aph_label_s/g"\ + -e "s/\<undirected edge\>/_ed_ge_label_/g"\ + -e "s/\<undirected edges\>/_ed_ge_label_s/g"\ + -e "s/\<directed graph\>/_digr_aph_label_/g"\ + -e "s/\<directed graphs\>/_digr_aph_label_s/g"\ + -e "s/\<directed edge\>/_ar_c_label_/g"\ + -e "s/\<directed edges\>/_ar_c_label_s/g"\ + -e "s/UGraph/_Gr_aph_label_/g"\ + -e "s/u[Gg]raph/_gr_aph_label_/g"\ + -e "s/Graph\>/_Digr_aph_label_/g"\ + -e "s/\<graph\>/_digr_aph_label_/g"\ + -e "s/Graphs\>/_Digr_aph_label_s/g"\ + -e "s/\<graphs\>/_digr_aph_label_s/g"\ + -e "s/\([Gg]\)raph\([a-z]\)/_\1r_aph_label_\2/g"\ + -e "s/\([a-z_]\)graph/\1_gr_aph_label_/g"\ + -e "s/Graph/_Digr_aph_label_/g"\ + -e "s/graph/_digr_aph_label_/g"\ + -e "s/UEdge/_Ed_ge_label_/g"\ + -e "s/u[Ee]dge/_ed_ge_label_/g"\ + -e "s/IncEdgeIt/_In_cEd_geIt_label_/g"\ + -e "s/Edge\>/_Ar_c_label_/g"\ + -e "s/\<edge\>/_ar_c_label_/g"\ + -e "s/_edge\>/__ar_c_label_/g"\ + -e "s/Edges\>/_Ar_c_label_s/g"\ + -e "s/\<edges\>/_ar_c_label_s/g"\ + -e "s/_edges\>/__ar_c_label_s/g"\ + -e "s/\([Ee]\)dge\([a-z]\)/_\1d_ge_label_\2/g"\ + -e "s/\([a-z]\)edge/\1_ed_ge_label_/g"\ + -e "s/Edge/_Ar_c_label_/g"\ + -e "s/edge/_ar_c_label_/g"\ + -e "s/A[Nn]ode/_Re_d_label_/g"\ + -e "s/B[Nn]ode/_Blu_e_label_/g"\ + -e "s/A-[Nn]ode/_Re_d_label_/g"\ + -e "s/B-[Nn]ode/_Blu_e_label_/g"\ + -e "s/a[Nn]ode/_re_d_label_/g"\ + -e "s/b[Nn]ode/_blu_e_label_/g"\ + -e "s/\<UGRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__GR_APH_TY_PEDE_FS_label_\1/g"\ + -e "s/\<GRAPH_TYPEDEFS\([ \t]*([ \t]*\)typename[ \t]/TEMPLATE__DIGR_APH_TY_PEDE_FS_label_\1/g"\ + -e "s/\<UGRAPH_TYPEDEFS\>/_GR_APH_TY_PEDE_FS_label_/g"\ + -e "s/\<GRAPH_TYPEDEFS\>/_DIGR_APH_TY_PEDE_FS_label_/g"\ + -e "s/_Digr_aph_label_/Digraph/g"\ + -e "s/_digr_aph_label_/digraph/g"\ + -e "s/_Gr_aph_label_/Graph/g"\ + -e "s/_gr_aph_label_/graph/g"\ + -e "s/_Ar_c_label_/Arc/g"\ + -e "s/_ar_c_label_/arc/g"\ + -e "s/_Ed_ge_label_/Edge/g"\ + -e "s/_ed_ge_label_/edge/g"\ + -e "s/_In_cEd_geIt_label_/IncEdgeIt/g"\ + -e "s/_Re_d_label_/Red/g"\ + -e "s/_Blu_e_label_/Blue/g"\ + -e "s/_re_d_label_/red/g"\ + -e "s/_blu_e_label_/blue/g"\ + -e "s/_GR_APH_TY_PEDE_FS_label_/GRAPH_TYPEDEFS/g"\ + -e "s/_DIGR_APH_TY_PEDE_FS_label_/DIGRAPH_TYPEDEFS/g"\ + -e "s/\<digraph_adaptor\.h\>/adaptors.h/g"\ + -e "s/\<digraph_utils\.h\>/core.h/g"\ + -e "s/\<digraph_reader\.h\>/lgf_reader.h/g"\ + -e "s/\<digraph_writer\.h\>/lgf_writer.h/g"\ + -e "s/\<topology\.h\>/connectivity.h/g"\ + -e "s/DigraphToEps/GraphToEps/g"\ + -e "s/digraphToEps/graphToEps/g"\ + -e "s/\<DefPredMap\>/SetPredMap/g"\ + -e "s/\<DefDistMap\>/SetDistMap/g"\ + -e "s/\<DefReachedMap\>/SetReachedMap/g"\ + -e "s/\<DefProcessedMap\>/SetProcessedMap/g"\ + -e "s/\<DefHeap\>/SetHeap/g"\ + -e "s/\<DefStandardHeap\>/SetStandradHeap/g"\ + -e "s/\<DefOperationTraits\>/SetOperationTraits/g"\ + -e "s/\<DefProcessedMapToBeDefaultMap\>/SetStandardProcessedMap/g"\ + -e "s/\<copyGraph\>/graphCopy/g"\ + -e "s/\<copyDigraph\>/digraphCopy/g"\ + -e "s/\<HyperCubeDigraph\>/HypercubeGraph/g"\ + -e "s/\<IntegerMap\>/RangeMap/g"\ + -e "s/\<integerMap\>/rangeMap/g"\ + -e "s/\<\([sS]\)tdMap\>/\1parseMap/g"\ + -e "s/\<\([Ff]\)unctorMap\>/\1unctorToMap/g"\ + -e "s/\<\([Mm]\)apFunctor\>/\1apToFunctor/g"\ + -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\ + -e "s/\<StoreBoolMap\>/LoggerBoolMap/g"\ + -e "s/\<storeBoolMap\>/loggerBoolMap/g"\ + -e "s/\<InvertableMap\>/CrossRefMap/g"\ + -e "s/\<invertableMap\>/crossRefMap/g"\ + -e "s/\<DescriptorMap\>/RangeIdMap/g"\ + -e "s/\<descriptorMap\>/rangeIdMap/g"\ + -e "s/\<BoundingBox\>/Box/g"\ + -e "s/\<readNauty\>/readNautyGraph/g"\ + -e "s/\<RevDigraphAdaptor\>/ReverseDigraph/g"\ + -e "s/\<revDigraphAdaptor\>/reverseDigraph/g"\ + -e "s/\<SubDigraphAdaptor\>/SubDigraph/g"\ + -e "s/\<subDigraphAdaptor\>/subDigraph/g"\ + -e "s/\<SubGraphAdaptor\>/SubGraph/g"\ + -e "s/\<subGraphAdaptor\>/subGraph/g"\ + -e "s/\<NodeSubDigraphAdaptor\>/FilterNodes/g"\ + -e "s/\<nodeSubDigraphAdaptor\>/filterNodes/g"\ + -e "s/\<ArcSubDigraphAdaptor\>/FilterArcs/g"\ + -e "s/\<arcSubDigraphAdaptor\>/filterArcs/g"\ + -e "s/\<UndirDigraphAdaptor\>/Undirector/g"\ + -e "s/\<undirDigraphAdaptor\>/undirector/g"\ + -e "s/\<ResDigraphAdaptor\>/ResidualDigraph/g"\ + -e "s/\<resDigraphAdaptor\>/residualDigraph/g"\ + -e "s/\<SplitDigraphAdaptor\>/SplitNodes/g"\ + -e "s/\<splitDigraphAdaptor\>/splitNodes/g"\ + -e "s/\<SubGraphAdaptor\>/SubGraph/g"\ + -e "s/\<subGraphAdaptor\>/subGraph/g"\ + -e "s/\<NodeSubGraphAdaptor\>/FilterNodes/g"\ + -e "s/\<nodeSubGraphAdaptor\>/filterNodes/g"\ + -e "s/\<ArcSubGraphAdaptor\>/FilterEdges/g"\ + -e "s/\<arcSubGraphAdaptor\>/filterEdges/g"\ + -e "s/\<DirGraphAdaptor\>/Orienter/g"\ + -e "s/\<dirGraphAdaptor\>/orienter/g"\ + -e "s/\<LpCplex\>/CplexLp/g"\ + -e "s/\<MipCplex\>/CplexMip/g"\ + -e "s/\<LpGlpk\>/GlpkLp/g"\ + -e "s/\<MipGlpk\>/GlpkMip/g"\ + -e "s/\<LpSoplex\>/SoplexLp/g"\ + <$i > $TMP + mv $TMP $i +done diff --git a/lemon/tools/lgf-gen.cc b/lemon/tools/lgf-gen.cc new file mode 100644 index 0000000..e8bf7cd --- /dev/null +++ b/lemon/tools/lgf-gen.cc @@ -0,0 +1,834 @@ +/* -*- 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. + * + */ + +/// \ingroup tools +/// \file +/// \brief Special plane graph generator. +/// +/// Graph generator application for various types of plane graphs. +/// +/// See +/// \code +/// lgf-gen --help +/// \endcode +/// for more information on the usage. + +#include <algorithm> +#include <set> +#include <ctime> +#include <lemon/list_graph.h> +#include <lemon/random.h> +#include <lemon/dim2.h> +#include <lemon/bfs.h> +#include <lemon/counter.h> +#include <lemon/suurballe.h> +#include <lemon/graph_to_eps.h> +#include <lemon/lgf_writer.h> +#include <lemon/arg_parser.h> +#include <lemon/euler.h> +#include <lemon/math.h> +#include <lemon/kruskal.h> +#include <lemon/time_measure.h> + +using namespace lemon; + +typedef dim2::Point<double> Point; + +GRAPH_TYPEDEFS(ListGraph); + +bool progress=true; + +int N; +// int girth; + +ListGraph g; + +std::vector<Node> nodes; +ListGraph::NodeMap<Point> coords(g); + + +double totalLen(){ + double tlen=0; + for(EdgeIt e(g);e!=INVALID;++e) + tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare()); + return tlen; +} + +int tsp_impr_num=0; + +const double EPSILON=1e-8; +bool tsp_improve(Node u, Node v) +{ + double luv=std::sqrt((coords[v]-coords[u]).normSquare()); + Node u2=u; + Node v2=v; + do { + Node n; + for(IncEdgeIt e(g,v2);(n=g.runningNode(e))==u2;++e) { } + u2=v2; + v2=n; + if(luv+std::sqrt((coords[v2]-coords[u2]).normSquare())-EPSILON> + std::sqrt((coords[u]-coords[u2]).normSquare())+ + std::sqrt((coords[v]-coords[v2]).normSquare())) + { + g.erase(findEdge(g,u,v)); + g.erase(findEdge(g,u2,v2)); + g.addEdge(u2,u); + g.addEdge(v,v2); + tsp_impr_num++; + return true; + } + } while(v2!=u); + return false; +} + +bool tsp_improve(Node u) +{ + for(IncEdgeIt e(g,u);e!=INVALID;++e) + if(tsp_improve(u,g.runningNode(e))) return true; + return false; +} + +void tsp_improve() +{ + bool b; + do { + b=false; + for(NodeIt n(g);n!=INVALID;++n) + if(tsp_improve(n)) b=true; + } while(b); +} + +void tsp() +{ + for(int i=0;i<N;i++) g.addEdge(nodes[i],nodes[(i+1)%N]); + tsp_improve(); +} + +class Line +{ +public: + Point a; + Point b; + Line(Point _a,Point _b) :a(_a),b(_b) {} + Line(Node _a,Node _b) : a(coords[_a]),b(coords[_b]) {} + Line(const Arc &e) : a(coords[g.source(e)]),b(coords[g.target(e)]) {} + Line(const Edge &e) : a(coords[g.u(e)]),b(coords[g.v(e)]) {} +}; + +inline std::ostream& operator<<(std::ostream &os, const Line &l) +{ + os << l.a << "->" << l.b; + return os; +} + +bool cross(Line a, Line b) +{ + Point ao=rot90(a.b-a.a); + Point bo=rot90(b.b-b.a); + return (ao*(b.a-a.a))*(ao*(b.b-a.a))<0 && + (bo*(a.a-b.a))*(bo*(a.b-b.a))<0; +} + +struct Parc +{ + Node a; + Node b; + double len; +}; + +bool pedgeLess(Parc a,Parc b) +{ + return a.len<b.len; +} + +std::vector<Edge> arcs; + +namespace _delaunay_bits { + + struct Part { + int prev, curr, next; + + Part(int p, int c, int n) : prev(p), curr(c), next(n) {} + }; + + inline std::ostream& operator<<(std::ostream& os, const Part& part) { + os << '(' << part.prev << ',' << part.curr << ',' << part.next << ')'; + return os; + } + + inline double circle_point(const Point& p, const Point& q, const Point& r) { + double a = p.x * (q.y - r.y) + q.x * (r.y - p.y) + r.x * (p.y - q.y); + if (a == 0) return std::numeric_limits<double>::quiet_NaN(); + + double d = (p.x * p.x + p.y * p.y) * (q.y - r.y) + + (q.x * q.x + q.y * q.y) * (r.y - p.y) + + (r.x * r.x + r.y * r.y) * (p.y - q.y); + + double e = (p.x * p.x + p.y * p.y) * (q.x - r.x) + + (q.x * q.x + q.y * q.y) * (r.x - p.x) + + (r.x * r.x + r.y * r.y) * (p.x - q.x); + + double f = (p.x * p.x + p.y * p.y) * (q.x * r.y - r.x * q.y) + + (q.x * q.x + q.y * q.y) * (r.x * p.y - p.x * r.y) + + (r.x * r.x + r.y * r.y) * (p.x * q.y - q.x * p.y); + + return d / (2 * a) + std::sqrt((d * d + e * e) / (4 * a * a) + f / a); + } + + inline bool circle_form(const Point& p, const Point& q, const Point& r) { + return rot90(q - p) * (r - q) < 0.0; + } + + inline double intersection(const Point& p, const Point& q, double sx) { + const double epsilon = 1e-8; + + if (p.x == q.x) return (p.y + q.y) / 2.0; + + if (sx < p.x + epsilon) return p.y; + if (sx < q.x + epsilon) return q.y; + + double a = q.x - p.x; + double b = (q.x - sx) * p.y - (p.x - sx) * q.y; + double d = (q.x - sx) * (p.x - sx) * (p - q).normSquare(); + return (b - std::sqrt(d)) / a; + } + + struct YLess { + + + YLess(const std::vector<Point>& points, double& sweep) + : _points(points), _sweep(sweep) {} + + bool operator()(const Part& l, const Part& r) const { + const double epsilon = 1e-8; + + // std::cerr << l << " vs " << r << std::endl; + double lbx = l.prev != -1 ? + intersection(_points[l.prev], _points[l.curr], _sweep) : + - std::numeric_limits<double>::infinity(); + double rbx = r.prev != -1 ? + intersection(_points[r.prev], _points[r.curr], _sweep) : + - std::numeric_limits<double>::infinity(); + double lex = l.next != -1 ? + intersection(_points[l.curr], _points[l.next], _sweep) : + std::numeric_limits<double>::infinity(); + double rex = r.next != -1 ? + intersection(_points[r.curr], _points[r.next], _sweep) : + std::numeric_limits<double>::infinity(); + + if (lbx > lex) std::swap(lbx, lex); + if (rbx > rex) std::swap(rbx, rex); + + if (lex < epsilon + rex && lbx + epsilon < rex) return true; + if (rex < epsilon + lex && rbx + epsilon < lex) return false; + return lex < rex; + } + + const std::vector<Point>& _points; + double& _sweep; + }; + + struct BeachIt; + + typedef std::multimap<double, BeachIt> SpikeHeap; + + typedef std::multimap<Part, SpikeHeap::iterator, YLess> Beach; + + struct BeachIt { + Beach::iterator it; + + BeachIt(Beach::iterator iter) : it(iter) {} + }; + +} + +inline void delaunay() { + Counter cnt("Number of arcs added: "); + + using namespace _delaunay_bits; + + typedef _delaunay_bits::Part Part; + typedef std::vector<std::pair<double, int> > SiteHeap; + + + std::vector<Point> points; + std::vector<Node> nodes; + + for (NodeIt it(g); it != INVALID; ++it) { + nodes.push_back(it); + points.push_back(coords[it]); + } + + SiteHeap siteheap(points.size()); + + double sweep; + + + for (int i = 0; i < int(siteheap.size()); ++i) { + siteheap[i] = std::make_pair(points[i].x, i); + } + + std::sort(siteheap.begin(), siteheap.end()); + sweep = siteheap.front().first; + + YLess yless(points, sweep); + Beach beach(yless); + + SpikeHeap spikeheap; + + std::set<std::pair<int, int> > arcs; + + int siteindex = 0; + { + SiteHeap front; + + while (siteindex < int(siteheap.size()) && + siteheap[0].first == siteheap[siteindex].first) { + front.push_back(std::make_pair(points[siteheap[siteindex].second].y, + siteheap[siteindex].second)); + ++siteindex; + } + + std::sort(front.begin(), front.end()); + + for (int i = 0; i < int(front.size()); ++i) { + int prev = (i == 0 ? -1 : front[i - 1].second); + int curr = front[i].second; + int next = (i + 1 == int(front.size()) ? -1 : front[i + 1].second); + + beach.insert(std::make_pair(Part(prev, curr, next), + spikeheap.end())); + } + } + + while (siteindex < int(points.size()) || !spikeheap.empty()) { + + SpikeHeap::iterator spit = spikeheap.begin(); + + if (siteindex < int(points.size()) && + (spit == spikeheap.end() || siteheap[siteindex].first < spit->first)) { + int site = siteheap[siteindex].second; + sweep = siteheap[siteindex].first; + + Beach::iterator bit = beach.upper_bound(Part(site, site, site)); + + if (bit->second != spikeheap.end()) { + spikeheap.erase(bit->second); + } + + int prev = bit->first.prev; + int curr = bit->first.curr; + int next = bit->first.next; + + beach.erase(bit); + + SpikeHeap::iterator pit = spikeheap.end(); + if (prev != -1 && + circle_form(points[prev], points[curr], points[site])) { + double x = circle_point(points[prev], points[curr], points[site]); + pit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end()))); + pit->second.it = + beach.insert(std::make_pair(Part(prev, curr, site), pit)); + } else { + beach.insert(std::make_pair(Part(prev, curr, site), pit)); + } + + beach.insert(std::make_pair(Part(curr, site, curr), spikeheap.end())); + + SpikeHeap::iterator nit = spikeheap.end(); + if (next != -1 && + circle_form(points[site], points[curr],points[next])) { + double x = circle_point(points[site], points[curr], points[next]); + nit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end()))); + nit->second.it = + beach.insert(std::make_pair(Part(site, curr, next), nit)); + } else { + beach.insert(std::make_pair(Part(site, curr, next), nit)); + } + + ++siteindex; + } else { + sweep = spit->first; + + Beach::iterator bit = spit->second.it; + + int prev = bit->first.prev; + int curr = bit->first.curr; + int next = bit->first.next; + + { + std::pair<int, int> arc; + + arc = prev < curr ? + std::make_pair(prev, curr) : std::make_pair(curr, prev); + + if (arcs.find(arc) == arcs.end()) { + arcs.insert(arc); + g.addEdge(nodes[prev], nodes[curr]); + ++cnt; + } + + arc = curr < next ? + std::make_pair(curr, next) : std::make_pair(next, curr); + + if (arcs.find(arc) == arcs.end()) { + arcs.insert(arc); + g.addEdge(nodes[curr], nodes[next]); + ++cnt; + } + } + + Beach::iterator pbit = bit; --pbit; + int ppv = pbit->first.prev; + Beach::iterator nbit = bit; ++nbit; + int nnt = nbit->first.next; + + if (bit->second != spikeheap.end()) spikeheap.erase(bit->second); + if (pbit->second != spikeheap.end()) spikeheap.erase(pbit->second); + if (nbit->second != spikeheap.end()) spikeheap.erase(nbit->second); + + beach.erase(nbit); + beach.erase(bit); + beach.erase(pbit); + + SpikeHeap::iterator pit = spikeheap.end(); + if (ppv != -1 && ppv != next && + circle_form(points[ppv], points[prev], points[next])) { + double x = circle_point(points[ppv], points[prev], points[next]); + if (x < sweep) x = sweep; + pit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end()))); + pit->second.it = + beach.insert(std::make_pair(Part(ppv, prev, next), pit)); + } else { + beach.insert(std::make_pair(Part(ppv, prev, next), pit)); + } + + SpikeHeap::iterator nit = spikeheap.end(); + if (nnt != -1 && prev != nnt && + circle_form(points[prev], points[next], points[nnt])) { + double x = circle_point(points[prev], points[next], points[nnt]); + if (x < sweep) x = sweep; + nit = spikeheap.insert(std::make_pair(x, BeachIt(beach.end()))); + nit->second.it = + beach.insert(std::make_pair(Part(prev, next, nnt), nit)); + } else { + beach.insert(std::make_pair(Part(prev, next, nnt), nit)); + } + + } + } + + for (Beach::iterator it = beach.begin(); it != beach.end(); ++it) { + int curr = it->first.curr; + int next = it->first.next; + + if (next == -1) continue; + + std::pair<int, int> arc; + + arc = curr < next ? + std::make_pair(curr, next) : std::make_pair(next, curr); + + if (arcs.find(arc) == arcs.end()) { + arcs.insert(arc); + g.addEdge(nodes[curr], nodes[next]); + ++cnt; + } + } +} + +void sparse(int d) +{ + Counter cnt("Number of arcs removed: "); + Bfs<ListGraph> bfs(g); + for(std::vector<Edge>::reverse_iterator ei=arcs.rbegin(); + ei!=arcs.rend();++ei) + { + Node a=g.u(*ei); + Node b=g.v(*ei); + g.erase(*ei); + bfs.run(a,b); + if(bfs.predArc(b)==INVALID || bfs.dist(b)>d) + g.addEdge(a,b); + else cnt++; + } +} + +void sparse2(int d) +{ + Counter cnt("Number of arcs removed: "); + for(std::vector<Edge>::reverse_iterator ei=arcs.rbegin(); + ei!=arcs.rend();++ei) + { + Node a=g.u(*ei); + Node b=g.v(*ei); + g.erase(*ei); + ConstMap<Arc,int> cegy(1); + Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy); + int k=sur.run(a,b,2); + if(k<2 || sur.totalLength()>d) + g.addEdge(a,b); + else cnt++; +// else std::cout << "Remove arc " << g.id(a) << "-" << g.id(b) << '\n'; + } +} + +void sparseTriangle(int d) +{ + Counter cnt("Number of arcs added: "); + std::vector<Parc> pedges; + for(NodeIt n(g);n!=INVALID;++n) + for(NodeIt m=++(NodeIt(n));m!=INVALID;++m) + { + Parc p; + p.a=n; + p.b=m; + p.len=(coords[m]-coords[n]).normSquare(); + pedges.push_back(p); + } + std::sort(pedges.begin(),pedges.end(),pedgeLess); + for(std::vector<Parc>::iterator pi=pedges.begin();pi!=pedges.end();++pi) + { + Line li(pi->a,pi->b); + EdgeIt e(g); + for(;e!=INVALID && !cross(e,li);++e) ; + Edge ne; + if(e==INVALID) { + ConstMap<Arc,int> cegy(1); + Suurballe<ListGraph,ConstMap<Arc,int> > sur(g,cegy); + int k=sur.run(pi->a,pi->b,2); + if(k<2 || sur.totalLength()>d) + { + ne=g.addEdge(pi->a,pi->b); + arcs.push_back(ne); + cnt++; + } + } + } +} + +template <typename Graph, typename CoordMap> +class LengthSquareMap { +public: + typedef typename Graph::Edge Key; + typedef typename CoordMap::Value::Value Value; + + LengthSquareMap(const Graph& graph, const CoordMap& coords) + : _graph(graph), _coords(coords) {} + + Value operator[](const Key& key) const { + return (_coords[_graph.v(key)] - + _coords[_graph.u(key)]).normSquare(); + } + +private: + + const Graph& _graph; + const CoordMap& _coords; +}; + +void minTree() { + std::vector<Parc> pedges; + Timer T; + std::cout << T.realTime() << "s: Creating delaunay triangulation...\n"; + delaunay(); + std::cout << T.realTime() << "s: Calculating spanning tree...\n"; + LengthSquareMap<ListGraph, ListGraph::NodeMap<Point> > ls(g, coords); + ListGraph::EdgeMap<bool> tree(g); + kruskal(g, ls, tree); + std::cout << T.realTime() << "s: Removing non tree arcs...\n"; + std::vector<Edge> remove; + for (EdgeIt e(g); e != INVALID; ++e) { + if (!tree[e]) remove.push_back(e); + } + for(int i = 0; i < int(remove.size()); ++i) { + g.erase(remove[i]); + } + std::cout << T.realTime() << "s: Done\n"; +} + +void tsp2() +{ + std::cout << "Find a tree..." << std::endl; + + minTree(); + + std::cout << "Total arc length (tree) : " << totalLen() << std::endl; + + std::cout << "Make it Euler..." << std::endl; + + { + std::vector<Node> leafs; + for(NodeIt n(g);n!=INVALID;++n) + if(countIncEdges(g,n)%2==1) leafs.push_back(n); + +// for(unsigned int i=0;i<leafs.size();i+=2) +// g.addArc(leafs[i],leafs[i+1]); + + std::vector<Parc> pedges; + for(unsigned int i=0;i<leafs.size()-1;i++) + for(unsigned int j=i+1;j<leafs.size();j++) + { + Node n=leafs[i]; + Node m=leafs[j]; + Parc p; + p.a=n; + p.b=m; + p.len=(coords[m]-coords[n]).normSquare(); + pedges.push_back(p); + } + std::sort(pedges.begin(),pedges.end(),pedgeLess); + for(unsigned int i=0;i<pedges.size();i++) + if(countIncEdges(g,pedges[i].a)%2 && + countIncEdges(g,pedges[i].b)%2) + g.addEdge(pedges[i].a,pedges[i].b); + } + + for(NodeIt n(g);n!=INVALID;++n) + if(countIncEdges(g,n)%2 || countIncEdges(g,n)==0 ) + std::cout << "GEBASZ!!!" << std::endl; + + for(EdgeIt e(g);e!=INVALID;++e) + if(g.u(e)==g.v(e)) + std::cout << "LOOP GEBASZ!!!" << std::endl; + + std::cout << "Number of arcs : " << countEdges(g) << std::endl; + + std::cout << "Total arc length (euler) : " << totalLen() << std::endl; + + ListGraph::EdgeMap<Arc> enext(g); + { + EulerIt<ListGraph> e(g); + Arc eo=e; + Arc ef=e; +// std::cout << "Tour arc: " << g.id(Edge(e)) << std::endl; + for(++e;e!=INVALID;++e) + { +// std::cout << "Tour arc: " << g.id(Edge(e)) << std::endl; + enext[eo]=e; + eo=e; + } + enext[eo]=ef; + } + + std::cout << "Creating a tour from that..." << std::endl; + + int nnum = countNodes(g); + int ednum = countEdges(g); + + for(Arc p=enext[EdgeIt(g)];ednum>nnum;p=enext[p]) + { +// std::cout << "Checking arc " << g.id(p) << std::endl; + Arc e=enext[p]; + Arc f=enext[e]; + Node n2=g.source(f); + Node n1=g.oppositeNode(n2,e); + Node n3=g.oppositeNode(n2,f); + if(countIncEdges(g,n2)>2) + { +// std::cout << "Remove an Arc" << std::endl; + Arc ff=enext[f]; + g.erase(e); + g.erase(f); + if(n1!=n3) + { + Arc ne=g.direct(g.addEdge(n1,n3),n1); + enext[p]=ne; + enext[ne]=ff; + ednum--; + } + else { + enext[p]=ff; + ednum-=2; + } + } + } + + std::cout << "Total arc length (tour) : " << totalLen() << std::endl; + + std::cout << "2-opt the tour..." << std::endl; + + tsp_improve(); + + std::cout << "Total arc length (2-opt tour) : " << totalLen() << std::endl; +} + + +int main(int argc,const char **argv) +{ + ArgParser ap(argc,argv); + +// bool eps; + bool disc_d, square_d, gauss_d; +// bool tsp_a,two_a,tree_a; + int num_of_cities=1; + double area=1; + N=100; +// girth=10; + std::string ndist("disc"); + ap.refOption("n", "Number of nodes (default is 100)", N) + .intOption("g", "Girth parameter (default is 10)", 10) + .refOption("cities", "Number of cities (default is 1)", num_of_cities) + .refOption("area", "Full relative area of the cities (default is 1)", area) + .refOption("disc", "Nodes are evenly distributed on a unit disc (default)", + disc_d) + .optionGroup("dist", "disc") + .refOption("square", "Nodes are evenly distributed on a unit square", + square_d) + .optionGroup("dist", "square") + .refOption("gauss", "Nodes are located according to a two-dim Gauss " + "distribution", gauss_d) + .optionGroup("dist", "gauss") + .onlyOneGroup("dist") + .boolOption("eps", "Also generate .eps output (<prefix>.eps)") + .boolOption("nonodes", "Draw only the edges in the generated .eps output") + .boolOption("dir", "Directed graph is generated (each edge is replaced by " + "two directed arcs)") + .boolOption("2con", "Create a two connected planar graph") + .optionGroup("alg","2con") + .boolOption("tree", "Create a min. cost spanning tree") + .optionGroup("alg","tree") + .boolOption("tsp", "Create a TSP tour") + .optionGroup("alg","tsp") + .boolOption("tsp2", "Create a TSP tour (tree based)") + .optionGroup("alg","tsp2") + .boolOption("dela", "Delaunay triangulation graph") + .optionGroup("alg","dela") + .onlyOneGroup("alg") + .boolOption("rand", "Use time seed for random number generator") + .optionGroup("rand", "rand") + .intOption("seed", "Random seed", -1) + .optionGroup("rand", "seed") + .onlyOneGroup("rand") + .other("[prefix]","Prefix of the output files. Default is 'lgf-gen-out'") + .run(); + + if (ap["rand"]) { + int seed = int(time(0)); + std::cout << "Random number seed: " << seed << std::endl; + rnd = Random(seed); + } + if (ap.given("seed")) { + int seed = ap["seed"]; + std::cout << "Random number seed: " << seed << std::endl; + rnd = Random(seed); + } + + std::string prefix; + switch(ap.files().size()) + { + case 0: + prefix="lgf-gen-out"; + break; + case 1: + prefix=ap.files()[0]; + break; + default: + std::cerr << "\nAt most one prefix can be given\n\n"; + exit(1); + } + + double sum_sizes=0; + std::vector<double> sizes; + std::vector<double> cum_sizes; + for(int s=0;s<num_of_cities;s++) + { + // sum_sizes+=rnd.exponential(); + double d=rnd(); + sum_sizes+=d; + sizes.push_back(d); + cum_sizes.push_back(sum_sizes); + } + int i=0; + for(int s=0;s<num_of_cities;s++) + { + Point center=(num_of_cities==1?Point(0,0):rnd.disc()); + if(gauss_d) + for(;i<N*(cum_sizes[s]/sum_sizes);i++) { + Node n=g.addNode(); + nodes.push_back(n); + coords[n]=center+rnd.gauss2()*area* + std::sqrt(sizes[s]/sum_sizes); + } + else if(square_d) + for(;i<N*(cum_sizes[s]/sum_sizes);i++) { + Node n=g.addNode(); + nodes.push_back(n); + coords[n]=center+Point(rnd()*2-1,rnd()*2-1)*area* + std::sqrt(sizes[s]/sum_sizes); + } + else if(disc_d || true) + for(;i<N*(cum_sizes[s]/sum_sizes);i++) { + Node n=g.addNode(); + nodes.push_back(n); + coords[n]=center+rnd.disc()*area* + std::sqrt(sizes[s]/sum_sizes); + } + } + +// for (ListGraph::NodeIt n(g); n != INVALID; ++n) { +// std::cerr << coords[n] << std::endl; +// } + + if(ap["tsp"]) { + tsp(); + std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; + } + if(ap["tsp2"]) { + tsp2(); + std::cout << "#2-opt improvements: " << tsp_impr_num << std::endl; + } + else if(ap["2con"]) { + std::cout << "Make triangles\n"; + // triangle(); + sparseTriangle(ap["g"]); + std::cout << "Make it sparser\n"; + sparse2(ap["g"]); + } + else if(ap["tree"]) { + minTree(); + } + else if(ap["dela"]) { + delaunay(); + } + + + std::cout << "Number of nodes : " << countNodes(g) << std::endl; + std::cout << "Number of arcs : " << countEdges(g) << std::endl; + double tlen=0; + for(EdgeIt e(g);e!=INVALID;++e) + tlen+=std::sqrt((coords[g.v(e)]-coords[g.u(e)]).normSquare()); + std::cout << "Total arc length : " << tlen << std::endl; + + if(ap["eps"]) + graphToEps(g,prefix+".eps").scaleToA4(). + scale(600).nodeScale(.005).arcWidthScale(.001).preScale(false). + coords(coords).hideNodes(ap.given("nonodes")).run(); + + if(ap["dir"]) + DigraphWriter<ListGraph>(g,prefix+".lgf"). + nodeMap("coordinates_x",scaleMap(xMap(coords),600)). + nodeMap("coordinates_y",scaleMap(yMap(coords),600)). + run(); + else GraphWriter<ListGraph>(g,prefix+".lgf"). + nodeMap("coordinates_x",scaleMap(xMap(coords),600)). + nodeMap("coordinates_y",scaleMap(yMap(coords),600)). + run(); +} + |