# HG changeset patch # User Alpar Juttner # Date 1240306489 -3600 # Node ID f63e87b9748ef2b2150ead29795b5c914c275fab # Parent a3402913cffe4d170e27dc6fa0a632da40bcf4f3# Parent 2ca0cdb5f366b786af35f7a426cedf3e7268b0cb Merge diff -r a3402913cffe -r f63e87b9748e doc/CMakeLists.txt --- a/doc/CMakeLists.txt Sat Apr 18 21:54:30 2009 +0200 +++ b/doc/CMakeLists.txt Tue Apr 21 10:34:49 2009 +0100 @@ -14,12 +14,18 @@ ADD_CUSTOM_TARGET(html COMMAND rm -rf gen-images COMMAND mkdir gen-images + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps COMMAND rm -rf html COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}) @@ -27,11 +33,18 @@ ADD_CUSTOM_TARGET(html COMMAND if exist gen-images rmdir /s /q gen-images COMMAND mkdir gen-images + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_matching.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_matching.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/bipartite_partitions.png ${CMAKE_CURRENT_SOURCE_DIR}/images/bipartite_partitions.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/connected_components.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/edge_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/edge_biconnected_components.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/grid_graph.png ${CMAKE_CURRENT_SOURCE_DIR}/images/grid_graph.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/node_biconnected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/node_biconnected_components.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_0.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_0.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_1.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_1.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_2.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_2.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_3.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_3.eps COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/nodeshape_4.png ${CMAKE_CURRENT_SOURCE_DIR}/images/nodeshape_4.eps + COMMAND ${GHOSTSCRIPT_EXECUTABLE} -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4 -sDEVICE=pngalpha -r18 -sOutputFile=gen-images/strongly_connected_components.png ${CMAKE_CURRENT_SOURCE_DIR}/images/strongly_connected_components.eps COMMAND if exist html rmdir /s /q html COMMAND ${DOXYGEN_EXECUTABLE} Doxyfile WORKING_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}) diff -r a3402913cffe -r f63e87b9748e doc/Makefile.am --- a/doc/Makefile.am Sat Apr 18 21:54:30 2009 +0200 +++ b/doc/Makefile.am Tue Apr 21 10:34:49 2009 +0100 @@ -21,8 +21,17 @@ nodeshape_3.eps \ nodeshape_4.eps +DOC_EPS_IMAGES27 = \ + bipartite_matching.eps \ + bipartite_partitions.eps \ + connected_components.eps \ + edge_biconnected_components.eps \ + node_biconnected_components.eps \ + strongly_connected_components.eps + DOC_EPS_IMAGES = \ - $(DOC_EPS_IMAGES18) + $(DOC_EPS_IMAGES18) \ + $(DOC_EPS_IMAGES27) DOC_PNG_IMAGES = \ $(DOC_EPS_IMAGES:%.eps=doc/gen-images/%.png) @@ -45,6 +54,17 @@ exit 1; \ fi +$(DOC_EPS_IMAGES27:%.eps=doc/gen-images/%.png): doc/gen-images/%.png: doc/images/%.eps + -mkdir doc/gen-images + if test ${gs_found} = yes; then \ + $(GS_COMMAND) -sDEVICE=pngalpha -r27 -sOutputFile=$@ $<; \ + else \ + echo; \ + echo "Ghostscript not found."; \ + echo; \ + exit 1; \ + fi + html-local: $(DOC_PNG_IMAGES) if test ${doxygen_found} = yes; then \ cd doc; \ diff -r a3402913cffe -r f63e87b9748e doc/groups.dox --- a/doc/groups.dox Sat Apr 18 21:54:30 2009 +0200 +++ b/doc/groups.dox Tue Apr 21 10:34:49 2009 +0100 @@ -407,7 +407,7 @@ */ /** -@defgroup graph_prop Connectivity and Other Graph Properties +@defgroup graph_properties Connectivity and Other Graph Properties @ingroup algs \brief Algorithms for discovering the graph properties diff -r a3402913cffe -r f63e87b9748e doc/images/bipartite_matching.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/images/bipartite_matching.eps Tue Apr 21 10:34:49 2009 +0100 @@ -0,0 +1,586 @@ +%!PS-Adobe-3.0 EPSF-3.0 +%%BoundingBox: 15 18 829 570 +%%HiResBoundingBox: 15.1913 18.4493 828.078 569.438 +%%Creator: Karbon14 EPS Exportfilter 0.5 +%%CreationDate: (04/15/06 15:20:26) +%%For: (Balazs Dezso) () +%%Title: () + +/N {newpath} def +/C {closepath} def +/m {moveto} def +/c {curveto} def +/l {lineto} def +/s {stroke} def +/f {fill} def +/w {setlinewidth} def +/d {setdash} def +/r {setrgbcolor} def +/S {gsave} def +/R {grestore} def + +N +251.402 32.047 m +532.945 293.946 814.484 555.844 814.484 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +749.012 32.047 m +742.465 293.946 735.918 555.844 735.918 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +539.492 32.047 m +637.703 293.946 735.918 555.844 735.918 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +172.832 32.047 m +454.375 293.946 735.918 555.844 735.918 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +107.355 32.047 m +421.637 293.946 735.918 555.844 735.918 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +644.25 555.844 m +696.633 293.946 749.012 32.047 749.012 32.047 c +[] 0 d 0 0 0 r 1.96407 w s + +N +474.016 555.844 m +611.516 293.946 749.012 32.047 749.012 32.047 c +[] 0 d 1 0 0 r 3.92814 w s + +N +683.535 32.047 m +663.894 293.946 644.25 555.844 644.25 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +120.453 555.844 m +401.992 293.946 683.535 32.047 683.535 32.047 c +[] 0 d 0 0 0 r 1.96407 w s + +N +28.7853 555.844 m +356.16 293.946 683.535 32.047 683.535 32.047 c +[] 0 d 1 0 0 r 3.92814 w s + +N +539.492 32.047 m +546.039 293.946 552.586 555.844 552.586 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +316.875 32.047 m +349.613 293.946 382.351 555.844 382.351 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +107.355 32.047 m +244.855 293.946 382.351 555.844 382.351 555.844 c +[] 0 d 0 0 0 r 1.96407 w s + +N +290.687 555.844 m +375.805 293.946 460.922 32.047 460.922 32.047 c +[] 0 d 1 0 0 r 3.92814 w s + +N +120.453 555.844 m +290.687 293.946 460.922 32.047 460.922 32.047 c +[] 0 d 0 0 0 r 1.96407 w s + +N +172.832 32.047 m +146.64 293.946 120.453 555.844 120.453 555.844 c +[] 0 d 1 0 0 r 3.92814 w s + +N +15.6913 555.844 m +15.6913 555.844 l +15.6913 548.614 21.5553 542.75 28.7853 542.75 c +36.0163 542.75 41.8833 548.614 41.8833 555.844 c +41.8833 563.075 36.0163 568.938 28.7853 568.938 c +21.5553 568.938 15.6913 563.075 15.6913 555.844 c +15.6913 555.844 l +C +S 0 0 0 r f R + +N +16.8833 555.844 m +16.8833 555.844 l +16.8833 549.27 22.2113 543.942 28.7853 543.942 c +35.3593 543.942 40.6913 549.27 40.6913 555.844 c +40.6913 562.418 35.3593 567.747 28.7853 567.747 c +22.2113 567.747 16.8833 562.418 16.8833 555.844 c +16.8833 555.844 l +C +S 1 0.5 1 r f R + +N +107.355 555.844 m +107.355 555.844 l +107.355 548.614 113.223 542.75 120.453 542.75 c +127.683 542.75 133.547 548.614 133.547 555.844 c +133.547 563.075 127.683 568.938 120.453 568.938 c +113.223 568.938 107.355 563.075 107.355 555.844 c +107.355 555.844 l +C +S 0 0 0 r f R + +N +108.547 555.844 m +108.547 555.844 l +108.547 549.27 113.879 543.942 120.453 543.942 c +127.027 543.942 132.355 549.27 132.355 555.844 c +132.355 562.418 127.027 567.747 120.453 567.747 c +113.879 567.747 108.547 562.418 108.547 555.844 c +108.547 555.844 l +C +S 1 0 1 r f R + +N +199.019 555.844 m +199.019 555.844 l +199.019 548.614 204.887 542.75 212.117 542.75 c +219.348 542.75 225.211 548.614 225.211 555.844 c +225.211 563.075 219.348 568.938 212.117 568.938 c +204.887 568.938 199.019 563.075 199.019 555.844 c +199.019 555.844 l +C +S 0 0 0 r f R + +N +200.211 555.844 m +200.211 555.844 l +200.211 549.27 205.543 543.942 212.117 543.942 c +218.691 543.942 224.019 549.27 224.019 555.844 c +224.019 562.418 218.691 567.747 212.117 567.747 c +205.543 567.747 200.211 562.418 200.211 555.844 c +200.211 555.844 l +C +S 1 0.5 1 r f R + +N +277.59 555.844 m +277.59 555.844 l +277.59 548.614 283.457 542.75 290.687 542.75 c +297.918 542.75 303.781 548.614 303.781 555.844 c +303.781 563.075 297.918 568.938 290.687 568.938 c +283.457 568.938 277.59 563.075 277.59 555.844 c +277.59 555.844 l +C +S 0 0 0 r f R + +N +278.781 555.844 m +278.781 555.844 l +278.781 549.27 284.113 543.942 290.687 543.942 c +297.262 543.942 302.59 549.27 302.59 555.844 c +302.59 562.418 297.262 567.747 290.687 567.747 c +284.113 567.747 278.781 562.418 278.781 555.844 c +278.781 555.844 l +C +S 1 0 1 r f R + +N +369.258 555.844 m +369.258 555.844 l +369.258 548.614 375.121 542.75 382.351 542.75 c +389.582 542.75 395.445 548.614 395.445 555.844 c +395.445 563.075 389.582 568.938 382.351 568.938 c +375.121 568.938 369.258 563.075 369.258 555.844 c +369.258 555.844 l +C +S 0 0 0 r f R + +N +370.445 555.844 m +370.445 555.844 l +370.445 549.27 375.777 543.942 382.351 543.942 c +388.926 543.942 394.258 549.27 394.258 555.844 c +394.258 562.418 388.926 567.747 382.351 567.747 c +375.777 567.747 370.445 562.418 370.445 555.844 c +370.445 555.844 l +C +S 1 0 1 r f R + +N +460.922 555.844 m +460.922 555.844 l +460.922 548.614 466.785 542.75 474.016 542.75 c +481.246 542.75 487.109 548.614 487.109 555.844 c +487.109 563.075 481.246 568.938 474.016 568.938 c +466.785 568.938 460.922 563.075 460.922 555.844 c +460.922 555.844 l +C +S 0 0 0 r f R + +N +462.113 555.844 m +462.113 555.844 l +462.113 549.27 467.441 543.942 474.016 543.942 c +480.59 543.942 485.922 549.27 485.922 555.844 c +485.922 562.418 480.59 567.747 474.016 567.747 c +467.441 567.747 462.113 562.418 462.113 555.844 c +462.113 555.844 l +C +S 1 0.5 1 r f R + +N +539.492 555.844 m +539.492 555.844 l +539.492 548.614 545.355 542.75 552.586 542.75 c +559.816 542.75 565.68 548.614 565.68 555.844 c +565.68 563.075 559.816 568.938 552.586 568.938 c +545.355 568.938 539.492 563.075 539.492 555.844 c +539.492 555.844 l +C +S 0 0 0 r f R + +N +540.683 555.844 m +540.683 555.844 l +540.683 549.27 546.012 543.942 552.586 543.942 c +559.16 543.942 564.492 549.27 564.492 555.844 c +564.492 562.418 559.16 567.747 552.586 567.747 c +546.012 567.747 540.683 562.418 540.683 555.844 c +540.683 555.844 l +C +S 1 0 1 r f R + +N +631.156 555.844 m +631.156 555.844 l +631.156 548.614 637.019 542.75 644.25 542.75 c +651.48 542.75 657.348 548.614 657.348 555.844 c +657.348 563.075 651.48 568.938 644.25 568.938 c +637.019 568.938 631.156 563.075 631.156 555.844 c +631.156 555.844 l +C +S 0 0 0 r f R + +N +632.348 555.844 m +632.348 555.844 l +632.348 549.27 637.676 543.942 644.25 543.942 c +650.824 543.942 656.156 549.27 656.156 555.844 c +656.156 562.418 650.824 567.747 644.25 567.747 c +637.676 567.747 632.348 562.418 632.348 555.844 c +632.348 555.844 l +C +S 1 0.5 1 r f R + +N +722.82 555.844 m +722.82 555.844 l +722.82 548.614 728.687 542.75 735.918 542.75 c +743.149 542.75 749.012 548.614 749.012 555.844 c +749.012 563.075 743.149 568.938 735.918 568.938 c +728.687 568.938 722.82 563.075 722.82 555.844 c +722.82 555.844 l +C +S 0 0 0 r f R + +N +724.012 555.844 m +724.012 555.844 l +724.012 549.27 729.344 543.942 735.918 543.942 c +742.492 543.942 747.82 549.27 747.82 555.844 c +747.82 562.418 742.492 567.747 735.918 567.747 c +729.344 567.747 724.012 562.418 724.012 555.844 c +724.012 555.844 l +C +S 1 0 1 r f R + +N +801.391 555.844 m +801.391 555.844 l +801.391 548.614 807.254 542.75 814.484 542.75 c +821.715 542.75 827.578 548.614 827.578 555.844 c +827.578 563.075 821.715 568.938 814.484 568.938 c +807.254 568.938 801.391 563.075 801.391 555.844 c +801.391 555.844 l +C +S 0 0 0 r f R + +N +802.582 555.844 m +802.582 555.844 l +802.582 549.27 807.91 543.942 814.484 543.942 c +821.059 543.942 826.387 549.27 826.387 555.844 c +826.387 562.418 821.059 567.747 814.484 567.747 c +807.91 567.747 802.582 562.418 802.582 555.844 c +802.582 555.844 l +C +S 1 0 1 r f R + +N +15.6913 32.047 m +15.6913 32.047 l +15.6913 24.8165 21.5553 18.9493 28.7853 18.9493 c +36.0163 18.9493 41.8833 24.8165 41.8833 32.047 c +41.8833 39.2775 36.0163 45.1407 28.7853 45.1407 c +21.5553 45.1407 15.6913 39.2775 15.6913 32.047 c +15.6913 32.047 l +C +S 0 0 0 r f R + +N +16.8833 32.047 m +16.8833 32.047 l +16.8833 25.4728 22.2113 20.1407 28.7853 20.1407 c +35.3593 20.1407 40.6913 25.4728 40.6913 32.047 c +40.6913 38.6212 35.3593 43.9493 28.7853 43.9493 c +22.2113 43.9493 16.8833 38.6212 16.8833 32.047 c +16.8833 32.047 l +C +S 0.5 0.5 1 r f R + +N +94.2623 32.047 m +94.2623 32.047 l +94.2623 24.8165 100.125 18.9493 107.355 18.9493 c +114.586 18.9493 120.453 24.8165 120.453 32.047 c +120.453 39.2775 114.586 45.1407 107.355 45.1407 c +100.125 45.1407 94.2623 39.2775 94.2623 32.047 c +94.2623 32.047 l +C +S 0 0 0 r f R + +N +95.4533 32.047 m +95.4533 32.047 l +95.4533 25.4728 100.781 20.1407 107.355 20.1407 c +113.93 20.1407 119.262 25.4728 119.262 32.047 c +119.262 38.6212 113.93 43.9493 107.355 43.9493 c +100.781 43.9493 95.4533 38.6212 95.4533 32.047 c +95.4533 32.047 l +C +S 0.5 0.5 1 r f R + +N +159.734 32.047 m +159.734 32.047 l +159.734 24.8165 165.601 18.9493 172.832 18.9493 c +180.062 18.9493 185.926 24.8165 185.926 32.047 c +185.926 39.2775 180.062 45.1407 172.832 45.1407 c +165.601 45.1407 159.734 39.2775 159.734 32.047 c +159.734 32.047 l +C +S 0 0 0 r f R + +N +160.926 32.047 m +160.926 32.047 l +160.926 25.4728 166.258 20.1407 172.832 20.1407 c +179.406 20.1407 184.734 25.4728 184.734 32.047 c +184.734 38.6212 179.406 43.9493 172.832 43.9493 c +166.258 43.9493 160.926 38.6212 160.926 32.047 c +160.926 32.047 l +C +S 0.5 0.5 1 r f R + +N +238.305 32.047 m +238.305 32.047 l +238.305 24.8165 244.172 18.9493 251.402 18.9493 c +258.633 18.9493 264.496 24.8165 264.496 32.047 c +264.496 39.2775 258.633 45.1407 251.402 45.1407 c +244.172 45.1407 238.305 39.2775 238.305 32.047 c +238.305 32.047 l +C +S 0 0 0 r f R + +N +239.496 32.047 m +239.496 32.047 l +239.496 25.4728 244.828 20.1407 251.402 20.1407 c +257.976 20.1407 263.305 25.4728 263.305 32.047 c +263.305 38.6212 257.976 43.9493 251.402 43.9493 c +244.828 43.9493 239.496 38.6212 239.496 32.047 c +239.496 32.047 l +C +S 0.5 0.5 1 r f R + +N +303.781 32.047 m +303.781 32.047 l +303.781 24.8165 309.644 18.9493 316.875 18.9493 c +324.105 18.9493 329.973 24.8165 329.973 32.047 c +329.973 39.2775 324.105 45.1407 316.875 45.1407 c +309.644 45.1407 303.781 39.2775 303.781 32.047 c +303.781 32.047 l +C +S 0 0 0 r f R + +N +304.973 32.047 m +304.973 32.047 l +304.973 25.4728 310.301 20.1407 316.875 20.1407 c +323.449 20.1407 328.781 25.4728 328.781 32.047 c +328.781 38.6212 323.449 43.9493 316.875 43.9493 c +310.301 43.9493 304.973 38.6212 304.973 32.047 c +304.973 32.047 l +C +S 0.5 0.5 1 r f R + +N +382.351 32.047 m +382.351 32.047 l +382.351 24.8165 388.215 18.9493 395.445 18.9493 c +402.676 18.9493 408.543 24.8165 408.543 32.047 c +408.543 39.2775 402.676 45.1407 395.445 45.1407 c +388.215 45.1407 382.351 39.2775 382.351 32.047 c +382.351 32.047 l +C +S 0 0 0 r f R + +N +383.543 32.047 m +383.543 32.047 l +383.543 25.4728 388.871 20.1407 395.445 20.1407 c +402.019 20.1407 407.351 25.4728 407.351 32.047 c +407.351 38.6212 402.019 43.9493 395.445 43.9493 c +388.871 43.9493 383.543 38.6212 383.543 32.047 c +383.543 32.047 l +C +S 0.5 0.5 1 r f R + +N +447.828 32.047 m +447.828 32.047 l +447.828 24.8165 453.691 18.9493 460.922 18.9493 c +468.152 18.9493 474.016 24.8165 474.016 32.047 c +474.016 39.2775 468.152 45.1407 460.922 45.1407 c +453.691 45.1407 447.828 39.2775 447.828 32.047 c +447.828 32.047 l +C +S 0 0 0 r f R + +N +449.016 32.047 m +449.016 32.047 l +449.016 25.4728 454.348 20.1407 460.922 20.1407 c +467.496 20.1407 472.824 25.4728 472.824 32.047 c +472.824 38.6212 467.496 43.9493 460.922 43.9493 c +454.348 43.9493 449.016 38.6212 449.016 32.047 c +449.016 32.047 l +C +S 0.5 0.5 1 r f R + +N +526.394 32.047 m +526.394 32.047 l +526.394 24.8165 532.262 18.9493 539.492 18.9493 c +546.723 18.9493 552.586 24.8165 552.586 32.047 c +552.586 39.2775 546.723 45.1407 539.492 45.1407 c +532.262 45.1407 526.394 39.2775 526.394 32.047 c +526.394 32.047 l +C +S 0 0 0 r f R + +N +527.586 32.047 m +527.586 32.047 l +527.586 25.4728 532.918 20.1407 539.492 20.1407 c +546.066 20.1407 551.394 25.4728 551.394 32.047 c +551.394 38.6212 546.066 43.9493 539.492 43.9493 c +532.918 43.9493 527.586 38.6212 527.586 32.047 c +527.586 32.047 l +C +S 0.5 0.5 1 r f R + +N +591.871 32.047 m +591.871 32.047 l +591.871 24.8165 597.734 18.9493 604.965 18.9493 c +612.195 18.9493 618.062 24.8165 618.062 32.047 c +618.062 39.2775 612.195 45.1407 604.965 45.1407 c +597.734 45.1407 591.871 39.2775 591.871 32.047 c +591.871 32.047 l +C +S 0 0 0 r f R + +N +593.062 32.047 m +593.062 32.047 l +593.062 25.4728 598.39 20.1407 604.965 20.1407 c +611.539 20.1407 616.871 25.4728 616.871 32.047 c +616.871 38.6212 611.539 43.9493 604.965 43.9493 c +598.39 43.9493 593.062 38.6212 593.062 32.047 c +593.062 32.047 l +C +S 0.5 0.5 1 r f R + +N +670.441 32.047 m +670.441 32.047 l +670.441 24.8165 676.305 18.9493 683.535 18.9493 c +690.766 18.9493 696.633 24.8165 696.633 32.047 c +696.633 39.2775 690.766 45.1407 683.535 45.1407 c +676.305 45.1407 670.441 39.2775 670.441 32.047 c +670.441 32.047 l +C +S 0 0 0 r f R + +N +671.633 32.047 m +671.633 32.047 l +671.633 25.4728 676.961 20.1407 683.535 20.1407 c +690.109 20.1407 695.441 25.4728 695.441 32.047 c +695.441 38.6212 690.109 43.9493 683.535 43.9493 c +676.961 43.9493 671.633 38.6212 671.633 32.047 c +671.633 32.047 l +C +S 0 0 1 r f R + +N +735.918 32.047 m +735.918 32.047 l +735.918 24.8165 741.781 18.9493 749.012 18.9493 c +756.242 18.9493 762.106 24.8165 762.106 32.047 c +762.106 39.2775 756.242 45.1407 749.012 45.1407 c +741.781 45.1407 735.918 39.2775 735.918 32.047 c +735.918 32.047 l +C +S 0 0 0 r f R + +N +737.105 32.047 m +737.105 32.047 l +737.105 25.4728 742.437 20.1407 749.012 20.1407 c +755.586 20.1407 760.914 25.4728 760.914 32.047 c +760.914 38.6212 755.586 43.9493 749.012 43.9493 c +742.437 43.9493 737.105 38.6212 737.105 32.047 c +737.105 32.047 l +C +S 0 0 1 r f R + +N +801.391 32.047 m +801.391 32.047 l +801.391 24.8165 807.254 18.9493 814.484 18.9493 c +821.715 18.9493 827.578 24.8165 827.578 32.047 c +827.578 39.2775 821.715 45.1407 814.484 45.1407 c +807.254 45.1407 801.391 39.2775 801.391 32.047 c +801.391 32.047 l +C +S 0 0 0 r f R + +N +802.582 32.047 m +802.582 32.047 l +802.582 25.4728 807.91 20.1407 814.484 20.1407 c +821.059 20.1407 826.387 25.4728 826.387 32.047 c +826.387 38.6212 821.059 43.9493 814.484 43.9493 c +807.91 43.9493 802.582 38.6212 802.582 32.047 c +802.582 32.047 l +C +S 0.5 0.5 1 r f R + +%%EOF diff -r a3402913cffe -r f63e87b9748e doc/images/bipartite_partitions.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/images/bipartite_partitions.eps Tue Apr 21 10:34:49 2009 +0100 @@ -0,0 +1,114 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Tue Nov 15 16:51:43 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +71.6378 15 translate +0.389093 dup scale +90 rotate +1197.47 -613.138 translate +%Edges: +gsave +513.857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb +513.857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb +393.468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb +393.468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb +393.468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb +869.153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb +869.153 52.8539 753.168 -66.0676 637.183 -184.989 0 0 0 2 lb +-82.2171 593.138 -91.0261 346.487 -99.8351 99.8351 0 0 0 2 lb +-663.61 546.157 -753.168 394.936 -842.726 243.715 0 0 0 2 lb +-663.61 546.157 -574.052 437.513 -484.494 328.869 0 0 0 2 lb +-1077.63 161.498 -960.178 202.606 -842.726 243.715 0 0 0 2 lb +-1077.63 161.498 -968.987 66.0674 -860.344 -29.3633 0 0 0 2 lb +-1177.47 -234.906 -1029.18 -381.722 -880.898 -528.539 0 0 0 2 lb +-1177.47 -234.906 -1018.91 -132.135 -860.344 -29.3633 0 0 0 2 lb +-880.898 -528.539 -744.359 -387.595 -607.82 -246.651 0 0 0 2 lb +-499.175 -499.175 -355.295 -475.685 -211.415 -452.194 0 0 0 2 lb +-499.175 -499.175 -553.498 -372.913 -607.82 -246.651 0 0 0 2 lb +-499.175 -499.175 -386.587 -315.087 -274 -131 0 0 0 2 lb +79.2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb +637.183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb +205.543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb +399.34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb +399.34 88.0898 253.992 211.415 108.644 334.741 0 0 0 2 lb +-842.726 243.715 -471.281 171.775 -99.8351 99.8351 0 0 0 2 lb +-842.726 243.715 -558.363 56.3575 -274 -131 0 0 0 2 lb +-860.344 -29.3633 -734.082 -138.007 -607.82 -246.651 0 0 0 2 lb +-211.415 -452.194 -45.513 -290.696 120.389 -129.198 0 0 0 2 lb +-99.8351 99.8351 4.40445 217.288 108.644 334.741 0 0 0 2 lb +-99.8351 99.8351 -292.165 214.352 -484.494 328.869 0 0 0 2 lb +120.389 -129.198 -76.8055 -130.099 -274 -131 0 0 0 2 lb +grestore +%Nodes: +gsave +-274 -131 20 1 0 0 nc +-607.82 -246.651 20 1 0 0 nc +-484.494 328.869 20 0 0 1 nc +108.644 334.741 20 0 0 1 nc +120.389 -129.198 20 0 0 1 nc +-99.8351 99.8351 20 1 0 0 nc +-211.415 -452.194 20 1 0 0 nc +-860.344 -29.3633 20 0 0 1 nc +-842.726 243.715 20 0 0 1 nc +399.34 88.0898 20 1 0 0 nc +205.543 -322.996 20 1 0 0 nc +637.183 -184.989 20 0 0 1 nc +79.2808 -528.539 20 0 0 1 nc +-499.175 -499.175 20 0 0 1 nc +-880.898 -528.539 20 0 0 1 nc +-1177.47 -234.906 20 1 0 0 nc +-1077.63 161.498 20 1 0 0 nc +-663.61 546.157 20 1 0 0 nc +-82.2171 593.138 20 0 0 1 nc +596.074 302.442 20 0 0 1 nc +869.153 52.8539 20 1 0 0 nc +393.468 566.711 20 1 0 0 nc +513.857 -446.322 20 1 0 0 nc +grestore +grestore +showpage diff -r a3402913cffe -r f63e87b9748e doc/images/connected_components.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/images/connected_components.eps Tue Apr 21 10:34:49 2009 +0100 @@ -0,0 +1,159 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Nov 4 13:47:12 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +71.0944 15 translate +0.434694 dup scale +90 rotate +860.856 -588.349 translate +%Edges: +gsave +574.035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb +694.579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb +280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb +280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb +212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb +286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb +286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb +438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb +438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb +397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb +366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb +271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb +271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb +277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 0 2 lb +-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0 0 2 lb +-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0 2 lb +-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0 2 lb +-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0 2 lb +906.312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb +906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb +986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 0 2 lb +-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0 0 0 2 lb +422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb +422.945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb +422.945 521.129 474.554 276.928 526.164 32.7279 0 0 0 2 lb +-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 0 2 lb +329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 0 2 lb +-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 0 2 lb +762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb +762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb +526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb +730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb +415.393 -289.516 173.71 -318.468 -67.9734 -347.42 0 0 0 2 lb +-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 0 2 lb +-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 0 2 lb +-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 0 2 lb +-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 0 2 lb +-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 0 2 lb +-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 0 2 lb +-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 0 2 lb +-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 0 2 lb +116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 0 2 lb +-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 0 2 lb +-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 0 2 lb +-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 0 2 lb +-180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 0 2 lb +-180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 0 2 lb +-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 0 2 lb +-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 0 2 lb +-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 0 2 lb +670.264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb +670.264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb +588.113 544.499 756.39 476.923 924.667 409.347 0 0 0 2 lb +-689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 0 2 lb +-689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 0 2 lb +grestore +%Nodes: +gsave +-567.302 43.6423 20 0 0 0 nc +-689.204 -237.261 20 0 0 0 nc +924.667 409.347 20 1 0 0 nc +588.113 544.499 20 1 0 0 nc +670.264 274.195 20 1 0 0 nc +-371.2 568.349 20 0 1 0 nc +-132.697 451.748 20 0 1 0 nc +-416.25 345.746 20 0 1 0 nc +-180.397 245.045 20 0 1 0 nc +-13.4452 133.743 20 0 1 0 nc +-262.548 107.243 20 0 1 0 nc +201.208 38.3422 20 0 1 0 nc +116.407 -173.66 20 0 1 0 nc +-26.6953 -19.9585 20 0 1 0 nc +-539.894 -262.64 20 0 0 1 nc +-323.543 -433.964 20 0 0 1 nc +-309.657 -57.9033 20 0 0 1 nc +-67.9734 -347.42 20 0 0 1 nc +415.393 -289.516 20 0 0 1 nc +730.084 -307.139 20 0 0 1 nc +526.164 32.7279 20 0 0 1 nc +762.812 -17.6227 20 0 0 1 nc +-67.9734 319.727 20 0 0 1 nc +329.797 314.692 20 0 0 1 nc +-5.03507 561.41 20 0 0 1 nc +422.945 521.129 20 0 0 1 nc +-470.779 158.605 20 0 0 1 nc +986.873 -115.807 20 0 0 1 nc +906.312 201.403 20 0 0 1 nc +-767.847 113.289 20 0 0 1 nc +-579.033 445.603 20 0 0 1 nc +-840.856 -246.718 20 0 0 1 nc +206.221 -205.967 20 1 1 0 nc +277.311 -252.33 20 1 1 0 nc +271.13 -175.058 20 1 1 0 nc +366.947 -110.15 20 1 1 0 nc +397.855 -196.694 20 1 1 0 nc +438.037 -88.514 20 1 1 0 nc +286.584 -48.3327 20 1 1 0 nc +212.403 -23.6057 20 1 1 0 nc +280.402 10.3938 20 1 1 0 nc +694.579 115.483 20 1 0 0 nc +574.035 177.301 20 1 0 0 nc +grestore +grestore +showpage diff -r a3402913cffe -r f63e87b9748e doc/images/edge_biconnected_components.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/images/edge_biconnected_components.eps Tue Apr 21 10:34:49 2009 +0100 @@ -0,0 +1,159 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Nov 4 13:47:12 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +71.0944 15 translate +0.434694 dup scale +90 rotate +860.856 -588.349 translate +%Edges: +gsave +574.035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb +694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb +280.402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb +280.402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb +212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb +286.584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb +286.584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb +438.037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb +438.037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb +397.855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb +366.947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb +271.13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb +271.13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb +277.311 -252.33 241.766 -229.149 206.221 -205.967 0 0 1 2 lb +-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 1 0 0 2 lb +-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 1 2 lb +-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 1 2 lb +-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 1 2 lb +906.312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb +906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb +986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0 1 2 lb +-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 1 0 0 2 lb +422.945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb +422.945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb +422.945 521.129 474.554 276.928 526.164 32.7279 0 0 1 2 lb +-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0 0 1 2 lb +329.797 314.692 130.912 317.209 -67.9734 319.727 0 0 1 2 lb +-67.9734 319.727 229.095 176.227 526.164 32.7279 0 0 1 2 lb +762.812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb +762.812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb +526.164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb +730.084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb +415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0 0 2 lb +-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0 0 1 2 lb +-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0 0 1 2 lb +-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0 0 1 2 lb +-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0 0 1 2 lb +-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 0 0 1 2 lb +-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 0 0 1 2 lb +-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 0 0 1 2 lb +-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 0 0 1 2 lb +116.407 -173.66 158.808 -67.6589 201.208 38.3422 0 0 1 2 lb +-262.548 107.243 -137.997 120.493 -13.4452 133.743 0 0 1 2 lb +-262.548 107.243 -221.472 176.144 -180.397 245.045 0 0 1 2 lb +-13.4452 133.743 -96.9211 189.394 -180.397 245.045 0 0 1 2 lb +-180.397 245.045 -142.256 345.099 -132.697 451.748 0 0 1 2 lb +-180.397 245.045 -170.838 351.694 -132.697 451.748 0 0 1 2 lb +-416.25 345.746 -274.474 398.747 -132.697 451.748 0 0 1 2 lb +-416.25 345.746 -393.725 457.048 -371.2 568.349 0 0 1 2 lb +-132.697 451.748 -251.948 510.048 -371.2 568.349 0 0 1 2 lb +670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb +670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb +588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 2 lb +-689.204 -237.261 -614.799 -102.648 -567.302 43.6423 0 0 1 2 lb +-689.204 -237.261 -641.707 -90.9706 -567.302 43.6423 0 0 1 2 lb +grestore +%Nodes: +gsave +-567.302 43.6423 20 0 0 0 nc +-689.204 -237.261 20 0 0 0 nc +924.667 409.347 20 0 0 1 nc +588.113 544.499 20 0 0 1 nc +670.264 274.195 20 0 0 1 nc +-371.2 568.349 20 1 1 0 nc +-132.697 451.748 20 1 1 0 nc +-416.25 345.746 20 1 1 0 nc +-180.397 245.045 20 1 1 0 nc +-13.4452 133.743 20 1 1 0 nc +-262.548 107.243 20 1 1 0 nc +201.208 38.3422 20 1 1 0 nc +116.407 -173.66 20 1 1 0 nc +-26.6953 -19.9585 20 1 1 0 nc +-539.894 -262.64 20 0 0.5 0 nc +-323.543 -433.964 20 0 0.5 0 nc +-309.657 -57.9033 20 0 0.5 0 nc +-67.9734 -347.42 20 0 0.5 0 nc +415.393 -289.516 20 0.5 0 0 nc +730.084 -307.139 20 0.5 0 0 nc +526.164 32.7279 20 0.5 0 0 nc +762.812 -17.6227 20 0.5 0 0 nc +-67.9734 319.727 20 0.5 0 0 nc +329.797 314.692 20 0.5 0 0 nc +-5.03507 561.41 20 0.5 0 0 nc +422.945 521.129 20 0.5 0 0 nc +-470.779 158.605 20 0 1 1 nc +986.873 -115.807 20 0.5 0 0 nc +906.312 201.403 20 0.5 0 0 nc +-767.847 113.289 20 0 1 1 nc +-579.033 445.603 20 0 1 1 nc +-840.856 -246.718 20 1 0 1 nc +206.221 -205.967 20 0 0 0.5 nc +277.311 -252.33 20 0 0 0.5 nc +271.13 -175.058 20 0 0 0.5 nc +366.947 -110.15 20 0 0 0.5 nc +397.855 -196.694 20 0 0 0.5 nc +438.037 -88.514 20 0 0 0.5 nc +286.584 -48.3327 20 0 0 0.5 nc +212.403 -23.6057 20 0 0 0.5 nc +280.402 10.3938 20 0 0 0.5 nc +694.579 115.483 20 1 0 0 nc +574.035 177.301 20 0 1 0 nc +grestore +grestore +showpage diff -r a3402913cffe -r f63e87b9748e doc/images/node_biconnected_components.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/images/node_biconnected_components.eps Tue Apr 21 10:34:49 2009 +0100 @@ -0,0 +1,159 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Nov 4 13:47:12 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 1 def +/arrw 0.3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +71.0944 15 translate +0.434694 dup scale +90 rotate +860.856 -588.349 translate +%Edges: +gsave +574.035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb +694.579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb +280.402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb +280.402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb +212.403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb +286.584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb +286.584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb +438.037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb +438.037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb +397.855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb +366.947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb +271.13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb +271.13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb +277.311 -252.33 241.766 -229.149 206.221 -205.967 0.5 1 1 5 lb +-840.856 -246.718 -804.351 -66.7145 -767.847 113.289 0 0.5 0 5 lb +-579.033 445.603 -673.44 279.446 -767.847 113.289 0 0 0.5 5 lb +-579.033 445.603 -524.906 302.104 -470.779 158.605 0 0 0.5 5 lb +-767.847 113.289 -619.313 135.947 -470.779 158.605 0 0 0.5 5 lb +906.312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb +906.312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb +986.873 -115.807 874.842 -66.7148 762.812 -17.6227 0 0.5 0.5 5 lb +-470.779 158.605 -390.218 50.3508 -309.657 -57.9033 0.5 0.5 0 5 lb +422.945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb +422.945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb +422.945 521.129 474.554 276.928 526.164 32.7279 0.5 0 0.5 5 lb +-5.03507 561.41 -36.5042 440.568 -67.9734 319.727 0.5 0 0.5 5 lb +329.797 314.692 130.912 317.209 -67.9734 319.727 0.5 0 0.5 5 lb +-67.9734 319.727 229.095 176.227 526.164 32.7279 0.5 0 0.5 5 lb +762.812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb +762.812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb +526.164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb +730.084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb +415.393 -289.516 173.71 -318.468 -67.9734 -347.42 1 0.5 0.5 5 lb +-67.9734 -347.42 -188.815 -202.662 -309.657 -57.9033 0.5 1 0.5 5 lb +-67.9734 -347.42 -195.758 -390.692 -323.543 -433.964 0.5 1 0.5 5 lb +-309.657 -57.9033 -424.775 -160.272 -539.894 -262.64 0.5 1 0.5 5 lb +-323.543 -433.964 -431.719 -348.302 -539.894 -262.64 0.5 1 0.5 5 lb +-26.6953 -19.9585 44.8558 -96.8093 116.407 -173.66 1 1 0 5 lb +-26.6953 -19.9585 87.2563 9.19185 201.208 38.3422 1 1 0 5 lb +-26.6953 -19.9585 -144.622 43.6422 -262.548 107.243 1 0 1 5 lb +-26.6953 -19.9585 -20.0703 56.8923 -13.4452 133.743 1 0 1 5 lb +116.407 -173.66 158.808 -67.6589 201.208 38.3422 1 1 0 5 lb +-262.548 107.243 -137.997 120.493 -13.4452 133.743 1 0 1 5 lb +-262.548 107.243 -221.472 176.144 -180.397 245.045 1 0 1 5 lb +-13.4452 133.743 -96.9211 189.394 -180.397 245.045 1 0 1 5 lb +-180.397 245.045 -140.307 344.649 -132.697 451.748 0 1 1 5 lb +-180.397 245.045 -172.787 352.144 -132.697 451.748 0 1 1 5 lb +-416.25 345.746 -274.474 398.747 -132.697 451.748 0.5 0 0 5 lb +-416.25 345.746 -393.725 457.048 -371.2 568.349 0.5 0 0 5 lb +-132.697 451.748 -251.948 510.048 -371.2 568.349 0.5 0 0 5 lb +670.264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb +670.264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb +588.113 544.499 756.39 476.923 924.667 409.347 0 0 1 5 lb +-689.204 -237.261 -612.964 -103.444 -567.302 43.6423 0 0 0 5 lb +-689.204 -237.261 -643.542 -90.1744 -567.302 43.6423 0 0 0 5 lb +grestore +%Nodes: +gsave +-567.302 43.6423 20 0 0 1 nc +-689.204 -237.261 20 0 0 1 nc +924.667 409.347 20 0 0 1 nc +588.113 544.499 20 0 0 1 nc +670.264 274.195 20 1 0 0 nc +-371.2 568.349 20 0 0 1 nc +-132.697 451.748 20 1 0 0 nc +-416.25 345.746 20 0 0 1 nc +-180.397 245.045 20 1 0 0 nc +-13.4452 133.743 20 0 0 1 nc +-262.548 107.243 20 0 0 1 nc +201.208 38.3422 20 0 0 1 nc +116.407 -173.66 20 0 0 1 nc +-26.6953 -19.9585 20 1 0 0 nc +-539.894 -262.64 20 0 0 1 nc +-323.543 -433.964 20 0 0 1 nc +-309.657 -57.9033 20 1 0 0 nc +-67.9734 -347.42 20 1 0 0 nc +415.393 -289.516 20 1 0 0 nc +730.084 -307.139 20 0 0 1 nc +526.164 32.7279 20 1 0 0 nc +762.812 -17.6227 20 1 0 0 nc +-67.9734 319.727 20 0 0 1 nc +329.797 314.692 20 0 0 1 nc +-5.03507 561.41 20 0 0 1 nc +422.945 521.129 20 0 0 1 nc +-470.779 158.605 20 1 0 0 nc +986.873 -115.807 20 0 0 1 nc +906.312 201.403 20 0 0 1 nc +-767.847 113.289 20 1 0 0 nc +-579.033 445.603 20 0 0 1 nc +-840.856 -246.718 20 0 0 1 nc +206.221 -205.967 20 0 0 1 nc +277.311 -252.33 20 0 0 1 nc +271.13 -175.058 20 1 0 0 nc +366.947 -110.15 20 1 0 0 nc +397.855 -196.694 20 0 0 1 nc +438.037 -88.514 20 0 0 1 nc +286.584 -48.3327 20 1 0 0 nc +212.403 -23.6057 20 0 0 1 nc +280.402 10.3938 20 0 0 1 nc +694.579 115.483 20 0 0 1 nc +574.035 177.301 20 0 0 1 nc +grestore +grestore +showpage diff -r a3402913cffe -r f63e87b9748e doc/images/strongly_connected_components.eps --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/images/strongly_connected_components.eps Tue Apr 21 10:34:49 2009 +0100 @@ -0,0 +1,180 @@ +%!PS-Adobe-2.0 EPSF-2.0 +%%Creator: LEMON, graphToEps() +%%CreationDate: Fri Nov 4 13:47:12 2005 +%%BoundingBox: 0 0 842 596 +%%EndComments +/lb { setlinewidth setrgbcolor newpath moveto + 4 2 roll 1 index 1 index curveto stroke } bind def +/l { setlinewidth setrgbcolor newpath moveto lineto stroke } bind def +/c { newpath dup 3 index add 2 index moveto 0 360 arc closepath } bind def +/sq { newpath 2 index 1 index add 2 index 2 index add moveto + 2 index 1 index sub 2 index 2 index add lineto + 2 index 1 index sub 2 index 2 index sub lineto + 2 index 1 index add 2 index 2 index sub lineto + closepath pop pop pop} bind def +/di { newpath 2 index 1 index add 2 index moveto + 2 index 2 index 2 index add lineto + 2 index 1 index sub 2 index lineto + 2 index 2 index 2 index sub lineto + closepath pop pop pop} bind def +/nc { 0 0 0 setrgbcolor 5 index 5 index 5 index c fill + setrgbcolor 1.1 div c fill + } bind def +/nsq { 0 0 0 setrgbcolor 5 index 5 index 5 index sq fill + setrgbcolor 1.1 div sq fill + } bind def +/ndi { 0 0 0 setrgbcolor 5 index 5 index 5 index di fill + setrgbcolor 1.1 div di fill + } bind def +/arrl 10 def +/arrw 3 def +/lrl { 2 index mul exch 2 index mul exch rlineto pop} bind def +/arr { setrgbcolor /y1 exch def /x1 exch def /dy exch def /dx exch def + /w exch def /len exch def + newpath x1 dy w 2 div mul add y1 dx w 2 div mul sub moveto + len w sub arrl sub dx dy lrl + arrw dy dx neg lrl + dx arrl w add mul dy w 2 div arrw add mul sub + dy arrl w add mul dx w 2 div arrw add mul add rlineto + dx arrl w add mul neg dy w 2 div arrw add mul sub + dy arrl w add mul neg dx w 2 div arrw add mul add rlineto + arrw dy dx neg lrl + len w sub arrl sub neg dx dy lrl + closepath fill } bind def +/cshow { 2 index 2 index moveto dup stringwidth pop + neg 2 div fosi .35 mul neg rmoveto show pop pop} def + +gsave +90 rotate +0 -842 translate +77.1122 15 translate +0.585745 dup scale +90 rotate +695.963 -397.916 translate +%Edges: +gsave +2 setlinewidth 0 0 1 setrgbcolor newpath +218.178 27.2723 moveto +192.373 -40.1551 188.622 -49.9556 169.228 -100.631 curveto stroke +newpath 164.939 -111.838 moveto 165.492 -99.2013 lineto 172.964 -102.061 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +44.8044 15.5841 moveto +119.293 20.6059 129.775 21.3125 186.25 25.1199 curveto stroke +newpath 198.223 25.927 moveto 186.519 21.1289 lineto 185.981 29.1108 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +218.178 27.2723 moveto +285.395 -87.4449 290.763 -96.6058 348.102 -194.464 curveto stroke +newpath 354.169 -204.818 moveto 344.651 -196.487 lineto 351.554 -192.442 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +157.79 -130.517 moveto +108.71 -67.0521 102.27 -58.7243 64.3804 -9.72954 curveto stroke +newpath 57.0394 -0.236898 moveto 67.5446 -7.28254 lineto 61.2162 -12.1765 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +-105.193 -261.035 moveto +-35.6576 -132.801 -30.5923 -123.459 29.5506 -12.5464 curveto stroke +newpath 35.2708 -1.99743 moveto 33.0669 -14.4531 lineto 26.0343 -10.6397 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-465.576 -42.8564 moveto +-559.078 -25.5413 -569.47 -23.6169 -644.498 -9.72286 curveto stroke +newpath -656.297 -7.5378 moveto -643.77 -5.78973 lineto -645.226 -13.656 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-574.666 -153.893 moveto +-528.842 -107.252 -521.515 -99.794 -488.002 -65.683 curveto stroke +newpath -479.592 -57.123 moveto -485.149 -68.4863 lineto -490.856 -62.8797 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +-490.901 120.777 moveto +-480.122 51.1328 -478.519 40.7713 -470.47 -11.2329 curveto stroke +newpath -468.635 -23.0917 moveto -474.423 -11.8447 lineto -466.517 -10.6212 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-675.963 -3.89604 moveto +-632.116 -68.8235 -626.228 -77.5422 -592.575 -127.374 curveto stroke +newpath -585.859 -137.319 moveto -595.89 -129.612 lineto -589.26 -125.135 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-490.901 120.777 moveto +-435.445 215.844 -430.107 224.995 -384.3 303.522 curveto stroke +newpath -378.253 313.887 moveto -380.845 301.507 lineto -387.755 305.537 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-266.879 114.933 moveto +-367.067 117.547 -377.642 117.822 -458.912 119.943 curveto stroke +newpath -470.908 120.255 moveto -458.807 123.941 lineto -459.016 115.944 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-368.176 331.163 moveto +-322.511 233.685 -318.018 224.095 -280.454 143.911 curveto stroke +newpath -275.364 133.044 moveto -284.076 142.214 lineto -276.832 145.608 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +-266.879 114.933 moveto +-224.004 235.52 -220.448 245.52 -184.094 347.765 curveto stroke +newpath -180.074 359.072 moveto -180.325 346.425 lineto -187.863 349.105 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-251.294 -335.059 moveto +-189.25 -303.624 -179.902 -298.887 -133.738 -275.498 curveto stroke +newpath -123.034 -270.074 moveto -131.93 -279.066 lineto -135.546 -271.93 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-389.604 -136.361 moveto +-327.15 -226.083 -321.098 -234.777 -269.576 -308.795 curveto stroke +newpath -262.72 -318.644 moveto -272.859 -311.081 lineto -266.293 -306.51 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +5.84406 175.322 moveto +-76.0754 267.926 -83.1051 275.873 -152.172 353.948 curveto stroke +newpath -160.122 362.936 moveto -149.176 356.598 lineto -155.168 351.298 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +169.478 311.683 moveto +96.8003 251.119 88.6819 244.353 30.4273 195.808 curveto stroke +newpath 21.2086 188.126 moveto 27.8666 198.881 lineto 32.988 192.735 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +342.851 111.037 moveto +263.766 202.563 256.831 210.589 190.4 287.47 curveto stroke +newpath 182.554 296.55 moveto 193.427 290.085 lineto 187.373 284.855 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +5.84406 175.322 moveto +163.16 145.314 173.605 143.321 311.418 117.033 curveto stroke +newpath 323.205 114.784 moveto 310.668 113.104 lineto 312.167 120.962 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +342.851 111.037 moveto +497.255 2.58683 505.964 -3.53033 643.932 -100.436 curveto stroke +newpath 653.752 -107.334 moveto 641.633 -103.71 lineto 646.231 -97.163 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +364.28 -222.074 moveto +354.298 -66.9063 353.616 -56.2971 344.905 79.1029 curveto stroke +newpath 344.135 91.0781 moveto 348.897 79.3597 lineto 340.914 78.8461 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +670.118 -118.829 moveto +528.037 -166.793 517.967 -170.192 394.599 -211.839 curveto stroke +newpath 383.229 -215.677 moveto 393.32 -208.049 lineto 395.878 -215.629 lineto closepath fill +2 setlinewidth 1 0 0 setrgbcolor newpath +-105.193 -261.035 moveto +118.401 -242.479 129.015 -241.598 332.39 -224.721 curveto stroke +newpath 344.348 -223.728 moveto 332.72 -228.707 lineto 332.059 -220.734 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-105.193 -261.035 moveto +-160.867 -161.176 -166.028 -151.918 -212.336 -68.858 curveto stroke +newpath -218.179 -58.3769 moveto -208.842 -66.9102 lineto -215.829 -70.8058 lineto closepath fill +2 setlinewidth 0 0 1 setrgbcolor newpath +-227.918 -40.9084 moveto +-298.35 -82.4884 -307.42 -87.8432 -362.048 -120.093 curveto stroke +newpath -372.381 -126.193 moveto -364.081 -116.648 lineto -360.014 -123.537 lineto closepath fill +grestore +%Nodes: +gsave +-389.604 -136.361 20 0 1 0 nc +-227.918 -40.9084 20 0 1 0 nc +-105.193 -261.035 20 0 1 0 nc +364.28 -222.074 20 1 1 0 nc +670.118 -118.829 20 1 1 0 nc +342.851 111.037 20 1 1 0 nc +5.84406 175.322 20 1 1 0 nc +169.478 311.683 20 1 1 0 nc +-173.374 377.916 20 1 0 1 nc +-251.294 -335.059 20 0 1 0 nc +-266.879 114.933 20 0 0 0 nc +-368.176 331.163 20 0 0 0 nc +-490.901 120.777 20 0 0 0 nc +-574.666 -153.893 20 1 0 0 nc +-675.963 -3.89604 20 1 0 0 nc +-465.576 -42.8564 20 1 0 0 nc +44.8044 15.5841 20 0 0 1 nc +157.79 -130.517 20 0 0 1 nc +218.178 27.2723 20 0 0 1 nc +grestore +grestore +showpage diff -r a3402913cffe -r f63e87b9748e lemon/adaptors.h --- a/lemon/adaptors.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/adaptors.h Tue Apr 21 10:34:49 2009 +0100 @@ -2192,6 +2192,9 @@ typedef typename ItemSetTraits::ItemNotifier EdgeNotifier; EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); } + + typedef EdgeNotifier ArcNotifier; + ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); } protected: diff -r a3402913cffe -r f63e87b9748e lemon/bin_heap.h --- a/lemon/bin_heap.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/bin_heap.h Tue Apr 21 10:34:49 2009 +0100 @@ -73,9 +73,9 @@ /// The item-int map must be initialized in such way that it assigns /// \c PRE_HEAP (-1) to any element to be put in the heap. enum State { - IN_HEAP = 0, ///< \e - PRE_HEAP = -1, ///< \e - POST_HEAP = -2 ///< \e + IN_HEAP = 0, ///< = 0. + PRE_HEAP = -1, ///< = -1. + POST_HEAP = -2 ///< = -2. }; private: diff -r a3402913cffe -r f63e87b9748e lemon/bits/graph_adaptor_extender.h --- a/lemon/bits/graph_adaptor_extender.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/bits/graph_adaptor_extender.h Tue Apr 21 10:34:49 2009 +0100 @@ -22,8 +22,6 @@ #include #include -#include - namespace lemon { template diff -r a3402913cffe -r f63e87b9748e lemon/bits/map_extender.h --- a/lemon/bits/map_extender.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/bits/map_extender.h Tue Apr 21 10:34:49 2009 +0100 @@ -47,6 +47,8 @@ typedef typename Parent::Key Key; typedef typename Parent::Value Value; + typedef typename Parent::Reference Reference; + typedef typename Parent::ConstReference ConstReference; class MapIt; class ConstMapIt; @@ -187,6 +189,8 @@ typedef typename Parent::Key Key; typedef typename Parent::Value Value; + typedef typename Parent::Reference Reference; + typedef typename Parent::ConstReference ConstReference; class MapIt; class ConstMapIt; diff -r a3402913cffe -r f63e87b9748e lemon/cbc.cc --- a/lemon/cbc.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/cbc.cc Tue Apr 21 10:34:49 2009 +0100 @@ -55,12 +55,15 @@ _prob->setProblemName("LEMON"); _osi_solver = 0; _cbc_model = 0; + messageLevel(MESSAGE_NOTHING); } CbcMip::CbcMip(const CbcMip& other) { _prob = new CoinModel(*other._prob); + _prob->setProblemName("LEMON"); _osi_solver = 0; _cbc_model = 0; + messageLevel(MESSAGE_NOTHING); } CbcMip::~CbcMip() { @@ -270,24 +273,8 @@ } _cbc_model= new CbcModel(*_osi_solver); - switch (_message_level) { - case MESSAGE_NO_OUTPUT: - _osi_solver->messageHandler()->setLogLevel(0); - _cbc_model->setLogLevel(0); - break; - case MESSAGE_ERROR_MESSAGE: - _osi_solver->messageHandler()->setLogLevel(1); - _cbc_model->setLogLevel(1); - break; - case MESSAGE_NORMAL_OUTPUT: - _osi_solver->messageHandler()->setLogLevel(2); - _cbc_model->setLogLevel(2); - break; - case MESSAGE_FULL_OUTPUT: - _osi_solver->messageHandler()->setLogLevel(3); - _cbc_model->setLogLevel(3); - break; - } + _osi_solver->messageHandler()->setLogLevel(_message_level); + _cbc_model->setLogLevel(_message_level); _cbc_model->initialSolve(); _cbc_model->solver()->setHintParam(OsiDoReducePrint, true, OsiHintTry); @@ -453,8 +440,24 @@ cols.clear(); } - void CbcMip::messageLevel(MessageLevel m) { - _message_level = m; + void CbcMip::_messageLevel(MessageLevel level) { + switch (level) { + case MESSAGE_NOTHING: + _message_level = 0; + break; + case MESSAGE_ERROR: + _message_level = 1; + break; + case MESSAGE_WARNING: + _message_level = 1; + break; + case MESSAGE_NORMAL: + _message_level = 2; + break; + case MESSAGE_VERBOSE: + _message_level = 3; + break; + } } } //END OF NAMESPACE LEMON diff -r a3402913cffe -r f63e87b9748e lemon/cbc.h --- a/lemon/cbc.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/cbc.h Tue Apr 21 10:34:49 2009 +0100 @@ -115,33 +115,12 @@ virtual void _clear(); - public: + virtual void _messageLevel(MessageLevel level); + void _applyMessageLevel(); - ///Enum for \c messageLevel() parameter - enum MessageLevel { - /// no output (default value) - MESSAGE_NO_OUTPUT = 0, - /// error messages only - MESSAGE_ERROR_MESSAGE = 1, - /// normal output - MESSAGE_NORMAL_OUTPUT = 2, - /// full output (includes informational messages) - MESSAGE_FULL_OUTPUT = 3 - }; + int _message_level; - private: - - MessageLevel _message_level; - - public: - - ///Set the verbosity of the messages - - ///Set the verbosity of the messages - /// - ///\param m is the level of the messages output by the solver routines. - void messageLevel(MessageLevel m); - + }; diff -r a3402913cffe -r f63e87b9748e lemon/circulation.h --- a/lemon/circulation.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/circulation.h Tue Apr 21 10:34:49 2009 +0100 @@ -453,13 +453,13 @@ createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { - _excess->set(n, (*_delta)[n]); + (*_excess)[n] = (*_delta)[n]; } for (ArcIt e(_g);e!=INVALID;++e) { _flow->set(e, (*_lo)[e]); - _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_flow)[e]); - _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_flow)[e]); + (*_excess)[_g.target(e)] += (*_flow)[e]; + (*_excess)[_g.source(e)] -= (*_flow)[e]; } // global relabeling tested, but in general case it provides @@ -482,23 +482,23 @@ createStructures(); for(NodeIt n(_g);n!=INVALID;++n) { - _excess->set(n, (*_delta)[n]); + (*_excess)[n] = (*_delta)[n]; } for (ArcIt e(_g);e!=INVALID;++e) { if (!_tol.positive((*_excess)[_g.target(e)] + (*_up)[e])) { _flow->set(e, (*_up)[e]); - _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_up)[e]); - _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_up)[e]); + (*_excess)[_g.target(e)] += (*_up)[e]; + (*_excess)[_g.source(e)] -= (*_up)[e]; } else if (_tol.positive((*_excess)[_g.target(e)] + (*_lo)[e])) { _flow->set(e, (*_lo)[e]); - _excess->set(_g.target(e), (*_excess)[_g.target(e)] + (*_lo)[e]); - _excess->set(_g.source(e), (*_excess)[_g.source(e)] - (*_lo)[e]); + (*_excess)[_g.target(e)] += (*_lo)[e]; + (*_excess)[_g.source(e)] -= (*_lo)[e]; } else { Value fc = -(*_excess)[_g.target(e)]; _flow->set(e, fc); - _excess->set(_g.target(e), 0); - _excess->set(_g.source(e), (*_excess)[_g.source(e)] - fc); + (*_excess)[_g.target(e)] = 0; + (*_excess)[_g.source(e)] -= fc; } } @@ -537,16 +537,16 @@ if((*_level)[v]set(e, (*_flow)[e] + exc); - _excess->set(v, (*_excess)[v] + exc); + (*_excess)[v] += exc; if(!_level->active(v) && _tol.positive((*_excess)[v])) _level->activate(v); - _excess->set(act,0); + (*_excess)[act] = 0; _level->deactivate(act); goto next_l; } else { _flow->set(e, (*_up)[e]); - _excess->set(v, (*_excess)[v] + fc); + (*_excess)[v] += fc; if(!_level->active(v) && _tol.positive((*_excess)[v])) _level->activate(v); exc-=fc; @@ -561,16 +561,16 @@ if((*_level)[v]set(e, (*_flow)[e] - exc); - _excess->set(v, (*_excess)[v] + exc); + (*_excess)[v] += exc; if(!_level->active(v) && _tol.positive((*_excess)[v])) _level->activate(v); - _excess->set(act,0); + (*_excess)[act] = 0; _level->deactivate(act); goto next_l; } else { _flow->set(e, (*_lo)[e]); - _excess->set(v, (*_excess)[v] + fc); + (*_excess)[v] += fc; if(!_level->active(v) && _tol.positive((*_excess)[v])) _level->activate(v); exc-=fc; @@ -579,7 +579,7 @@ else if((*_level)[v]set(act, exc); + (*_excess)[act] = exc; if(!_tol.positive(exc)) _level->deactivate(act); else if(mlevel==_node_num) { _level->liftHighestActiveToTop(); diff -r a3402913cffe -r f63e87b9748e lemon/clp.cc --- a/lemon/clp.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/clp.cc Tue Apr 21 10:34:49 2009 +0100 @@ -24,7 +24,7 @@ ClpLp::ClpLp() { _prob = new ClpSimplex(); _init_temporals(); - messageLevel(MESSAGE_NO_OUTPUT); + messageLevel(MESSAGE_NOTHING); } ClpLp::ClpLp(const ClpLp& other) { @@ -32,7 +32,7 @@ rows = other.rows; cols = other.cols; _init_temporals(); - messageLevel(MESSAGE_NO_OUTPUT); + messageLevel(MESSAGE_NOTHING); } ClpLp::~ClpLp() { @@ -430,8 +430,24 @@ _clear_temporals(); } - void ClpLp::messageLevel(MessageLevel m) { - _prob->setLogLevel(static_cast(m)); + void ClpLp::_messageLevel(MessageLevel level) { + switch (level) { + case MESSAGE_NOTHING: + _prob->setLogLevel(0); + break; + case MESSAGE_ERROR: + _prob->setLogLevel(1); + break; + case MESSAGE_WARNING: + _prob->setLogLevel(2); + break; + case MESSAGE_NORMAL: + _prob->setLogLevel(3); + break; + case MESSAGE_VERBOSE: + _prob->setLogLevel(4); + break; + } } } //END OF NAMESPACE LEMON diff -r a3402913cffe -r f63e87b9748e lemon/clp.h --- a/lemon/clp.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/clp.h Tue Apr 21 10:34:49 2009 +0100 @@ -136,6 +136,8 @@ virtual void _clear(); + virtual void _messageLevel(MessageLevel); + public: ///Solves LP with primal simplex method. @@ -153,26 +155,6 @@ ///Returns the variable identifier understood by CLP. int clpCol(Col c) const { return cols(id(c)); } - ///Enum for \c messageLevel() parameter - enum MessageLevel { - /// no output (default value) - MESSAGE_NO_OUTPUT = 0, - /// print final solution - MESSAGE_FINAL_SOLUTION = 1, - /// print factorization - MESSAGE_FACTORIZATION = 2, - /// normal output - MESSAGE_NORMAL_OUTPUT = 3, - /// verbose output - MESSAGE_VERBOSE_OUTPUT = 4 - }; - ///Set the verbosity of the messages - - ///Set the verbosity of the messages - /// - ///\param m is the level of the messages output by the solver routines. - void messageLevel(MessageLevel m); - }; } //END OF NAMESPACE LEMON diff -r a3402913cffe -r f63e87b9748e lemon/concepts/digraph.h --- a/lemon/concepts/digraph.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/concepts/digraph.h Tue Apr 21 10:34:49 2009 +0100 @@ -421,12 +421,11 @@ /// Gives back the opposite node on the given arc. Node oppositeNode(const Node&, const Arc&) const { return INVALID; } - /// \brief Read write map of the nodes to type \c T. + /// \brief Reference map of the nodes to type \c T. /// - /// ReadWrite map of the nodes to type \c T. - /// \sa Reference + /// Reference map of the nodes to type \c T. template - class NodeMap : public ReadWriteMap< Node, T > { + class NodeMap : public ReferenceMap { public: ///\e @@ -436,7 +435,8 @@ private: ///Copy constructor - NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } + NodeMap(const NodeMap& nm) : + ReferenceMap(nm) { } ///Assignment operator template NodeMap& operator=(const CMap&) { @@ -445,12 +445,11 @@ } }; - /// \brief Read write map of the arcs to type \c T. + /// \brief Reference map of the arcs to type \c T. /// /// Reference map of the arcs to type \c T. - /// \sa Reference template - class ArcMap : public ReadWriteMap { + class ArcMap : public ReferenceMap { public: ///\e @@ -459,7 +458,8 @@ ArcMap(const Digraph&, T) { } private: ///Copy constructor - ArcMap(const ArcMap& em) : ReadWriteMap(em) { } + ArcMap(const ArcMap& em) : + ReferenceMap(em) { } ///Assignment operator template ArcMap& operator=(const CMap&) { @@ -471,6 +471,7 @@ template struct Constraints { void constraints() { + checkConcept(); checkConcept, _Digraph>(); checkConcept, _Digraph>(); checkConcept, _Digraph>(); diff -r a3402913cffe -r f63e87b9748e lemon/concepts/graph.h --- a/lemon/concepts/graph.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/concepts/graph.h Tue Apr 21 10:34:49 2009 +0100 @@ -497,12 +497,11 @@ InArcIt& operator++() { return *this; } }; - /// \brief Read write map of the nodes to type \c T. + /// \brief Reference map of the nodes to type \c T. /// - /// ReadWrite map of the nodes to type \c T. - /// \sa Reference + /// Reference map of the nodes to type \c T. template - class NodeMap : public ReadWriteMap< Node, T > + class NodeMap : public ReferenceMap { public: @@ -513,7 +512,8 @@ private: ///Copy constructor - NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { } + NodeMap(const NodeMap& nm) : + ReferenceMap(nm) { } ///Assignment operator template NodeMap& operator=(const CMap&) { @@ -522,12 +522,11 @@ } }; - /// \brief Read write map of the directed arcs to type \c T. + /// \brief Reference map of the arcs to type \c T. /// - /// Reference map of the directed arcs to type \c T. - /// \sa Reference + /// Reference map of the arcs to type \c T. template - class ArcMap : public ReadWriteMap + class ArcMap : public ReferenceMap { public: @@ -537,7 +536,8 @@ ArcMap(const Graph&, T) { } private: ///Copy constructor - ArcMap(const ArcMap& em) : ReadWriteMap(em) { } + ArcMap(const ArcMap& em) : + ReferenceMap(em) { } ///Assignment operator template ArcMap& operator=(const CMap&) { @@ -546,12 +546,11 @@ } }; - /// Read write map of the edges to type \c T. + /// Reference map of the edges to type \c T. - /// Reference map of the arcs to type \c T. - /// \sa Reference + /// Reference map of the edges to type \c T. template - class EdgeMap : public ReadWriteMap + class EdgeMap : public ReferenceMap { public: @@ -561,7 +560,8 @@ EdgeMap(const Graph&, T) { } private: ///Copy constructor - EdgeMap(const EdgeMap& em) : ReadWriteMap(em) {} + EdgeMap(const EdgeMap& em) : + ReferenceMap(em) {} ///Assignment operator template EdgeMap& operator=(const CMap&) { @@ -748,6 +748,7 @@ template struct Constraints { void constraints() { + checkConcept(); checkConcept, _Graph>(); checkConcept, _Graph>(); checkConcept, _Graph>(); diff -r a3402913cffe -r f63e87b9748e lemon/concepts/graph_components.h --- a/lemon/concepts/graph_components.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/concepts/graph_components.h Tue Apr 21 10:34:49 2009 +0100 @@ -31,17 +31,16 @@ namespace lemon { namespace concepts { - /// \brief Skeleton class for graph Node and Arc types + /// \brief Concept class for \c Node, \c Arc and \c Edge types. /// - /// This class describes the interface of Node and Arc (and Edge - /// in undirected graphs) subtypes of graph types. + /// This class describes the concept of \c Node, \c Arc and \c Edge + /// subtypes of digraph and graph types. /// /// \note This class is a template class so that we can use it to - /// create graph skeleton classes. The reason for this is than Node - /// and Arc types should \em not derive from the same base class. - /// For Node you should instantiate it with character 'n' and for Arc - /// with 'a'. - + /// create graph skeleton classes. The reason for this is that \c Node + /// and \c Arc (or \c Edge) types should \e not derive from the same + /// base class. For \c Node you should instantiate it with character + /// \c 'n', for \c Arc with \c 'a' and for \c Edge with \c 'e'. #ifndef DOXYGEN template #endif @@ -49,45 +48,49 @@ public: /// \brief Default constructor. /// + /// Default constructor. /// \warning The default constructor is not required to set /// the item to some well-defined value. So you should consider it /// as uninitialized. GraphItem() {} + /// \brief Copy constructor. /// /// Copy constructor. + GraphItem(const GraphItem &) {} + + /// \brief Constructor for conversion from \c INVALID. /// - GraphItem(const GraphItem &) {} - /// \brief Invalid constructor \& conversion. - /// - /// This constructor initializes the item to be invalid. + /// Constructor for conversion from \c INVALID. + /// It initializes the item to be invalid. /// \sa Invalid for more details. GraphItem(Invalid) {} - /// \brief Assign operator for nodes. + + /// \brief Assignment operator. /// - /// The nodes are assignable. - /// - GraphItem& operator=(GraphItem const&) { return *this; } + /// Assignment operator for the item. + GraphItem& operator=(const GraphItem&) { return *this; } + /// \brief Equality operator. /// - /// Two iterators are equal if and only if they represents the - /// same node in the graph or both are invalid. - bool operator==(GraphItem) const { return false; } + /// Equality operator. + bool operator==(const GraphItem&) const { return false; } + /// \brief Inequality operator. /// - /// \sa operator==(const Node& n) + /// Inequality operator. + bool operator!=(const GraphItem&) const { return false; } + + /// \brief Ordering operator. /// - bool operator!=(GraphItem) const { return false; } - - /// \brief Artificial ordering operator. - /// - /// To allow the use of graph descriptors as key type in std::map or - /// similar associative container we require this. + /// This operator defines an ordering of the items. + /// It makes possible to use graph item types as key types in + /// associative containers (e.g. \c std::map). /// /// \note This operator only have to define some strict ordering of /// the items; this order has nothing to do with the iteration /// ordering of the items. - bool operator<(GraphItem) const { return false; } + bool operator<(const GraphItem&) const { return false; } template struct Constraints { @@ -99,7 +102,6 @@ i1 = i2 = i3; bool b; - // b = (ia == ib) && (ia != ib) && (ia < ib); b = (ia == ib) && (ia != ib); b = (ia == INVALID) && (ib != INVALID); b = (ia < ib); @@ -110,13 +112,12 @@ }; }; - /// \brief An empty base directed graph class. + /// \brief Base skeleton class for directed graphs. /// - /// This class provides the minimal set of features needed for a - /// directed graph structure. All digraph concepts have to - /// conform to this base directed graph. It just provides types - /// for nodes and arcs and functions to get the source and the - /// target of the arcs. + /// This class describes the base interface of directed graph types. + /// All digraph %concepts have to conform to this class. + /// It just provides types for nodes and arcs and functions + /// to get the source and the target nodes of arcs. class BaseDigraphComponent { public: @@ -124,31 +125,27 @@ /// \brief Node class of the digraph. /// - /// This class represents the Nodes of the digraph. - /// + /// This class represents the nodes of the digraph. typedef GraphItem<'n'> Node; /// \brief Arc class of the digraph. /// - /// This class represents the Arcs of the digraph. + /// This class represents the arcs of the digraph. + typedef GraphItem<'a'> Arc; + + /// \brief Return the source node of an arc. /// - typedef GraphItem<'e'> Arc; + /// This function returns the source node of an arc. + Node source(const Arc&) const { return INVALID; } - /// \brief Gives back the target node of an arc. + /// \brief Return the target node of an arc. /// - /// Gives back the target node of an arc. + /// This function returns the target node of an arc. + Node target(const Arc&) const { return INVALID; } + + /// \brief Return the opposite node on the given arc. /// - Node target(const Arc&) const { return INVALID;} - - /// \brief Gives back the source node of an arc. - /// - /// Gives back the source node of an arc. - /// - Node source(const Arc&) const { return INVALID;} - - /// \brief Gives back the opposite node on the given arc. - /// - /// Gives back the opposite node on the given arc. + /// This function returns the opposite node on the given arc. Node oppositeNode(const Node&, const Arc&) const { return INVALID; } @@ -174,91 +171,96 @@ }; }; - /// \brief An empty base undirected graph class. + /// \brief Base skeleton class for undirected graphs. /// - /// This class provides the minimal set of features needed for an - /// undirected graph structure. All undirected graph concepts have - /// to conform to this base graph. It just provides types for - /// nodes, arcs and edges and functions to get the - /// source and the target of the arcs and edges, - /// conversion from arcs to edges and function to get - /// both direction of the edges. + /// This class describes the base interface of undirected graph types. + /// All graph %concepts have to conform to this class. + /// It extends the interface of \ref BaseDigraphComponent with an + /// \c Edge type and functions to get the end nodes of edges, + /// to convert from arcs to edges and to get both direction of edges. class BaseGraphComponent : public BaseDigraphComponent { public: typedef BaseDigraphComponent::Node Node; typedef BaseDigraphComponent::Arc Arc; - /// \brief Undirected arc class of the graph. + + /// \brief Undirected edge class of the graph. /// - /// This class represents the edges of the graph. - /// The undirected graphs can be used as a directed graph which - /// for each arc contains the opposite arc too so the graph is - /// bidirected. The edge represents two opposite - /// directed arcs. - class Edge : public GraphItem<'u'> { + /// This class represents the undirected edges of the graph. + /// Undirected graphs can be used as directed graphs, each edge is + /// represented by two opposite directed arcs. + class Edge : public GraphItem<'e'> { public: - typedef GraphItem<'u'> Parent; + typedef GraphItem<'e'> Parent; + /// \brief Default constructor. /// + /// Default constructor. /// \warning The default constructor is not required to set /// the item to some well-defined value. So you should consider it /// as uninitialized. Edge() {} + /// \brief Copy constructor. /// /// Copy constructor. + Edge(const Edge &) : Parent() {} + + /// \brief Constructor for conversion from \c INVALID. /// - Edge(const Edge &) : Parent() {} - /// \brief Invalid constructor \& conversion. - /// - /// This constructor initializes the item to be invalid. + /// Constructor for conversion from \c INVALID. + /// It initializes the item to be invalid. /// \sa Invalid for more details. Edge(Invalid) {} - /// \brief Converter from arc to edge. + + /// \brief Constructor for conversion from an arc. /// + /// Constructor for conversion from an arc. /// Besides the core graph item functionality each arc should /// be convertible to the represented edge. Edge(const Arc&) {} - /// \brief Assign arc to edge. + + /// \brief Assign an arc to an edge. /// + /// This function assigns an arc to an edge. /// Besides the core graph item functionality each arc should /// be convertible to the represented edge. Edge& operator=(const Arc&) { return *this; } }; - /// \brief Returns the direction of the arc. + /// \brief Return one end node of an edge. + /// + /// This function returns one end node of an edge. + Node u(const Edge&) const { return INVALID; } + + /// \brief Return the other end node of an edge. + /// + /// This function returns the other end node of an edge. + Node v(const Edge&) const { return INVALID; } + + /// \brief Return a directed arc related to an edge. + /// + /// This function returns a directed arc from its direction and the + /// represented edge. + Arc direct(const Edge&, bool) const { return INVALID; } + + /// \brief Return a directed arc related to an edge. + /// + /// This function returns a directed arc from its source node and the + /// represented edge. + Arc direct(const Edge&, const Node&) const { return INVALID; } + + /// \brief Return the direction of the arc. /// /// Returns the direction of the arc. Each arc represents an /// edge with a direction. It gives back the /// direction. bool direction(const Arc&) const { return true; } - /// \brief Returns the directed arc. + /// \brief Return the opposite arc. /// - /// Returns the directed arc from its direction and the - /// represented edge. - Arc direct(const Edge&, bool) const { return INVALID;} - - /// \brief Returns the directed arc. - /// - /// Returns the directed arc from its source and the - /// represented edge. - Arc direct(const Edge&, const Node&) const { return INVALID;} - - /// \brief Returns the opposite arc. - /// - /// Returns the opposite arc. It is the arc representing the - /// same edge and has opposite direction. - Arc oppositeArc(const Arc&) const { return INVALID;} - - /// \brief Gives back one ending of an edge. - /// - /// Gives back one ending of an edge. - Node u(const Edge&) const { return INVALID;} - - /// \brief Gives back the other ending of an edge. - /// - /// Gives back the other ending of an edge. - Node v(const Edge&) const { return INVALID;} + /// This function returns the opposite arc, i.e. the arc representing + /// the same edge and has opposite direction. + Arc oppositeArc(const Arc&) const { return INVALID; } template struct Constraints { @@ -268,7 +270,7 @@ void constraints() { checkConcept(); - checkConcept, Edge>(); + checkConcept, Edge>(); { Node n; Edge ue(INVALID); @@ -276,6 +278,7 @@ n = graph.u(ue); n = graph.v(ue); e = graph.direct(ue, true); + e = graph.direct(ue, false); e = graph.direct(ue, n); e = graph.oppositeArc(e); ue = e; @@ -289,12 +292,12 @@ }; - /// \brief An empty idable base digraph class. + /// \brief Skeleton class for \e idable directed graphs. /// - /// This class provides beside the core digraph features - /// core id functions for the digraph structure. - /// The most of the base digraphs should conform to this concept. - /// The id's are unique and immutable. + /// This class describes the interface of \e idable directed graphs. + /// It extends \ref BaseDigraphComponent with the core ID functions. + /// The ids of the items must be unique and immutable. + /// This concept is part of the Digraph concept. template class IDableDigraphComponent : public BAS { public: @@ -303,45 +306,43 @@ typedef typename Base::Node Node; typedef typename Base::Arc Arc; - /// \brief Gives back an unique integer id for the Node. + /// \brief Return a unique integer id for the given node. /// - /// Gives back an unique integer id for the Node. + /// This function returns a unique integer id for the given node. + int id(const Node&) const { return -1; } + + /// \brief Return the node by its unique id. /// - int id(const Node&) const { return -1;} + /// This function returns the node by its unique id. + /// If the digraph does not contain a node with the given id, + /// then the result of the function is undefined. + Node nodeFromId(int) const { return INVALID; } - /// \brief Gives back the node by the unique id. + /// \brief Return a unique integer id for the given arc. /// - /// Gives back the node by the unique id. - /// If the digraph does not contain node with the given id - /// then the result of the function is undetermined. - Node nodeFromId(int) const { return INVALID;} + /// This function returns a unique integer id for the given arc. + int id(const Arc&) const { return -1; } - /// \brief Gives back an unique integer id for the Arc. + /// \brief Return the arc by its unique id. /// - /// Gives back an unique integer id for the Arc. + /// This function returns the arc by its unique id. + /// If the digraph does not contain an arc with the given id, + /// then the result of the function is undefined. + Arc arcFromId(int) const { return INVALID; } + + /// \brief Return an integer greater or equal to the maximum + /// node id. /// - int id(const Arc&) const { return -1;} + /// This function returns an integer greater or equal to the + /// maximum node id. + int maxNodeId() const { return -1; } - /// \brief Gives back the arc by the unique id. + /// \brief Return an integer greater or equal to the maximum + /// arc id. /// - /// Gives back the arc by the unique id. - /// If the digraph does not contain arc with the given id - /// then the result of the function is undetermined. - Arc arcFromId(int) const { return INVALID;} - - /// \brief Gives back an integer greater or equal to the maximum - /// Node id. - /// - /// Gives back an integer greater or equal to the maximum Node - /// id. - int maxNodeId() const { return -1;} - - /// \brief Gives back an integer greater or equal to the maximum - /// Arc id. - /// - /// Gives back an integer greater or equal to the maximum Arc - /// id. - int maxArcId() const { return -1;} + /// This function returns an integer greater or equal to the + /// maximum arc id. + int maxArcId() const { return -1; } template struct Constraints { @@ -367,12 +368,13 @@ }; }; - /// \brief An empty idable base undirected graph class. + /// \brief Skeleton class for \e idable undirected graphs. /// - /// This class provides beside the core undirected graph features - /// core id functions for the undirected graph structure. The - /// most of the base undirected graphs should conform to this - /// concept. The id's are unique and immutable. + /// This class describes the interface of \e idable undirected + /// graphs. It extends \ref IDableDigraphComponent with the core ID + /// functions of undirected graphs. + /// The ids of the items must be unique and immutable. + /// This concept is part of the Graph concept. template class IDableGraphComponent : public IDableDigraphComponent { public: @@ -382,31 +384,29 @@ using IDableDigraphComponent::id; - /// \brief Gives back an unique integer id for the Edge. + /// \brief Return a unique integer id for the given edge. /// - /// Gives back an unique integer id for the Edge. + /// This function returns a unique integer id for the given edge. + int id(const Edge&) const { return -1; } + + /// \brief Return the edge by its unique id. /// - int id(const Edge&) const { return -1;} + /// This function returns the edge by its unique id. + /// If the graph does not contain an edge with the given id, + /// then the result of the function is undefined. + Edge edgeFromId(int) const { return INVALID; } - /// \brief Gives back the edge by the unique id. + /// \brief Return an integer greater or equal to the maximum + /// edge id. /// - /// Gives back the edge by the unique id. If the - /// graph does not contain arc with the given id then the - /// result of the function is undetermined. - Edge edgeFromId(int) const { return INVALID;} - - /// \brief Gives back an integer greater or equal to the maximum - /// Edge id. - /// - /// Gives back an integer greater or equal to the maximum Edge - /// id. - int maxEdgeId() const { return -1;} + /// This function returns an integer greater or equal to the + /// maximum edge id. + int maxEdgeId() const { return -1; } template struct Constraints { void constraints() { - checkConcept(); checkConcept, _Graph >(); typename _Graph::Edge edge; int ueid = graph.id(edge); @@ -420,59 +420,71 @@ }; }; - /// \brief Skeleton class for graph NodeIt and ArcIt + /// \brief Concept class for \c NodeIt, \c ArcIt and \c EdgeIt types. /// - /// Skeleton class for graph NodeIt and ArcIt. - /// + /// This class describes the concept of \c NodeIt, \c ArcIt and + /// \c EdgeIt subtypes of digraph and graph types. template class GraphItemIt : public Item { public: /// \brief Default constructor. /// - /// @warning The default constructor sets the iterator - /// to an undefined value. + /// Default constructor. + /// \warning The default constructor is not required to set + /// the iterator to some well-defined value. So you should consider it + /// as uninitialized. GraphItemIt() {} + /// \brief Copy constructor. /// /// Copy constructor. + GraphItemIt(const GraphItemIt& it) : Item(it) {} + + /// \brief Constructor that sets the iterator to the first item. /// - GraphItemIt(const GraphItemIt& ) {} - /// \brief Sets the iterator to the first item. + /// Constructor that sets the iterator to the first item. + explicit GraphItemIt(const GR&) {} + + /// \brief Constructor for conversion from \c INVALID. /// - /// Sets the iterator to the first item of \c the graph. - /// - explicit GraphItemIt(const GR&) {} - /// \brief Invalid constructor \& conversion. - /// - /// This constructor initializes the item to be invalid. + /// Constructor for conversion from \c INVALID. + /// It initializes the iterator to be invalid. /// \sa Invalid for more details. GraphItemIt(Invalid) {} - /// \brief Assign operator for items. + + /// \brief Assignment operator. /// - /// The items are assignable. + /// Assignment operator for the iterator. + GraphItemIt& operator=(const GraphItemIt&) { return *this; } + + /// \brief Increment the iterator. /// - GraphItemIt& operator=(const GraphItemIt&) { return *this; } - /// \brief Next item. - /// - /// Assign the iterator to the next item. - /// + /// This operator increments the iterator, i.e. assigns it to the + /// next item. GraphItemIt& operator++() { return *this; } + /// \brief Equality operator /// + /// Equality operator. /// Two iterators are equal if and only if they point to the /// same object or both are invalid. bool operator==(const GraphItemIt&) const { return true;} + /// \brief Inequality operator /// - /// \sa operator==(Node n) - /// + /// Inequality operator. + /// Two iterators are equal if and only if they point to the + /// same object or both are invalid. bool operator!=(const GraphItemIt&) const { return true;} template struct Constraints { void constraints() { + checkConcept, _GraphItemIt>(); _GraphItemIt it1(g); _GraphItemIt it2; + _GraphItemIt it3 = it1; + _GraphItemIt it4 = INVALID; it2 = ++it1; ++it2 = it1; @@ -481,16 +493,20 @@ Item bi = it1; bi = it2; } - GR& g; + const GR& g; }; }; - /// \brief Skeleton class for graph InArcIt and OutArcIt + /// \brief Concept class for \c InArcIt, \c OutArcIt and + /// \c IncEdgeIt types. /// - /// \note Because InArcIt and OutArcIt may not inherit from the same - /// base class, the \c sel is a additional template parameter (selector). - /// For InArcIt you should instantiate it with character 'i' and for - /// OutArcIt with 'o'. + /// This class describes the concept of \c InArcIt, \c OutArcIt + /// and \c IncEdgeIt subtypes of digraph and graph types. + /// + /// \note Since these iterator classes do not inherit from the same + /// base class, there is an additional template parameter (selector) + /// \c sel. For \c InArcIt you should instantiate it with character + /// \c 'i', for \c OutArcIt with \c 'o' and for \c IncEdgeIt with \c 'e'. template @@ -548,27 +571,25 @@ checkConcept, _GraphIncIt>(); _GraphIncIt it1(graph, node); _GraphIncIt it2; + _GraphIncIt it3 = it1; + _GraphIncIt it4 = INVALID; it2 = ++it1; ++it2 = it1; ++(++it1); Item e = it1; e = it2; - } - - Item arc; - Base node; - GR graph; - _GraphIncIt it; + const Base& node; + const GR& graph; }; }; - - /// \brief An empty iterable digraph class. + /// \brief Skeleton class for iterable directed graphs. /// - /// This class provides beside the core digraph features - /// iterator based iterable interface for the digraph structure. + /// This class describes the interface of iterable directed + /// graphs. It extends \ref BaseDigraphComponent with the core + /// iterable interface. /// This concept is part of the Digraph concept. template class IterableDigraphComponent : public BAS { @@ -581,70 +602,61 @@ typedef IterableDigraphComponent Digraph; - /// \name Base iteration + /// \name Base Iteration /// - /// This interface provides functions for iteration on digraph items + /// This interface provides functions for iteration on digraph items. /// /// @{ - /// \brief Gives back the first node in the iterating order. + /// \brief Return the first node. /// - /// Gives back the first node in the iterating order. - /// + /// This function gives back the first node in the iteration order. void first(Node&) const {} - /// \brief Gives back the next node in the iterating order. + /// \brief Return the next node. /// - /// Gives back the next node in the iterating order. - /// + /// This function gives back the next node in the iteration order. void next(Node&) const {} - /// \brief Gives back the first arc in the iterating order. + /// \brief Return the first arc. /// - /// Gives back the first arc in the iterating order. - /// + /// This function gives back the first arc in the iteration order. void first(Arc&) const {} - /// \brief Gives back the next arc in the iterating order. + /// \brief Return the next arc. /// - /// Gives back the next arc in the iterating order. - /// + /// This function gives back the next arc in the iteration order. void next(Arc&) const {} - - /// \brief Gives back the first of the arcs point to the given - /// node. + /// \brief Return the first arc incomming to the given node. /// - /// Gives back the first of the arcs point to the given node. - /// + /// This function gives back the first arc incomming to the + /// given node. void firstIn(Arc&, const Node&) const {} - /// \brief Gives back the next of the arcs points to the given - /// node. + /// \brief Return the next arc incomming to the given node. /// - /// Gives back the next of the arcs points to the given node. - /// + /// This function gives back the next arc incomming to the + /// given node. void nextIn(Arc&) const {} - /// \brief Gives back the first of the arcs start from the + /// \brief Return the first arc outgoing form the given node. + /// + /// This function gives back the first arc outgoing form the /// given node. - /// - /// Gives back the first of the arcs start from the given node. - /// void firstOut(Arc&, const Node&) const {} - /// \brief Gives back the next of the arcs start from the given - /// node. + /// \brief Return the next arc outgoing form the given node. /// - /// Gives back the next of the arcs start from the given node. - /// + /// This function gives back the next arc outgoing form the + /// given node. void nextOut(Arc&) const {} /// @} - /// \name Class based iteration + /// \name Class Based Iteration /// - /// This interface provides functions for iteration on digraph items + /// This interface provides iterator classes for digraph items. /// /// @{ @@ -654,15 +666,15 @@ /// typedef GraphItemIt NodeIt; - /// \brief This iterator goes through each node. + /// \brief This iterator goes through each arc. /// - /// This iterator goes through each node. + /// This iterator goes through each arc. /// typedef GraphItemIt ArcIt; /// \brief This iterator goes trough the incoming arcs of a node. /// - /// This iterator goes trough the \e inccoming arcs of a certain node + /// This iterator goes trough the \e incoming arcs of a certain node /// of a digraph. typedef GraphIncIt InArcIt; @@ -674,26 +686,26 @@ /// \brief The base node of the iterator. /// - /// Gives back the base node of the iterator. - /// It is always the target of the pointed arc. + /// This function gives back the base node of the iterator. + /// It is always the target node of the pointed arc. Node baseNode(const InArcIt&) const { return INVALID; } /// \brief The running node of the iterator. /// - /// Gives back the running node of the iterator. - /// It is always the source of the pointed arc. + /// This function gives back the running node of the iterator. + /// It is always the source node of the pointed arc. Node runningNode(const InArcIt&) const { return INVALID; } /// \brief The base node of the iterator. /// - /// Gives back the base node of the iterator. - /// It is always the source of the pointed arc. + /// This function gives back the base node of the iterator. + /// It is always the source node of the pointed arc. Node baseNode(const OutArcIt&) const { return INVALID; } /// \brief The running node of the iterator. /// - /// Gives back the running node of the iterator. - /// It is always the target of the pointed arc. + /// This function gives back the running node of the iterator. + /// It is always the target node of the pointed arc. Node runningNode(const OutArcIt&) const { return INVALID; } /// @} @@ -735,25 +747,25 @@ typename _Digraph::Node, 'o'>, typename _Digraph::OutArcIt>(); typename _Digraph::Node n; - typename _Digraph::InArcIt ieit(INVALID); - typename _Digraph::OutArcIt oeit(INVALID); - n = digraph.baseNode(ieit); - n = digraph.runningNode(ieit); - n = digraph.baseNode(oeit); - n = digraph.runningNode(oeit); + const typename _Digraph::InArcIt iait(INVALID); + const typename _Digraph::OutArcIt oait(INVALID); + n = digraph.baseNode(iait); + n = digraph.runningNode(iait); + n = digraph.baseNode(oait); + n = digraph.runningNode(oait); ignore_unused_variable_warning(n); } } const _Digraph& digraph; - }; }; - /// \brief An empty iterable undirected graph class. + /// \brief Skeleton class for iterable undirected graphs. /// - /// This class provides beside the core graph features iterator - /// based iterable interface for the undirected graph structure. + /// This class describes the interface of iterable undirected + /// graphs. It extends \ref IterableDigraphComponent with the core + /// iterable interface of undirected graphs. /// This concept is part of the Graph concept. template class IterableGraphComponent : public IterableDigraphComponent { @@ -767,44 +779,38 @@ typedef IterableGraphComponent Graph; - /// \name Base iteration + /// \name Base Iteration /// - /// This interface provides functions for iteration on graph items + /// This interface provides functions for iteration on edges. + /// /// @{ using IterableDigraphComponent::first; using IterableDigraphComponent::next; - /// \brief Gives back the first edge in the iterating - /// order. + /// \brief Return the first edge. /// - /// Gives back the first edge in the iterating order. - /// + /// This function gives back the first edge in the iteration order. void first(Edge&) const {} - /// \brief Gives back the next edge in the iterating - /// order. + /// \brief Return the next edge. /// - /// Gives back the next edge in the iterating order. - /// + /// This function gives back the next edge in the iteration order. void next(Edge&) const {} - - /// \brief Gives back the first of the edges from the + /// \brief Return the first edge incident to the given node. + /// + /// This function gives back the first edge incident to the given + /// node. The bool parameter gives back the direction for which the + /// source node of the directed arc representing the edge is the /// given node. - /// - /// Gives back the first of the edges from the given - /// node. The bool parameter gives back that direction which - /// gives a good direction of the edge so the source of the - /// directed arc is the given node. void firstInc(Edge&, bool&, const Node&) const {} /// \brief Gives back the next of the edges from the /// given node. /// - /// Gives back the next of the edges from the given - /// node. The bool parameter should be used as the \c firstInc() - /// use it. + /// This function gives back the next edge incident to the given + /// node. The bool parameter should be used as \c firstInc() use it. void nextInc(Edge&, bool&) const {} using IterableDigraphComponent::baseNode; @@ -812,30 +818,32 @@ /// @} - /// \name Class based iteration + /// \name Class Based Iteration /// - /// This interface provides functions for iteration on graph items + /// This interface provides iterator classes for edges. /// /// @{ - /// \brief This iterator goes through each node. + /// \brief This iterator goes through each edge. /// - /// This iterator goes through each node. + /// This iterator goes through each edge. typedef GraphItemIt EdgeIt; - /// \brief This iterator goes trough the incident arcs of a + + /// \brief This iterator goes trough the incident edges of a /// node. /// - /// This iterator goes trough the incident arcs of a certain + /// This iterator goes trough the incident edges of a certain /// node of a graph. - typedef GraphIncIt IncEdgeIt; + typedef GraphIncIt IncEdgeIt; + /// \brief The base node of the iterator. /// - /// Gives back the base node of the iterator. + /// This function gives back the base node of the iterator. Node baseNode(const IncEdgeIt&) const { return INVALID; } /// \brief The running node of the iterator. /// - /// Gives back the running node of the iterator. + /// This function gives back the running node of the iterator. Node runningNode(const IncEdgeIt&) const { return INVALID; } /// @} @@ -864,12 +872,12 @@ checkConcept, typename _Graph::EdgeIt >(); checkConcept, typename _Graph::IncEdgeIt>(); + typename _Graph::Node, 'e'>, typename _Graph::IncEdgeIt>(); typename _Graph::Node n; - typename _Graph::IncEdgeIt ueit(INVALID); - n = graph.baseNode(ueit); - n = graph.runningNode(ueit); + const typename _Graph::IncEdgeIt ieit(INVALID); + n = graph.baseNode(ieit); + n = graph.runningNode(ieit); } } @@ -877,13 +885,14 @@ }; }; - /// \brief An empty alteration notifier digraph class. + /// \brief Skeleton class for alterable directed graphs. /// - /// This class provides beside the core digraph features alteration - /// notifier interface for the digraph structure. This implements + /// This class describes the interface of alterable directed + /// graphs. It extends \ref BaseDigraphComponent with the alteration + /// notifier interface. It implements /// an observer-notifier pattern for each digraph item. More /// obsevers can be registered into the notifier and whenever an - /// alteration occured in the digraph all the observers will + /// alteration occured in the digraph all the observers will be /// notified about it. template class AlterableDigraphComponent : public BAS { @@ -894,23 +903,23 @@ typedef typename Base::Arc Arc; - /// The node observer registry. + /// Node alteration notifier class. typedef AlterationNotifier NodeNotifier; - /// The arc observer registry. + /// Arc alteration notifier class. typedef AlterationNotifier ArcNotifier; - /// \brief Gives back the node alteration notifier. + /// \brief Return the node alteration notifier. /// - /// Gives back the node alteration notifier. + /// This function gives back the node alteration notifier. NodeNotifier& notifier(Node) const { - return NodeNotifier(); + return NodeNotifier(); } - /// \brief Gives back the arc alteration notifier. + /// \brief Return the arc alteration notifier. /// - /// Gives back the arc alteration notifier. + /// This function gives back the arc alteration notifier. ArcNotifier& notifier(Arc) const { return ArcNotifier(); } @@ -930,18 +939,17 @@ } const _Digraph& digraph; - }; - }; - /// \brief An empty alteration notifier undirected graph class. + /// \brief Skeleton class for alterable undirected graphs. /// - /// This class provides beside the core graph features alteration - /// notifier interface for the graph structure. This implements - /// an observer-notifier pattern for each graph item. More + /// This class describes the interface of alterable undirected + /// graphs. It extends \ref AlterableDigraphComponent with the alteration + /// notifier interface of undirected graphs. It implements + /// an observer-notifier pattern for the edges. More /// obsevers can be registered into the notifier and whenever an - /// alteration occured in the graph all the observers will + /// alteration occured in the graph all the observers will be /// notified about it. template class AlterableGraphComponent : public AlterableDigraphComponent { @@ -951,13 +959,13 @@ typedef typename Base::Edge Edge; - /// The arc observer registry. + /// Edge alteration notifier class. typedef AlterationNotifier EdgeNotifier; - /// \brief Gives back the arc alteration notifier. + /// \brief Return the edge alteration notifier. /// - /// Gives back the arc alteration notifier. + /// This function gives back the edge alteration notifier. EdgeNotifier& notifier(Edge) const { return EdgeNotifier(); } @@ -965,7 +973,7 @@ template struct Constraints { void constraints() { - checkConcept, _Graph>(); + checkConcept, _Graph>(); typename _Graph::EdgeNotifier& uen = graph.notifier(typename _Graph::Edge()); ignore_unused_variable_warning(uen); @@ -975,13 +983,14 @@ }; }; - /// \brief Class describing the concept of graph maps + /// \brief Concept class for standard graph maps. /// - /// This class describes the common interface of the graph maps - /// (NodeMap, ArcMap), that is maps that can be used to - /// associate data to graph descriptors (nodes or arcs). + /// This class describes the concept of standard graph maps, i.e. + /// the \c NodeMap, \c ArcMap and \c EdgeMap subtypes of digraph and + /// graph types, which can be used for associating data to graph items. + /// The standard graph maps must conform to the ReferenceMap concept. template - class GraphMap : public ReadWriteMap { + class GraphMap : public ReferenceMap { public: typedef ReadWriteMap Parent; @@ -992,6 +1001,13 @@ typedef K Key; /// The value type of the map. typedef V Value; + /// The reference type of the map. + typedef Value& Reference; + /// The const reference type of the map. + typedef const Value& ConstReference; + + // The reference map tag. + typedef True ReferenceMapTag; /// \brief Construct a new map. /// @@ -999,7 +1015,7 @@ explicit GraphMap(const Graph&) {} /// \brief Construct a new map with default value. /// - /// Construct a new map for the graph and initalise the values. + /// Construct a new map for the graph and initalize the values. GraphMap(const Graph&, const Value&) {} private: @@ -1008,9 +1024,9 @@ /// Copy Constructor. GraphMap(const GraphMap&) : Parent() {} - /// \brief Assign operator. + /// \brief Assignment operator. /// - /// Assign operator. It does not mofify the underlying graph, + /// Assignment operator. It does not mofify the underlying graph, /// it just iterates on the current item set and set the map /// with the value returned by the assigned map. template @@ -1023,33 +1039,35 @@ template struct Constraints { void constraints() { - checkConcept, _Map >(); - // Construction with a graph parameter - _Map a(g); - // Constructor with a graph and a default value parameter - _Map a2(g,t); - // Copy constructor. - // _Map b(c); + checkConcept + , _Map>(); + _Map m1(g); + _Map m2(g,t); + + // Copy constructor + // _Map m3(m); + // Assignment operator // ReadMap cmap; - // b = cmap; + // m3 = cmap; - ignore_unused_variable_warning(a); - ignore_unused_variable_warning(a2); - // ignore_unused_variable_warning(b); + ignore_unused_variable_warning(m1); + ignore_unused_variable_warning(m2); + // ignore_unused_variable_warning(m3); } - const _Map &c; + const _Map &m; const Graph &g; const typename GraphMap::Value &t; }; }; - /// \brief An empty mappable digraph class. + /// \brief Skeleton class for mappable directed graphs. /// - /// This class provides beside the core digraph features - /// map interface for the digraph structure. + /// This class describes the interface of mappable directed graphs. + /// It extends \ref BaseDigraphComponent with the standard digraph + /// map classes, namely \c NodeMap and \c ArcMap. /// This concept is part of the Digraph concept. template class MappableDigraphComponent : public BAS { @@ -1061,12 +1079,12 @@ typedef MappableDigraphComponent Digraph; - /// \brief ReadWrite map of the nodes. + /// \brief Standard graph map for the nodes. /// - /// ReadWrite map of the nodes. - /// + /// Standard graph map for the nodes. + /// It conforms to the ReferenceMap concept. template - class NodeMap : public GraphMap { + class NodeMap : public GraphMap { public: typedef GraphMap Parent; @@ -1078,7 +1096,7 @@ /// \brief Construct a new map with default value. /// - /// Construct a new map for the digraph and initalise the values. + /// Construct a new map for the digraph and initalize the values. NodeMap(const MappableDigraphComponent& digraph, const V& value) : Parent(digraph, value) {} @@ -1088,9 +1106,9 @@ /// Copy Constructor. NodeMap(const NodeMap& nm) : Parent(nm) {} - /// \brief Assign operator. + /// \brief Assignment operator. /// - /// Assign operator. + /// Assignment operator. template NodeMap& operator=(const CMap&) { checkConcept, CMap>(); @@ -1099,12 +1117,12 @@ }; - /// \brief ReadWrite map of the arcs. + /// \brief Standard graph map for the arcs. /// - /// ReadWrite map of the arcs. - /// + /// Standard graph map for the arcs. + /// It conforms to the ReferenceMap concept. template - class ArcMap : public GraphMap { + class ArcMap : public GraphMap { public: typedef GraphMap Parent; @@ -1116,7 +1134,7 @@ /// \brief Construct a new map with default value. /// - /// Construct a new map for the digraph and initalise the values. + /// Construct a new map for the digraph and initalize the values. ArcMap(const MappableDigraphComponent& digraph, const V& value) : Parent(digraph, value) {} @@ -1126,9 +1144,9 @@ /// Copy Constructor. ArcMap(const ArcMap& nm) : Parent(nm) {} - /// \brief Assign operator. + /// \brief Assignment operator. /// - /// Assign operator. + /// Assignment operator. template ArcMap& operator=(const CMap&) { checkConcept, CMap>(); @@ -1178,14 +1196,15 @@ } } - _Digraph& digraph; + const _Digraph& digraph; }; }; - /// \brief An empty mappable base bipartite graph class. + /// \brief Skeleton class for mappable undirected graphs. /// - /// This class provides beside the core graph features - /// map interface for the graph structure. + /// This class describes the interface of mappable undirected graphs. + /// It extends \ref MappableDigraphComponent with the standard graph + /// map class for edges (\c EdgeMap). /// This concept is part of the Graph concept. template class MappableGraphComponent : public MappableDigraphComponent { @@ -1196,12 +1215,12 @@ typedef MappableGraphComponent Graph; - /// \brief ReadWrite map of the edges. + /// \brief Standard graph map for the edges. /// - /// ReadWrite map of the edges. - /// + /// Standard graph map for the edges. + /// It conforms to the ReferenceMap concept. template - class EdgeMap : public GraphMap { + class EdgeMap : public GraphMap { public: typedef GraphMap Parent; @@ -1213,7 +1232,7 @@ /// \brief Construct a new map with default value. /// - /// Construct a new map for the graph and initalise the values. + /// Construct a new map for the graph and initalize the values. EdgeMap(const MappableGraphComponent& graph, const V& value) : Parent(graph, value) {} @@ -1223,9 +1242,9 @@ /// Copy Constructor. EdgeMap(const EdgeMap& nm) : Parent(nm) {} - /// \brief Assign operator. + /// \brief Assignment operator. /// - /// Assign operator. + /// Assignment operator. template EdgeMap& operator=(const CMap&) { checkConcept, CMap>(); @@ -1245,7 +1264,7 @@ }; void constraints() { - checkConcept, _Graph>(); + checkConcept, _Graph>(); { // int map test typedef typename _Graph::template EdgeMap IntEdgeMap; @@ -1262,16 +1281,16 @@ } } - _Graph& graph; + const _Graph& graph; }; }; - /// \brief An empty extendable digraph class. + /// \brief Skeleton class for extendable directed graphs. /// - /// This class provides beside the core digraph features digraph - /// extendable interface for the digraph structure. The main - /// difference between the base and this interface is that the - /// digraph alterations should handled already on this level. + /// This class describes the interface of extendable directed graphs. + /// It extends \ref BaseDigraphComponent with functions for adding + /// nodes and arcs to the digraph. + /// This concept requires \ref AlterableDigraphComponent. template class ExtendableDigraphComponent : public BAS { public: @@ -1280,17 +1299,17 @@ typedef typename Base::Node Node; typedef typename Base::Arc Arc; - /// \brief Adds a new node to the digraph. + /// \brief Add a new node to the digraph. /// - /// Adds a new node to the digraph. - /// + /// This function adds a new node to the digraph. Node addNode() { return INVALID; } - /// \brief Adds a new arc connects the given two nodes. + /// \brief Add a new arc connecting the given two nodes. /// - /// Adds a new arc connects the the given two nodes. + /// This function adds a new arc connecting the given two nodes + /// of the digraph. Arc addArc(const Node&, const Node&) { return INVALID; } @@ -1310,13 +1329,12 @@ }; }; - /// \brief An empty extendable base undirected graph class. + /// \brief Skeleton class for extendable undirected graphs. /// - /// This class provides beside the core undirected graph features - /// core undircted graph extend interface for the graph structure. - /// The main difference between the base and this interface is - /// that the graph alterations should handled already on this - /// level. + /// This class describes the interface of extendable undirected graphs. + /// It extends \ref BaseGraphComponent with functions for adding + /// nodes and edges to the graph. + /// This concept requires \ref AlterableGraphComponent. template class ExtendableGraphComponent : public BAS { public: @@ -1325,18 +1343,18 @@ typedef typename Base::Node Node; typedef typename Base::Edge Edge; - /// \brief Adds a new node to the graph. + /// \brief Add a new node to the digraph. /// - /// Adds a new node to the graph. - /// + /// This function adds a new node to the digraph. Node addNode() { return INVALID; } - /// \brief Adds a new arc connects the given two nodes. + /// \brief Add a new edge connecting the given two nodes. /// - /// Adds a new arc connects the the given two nodes. - Edge addArc(const Node&, const Node&) { + /// This function adds a new edge connecting the given two nodes + /// of the graph. + Edge addEdge(const Node&, const Node&) { return INVALID; } @@ -1355,12 +1373,12 @@ }; }; - /// \brief An empty erasable digraph class. + /// \brief Skeleton class for erasable directed graphs. /// - /// This class provides beside the core digraph features core erase - /// functions for the digraph structure. The main difference between - /// the base and this interface is that the digraph alterations - /// should handled already on this level. + /// This class describes the interface of erasable directed graphs. + /// It extends \ref BaseDigraphComponent with functions for removing + /// nodes and arcs from the digraph. + /// This concept requires \ref AlterableDigraphComponent. template class ErasableDigraphComponent : public BAS { public: @@ -1371,23 +1389,22 @@ /// \brief Erase a node from the digraph. /// - /// Erase a node from the digraph. This function should - /// erase all arcs connecting to the node. + /// This function erases the given node from the digraph and all arcs + /// connected to the node. void erase(const Node&) {} /// \brief Erase an arc from the digraph. /// - /// Erase an arc from the digraph. - /// + /// This function erases the given arc from the digraph. void erase(const Arc&) {} template struct Constraints { void constraints() { checkConcept(); - typename _Digraph::Node node; + const typename _Digraph::Node node(INVALID); digraph.erase(node); - typename _Digraph::Arc arc; + const typename _Digraph::Arc arc(INVALID); digraph.erase(arc); } @@ -1395,12 +1412,12 @@ }; }; - /// \brief An empty erasable base undirected graph class. + /// \brief Skeleton class for erasable undirected graphs. /// - /// This class provides beside the core undirected graph features - /// core erase functions for the undirceted graph structure. The - /// main difference between the base and this interface is that - /// the graph alterations should handled already on this level. + /// This class describes the interface of erasable undirected graphs. + /// It extends \ref BaseGraphComponent with functions for removing + /// nodes and edges from the graph. + /// This concept requires \ref AlterableGraphComponent. template class ErasableGraphComponent : public BAS { public: @@ -1411,23 +1428,22 @@ /// \brief Erase a node from the graph. /// - /// Erase a node from the graph. This function should erase - /// arcs connecting to the node. + /// This function erases the given node from the graph and all edges + /// connected to the node. void erase(const Node&) {} - /// \brief Erase an arc from the graph. + /// \brief Erase an edge from the digraph. /// - /// Erase an arc from the graph. - /// + /// This function erases the given edge from the digraph. void erase(const Edge&) {} template struct Constraints { void constraints() { checkConcept(); - typename _Graph::Node node; + const typename _Graph::Node node(INVALID); graph.erase(node); - typename _Graph::Edge edge; + const typename _Graph::Edge edge(INVALID); graph.erase(edge); } @@ -1435,12 +1451,12 @@ }; }; - /// \brief An empty clearable base digraph class. + /// \brief Skeleton class for clearable directed graphs. /// - /// This class provides beside the core digraph features core clear - /// functions for the digraph structure. The main difference between - /// the base and this interface is that the digraph alterations - /// should handled already on this level. + /// This class describes the interface of clearable directed graphs. + /// It extends \ref BaseDigraphComponent with a function for clearing + /// the digraph. + /// This concept requires \ref AlterableDigraphComponent. template class ClearableDigraphComponent : public BAS { public: @@ -1449,8 +1465,7 @@ /// \brief Erase all nodes and arcs from the digraph. /// - /// Erase all nodes and arcs from the digraph. - /// + /// This function erases all nodes and arcs from the digraph. void clear() {} template @@ -1460,29 +1475,35 @@ digraph.clear(); } - _Digraph digraph; + _Digraph& digraph; }; }; - /// \brief An empty clearable base undirected graph class. + /// \brief Skeleton class for clearable undirected graphs. /// - /// This class provides beside the core undirected graph features - /// core clear functions for the undirected graph structure. The - /// main difference between the base and this interface is that - /// the graph alterations should handled already on this level. + /// This class describes the interface of clearable undirected graphs. + /// It extends \ref BaseGraphComponent with a function for clearing + /// the graph. + /// This concept requires \ref AlterableGraphComponent. template class ClearableGraphComponent : public ClearableDigraphComponent { public: typedef BAS Base; + /// \brief Erase all nodes and edges from the graph. + /// + /// This function erases all nodes and edges from the graph. + void clear() {} + template struct Constraints { void constraints() { - checkConcept, _Graph>(); + checkConcept(); + graph.clear(); } - _Graph graph; + _Graph& graph; }; }; diff -r a3402913cffe -r f63e87b9748e lemon/concepts/heap.h --- a/lemon/concepts/heap.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/concepts/heap.h Tue Apr 21 10:34:49 2009 +0100 @@ -71,9 +71,9 @@ /// The item-int map must be initialized in such way that it assigns /// \c PRE_HEAP (-1) to any element to be put in the heap. enum State { - IN_HEAP = 0, ///< The "in heap" state constant. - PRE_HEAP = -1, ///< The "pre heap" state constant. - POST_HEAP = -2 ///< The "post heap" state constant. + IN_HEAP = 0, ///< = 0. The "in heap" state constant. + PRE_HEAP = -1, ///< = -1. The "pre heap" state constant. + POST_HEAP = -2 ///< = -2. The "post heap" state constant. }; /// \brief The constructor. diff -r a3402913cffe -r f63e87b9748e lemon/connectivity.h --- a/lemon/connectivity.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/connectivity.h Tue Apr 21 10:34:49 2009 +0100 @@ -32,7 +32,7 @@ #include #include -/// \ingroup connectivity +/// \ingroup graph_properties /// \file /// \brief Connectivity algorithms /// @@ -40,7 +40,7 @@ namespace lemon { - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Check whether the given undirected graph is connected. /// @@ -63,7 +63,7 @@ return true; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Count the number of connected components of an undirected graph /// @@ -105,19 +105,21 @@ return compNum; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Find the connected components of an undirected graph /// /// Find the connected components of an undirected graph. /// + /// \image html connected_components.png + /// \image latex connected_components.eps "Connected components" width=\textwidth + /// /// \param graph The graph. It must be undirected. /// \retval compMap A writable node map. The values will be set from 0 to /// the number of the connected components minus one. Each values of the map /// will be set exactly once, the values of a certain component will be /// set continuously. /// \return The number of components - /// template int connectedComponents(const Graph &graph, NodeMap &compMap) { checkConcept(); @@ -227,7 +229,7 @@ } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Check whether the given directed graph is strongly connected. /// @@ -285,7 +287,7 @@ return true; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Count the strongly connected components of a directed graph /// @@ -349,7 +351,7 @@ return compNum; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Find the strongly connected components of a directed graph /// @@ -361,13 +363,15 @@ /// that there is no arc going from a higher numbered component to /// a lower. /// + /// \image html strongly_connected_components.png + /// \image latex strongly_connected_components.eps "Strongly connected components" width=\textwidth + /// /// \param digraph The digraph. /// \retval compMap A writable node map. The values will be set from 0 to /// the number of the strongly connected components minus one. Each value /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components - /// template int stronglyConnectedComponents(const Digraph& digraph, NodeMap& compMap) { checkConcept(); @@ -416,7 +420,7 @@ return compNum; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Find the cut arcs of the strongly connected components. /// @@ -700,7 +704,7 @@ template int countBiNodeConnectedComponents(const Graph& graph); - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Checks the graph is bi-node-connected. /// @@ -715,7 +719,7 @@ return countBiNodeConnectedComponents(graph) <= 1; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Count the biconnected components. /// @@ -750,7 +754,7 @@ return compNum; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Find the bi-node-connected components. /// @@ -759,13 +763,15 @@ /// relation on the undirected edges. Two undirected edge are in relationship /// when they are on same circle. /// + /// \image html node_biconnected_components.png + /// \image latex node_biconnected_components.eps "bi-node-connected components" width=\textwidth + /// /// \param graph The graph. /// \retval compMap A writable uedge map. The values will be set from 0 /// to the number of the biconnected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components. - /// template int biNodeConnectedComponents(const Graph& graph, EdgeMap& compMap) { @@ -793,7 +799,7 @@ return compNum; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Find the bi-node-connected cut nodes. /// @@ -1023,7 +1029,7 @@ template int countBiEdgeConnectedComponents(const Graph& graph); - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Checks that the graph is bi-edge-connected. /// @@ -1038,7 +1044,7 @@ return countBiEdgeConnectedComponents(graph) <= 1; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Count the bi-edge-connected components. /// @@ -1073,7 +1079,7 @@ return compNum; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Find the bi-edge-connected components. /// @@ -1082,13 +1088,15 @@ /// relation on the nodes. Two nodes are in relationship when they are /// connected at least two edge-disjoint paths. /// + /// \image html edge_biconnected_components.png + /// \image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth + /// /// \param graph The graph. /// \retval compMap A writable node map. The values will be set from 0 to /// the number of the biconnected components minus one. Each values /// of the map will be set exactly once, the values of a certain component /// will be set continuously. /// \return The number of components. - /// template int biEdgeConnectedComponents(const Graph& graph, NodeMap& compMap) { checkConcept(); @@ -1115,7 +1123,7 @@ return compNum; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Find the bi-edge-connected cut edges. /// @@ -1179,7 +1187,7 @@ } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Sort the nodes of a DAG into topolgical order. /// @@ -1218,7 +1226,7 @@ } } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Sort the nodes of a DAG into topolgical order. /// @@ -1273,7 +1281,7 @@ return true; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Check that the given directed graph is a DAG. /// @@ -1315,7 +1323,7 @@ return true; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Check that the given undirected graph is acyclic. /// @@ -1349,7 +1357,7 @@ return true; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Check that the given undirected graph is tree. /// @@ -1441,7 +1449,7 @@ }; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Check if the given undirected graph is bipartite or not /// @@ -1478,7 +1486,7 @@ return true; } - /// \ingroup connectivity + /// \ingroup graph_properties /// /// \brief Check if the given undirected graph is bipartite or not /// @@ -1486,6 +1494,10 @@ /// or not. The \ref Bfs algorithm is used to calculate the result. /// During the execution, the \c partMap will be set as the two /// partitions of the graph. + /// + /// \image html bipartite_partitions.png + /// \image latex bipartite_partitions.eps "Bipartite partititions" width=\textwidth + /// /// \param graph The undirected graph. /// \retval partMap A writable bool map of nodes. It will be set as the /// two partitions of the graph. diff -r a3402913cffe -r f63e87b9748e lemon/core.h --- a/lemon/core.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/core.h Tue Apr 21 10:34:49 2009 +0100 @@ -1315,27 +1315,27 @@ virtual void clear() { for(NodeIt n(_g);n!=INVALID;++n) { - _head.set(n, INVALID); + _head[n] = INVALID; } } void insert(Arc arc) { Node s = _g.source(arc); Node t = _g.target(arc); - _left.set(arc, INVALID); - _right.set(arc, INVALID); + _left[arc] = INVALID; + _right[arc] = INVALID; Arc e = _head[s]; if (e == INVALID) { - _head.set(s, arc); - _parent.set(arc, INVALID); + _head[s] = arc; + _parent[arc] = INVALID; return; } while (true) { if (t < _g.target(e)) { if (_left[e] == INVALID) { - _left.set(e, arc); - _parent.set(arc, e); + _left[e] = arc; + _parent[arc] = e; splay(arc); return; } else { @@ -1343,8 +1343,8 @@ } } else { if (_right[e] == INVALID) { - _right.set(e, arc); - _parent.set(arc, e); + _right[e] = arc; + _parent[arc] = e; splay(arc); return; } else { @@ -1357,27 +1357,27 @@ void remove(Arc arc) { if (_left[arc] == INVALID) { if (_right[arc] != INVALID) { - _parent.set(_right[arc], _parent[arc]); + _parent[_right[arc]] = _parent[arc]; } if (_parent[arc] != INVALID) { if (_left[_parent[arc]] == arc) { - _left.set(_parent[arc], _right[arc]); + _left[_parent[arc]] = _right[arc]; } else { - _right.set(_parent[arc], _right[arc]); + _right[_parent[arc]] = _right[arc]; } } else { - _head.set(_g.source(arc), _right[arc]); + _head[_g.source(arc)] = _right[arc]; } } else if (_right[arc] == INVALID) { - _parent.set(_left[arc], _parent[arc]); + _parent[_left[arc]] = _parent[arc]; if (_parent[arc] != INVALID) { if (_left[_parent[arc]] == arc) { - _left.set(_parent[arc], _left[arc]); + _left[_parent[arc]] = _left[arc]; } else { - _right.set(_parent[arc], _left[arc]); + _right[_parent[arc]] = _left[arc]; } } else { - _head.set(_g.source(arc), _left[arc]); + _head[_g.source(arc)] = _left[arc]; } } else { Arc e = _left[arc]; @@ -1387,38 +1387,38 @@ e = _right[e]; } Arc s = _parent[e]; - _right.set(_parent[e], _left[e]); + _right[_parent[e]] = _left[e]; if (_left[e] != INVALID) { - _parent.set(_left[e], _parent[e]); + _parent[_left[e]] = _parent[e]; } - _left.set(e, _left[arc]); - _parent.set(_left[arc], e); - _right.set(e, _right[arc]); - _parent.set(_right[arc], e); + _left[e] = _left[arc]; + _parent[_left[arc]] = e; + _right[e] = _right[arc]; + _parent[_right[arc]] = e; - _parent.set(e, _parent[arc]); + _parent[e] = _parent[arc]; if (_parent[arc] != INVALID) { if (_left[_parent[arc]] == arc) { - _left.set(_parent[arc], e); + _left[_parent[arc]] = e; } else { - _right.set(_parent[arc], e); + _right[_parent[arc]] = e; } } splay(s); } else { - _right.set(e, _right[arc]); - _parent.set(_right[arc], e); - _parent.set(e, _parent[arc]); + _right[e] = _right[arc]; + _parent[_right[arc]] = e; + _parent[e] = _parent[arc]; if (_parent[arc] != INVALID) { if (_left[_parent[arc]] == arc) { - _left.set(_parent[arc], e); + _left[_parent[arc]] = e; } else { - _right.set(_parent[arc], e); + _right[_parent[arc]] = e; } } else { - _head.set(_g.source(arc), e); + _head[_g.source(arc)] = e; } } } @@ -1430,17 +1430,17 @@ Arc me=v[m]; if (a < m) { Arc left = refreshRec(v,a,m-1); - _left.set(me, left); - _parent.set(left, me); + _left[me] = left; + _parent[left] = me; } else { - _left.set(me, INVALID); + _left[me] = INVALID; } if (m < b) { Arc right = refreshRec(v,m+1,b); - _right.set(me, right); - _parent.set(right, me); + _right[me] = right; + _parent[right] = me; } else { - _right.set(me, INVALID); + _right[me] = INVALID; } return me; } @@ -1452,46 +1452,46 @@ if (!v.empty()) { std::sort(v.begin(),v.end(),ArcLess(_g)); Arc head = refreshRec(v,0,v.size()-1); - _head.set(n, head); - _parent.set(head, INVALID); + _head[n] = head; + _parent[head] = INVALID; } - else _head.set(n, INVALID); + else _head[n] = INVALID; } } void zig(Arc v) { Arc w = _parent[v]; - _parent.set(v, _parent[w]); - _parent.set(w, v); - _left.set(w, _right[v]); - _right.set(v, w); + _parent[v] = _parent[w]; + _parent[w] = v; + _left[w] = _right[v]; + _right[v] = w; if (_parent[v] != INVALID) { if (_right[_parent[v]] == w) { - _right.set(_parent[v], v); + _right[_parent[v]] = v; } else { - _left.set(_parent[v], v); + _left[_parent[v]] = v; } } if (_left[w] != INVALID){ - _parent.set(_left[w], w); + _parent[_left[w]] = w; } } void zag(Arc v) { Arc w = _parent[v]; - _parent.set(v, _parent[w]); - _parent.set(w, v); - _right.set(w, _left[v]); - _left.set(v, w); + _parent[v] = _parent[w]; + _parent[w] = v; + _right[w] = _left[v]; + _left[v] = w; if (_parent[v] != INVALID){ if (_left[_parent[v]] == w) { - _left.set(_parent[v], v); + _left[_parent[v]] = v; } else { - _right.set(_parent[v], v); + _right[_parent[v]] = v; } } if (_right[w] != INVALID){ - _parent.set(_right[w], w); + _parent[_right[w]] = w; } } diff -r a3402913cffe -r f63e87b9748e lemon/cplex.cc --- a/lemon/cplex.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/cplex.cc Tue Apr 21 10:34:49 2009 +0100 @@ -72,12 +72,14 @@ CplexBase::CplexBase() : LpBase() { int status; _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem"); + messageLevel(MESSAGE_NOTHING); } CplexBase::CplexBase(const CplexEnv& env) : LpBase(), _env(env) { int status; _prob = CPXcreateprob(cplexEnv(), &status, "Cplex problem"); + messageLevel(MESSAGE_NOTHING); } CplexBase::CplexBase(const CplexBase& cplex) @@ -86,6 +88,7 @@ _prob = CPXcloneprob(cplexEnv(), cplex._prob, &status); rows = cplex.rows; cols = cplex.cols; + messageLevel(MESSAGE_NOTHING); } CplexBase::~CplexBase() { @@ -438,6 +441,25 @@ cols.clear(); } + void CplexBase::_messageLevel(MessageLevel level) { + switch (level) { + case MESSAGE_NOTHING: + _message_enabled = false; + break; + case MESSAGE_ERROR: + case MESSAGE_WARNING: + case MESSAGE_NORMAL: + case MESSAGE_VERBOSE: + _message_enabled = true; + break; + } + } + + void CplexBase::_applyMessageLevel() { + CPXsetintparam(cplexEnv(), CPX_PARAM_SCRIND, + _message_enabled ? CPX_ON : CPX_OFF); + } + // CplexLp members CplexLp::CplexLp() @@ -507,21 +529,25 @@ CplexLp::SolveExitStatus CplexLp::_solve() { _clear_temporals(); + _applyMessageLevel(); return convertStatus(CPXlpopt(cplexEnv(), _prob)); } CplexLp::SolveExitStatus CplexLp::solvePrimal() { _clear_temporals(); + _applyMessageLevel(); return convertStatus(CPXprimopt(cplexEnv(), _prob)); } CplexLp::SolveExitStatus CplexLp::solveDual() { _clear_temporals(); + _applyMessageLevel(); return convertStatus(CPXdualopt(cplexEnv(), _prob)); } CplexLp::SolveExitStatus CplexLp::solveBarrier() { _clear_temporals(); + _applyMessageLevel(); return convertStatus(CPXbaropt(cplexEnv(), _prob)); } @@ -600,7 +626,7 @@ return _dual_ray[i]; } - //7.5-os cplex statusai (Vigyazat: a 9.0-asei masok!) + // Cplex 7.0 status values // This table lists the statuses, returned by the CPXgetstat() // routine, for solutions to LP problems or mixed integer problems. If // no solution exists, the return value is zero. @@ -647,7 +673,7 @@ // 20 CPX_PIVOT // User pivot used // - // Ezeket hova tegyem: + // Pending return values // ??case CPX_ABORT_DUAL_INFEAS // ??case CPX_ABORT_CROSSOVER // ??case CPX_INForUNBD @@ -718,7 +744,6 @@ #else statusSwitch(cplexEnv(),stat); //CPXgetstat(cplexEnv(), _prob); - //printf("A primal status: %d, CPX_OPTIMAL=%d \n",stat,CPX_OPTIMAL); switch (stat) { case 0: return UNDEFINED; //Undefined @@ -751,7 +776,7 @@ #endif } - //9.0-as cplex verzio statusai + // Cplex 9.0 status values // CPX_STAT_ABORT_DUAL_OBJ_LIM // CPX_STAT_ABORT_IT_LIM // CPX_STAT_ABORT_OBJ_LIM @@ -864,6 +889,7 @@ CplexMip::SolveExitStatus CplexMip::_solve() { int status; + _applyMessageLevel(); status = CPXmipopt (cplexEnv(), _prob); if (status==0) return SOLVED; diff -r a3402913cffe -r f63e87b9748e lemon/cplex.h --- a/lemon/cplex.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/cplex.h Tue Apr 21 10:34:49 2009 +0100 @@ -144,14 +144,29 @@ virtual void _clear(); + virtual void _messageLevel(MessageLevel level); + void _applyMessageLevel(); + + bool _message_enabled; + public: /// Returns the used \c CplexEnv instance const CplexEnv& env() const { return _env; } + + /// \brief Returns the const cpxenv pointer /// + /// \note The cpxenv might be destructed with the solver. const cpxenv* cplexEnv() const { return _env.cplexEnv(); } + /// \brief Returns the const cpxenv pointer + /// + /// \note The cpxenv might be destructed with the solver. + cpxenv* cplexEnv() { return _env.cplexEnv(); } + + /// Returns the cplex problem object cpxlp* cplexLp() { return _prob; } + /// Returns the cplex problem object const cpxlp* cplexLp() const { return _prob; } }; diff -r a3402913cffe -r f63e87b9748e lemon/dfs.h --- a/lemon/dfs.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/dfs.h Tue Apr 21 10:34:49 2009 +0100 @@ -206,7 +206,7 @@ typedef Dfs Create; - ///\name Named template parameters + ///\name Named Template Parameters ///@{ diff -r a3402913cffe -r f63e87b9748e lemon/dijkstra.h --- a/lemon/dijkstra.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/dijkstra.h Tue Apr 21 10:34:49 2009 +0100 @@ -286,7 +286,7 @@ typedef Dijkstra Create; - ///\name Named template parameters + ///\name Named Template Parameters ///@{ diff -r a3402913cffe -r f63e87b9748e lemon/dimacs.h --- a/lemon/dimacs.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/dimacs.h Tue Apr 21 10:34:49 2009 +0100 @@ -37,11 +37,16 @@ /// DIMACS file type descriptor. struct DimacsDescriptor { - ///File type enum - enum Type - { - NONE, MIN, MAX, SP, MAT - }; + ///\brief DIMACS file type enum + /// + ///DIMACS file type enum. + enum Type { + NONE, ///< Undefined type. + MIN, ///< DIMACS file type for minimum cost flow problems. + MAX, ///< DIMACS file type for maximum flow problems. + SP, ///< DIMACS file type for shostest path problems. + MAT ///< DIMACS file type for plain graphs and matching problems. + }; ///The file type Type type; ///The number of nodes in the graph @@ -49,16 +54,16 @@ ///The number of edges in the graph int edgeNum; int lineShift; - /// Constructor. Sets the type to NONE. + ///Constructor. It sets the type to \c NONE. DimacsDescriptor() : type(NONE) {} }; ///Discover the type of a DIMACS file - ///It starts seeking the beginning of the file for the problem type - ///and size info. The found data is returned in a special struct - ///that can be evaluated and passed to the appropriate reader - ///function. + ///This function starts seeking the beginning of the given file for the + ///problem type and size info. + ///The found data is returned in a special struct that can be evaluated + ///and passed to the appropriate reader function. DimacsDescriptor dimacsType(std::istream& is) { DimacsDescriptor r; @@ -96,8 +101,7 @@ } - - /// DIMACS minimum cost flow reader function. + /// \brief DIMACS minimum cost flow reader function. /// /// This function reads a minimum cost flow instance from DIMACS format, /// i.e. from a DIMACS file having a line starting with @@ -253,7 +257,7 @@ } } - /// DIMACS maximum flow reader function. + /// \brief DIMACS maximum flow reader function. /// /// This function reads a maximum flow instance from DIMACS format, /// i.e. from a DIMACS file having a line starting with @@ -287,7 +291,7 @@ _readDimacs(is,g,capacity,s,t,infty,desc); } - /// DIMACS shortest path reader function. + /// \brief DIMACS shortest path reader function. /// /// This function reads a shortest path instance from DIMACS format, /// i.e. from a DIMACS file having a line starting with @@ -313,7 +317,7 @@ _readDimacs(is, g, length, s, t, 0, desc); } - /// DIMACS capacitated digraph reader function. + /// \brief DIMACS capacitated digraph reader function. /// /// This function reads an arc capacitated digraph instance from /// DIMACS 'max' or 'sp' format. @@ -359,11 +363,11 @@ g.addArc(s,t); } - /// DIMACS plain (di)graph reader function. + /// \brief DIMACS plain (di)graph reader function. /// - /// This function reads a (di)graph without any designated nodes and - /// maps from DIMACS format, i.e. from DIMACS files having a line - /// starting with + /// This function reads a plain (di)graph without any designated nodes + /// and maps (e.g. a matching instance) from DIMACS format, i.e. from + /// DIMACS files having a line starting with /// \code /// p mat /// \endcode diff -r a3402913cffe -r f63e87b9748e lemon/elevator.h --- a/lemon/elevator.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/elevator.h Tue Apr 21 10:34:49 2009 +0100 @@ -76,7 +76,7 @@ void copy(Item i, Vit p) { - _where.set(*p=i,p); + _where[*p=i] = p; } void copy(Vit s, Vit p) { @@ -84,15 +84,15 @@ { Item i=*s; *p=i; - _where.set(i,p); + _where[i] = p; } } void swap(Vit i, Vit j) { Item ti=*i; Vit ct = _where[ti]; - _where.set(ti,_where[*i=*j]); - _where.set(*j,ct); + _where[ti] = _where[*i=*j]; + _where[*j] = ct; *j=ti; } @@ -226,7 +226,7 @@ void liftHighestActive() { Item it = *_last_active[_highest_active]; - _level.set(it,_level[it]+1); + ++_level[it]; swap(_last_active[_highest_active]--,_last_active[_highest_active+1]); --_first[++_highest_active]; } @@ -249,7 +249,7 @@ --_last_active[l]; } copy(li,_first[new_level]); - _level.set(li,new_level); + _level[li] = new_level; _highest_active=new_level; } @@ -269,7 +269,7 @@ } copy(li,_first[_max_level]); --_last_active[_max_level]; - _level.set(li,_max_level); + _level[li] = _max_level; while(_highest_active>=0 && _last_active[_highest_active]<_first[_highest_active]) @@ -299,7 +299,7 @@ Item liftActiveOn(int level) { Item it =*_last_active[level]; - _level.set(it,_level[it]+1); + ++_level[it]; swap(_last_active[level]--, --_first[level+1]); if (level+1>_highest_active) ++_highest_active; } @@ -319,7 +319,7 @@ copy(--_first[l+1], _last_active[l]--); } copy(ai,_first[new_level]); - _level.set(ai,new_level); + _level[ai] = new_level; if (new_level>_highest_active) _highest_active=new_level; } @@ -339,7 +339,7 @@ } copy(ai,_first[_max_level]); --_last_active[_max_level]; - _level.set(ai,_max_level); + _level[ai] = _max_level; if (_highest_active==level) { while(_highest_active>=0 && @@ -370,7 +370,7 @@ copy(--_first[l+1],_last_active[l]--); } copy(i,_first[new_level]); - _level.set(i,new_level); + _level[i] = new_level; if(new_level>_highest_active) _highest_active=new_level; } @@ -382,7 +382,7 @@ ///only if you really know what it is for. ///\pre The item is on the top level. void dirtyTopButOne(Item i) { - _level.set(i,_max_level - 1); + _level[i] = _max_level - 1; } ///Lift all items on and above the given level to the top level. @@ -394,7 +394,7 @@ const Vit f=_first[l]; const Vit tl=_first[_max_level]; for(Vit i=f;i!=tl;++i) - _level.set(*i,_max_level); + _level[*i] = _max_level; for(int i=l;i<=_max_level;i++) { _first[i]=f; @@ -433,8 +433,8 @@ for(typename ItemSetTraits::ItemIt i(_g);i!=INVALID;++i) { *n=i; - _where.set(i,n); - _level.set(i,_max_level); + _where[i] = n; + _level[i] = _max_level; ++n; } } @@ -443,7 +443,7 @@ void initAddItem(Item i) { swap(_where[i],_init_num); - _level.set(i,_init_lev); + _level[i] = _init_lev; ++_init_num; } @@ -551,7 +551,7 @@ ///Activate item \c i. ///\pre Item \c i shouldn't be active before. void activate(Item i) { - _active.set(i, true); + _active[i] = true; int level = _level[i]; if (level > _highest_active) { @@ -560,16 +560,16 @@ if (_prev[i] == INVALID || _active[_prev[i]]) return; //unlace - _next.set(_prev[i], _next[i]); + _next[_prev[i]] = _next[i]; if (_next[i] != INVALID) { - _prev.set(_next[i], _prev[i]); + _prev[_next[i]] = _prev[i]; } else { _last[level] = _prev[i]; } //lace - _next.set(i, _first[level]); - _prev.set(_first[level], i); - _prev.set(i, INVALID); + _next[i] = _first[level]; + _prev[_first[level]] = i; + _prev[i] = INVALID; _first[level] = i; } @@ -579,23 +579,23 @@ ///Deactivate item \c i. ///\pre Item \c i must be active before. void deactivate(Item i) { - _active.set(i, false); + _active[i] = false; int level = _level[i]; if (_next[i] == INVALID || !_active[_next[i]]) goto find_highest_level; //unlace - _prev.set(_next[i], _prev[i]); + _prev[_next[i]] = _prev[i]; if (_prev[i] != INVALID) { - _next.set(_prev[i], _next[i]); + _next[_prev[i]] = _next[i]; } else { _first[_level[i]] = _next[i]; } //lace - _prev.set(i, _last[level]); - _next.set(_last[level], i); - _next.set(i, INVALID); + _prev[i] = _last[level]; + _next[_last[level]] = i; + _next[i] = INVALID; _last[level] = i; find_highest_level: @@ -685,21 +685,21 @@ void liftHighestActive() { Item i = _first[_highest_active]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[_highest_active] = _next[i]; } else { _first[_highest_active] = INVALID; _last[_highest_active] = INVALID; } - _level.set(i, ++_highest_active); + _level[i] = ++_highest_active; if (_first[_highest_active] == INVALID) { _first[_highest_active] = i; _last[_highest_active] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[_highest_active], i); - _next.set(i, _first[_highest_active]); + _prev[_first[_highest_active]] = i; + _next[i] = _first[_highest_active]; _first[_highest_active] = i; } } @@ -714,20 +714,20 @@ void liftHighestActive(int new_level) { Item i = _first[_highest_active]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[_highest_active] = _next[i]; } else { _first[_highest_active] = INVALID; _last[_highest_active] = INVALID; } - _level.set(i, _highest_active = new_level); + _level[i] = _highest_active = new_level; if (_first[_highest_active] == INVALID) { _first[_highest_active] = _last[_highest_active] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[_highest_active], i); - _next.set(i, _first[_highest_active]); + _prev[_first[_highest_active]] = i; + _next[i] = _first[_highest_active]; _first[_highest_active] = i; } } @@ -738,9 +738,9 @@ ///deactivate it. void liftHighestActiveToTop() { Item i = _first[_highest_active]; - _level.set(i, _max_level); + _level[i] = _max_level; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[_highest_active] = _next[i]; } else { _first[_highest_active] = INVALID; @@ -774,20 +774,20 @@ { Item i = _first[l]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[l] = _next[i]; } else { _first[l] = INVALID; _last[l] = INVALID; } - _level.set(i, ++l); + _level[i] = ++l; if (_first[l] == INVALID) { _first[l] = _last[l] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[l], i); - _next.set(i, _first[l]); + _prev[_first[l]] = i; + _next[i] = _first[l]; _first[l] = i; } if (_highest_active < l) { @@ -803,20 +803,20 @@ { Item i = _first[l]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[l] = _next[i]; } else { _first[l] = INVALID; _last[l] = INVALID; } - _level.set(i, l = new_level); + _level[i] = l = new_level; if (_first[l] == INVALID) { _first[l] = _last[l] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[l], i); - _next.set(i, _first[l]); + _prev[_first[l]] = i; + _next[i] = _first[l]; _first[l] = i; } if (_highest_active < l) { @@ -832,13 +832,13 @@ { Item i = _first[l]; if (_next[i] != INVALID) { - _prev.set(_next[i], INVALID); + _prev[_next[i]] = INVALID; _first[l] = _next[i]; } else { _first[l] = INVALID; _last[l] = INVALID; } - _level.set(i, _max_level); + _level[i] = _max_level; if (l == _highest_active) { while (_highest_active >= 0 && activeFree(_highest_active)) --_highest_active; @@ -856,23 +856,23 @@ /// void lift(Item i, int new_level) { if (_next[i] != INVALID) { - _prev.set(_next[i], _prev[i]); + _prev[_next[i]] = _prev[i]; } else { _last[new_level] = _prev[i]; } if (_prev[i] != INVALID) { - _next.set(_prev[i], _next[i]); + _next[_prev[i]] = _next[i]; } else { _first[new_level] = _next[i]; } - _level.set(i, new_level); + _level[i] = new_level; if (_first[new_level] == INVALID) { _first[new_level] = _last[new_level] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(_first[new_level], i); - _next.set(i, _first[new_level]); + _prev[_first[new_level]] = i; + _next[i] = _first[new_level]; _first[new_level] = i; } if (_highest_active < new_level) { @@ -888,7 +888,7 @@ ///only if you really know what it is for. ///\pre The item is on the top level. void dirtyTopButOne(Item i) { - _level.set(i, _max_level - 1); + _level[i] = _max_level - 1; } ///Lift all items on and above the given level to the top level. @@ -899,7 +899,7 @@ for (int i = l + 1; _first[i] != INVALID; ++i) { Item n = _first[i]; while (n != INVALID) { - _level.set(n, _max_level); + _level[n] = _max_level; n = _next[n]; } _first[i] = INVALID; @@ -937,23 +937,23 @@ _init_level = 0; for(typename ItemSetTraits::ItemIt i(_graph); i != INVALID; ++i) { - _level.set(i, _max_level); - _active.set(i, false); + _level[i] = _max_level; + _active[i] = false; } } ///Add an item to the current level. void initAddItem(Item i) { - _level.set(i, _init_level); + _level[i] = _init_level; if (_last[_init_level] == INVALID) { _first[_init_level] = i; _last[_init_level] = i; - _prev.set(i, INVALID); - _next.set(i, INVALID); + _prev[i] = INVALID; + _next[i] = INVALID; } else { - _prev.set(i, _last[_init_level]); - _next.set(i, INVALID); - _next.set(_last[_init_level], i); + _prev[i] = _last[_init_level]; + _next[i] = INVALID; + _next[_last[_init_level]] = i; _last[_init_level] = i; } } diff -r a3402913cffe -r f63e87b9748e lemon/euler.h --- a/lemon/euler.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/euler.h Tue Apr 21 10:34:49 2009 +0100 @@ -24,7 +24,7 @@ #include #include -/// \ingroup graph_prop +/// \ingroup graph_properties /// \file /// \brief Euler tour /// @@ -36,7 +36,7 @@ ///Euler iterator for digraphs. - /// \ingroup graph_prop + /// \ingroup graph_properties ///This iterator converts to the \c Arc type of the digraph and using ///operator ++, it provides an Euler tour of a \e directed ///graph (if there exists). @@ -123,7 +123,7 @@ ///Euler iterator for graphs. - /// \ingroup graph_prop + /// \ingroup graph_properties ///This iterator converts to the \c Arc (or \c Edge) ///type of the digraph and using ///operator ++, it provides an Euler tour of an undirected @@ -228,7 +228,7 @@ ///Checks if the graph is Eulerian - /// \ingroup graph_prop + /// \ingroup graph_properties ///Checks if the graph is Eulerian. It works for both directed and undirected ///graphs. ///\note By definition, a digraph is called \e Eulerian if diff -r a3402913cffe -r f63e87b9748e lemon/full_graph.h --- a/lemon/full_graph.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/full_graph.h Tue Apr 21 10:34:49 2009 +0100 @@ -157,9 +157,8 @@ /// can neither add nor delete either arcs or nodes, and it needs /// constant space in memory. /// - /// This class conforms to the \ref concepts::Digraph "Digraph" concept - /// and it also has an important extra feature that its maps are - /// real \ref concepts::ReferenceMap "reference map"s. + /// This class fully conforms to the \ref concepts::Digraph + /// "Digraph concept". /// /// The \c FullDigraph and \c FullGraph classes are very similar, /// but there are two differences. While this class conforms only @@ -527,9 +526,7 @@ /// add nor delete either edges or nodes, and it needs constant /// space in memory. /// - /// This class conforms to the \ref concepts::Graph "Graph" concept - /// and it also has an important extra feature that its maps are - /// real \ref concepts::ReferenceMap "reference map"s. + /// This class fully conforms to the \ref concepts::Graph "Graph concept". /// /// The \c FullGraph and \c FullDigraph classes are very similar, /// but there are two differences. While the \c FullDigraph class diff -r a3402913cffe -r f63e87b9748e lemon/glpk.cc --- a/lemon/glpk.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/glpk.cc Tue Apr 21 10:34:49 2009 +0100 @@ -31,6 +31,7 @@ GlpkBase::GlpkBase() : LpBase() { lp = glp_create_prob(); glp_create_index(lp); + messageLevel(MESSAGE_NOTHING); } GlpkBase::GlpkBase(const GlpkBase &other) : LpBase() { @@ -39,6 +40,7 @@ glp_create_index(lp); rows = other.rows; cols = other.cols; + messageLevel(MESSAGE_NOTHING); } GlpkBase::~GlpkBase() { @@ -526,19 +528,37 @@ glp_free_env(); } + void GlpkBase::_messageLevel(MessageLevel level) { + switch (level) { + case MESSAGE_NOTHING: + _message_level = GLP_MSG_OFF; + break; + case MESSAGE_ERROR: + _message_level = GLP_MSG_ERR; + break; + case MESSAGE_WARNING: + _message_level = GLP_MSG_ERR; + break; + case MESSAGE_NORMAL: + _message_level = GLP_MSG_ON; + break; + case MESSAGE_VERBOSE: + _message_level = GLP_MSG_ALL; + break; + } + } + GlpkBase::FreeEnvHelper GlpkBase::freeEnvHelper; // GlpkLp members GlpkLp::GlpkLp() : LpBase(), LpSolver(), GlpkBase() { - messageLevel(MESSAGE_NO_OUTPUT); presolver(false); } GlpkLp::GlpkLp(const GlpkLp& other) : LpBase(other), LpSolver(other), GlpkBase(other) { - messageLevel(MESSAGE_NO_OUTPUT); presolver(false); } @@ -562,20 +582,7 @@ glp_smcp smcp; glp_init_smcp(&smcp); - switch (_message_level) { - case MESSAGE_NO_OUTPUT: - smcp.msg_lev = GLP_MSG_OFF; - break; - case MESSAGE_ERROR_MESSAGE: - smcp.msg_lev = GLP_MSG_ERR; - break; - case MESSAGE_NORMAL_OUTPUT: - smcp.msg_lev = GLP_MSG_ON; - break; - case MESSAGE_FULL_OUTPUT: - smcp.msg_lev = GLP_MSG_ALL; - break; - } + smcp.msg_lev = _message_level; smcp.presolve = _presolve; // If the basis is not valid we get an error return value. @@ -604,20 +611,7 @@ glp_smcp smcp; glp_init_smcp(&smcp); - switch (_message_level) { - case MESSAGE_NO_OUTPUT: - smcp.msg_lev = GLP_MSG_OFF; - break; - case MESSAGE_ERROR_MESSAGE: - smcp.msg_lev = GLP_MSG_ERR; - break; - case MESSAGE_NORMAL_OUTPUT: - smcp.msg_lev = GLP_MSG_ON; - break; - case MESSAGE_FULL_OUTPUT: - smcp.msg_lev = GLP_MSG_ALL; - break; - } + smcp.msg_lev = _message_level; smcp.meth = GLP_DUAL; smcp.presolve = _presolve; @@ -858,20 +852,14 @@ _presolve = presolve; } - void GlpkLp::messageLevel(MessageLevel m) { - _message_level = m; - } - // GlpkMip members GlpkMip::GlpkMip() : LpBase(), MipSolver(), GlpkBase() { - messageLevel(MESSAGE_NO_OUTPUT); } GlpkMip::GlpkMip(const GlpkMip& other) : LpBase(), MipSolver(), GlpkBase(other) { - messageLevel(MESSAGE_NO_OUTPUT); } void GlpkMip::_setColType(int i, GlpkMip::ColTypes col_type) { @@ -900,20 +888,7 @@ glp_smcp smcp; glp_init_smcp(&smcp); - switch (_message_level) { - case MESSAGE_NO_OUTPUT: - smcp.msg_lev = GLP_MSG_OFF; - break; - case MESSAGE_ERROR_MESSAGE: - smcp.msg_lev = GLP_MSG_ERR; - break; - case MESSAGE_NORMAL_OUTPUT: - smcp.msg_lev = GLP_MSG_ON; - break; - case MESSAGE_FULL_OUTPUT: - smcp.msg_lev = GLP_MSG_ALL; - break; - } + smcp.msg_lev = _message_level; smcp.meth = GLP_DUAL; // If the basis is not valid we get an error return value. @@ -938,20 +913,7 @@ glp_iocp iocp; glp_init_iocp(&iocp); - switch (_message_level) { - case MESSAGE_NO_OUTPUT: - iocp.msg_lev = GLP_MSG_OFF; - break; - case MESSAGE_ERROR_MESSAGE: - iocp.msg_lev = GLP_MSG_ERR; - break; - case MESSAGE_NORMAL_OUTPUT: - iocp.msg_lev = GLP_MSG_ON; - break; - case MESSAGE_FULL_OUTPUT: - iocp.msg_lev = GLP_MSG_ALL; - break; - } + iocp.msg_lev = _message_level; if (glp_intopt(lp, &iocp) != 0) return UNSOLVED; return SOLVED; @@ -1002,8 +964,4 @@ const char* GlpkMip::_solverName() const { return "GlpkMip"; } - void GlpkMip::messageLevel(MessageLevel m) { - _message_level = m; - } - } //END OF NAMESPACE LEMON diff -r a3402913cffe -r f63e87b9748e lemon/glpk.h --- a/lemon/glpk.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/glpk.h Tue Apr 21 10:34:49 2009 +0100 @@ -100,6 +100,8 @@ virtual void _clear(); + virtual void _messageLevel(MessageLevel level); + private: static void freeEnv(); @@ -111,6 +113,10 @@ }; static FreeEnvHelper freeEnvHelper; + + protected: + + int _message_level; public: @@ -191,30 +197,6 @@ ///The presolver is off by default. void presolver(bool presolve); - ///Enum for \c messageLevel() parameter - enum MessageLevel { - /// no output (default value) - MESSAGE_NO_OUTPUT = 0, - /// error messages only - MESSAGE_ERROR_MESSAGE = 1, - /// normal output - MESSAGE_NORMAL_OUTPUT = 2, - /// full output (includes informational messages) - MESSAGE_FULL_OUTPUT = 3 - }; - - private: - - MessageLevel _message_level; - - public: - - ///Set the verbosity of the messages - - ///Set the verbosity of the messages - /// - ///\param m is the level of the messages output by the solver routines. - void messageLevel(MessageLevel m); }; /// \brief Interface for the GLPK MIP solver @@ -244,30 +226,6 @@ virtual Value _getSol(int i) const; virtual Value _getSolValue() const; - ///Enum for \c messageLevel() parameter - enum MessageLevel { - /// no output (default value) - MESSAGE_NO_OUTPUT = 0, - /// error messages only - MESSAGE_ERROR_MESSAGE = 1, - /// normal output - MESSAGE_NORMAL_OUTPUT = 2, - /// full output (includes informational messages) - MESSAGE_FULL_OUTPUT = 3 - }; - - private: - - MessageLevel _message_level; - - public: - - ///Set the verbosity of the messages - - ///Set the verbosity of the messages - /// - ///\param m is the level of the messages output by the solver routines. - void messageLevel(MessageLevel m); }; diff -r a3402913cffe -r f63e87b9748e lemon/gomory_hu.h --- a/lemon/gomory_hu.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/gomory_hu.h Tue Apr 21 10:34:49 2009 +0100 @@ -42,24 +42,22 @@ /// in this tree has the same weight as the minimum cut in the graph /// between these nodes. Moreover the components obtained by removing /// this edge from the tree determine the corresponding minimum cut. - /// /// Therefore once this tree is computed, the minimum cut between any pair /// of nodes can easily be obtained. /// /// The algorithm calculates \e n-1 distinct minimum cuts (currently with - /// the \ref Preflow algorithm), therefore the algorithm has - /// \f$(O(n^3\sqrt{e})\f$ overall time complexity. It calculates a - /// rooted Gomory-Hu tree, its structure and the weights can be obtained - /// by \c predNode(), \c predValue() and \c rootDist(). - /// - /// The members \c minCutMap() and \c minCutValue() calculate + /// the \ref Preflow algorithm), thus it has \f$O(n^3\sqrt{e})\f$ overall + /// time complexity. It calculates a rooted Gomory-Hu tree. + /// The structure of the tree and the edge weights can be + /// obtained using \c predNode(), \c predValue() and \c rootDist(). + /// The functions \c minCutMap() and \c minCutValue() calculate /// the minimum cut and the minimum cut value between any two nodes /// in the graph. You can also list (iterate on) the nodes and the /// edges of the cuts using \c MinCutNodeIt and \c MinCutEdgeIt. /// /// \tparam GR The type of the undirected graph the algorithm runs on. - /// \tparam CAP The type of the edge map describing the edge capacities. - /// It is \ref concepts::Graph::EdgeMap "GR::EdgeMap" by default. + /// \tparam CAP The type of the edge map containing the capacities. + /// The default map type is \ref concepts::Graph::EdgeMap "GR::EdgeMap". #ifdef DOXYGEN template @@ -70,9 +68,9 @@ class GomoryHu { public: - /// The graph type + /// The graph type of the algorithm typedef GR Graph; - /// The type of the edge capacity map + /// The capacity map type of the algorithm typedef CAP Capacity; /// The value type of capacities typedef typename Capacity::Value Value; @@ -117,7 +115,7 @@ /// \brief Constructor /// - /// Constructor + /// Constructor. /// \param graph The undirected graph the algorithm runs on. /// \param capacity The edge capacity map. GomoryHu(const Graph& graph, const Capacity& capacity) @@ -130,7 +128,7 @@ /// \brief Destructor /// - /// Destructor + /// Destructor. ~GomoryHu() { destroyStructures(); } @@ -143,11 +141,11 @@ _root = NodeIt(_graph); for (NodeIt n(_graph); n != INVALID; ++n) { - _pred->set(n, _root); - _order->set(n, -1); + (*_pred)[n] = _root; + (*_order)[n] = -1; } - _pred->set(_root, INVALID); - _weight->set(_root, std::numeric_limits::max()); + (*_pred)[_root] = INVALID; + (*_weight)[_root] = std::numeric_limits::max(); } @@ -164,22 +162,22 @@ fa.runMinCut(); - _weight->set(n, fa.flowValue()); + (*_weight)[n] = fa.flowValue(); for (NodeIt nn(_graph); nn != INVALID; ++nn) { if (nn != n && fa.minCut(nn) && (*_pred)[nn] == pn) { - _pred->set(nn, n); + (*_pred)[nn] = n; } } if ((*_pred)[pn] != INVALID && fa.minCut((*_pred)[pn])) { - _pred->set(n, (*_pred)[pn]); - _pred->set(pn, n); - _weight->set(n, (*_weight)[pn]); - _weight->set(pn, fa.flowValue()); + (*_pred)[n] = (*_pred)[pn]; + (*_pred)[pn] = n; + (*_weight)[n] = (*_weight)[pn]; + (*_weight)[pn] = fa.flowValue(); } } - _order->set(_root, 0); + (*_order)[_root] = 0; int index = 1; for (NodeIt n(_graph); n != INVALID; ++n) { @@ -190,7 +188,7 @@ nn = (*_pred)[nn]; } while (!st.empty()) { - _order->set(st.back(), index++); + (*_order)[st.back()] = index++; st.pop_back(); } } @@ -215,43 +213,53 @@ ///\name Query Functions ///The results of the algorithm can be obtained using these ///functions.\n - ///\ref run() "run()" should be called before using them.\n + ///\ref run() should be called before using them.\n ///See also \ref MinCutNodeIt and \ref MinCutEdgeIt. ///@{ /// \brief Return the predecessor node in the Gomory-Hu tree. /// - /// This function returns the predecessor node in the Gomory-Hu tree. - /// If the node is - /// the root of the Gomory-Hu tree, then it returns \c INVALID. - Node predNode(const Node& node) { + /// This function returns the predecessor node of the given node + /// in the Gomory-Hu tree. + /// If \c node is the root of the tree, then it returns \c INVALID. + /// + /// \pre \ref run() must be called before using this function. + Node predNode(const Node& node) const { return (*_pred)[node]; } - /// \brief Return the distance from the root node in the Gomory-Hu tree. - /// - /// This function returns the distance of \c node from the root node - /// in the Gomory-Hu tree. - int rootDist(const Node& node) { - return (*_order)[node]; - } - /// \brief Return the weight of the predecessor edge in the /// Gomory-Hu tree. /// - /// This function returns the weight of the predecessor edge in the - /// Gomory-Hu tree. If the node is the root, the result is undefined. - Value predValue(const Node& node) { + /// This function returns the weight of the predecessor edge of the + /// given node in the Gomory-Hu tree. + /// If \c node is the root of the tree, the result is undefined. + /// + /// \pre \ref run() must be called before using this function. + Value predValue(const Node& node) const { return (*_weight)[node]; } + /// \brief Return the distance from the root node in the Gomory-Hu tree. + /// + /// This function returns the distance of the given node from the root + /// node in the Gomory-Hu tree. + /// + /// \pre \ref run() must be called before using this function. + int rootDist(const Node& node) const { + return (*_order)[node]; + } + /// \brief Return the minimum cut value between two nodes /// - /// This function returns the minimum cut value between two nodes. The - /// algorithm finds the nearest common ancestor in the Gomory-Hu - /// tree and calculates the minimum weight edge on the paths to - /// the ancestor. + /// This function returns the minimum cut value between the nodes + /// \c s and \c t. + /// It finds the nearest common ancestor of the given nodes in the + /// Gomory-Hu tree and calculates the minimum weight edge on the + /// paths to the ancestor. + /// + /// \pre \ref run() must be called before using this function. Value minCutValue(const Node& s, const Node& t) const { Node sn = s, tn = t; Value value = std::numeric_limits::max(); @@ -274,16 +282,23 @@ /// in the \c cutMap parameter by setting the nodes in the component of /// \c s to \c true and the other nodes to \c false. /// - /// For higher level interfaces, see MinCutNodeIt and MinCutEdgeIt. + /// For higher level interfaces see MinCutNodeIt and MinCutEdgeIt. + /// + /// \param s The base node. + /// \param t The node you want to separate from node \c s. + /// \param cutMap The cut will be returned in this map. + /// It must be a \c bool (or convertible) \ref concepts::ReadWriteMap + /// "ReadWriteMap" on the graph nodes. + /// + /// \return The value of the minimum cut between \c s and \c t. + /// + /// \pre \ref run() must be called before using this function. template - Value minCutMap(const Node& s, ///< The base node. + Value minCutMap(const Node& s, ///< const Node& t, - ///< The node you want to separate from node \c s. + ///< CutMap& cutMap - ///< The cut will be returned in this map. - /// It must be a \c bool (or convertible) - /// \ref concepts::ReadWriteMap "ReadWriteMap" - /// on the graph nodes. + ///< ) const { Node sn = s, tn = t; bool s_root=false; @@ -309,9 +324,9 @@ } typename Graph::template NodeMap reached(_graph, false); - reached.set(_root, true); + reached[_root] = true; cutMap.set(_root, !s_root); - reached.set(rn, true); + reached[rn] = true; cutMap.set(rn, s_root); std::vector st; @@ -338,7 +353,7 @@ /// Iterate on the nodes of a minimum cut /// This iterator class lists the nodes of a minimum cut found by - /// GomoryHu. Before using it, you must allocate a GomoryHu class, + /// GomoryHu. Before using it, you must allocate a GomoryHu class /// and call its \ref GomoryHu::run() "run()" method. /// /// This example counts the nodes in the minimum cut separating \c s from @@ -435,7 +450,7 @@ /// Iterate on the edges of a minimum cut /// This iterator class lists the edges of a minimum cut found by - /// GomoryHu. Before using it, you must allocate a GomoryHu class, + /// GomoryHu. Before using it, you must allocate a GomoryHu class /// and call its \ref GomoryHu::run() "run()" method. /// /// This example computes the value of the minimum cut separating \c s from @@ -447,8 +462,8 @@ /// for(GomoruHu::MinCutEdgeIt e(gom,s,t); e!=INVALID; ++e) /// value+=capacities[e]; /// \endcode - /// the result will be the same as it is returned by - /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)" + /// The result will be the same as the value returned by + /// \ref GomoryHu::minCutValue() "gom.minCutValue(s,t)". class MinCutEdgeIt { bool _side; @@ -468,6 +483,10 @@ } public: + /// Constructor + + /// Constructor. + /// MinCutEdgeIt(GomoryHu const &gomory, ///< The GomoryHu class. You must call its /// run() method @@ -478,7 +497,7 @@ bool side=true ///< If it is \c true (default) then the listed arcs /// will be oriented from the - /// the nodes of the component containing \c s, + /// nodes of the component containing \c s, /// otherwise they will be oriented in the opposite /// direction. ) diff -r a3402913cffe -r f63e87b9748e lemon/graph_to_eps.h --- a/lemon/graph_to_eps.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/graph_to_eps.h Tue Apr 21 10:34:49 2009 +0100 @@ -268,22 +268,18 @@ /// = 1 ///\image html nodeshape_1.png ///\image latex nodeshape_1.eps "SQUARE shape (1)" width=2cm - /// SQUARE=1, /// = 2 ///\image html nodeshape_2.png ///\image latex nodeshape_2.eps "DIAMOND shape (2)" width=2cm - /// DIAMOND=2, /// = 3 ///\image html nodeshape_3.png - ///\image latex nodeshape_2.eps "MALE shape (4)" width=2cm - /// + ///\image latex nodeshape_3.eps "MALE shape (3)" width=2cm MALE=3, /// = 4 ///\image html nodeshape_4.png - ///\image latex nodeshape_2.eps "FEMALE shape (4)" width=2cm - /// + ///\image latex nodeshape_4.eps "FEMALE shape (4)" width=2cm FEMALE=4 }; diff -r a3402913cffe -r f63e87b9748e lemon/grid_graph.h --- a/lemon/grid_graph.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/grid_graph.h Tue Apr 21 10:34:49 2009 +0100 @@ -497,9 +497,7 @@ ///\endcode /// /// This graph type fully conforms to the \ref concepts::Graph - /// "Graph" concept, and it also has an important extra feature - /// that its maps are real \ref concepts::ReferenceMap - /// "reference map"s. + /// "Graph concept". class GridGraph : public ExtendedGridGraphBase { public: diff -r a3402913cffe -r f63e87b9748e lemon/hao_orlin.h --- a/lemon/hao_orlin.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/hao_orlin.h Tue Apr 21 10:34:49 2009 +0100 @@ -31,39 +31,41 @@ /// \ingroup min_cut /// \brief Implementation of the Hao-Orlin algorithm. /// -/// Implementation of the Hao-Orlin algorithm class for testing network -/// reliability. +/// Implementation of the Hao-Orlin algorithm for finding a minimum cut +/// in a digraph. namespace lemon { /// \ingroup min_cut /// - /// \brief %Hao-Orlin algorithm to find a minimum cut in directed graphs. + /// \brief Hao-Orlin algorithm for finding a minimum cut in a digraph. /// - /// Hao-Orlin calculates a minimum cut in a directed graph - /// \f$D=(V,A)\f$. It takes a fixed node \f$ source \in V \f$ and + /// This class implements the Hao-Orlin algorithm for finding a minimum + /// value cut in a directed graph \f$D=(V,A)\f$. + /// It takes a fixed node \f$ source \in V \f$ and /// consists of two phases: in the first phase it determines a /// minimum cut with \f$ source \f$ on the source-side (i.e. a set - /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal - /// out-degree) and in the second phase it determines a minimum cut + /// \f$ X\subsetneq V \f$ with \f$ source \in X \f$ and minimal outgoing + /// capacity) and in the second phase it determines a minimum cut /// with \f$ source \f$ on the sink-side (i.e. a set - /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal - /// out-degree). Obviously, the smaller of these two cuts will be a + /// \f$ X\subsetneq V \f$ with \f$ source \notin X \f$ and minimal outgoing + /// capacity). Obviously, the smaller of these two cuts will be a /// minimum cut of \f$ D \f$. The algorithm is a modified - /// push-relabel preflow algorithm and our implementation calculates + /// preflow push-relabel algorithm. Our implementation calculates /// the minimum cut in \f$ O(n^2\sqrt{m}) \f$ time (we use the /// highest-label rule), or in \f$O(nm)\f$ for unit capacities. The - /// purpose of such algorithm is testing network reliability. For an - /// undirected graph you can run just the first phase of the - /// algorithm or you can use the algorithm of Nagamochi and Ibaraki - /// which solves the undirected problem in - /// \f$ O(nm + n^2 \log n) \f$ time: it is implemented in the - /// NagamochiIbaraki algorithm class. + /// purpose of such algorithm is e.g. testing network reliability. /// - /// \param GR The digraph class the algorithm runs on. - /// \param CAP An arc map of capacities which can be any numreric type. - /// The default type is \ref concepts::Digraph::ArcMap "GR::ArcMap". - /// \param TOL Tolerance class for handling inexact computations. The + /// For an undirected graph you can run just the first phase of the + /// algorithm or you can use the algorithm of Nagamochi and Ibaraki, + /// which solves the undirected problem in \f$ O(nm + n^2 \log n) \f$ + /// time. It is implemented in the NagamochiIbaraki algorithm class. + /// + /// \tparam GR The type of the digraph the algorithm runs on. + /// \tparam CAP The type of the arc map containing the capacities, + /// which can be any numreric type. The default map type is + /// \ref concepts::Digraph::ArcMap "GR::ArcMap". + /// \tparam TOL Tolerance class for handling inexact computations. The /// default tolerance type is \ref Tolerance "Tolerance". #ifdef DOXYGEN template @@ -73,15 +75,20 @@ typename TOL = Tolerance > #endif class HaoOrlin { + public: + + /// The digraph type of the algorithm + typedef GR Digraph; + /// The capacity map type of the algorithm + typedef CAP CapacityMap; + /// The tolerance type of the algorithm + typedef TOL Tolerance; + private: - typedef GR Digraph; - typedef CAP CapacityMap; - typedef TOL Tolerance; - typedef typename CapacityMap::Value Value; - TEMPLATE_GRAPH_TYPEDEFS(Digraph); + TEMPLATE_DIGRAPH_TYPEDEFS(Digraph); const Digraph& _graph; const CapacityMap* _capacity; @@ -161,56 +168,56 @@ private: void activate(const Node& i) { - _active->set(i, true); + (*_active)[i] = true; int bucket = (*_bucket)[i]; if ((*_prev)[i] == INVALID || (*_active)[(*_prev)[i]]) return; //unlace - _next->set((*_prev)[i], (*_next)[i]); + (*_next)[(*_prev)[i]] = (*_next)[i]; if ((*_next)[i] != INVALID) { - _prev->set((*_next)[i], (*_prev)[i]); + (*_prev)[(*_next)[i]] = (*_prev)[i]; } else { _last[bucket] = (*_prev)[i]; } //lace - _next->set(i, _first[bucket]); - _prev->set(_first[bucket], i); - _prev->set(i, INVALID); + (*_next)[i] = _first[bucket]; + (*_prev)[_first[bucket]] = i; + (*_prev)[i] = INVALID; _first[bucket] = i; } void deactivate(const Node& i) { - _active->set(i, false); + (*_active)[i] = false; int bucket = (*_bucket)[i]; if ((*_next)[i] == INVALID || !(*_active)[(*_next)[i]]) return; //unlace - _prev->set((*_next)[i], (*_prev)[i]); + (*_prev)[(*_next)[i]] = (*_prev)[i]; if ((*_prev)[i] != INVALID) { - _next->set((*_prev)[i], (*_next)[i]); + (*_next)[(*_prev)[i]] = (*_next)[i]; } else { _first[bucket] = (*_next)[i]; } //lace - _prev->set(i, _last[bucket]); - _next->set(_last[bucket], i); - _next->set(i, INVALID); + (*_prev)[i] = _last[bucket]; + (*_next)[_last[bucket]] = i; + (*_next)[i] = INVALID; _last[bucket] = i; } void addItem(const Node& i, int bucket) { (*_bucket)[i] = bucket; if (_last[bucket] != INVALID) { - _prev->set(i, _last[bucket]); - _next->set(_last[bucket], i); - _next->set(i, INVALID); + (*_prev)[i] = _last[bucket]; + (*_next)[_last[bucket]] = i; + (*_next)[i] = INVALID; _last[bucket] = i; } else { - _prev->set(i, INVALID); + (*_prev)[i] = INVALID; _first[bucket] = i; - _next->set(i, INVALID); + (*_next)[i] = INVALID; _last[bucket] = i; } } @@ -218,11 +225,12 @@ void findMinCutOut() { for (NodeIt n(_graph); n != INVALID; ++n) { - _excess->set(n, 0); + (*_excess)[n] = 0; + (*_source_set)[n] = false; } for (ArcIt a(_graph); a != INVALID; ++a) { - _flow->set(a, 0); + (*_flow)[a] = 0; } int bucket_num = 0; @@ -232,7 +240,7 @@ { typename Digraph::template NodeMap reached(_graph, false); - reached.set(_source, true); + reached[_source] = true; bool first_set = true; for (NodeIt t(_graph); t != INVALID; ++t) { @@ -240,7 +248,7 @@ _sets.push_front(std::list()); queue[qlast++] = t; - reached.set(t, true); + reached[t] = true; while (qfirst != qlast) { if (qsep == qfirst) { @@ -257,7 +265,7 @@ for (InArcIt a(_graph, n); a != INVALID; ++a) { Node u = _graph.source(a); if (!reached[u] && _tolerance.positive((*_capacity)[a])) { - reached.set(u, true); + reached[u] = true; queue[qlast++] = u; } } @@ -266,18 +274,18 @@ } ++bucket_num; - _bucket->set(_source, 0); + (*_bucket)[_source] = 0; _dormant[0] = true; } - _source_set->set(_source, true); + (*_source_set)[_source] = true; Node target = _last[_sets.back().back()]; { for (OutArcIt a(_graph, _source); a != INVALID; ++a) { if (_tolerance.positive((*_capacity)[a])) { Node u = _graph.target(a); - _flow->set(a, (*_capacity)[a]); - _excess->set(u, (*_excess)[u] + (*_capacity)[a]); + (*_flow)[a] = (*_capacity)[a]; + (*_excess)[u] += (*_capacity)[a]; if (!(*_active)[u] && u != _source) { activate(u); } @@ -318,14 +326,14 @@ activate(v); } if (!_tolerance.less(rem, excess)) { - _flow->set(a, (*_flow)[a] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_flow)[a] += excess; + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, (*_capacity)[a]); + (*_excess)[v] += rem; + (*_flow)[a] = (*_capacity)[a]; } } else if (next_bucket > (*_bucket)[v]) { next_bucket = (*_bucket)[v]; @@ -342,14 +350,14 @@ activate(v); } if (!_tolerance.less(rem, excess)) { - _flow->set(a, (*_flow)[a] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_flow)[a] -= excess; + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, 0); + (*_excess)[v] += rem; + (*_flow)[a] = 0; } } else if (next_bucket > (*_bucket)[v]) { next_bucket = (*_bucket)[v]; @@ -358,7 +366,7 @@ no_more_push: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if ((*_next)[n] == INVALID) { @@ -376,16 +384,16 @@ } } else if (next_bucket == _node_num) { _first[(*_bucket)[n]] = (*_next)[n]; - _prev->set((*_next)[n], INVALID); + (*_prev)[(*_next)[n]] = INVALID; std::list >::iterator new_set = _sets.insert(--_sets.end(), std::list()); new_set->push_front(bucket_num); - _bucket->set(n, bucket_num); + (*_bucket)[n] = bucket_num; _first[bucket_num] = _last[bucket_num] = n; - _next->set(n, INVALID); - _prev->set(n, INVALID); + (*_next)[n] = INVALID; + (*_prev)[n] = INVALID; _dormant[bucket_num] = true; ++bucket_num; @@ -395,7 +403,7 @@ } } else { _first[*_highest] = (*_next)[n]; - _prev->set((*_next)[n], INVALID); + (*_prev)[(*_next)[n]] = INVALID; while (next_bucket != *_highest) { --_highest; @@ -409,10 +417,10 @@ } --_highest; - _bucket->set(n, *_highest); - _next->set(n, _first[*_highest]); + (*_bucket)[n] = *_highest; + (*_next)[n] = _first[*_highest]; if (_first[*_highest] != INVALID) { - _prev->set(_first[*_highest], n); + (*_prev)[_first[*_highest]] = n; } else { _last[*_highest] = n; } @@ -434,13 +442,13 @@ if ((*_excess)[target] < _min_cut) { _min_cut = (*_excess)[target]; for (NodeIt i(_graph); i != INVALID; ++i) { - _min_cut_map->set(i, true); + (*_min_cut_map)[i] = true; } for (std::list::iterator it = _sets.back().begin(); it != _sets.back().end(); ++it) { Node n = _first[*it]; while (n != INVALID) { - _min_cut_map->set(n, false); + (*_min_cut_map)[n] = false; n = (*_next)[n]; } } @@ -453,13 +461,13 @@ _last[(*_bucket)[target]] = (*_prev)[target]; new_target = (*_prev)[target]; } else { - _prev->set((*_next)[target], (*_prev)[target]); + (*_prev)[(*_next)[target]] = (*_prev)[target]; new_target = (*_next)[target]; } if ((*_prev)[target] == INVALID) { _first[(*_bucket)[target]] = (*_next)[target]; } else { - _next->set((*_prev)[target], (*_next)[target]); + (*_next)[(*_prev)[target]] = (*_next)[target]; } } else { _sets.back().pop_back(); @@ -475,9 +483,9 @@ new_target = _last[_sets.back().back()]; } - _bucket->set(target, 0); + (*_bucket)[target] = 0; - _source_set->set(target, true); + (*_source_set)[target] = true; for (OutArcIt a(_graph, target); a != INVALID; ++a) { Value rem = (*_capacity)[a] - (*_flow)[a]; if (!_tolerance.positive(rem)) continue; @@ -485,8 +493,8 @@ if (!(*_active)[v] && !(*_source_set)[v]) { activate(v); } - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, (*_capacity)[a]); + (*_excess)[v] += rem; + (*_flow)[a] = (*_capacity)[a]; } for (InArcIt a(_graph, target); a != INVALID; ++a) { @@ -496,8 +504,8 @@ if (!(*_active)[v] && !(*_source_set)[v]) { activate(v); } - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, 0); + (*_excess)[v] += rem; + (*_flow)[a] = 0; } target = new_target; @@ -517,11 +525,12 @@ void findMinCutIn() { for (NodeIt n(_graph); n != INVALID; ++n) { - _excess->set(n, 0); + (*_excess)[n] = 0; + (*_source_set)[n] = false; } for (ArcIt a(_graph); a != INVALID; ++a) { - _flow->set(a, 0); + (*_flow)[a] = 0; } int bucket_num = 0; @@ -531,7 +540,7 @@ { typename Digraph::template NodeMap reached(_graph, false); - reached.set(_source, true); + reached[_source] = true; bool first_set = true; @@ -540,7 +549,7 @@ _sets.push_front(std::list()); queue[qlast++] = t; - reached.set(t, true); + reached[t] = true; while (qfirst != qlast) { if (qsep == qfirst) { @@ -557,7 +566,7 @@ for (OutArcIt a(_graph, n); a != INVALID; ++a) { Node u = _graph.target(a); if (!reached[u] && _tolerance.positive((*_capacity)[a])) { - reached.set(u, true); + reached[u] = true; queue[qlast++] = u; } } @@ -566,18 +575,18 @@ } ++bucket_num; - _bucket->set(_source, 0); + (*_bucket)[_source] = 0; _dormant[0] = true; } - _source_set->set(_source, true); + (*_source_set)[_source] = true; Node target = _last[_sets.back().back()]; { for (InArcIt a(_graph, _source); a != INVALID; ++a) { if (_tolerance.positive((*_capacity)[a])) { Node u = _graph.source(a); - _flow->set(a, (*_capacity)[a]); - _excess->set(u, (*_excess)[u] + (*_capacity)[a]); + (*_flow)[a] = (*_capacity)[a]; + (*_excess)[u] += (*_capacity)[a]; if (!(*_active)[u] && u != _source) { activate(u); } @@ -618,14 +627,14 @@ activate(v); } if (!_tolerance.less(rem, excess)) { - _flow->set(a, (*_flow)[a] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_flow)[a] += excess; + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, (*_capacity)[a]); + (*_excess)[v] += rem; + (*_flow)[a] = (*_capacity)[a]; } } else if (next_bucket > (*_bucket)[v]) { next_bucket = (*_bucket)[v]; @@ -642,14 +651,14 @@ activate(v); } if (!_tolerance.less(rem, excess)) { - _flow->set(a, (*_flow)[a] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_flow)[a] -= excess; + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, 0); + (*_excess)[v] += rem; + (*_flow)[a] = 0; } } else if (next_bucket > (*_bucket)[v]) { next_bucket = (*_bucket)[v]; @@ -658,7 +667,7 @@ no_more_push: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if ((*_next)[n] == INVALID) { @@ -676,16 +685,16 @@ } } else if (next_bucket == _node_num) { _first[(*_bucket)[n]] = (*_next)[n]; - _prev->set((*_next)[n], INVALID); + (*_prev)[(*_next)[n]] = INVALID; std::list >::iterator new_set = _sets.insert(--_sets.end(), std::list()); new_set->push_front(bucket_num); - _bucket->set(n, bucket_num); + (*_bucket)[n] = bucket_num; _first[bucket_num] = _last[bucket_num] = n; - _next->set(n, INVALID); - _prev->set(n, INVALID); + (*_next)[n] = INVALID; + (*_prev)[n] = INVALID; _dormant[bucket_num] = true; ++bucket_num; @@ -695,7 +704,7 @@ } } else { _first[*_highest] = (*_next)[n]; - _prev->set((*_next)[n], INVALID); + (*_prev)[(*_next)[n]] = INVALID; while (next_bucket != *_highest) { --_highest; @@ -708,10 +717,10 @@ } --_highest; - _bucket->set(n, *_highest); - _next->set(n, _first[*_highest]); + (*_bucket)[n] = *_highest; + (*_next)[n] = _first[*_highest]; if (_first[*_highest] != INVALID) { - _prev->set(_first[*_highest], n); + (*_prev)[_first[*_highest]] = n; } else { _last[*_highest] = n; } @@ -733,13 +742,13 @@ if ((*_excess)[target] < _min_cut) { _min_cut = (*_excess)[target]; for (NodeIt i(_graph); i != INVALID; ++i) { - _min_cut_map->set(i, false); + (*_min_cut_map)[i] = false; } for (std::list::iterator it = _sets.back().begin(); it != _sets.back().end(); ++it) { Node n = _first[*it]; while (n != INVALID) { - _min_cut_map->set(n, true); + (*_min_cut_map)[n] = true; n = (*_next)[n]; } } @@ -752,13 +761,13 @@ _last[(*_bucket)[target]] = (*_prev)[target]; new_target = (*_prev)[target]; } else { - _prev->set((*_next)[target], (*_prev)[target]); + (*_prev)[(*_next)[target]] = (*_prev)[target]; new_target = (*_next)[target]; } if ((*_prev)[target] == INVALID) { _first[(*_bucket)[target]] = (*_next)[target]; } else { - _next->set((*_prev)[target], (*_next)[target]); + (*_next)[(*_prev)[target]] = (*_next)[target]; } } else { _sets.back().pop_back(); @@ -774,9 +783,9 @@ new_target = _last[_sets.back().back()]; } - _bucket->set(target, 0); + (*_bucket)[target] = 0; - _source_set->set(target, true); + (*_source_set)[target] = true; for (InArcIt a(_graph, target); a != INVALID; ++a) { Value rem = (*_capacity)[a] - (*_flow)[a]; if (!_tolerance.positive(rem)) continue; @@ -784,8 +793,8 @@ if (!(*_active)[v] && !(*_source_set)[v]) { activate(v); } - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, (*_capacity)[a]); + (*_excess)[v] += rem; + (*_flow)[a] = (*_capacity)[a]; } for (OutArcIt a(_graph, target); a != INVALID; ++a) { @@ -795,8 +804,8 @@ if (!(*_active)[v] && !(*_source_set)[v]) { activate(v); } - _excess->set(v, (*_excess)[v] + rem); - _flow->set(a, 0); + (*_excess)[v] += rem; + (*_flow)[a] = 0; } target = new_target; @@ -815,31 +824,32 @@ public: - /// \name Execution control + /// \name Execution Control /// The simplest way to execute the algorithm is to use /// one of the member functions called \ref run(). /// \n - /// If you need more control on the execution, - /// first you must call \ref init(), then the \ref calculateIn() or - /// \ref calculateOut() functions. + /// If you need better control on the execution, + /// you have to call one of the \ref init() functions first, then + /// \ref calculateOut() and/or \ref calculateIn(). /// @{ - /// \brief Initializes the internal data structures. + /// \brief Initialize the internal data structures. /// - /// Initializes the internal data structures. It creates - /// the maps, residual graph adaptors and some bucket structures - /// for the algorithm. + /// This function initializes the internal data structures. It creates + /// the maps and some bucket structures for the algorithm. + /// The first node is used as the source node for the push-relabel + /// algorithm. void init() { init(NodeIt(_graph)); } - /// \brief Initializes the internal data structures. + /// \brief Initialize the internal data structures. /// - /// Initializes the internal data structures. It creates - /// the maps, residual graph adaptor and some bucket structures - /// for the algorithm. Node \c source is used as the push-relabel - /// algorithm's source. + /// This function initializes the internal data structures. It creates + /// the maps and some bucket structures for the algorithm. + /// The given node is used as the source node for the push-relabel + /// algorithm. void init(const Node& source) { _source = source; @@ -879,31 +889,35 @@ } - /// \brief Calculates a minimum cut with \f$ source \f$ on the + /// \brief Calculate a minimum cut with \f$ source \f$ on the /// source-side. /// - /// Calculates a minimum cut with \f$ source \f$ on the + /// This function calculates a minimum cut with \f$ source \f$ on the /// source-side (i.e. a set \f$ X\subsetneq V \f$ with - /// \f$ source \in X \f$ and minimal out-degree). + /// \f$ source \in X \f$ and minimal outgoing capacity). + /// + /// \pre \ref init() must be called before using this function. void calculateOut() { findMinCutOut(); } - /// \brief Calculates a minimum cut with \f$ source \f$ on the - /// target-side. + /// \brief Calculate a minimum cut with \f$ source \f$ on the + /// sink-side. /// - /// Calculates a minimum cut with \f$ source \f$ on the - /// target-side (i.e. a set \f$ X\subsetneq V \f$ with - /// \f$ source \in X \f$ and minimal out-degree). + /// This function calculates a minimum cut with \f$ source \f$ on the + /// sink-side (i.e. a set \f$ X\subsetneq V \f$ with + /// \f$ source \notin X \f$ and minimal outgoing capacity). + /// + /// \pre \ref init() must be called before using this function. void calculateIn() { findMinCutIn(); } - /// \brief Runs the algorithm. + /// \brief Run the algorithm. /// - /// Runs the algorithm. It finds nodes \c source and \c target - /// arbitrarily and then calls \ref init(), \ref calculateOut() + /// This function runs the algorithm. It finds nodes \c source and + /// \c target arbitrarily and then calls \ref init(), \ref calculateOut() /// and \ref calculateIn(). void run() { init(); @@ -911,11 +925,11 @@ calculateIn(); } - /// \brief Runs the algorithm. + /// \brief Run the algorithm. /// - /// Runs the algorithm. It uses the given \c source node, finds a - /// proper \c target and then calls the \ref init(), \ref - /// calculateOut() and \ref calculateIn(). + /// This function runs the algorithm. It uses the given \c source node, + /// finds a proper \c target node and then calls the \ref init(), + /// \ref calculateOut() and \ref calculateIn(). void run(const Node& s) { init(s); calculateOut(); @@ -926,32 +940,41 @@ /// \name Query Functions /// The result of the %HaoOrlin algorithm - /// can be obtained using these functions. - /// \n - /// Before using these functions, either \ref run(), \ref - /// calculateOut() or \ref calculateIn() must be called. + /// can be obtained using these functions.\n + /// \ref run(), \ref calculateOut() or \ref calculateIn() + /// should be called before using them. /// @{ - /// \brief Returns the value of the minimum value cut. + /// \brief Return the value of the minimum cut. /// - /// Returns the value of the minimum value cut. + /// This function returns the value of the minimum cut. + /// + /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() + /// must be called before using this function. Value minCutValue() const { return _min_cut; } - /// \brief Returns a minimum cut. + /// \brief Return a minimum cut. /// - /// Sets \c nodeMap to the characteristic vector of a minimum - /// value cut: it will give a nonempty set \f$ X\subsetneq V \f$ - /// with minimal out-degree (i.e. \c nodeMap will be true exactly - /// for the nodes of \f$ X \f$). \pre nodeMap should be a - /// bool-valued node-map. - template - Value minCutMap(NodeMap& nodeMap) const { + /// This function sets \c cutMap to the characteristic vector of a + /// minimum value cut: it will give a non-empty set \f$ X\subsetneq V \f$ + /// with minimal outgoing capacity (i.e. \c cutMap will be \c true exactly + /// for the nodes of \f$ X \f$). + /// + /// \param cutMap A \ref concepts::WriteMap "writable" node map with + /// \c bool (or convertible) value type. + /// + /// \return The value of the minimum cut. + /// + /// \pre \ref run(), \ref calculateOut() or \ref calculateIn() + /// must be called before using this function. + template + Value minCutMap(CutMap& cutMap) const { for (NodeIt it(_graph); it != INVALID; ++it) { - nodeMap.set(it, (*_min_cut_map)[it]); + cutMap.set(it, (*_min_cut_map)[it]); } return _min_cut; } @@ -960,7 +983,6 @@ }; //class HaoOrlin - } //namespace lemon #endif //LEMON_HAO_ORLIN_H diff -r a3402913cffe -r f63e87b9748e lemon/hypercube_graph.h --- a/lemon/hypercube_graph.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/hypercube_graph.h Tue Apr 21 10:34:49 2009 +0100 @@ -292,9 +292,7 @@ /// (assuming that the size of \c int is 32 bit). /// /// This graph type fully conforms to the \ref concepts::Graph - /// "Graph" concept, and it also has an important extra feature - /// that its maps are real \ref concepts::ReferenceMap - /// "reference map"s. + /// "Graph concept". class HypercubeGraph : public ExtendedHypercubeGraphBase { public: diff -r a3402913cffe -r f63e87b9748e lemon/kruskal.h --- a/lemon/kruskal.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/kruskal.h Tue Apr 21 10:34:49 2009 +0100 @@ -248,11 +248,11 @@ /// \ingroup spantree /// - /// \brief Kruskal algorithm to find a minimum cost spanning tree of + /// \brief Kruskal's algorithm for finding a minimum cost spanning tree of /// a graph. /// /// This function runs Kruskal's algorithm to find a minimum cost - /// spanning tree. + /// spanning tree of a graph. /// Due to some C++ hacking, it accepts various input and output types. /// /// \param g The graph the algorithm runs on. @@ -264,17 +264,17 @@ /// \param in This object is used to describe the arc/edge costs. /// It can be one of the following choices. /// - An STL compatible 'Forward Container' with - /// std::pair or - /// std::pair as its value_type, where - /// \c X is the type of the costs. The pairs indicates the arcs/edges + /// std::pair or + /// std::pair as its value_type, where + /// \c C is the type of the costs. The pairs indicates the arcs/edges /// along with the assigned cost. They must be in a /// cost-ascending order. /// - Any readable arc/edge map. The values of the map indicate the /// arc/edge costs. /// /// \retval out Here we also have a choice. - /// - It can be a writable \c bool arc/edge map. After running the - /// algorithm it will contain the found minimum cost spanning + /// - It can be a writable arc/edge map with \c bool value type. After + /// running the algorithm it will contain the found minimum cost spanning /// tree: the value of an arc/edge will be set to \c true if it belongs /// to the tree, otherwise it will be set to \c false. The value of /// each arc/edge will be set exactly once. @@ -301,8 +301,8 @@ /// forest is calculated instead of a spanning tree. #ifdef DOXYGEN - template - Value kruskal(GR const& g, const In& in, Out& out) + template + Value kruskal(const Graph& g, const In& in, Out& out) #else template inline typename _kruskal_bits::KruskalValueSelector::Value @@ -314,8 +314,6 @@ } - - template inline typename _kruskal_bits::KruskalValueSelector::Value kruskal(const Graph& graph, const In& in, const Out& out) diff -r a3402913cffe -r f63e87b9748e lemon/lgf_reader.h --- a/lemon/lgf_reader.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/lgf_reader.h Tue Apr 21 10:34:49 2009 +0100 @@ -592,7 +592,7 @@ public: - /// \name Reading rules + /// \name Reading Rules /// @{ /// \brief Node map reading rule @@ -697,7 +697,7 @@ /// @} - /// \name Select section by name + /// \name Select Section by Name /// @{ /// \brief Set \c \@nodes section to be read @@ -726,7 +726,7 @@ /// @} - /// \name Using previously constructed node or arc set + /// \name Using Previously Constructed Node or Arc Set /// @{ /// \brief Use previously constructed node set @@ -1115,7 +1115,7 @@ public: - /// \name Execution of the reader + /// \name Execution of the Reader /// @{ /// \brief Start the batch processing @@ -1415,7 +1415,7 @@ public: - /// \name Reading rules + /// \name Reading Rules /// @{ /// \brief Node map reading rule @@ -1566,7 +1566,7 @@ /// @} - /// \name Select section by name + /// \name Select Section by Name /// @{ /// \brief Set \c \@nodes section to be read @@ -1595,7 +1595,7 @@ /// @} - /// \name Using previously constructed node or edge set + /// \name Using Previously Constructed Node or Edge Set /// @{ /// \brief Use previously constructed node set @@ -1985,7 +1985,7 @@ public: - /// \name Execution of the reader + /// \name Execution of the Reader /// @{ /// \brief Start the batch processing @@ -2209,7 +2209,7 @@ public: - /// \name Section readers + /// \name Section Readers /// @{ /// \brief Add a section processor with line oriented reading @@ -2308,7 +2308,7 @@ public: - /// \name Execution of the reader + /// \name Execution of the Reader /// @{ /// \brief Start the batch processing @@ -2500,7 +2500,7 @@ public: - /// \name Node sections + /// \name Node Sections /// @{ /// \brief Gives back the number of node sections in the file. @@ -2526,7 +2526,7 @@ /// @} - /// \name Arc/Edge sections + /// \name Arc/Edge Sections /// @{ /// \brief Gives back the number of arc/edge sections in the file. @@ -2584,7 +2584,7 @@ /// @} - /// \name Attribute sections + /// \name Attribute Sections /// @{ /// \brief Gives back the number of attribute sections in the file. @@ -2610,7 +2610,7 @@ /// @} - /// \name Extra sections + /// \name Extra Sections /// @{ /// \brief Gives back the number of extra sections in the file. @@ -2686,7 +2686,7 @@ public: - /// \name Execution of the contents reader + /// \name Execution of the Contents Reader /// @{ /// \brief Starts the reading diff -r a3402913cffe -r f63e87b9748e lemon/lgf_writer.h --- a/lemon/lgf_writer.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/lgf_writer.h Tue Apr 21 10:34:49 2009 +0100 @@ -536,7 +536,7 @@ public: - /// \name Writing rules + /// \name Writing Rules /// @{ /// \brief Node map writing rule @@ -639,7 +639,7 @@ return *this; } - /// \name Section captions + /// \name Section Captions /// @{ /// \brief Add an additional caption to the \c \@nodes section @@ -666,7 +666,7 @@ return *this; } - /// \name Skipping section + /// \name Skipping Section /// @{ /// \brief Skip writing the node set @@ -883,7 +883,7 @@ public: - /// \name Execution of the writer + /// \name Execution of the Writer /// @{ /// \brief Start the batch processing @@ -1129,7 +1129,7 @@ public: - /// \name Writing rules + /// \name Writing Rules /// @{ /// \brief Node map writing rule @@ -1278,7 +1278,7 @@ return *this; } - /// \name Section captions + /// \name Section Captions /// @{ /// \brief Add an additional caption to the \c \@nodes section @@ -1305,7 +1305,7 @@ return *this; } - /// \name Skipping section + /// \name Skipping Section /// @{ /// \brief Skip writing the node set @@ -1522,7 +1522,7 @@ public: - /// \name Execution of the writer + /// \name Execution of the Writer /// @{ /// \brief Start the batch processing @@ -1699,7 +1699,7 @@ public: - /// \name Section writers + /// \name Section Writers /// @{ /// \brief Add a section writer with line oriented writing @@ -1766,7 +1766,7 @@ public: - /// \name Execution of the writer + /// \name Execution of the Writer /// @{ /// \brief Start the batch processing diff -r a3402913cffe -r f63e87b9748e lemon/list_graph.h --- a/lemon/list_graph.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/list_graph.h Tue Apr 21 10:34:49 2009 +0100 @@ -320,9 +320,6 @@ ///Most of the member functions and nested classes are documented ///only in the concept class. /// - ///An important extra feature of this digraph implementation is that - ///its maps are real \ref concepts::ReferenceMap "reference map"s. - /// ///\sa concepts::Digraph class ListDigraph : public ExtendedListDigraphBase { @@ -1176,9 +1173,6 @@ ///Most of the member functions and nested classes are documented ///only in the concept class. /// - ///An important extra feature of this graph implementation is that - ///its maps are real \ref concepts::ReferenceMap "reference map"s. - /// ///\sa concepts::Graph class ListGraph : public ExtendedListGraphBase { diff -r a3402913cffe -r f63e87b9748e lemon/lp_base.h --- a/lemon/lp_base.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/lp_base.h Tue Apr 21 10:34:49 2009 +0100 @@ -52,12 +52,12 @@ ///Possible outcomes of an LP solving procedure enum SolveExitStatus { - ///This means that the problem has been successfully solved: either + /// = 0. It means that the problem has been successfully solved: either ///an optimal solution has been found or infeasibility/unboundedness ///has been proved. SOLVED = 0, - ///Any other case (including the case when some user specified - ///limit has been exceeded) + /// = 1. Any other case (including the case when some user specified + ///limit has been exceeded). UNSOLVED = 1 }; @@ -69,6 +69,21 @@ MAX }; + ///Enum for \c messageLevel() parameter + enum MessageLevel { + /// No output (default value). + MESSAGE_NOTHING, + /// Error messages only. + MESSAGE_ERROR, + /// Warnings. + MESSAGE_WARNING, + /// Normal output. + MESSAGE_NORMAL, + /// Verbose output. + MESSAGE_VERBOSE + }; + + ///The floating point type used by the solver typedef double Value; ///The infinity constant @@ -973,6 +988,8 @@ virtual const char* _solverName() const = 0; + virtual void _messageLevel(MessageLevel level) = 0; + //Own protected stuff //Constant component of the objective function @@ -988,7 +1005,7 @@ ///Gives back the name of the solver. const char* solverName() const {return _solverName();} - ///\name Build up and modify the LP + ///\name Build Up and Modify the LP ///@{ @@ -1527,6 +1544,9 @@ ///Clears the problem void clear() { _clear(); } + /// Sets the message level of the solver + void messageLevel(MessageLevel level) { _messageLevel(level); } + ///@} }; @@ -1768,15 +1788,15 @@ /// The problem types for primal and dual problems enum ProblemType { - ///Feasible solution hasn't been found (but may exist). + /// = 0. Feasible solution hasn't been found (but may exist). UNDEFINED = 0, - ///The problem has no feasible solution + /// = 1. The problem has no feasible solution. INFEASIBLE = 1, - ///Feasible solution found + /// = 2. Feasible solution found. FEASIBLE = 2, - ///Optimal solution exists and found + /// = 3. Optimal solution exists and found. OPTIMAL = 3, - ///The cost function is unbounded + /// = 4. The cost function is unbounded. UNBOUNDED = 4 }; @@ -1832,7 +1852,7 @@ ///@} - ///\name Obtain the solution + ///\name Obtain the Solution ///@{ @@ -1954,17 +1974,16 @@ /// The problem types for MIP problems enum ProblemType { - ///Feasible solution hasn't been found (but may exist). + /// = 0. Feasible solution hasn't been found (but may exist). UNDEFINED = 0, - ///The problem has no feasible solution + /// = 1. The problem has no feasible solution. INFEASIBLE = 1, - ///Feasible solution found + /// = 2. Feasible solution found. FEASIBLE = 2, - ///Optimal solution exists and found + /// = 3. Optimal solution exists and found. OPTIMAL = 3, - ///The cost function is unbounded - /// - ///The Mip or at least the relaxed problem is unbounded + /// = 4. The cost function is unbounded. + ///The Mip or at least the relaxed problem is unbounded. UNBOUNDED = 4 }; @@ -1986,14 +2005,14 @@ ///@} - ///\name Setting column type + ///\name Set Column Type ///@{ ///Possible variable (column) types (e.g. real, integer, binary etc.) enum ColTypes { - ///Continuous variable (default) + /// = 0. Continuous variable (default). REAL = 0, - ///Integer variable + /// = 1. Integer variable. INTEGER = 1 }; @@ -2014,7 +2033,7 @@ } ///@} - ///\name Obtain the solution + ///\name Obtain the Solution ///@{ diff -r a3402913cffe -r f63e87b9748e lemon/lp_skeleton.cc --- a/lemon/lp_skeleton.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/lp_skeleton.cc Tue Apr 21 10:34:49 2009 +0100 @@ -84,6 +84,8 @@ row_num = col_num = 0; } + void SkeletonSolverBase::_messageLevel(MessageLevel) {} + LpSkeleton::SolveExitStatus LpSkeleton::_solve() { return SOLVED; } LpSkeleton::Value LpSkeleton::_getPrimal(int) const { return 0; } diff -r a3402913cffe -r f63e87b9748e lemon/lp_skeleton.h --- a/lemon/lp_skeleton.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/lp_skeleton.h Tue Apr 21 10:34:49 2009 +0100 @@ -140,6 +140,8 @@ ///\e virtual void _clear(); + ///\e + virtual void _messageLevel(MessageLevel); }; /// \brief Skeleton class for an LP solver interface diff -r a3402913cffe -r f63e87b9748e lemon/maps.h --- a/lemon/maps.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/maps.h Tue Apr 21 10:34:49 2009 +0100 @@ -2728,8 +2728,8 @@ /// \brief Potential difference map /// - /// PotentialMap returns the difference between the potentials of the - /// source and target nodes of each arc in a digraph, i.e. it returns + /// PotentialDifferenceMap returns the difference between the potentials of + /// the source and target nodes of each arc in a digraph, i.e. it returns /// \code /// potential[gr.target(arc)] - potential[gr.source(arc)]. /// \endcode diff -r a3402913cffe -r f63e87b9748e lemon/max_matching.h --- a/lemon/max_matching.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/max_matching.h Tue Apr 21 10:34:49 2009 +0100 @@ -282,20 +282,20 @@ Node base = (*_blossom_rep)[_blossom_set->find(node)]; while (base != nca) { - _ear->set(node, arc); + (*_ear)[node] = arc; Node n = node; while (n != base) { n = _graph.target((*_matching)[n]); Arc a = (*_ear)[n]; n = _graph.target(a); - _ear->set(n, _graph.oppositeArc(a)); + (*_ear)[n] = _graph.oppositeArc(a); } node = _graph.target((*_matching)[base]); _tree_set->erase(base); _tree_set->erase(node); _blossom_set->insert(node, _blossom_set->find(base)); - _status->set(node, EVEN); + (*_status)[node] = EVEN; _node_queue[_last++] = node; arc = _graph.oppositeArc((*_ear)[node]); node = _graph.target((*_ear)[node]); @@ -304,7 +304,7 @@ } } - _blossom_rep->set(_blossom_set->find(nca), nca); + (*_blossom_rep)[_blossom_set->find(nca)] = nca; { @@ -313,20 +313,20 @@ Node base = (*_blossom_rep)[_blossom_set->find(node)]; while (base != nca) { - _ear->set(node, arc); + (*_ear)[node] = arc; Node n = node; while (n != base) { n = _graph.target((*_matching)[n]); Arc a = (*_ear)[n]; n = _graph.target(a); - _ear->set(n, _graph.oppositeArc(a)); + (*_ear)[n] = _graph.oppositeArc(a); } node = _graph.target((*_matching)[base]); _tree_set->erase(base); _tree_set->erase(node); _blossom_set->insert(node, _blossom_set->find(base)); - _status->set(node, EVEN); + (*_status)[node] = EVEN; _node_queue[_last++] = node; arc = _graph.oppositeArc((*_ear)[node]); node = _graph.target((*_ear)[node]); @@ -335,7 +335,7 @@ } } - _blossom_rep->set(_blossom_set->find(nca), nca); + (*_blossom_rep)[_blossom_set->find(nca)] = nca; } @@ -344,11 +344,11 @@ Node base = _graph.source(a); Node odd = _graph.target(a); - _ear->set(odd, _graph.oppositeArc(a)); + (*_ear)[odd] = _graph.oppositeArc(a); Node even = _graph.target((*_matching)[odd]); - _blossom_rep->set(_blossom_set->insert(even), even); - _status->set(odd, ODD); - _status->set(even, EVEN); + (*_blossom_rep)[_blossom_set->insert(even)] = even; + (*_status)[odd] = ODD; + (*_status)[even] = EVEN; int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(base)]); _tree_set->insert(odd, tree); _tree_set->insert(even, tree); @@ -362,30 +362,30 @@ int tree = _tree_set->find((*_blossom_rep)[_blossom_set->find(even)]); - _matching->set(odd, _graph.oppositeArc(a)); - _status->set(odd, MATCHED); + (*_matching)[odd] = _graph.oppositeArc(a); + (*_status)[odd] = MATCHED; Arc arc = (*_matching)[even]; - _matching->set(even, a); + (*_matching)[even] = a; while (arc != INVALID) { odd = _graph.target(arc); arc = (*_ear)[odd]; even = _graph.target(arc); - _matching->set(odd, arc); + (*_matching)[odd] = arc; arc = (*_matching)[even]; - _matching->set(even, _graph.oppositeArc((*_matching)[odd])); + (*_matching)[even] = _graph.oppositeArc((*_matching)[odd]); } for (typename TreeSet::ItemIt it(*_tree_set, tree); it != INVALID; ++it) { if ((*_status)[it] == ODD) { - _status->set(it, MATCHED); + (*_status)[it] = MATCHED; } else { int blossom = _blossom_set->find(it); for (typename BlossomSet::ItemIt jt(*_blossom_set, blossom); jt != INVALID; ++jt) { - _status->set(jt, MATCHED); + (*_status)[jt] = MATCHED; } _blossom_set->eraseClass(blossom); } @@ -427,8 +427,8 @@ void init() { createStructures(); for(NodeIt n(_graph); n != INVALID; ++n) { - _matching->set(n, INVALID); - _status->set(n, UNMATCHED); + (*_matching)[n] = INVALID; + (*_status)[n] = UNMATCHED; } } @@ -438,18 +438,18 @@ void greedyInit() { createStructures(); for (NodeIt n(_graph); n != INVALID; ++n) { - _matching->set(n, INVALID); - _status->set(n, UNMATCHED); + (*_matching)[n] = INVALID; + (*_status)[n] = UNMATCHED; } for (NodeIt n(_graph); n != INVALID; ++n) { if ((*_matching)[n] == INVALID) { for (OutArcIt a(_graph, n); a != INVALID ; ++a) { Node v = _graph.target(a); if ((*_matching)[v] == INVALID && v != n) { - _matching->set(n, a); - _status->set(n, MATCHED); - _matching->set(v, _graph.oppositeArc(a)); - _status->set(v, MATCHED); + (*_matching)[n] = a; + (*_status)[n] = MATCHED; + (*_matching)[v] = _graph.oppositeArc(a); + (*_status)[v] = MATCHED; break; } } @@ -469,21 +469,21 @@ createStructures(); for (NodeIt n(_graph); n != INVALID; ++n) { - _matching->set(n, INVALID); - _status->set(n, UNMATCHED); + (*_matching)[n] = INVALID; + (*_status)[n] = UNMATCHED; } for(EdgeIt e(_graph); e!=INVALID; ++e) { if (matching[e]) { Node u = _graph.u(e); if ((*_matching)[u] != INVALID) return false; - _matching->set(u, _graph.direct(e, true)); - _status->set(u, MATCHED); + (*_matching)[u] = _graph.direct(e, true); + (*_status)[u] = MATCHED; Node v = _graph.v(e); if ((*_matching)[v] != INVALID) return false; - _matching->set(v, _graph.direct(e, false)); - _status->set(v, MATCHED); + (*_matching)[v] = _graph.direct(e, false); + (*_status)[v] = MATCHED; } } return true; @@ -497,7 +497,7 @@ if ((*_status)[n] == UNMATCHED) { (*_blossom_rep)[_blossom_set->insert(n)] = n; _tree_set->insert(n); - _status->set(n, EVEN); + (*_status)[n] = EVEN; processSparse(n); } } @@ -512,7 +512,7 @@ if ((*_status)[n] == UNMATCHED) { (*_blossom_rep)[_blossom_set->insert(n)] = n; _tree_set->insert(n); - _status->set(n, EVEN); + (*_status)[n] = EVEN; processDense(n); } } @@ -1548,9 +1548,9 @@ int bi = (*_node_index)[base]; Value pot = (*_node_data)[bi].pot; - _matching->set(base, matching); + (*_matching)[base] = matching; _blossom_node_list.push_back(base); - _node_potential->set(base, pot); + (*_node_potential)[base] = pot; } else { Value pot = (*_blossom_data)[blossom].pot; @@ -1644,17 +1644,17 @@ createStructures(); for (ArcIt e(_graph); e != INVALID; ++e) { - _node_heap_index->set(e, BinHeap::PRE_HEAP); + (*_node_heap_index)[e] = BinHeap::PRE_HEAP; } for (NodeIt n(_graph); n != INVALID; ++n) { - _delta1_index->set(n, _delta1->PRE_HEAP); + (*_delta1_index)[n] = _delta1->PRE_HEAP; } for (EdgeIt e(_graph); e != INVALID; ++e) { - _delta3_index->set(e, _delta3->PRE_HEAP); + (*_delta3_index)[e] = _delta3->PRE_HEAP; } for (int i = 0; i < _blossom_num; ++i) { - _delta2_index->set(i, _delta2->PRE_HEAP); - _delta4_index->set(i, _delta4->PRE_HEAP); + (*_delta2_index)[i] = _delta2->PRE_HEAP; + (*_delta4_index)[i] = _delta4->PRE_HEAP; } int index = 0; @@ -1666,7 +1666,7 @@ max = (dualScale * _weight[e]) / 2; } } - _node_index->set(n, index); + (*_node_index)[n] = index; (*_node_data)[index].pot = max; _delta1->push(n, max); int blossom = @@ -2741,9 +2741,9 @@ int bi = (*_node_index)[base]; Value pot = (*_node_data)[bi].pot; - _matching->set(base, matching); + (*_matching)[base] = matching; _blossom_node_list.push_back(base); - _node_potential->set(base, pot); + (*_node_potential)[base] = pot; } else { Value pot = (*_blossom_data)[blossom].pot; @@ -2831,14 +2831,14 @@ createStructures(); for (ArcIt e(_graph); e != INVALID; ++e) { - _node_heap_index->set(e, BinHeap::PRE_HEAP); + (*_node_heap_index)[e] = BinHeap::PRE_HEAP; } for (EdgeIt e(_graph); e != INVALID; ++e) { - _delta3_index->set(e, _delta3->PRE_HEAP); + (*_delta3_index)[e] = _delta3->PRE_HEAP; } for (int i = 0; i < _blossom_num; ++i) { - _delta2_index->set(i, _delta2->PRE_HEAP); - _delta4_index->set(i, _delta4->PRE_HEAP); + (*_delta2_index)[i] = _delta2->PRE_HEAP; + (*_delta4_index)[i] = _delta4->PRE_HEAP; } int index = 0; @@ -2850,7 +2850,7 @@ max = (dualScale * _weight[e]) / 2; } } - _node_index->set(n, index); + (*_node_index)[n] = index; (*_node_data)[index].pot = max; int blossom = _blossom_set->insert(n, std::numeric_limits::max()); diff -r a3402913cffe -r f63e87b9748e lemon/min_cost_arborescence.h --- a/lemon/min_cost_arborescence.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/min_cost_arborescence.h Tue Apr 21 10:34:49 2009 +0100 @@ -90,10 +90,10 @@ /// \ingroup spantree /// - /// \brief %MinCostArborescence algorithm class. + /// \brief Minimum Cost Arborescence algorithm class. /// /// This class provides an efficient implementation of - /// %MinCostArborescence algorithm. The arborescence is a tree + /// Minimum Cost Arborescence algorithm. The arborescence is a tree /// which is directed from a given source node of the digraph. One or /// more sources should be given for the algorithm and it will calculate /// the minimum cost subgraph which are union of arborescences with the @@ -293,7 +293,7 @@ minimum = (*_cost_arcs)[nodes[i]]; } } - _arc_order->set(minimum.arc, _dual_variables.size()); + (*_arc_order)[minimum.arc] = _dual_variables.size(); DualVariable var(_dual_node_list.size() - 1, _dual_node_list.size(), minimum.value); _dual_variables.push_back(var); @@ -335,7 +335,7 @@ minimum = (*_cost_arcs)[nodes[i]]; } } - _arc_order->set(minimum.arc, _dual_variables.size()); + (*_arc_order)[minimum.arc] = _dual_variables.size(); DualVariable var(node_bottom, _dual_node_list.size(), minimum.value); _dual_variables.push_back(var); StackLevel level; @@ -364,7 +364,7 @@ while (!_heap->empty()) { Node source = _heap->top(); _heap->pop(); - _node_order->set(source, -1); + (*_node_order)[source] = -1; for (OutArcIt it(*_digraph, source); it != INVALID; ++it) { if ((*_arc_order)[it] < 0) continue; Node target = _digraph->target(it); @@ -390,7 +390,7 @@ public: - /// \name Named template parameters + /// \name Named Template Parameters /// @{ @@ -630,7 +630,7 @@ /// @} - /// \name Execution control + /// \name Execution Control /// The simplest way to execute the algorithm is to use /// one of the member functions called \c run(...). \n /// If you need more control on the execution, @@ -650,13 +650,13 @@ _heap->clear(); for (NodeIt it(*_digraph); it != INVALID; ++it) { (*_cost_arcs)[it].arc = INVALID; - _node_order->set(it, -3); - _heap_cross_ref->set(it, Heap::PRE_HEAP); + (*_node_order)[it] = -3; + (*_heap_cross_ref)[it] = Heap::PRE_HEAP; _pred->set(it, INVALID); } for (ArcIt it(*_digraph); it != INVALID; ++it) { _arborescence->set(it, false); - _arc_order->set(it, -1); + (*_arc_order)[it] = -1; } _dual_node_list.clear(); _dual_variables.clear(); diff -r a3402913cffe -r f63e87b9748e lemon/preflow.h --- a/lemon/preflow.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/preflow.h Tue Apr 21 10:34:49 2009 +0100 @@ -404,7 +404,7 @@ _phase = true; for (NodeIt n(_graph); n != INVALID; ++n) { - _excess->set(n, 0); + (*_excess)[n] = 0; } for (ArcIt e(_graph); e != INVALID; ++e) { @@ -417,10 +417,10 @@ _level->initAddItem(_target); std::vector queue; - reached.set(_source, true); + reached[_source] = true; queue.push_back(_target); - reached.set(_target, true); + reached[_target] = true; while (!queue.empty()) { _level->initNewLevel(); std::vector nqueue; @@ -429,7 +429,7 @@ for (InArcIt e(_graph, n); e != INVALID; ++e) { Node u = _graph.source(e); if (!reached[u] && _tolerance.positive((*_capacity)[e])) { - reached.set(u, true); + reached[u] = true; _level->initAddItem(u); nqueue.push_back(u); } @@ -444,7 +444,7 @@ Node u = _graph.target(e); if ((*_level)[u] == _level->maxLevel()) continue; _flow->set(e, (*_capacity)[e]); - _excess->set(u, (*_excess)[u] + (*_capacity)[e]); + (*_excess)[u] += (*_capacity)[e]; if (u != _target && !_level->active(u)) { _level->activate(u); } @@ -478,7 +478,7 @@ excess -= (*_flow)[e]; } if (excess < 0 && n != _source) return false; - _excess->set(n, excess); + (*_excess)[n] = excess; } typename Digraph::template NodeMap reached(_graph, false); @@ -487,10 +487,10 @@ _level->initAddItem(_target); std::vector queue; - reached.set(_source, true); + reached[_source] = true; queue.push_back(_target); - reached.set(_target, true); + reached[_target] = true; while (!queue.empty()) { _level->initNewLevel(); std::vector nqueue; @@ -500,7 +500,7 @@ Node u = _graph.source(e); if (!reached[u] && _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { - reached.set(u, true); + reached[u] = true; _level->initAddItem(u); nqueue.push_back(u); } @@ -508,7 +508,7 @@ for (OutArcIt e(_graph, n); e != INVALID; ++e) { Node v = _graph.target(e); if (!reached[v] && _tolerance.positive((*_flow)[e])) { - reached.set(v, true); + reached[v] = true; _level->initAddItem(v); nqueue.push_back(v); } @@ -524,7 +524,7 @@ Node u = _graph.target(e); if ((*_level)[u] == _level->maxLevel()) continue; _flow->set(e, (*_capacity)[e]); - _excess->set(u, (*_excess)[u] + rem); + (*_excess)[u] += rem; if (u != _target && !_level->active(u)) { _level->activate(u); } @@ -536,7 +536,7 @@ Node v = _graph.source(e); if ((*_level)[v] == _level->maxLevel()) continue; _flow->set(e, 0); - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; if (v != _target && !_level->active(v)) { _level->activate(v); } @@ -577,12 +577,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push_1; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, (*_capacity)[e]); } } else if (new_level > (*_level)[v]) { @@ -600,12 +600,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push_1; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, 0); } } else if (new_level > (*_level)[v]) { @@ -615,7 +615,7 @@ no_more_push_1: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if (new_level + 1 < _level->maxLevel()) { @@ -650,12 +650,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push_2; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, (*_capacity)[e]); } } else if (new_level > (*_level)[v]) { @@ -673,12 +673,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push_2; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, 0); } } else if (new_level > (*_level)[v]) { @@ -688,7 +688,7 @@ no_more_push_2: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if (new_level + 1 < _level->maxLevel()) { @@ -731,7 +731,7 @@ typename Digraph::template NodeMap reached(_graph); for (NodeIt n(_graph); n != INVALID; ++n) { - reached.set(n, (*_level)[n] < _level->maxLevel()); + reached[n] = (*_level)[n] < _level->maxLevel(); } _level->initStart(); @@ -739,7 +739,7 @@ std::vector queue; queue.push_back(_source); - reached.set(_source, true); + reached[_source] = true; while (!queue.empty()) { _level->initNewLevel(); @@ -749,7 +749,7 @@ for (OutArcIt e(_graph, n); e != INVALID; ++e) { Node v = _graph.target(e); if (!reached[v] && _tolerance.positive((*_flow)[e])) { - reached.set(v, true); + reached[v] = true; _level->initAddItem(v); nqueue.push_back(v); } @@ -758,7 +758,7 @@ Node u = _graph.source(e); if (!reached[u] && _tolerance.positive((*_capacity)[e] - (*_flow)[e])) { - reached.set(u, true); + reached[u] = true; _level->initAddItem(u); nqueue.push_back(u); } @@ -792,12 +792,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] + excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, (*_capacity)[e]); } } else if (new_level > (*_level)[v]) { @@ -815,12 +815,12 @@ } if (!_tolerance.less(rem, excess)) { _flow->set(e, (*_flow)[e] - excess); - _excess->set(v, (*_excess)[v] + excess); + (*_excess)[v] += excess; excess = 0; goto no_more_push; } else { excess -= rem; - _excess->set(v, (*_excess)[v] + rem); + (*_excess)[v] += rem; _flow->set(e, 0); } } else if (new_level > (*_level)[v]) { @@ -830,7 +830,7 @@ no_more_push: - _excess->set(n, excess); + (*_excess)[n] = excess; if (excess != 0) { if (new_level + 1 < _level->maxLevel()) { diff -r a3402913cffe -r f63e87b9748e lemon/random.h --- a/lemon/random.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/random.h Tue Apr 21 10:34:49 2009 +0100 @@ -659,7 +659,7 @@ /// @} - ///\name Uniform distributions + ///\name Uniform Distributions /// /// @{ @@ -762,7 +762,7 @@ /// @} - ///\name Non-uniform distributions + ///\name Non-uniform Distributions /// ///@{ @@ -938,7 +938,7 @@ ///@} - ///\name Two dimensional distributions + ///\name Two Dimensional Distributions /// ///@{ diff -r a3402913cffe -r f63e87b9748e lemon/smart_graph.h --- a/lemon/smart_graph.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/smart_graph.h Tue Apr 21 10:34:49 2009 +0100 @@ -191,9 +191,7 @@ ///It is also quite memory efficient, but at the price ///that it does support only limited (only stack-like) ///node and arc deletions. - ///It conforms to the \ref concepts::Digraph "Digraph concept" with - ///an important extra feature that its maps are real \ref - ///concepts::ReferenceMap "reference map"s. + ///It fully conforms to the \ref concepts::Digraph "Digraph concept". /// ///\sa concepts::Digraph. class SmartDigraph : public ExtendedSmartDigraphBase { @@ -629,15 +627,9 @@ /// It is also quite memory efficient, but at the price /// that it does support only limited (only stack-like) /// node and arc deletions. - /// Except from this it conforms to - /// the \ref concepts::Graph "Graph concept". - /// - /// It also has an - /// important extra feature that - /// its maps are real \ref concepts::ReferenceMap "reference map"s. + /// It fully conforms to the \ref concepts::Graph "Graph concept". /// /// \sa concepts::Graph. - /// class SmartGraph : public ExtendedSmartGraphBase { private: diff -r a3402913cffe -r f63e87b9748e lemon/soplex.cc --- a/lemon/soplex.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/soplex.cc Tue Apr 21 10:34:49 2009 +0100 @@ -20,6 +20,7 @@ #include #include +#include ///\file @@ -28,6 +29,7 @@ SoplexLp::SoplexLp() { soplex = new soplex::SoPlex; + messageLevel(MESSAGE_NOTHING); } SoplexLp::~SoplexLp() { @@ -47,6 +49,7 @@ _row_names = lp._row_names; _row_names_ref = lp._row_names_ref; + messageLevel(MESSAGE_NOTHING); } void SoplexLp::_clear_temporals() { @@ -271,6 +274,8 @@ SoplexLp::SolveExitStatus SoplexLp::_solve() { _clear_temporals(); + + _applyMessageLevel(); soplex::SPxSolver::Status status = soplex->solve(); @@ -419,5 +424,29 @@ _clear_temporals(); } + void SoplexLp::_messageLevel(MessageLevel level) { + switch (level) { + case MESSAGE_NOTHING: + _message_level = -1; + break; + case MESSAGE_ERROR: + _message_level = soplex::SPxOut::ERROR; + break; + case MESSAGE_WARNING: + _message_level = soplex::SPxOut::WARNING; + break; + case MESSAGE_NORMAL: + _message_level = soplex::SPxOut::INFO2; + break; + case MESSAGE_VERBOSE: + _message_level = soplex::SPxOut::DEBUG; + break; + } + } + + void SoplexLp::_applyMessageLevel() { + soplex::Param::setVerbose(_message_level); + } + } //namespace lemon diff -r a3402913cffe -r f63e87b9748e lemon/soplex.h --- a/lemon/soplex.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/soplex.h Tue Apr 21 10:34:49 2009 +0100 @@ -144,6 +144,11 @@ virtual void _clear(); + void _messageLevel(MessageLevel m); + void _applyMessageLevel(); + + int _message_level; + }; } //END OF NAMESPACE LEMON diff -r a3402913cffe -r f63e87b9748e lemon/suurballe.h --- a/lemon/suurballe.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/suurballe.h Tue Apr 21 10:34:49 2009 +0100 @@ -288,7 +288,7 @@ return *this; } - /// \name Execution control + /// \name Execution Control /// The simplest way to execute the algorithm is to call the run() /// function. /// \n diff -r a3402913cffe -r f63e87b9748e lemon/time_measure.h --- a/lemon/time_measure.h Sat Apr 18 21:54:30 2009 +0200 +++ b/lemon/time_measure.h Tue Apr 21 10:34:49 2009 +0100 @@ -287,7 +287,7 @@ /// Timer(bool run=true) :_running(run) {_reset();} - ///\name Control the state of the timer + ///\name Control the State of the Timer ///Basically a Timer can be either running or stopped, ///but it provides a bit finer control on the execution. ///The \ref lemon::Timer "Timer" also counts the number of @@ -395,7 +395,7 @@ ///@} - ///\name Query Functions for the ellapsed time + ///\name Query Functions for the Ellapsed Time ///@{ diff -r a3402913cffe -r f63e87b9748e test/bfs_test.cc --- a/test/bfs_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/bfs_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -58,41 +58,80 @@ typedef Digraph::Arc Arc; Digraph G; - Node s, t; + Node s, t, n; Arc e; - int l; + int l, i; bool b; BType::DistMap d(G); BType::PredMap p(G); Path pp; + concepts::ReadMap nm; { BType bfs_test(G); + const BType& const_bfs_test = bfs_test; bfs_test.run(s); bfs_test.run(s,t); bfs_test.run(); - l = bfs_test.dist(t); - e = bfs_test.predArc(t); - s = bfs_test.predNode(t); - b = bfs_test.reached(t); - d = bfs_test.distMap(); - p = bfs_test.predMap(); - pp = bfs_test.path(t); + bfs_test.init(); + bfs_test.addSource(s); + n = bfs_test.processNextNode(); + n = bfs_test.processNextNode(t, b); + n = bfs_test.processNextNode(nm, n); + n = const_bfs_test.nextNode(); + b = const_bfs_test.emptyQueue(); + i = const_bfs_test.queueSize(); + + bfs_test.start(); + bfs_test.start(t); + bfs_test.start(nm); + + l = const_bfs_test.dist(t); + e = const_bfs_test.predArc(t); + s = const_bfs_test.predNode(t); + b = const_bfs_test.reached(t); + d = const_bfs_test.distMap(); + p = const_bfs_test.predMap(); + pp = const_bfs_test.path(t); } { BType ::SetPredMap > ::SetDistMap > ::SetReachedMap > + ::SetStandardProcessedMap ::SetProcessedMap > - ::SetStandardProcessedMap ::Create bfs_test(G); + + concepts::ReadWriteMap pred_map; + concepts::ReadWriteMap dist_map; + concepts::ReadWriteMap reached_map; + concepts::WriteMap processed_map; + + bfs_test + .predMap(pred_map) + .distMap(dist_map) + .reachedMap(reached_map) + .processedMap(processed_map); bfs_test.run(s); bfs_test.run(s,t); bfs_test.run(); + + bfs_test.init(); + bfs_test.addSource(s); + n = bfs_test.processNextNode(); + n = bfs_test.processNextNode(t, b); + n = bfs_test.processNextNode(nm, n); + n = bfs_test.nextNode(); + b = bfs_test.emptyQueue(); + i = bfs_test.queueSize(); + + bfs_test.start(); + bfs_test.start(t); + bfs_test.start(nm); l = bfs_test.dist(t); e = bfs_test.predArc(t); diff -r a3402913cffe -r f63e87b9748e test/circulation_test.cc --- a/test/circulation_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/circulation_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -71,27 +71,34 @@ DeltaMap delta; FlowMap flow; BarrierMap bar; + VType v; + bool b; - Circulation - ::SetFlowMap - ::SetElevator - ::SetStandardElevator - ::Create circ_test(g,lcap,ucap,delta); - - circ_test.lowerCapMap(lcap); - circ_test.upperCapMap(ucap); - circ_test.deltaMap(delta); - flow = circ_test.flowMap(); - circ_test.flowMap(flow); + typedef Circulation + ::SetFlowMap + ::SetElevator + ::SetStandardElevator + ::Create CirculationType; + CirculationType circ_test(g, lcap, ucap, delta); + const CirculationType& const_circ_test = circ_test; + + circ_test + .lowerCapMap(lcap) + .upperCapMap(ucap) + .deltaMap(delta) + .flowMap(flow); circ_test.init(); circ_test.greedyInit(); circ_test.start(); circ_test.run(); - circ_test.barrier(n); - circ_test.barrierMap(bar); - circ_test.flow(a); + v = const_circ_test.flow(a); + const FlowMap& fm = const_circ_test.flowMap(); + b = const_circ_test.barrier(n); + const_circ_test.barrierMap(bar); + + ignore_unused_variable_warning(fm); } template diff -r a3402913cffe -r f63e87b9748e test/dfs_test.cc --- a/test/dfs_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/dfs_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -62,39 +62,74 @@ Digraph G; Node s, t; Arc e; - int l; + int l, i; bool b; DType::DistMap d(G); DType::PredMap p(G); Path pp; + concepts::ReadMap am; { DType dfs_test(G); + const DType& const_dfs_test = dfs_test; dfs_test.run(s); dfs_test.run(s,t); dfs_test.run(); - l = dfs_test.dist(t); - e = dfs_test.predArc(t); - s = dfs_test.predNode(t); - b = dfs_test.reached(t); - d = dfs_test.distMap(); - p = dfs_test.predMap(); - pp = dfs_test.path(t); + dfs_test.init(); + dfs_test.addSource(s); + e = dfs_test.processNextArc(); + e = const_dfs_test.nextArc(); + b = const_dfs_test.emptyQueue(); + i = const_dfs_test.queueSize(); + + dfs_test.start(); + dfs_test.start(t); + dfs_test.start(am); + + l = const_dfs_test.dist(t); + e = const_dfs_test.predArc(t); + s = const_dfs_test.predNode(t); + b = const_dfs_test.reached(t); + d = const_dfs_test.distMap(); + p = const_dfs_test.predMap(); + pp = const_dfs_test.path(t); } { DType ::SetPredMap > ::SetDistMap > ::SetReachedMap > + ::SetStandardProcessedMap ::SetProcessedMap > - ::SetStandardProcessedMap ::Create dfs_test(G); + concepts::ReadWriteMap pred_map; + concepts::ReadWriteMap dist_map; + concepts::ReadWriteMap reached_map; + concepts::WriteMap processed_map; + + dfs_test + .predMap(pred_map) + .distMap(dist_map) + .reachedMap(reached_map) + .processedMap(processed_map); + dfs_test.run(s); dfs_test.run(s,t); dfs_test.run(); + dfs_test.init(); + + dfs_test.addSource(s); + e = dfs_test.processNextArc(); + e = dfs_test.nextArc(); + b = dfs_test.emptyQueue(); + i = dfs_test.queueSize(); + + dfs_test.start(); + dfs_test.start(t); + dfs_test.start(am); l = dfs_test.dist(t); e = dfs_test.predArc(t); diff -r a3402913cffe -r f63e87b9748e test/dijkstra_test.cc --- a/test/dijkstra_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/dijkstra_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -60,48 +60,94 @@ typedef Digraph::Arc Arc; Digraph G; - Node s, t; + Node s, t, n; Arc e; VType l; + int i; bool b; DType::DistMap d(G); DType::PredMap p(G); LengthMap length; Path pp; + concepts::ReadMap nm; { DType dijkstra_test(G,length); + const DType& const_dijkstra_test = dijkstra_test; dijkstra_test.run(s); dijkstra_test.run(s,t); + dijkstra_test.init(); + dijkstra_test.addSource(s); + dijkstra_test.addSource(s, 1); + n = dijkstra_test.processNextNode(); + n = const_dijkstra_test.nextNode(); + b = const_dijkstra_test.emptyQueue(); + i = const_dijkstra_test.queueSize(); + + dijkstra_test.start(); + dijkstra_test.start(t); + dijkstra_test.start(nm); + + l = const_dijkstra_test.dist(t); + e = const_dijkstra_test.predArc(t); + s = const_dijkstra_test.predNode(t); + b = const_dijkstra_test.reached(t); + b = const_dijkstra_test.processed(t); + d = const_dijkstra_test.distMap(); + p = const_dijkstra_test.predMap(); + pp = const_dijkstra_test.path(t); + l = const_dijkstra_test.currentDist(t); + } + { + DType + ::SetPredMap > + ::SetDistMap > + ::SetStandardProcessedMap + ::SetProcessedMap > + ::SetOperationTraits > + ::SetHeap > > + ::SetStandardHeap > > + ::SetHeap >, + concepts::ReadWriteMap > + ::Create dijkstra_test(G,length); + + LengthMap length_map; + concepts::ReadWriteMap pred_map; + concepts::ReadWriteMap dist_map; + concepts::WriteMap processed_map; + concepts::ReadWriteMap heap_cross_ref; + BinHeap > heap(heap_cross_ref); + + dijkstra_test + .lengthMap(length_map) + .predMap(pred_map) + .distMap(dist_map) + .processedMap(processed_map) + .heap(heap, heap_cross_ref); + + dijkstra_test.run(s); + dijkstra_test.run(s,t); + + dijkstra_test.addSource(s); + dijkstra_test.addSource(s, 1); + n = dijkstra_test.processNextNode(); + n = dijkstra_test.nextNode(); + b = dijkstra_test.emptyQueue(); + i = dijkstra_test.queueSize(); + + dijkstra_test.start(); + dijkstra_test.start(t); + dijkstra_test.start(nm); + l = dijkstra_test.dist(t); e = dijkstra_test.predArc(t); s = dijkstra_test.predNode(t); b = dijkstra_test.reached(t); - d = dijkstra_test.distMap(); - p = dijkstra_test.predMap(); + b = dijkstra_test.processed(t); pp = dijkstra_test.path(t); - } - { - DType - ::SetPredMap > - ::SetDistMap > - ::SetProcessedMap > - ::SetStandardProcessedMap - ::SetOperationTraits > - ::SetHeap > > - ::SetStandardHeap > > - ::Create dijkstra_test(G,length); - - dijkstra_test.run(s); - dijkstra_test.run(s,t); - - l = dijkstra_test.dist(t); - e = dijkstra_test.predArc(t); - s = dijkstra_test.predNode(t); - b = dijkstra_test.reached(t); - pp = dijkstra_test.path(t); + l = dijkstra_test.currentDist(t); } } diff -r a3402913cffe -r f63e87b9748e test/gomory_hu_test.cc --- a/test/gomory_hu_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/gomory_hu_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -2,6 +2,8 @@ #include "test_tools.h" #include +#include +#include #include #include #include @@ -32,6 +34,36 @@ "source 0\n" "target 3\n"; +void checkGomoryHuCompile() +{ + typedef int Value; + typedef concepts::Graph Graph; + + typedef Graph::Node Node; + typedef Graph::Edge Edge; + typedef concepts::ReadMap CapMap; + typedef concepts::ReadWriteMap CutMap; + + Graph g; + Node n; + CapMap cap; + CutMap cut; + Value v; + int d; + + GomoryHu gh_test(g, cap); + const GomoryHu& + const_gh_test = gh_test; + + gh_test.run(); + + n = const_gh_test.predNode(n); + v = const_gh_test.predValue(n); + d = const_gh_test.rootDist(n); + v = const_gh_test.minCutValue(n, n); + v = const_gh_test.minCutMap(n, n, cut); +} + GRAPH_TYPEDEFS(Graph); typedef Graph::EdgeMap IntEdgeMap; typedef Graph::NodeMap BoolNodeMap; @@ -70,8 +102,8 @@ BoolNodeMap cm(graph); ght.minCutMap(u, v, cm); check(pf.flowValue() == ght.minCutValue(u, v), "Wrong cut 1"); - check(cm[u] != cm[v], "Wrong cut 3"); - check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 2"); + check(cm[u] != cm[v], "Wrong cut 2"); + check(pf.flowValue() == cutValue(graph, cm, capacity), "Wrong cut 3"); int sum=0; for(GomoryHu::MinCutEdgeIt a(ght, u, v);a!=INVALID;++a) @@ -84,7 +116,6 @@ for(GomoryHu::MinCutNodeIt n(ght, u, v,false);n!=INVALID;++n) sum++; check(sum == countNodes(graph), "Problem with MinCutNodeIt"); - } } diff -r a3402913cffe -r f63e87b9748e test/hao_orlin_test.cc --- a/test/hao_orlin_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/hao_orlin_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -19,9 +19,12 @@ #include #include +#include +#include +#include +#include #include -#include #include "test_tools.h" using namespace lemon; @@ -37,27 +40,124 @@ "4\n" "5\n" "@edges\n" - " label capacity\n" - "0 1 0 2\n" - "1 2 1 2\n" - "2 0 2 2\n" - "3 4 3 2\n" - "4 5 4 2\n" - "5 3 5 2\n" - "2 3 6 3\n"; + " cap1 cap2 cap3\n" + "0 1 1 1 1 \n" + "0 2 2 2 4 \n" + "1 2 4 4 4 \n" + "3 4 1 1 1 \n" + "3 5 2 2 4 \n" + "4 5 4 4 4 \n" + "5 4 4 4 4 \n" + "2 3 1 6 6 \n" + "4 0 1 6 6 \n"; + +void checkHaoOrlinCompile() +{ + typedef int Value; + typedef concepts::Digraph Digraph; + + typedef Digraph::Node Node; + typedef Digraph::Arc Arc; + typedef concepts::ReadMap CapMap; + typedef concepts::WriteMap CutMap; + + Digraph g; + Node n; + CapMap cap; + CutMap cut; + Value v; + + HaoOrlin ho_test(g, cap); + const HaoOrlin& + const_ho_test = ho_test; + + ho_test.init(); + ho_test.init(n); + ho_test.calculateOut(); + ho_test.calculateIn(); + ho_test.run(); + ho_test.run(n); + + v = const_ho_test.minCutValue(); + v = const_ho_test.minCutMap(cut); +} + +template +typename CapMap::Value + cutValue(const Graph& graph, const CapMap& cap, const CutMap& cut) +{ + typename CapMap::Value sum = 0; + for (typename Graph::ArcIt a(graph); a != INVALID; ++a) { + if (cut[graph.source(a)] && !cut[graph.target(a)]) + sum += cap[a]; + } + return sum; +} int main() { - SmartGraph graph; - SmartGraph::EdgeMap capacity(graph); + SmartDigraph graph; + SmartDigraph::ArcMap cap1(graph), cap2(graph), cap3(graph); + SmartDigraph::NodeMap cut(graph); - istringstream lgfs(lgf); - graphReader(graph, lgfs). - edgeMap("capacity", capacity).run(); + istringstream input(lgf); + digraphReader(graph, input) + .arcMap("cap1", cap1) + .arcMap("cap2", cap2) + .arcMap("cap3", cap3) + .run(); - HaoOrlin > ho(graph, capacity); - ho.run(); + { + HaoOrlin ho(graph, cap1); + ho.run(); + ho.minCutMap(cut); + + check(ho.minCutValue() == 1, "Wrong cut value"); + check(ho.minCutValue() == cutValue(graph, cap1, cut), "Wrong cut value"); + } + { + HaoOrlin ho(graph, cap2); + ho.run(); + ho.minCutMap(cut); - check(ho.minCutValue() == 3, "Wrong cut value"); + check(ho.minCutValue() == 1, "Wrong cut value"); + check(ho.minCutValue() == cutValue(graph, cap2, cut), "Wrong cut value"); + } + { + HaoOrlin ho(graph, cap3); + ho.run(); + ho.minCutMap(cut); + + check(ho.minCutValue() == 1, "Wrong cut value"); + check(ho.minCutValue() == cutValue(graph, cap3, cut), "Wrong cut value"); + } + + typedef Undirector UGraph; + UGraph ugraph(graph); + + { + HaoOrlin > ho(ugraph, cap1); + ho.run(); + ho.minCutMap(cut); + + check(ho.minCutValue() == 2, "Wrong cut value"); + check(ho.minCutValue() == cutValue(ugraph, cap1, cut), "Wrong cut value"); + } + { + HaoOrlin > ho(ugraph, cap2); + ho.run(); + ho.minCutMap(cut); + + check(ho.minCutValue() == 5, "Wrong cut value"); + check(ho.minCutValue() == cutValue(ugraph, cap2, cut), "Wrong cut value"); + } + { + HaoOrlin > ho(ugraph, cap3); + ho.run(); + ho.minCutMap(cut); + + check(ho.minCutValue() == 5, "Wrong cut value"); + check(ho.minCutValue() == cutValue(ugraph, cap3, cut), "Wrong cut value"); + } return 0; } diff -r a3402913cffe -r f63e87b9748e test/kruskal_test.cc --- a/test/kruskal_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/kruskal_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -99,16 +99,16 @@ check(kruskal(G, edge_cost_map, tree_map)==10, "Total cost should be 10"); - edge_cost_map.set(e1, -10); - edge_cost_map.set(e2, -9); - edge_cost_map.set(e3, -8); - edge_cost_map.set(e4, -7); - edge_cost_map.set(e5, -6); - edge_cost_map.set(e6, -5); - edge_cost_map.set(e7, -4); - edge_cost_map.set(e8, -3); - edge_cost_map.set(e9, -2); - edge_cost_map.set(e10, -1); + edge_cost_map[e1] = -10; + edge_cost_map[e2] = -9; + edge_cost_map[e3] = -8; + edge_cost_map[e4] = -7; + edge_cost_map[e5] = -6; + edge_cost_map[e6] = -5; + edge_cost_map[e7] = -4; + edge_cost_map[e8] = -3; + edge_cost_map[e9] = -2; + edge_cost_map[e10] = -1; vector tree_edge_vec(5); diff -r a3402913cffe -r f63e87b9748e test/lp_test.cc --- a/test/lp_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/lp_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -395,12 +395,7 @@ aTest(lp_cplex2); cloneTest(); } catch (CplexEnv::LicenseError& error) { -#ifdef LEMON_FORCE_CPLEX_CHECK check(false, error.what()); -#else - std::cerr << error.what() << std::endl; - std::cerr << "Cplex license check failed, lp check skipped" << std::endl; -#endif } #endif diff -r a3402913cffe -r f63e87b9748e test/mip_test.cc --- a/test/mip_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/mip_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -143,12 +143,7 @@ aTest(mip2); cloneTest(); } catch (CplexEnv::LicenseError& error) { -#ifdef LEMON_FORCE_CPLEX_CHECK check(false, error.what()); -#else - std::cerr << error.what() << std::endl; - std::cerr << "Cplex license check failed, lp check skipped" << std::endl; -#endif } #endif diff -r a3402913cffe -r f63e87b9748e test/preflow_test.cc --- a/test/preflow_test.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/test/preflow_test.cc Tue Apr 21 10:34:49 2009 +0100 @@ -84,18 +84,22 @@ CapMap cap; FlowMap flow; CutMap cut; + VType v; + bool b; - Preflow - ::SetFlowMap - ::SetElevator - ::SetStandardElevator - ::Create preflow_test(g,cap,n,n); + typedef Preflow + ::SetFlowMap + ::SetElevator + ::SetStandardElevator + ::Create PreflowType; + PreflowType preflow_test(g, cap, n, n); + const PreflowType& const_preflow_test = preflow_test; - preflow_test.capacityMap(cap); - flow = preflow_test.flowMap(); - preflow_test.flowMap(flow); - preflow_test.source(n); - preflow_test.target(n); + preflow_test + .capacityMap(cap) + .flowMap(flow) + .source(n) + .target(n); preflow_test.init(); preflow_test.init(cap); @@ -104,11 +108,13 @@ preflow_test.run(); preflow_test.runMinCut(); - preflow_test.flowValue(); - preflow_test.minCut(n); - preflow_test.minCutMap(cut); - preflow_test.flow(e); - + v = const_preflow_test.flowValue(); + v = const_preflow_test.flow(e); + const FlowMap& fm = const_preflow_test.flowMap(); + b = const_preflow_test.minCut(n); + const_preflow_test.minCutMap(cut); + + ignore_unused_variable_warning(fm); } int cutValue (const SmartDigraph& g, diff -r a3402913cffe -r f63e87b9748e tools/dimacs-solver.cc --- a/tools/dimacs-solver.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/tools/dimacs-solver.cc Tue Apr 21 10:34:49 2009 +0100 @@ -23,11 +23,10 @@ /// This program solves various problems given in DIMACS format. /// /// See -/// \verbatim -/// dimacs-solver --help -/// \endverbatim +/// \code +/// dimacs-solver --help +/// \endcode /// for more info on usage. -/// #include #include diff -r a3402913cffe -r f63e87b9748e tools/dimacs-to-lgf.cc --- a/tools/dimacs-to-lgf.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/tools/dimacs-to-lgf.cc Tue Apr 21 10:34:49 2009 +0100 @@ -24,11 +24,10 @@ /// (LGF). /// /// See -/// \verbatim -/// dimacs-to-lgf --help -/// \endverbatim -/// for more info on usage. -/// +/// \code +/// dimacs-to-lgf --help +/// \endcode +/// for more info on the usage. #include #include diff -r a3402913cffe -r f63e87b9748e tools/lemon-0.x-to-1.x.sh --- a/tools/lemon-0.x-to-1.x.sh Sat Apr 18 21:54:30 2009 +0200 +++ b/tools/lemon-0.x-to-1.x.sh Tue Apr 21 10:34:49 2009 +0100 @@ -89,6 +89,10 @@ -e "s/\<\([Ff]\)orkWriteMap\>/\1orkMap/g"\ -e "s/\/LoggerBoolMap/g"\ -e "s/\/loggerBoolMap/g"\ + -e "s/\/CrossRefMap/g"\ + -e "s/\/crossRefMap/g"\ + -e "s/\/RangeIdMap/g"\ + -e "s/\/rangeIdMap/g"\ -e "s/\/Box/g"\ -e "s/\/readNautyGraph/g"\ -e "s/\/ReverseDigraph/g"\ diff -r a3402913cffe -r f63e87b9748e tools/lgf-gen.cc --- a/tools/lgf-gen.cc Sat Apr 18 21:54:30 2009 +0200 +++ b/tools/lgf-gen.cc Tue Apr 21 10:34:49 2009 +0100 @@ -23,12 +23,10 @@ /// Graph generator application for various types of plane graphs. /// /// See -/// \verbatim -/// lgf-gen --help -/// \endverbatim +/// \code +/// lgf-gen --help +/// \endcode /// for more info on the usage. -/// - #include #include