LEMON/LEMON-official Changeset - r646:f63e87b9748e

Repositories » LEMON » LEMON-official

Summary
Changelog
Files
Switch To
- loading...
Options
- Lightweight changelog
- Search
Pull Requests

Changeset - r646:f63e87b9748e

« 644:2ca0cd
« 645:a34029

647:0ba8df »

r646:f63e87b9748e

Tue, 21 Apr 2009 11:34:49

[Not Reviewed]

0 comments (0 inline)

alpar (Alpar Juttner)
alpar@cs.elte.hu

Merge

0 64 6

merge default

2 files changed:

doc/images/bipartite_matching.eps

586

doc/images/bipartite_partitions.eps

114

doc/images/connected_components.eps

159

doc/images/edge_biconnected_components.eps

159

doc/images/node_biconnected_components.eps

159

doc/images/strongly_connected_components.eps

180

doc/CMakeLists.txt

doc/Makefile.am

doc/groups.dox

lemon/adaptors.h

lemon/bin_heap.h

lemon/bits/graph_adaptor_extender.h

lemon/bits/map_extender.h

lemon/cbc.cc

lemon/cbc.h

lemon/circulation.h

lemon/clp.cc

lemon/clp.h

lemon/concepts/digraph.h

lemon/concepts/graph.h

Changeset was too big and was cut off... Show full diff

↑ Collapse diff ↑

doc/images/bipartite_matching.eps

Show inline comments

 		%!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
 .402 32.047 m
 .945 293.946 814.484 555.844 814.484 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .012 32.047 m
 .465 293.946 735.918 555.844 735.918 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .492 32.047 m
 .703 293.946 735.918 555.844 735.918 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .832 32.047 m
 .375 293.946 735.918 555.844 735.918 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .355 32.047 m
 .637 293.946 735.918 555.844 735.918 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .25 555.844 m
 .633 293.946 749.012 32.047 749.012 32.047 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .016 555.844 m
 .516 293.946 749.012 32.047 749.012 32.047 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .535 32.047 m
 .894 293.946 644.25 555.844 644.25 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .453 555.844 m
 .992 293.946 683.535 32.047 683.535 32.047 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .7853 555.844 m
 .16 293.946 683.535 32.047 683.535 32.047 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .492 32.047 m
 .039 293.946 552.586 555.844 552.586 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .875 32.047 m
 .613 293.946 382.351 555.844 382.351 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .355 32.047 m
 .855 293.946 382.351 555.844 382.351 555.844 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .687 555.844 m
 .805 293.946 460.922 32.047 460.922 32.047 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .453 555.844 m
 .687 293.946 460.922 32.047 460.922 32.047 c
 		[] 0 d 0 0 0 r 1.96407 w s
+		N
 .832 32.047 m
 .64 293.946 120.453 555.844 120.453 555.844 c
 		[] 0 d 1 0 0 r 3.92814 w s
+		N
 .6913 555.844 m
 .6913 555.844 l
 .6913 548.614 21.5553 542.75 28.7853 542.75 c
 .0163 542.75 41.8833 548.614 41.8833 555.844 c
 .8833 563.075 36.0163 568.938 28.7853 568.938 c
 .5553 568.938 15.6913 563.075 15.6913 555.844 c
 .6913 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .8833 555.844 m
 .8833 555.844 l
 .8833 549.27 22.2113 543.942 28.7853 543.942 c
 .3593 543.942 40.6913 549.27 40.6913 555.844 c
 .6913 562.418 35.3593 567.747 28.7853 567.747 c
 .2113 567.747 16.8833 562.418 16.8833 555.844 c
 .8833 555.844 l
+		C
 		S 1 0.5 1 r f R
+		N
 .355 555.844 m
 .355 555.844 l
 .355 548.614 113.223 542.75 120.453 542.75 c
 .683 542.75 133.547 548.614 133.547 555.844 c
 .547 563.075 127.683 568.938 120.453 568.938 c
 .223 568.938 107.355 563.075 107.355 555.844 c
 .355 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .547 555.844 m
 .547 555.844 l
 .547 549.27 113.879 543.942 120.453 543.942 c
 .027 543.942 132.355 549.27 132.355 555.844 c
 .355 562.418 127.027 567.747 120.453 567.747 c
 .879 567.747 108.547 562.418 108.547 555.844 c
 .547 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .019 555.844 m
 .019 555.844 l
 .019 548.614 204.887 542.75 212.117 542.75 c
 .348 542.75 225.211 548.614 225.211 555.844 c
 .211 563.075 219.348 568.938 212.117 568.938 c
 .887 568.938 199.019 563.075 199.019 555.844 c
 .019 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .211 555.844 m
 .211 555.844 l
 .211 549.27 205.543 543.942 212.117 543.942 c
 .691 543.942 224.019 549.27 224.019 555.844 c
 .019 562.418 218.691 567.747 212.117 567.747 c
 .543 567.747 200.211 562.418 200.211 555.844 c
 .211 555.844 l
+		C
 		S 1 0.5 1 r f R
+		N
 .59 555.844 m
 .59 555.844 l
 .59 548.614 283.457 542.75 290.687 542.75 c
 .918 542.75 303.781 548.614 303.781 555.844 c
 .781 563.075 297.918 568.938 290.687 568.938 c
 .457 568.938 277.59 563.075 277.59 555.844 c
 .59 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .781 555.844 m
 .781 555.844 l
 .781 549.27 284.113 543.942 290.687 543.942 c
 .262 543.942 302.59 549.27 302.59 555.844 c
 .59 562.418 297.262 567.747 290.687 567.747 c
 .113 567.747 278.781 562.418 278.781 555.844 c
 .781 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .258 555.844 m
 .258 555.844 l
 .258 548.614 375.121 542.75 382.351 542.75 c
 .582 542.75 395.445 548.614 395.445 555.844 c
 .445 563.075 389.582 568.938 382.351 568.938 c
 .121 568.938 369.258 563.075 369.258 555.844 c
 .258 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .445 555.844 m
 .445 555.844 l
 .445 549.27 375.777 543.942 382.351 543.942 c
 .926 543.942 394.258 549.27 394.258 555.844 c
 .258 562.418 388.926 567.747 382.351 567.747 c
 .777 567.747 370.445 562.418 370.445 555.844 c
 .445 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .922 555.844 m
 .922 555.844 l
 .922 548.614 466.785 542.75 474.016 542.75 c
 .246 542.75 487.109 548.614 487.109 555.844 c
 .109 563.075 481.246 568.938 474.016 568.938 c
 .785 568.938 460.922 563.075 460.922 555.844 c
 .922 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .113 555.844 m
 .113 555.844 l
 .113 549.27 467.441 543.942 474.016 543.942 c
 .59 543.942 485.922 549.27 485.922 555.844 c
 .922 562.418 480.59 567.747 474.016 567.747 c
 .441 567.747 462.113 562.418 462.113 555.844 c
 .113 555.844 l
+		C
 		S 1 0.5 1 r f R
+		N
 .492 555.844 m
 .492 555.844 l
 .492 548.614 545.355 542.75 552.586 542.75 c
 .816 542.75 565.68 548.614 565.68 555.844 c
 .68 563.075 559.816 568.938 552.586 568.938 c
 .355 568.938 539.492 563.075 539.492 555.844 c
 .492 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .683 555.844 m
 .683 555.844 l
 .683 549.27 546.012 543.942 552.586 543.942 c
 .16 543.942 564.492 549.27 564.492 555.844 c
 .492 562.418 559.16 567.747 552.586 567.747 c
 .012 567.747 540.683 562.418 540.683 555.844 c
 .683 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .156 555.844 m
 .156 555.844 l
 .156 548.614 637.019 542.75 644.25 542.75 c
 .48 542.75 657.348 548.614 657.348 555.844 c
 .348 563.075 651.48 568.938 644.25 568.938 c
 .019 568.938 631.156 563.075 631.156 555.844 c
 .156 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .348 555.844 m
 .348 555.844 l
 .348 549.27 637.676 543.942 644.25 543.942 c
 .824 543.942 656.156 549.27 656.156 555.844 c
 .156 562.418 650.824 567.747 644.25 567.747 c
 .676 567.747 632.348 562.418 632.348 555.844 c
 .348 555.844 l
+		C
 		S 1 0.5 1 r f R
+		N
 .82 555.844 m
 .82 555.844 l
 .82 548.614 728.687 542.75 735.918 542.75 c
 .149 542.75 749.012 548.614 749.012 555.844 c
 .012 563.075 743.149 568.938 735.918 568.938 c
 .687 568.938 722.82 563.075 722.82 555.844 c
 .82 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .012 555.844 m
 .012 555.844 l
 .012 549.27 729.344 543.942 735.918 543.942 c
 .492 543.942 747.82 549.27 747.82 555.844 c
 .82 562.418 742.492 567.747 735.918 567.747 c
 .344 567.747 724.012 562.418 724.012 555.844 c
 .012 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .391 555.844 m
 .391 555.844 l
 .391 548.614 807.254 542.75 814.484 542.75 c
 .715 542.75 827.578 548.614 827.578 555.844 c
 .578 563.075 821.715 568.938 814.484 568.938 c
 .254 568.938 801.391 563.075 801.391 555.844 c
 .391 555.844 l
+		C
 		S 0 0 0 r f R
+		N
 .582 555.844 m
 .582 555.844 l
 .582 549.27 807.91 543.942 814.484 543.942 c
 .059 543.942 826.387 549.27 826.387 555.844 c
 .387 562.418 821.059 567.747 814.484 567.747 c
 .91 567.747 802.582 562.418 802.582 555.844 c
 .582 555.844 l
+		C
 		S 1 0 1 r f R
+		N
 .6913 32.047 m
 .6913 32.047 l
 .6913 24.8165 21.5553 18.9493 28.7853 18.9493 c
 .0163 18.9493 41.8833 24.8165 41.8833 32.047 c
 .8833 39.2775 36.0163 45.1407 28.7853 45.1407 c
 .5553 45.1407 15.6913 39.2775 15.6913 32.047 c
 .6913 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .8833 32.047 m
 .8833 32.047 l
 .8833 25.4728 22.2113 20.1407 28.7853 20.1407 c
 .3593 20.1407 40.6913 25.4728 40.6913 32.047 c
 .6913 38.6212 35.3593 43.9493 28.7853 43.9493 c
 .2113 43.9493 16.8833 38.6212 16.8833 32.047 c
 .8833 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .2623 32.047 m
 .2623 32.047 l
 .2623 24.8165 100.125 18.9493 107.355 18.9493 c
 .586 18.9493 120.453 24.8165 120.453 32.047 c
 .453 39.2775 114.586 45.1407 107.355 45.1407 c
 .125 45.1407 94.2623 39.2775 94.2623 32.047 c
 .2623 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .4533 32.047 m
 .4533 32.047 l
 .4533 25.4728 100.781 20.1407 107.355 20.1407 c
 .93 20.1407 119.262 25.4728 119.262 32.047 c
 .262 38.6212 113.93 43.9493 107.355 43.9493 c
 .781 43.9493 95.4533 38.6212 95.4533 32.047 c
 .4533 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .734 32.047 m
 .734 32.047 l
 .734 24.8165 165.601 18.9493 172.832 18.9493 c
 .062 18.9493 185.926 24.8165 185.926 32.047 c
 .926 39.2775 180.062 45.1407 172.832 45.1407 c
 .601 45.1407 159.734 39.2775 159.734 32.047 c
 .734 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .926 32.047 m
 .926 32.047 l
 .926 25.4728 166.258 20.1407 172.832 20.1407 c
 .406 20.1407 184.734 25.4728 184.734 32.047 c
 .734 38.6212 179.406 43.9493 172.832 43.9493 c
 .258 43.9493 160.926 38.6212 160.926 32.047 c
 .926 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .305 32.047 m
 .305 32.047 l
 .305 24.8165 244.172 18.9493 251.402 18.9493 c
 .633 18.9493 264.496 24.8165 264.496 32.047 c
 .496 39.2775 258.633 45.1407 251.402 45.1407 c
 .172 45.1407 238.305 39.2775 238.305 32.047 c
 .305 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .496 32.047 m
 .496 32.047 l
 .496 25.4728 244.828 20.1407 251.402 20.1407 c
 .976 20.1407 263.305 25.4728 263.305 32.047 c
 .305 38.6212 257.976 43.9493 251.402 43.9493 c
 .828 43.9493 239.496 38.6212 239.496 32.047 c
 .496 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .781 32.047 m
 .781 32.047 l
 .781 24.8165 309.644 18.9493 316.875 18.9493 c
 .105 18.9493 329.973 24.8165 329.973 32.047 c
 .973 39.2775 324.105 45.1407 316.875 45.1407 c
 .644 45.1407 303.781 39.2775 303.781 32.047 c
 .781 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .973 32.047 m
 .973 32.047 l
 .973 25.4728 310.301 20.1407 316.875 20.1407 c
 .449 20.1407 328.781 25.4728 328.781 32.047 c
 .781 38.6212 323.449 43.9493 316.875 43.9493 c
 .301 43.9493 304.973 38.6212 304.973 32.047 c
 .973 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .351 32.047 m
 .351 32.047 l
 .351 24.8165 388.215 18.9493 395.445 18.9493 c
 .676 18.9493 408.543 24.8165 408.543 32.047 c
 .543 39.2775 402.676 45.1407 395.445 45.1407 c
 .215 45.1407 382.351 39.2775 382.351 32.047 c
 .351 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .543 32.047 m
 .543 32.047 l
 .543 25.4728 388.871 20.1407 395.445 20.1407 c
 .019 20.1407 407.351 25.4728 407.351 32.047 c
 .351 38.6212 402.019 43.9493 395.445 43.9493 c
 .871 43.9493 383.543 38.6212 383.543 32.047 c
 .543 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .828 32.047 m
 .828 32.047 l
 .828 24.8165 453.691 18.9493 460.922 18.9493 c
 .152 18.9493 474.016 24.8165 474.016 32.047 c
 .016 39.2775 468.152 45.1407 460.922 45.1407 c
 .691 45.1407 447.828 39.2775 447.828 32.047 c
 .828 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .016 32.047 m
 .016 32.047 l
 .016 25.4728 454.348 20.1407 460.922 20.1407 c
 .496 20.1407 472.824 25.4728 472.824 32.047 c
 .824 38.6212 467.496 43.9493 460.922 43.9493 c
 .348 43.9493 449.016 38.6212 449.016 32.047 c
 .016 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .394 32.047 m
 .394 32.047 l
 .394 24.8165 532.262 18.9493 539.492 18.9493 c
 .723 18.9493 552.586 24.8165 552.586 32.047 c
 .586 39.2775 546.723 45.1407 539.492 45.1407 c
 .262 45.1407 526.394 39.2775 526.394 32.047 c
 .394 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .586 32.047 m
 .586 32.047 l
 .586 25.4728 532.918 20.1407 539.492 20.1407 c
 .066 20.1407 551.394 25.4728 551.394 32.047 c
 .394 38.6212 546.066 43.9493 539.492 43.9493 c
 .918 43.9493 527.586 38.6212 527.586 32.047 c
 .586 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .871 32.047 m
 .871 32.047 l
 .871 24.8165 597.734 18.9493 604.965 18.9493 c
 .195 18.9493 618.062 24.8165 618.062 32.047 c
 .062 39.2775 612.195 45.1407 604.965 45.1407 c
 .734 45.1407 591.871 39.2775 591.871 32.047 c
 .871 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .062 32.047 m
 .062 32.047 l
 .062 25.4728 598.39 20.1407 604.965 20.1407 c
 .539 20.1407 616.871 25.4728 616.871 32.047 c
 .871 38.6212 611.539 43.9493 604.965 43.9493 c
 .39 43.9493 593.062 38.6212 593.062 32.047 c
 .062 32.047 l
+		C
 		S 0.5 0.5 1 r f R
+		N
 .441 32.047 m
 .441 32.047 l
 .441 24.8165 676.305 18.9493 683.535 18.9493 c
 .766 18.9493 696.633 24.8165 696.633 32.047 c
 .633 39.2775 690.766 45.1407 683.535 45.1407 c
 .305 45.1407 670.441 39.2775 670.441 32.047 c
 .441 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .633 32.047 m
 .633 32.047 l
 .633 25.4728 676.961 20.1407 683.535 20.1407 c
 .109 20.1407 695.441 25.4728 695.441 32.047 c
 .441 38.6212 690.109 43.9493 683.535 43.9493 c
 .961 43.9493 671.633 38.6212 671.633 32.047 c
 .633 32.047 l
+		C
 		S 0 0 1 r f R
+		N
 .918 32.047 m
 .918 32.047 l
 .918 24.8165 741.781 18.9493 749.012 18.9493 c
 .242 18.9493 762.106 24.8165 762.106 32.047 c
 .106 39.2775 756.242 45.1407 749.012 45.1407 c
 .781 45.1407 735.918 39.2775 735.918 32.047 c
 .918 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .105 32.047 m
 .105 32.047 l
 .105 25.4728 742.437 20.1407 749.012 20.1407 c
 .586 20.1407 760.914 25.4728 760.914 32.047 c
 .914 38.6212 755.586 43.9493 749.012 43.9493 c
 .437 43.9493 737.105 38.6212 737.105 32.047 c
 .105 32.047 l
+		C
 		S 0 0 1 r f R
+		N
 .391 32.047 m
 .391 32.047 l
 .391 24.8165 807.254 18.9493 814.484 18.9493 c
 .715 18.9493 827.578 24.8165 827.578 32.047 c
 .578 39.2775 821.715 45.1407 814.484 45.1407 c
 .254 45.1407 801.391 39.2775 801.391 32.047 c
 .391 32.047 l
+		C
 		S 0 0 0 r f R
+		N
 .582 32.047 m
 .582 32.047 l
 .582 25.4728 807.91 20.1407 814.484 20.1407 c
 .059 20.1407 826.387 25.4728 826.387 32.047 c
 .387 38.6212 821.059 43.9493 814.484 43.9493 c
 .91 43.9493 802.582 38.6212 802.582 32.047 c
 .582 32.047 l
+		C
 		S 0.5 0.5 1 r f R
 		%%EOF

doc/images/bipartite_partitions.eps

Show inline comments

 		%!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
 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
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 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
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 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
 rotate
 -842 translate
 .6378 15 translate
 .389093 dup scale
 rotate
 .47 -613.138 translate
 		%Edges:
 		gsave
 .857 -446.322 296.569 -487.43 79.2808 -528.539 0 0 0 2 lb
 .857 -446.322 575.52 -315.655 637.183 -184.989 0 0 0 2 lb
 .468 566.711 494.771 434.577 596.074 302.442 0 0 0 2 lb
 .468 566.711 155.625 579.925 -82.2171 593.138 0 0 0 2 lb
 .468 566.711 251.056 450.726 108.644 334.741 0 0 0 2 lb
 .153 52.8539 732.613 177.648 596.074 302.442 0 0 0 2 lb
 .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
 .2808 -528.539 -66.0671 -490.366 -211.415 -452.194 0 0 0 2 lb
 .183 -184.989 421.363 -253.993 205.543 -322.996 0 0 0 2 lb
 .543 -322.996 162.966 -226.097 120.389 -129.198 0 0 0 2 lb
 .34 88.0898 259.865 -20.5541 120.389 -129.198 0 0 0 2 lb
 .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
 .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
 .644 334.741 20 0 0 1 nc
 .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
 .34 88.0898 20 1 0 0 nc
 .543 -322.996 20 1 0 0 nc
 .183 -184.989 20 0 0 1 nc
 .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
 .074 302.442 20 0 0 1 nc
 .153 52.8539 20 1 0 0 nc
 .468 566.711 20 1 0 0 nc
 .857 -446.322 20 1 0 0 nc
 		grestore
 		grestore
 		showpage

doc/images/connected_components.eps

Show inline comments

 		%!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
 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
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 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
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 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
 rotate
 -842 translate
 .0944 15 translate
 .434694 dup scale
 rotate
 .856 -588.349 translate
 		%Edges:
 		gsave
 .035 177.301 622.149 225.748 670.264 274.195 0 0 0 2 lb
 .579 115.483 682.421 194.839 670.264 274.195 0 0 0 2 lb
 .402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 0 2 lb
 .402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 0 2 lb
 .403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 0 2 lb
 .584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 0 2 lb
 .584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 0 2 lb
 .037 -88.514 417.946 -142.604 397.855 -196.694 0 0 0 2 lb
 .037 -88.514 402.492 -99.332 366.947 -110.15 0 0 0 2 lb
 .855 -196.694 382.401 -153.422 366.947 -110.15 0 0 0 2 lb
 .947 -110.15 319.038 -142.604 271.13 -175.058 0 0 0 2 lb
 .13 -175.058 274.221 -213.694 277.311 -252.33 0 0 0 2 lb
 .13 -175.058 238.675 -190.512 206.221 -205.967 0 0 0 2 lb
 .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
 .312 201.403 946.592 42.798 986.873 -115.807 0 0 0 2 lb
 .312 201.403 834.562 91.8901 762.812 -17.6227 0 0 0 2 lb
 .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
 .945 521.129 208.955 541.269 -5.03507 561.41 0 0 0 2 lb
 .945 521.129 376.371 417.911 329.797 314.692 0 0 0 2 lb
 .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
 .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
 .812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 0 2 lb
 .812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 0 2 lb
 .164 32.7279 470.779 -128.394 415.393 -289.516 0 0 0 2 lb
 .084 -307.139 572.738 -298.327 415.393 -289.516 0 0 0 2 lb
 .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
 .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
 .264 274.195 629.188 409.347 588.113 544.499 0 0 0 2 lb
 .264 274.195 797.466 341.771 924.667 409.347 0 0 0 2 lb
 .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
 .667 409.347 20 1 0 0 nc
 .113 544.499 20 1 0 0 nc
 .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
 .208 38.3422 20 0 1 0 nc
 .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
 .393 -289.516 20 0 0 1 nc
 .084 -307.139 20 0 0 1 nc
 .164 32.7279 20 0 0 1 nc
 .812 -17.6227 20 0 0 1 nc
 		-67.9734 319.727 20 0 0 1 nc
 .797 314.692 20 0 0 1 nc
 		-5.03507 561.41 20 0 0 1 nc
 .945 521.129 20 0 0 1 nc
 		-470.779 158.605 20 0 0 1 nc
 .873 -115.807 20 0 0 1 nc
 .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
 .221 -205.967 20 1 1 0 nc
 .311 -252.33 20 1 1 0 nc
 .13 -175.058 20 1 1 0 nc
 .947 -110.15 20 1 1 0 nc
 .855 -196.694 20 1 1 0 nc
 .037 -88.514 20 1 1 0 nc
 .584 -48.3327 20 1 1 0 nc
 .403 -23.6057 20 1 1 0 nc
 .402 10.3938 20 1 1 0 nc
 .579 115.483 20 1 0 0 nc
 .035 177.301 20 1 0 0 nc
 		grestore
 		grestore
 		showpage

doc/images/edge_biconnected_components.eps

Show inline comments

 		%!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
 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
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 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
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 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
 rotate
 -842 translate
 .0944 15 translate
 .434694 dup scale
 rotate
 .856 -588.349 translate
 		%Edges:
 		gsave
 .035 177.301 622.149 225.748 670.264 274.195 1 0 0 2 lb
 .579 115.483 682.421 194.839 670.264 274.195 1 0 0 2 lb
 .402 10.3938 246.402 -6.60595 212.403 -23.6057 0 0 1 2 lb
 .402 10.3938 283.493 -18.9695 286.584 -48.3327 0 0 1 2 lb
 .403 -23.6057 249.493 -35.9692 286.584 -48.3327 0 0 1 2 lb
 .584 -48.3327 326.765 -79.2414 366.947 -110.15 0 0 1 2 lb
 .584 -48.3327 278.857 -111.695 271.13 -175.058 0 0 1 2 lb
 .037 -88.514 417.946 -142.604 397.855 -196.694 0 0 1 2 lb
 .037 -88.514 402.492 -99.332 366.947 -110.15 0 0 1 2 lb
 .855 -196.694 382.401 -153.422 366.947 -110.15 0 0 1 2 lb
 .947 -110.15 319.038 -142.604 271.13 -175.058 0 0 1 2 lb
 .13 -175.058 274.221 -213.694 277.311 -252.33 0 0 1 2 lb
 .13 -175.058 238.675 -190.512 206.221 -205.967 0 0 1 2 lb
 .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
 .312 201.403 946.592 42.798 986.873 -115.807 0 0 1 2 lb
 .312 201.403 834.562 91.8901 762.812 -17.6227 0 0 1 2 lb
 .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
 .945 521.129 208.955 541.269 -5.03507 561.41 0 0 1 2 lb
 .945 521.129 376.371 417.911 329.797 314.692 0 0 1 2 lb
 .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
 .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
 .812 -17.6227 644.488 7.5526 526.164 32.7279 0 0 1 2 lb
 .812 -17.6227 746.448 -162.381 730.084 -307.139 0 0 1 2 lb
 .164 32.7279 470.779 -128.394 415.393 -289.516 0 0 1 2 lb
 .084 -307.139 572.738 -298.327 415.393 -289.516 0 0 1 2 lb
 .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
 .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
 .264 274.195 629.188 409.347 588.113 544.499 0 0 1 2 lb
 .264 274.195 797.466 341.771 924.667 409.347 0 0 1 2 lb
 .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
 .667 409.347 20 0 0 1 nc
 .113 544.499 20 0 0 1 nc
 .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
 .208 38.3422 20 1 1 0 nc
 .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
 .393 -289.516 20 0.5 0 0 nc
 .084 -307.139 20 0.5 0 0 nc
 .164 32.7279 20 0.5 0 0 nc
 .812 -17.6227 20 0.5 0 0 nc
 		-67.9734 319.727 20 0.5 0 0 nc
 .797 314.692 20 0.5 0 0 nc
 		-5.03507 561.41 20 0.5 0 0 nc
 .945 521.129 20 0.5 0 0 nc
 		-470.779 158.605 20 0 1 1 nc
 .873 -115.807 20 0.5 0 0 nc
 .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
 .221 -205.967 20 0 0 0.5 nc
 .311 -252.33 20 0 0 0.5 nc
 .13 -175.058 20 0 0 0.5 nc
 .947 -110.15 20 0 0 0.5 nc
 .855 -196.694 20 0 0 0.5 nc
 .037 -88.514 20 0 0 0.5 nc
 .584 -48.3327 20 0 0 0.5 nc
 .403 -23.6057 20 0 0 0.5 nc
 .402 10.3938 20 0 0 0.5 nc
 .579 115.483 20 1 0 0 nc
 .035 177.301 20 0 1 0 nc
 		grestore
 		grestore
 		showpage

doc/images/node_biconnected_components.eps

Show inline comments

 		%!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
 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
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 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
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 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
 rotate
 -842 translate
 .0944 15 translate
 .434694 dup scale
 rotate
 .856 -588.349 translate
 		%Edges:
 		gsave
 .035 177.301 622.149 225.748 670.264 274.195 0 1 0 5 lb
 .579 115.483 682.421 194.839 670.264 274.195 1 0 0 5 lb
 .402 10.3938 246.402 -6.60595 212.403 -23.6057 1 1 0.5 5 lb
 .402 10.3938 283.493 -18.9695 286.584 -48.3327 1 1 0.5 5 lb
 .403 -23.6057 249.493 -35.9692 286.584 -48.3327 1 1 0.5 5 lb
 .584 -48.3327 326.765 -79.2414 366.947 -110.15 1 0.5 1 5 lb
 .584 -48.3327 278.857 -111.695 271.13 -175.058 1 0.5 1 5 lb
 .037 -88.514 417.946 -142.604 397.855 -196.694 0.5 0.5 1 5 lb
 .037 -88.514 402.492 -99.332 366.947 -110.15 0.5 0.5 1 5 lb
 .855 -196.694 382.401 -153.422 366.947 -110.15 0.5 0.5 1 5 lb
 .947 -110.15 319.038 -142.604 271.13 -175.058 1 0.5 1 5 lb
 .13 -175.058 274.221 -213.694 277.311 -252.33 0.5 1 1 5 lb
 .13 -175.058 238.675 -190.512 206.221 -205.967 0.5 1 1 5 lb
 .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
 .312 201.403 946.592 42.798 986.873 -115.807 0 0.5 0.5 5 lb
 .312 201.403 834.562 91.8901 762.812 -17.6227 0 0.5 0.5 5 lb
 .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
 .945 521.129 208.955 541.269 -5.03507 561.41 0.5 0 0.5 5 lb
 .945 521.129 376.371 417.911 329.797 314.692 0.5 0 0.5 5 lb
 .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
 .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
 .812 -17.6227 644.488 7.5526 526.164 32.7279 0.5 0.5 0.5 5 lb
 .812 -17.6227 746.448 -162.381 730.084 -307.139 0.5 0.5 0.5 5 lb
 .164 32.7279 470.779 -128.394 415.393 -289.516 0.5 0.5 0.5 5 lb
 .084 -307.139 572.738 -298.327 415.393 -289.516 0.5 0.5 0.5 5 lb
 .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
 .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
 .264 274.195 629.188 409.347 588.113 544.499 0 0 1 5 lb
 .264 274.195 797.466 341.771 924.667 409.347 0 0 1 5 lb
 .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
 .667 409.347 20 0 0 1 nc
 .113 544.499 20 0 0 1 nc
 .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
 .208 38.3422 20 0 0 1 nc
 .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
 .393 -289.516 20 1 0 0 nc
 .084 -307.139 20 0 0 1 nc
 .164 32.7279 20 1 0 0 nc
 .812 -17.6227 20 1 0 0 nc
 		-67.9734 319.727 20 0 0 1 nc
 .797 314.692 20 0 0 1 nc
 		-5.03507 561.41 20 0 0 1 nc
 .945 521.129 20 0 0 1 nc
 		-470.779 158.605 20 1 0 0 nc
 .873 -115.807 20 0 0 1 nc
 .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
 .221 -205.967 20 0 0 1 nc
 .311 -252.33 20 0 0 1 nc
 .13 -175.058 20 1 0 0 nc
 .947 -110.15 20 1 0 0 nc
 .855 -196.694 20 0 0 1 nc
 .037 -88.514 20 0 0 1 nc
 .584 -48.3327 20 1 0 0 nc
 .403 -23.6057 20 0 0 1 nc
 .402 10.3938 20 0 0 1 nc
 .579 115.483 20 0 0 1 nc
 .035 177.301 20 0 0 1 nc
 		grestore
 		grestore
 		showpage

doc/images/strongly_connected_components.eps

Show inline comments

 		%!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
 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
 index 1 index sub 2 index 2 index add lineto
 index 1 index sub 2 index 2 index sub lineto
 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
 index             2 index 2 index add lineto
 index 1 index sub 2 index             lineto
 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
 rotate
 -842 translate
 .1122 15 translate
 .585745 dup scale
 rotate
 .963 -397.916 translate
 		%Edges:
 		gsave
 setlinewidth 0 0 1 setrgbcolor newpath
 .178 27.2723 moveto
 .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
 setlinewidth 0 0 1 setrgbcolor newpath
 .8044 15.5841 moveto
 .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
 setlinewidth 1 0 0 setrgbcolor newpath
 .178 27.2723 moveto
 .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
 setlinewidth 0 0 1 setrgbcolor newpath
 .79 -130.517 moveto
 .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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 setlinewidth 1 0 0 setrgbcolor newpath
 .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
 setlinewidth 0 0 1 setrgbcolor newpath
 .478 311.683 moveto
 .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
 setlinewidth 0 0 1 setrgbcolor newpath
 .851 111.037 moveto
 .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
 setlinewidth 0 0 1 setrgbcolor newpath
 .84406 175.322 moveto
 .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
 setlinewidth 0 0 1 setrgbcolor newpath
 .851 111.037 moveto
 .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
 setlinewidth 0 0 1 setrgbcolor newpath
 .28 -222.074 moveto
 .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
 setlinewidth 0 0 1 setrgbcolor newpath
 .118 -118.829 moveto
 .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
 setlinewidth 1 0 0 setrgbcolor newpath
 		-105.193 -261.035 moveto
 .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
 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
 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
 .28 -222.074 20 1 1 0 nc
 .118 -118.829 20 1 1 0 nc
 .851 111.037 20 1 1 0 nc
 .84406 175.322 20 1 1 0 nc
 .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
 .8044 15.5841 20 0 0 1 nc
 .79 -130.517 20 0 0 1 nc
 .178 27.2723 20 0 0 1 nc
 		grestore
 		grestore
 		showpage

doc/CMakeLists.txt

Show inline comments

 		SET(PACKAGE_NAME ${PROJECT_NAME})
 		SET(PACKAGE_VERSION ${PROJECT_VERSION})
 		SET(abs_top_srcdir ${PROJECT_SOURCE_DIR})
 		SET(abs_top_builddir ${PROJECT_BINARY_DIR})
 		CONFIGURE_FILE(
 		  ${PROJECT_SOURCE_DIR}/doc/Doxyfile.in
 		  ${PROJECT_BINARY_DIR}/doc/Doxyfile
 		  @ONLY)
 		IF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)
 		  FILE(MAKE_DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/)
 		  IF(UNIX)
 		    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})
 		  ELSEIF(WIN32)
 		    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})
 		  ENDIF(UNIX)
 		  INSTALL(
 		    DIRECTORY ${CMAKE_CURRENT_BINARY_DIR}/html/
 		    DESTINATION share/doc
 		    COMPONENT html_documentation)
 		ENDIF(DOXYGEN_EXECUTABLE AND GHOSTSCRIPT_EXECUTABLE)

doc/Makefile.am

Show inline comments

 		EXTRA_DIST += \
 			doc/Doxyfile.in \
 			doc/DoxygenLayout.xml \
 			doc/coding_style.dox \
 			doc/dirs.dox \
 			doc/groups.dox \
 			doc/lgf.dox \
 			doc/license.dox \
 			doc/mainpage.dox \
 			doc/migration.dox \
 			doc/named-param.dox \
 			doc/namespaces.dox \
 			doc/html \
 			doc/CMakeLists.txt
 		DOC_EPS_IMAGES18 = \
 			grid_graph.eps \
 			nodeshape_0.eps \
 			nodeshape_1.eps \
 			nodeshape_2.eps \
 			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)
 		EXTRA_DIST += $(DOC_EPS_IMAGES:%=doc/images/%)
 		doc/html:
 			$(MAKE) $(AM_MAKEFLAGS) html
 		GS_COMMAND=gs -dNOPAUSE -dBATCH -q -dEPSCrop -dTextAlphaBits=4 -dGraphicsAlphaBits=4
 		$(DOC_EPS_IMAGES18:%.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 -r18 -sOutputFile=$@ $<; \
 			else \
 			  echo; \
 			  echo "Ghostscript not found."; \
 			  echo; \
 			  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; \
 			  doxygen Doxyfile; \
 			  cd ..; \
 			else \
 			  echo; \
 			  echo "Doxygen not found."; \
 			  echo; \
 			  exit 1; \
 			fi
 		clean-local:
 			-rm -rf doc/html
 			-rm -f doc/doxygen.log
 			-rm -f $(DOC_PNG_IMAGES)
 			-rm -rf doc/gen-images
 		update-external-tags:
 			wget -O doc/libstdc++.tag.tmp http://gcc.gnu.org/onlinedocs/libstdc++/latest-doxygen/libstdc++.tag && \
 			mv doc/libstdc++.tag.tmp doc/libstdc++.tag || \
 			rm doc/libstdc++.tag.tmp
 		install-html-local: doc/html
 			@$(NORMAL_INSTALL)
 			$(mkinstalldirs) $(DESTDIR)$(htmldir)/docs
 			for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
 			  f="`echo $$p | sed -e 's|^.*/||'`"; \
 			  echo " $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f"; \
 			  $(INSTALL_DATA) $$p $(DESTDIR)$(htmldir)/docs/$$f; \
 			done
 		uninstall-local:
 			@$(NORMAL_UNINSTALL)
 			for p in doc/html/*.{html,css,png,map,gif,tag} ; do \
 			  f="`echo $$p | sed -e 's|^.*/||'`"; \
 			  echo " rm -f $(DESTDIR)$(htmldir)/docs/$$f"; \
 			  rm -f $(DESTDIR)$(htmldir)/docs/$$f; \
 			done
 		.PHONY: update-external-tags

doc/groups.dox

Show inline comments

@@ -26,662 +26,662 @@
 		/**
 		@defgroup graphs Graph Structures
 		@ingroup datas
 		\brief Graph structures implemented in LEMON.
 		The implementation of combinatorial algorithms heavily relies on
 		efficient graph implementations. LEMON offers data structures which are
 		planned to be easily used in an experimental phase of implementation studies,
 		and thereafter the program code can be made efficient by small modifications.
 		The most efficient implementation of diverse applications require the
 		usage of different physical graph implementations. These differences
 		appear in the size of graph we require to handle, memory or time usage
 		limitations or in the set of operations through which the graph can be
 		accessed.  LEMON provides several physical graph structures to meet
 		the diverging requirements of the possible users.  In order to save on
 		running time or on memory usage, some structures may fail to provide
 		some graph features like arc/edge or node deletion.
 		Alteration of standard containers need a very limited number of
 		operations, these together satisfy the everyday requirements.
 		In the case of graph structures, different operations are needed which do
 		not alter the physical graph, but gives another view. If some nodes or
 		arcs have to be hidden or the reverse oriented graph have to be used, then
 		this is the case. It also may happen that in a flow implementation
 		the residual graph can be accessed by another algorithm, or a node-set
 		is to be shrunk for another algorithm.
 		LEMON also provides a variety of graphs for these requirements called
 		\ref graph_adaptors "graph adaptors". Adaptors cannot be used alone but only
 		in conjunction with other graph representations.
 		You are free to use the graph structure that fit your requirements
 		the best, most graph algorithms and auxiliary data structures can be used
 		with any graph structure.
 		<b>See also:</b> \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		@defgroup graph_adaptors Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Adaptor classes for digraphs and graphs
 		This group contains several useful adaptor classes for digraphs and graphs.
 		The main parts of LEMON are the different graph structures, generic
 		graph algorithms, graph concepts, which couple them, and graph
 		adaptors. While the previous notions are more or less clear, the
 		latter one needs further explanation. Graph adaptors are graph classes
 		which serve for considering graph structures in different ways.
 		A short example makes this much clearer.  Suppose that we have an
 		instance \c g of a directed graph type, say ListDigraph and an algorithm
 		\code
 		template <typename Digraph>
 		int algorithm(const Digraph&);
 		\endcode
 		is needed to run on the reverse oriented graph.  It may be expensive
 		(in time or in memory usage) to copy \c g with the reversed
 		arcs.  In this case, an adaptor class is used, which (according
 		to LEMON \ref concepts::Digraph "digraph concepts") works as a digraph.
 		The adaptor uses the original digraph structure and digraph operations when
 		methods of the reversed oriented graph are called.  This means that the adaptor
 		have minor memory usage, and do not perform sophisticated algorithmic
 		actions.  The purpose of it is to give a tool for the cases when a
 		graph have to be used in a specific alteration.  If this alteration is
 		obtained by a usual construction like filtering the node or the arc set or
 		considering a new orientation, then an adaptor is worthwhile to use.
 		To come back to the reverse oriented graph, in this situation
 		\code
 		template<typename Digraph> class ReverseDigraph;
 		\endcode
 		template class can be used. The code looks as follows
 		\code
 		ListDigraph g;
 		ReverseDigraph<ListDigraph> rg(g);
 		int result = algorithm(rg);
 		\endcode
 		During running the algorithm, the original digraph \c g is untouched.
 		This techniques give rise to an elegant code, and based on stable
 		graph adaptors, complex algorithms can be implemented easily.
 		In flow, circulation and matching problems, the residual
 		graph is of particular importance. Combining an adaptor implementing
 		this with shortest path algorithms or minimum mean cycle algorithms,
 		a range of weighted and cardinality optimization algorithms can be
 		obtained. For other examples, the interested user is referred to the
 		detailed documentation of particular adaptors.
 		The behavior of graph adaptors can be very different. Some of them keep
 		capabilities of the original graph while in other cases this would be
 		meaningless. This means that the concepts that they meet depend
 		on the graph adaptor, and the wrapped graph.
 		For example, if an arc of a reversed digraph is deleted, this is carried
 		out by deleting the corresponding arc of the original digraph, thus the
 		adaptor modifies the original digraph.
 		However in case of a residual digraph, this operation has no sense.
 		Let us stand one more example here to simplify your work.
 		ReverseDigraph has constructor
 		\code
 		ReverseDigraph(Digraph& digraph);
 		\endcode
 		This means that in a situation, when a <tt>const %ListDigraph&</tt>
 		reference to a graph is given, then it have to be instantiated with
 		<tt>Digraph=const %ListDigraph</tt>.
 		\code
 		int algorithm1(const ListDigraph& g) {
 		  ReverseDigraph<const ListDigraph> rg(g);
 		  return algorithm2(rg);
+		}
 		\endcode
 		*/
 		/**
 		@defgroup semi_adaptors Semi-Adaptor Classes for Graphs
 		@ingroup graphs
 		\brief Graph types between real graphs and graph adaptors.
 		This group contains some graph types between real graphs and graph adaptors.
 		These classes wrap graphs to give new functionality as the adaptors do it.
 		On the other hand they are not light-weight structures as the adaptors.
 		*/
 		/**
 		@defgroup maps Maps
 		@ingroup datas
 		\brief Map structures implemented in LEMON.
 		This group contains the map structures implemented in LEMON.
 		LEMON provides several special purpose maps and map adaptors that e.g. combine
 		new maps from existing ones.
 		<b>See also:</b> \ref map_concepts "Map Concepts".
 		*/
 		/**
 		@defgroup graph_maps Graph Maps
 		@ingroup maps
 		\brief Special graph-related maps.
 		This group contains maps that are specifically designed to assign
 		values to the nodes and arcs/edges of graphs.
 		If you are looking for the standard graph maps (\c NodeMap, \c ArcMap,
 		\c EdgeMap), see the \ref graph_concepts "Graph Structure Concepts".
 		*/
 		/**
 		\defgroup map_adaptors Map Adaptors
 		\ingroup maps
 		\brief Tools to create new maps from existing ones
 		This group contains map adaptors that are used to create "implicit"
 		maps from other maps.
 		Most of them are \ref concepts::ReadMap "read-only maps".
 		They can make arithmetic and logical operations between one or two maps
 		(negation, shifting, addition, multiplication, logical 'and', 'or',
 		'not' etc.) or e.g. convert a map to another one of different Value type.
 		The typical usage of this classes is passing implicit maps to
 		algorithms.  If a function type algorithm is called then the function
 		type map adaptors can be used comfortable. For example let's see the
 		usage of map adaptors with the \c graphToEps() function.
 		\code
 		  Color nodeColor(int deg) {
 		    if (deg >= 2) {
 		      return Color(0.5, 0.0, 0.5);
 		    } else if (deg == 1) {
 		      return Color(1.0, 0.5, 1.0);
 		    } else {
 		      return Color(0.0, 0.0, 0.0);
+		    }
+		  }
 		  Digraph::NodeMap<int> degree_map(graph);
 		  graphToEps(graph, "graph.eps")
 		    .coords(coords).scaleToA4().undirected()
 		    .nodeColors(composeMap(functorToMap(nodeColor), degree_map))
 		    .run();
 		\endcode
 		The \c functorToMap() function makes an \c int to \c Color map from the
 		\c nodeColor() function. The \c composeMap() compose the \c degree_map
 		and the previously created map. The composed map is a proper function to
 		get the color of each node.
 		The usage with class type algorithms is little bit harder. In this
 		case the function type map adaptors can not be used, because the
 		function map adaptors give back temporary objects.
 		\code
 		  Digraph graph;
 		  typedef Digraph::ArcMap<double> DoubleArcMap;
 		  DoubleArcMap length(graph);
 		  DoubleArcMap speed(graph);
 		  typedef DivMap<DoubleArcMap, DoubleArcMap> TimeMap;
 		  TimeMap time(length, speed);
 		  Dijkstra<Digraph, TimeMap> dijkstra(graph, time);
 		  dijkstra.run(source, target);
 		\endcode
 		We have a length map and a maximum speed map on the arcs of a digraph.
 		The minimum time to pass the arc can be calculated as the division of
 		the two maps which can be done implicitly with the \c DivMap template
 		class. We use the implicit minimum time map as the length map of the
 		\c Dijkstra algorithm.
 		*/
 		/**
 		@defgroup matrices Matrices
 		@ingroup datas
 		\brief Two dimensional data storages implemented in LEMON.
 		This group contains two dimensional data storages implemented in LEMON.
 		*/
 		/**
 		@defgroup paths Path Structures
 		@ingroup datas
 		\brief %Path structures implemented in LEMON.
 		This group contains the path structures implemented in LEMON.
 		LEMON provides flexible data structures to work with paths.
 		All of them have similar interfaces and they can be copied easily with
 		assignment operators and copy constructors. This makes it easy and
 		efficient to have e.g. the Dijkstra algorithm to store its result in
 		any kind of path structure.
 		\sa lemon::concepts::Path
 		*/
 		/**
 		@defgroup auxdat Auxiliary Data Structures
 		@ingroup datas
 		\brief Auxiliary data structures implemented in LEMON.
 		This group contains some data structures implemented in LEMON in
 		order to make it easier to implement combinatorial algorithms.
 		*/
 		/**
 		@defgroup algs Algorithms
 		\brief This group contains the several algorithms
 		implemented in LEMON.
 		This group contains the several algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup search Graph Search
 		@ingroup algs
 		\brief Common graph search algorithms.
 		This group contains the common graph search algorithms, namely
 		\e breadth-first \e search (BFS) and \e depth-first \e search (DFS).
 		*/
 		/**
 		@defgroup shortest_path Shortest Path Algorithms
 		@ingroup algs
 		\brief Algorithms for finding shortest paths.
 		This group contains the algorithms for finding shortest paths in digraphs.
 		 - \ref Dijkstra algorithm for finding shortest paths from a source node
 		   when all arc lengths are non-negative.
 		 - \ref BellmanFord "Bellman-Ford" algorithm for finding shortest paths
 		   from a source node when arc lenghts can be either positive or negative,
 		   but the digraph should not contain directed cycles with negative total
 		   length.
 		 - \ref FloydWarshall "Floyd-Warshall" and \ref Johnson "Johnson" algorithms
 		   for solving the \e all-pairs \e shortest \e paths \e problem when arc
 		   lenghts can be either positive or negative, but the digraph should
 		   not contain directed cycles with negative total length.
 		 - \ref Suurballe A successive shortest path algorithm for finding
 		   arc-disjoint paths between two nodes having minimum total length.
 		*/
 		/**
 		@defgroup max_flow Maximum Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding maximum flows.
 		This group contains the algorithms for finding maximum flows and
 		feasible circulations.
 		The \e maximum \e flow \e problem is to find a flow of maximum value between
 		a single source and a single target. Formally, there is a \f$G=(V,A)\f$
 		digraph, a \f$cap:A\rightarrow\mathbf{R}^+_0\f$ capacity function and
 		\f$s, t \in V\f$ source and target nodes.
 		A maximum flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of the
 		following optimization problem.
 		\f[ \max\sum_{a\in\delta_{out}(s)}f(a) - \sum_{a\in\delta_{in}(s)}f(a) \f]
 		\f[ \sum_{a\in\delta_{out}(v)} f(a) = \sum_{a\in\delta_{in}(v)} f(a)
 		    \qquad \forall v\in V\setminus\{s,t\} \f]
 		\f[ 0 \leq f(a) \leq cap(a) \qquad \forall a\in A \f]
 		LEMON contains several algorithms for solving maximum flow problems:
 		- \ref EdmondsKarp Edmonds-Karp algorithm.
 		- \ref Preflow Goldberg-Tarjan's preflow push-relabel algorithm.
 		- \ref DinitzSleatorTarjan Dinitz's blocking flow algorithm with dynamic trees.
 		- \ref GoldbergTarjan Preflow push-relabel algorithm with dynamic trees.
 		In most cases the \ref Preflow "Preflow" algorithm provides the
 		fastest method for computing a maximum flow. All implementations
 		provides functions to also query the minimum cut, which is the dual
 		problem of the maximum flow.
 		*/
 		/**
 		@defgroup min_cost_flow Minimum Cost Flow Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cost flows and circulations.
 		This group contains the algorithms for finding minimum cost flows and
 		circulations.
 		The \e minimum \e cost \e flow \e problem is to find a feasible flow of
 		minimum total cost from a set of supply nodes to a set of demand nodes
 		in a network with capacity constraints and arc costs.
 		Formally, let \f$G=(V,A)\f$ be a digraph,
 		\f$lower, upper: A\rightarrow\mathbf{Z}^+_0\f$ denote the lower and
 		upper bounds for the flow values on the arcs,
 		\f$cost: A\rightarrow\mathbf{Z}^+_0\f$ denotes the cost per unit flow
 		on the arcs, and
 		\f$supply: V\rightarrow\mathbf{Z}\f$ denotes the supply/demand values
 		of the nodes.
 		A minimum cost flow is an \f$f:A\rightarrow\mathbf{R}^+_0\f$ solution of
 		the following optimization problem.
 		\f[ \min\sum_{a\in A} f(a) cost(a) \f]
 		\f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a) =
 		    supply(v) \qquad \forall v\in V \f]
 		\f[ lower(a) \leq f(a) \leq upper(a) \qquad \forall a\in A \f]
 		LEMON contains several algorithms for solving minimum cost flow problems:
 		 - \ref CycleCanceling Cycle-canceling algorithms.
 		 - \ref CapacityScaling Successive shortest path algorithm with optional
 		   capacity scaling.
 		 - \ref CostScaling Push-relabel and augment-relabel algorithms based on
 		   cost scaling.
 		 - \ref NetworkSimplex Primal network simplex algorithm with various
 		   pivot strategies.
 		*/
 		/**
 		@defgroup min_cut Minimum Cut Algorithms
 		@ingroup algs
 		\brief Algorithms for finding minimum cut in graphs.
 		This group contains the algorithms for finding minimum cut in graphs.
 		The \e minimum \e cut \e problem is to find a non-empty and non-complete
 		\f$X\f$ subset of the nodes with minimum overall capacity on
 		outgoing arcs. Formally, there is a \f$G=(V,A)\f$ digraph, a
 		\f$cap: A\rightarrow\mathbf{R}^+_0\f$ capacity function. The minimum
 		cut is the \f$X\f$ solution of the next optimization problem:
 		\f[ \min_{X \subset V, X\not\in \{\emptyset, V\}}
 		    \sum_{uv\in A, u\in X, v\not\in X}cap(uv) \f]
 		LEMON contains several algorithms related to minimum cut problems:
 		- \ref HaoOrlin "Hao-Orlin algorithm" for calculating minimum cut
 		  in directed graphs.
 		- \ref NagamochiIbaraki "Nagamochi-Ibaraki algorithm" for
 		  calculating minimum cut in undirected graphs.
 		- \ref GomoryHu "Gomory-Hu tree computation" for calculating
 		  all-pairs minimum cut in undirected graphs.
 		If you want to find minimum cut just between two distinict nodes,
 		see the \ref max_flow "maximum flow problem".
 		*/
 		/**
-		@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
 		This group contains the algorithms for discovering the graph properties
 		like connectivity, bipartiteness, euler property, simplicity etc.
 		\image html edge_biconnected_components.png
 		\image latex edge_biconnected_components.eps "bi-edge-connected components" width=\textwidth
 		*/
 		/**
 		@defgroup planar Planarity Embedding and Drawing
 		@ingroup algs
 		\brief Algorithms for planarity checking, embedding and drawing
 		This group contains the algorithms for planarity checking,
 		embedding and drawing.
 		\image html planar.png
 		\image latex planar.eps "Plane graph" width=\textwidth
 		*/
 		/**
 		@defgroup matching Matching Algorithms
 		@ingroup algs
 		\brief Algorithms for finding matchings in graphs and bipartite graphs.
 		This group contains algorithm objects and functions to calculate
 		matchings in graphs and bipartite graphs. The general matching problem is
 		finding a subset of the arcs which does not shares common endpoints.
 		There are several different algorithms for calculate matchings in
 		graphs.  The matching problems in bipartite graphs are generally
 		easier than in general graphs. The goal of the matching optimization
 		can be finding maximum cardinality, maximum weight or minimum cost
 		matching. The search can be constrained to find perfect or
 		maximum cardinality matching.
 		The matching algorithms implemented in LEMON:
 		- \ref MaxBipartiteMatching Hopcroft-Karp augmenting path algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref PrBipartiteMatching Push-relabel algorithm
 		  for calculating maximum cardinality matching in bipartite graphs.
 		- \ref MaxWeightedBipartiteMatching
 		  Successive shortest path algorithm for calculating maximum weighted
 		  matching and maximum weighted bipartite matching in bipartite graphs.
 		- \ref MinCostMaxBipartiteMatching
 		  Successive shortest path algorithm for calculating minimum cost maximum
 		  matching in bipartite graphs.
 		- \ref MaxMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum cardinality matching in general graphs.
 		- \ref MaxWeightedMatching Edmond's blossom shrinking algorithm for calculating
 		  maximum weighted matching in general graphs.
 		- \ref MaxWeightedPerfectMatching
 		  Edmond's blossom shrinking algorithm for calculating maximum weighted
 		  perfect matching in general graphs.
 		\image html bipartite_matching.png
 		\image latex bipartite_matching.eps "Bipartite Matching" width=\textwidth
 		*/
 		/**
 		@defgroup spantree Minimum Spanning Tree Algorithms
 		@ingroup algs
 		\brief Algorithms for finding a minimum cost spanning tree in a graph.
 		This group contains the algorithms for finding a minimum cost spanning
 		tree in a graph.
 		*/
 		/**
 		@defgroup auxalg Auxiliary Algorithms
 		@ingroup algs
 		\brief Auxiliary algorithms implemented in LEMON.
 		This group contains some algorithms implemented in LEMON
 		in order to make it easier to implement complex algorithms.
 		*/
 		/**
 		@defgroup approx Approximation Algorithms
 		@ingroup algs
 		\brief Approximation algorithms.
 		This group contains the approximation and heuristic algorithms
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup gen_opt_group General Optimization Tools
 		\brief This group contains some general optimization frameworks
 		implemented in LEMON.
 		This group contains some general optimization frameworks
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup lp_group Lp and Mip Solvers
 		@ingroup gen_opt_group
 		\brief Lp and Mip solver interfaces for LEMON.
 		This group contains Lp and Mip solver interfaces for LEMON. The
 		various LP solvers could be used in the same manner with this
 		interface.
 		*/
 		/**
 		@defgroup lp_utils Tools for Lp and Mip Solvers
 		@ingroup lp_group
 		\brief Helper tools to the Lp and Mip solvers.
 		This group adds some helper tools to general optimization framework
 		implemented in LEMON.
 		*/
 		/**
 		@defgroup metah Metaheuristics
 		@ingroup gen_opt_group
 		\brief Metaheuristics for LEMON library.
 		This group contains some metaheuristic optimization tools.
 		*/
 		/**
 		@defgroup utils Tools and Utilities
 		\brief Tools and utilities for programming in LEMON
 		Tools and utilities for programming in LEMON.
 		*/
 		/**
 		@defgroup gutils Basic Graph Utilities
 		@ingroup utils
 		\brief Simple basic graph utilities.
 		This group contains some simple basic graph utilities.
 		*/
 		/**
 		@defgroup misc Miscellaneous Tools
 		@ingroup utils
 		\brief Tools for development, debugging and testing.
 		This group contains several useful tools for development,
 		debugging and testing.
 		*/
 		/**
 		@defgroup timecount Time Measuring and Counting
 		@ingroup misc
 		\brief Simple tools for measuring the performance of algorithms.
 		This group contains simple tools for measuring the performance
 		of algorithms.
 		*/
 		/**
 		@defgroup exceptions Exceptions
 		@ingroup utils
 		\brief Exceptions defined in LEMON.
 		This group contains the exceptions defined in LEMON.
 		*/
 		/**
 		@defgroup io_group Input-Output
 		\brief Graph Input-Output methods
 		This group contains the tools for importing and exporting graphs
 		and graph related data. Now it supports the \ref lgf-format
 		"LEMON Graph Format", the \c DIMACS format and the encapsulated
 		postscript (EPS) format.
 		*/
 		/**
 		@defgroup lemon_io LEMON Graph Format
 		@ingroup io_group
 		\brief Reading and writing LEMON Graph Format.
 		This group contains methods for reading and writing
 		\ref lgf-format "LEMON Graph Format".
 		*/
 		/**
 		@defgroup eps_io Postscript Exporting
 		@ingroup io_group
 		\brief General \c EPS drawer and graph exporter
 		This group contains general \c EPS drawing methods and special
 		graph exporting tools.
 		*/
 		/**
 		@defgroup dimacs_group DIMACS format
 		@ingroup io_group
 		\brief Read and write files in DIMACS format
 		Tools to read a digraph from or write it to a file in DIMACS format data.
 		*/
 		/**
 		@defgroup nauty_group NAUTY Format
 		@ingroup io_group
 		\brief Read \e Nauty format
 		Tool to read graphs from \e Nauty format data.
 		*/
 		/**
 		@defgroup concept Concepts
 		\brief Skeleton classes and concept checking classes
 		This group contains the data/algorithm skeletons and concept checking
 		classes implemented in LEMON.
 		The purpose of the classes in this group is fourfold.
 		- These classes contain the documentations of the %concepts. In order
 		  to avoid document multiplications, an implementation of a concept
 		  simply refers to the corresponding concept class.
 		- These classes declare every functions, <tt>typedef</tt>s etc. an
 		  implementation of the %concepts should provide, however completely
 		  without implementations and real data structures behind the
 		  interface. On the other hand they should provide nothing else. All
 		  the algorithms working on a data structure meeting a certain concept
 		  should compile with these classes. (Though it will not run properly,
 		  of course.) In this way it is easily to check if an algorithm
 		  doesn't use any extra feature of a certain implementation.
 		- The concept descriptor classes also provide a <em>checker class</em>
 		  that makes it possible to check whether a certain implementation of a
 		  concept indeed provides all the required features.
 		- Finally, They can serve as a skeleton of a new implementation of a concept.
 		*/
 		/**
 		@defgroup graph_concepts Graph Structure Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for graph structures
 		This group contains the skeletons and concept checking classes of LEMON's
 		graph structures and helper classes used to implement these.
 		*/
 		/**
 		@defgroup map_concepts Map Concepts
 		@ingroup concept
 		\brief Skeleton and concept checking classes for maps
 		This group contains the skeletons and concept checking classes of maps.
 		*/
 		/**
 		\anchor demoprograms
 		@defgroup demos Demo Programs
 		Some demo programs are listed here. Their full source codes can be found in
 		the \c demo subdirectory of the source tree.
 		In order to compile them, use the <tt>make demo</tt> or the
 		<tt>make check</tt> commands.
 		*/
 		/**
 		@defgroup tools Standalone Utility Applications
 		Some utility applications are listed here.
 		The standard compilation procedure (<tt>./configure;make</tt>) will compile
 		them, as well.
 		*/
+		}

lemon/adaptors.h

Show inline comments

@@ -1812,768 +1812,771 @@
 		  filterEdges(const GR& graph, const EF& edge_filter) {
 		    return FilterEdges<const GR, const EF>(graph, edge_filter);
+		  }
 		  template <typename DGR>
 		  class UndirectorBase {
 		  public:
 		    typedef DGR Digraph;
 		    typedef UndirectorBase Adaptor;
 		    typedef True UndirectedTag;
 		    typedef typename Digraph::Arc Edge;
 		    typedef typename Digraph::Node Node;
 		    class Arc : public Edge {
 		      friend class UndirectorBase;
 		    protected:
 		      bool _forward;
 		      Arc(const Edge& edge, bool forward) :
 		        Edge(edge), _forward(forward) {}
 		    public:
 		      Arc() {}
 		      Arc(Invalid) : Edge(INVALID), _forward(true) {}
 		      bool operator==(const Arc &other) const {
 		        return _forward == other._forward &&
 		          static_cast<const Edge&>(*this) == static_cast<const Edge&>(other);
+		      }
 		      bool operator!=(const Arc &other) const {
 		        return _forward != other._forward ||
 		          static_cast<const Edge&>(*this) != static_cast<const Edge&>(other);
+		      }
 		      bool operator<(const Arc &other) const {
 		        return _forward < other._forward ||
 		          (_forward == other._forward &&
 		           static_cast<const Edge&>(*this) < static_cast<const Edge&>(other));
+		      }
 		    };
 		    void first(Node& n) const {
 		      _digraph->first(n);
+		    }
 		    void next(Node& n) const {
 		      _digraph->next(n);
+		    }
 		    void first(Arc& a) const {
 		      _digraph->first(a);
 		      a._forward = true;
+		    }
 		    void next(Arc& a) const {
 		      if (a._forward) {
 		        a._forward = false;
 		      } else {
 		        _digraph->next(a);
 		        a._forward = true;
+		      }
+		    }
 		    void first(Edge& e) const {
 		      _digraph->first(e);
+		    }
 		    void next(Edge& e) const {
 		      _digraph->next(e);
+		    }
 		    void firstOut(Arc& a, const Node& n) const {
 		      _digraph->firstIn(a, n);
 		      if( static_cast<const Edge&>(a) != INVALID ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstOut(a, n);
 		        a._forward = true;
+		      }
+		    }
 		    void nextOut(Arc &a) const {
 		      if (!a._forward) {
 		        Node n = _digraph->target(a);
 		        _digraph->nextIn(a);
 		        if (static_cast<const Edge&>(a) == INVALID ) {
 		          _digraph->firstOut(a, n);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextOut(a);
+		      }
+		    }
 		    void firstIn(Arc &a, const Node &n) const {
 		      _digraph->firstOut(a, n);
 		      if (static_cast<const Edge&>(a) != INVALID ) {
 		        a._forward = false;
 		      } else {
 		        _digraph->firstIn(a, n);
 		        a._forward = true;
+		      }
+		    }
 		    void nextIn(Arc &a) const {
 		      if (!a._forward) {
 		        Node n = _digraph->source(a);
 		        _digraph->nextOut(a);
 		        if( static_cast<const Edge&>(a) == INVALID ) {
 		          _digraph->firstIn(a, n);
 		          a._forward = true;
+		        }
+		      }
 		      else {
 		        _digraph->nextIn(a);
+		      }
+		    }
 		    void firstInc(Edge &e, bool &d, const Node &n) const {
 		      d = true;
 		      _digraph->firstOut(e, n);
 		      if (e != INVALID) return;
 		      d = false;
 		      _digraph->firstIn(e, n);
+		    }
 		    void nextInc(Edge &e, bool &d) const {
 		      if (d) {
 		        Node s = _digraph->source(e);
 		        _digraph->nextOut(e);
 		        if (e != INVALID) return;
 		        d = false;
 		        _digraph->firstIn(e, s);
 		      } else {
 		        _digraph->nextIn(e);
+		      }
+		    }
 		    Node u(const Edge& e) const {
 		      return _digraph->source(e);
+		    }
 		    Node v(const Edge& e) const {
 		      return _digraph->target(e);
+		    }
 		    Node source(const Arc &a) const {
 		      return a._forward ? _digraph->source(a) : _digraph->target(a);
+		    }
 		    Node target(const Arc &a) const {
 		      return a._forward ? _digraph->target(a) : _digraph->source(a);
+		    }
 		    static Arc direct(const Edge &e, bool d) {
 		      return Arc(e, d);
+		    }
 		    Arc direct(const Edge &e, const Node& n) const {
 		      return Arc(e, _digraph->source(e) == n);
+		    }
 		    static bool direction(const Arc &a) { return a._forward; }
 		    Node nodeFromId(int ix) const { return _digraph->nodeFromId(ix); }
 		    Arc arcFromId(int ix) const {
 		      return direct(_digraph->arcFromId(ix >> 1), bool(ix & 1));
+		    }
 		    Edge edgeFromId(int ix) const { return _digraph->arcFromId(ix); }
 		    int id(const Node &n) const { return _digraph->id(n); }
 		    int id(const Arc &a) const {
 		      return  (_digraph->id(a) << 1) | (a._forward ? 1 : 0);
+		    }
 		    int id(const Edge &e) const { return _digraph->id(e); }
 		    int maxNodeId() const { return _digraph->maxNodeId(); }
 		    int maxArcId() const { return (_digraph->maxArcId() << 1) | 1; }
 		    int maxEdgeId() const { return _digraph->maxArcId(); }
 		    Node addNode() { return _digraph->addNode(); }
 		    Edge addEdge(const Node& u, const Node& v) {
 		      return _digraph->addArc(u, v);
+		    }
 		    void erase(const Node& i) { _digraph->erase(i); }
 		    void erase(const Edge& i) { _digraph->erase(i); }
 		    void clear() { _digraph->clear(); }
 		    typedef NodeNumTagIndicator<Digraph> NodeNumTag;
 		    int nodeNum() const { return _digraph->nodeNum(); }
 		    typedef ArcNumTagIndicator<Digraph> ArcNumTag;
 		    int arcNum() const { return 2 * _digraph->arcNum(); }
 		    typedef ArcNumTag EdgeNumTag;
 		    int edgeNum() const { return _digraph->arcNum(); }
 		    typedef FindArcTagIndicator<Digraph> FindArcTag;
 		    Arc findArc(Node s, Node t, Arc p = INVALID) const {
 		      if (p == INVALID) {
 		        Edge arc = _digraph->findArc(s, t);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = _digraph->findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else if (direction(p)) {
 		        Edge arc = _digraph->findArc(s, t, p);
 		        if (arc != INVALID) return direct(arc, true);
 		        arc = _digraph->findArc(t, s);
 		        if (arc != INVALID) return direct(arc, false);
 		      } else {
 		        Edge arc = _digraph->findArc(t, s, p);
 		        if (arc != INVALID) return direct(arc, false);
+		      }
 		      return INVALID;
+		    }
 		    typedef FindArcTag FindEdgeTag;
 		    Edge findEdge(Node s, Node t, Edge p = INVALID) const {
 		      if (s != t) {
 		        if (p == INVALID) {
 		          Edge arc = _digraph->findArc(s, t);
 		          if (arc != INVALID) return arc;
 		          arc = _digraph->findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else if (_digraph->source(p) == s) {
 		          Edge arc = _digraph->findArc(s, t, p);
 		          if (arc != INVALID) return arc;
 		          arc = _digraph->findArc(t, s);
 		          if (arc != INVALID) return arc;
 		        } else {
 		          Edge arc = _digraph->findArc(t, s, p);
 		          if (arc != INVALID) return arc;
+		        }
 		      } else {
 		        return _digraph->findArc(s, t, p);
+		      }
 		      return INVALID;
+		    }
 		  private:
 		    template <typename V>
 		    class ArcMapBase {
 		    private:
 		      typedef typename DGR::template ArcMap<V> MapImpl;
 		    public:
 		      typedef typename MapTraits<MapImpl>::ReferenceMapTag ReferenceMapTag;
 		      typedef V Value;
 		      typedef Arc Key;
 		      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<MapImpl>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<MapImpl>::ConstReturnValue ConstReference;
 		      typedef typename MapTraits<MapImpl>::ReturnValue Reference;
 		      ArcMapBase(const UndirectorBase<DGR>& adaptor) :
 		        _forward(*adaptor._digraph), _backward(*adaptor._digraph) {}
 		      ArcMapBase(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : _forward(*adaptor._digraph, value),
 		          _backward(*adaptor._digraph, value) {}
 		      void set(const Arc& a, const V& value) {
 		        if (direction(a)) {
 		          _forward.set(a, value);
 		        } else {
 		          _backward.set(a, value);
+		        }
+		      }
 		      ConstReturnValue operator[](const Arc& a) const {
 		        if (direction(a)) {
 		          return _forward[a];
 		        } else {
 		          return _backward[a];
+		        }
+		      }
 		      ReturnValue operator[](const Arc& a) {
 		        if (direction(a)) {
 		          return _forward[a];
 		        } else {
 		          return _backward[a];
+		        }
+		      }
 		    protected:
 		      MapImpl _forward, _backward;
 		    };
 		  public:
 		    template <typename V>
 		    class NodeMap : public DGR::template NodeMap<V> {
 		    public:
 		      typedef V Value;
 		      typedef typename DGR::template NodeMap<Value> Parent;
 		      explicit NodeMap(const UndirectorBase<DGR>& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      NodeMap(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : Parent(*adaptor._digraph, value) { }
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap
 		      : public SubMapExtender<UndirectorBase<DGR>, ArcMapBase<V> >
+		    {
 		    public:
 		      typedef V Value;
 		      typedef SubMapExtender<Adaptor, ArcMapBase<V> > Parent;
 		      explicit ArcMap(const UndirectorBase<DGR>& adaptor)
 		        : Parent(adaptor) {}
 		      ArcMap(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : Parent(adaptor, value) {}
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class EdgeMap : public Digraph::template ArcMap<V> {
 		    public:
 		      typedef V Value;
 		      typedef typename Digraph::template ArcMap<V> Parent;
 		      explicit EdgeMap(const UndirectorBase<DGR>& adaptor)
 		        : Parent(*adaptor._digraph) {}
 		      EdgeMap(const UndirectorBase<DGR>& adaptor, const V& value)
 		        : Parent(*adaptor._digraph, value) {}
 		    private:
 		      EdgeMap& operator=(const EdgeMap& cmap) {
 		        return operator=<EdgeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      EdgeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    typedef typename ItemSetTraits<DGR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _digraph->notifier(Node()); }
 		    typedef typename ItemSetTraits<DGR, Edge>::ItemNotifier EdgeNotifier;
 		    EdgeNotifier& notifier(Edge) const { return _digraph->notifier(Edge()); }
 		    typedef EdgeNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _digraph->notifier(Edge()); }
 		  protected:
 		    UndirectorBase() : _digraph(0) {}
 		    DGR* _digraph;
 		    void initialize(DGR& digraph) {
 		      _digraph = &digraph;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for viewing a digraph as an undirected graph.
 		  ///
 		  /// Undirector adaptor can be used for viewing a digraph as an undirected
 		  /// graph. All arcs of the underlying digraph are showed in the
 		  /// adaptor as an edge (and also as a pair of arcs, of course).
 		  /// This adaptor conforms to the \ref concepts::Graph "Graph" concept.
 		  ///
 		  /// The adapted digraph can also be modified through this adaptor
 		  /// by adding or removing nodes or edges, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam DGR The type of the adapted digraph.
 		  /// It must conform to the \ref concepts::Digraph "Digraph" concept.
 		  /// It can also be specified to be \c const.
 		  ///
 		  /// \note The \c Node type of this adaptor and the adapted digraph are
 		  /// convertible to each other, moreover the \c Edge type of the adaptor
 		  /// and the \c Arc type of the adapted digraph are also convertible to
 		  /// each other.
 		  /// (Thus the \c Arc type of the adaptor is convertible to the \c Arc type
 		  /// of the adapted digraph.)
 		  template<typename DGR>
 		#ifdef DOXYGEN
 		  class Undirector {
 		#else
 		  class Undirector :
 		    public GraphAdaptorExtender<UndirectorBase<DGR> > {
 		#endif
 		  public:
 		    /// The type of the adapted digraph.
 		    typedef DGR Digraph;
 		    typedef GraphAdaptorExtender<UndirectorBase<DGR> > Parent;
 		  protected:
 		    Undirector() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Creates an undirected graph from the given digraph.
 		    Undirector(DGR& digraph) {
 		      initialize(digraph);
+		    }
 		    /// \brief Arc map combined from two original arc maps
 		    ///
 		    /// This map adaptor class adapts two arc maps of the underlying
 		    /// digraph to get an arc map of the undirected graph.
 		    /// Its value type is inherited from the first arc map type (\c FW).
 		    /// \tparam FW The type of the "foward" arc map.
 		    /// \tparam BK The type of the "backward" arc map.
 		    template <typename FW, typename BK>
 		    class CombinedArcMap {
 		    public:
 		      /// The key type of the map
 		      typedef typename Parent::Arc Key;
 		      /// The value type of the map
 		      typedef typename FW::Value Value;
 		      typedef typename MapTraits<FW>::ReferenceMapTag ReferenceMapTag;
 		      typedef typename MapTraits<FW>::ReturnValue ReturnValue;
 		      typedef typename MapTraits<FW>::ConstReturnValue ConstReturnValue;
 		      typedef typename MapTraits<FW>::ReturnValue Reference;
 		      typedef typename MapTraits<FW>::ConstReturnValue ConstReference;
 		      /// Constructor
 		      CombinedArcMap(FW& forward, BK& backward)
 		        : _forward(&forward), _backward(&backward) {}
 		      /// Sets the value associated with the given key.
 		      void set(const Key& e, const Value& a) {
 		        if (Parent::direction(e)) {
 		          _forward->set(e, a);
 		        } else {
 		          _backward->set(e, a);
+		        }
+		      }
 		      /// Returns the value associated with the given key.
 		      ConstReturnValue operator[](const Key& e) const {
 		        if (Parent::direction(e)) {
 		          return (*_forward)[e];
 		        } else {
 		          return (*_backward)[e];
+		        }
+		      }
 		      /// Returns a reference to the value associated with the given key.
 		      ReturnValue operator[](const Key& e) {
 		        if (Parent::direction(e)) {
 		          return (*_forward)[e];
 		        } else {
 		          return (*_backward)[e];
+		        }
+		      }
 		    protected:
 		      FW* _forward;
 		      BK* _backward;
 		    };
 		    /// \brief Returns a combined arc map
 		    ///
 		    /// This function just returns a combined arc map.
 		    template <typename FW, typename BK>
 		    static CombinedArcMap<FW, BK>
 		    combinedArcMap(FW& forward, BK& backward) {
 		      return CombinedArcMap<FW, BK>(forward, backward);
+		    }
 		    template <typename FW, typename BK>
 		    static CombinedArcMap<const FW, BK>
 		    combinedArcMap(const FW& forward, BK& backward) {
 		      return CombinedArcMap<const FW, BK>(forward, backward);
+		    }
 		    template <typename FW, typename BK>
 		    static CombinedArcMap<FW, const BK>
 		    combinedArcMap(FW& forward, const BK& backward) {
 		      return CombinedArcMap<FW, const BK>(forward, backward);
+		    }
 		    template <typename FW, typename BK>
 		    static CombinedArcMap<const FW, const BK>
 		    combinedArcMap(const FW& forward, const BK& backward) {
 		      return CombinedArcMap<const FW, const BK>(forward, backward);
+		    }
 		  };
 		  /// \brief Returns a read-only Undirector adaptor
 		  ///
 		  /// This function just returns a read-only \ref Undirector adaptor.
 		  /// \ingroup graph_adaptors
 		  /// \relates Undirector
 		  template<typename DGR>
 		  Undirector<const DGR> undirector(const DGR& digraph) {
 		    return Undirector<const DGR>(digraph);
+		  }
 		  template <typename GR, typename DM>
 		  class OrienterBase {
 		  public:
 		    typedef GR Graph;
 		    typedef DM DirectionMap;
 		    typedef typename GR::Node Node;
 		    typedef typename GR::Edge Arc;
 		    void reverseArc(const Arc& arc) {
 		      _direction->set(arc, !(*_direction)[arc]);
+		    }
 		    void first(Node& i) const { _graph->first(i); }
 		    void first(Arc& i) const { _graph->first(i); }
 		    void firstIn(Arc& i, const Node& n) const {
 		      bool d = true;
 		      _graph->firstInc(i, d, n);
 		      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    void firstOut(Arc& i, const Node& n ) const {
 		      bool d = true;
 		      _graph->firstInc(i, d, n);
 		      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    void next(Node& i) const { _graph->next(i); }
 		    void next(Arc& i) const { _graph->next(i); }
 		    void nextIn(Arc& i) const {
 		      bool d = !(*_direction)[i];
 		      _graph->nextInc(i, d);
 		      while (i != INVALID && d == (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    void nextOut(Arc& i) const {
 		      bool d = (*_direction)[i];
 		      _graph->nextInc(i, d);
 		      while (i != INVALID && d != (*_direction)[i]) _graph->nextInc(i, d);
+		    }
 		    Node source(const Arc& e) const {
 		      return (*_direction)[e] ? _graph->u(e) : _graph->v(e);
+		    }
 		    Node target(const Arc& e) const {
 		      return (*_direction)[e] ? _graph->v(e) : _graph->u(e);
+		    }
 		    typedef NodeNumTagIndicator<Graph> NodeNumTag;
 		    int nodeNum() const { return _graph->nodeNum(); }
 		    typedef EdgeNumTagIndicator<Graph> ArcNumTag;
 		    int arcNum() const { return _graph->edgeNum(); }
 		    typedef FindEdgeTagIndicator<Graph> FindArcTag;
 		    Arc findArc(const Node& u, const Node& v,
 		                const Arc& prev = INVALID) const {
 		      Arc arc = _graph->findEdge(u, v, prev);
 		      while (arc != INVALID && source(arc) != u) {
 		        arc = _graph->findEdge(u, v, arc);
+		      }
 		      return arc;
+		    }
 		    Node addNode() {
 		      return Node(_graph->addNode());
+		    }
 		    Arc addArc(const Node& u, const Node& v) {
 		      Arc arc = _graph->addEdge(u, v);
 		      _direction->set(arc, _graph->u(arc) == u);
 		      return arc;
+		    }
 		    void erase(const Node& i) { _graph->erase(i); }
 		    void erase(const Arc& i) { _graph->erase(i); }
 		    void clear() { _graph->clear(); }
 		    int id(const Node& v) const { return _graph->id(v); }
 		    int id(const Arc& e) const { return _graph->id(e); }
 		    Node nodeFromId(int idx) const { return _graph->nodeFromId(idx); }
 		    Arc arcFromId(int idx) const { return _graph->edgeFromId(idx); }
 		    int maxNodeId() const { return _graph->maxNodeId(); }
 		    int maxArcId() const { return _graph->maxEdgeId(); }
 		    typedef typename ItemSetTraits<GR, Node>::ItemNotifier NodeNotifier;
 		    NodeNotifier& notifier(Node) const { return _graph->notifier(Node()); }
 		    typedef typename ItemSetTraits<GR, Arc>::ItemNotifier ArcNotifier;
 		    ArcNotifier& notifier(Arc) const { return _graph->notifier(Arc()); }
 		    template <typename V>
 		    class NodeMap : public GR::template NodeMap<V> {
 		    public:
 		      typedef typename GR::template NodeMap<V> Parent;
 		      explicit NodeMap(const OrienterBase<GR, DM>& adapter)
 		        : Parent(*adapter._graph) {}
 		      NodeMap(const OrienterBase<GR, DM>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) {}
 		    private:
 		      NodeMap& operator=(const NodeMap& cmap) {
 		        return operator=<NodeMap>(cmap);
+		      }
 		      template <typename CMap>
 		      NodeMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		    template <typename V>
 		    class ArcMap : public GR::template EdgeMap<V> {
 		    public:
 		      typedef typename Graph::template EdgeMap<V> Parent;
 		      explicit ArcMap(const OrienterBase<GR, DM>& adapter)
 		        : Parent(*adapter._graph) { }
 		      ArcMap(const OrienterBase<GR, DM>& adapter, const V& value)
 		        : Parent(*adapter._graph, value) { }
 		    private:
 		      ArcMap& operator=(const ArcMap& cmap) {
 		        return operator=<ArcMap>(cmap);
+		      }
 		      template <typename CMap>
 		      ArcMap& operator=(const CMap& cmap) {
 		        Parent::operator=(cmap);
 		        return *this;
+		      }
 		    };
 		  protected:
 		    Graph* _graph;
 		    DM* _direction;
 		    void initialize(GR& graph, DM& direction) {
 		      _graph = &graph;
 		      _direction = &direction;
+		    }
 		  };
 		  /// \ingroup graph_adaptors
 		  ///
 		  /// \brief Adaptor class for orienting the edges of a graph to get a digraph
 		  ///
 		  /// Orienter adaptor can be used for orienting the edges of a graph to
 		  /// get a digraph. A \c bool edge map of the underlying graph must be
 		  /// specified, which define the direction of the arcs in the adaptor.
 		  /// The arcs can be easily reversed by the \c reverseArc() member function
 		  /// of the adaptor.
 		  /// This class conforms to the \ref concepts::Digraph "Digraph" concept.
 		  ///
 		  /// The adapted graph can also be modified through this adaptor
 		  /// by adding or removing nodes or arcs, unless the \c GR template
 		  /// parameter is set to be \c const.
 		  ///
 		  /// \tparam GR The type of the adapted graph.
 		  /// It must conform to the \ref concepts::Graph "Graph" concept.
 		  /// It can also be specified to be \c const.
 		  /// \tparam DM The type of the direction map.
 		  /// It must be a \c bool (or convertible) edge map of the
 		  /// adapted graph. The default type is
 		  /// \ref concepts::Graph::EdgeMap "GR::EdgeMap<bool>".
 		  ///
 		  /// \note The \c Node type of this adaptor and the adapted graph are
 		  /// convertible to each other, moreover the \c Arc type of the adaptor
 		  /// and the \c Edge type of the adapted graph are also convertible to
 		  /// each other.
 		#ifdef DOXYGEN
 		  template<typename GR,
 		           typename DM>
 		  class Orienter {
 		#else
 		  template<typename GR,
 		           typename DM = typename GR::template EdgeMap<bool> >
 		  class Orienter :
 		    public DigraphAdaptorExtender<OrienterBase<GR, DM> > {
 		#endif
 		  public:
 		    /// The type of the adapted graph.
 		    typedef GR Graph;
 		    /// The type of the direction edge map.
 		    typedef DM DirectionMap;
 		    typedef DigraphAdaptorExtender<OrienterBase<GR, DM> > Parent;
 		    typedef typename Parent::Arc Arc;
 		  protected:
 		    Orienter() { }
 		  public:
 		    /// \brief Constructor
 		    ///
 		    /// Constructor of the adaptor.
 		    Orienter(GR& graph, DM& direction) {
 		      Parent::initialize(graph, direction);
+		    }
 		    /// \brief Reverses the given arc
 		    ///
 		    /// This function reverses the given arc.
 		    /// It is done by simply negate the assigned value of \c a
 		    /// in the direction map.
 		    void reverseArc(const Arc& a) {
 		      Parent::reverseArc(a);
+		    }
 		  };
 		  /// \brief Returns a read-only Orienter adaptor
 		  ///
 		  /// This function just returns a read-only \ref Orienter adaptor.
 		  /// \ingroup graph_adaptors

lemon/bin_heap.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BIN_HEAP_H
 		#define LEMON_BIN_HEAP_H
 		///\ingroup auxdat
 		///\file
 		///\brief Binary Heap implementation.
 		#include <vector>
 		#include <utility>
 		#include <functional>
 		namespace lemon {
 		  ///\ingroup auxdat
 		  ///
 		  ///\brief A Binary Heap implementation.
 		  ///
 		  ///This class implements the \e binary \e heap data structure.
 		  ///
 		  ///A \e heap is a data structure for storing items with specified values
 		  ///called \e priorities in such a way that finding the item with minimum
 		  ///priority is efficient. \c Comp specifies the ordering of the priorities.
 		  ///In a heap one can change the priority of an item, add or erase an
 		  ///item, etc.
 		  ///
 		  ///\tparam PR Type of the priority of the items.
 		  ///\tparam IM A read and writable item map with int values, used internally
 		  ///to handle the cross references.
 		  ///\tparam Comp A functor class for the ordering of the priorities.
 		  ///The default is \c std::less<PR>.
 		  ///
 		  ///\sa FibHeap
 		  ///\sa Dijkstra
 		  template <typename PR, typename IM, typename Comp = std::less<PR> >
 		  class BinHeap {
 		  public:
 		    ///\e
 		    typedef IM ItemIntMap;
 		    ///\e
 		    typedef PR Prio;
 		    ///\e
 		    typedef typename ItemIntMap::Key Item;
 		    ///\e
 		    typedef std::pair<Item,Prio> Pair;
 		    ///\e
 		    typedef Comp Compare;
 		    /// \brief Type to represent the items states.
 		    ///
 		    /// Each Item element have a state associated to it. It may be "in heap",
 		    /// "pre heap" or "post heap". The latter two are indifferent from the
 		    /// heap's point of view, but may be useful to the user.
 		    ///
 		    /// The item-int map must be initialized in such way that it assigns
 		    /// \c PRE_HEAP (<tt>-1</tt>) 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:
 		    std::vector<Pair> _data;
 		    Compare _comp;
 		    ItemIntMap &_iim;
 		  public:
 		    /// \brief The constructor.
 		    ///
 		    /// The constructor.
 		    /// \param map should be given to the constructor, since it is used
 		    /// internally to handle the cross references. The value of the map
 		    /// must be \c PRE_HEAP (<tt>-1</tt>) for every item.
 		    explicit BinHeap(ItemIntMap &map) : _iim(map) {}
 		    /// \brief The constructor.
 		    ///
 		    /// The constructor.
 		    /// \param map should be given to the constructor, since it is used
 		    /// internally to handle the cross references. The value of the map
 		    /// should be PRE_HEAP (-1) for each element.
 		    ///
 		    /// \param comp The comparator function object.
 		    BinHeap(ItemIntMap &map, const Compare &comp)
 		      : _iim(map), _comp(comp) {}
 		    /// The number of items stored in the heap.
 		    ///
 		    /// \brief Returns the number of items stored in the heap.
 		    int size() const { return _data.size(); }
 		    /// \brief Checks if the heap stores no items.
 		    ///
 		    /// Returns \c true if and only if the heap stores no items.
 		    bool empty() const { return _data.empty(); }
 		    /// \brief Make empty this heap.
 		    ///
 		    /// Make empty this heap. It does not change the cross reference map.
 		    /// If you want to reuse what is not surely empty you should first clear
 		    /// the heap and after that you should set the cross reference map for
 		    /// each item to \c PRE_HEAP.
 		    void clear() {
 		      _data.clear();
+		    }
 		  private:
 		    static int parent(int i) { return (i-1)/2; }
 		    static int second_child(int i) { return 2*i+2; }
 		    bool less(const Pair &p1, const Pair &p2) const {
 		      return _comp(p1.second, p2.second);
+		    }
 		    int bubble_up(int hole, Pair p) {
 		      int par = parent(hole);
 		      while( hole>0 && less(p,_data[par]) ) {
 		        move(_data[par],hole);
 		        hole = par;
 		        par = parent(hole);
+		      }
 		      move(p, hole);
 		      return hole;
+		    }
 		    int bubble_down(int hole, Pair p, int length) {
 		      int child = second_child(hole);
 		      while(child < length) {
 		        if( less(_data[child-1], _data[child]) ) {
 		          --child;
+		        }
 		        if( !less(_data[child], p) )
 		          goto ok;
 		        move(_data[child], hole);
 		        hole = child;
 		        child = second_child(hole);
+		      }
 		      child--;
 		      if( child<length && less(_data[child], p) ) {
 		        move(_data[child], hole);
 		        hole=child;
+		      }
 		    ok:
 		      move(p, hole);
 		      return hole;
+		    }
 		    void move(const Pair &p, int i) {
 		      _data[i] = p;
 		      _iim.set(p.first, i);
+		    }
 		  public:
 		    /// \brief Insert a pair of item and priority into the heap.
 		    ///
 		    /// Adds \c p.first to the heap with priority \c p.second.
 		    /// \param p The pair to insert.
 		    void push(const Pair &p) {
 		      int n = _data.size();
 		      _data.resize(n+1);
 		      bubble_up(n, p);
+		    }
 		    /// \brief Insert an item into the heap with the given heap.
 		    ///
 		    /// Adds \c i to the heap with priority \c p.
 		    /// \param i The item to insert.
 		    /// \param p The priority of the item.
 		    void push(const Item &i, const Prio &p) { push(Pair(i,p)); }
 		    /// \brief Returns the item with minimum priority relative to \c Compare.
 		    ///
 		    /// This method returns the item with minimum priority relative to \c
 		    /// Compare.
 		    /// \pre The heap must be nonempty.
 		    Item top() const {
 		      return _data[0].first;
+		    }
 		    /// \brief Returns the minimum priority relative to \c Compare.
 		    ///
 		    /// It returns the minimum priority relative to \c Compare.
 		    /// \pre The heap must be nonempty.
 		    Prio prio() const {
 		      return _data[0].second;
+		    }
 		    /// \brief Deletes the item with minimum priority relative to \c Compare.
 		    ///
 		    /// This method deletes the item with minimum priority relative to \c
 		    /// Compare from the heap.
 		    /// \pre The heap must be non-empty.
 		    void pop() {
 		      int n = _data.size()-1;
 		      _iim.set(_data[0].first, POST_HEAP);
 		      if (n > 0) {
 		        bubble_down(0, _data[n], n);
+		      }
 		      _data.pop_back();
+		    }
 		    /// \brief Deletes \c i from the heap.
 		    ///
 		    /// This method deletes item \c i from the heap.
 		    /// \param i The item to erase.
 		    /// \pre The item should be in the heap.
 		    void erase(const Item &i) {
 		      int h = _iim[i];
 		      int n = _data.size()-1;
 		      _iim.set(_data[h].first, POST_HEAP);
 		      if( h < n ) {
 		        if ( bubble_up(h, _data[n]) == h) {
 		          bubble_down(h, _data[n], n);
+		        }
+		      }
 		      _data.pop_back();
+		    }
 		    /// \brief Returns the priority of \c i.
 		    ///
 		    /// This function returns the priority of item \c i.
 		    /// \param i The item.
 		    /// \pre \c i must be in the heap.
 		    Prio operator[](const Item &i) const {
 		      int idx = _iim[i];
 		      return _data[idx].second;
+		    }
 		    /// \brief \c i gets to the heap with priority \c p independently
 		    /// if \c i was already there.
 		    ///
 		    /// This method calls \ref push(\c i, \c p) if \c i is not stored
 		    /// in the heap and sets the priority of \c i to \c p otherwise.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    void set(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      if( idx < 0 ) {
 		        push(i,p);
+		      }
 		      else if( _comp(p, _data[idx].second) ) {
 		        bubble_up(idx, Pair(i,p));
+		      }
 		      else {
 		        bubble_down(idx, Pair(i,p), _data.size());
+		      }
+		    }
 		    /// \brief Decreases the priority of \c i to \c p.
 		    ///
 		    /// This method decreases the priority of item \c i to \c p.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \c i must be stored in the heap with priority at least \c
 		    /// p relative to \c Compare.
 		    void decrease(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      bubble_up(idx, Pair(i,p));
+		    }
 		    /// \brief Increases the priority of \c i to \c p.
 		    ///
 		    /// This method sets the priority of item \c i to \c p.
 		    /// \param i The item.
 		    /// \param p The priority.
 		    /// \pre \c i must be stored in the heap with priority at most \c
 		    /// p relative to \c Compare.
 		    void increase(const Item &i, const Prio &p) {
 		      int idx = _iim[i];
 		      bubble_down(idx, Pair(i,p), _data.size());
+		    }
 		    /// \brief Returns if \c item is in, has already been in, or has
 		    /// never been in the heap.
 		    ///
 		    /// This method returns PRE_HEAP if \c item has never been in the
 		    /// heap, IN_HEAP if it is in the heap at the moment, and POST_HEAP
 		    /// otherwise. In the latter case it is possible that \c item will
 		    /// get back to the heap again.
 		    /// \param i The item.
 		    State state(const Item &i) const {
 		      int s = _iim[i];
 		      if( s>=0 )
 		        s=0;
 		      return State(s);
+		    }
 		    /// \brief Sets the state of the \c item in the heap.
 		    ///
 		    /// Sets the state of the \c item in the heap. It can be used to
 		    /// manually clear the heap when it is important to achive the
 		    /// better time complexity.
 		    /// \param i The item.
 		    /// \param st The state. It should not be \c IN_HEAP.
 		    void state(const Item& i, State st) {
 		      switch (st) {
 		      case POST_HEAP:
 		      case PRE_HEAP:
 		        if (state(i) == IN_HEAP) {
 		          erase(i);
+		        }
 		        _iim[i] = st;
 		        break;
 		      case IN_HEAP:
 		        break;
+		      }
+		    }
 		    /// \brief Replaces an item in the heap.
 		    ///
 		    /// The \c i item is replaced with \c j item. The \c i item should
 		    /// be in the heap, while the \c j should be out of the heap. The
 		    /// \c i item will out of the heap and \c j will be in the heap
 		    /// with the same prioriority as prevoiusly the \c i item.
 		    void replace(const Item& i, const Item& j) {
 		      int idx = _iim[i];
 		      _iim.set(i, _iim[j]);
 		      _iim.set(j, idx);
 		      _data[idx].first = j;
+		    }
 		  }; // class BinHeap
 		} // namespace lemon
 		#endif // LEMON_BIN_HEAP_H

lemon/bits/graph_adaptor_extender.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
 		#define LEMON_BITS_GRAPH_ADAPTOR_EXTENDER_H
 		#include <lemon/core.h>
 		#include <lemon/error.h>
 		#include <lemon/bits/default_map.h>
 		namespace lemon {
 		  template <typename _Digraph>
 		  class DigraphAdaptorExtender : public _Digraph {
 		  public:
 		    typedef _Digraph Parent;
 		    typedef _Digraph Digraph;
 		    typedef DigraphAdaptorExtender Adaptor;
 		    // Base extensions
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Arc &e) const {
 		      if (n == Parent::source(e))
 		        return Parent::target(e);
 		      else if(n==Parent::target(e))
 		        return Parent::source(e);
 		      else
 		        return INVALID;
+		    }
 		    class NodeIt : public Node {
 		      const Adaptor* _adaptor;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Adaptor& adaptor, const Node& node)
 		        : Node(node), _adaptor(&adaptor) {}
 		      NodeIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Adaptor& adaptor, const Arc& e) :
 		        Arc(e), _adaptor(&adaptor) { }
 		      ArcIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstOut(*this, node);
+		      }
 		      OutArcIt(const Adaptor& adaptor, const Arc& arc)
 		        : Arc(arc), _adaptor(&adaptor) {}
 		      OutArcIt& operator++() {
 		        _adaptor->nextOut(*this);
 		        return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstIn(*this, node);
+		      }
 		      InArcIt(const Adaptor& adaptor, const Arc& arc) :
 		        Arc(arc), _adaptor(&adaptor) {}
 		      InArcIt& operator++() {
 		        _adaptor->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    Node baseNode(const OutArcIt &e) const {
 		      return Parent::source(e);
+		    }
 		    Node runningNode(const OutArcIt &e) const {
 		      return Parent::target(e);
+		    }
 		    Node baseNode(const InArcIt &e) const {
 		      return Parent::target(e);
+		    }
 		    Node runningNode(const InArcIt &e) const {
 		      return Parent::source(e);
+		    }
 		  };
 		  template <typename _Graph>
 		  class GraphAdaptorExtender : public _Graph {
 		  public:
 		    typedef _Graph Parent;
 		    typedef _Graph Graph;
 		    typedef GraphAdaptorExtender Adaptor;
 		    typedef typename Parent::Node Node;
 		    typedef typename Parent::Arc Arc;
 		    typedef typename Parent::Edge Edge;
 		    // Graph extension
 		    int maxId(Node) const {
 		      return Parent::maxNodeId();
+		    }
 		    int maxId(Arc) const {
 		      return Parent::maxArcId();
+		    }
 		    int maxId(Edge) const {
 		      return Parent::maxEdgeId();
+		    }
 		    Node fromId(int id, Node) const {
 		      return Parent::nodeFromId(id);
+		    }
 		    Arc fromId(int id, Arc) const {
 		      return Parent::arcFromId(id);
+		    }
 		    Edge fromId(int id, Edge) const {
 		      return Parent::edgeFromId(id);
+		    }
 		    Node oppositeNode(const Node &n, const Edge &e) const {
 		      if( n == Parent::u(e))
 		        return Parent::v(e);
 		      else if( n == Parent::v(e))
 		        return Parent::u(e);
 		      else
 		        return INVALID;
+		    }
 		    Arc oppositeArc(const Arc &a) const {
 		      return Parent::direct(a, !Parent::direction(a));
+		    }
 		    using Parent::direct;
 		    Arc direct(const Edge &e, const Node &s) const {
 		      return Parent::direct(e, Parent::u(e) == s);
+		    }
 		    class NodeIt : public Node {
 		      const Adaptor* _adaptor;
 		    public:
 		      NodeIt() {}
 		      NodeIt(Invalid i) : Node(i) { }
 		      explicit NodeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Node&>(*this));
+		      }
 		      NodeIt(const Adaptor& adaptor, const Node& node)
 		        : Node(node), _adaptor(&adaptor) {}
 		      NodeIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class ArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      ArcIt() { }
 		      ArcIt(Invalid i) : Arc(i) { }
 		      explicit ArcIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Arc&>(*this));
+		      }
 		      ArcIt(const Adaptor& adaptor, const Arc& e) :
 		        Arc(e), _adaptor(&adaptor) { }
 		      ArcIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class OutArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      OutArcIt() { }
 		      OutArcIt(Invalid i) : Arc(i) { }
 		      OutArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstOut(*this, node);
+		      }
 		      OutArcIt(const Adaptor& adaptor, const Arc& arc)
 		        : Arc(arc), _adaptor(&adaptor) {}
 		      OutArcIt& operator++() {
 		        _adaptor->nextOut(*this);
 		        return *this;
+		      }
 		    };
 		    class InArcIt : public Arc {
 		      const Adaptor* _adaptor;
 		    public:
 		      InArcIt() { }
 		      InArcIt(Invalid i) : Arc(i) { }
 		      InArcIt(const Adaptor& adaptor, const Node& node)
 		        : _adaptor(&adaptor) {
 		        _adaptor->firstIn(*this, node);
+		      }
 		      InArcIt(const Adaptor& adaptor, const Arc& arc) :
 		        Arc(arc), _adaptor(&adaptor) {}
 		      InArcIt& operator++() {
 		        _adaptor->nextIn(*this);
 		        return *this;
+		      }
 		    };
 		    class EdgeIt : public Parent::Edge {
 		      const Adaptor* _adaptor;
 		    public:
 		      EdgeIt() { }
 		      EdgeIt(Invalid i) : Edge(i) { }
 		      explicit EdgeIt(const Adaptor& adaptor) : _adaptor(&adaptor) {
 		        _adaptor->first(static_cast<Edge&>(*this));
+		      }
 		      EdgeIt(const Adaptor& adaptor, const Edge& e) :
 		        Edge(e), _adaptor(&adaptor) { }
 		      EdgeIt& operator++() {
 		        _adaptor->next(*this);
 		        return *this;
+		      }
 		    };
 		    class IncEdgeIt : public Edge {
 		      friend class GraphAdaptorExtender;
 		      const Adaptor* _adaptor;
 		      bool direction;
 		    public:
 		      IncEdgeIt() { }
 		      IncEdgeIt(Invalid i) : Edge(i), direction(false) { }
 		      IncEdgeIt(const Adaptor& adaptor, const Node &n) : _adaptor(&adaptor) {
 		        _adaptor->firstInc(static_cast<Edge&>(*this), direction, n);
+		      }
 		      IncEdgeIt(const Adaptor& adaptor, const Edge &e, const Node &n)
 		        : _adaptor(&adaptor), Edge(e) {
 		        direction = (_adaptor->u(e) == n);
+		      }
 		      IncEdgeIt& operator++() {
 		        _adaptor->nextInc(*this, direction);
 		        return *this;
+		      }
 		    };
 		    Node baseNode(const OutArcIt &a) const {
 		      return Parent::source(a);
+		    }
 		    Node runningNode(const OutArcIt &a) const {
 		      return Parent::target(a);
+		    }
 		    Node baseNode(const InArcIt &a) const {
 		      return Parent::target(a);
+		    }
 		    Node runningNode(const InArcIt &a) const {
 		      return Parent::source(a);
+		    }
 		    Node baseNode(const IncEdgeIt &e) const {
 		      return e.direction ? Parent::u(e) : Parent::v(e);
+		    }
 		    Node runningNode(const IncEdgeIt &e) const {
 		      return e.direction ? Parent::v(e) : Parent::u(e);
+		    }
 		  };
+		}
 		#endif

lemon/bits/map_extender.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_BITS_MAP_EXTENDER_H
 		#define LEMON_BITS_MAP_EXTENDER_H
 		#include <iterator>
 		#include <lemon/bits/traits.h>
 		#include <lemon/concept_check.h>
 		#include <lemon/concepts/maps.h>
 		//\file
 		//\brief Extenders for iterable maps.
 		namespace lemon {
 		  // \ingroup graphbits
 		  //
 		  // \brief Extender for maps
 		  template <typename _Map>
 		  class MapExtender : public _Map {
 		  public:
 		    typedef _Map Parent;
 		    typedef MapExtender Map;
 		    typedef typename Parent::Graph Graph;
 		    typedef typename Parent::Key Item;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    typedef typename Parent::Reference Reference;
 		    typedef typename Parent::ConstReference ConstReference;
 		    class MapIt;
 		    class ConstMapIt;
 		    friend class MapIt;
 		    friend class ConstMapIt;
 		  public:
 		    MapExtender(const Graph& graph)
 		      : Parent(graph) {}
 		    MapExtender(const Graph& graph, const Value& value)
 		      : Parent(graph, value) {}
 		  private:
 		    MapExtender& operator=(const MapExtender& cmap) {
 		      return operator=<MapExtender>(cmap);
+		    }
 		    template <typename CMap>
 		    MapExtender& operator=(const CMap& cmap) {
 		      Parent::operator=(cmap);
 		      return *this;
+		    }
 		  public:
 		    class MapIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      typedef typename Map::Value Value;
 		      MapIt() {}
 		      MapIt(Invalid i) : Parent(i) { }
 		      explicit MapIt(Map& _map) : map(_map) {
 		        map.notifier()->first(*this);
+		      }
 		      MapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      MapIt& operator++() {
 		        map.notifier()->next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		      typename MapTraits<Map>::ReturnValue operator*() {
 		        return map[*this];
+		      }
 		      void set(const Value& value) {
 		        map.set(*this, value);
+		      }
 		    protected:
 		      Map& map;
 		    };
 		    class ConstMapIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      typedef typename Map::Value Value;
 		      ConstMapIt() {}
 		      ConstMapIt(Invalid i) : Parent(i) { }
 		      explicit ConstMapIt(Map& _map) : map(_map) {
 		        map.notifier()->first(*this);
+		      }
 		      ConstMapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ConstMapIt& operator++() {
 		        map.notifier()->next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		    protected:
 		      const Map& map;
 		    };
 		    class ItemIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      ItemIt() {}
 		      ItemIt(Invalid i) : Parent(i) { }
 		      explicit ItemIt(Map& _map) : map(_map) {
 		        map.notifier()->first(*this);
+		      }
 		      ItemIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ItemIt& operator++() {
 		        map.notifier()->next(*this);
 		        return *this;
+		      }
 		    protected:
 		      const Map& map;
 		    };
 		  };
 		  // \ingroup graphbits
 		  //
 		  // \brief Extender for maps which use a subset of the items.
 		  template <typename _Graph, typename _Map>
 		  class SubMapExtender : public _Map {
 		  public:
 		    typedef _Map Parent;
 		    typedef SubMapExtender Map;
 		    typedef _Graph Graph;
 		    typedef typename Parent::Key Item;
 		    typedef typename Parent::Key Key;
 		    typedef typename Parent::Value Value;
 		    typedef typename Parent::Reference Reference;
 		    typedef typename Parent::ConstReference ConstReference;
 		    class MapIt;
 		    class ConstMapIt;
 		    friend class MapIt;
 		    friend class ConstMapIt;
 		  public:
 		    SubMapExtender(const Graph& _graph)
 		      : Parent(_graph), graph(_graph) {}
 		    SubMapExtender(const Graph& _graph, const Value& _value)
 		      : Parent(_graph, _value), graph(_graph) {}
 		  private:
 		    SubMapExtender& operator=(const SubMapExtender& cmap) {
 		      return operator=<MapExtender>(cmap);
+		    }
 		    template <typename CMap>
 		    SubMapExtender& operator=(const CMap& cmap) {
 		      checkConcept<concepts::ReadMap<Key, Value>, CMap>();
 		      Item it;
 		      for (graph.first(it); it != INVALID; graph.next(it)) {
 		        Parent::set(it, cmap[it]);
+		      }
 		      return *this;
+		    }
 		  public:
 		    class MapIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      typedef typename Map::Value Value;
 		      MapIt() {}
 		      MapIt(Invalid i) : Parent(i) { }
 		      explicit MapIt(Map& _map) : map(_map) {
 		        map.graph.first(*this);
+		      }
 		      MapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      MapIt& operator++() {
 		        map.graph.next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		      typename MapTraits<Map>::ReturnValue operator*() {
 		        return map[*this];
+		      }
 		      void set(const Value& value) {
 		        map.set(*this, value);
+		      }
 		    protected:
 		      Map& map;
 		    };
 		    class ConstMapIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      typedef typename Map::Value Value;
 		      ConstMapIt() {}
 		      ConstMapIt(Invalid i) : Parent(i) { }
 		      explicit ConstMapIt(Map& _map) : map(_map) {
 		        map.graph.first(*this);
+		      }
 		      ConstMapIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ConstMapIt& operator++() {
 		        map.graph.next(*this);
 		        return *this;
+		      }
 		      typename MapTraits<Map>::ConstReturnValue operator*() const {
 		        return map[*this];
+		      }
 		    protected:
 		      const Map& map;
 		    };
 		    class ItemIt : public Item {
 		    public:
 		      typedef Item Parent;
 		      ItemIt() {}
 		      ItemIt(Invalid i) : Parent(i) { }
 		      explicit ItemIt(Map& _map) : map(_map) {
 		        map.graph.first(*this);
+		      }
 		      ItemIt(const Map& _map, const Item& item)
 		        : Parent(item), map(_map) {}
 		      ItemIt& operator++() {
 		        map.graph.next(*this);
 		        return *this;
+		      }
 		    protected:
 		      const Map& map;
 		    };
 		  private:
 		    const Graph& graph;
 		  };
+		}
 		#endif

lemon/cbc.cc

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		///\file
 		///\brief Implementation of the CBC MIP solver interface.
 		#include "cbc.h"
 		#include <coin/CoinModel.hpp>
 		#include <coin/CbcModel.hpp>
 		#include <coin/OsiSolverInterface.hpp>
 		#ifdef COIN_HAS_CLP
 		#include "coin/OsiClpSolverInterface.hpp"
 		#endif
 		#ifdef COIN_HAS_OSL
 		#include "coin/OsiOslSolverInterface.hpp"
 		#endif
 		#include "coin/CbcCutGenerator.hpp"
 		#include "coin/CbcHeuristicLocal.hpp"
 		#include "coin/CbcHeuristicGreedy.hpp"
 		#include "coin/CbcHeuristicFPump.hpp"
 		#include "coin/CbcHeuristicRINS.hpp"
 		#include "coin/CglGomory.hpp"
 		#include "coin/CglProbing.hpp"
 		#include "coin/CglKnapsackCover.hpp"
 		#include "coin/CglOddHole.hpp"
 		#include "coin/CglClique.hpp"
 		#include "coin/CglFlowCover.hpp"
 		#include "coin/CglMixedIntegerRounding.hpp"
 		#include "coin/CbcHeuristic.hpp"
 		namespace lemon {
 		  CbcMip::CbcMip() {
 		    _prob = new CoinModel();
 		    _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() {
 		    delete _prob;
 		    if (_osi_solver) delete _osi_solver;
 		    if (_cbc_model) delete _cbc_model;
+		  }
 		  const char* CbcMip::_solverName() const { return "CbcMip"; }
 		  int CbcMip::_addCol() {
 		    _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0, 0, false);
 		    return _prob->numberColumns() - 1;
+		  }
 		  CbcMip* CbcMip::newSolver() const {
 		    CbcMip* newlp = new CbcMip;
 		    return newlp;
+		  }
 		  CbcMip* CbcMip::cloneSolver() const {
 		    CbcMip* copylp = new CbcMip(*this);
 		    return copylp;
+		  }
 		  int CbcMip::_addRow() {
 		    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
 		    return _prob->numberRows() - 1;
+		  }
 		  void CbcMip::_eraseCol(int i) {
 		    _prob->deleteColumn(i);
+		  }
 		  void CbcMip::_eraseRow(int i) {
 		    _prob->deleteRow(i);
+		  }
 		  void CbcMip::_eraseColId(int i) {
 		    cols.eraseIndex(i);
+		  }
 		  void CbcMip::_eraseRowId(int i) {
 		    rows.eraseIndex(i);
+		  }
 		  void CbcMip::_getColName(int c, std::string& name) const {
 		    name = _prob->getColumnName(c);
+		  }
 		  void CbcMip::_setColName(int c, const std::string& name) {
 		    _prob->setColumnName(c, name.c_str());
+		  }
 		  int CbcMip::_colByName(const std::string& name) const {
 		    return _prob->column(name.c_str());
+		  }
 		  void CbcMip::_getRowName(int r, std::string& name) const {
 		    name = _prob->getRowName(r);
+		  }
 		  void CbcMip::_setRowName(int r, const std::string& name) {
 		    _prob->setRowName(r, name.c_str());
+		  }
 		  int CbcMip::_rowByName(const std::string& name) const {
 		    return _prob->row(name.c_str());
+		  }
 		  void CbcMip::_setRowCoeffs(int i, ExprIterator b, ExprIterator e) {
 		    for (ExprIterator it = b; it != e; ++it) {
 		      _prob->setElement(i, it->first, it->second);
+		    }
+		  }
 		  void CbcMip::_getRowCoeffs(int ix, InsertIterator b) const {
 		    int length = _prob->numberRows();
 		    std::vector<int> indices(length);
 		    std::vector<Value> values(length);
 		    length = _prob->getRow(ix, &indices[0], &values[0]);
 		    for (int i = 0; i < length; ++i) {
 		      *b = std::make_pair(indices[i], values[i]);
 		      ++b;
+		    }
+		  }
 		  void CbcMip::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
 		    for (ExprIterator it = b; it != e; ++it) {
 		      _prob->setElement(it->first, ix, it->second);
+		    }
+		  }
 		  void CbcMip::_getColCoeffs(int ix, InsertIterator b) const {
 		    int length = _prob->numberColumns();
 		    std::vector<int> indices(length);
 		    std::vector<Value> values(length);
 		    length = _prob->getColumn(ix, &indices[0], &values[0]);
 		    for (int i = 0; i < length; ++i) {
 		      *b = std::make_pair(indices[i], values[i]);
 		      ++b;
+		    }
+		  }
 		  void CbcMip::_setCoeff(int ix, int jx, Value value) {
 		    _prob->setElement(ix, jx, value);
+		  }
 		  CbcMip::Value CbcMip::_getCoeff(int ix, int jx) const {
 		    return _prob->getElement(ix, jx);
+		  }
 		  void CbcMip::_setColLowerBound(int i, Value lo) {
 		    LEMON_ASSERT(lo != INF, "Invalid bound");
 		    _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
+		  }
 		  CbcMip::Value CbcMip::_getColLowerBound(int i) const {
 		    double val = _prob->getColumnLower(i);
 		    return val == - COIN_DBL_MAX ? - INF : val;
+		  }
 		  void CbcMip::_setColUpperBound(int i, Value up) {
 		    LEMON_ASSERT(up != -INF, "Invalid bound");
 		    _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
+		  }
 		  CbcMip::Value CbcMip::_getColUpperBound(int i) const {
 		    double val = _prob->getColumnUpper(i);
 		    return val == COIN_DBL_MAX ? INF : val;
+		  }
 		  void CbcMip::_setRowLowerBound(int i, Value lo) {
 		    LEMON_ASSERT(lo != INF, "Invalid bound");
 		    _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
+		  }
 		  CbcMip::Value CbcMip::_getRowLowerBound(int i) const {
 		    double val = _prob->getRowLower(i);
 		    return val == - COIN_DBL_MAX ? - INF : val;
+		  }
 		  void CbcMip::_setRowUpperBound(int i, Value up) {
 		    LEMON_ASSERT(up != -INF, "Invalid bound");
 		    _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
+		  }
 		  CbcMip::Value CbcMip::_getRowUpperBound(int i) const {
 		    double val = _prob->getRowUpper(i);
 		    return val == COIN_DBL_MAX ? INF : val;
+		  }
 		  void CbcMip::_setObjCoeffs(ExprIterator b, ExprIterator e) {
 		    int num = _prob->numberColumns();
 		    for (int i = 0; i < num; ++i) {
 		      _prob->setColumnObjective(i, 0.0);
+		    }
 		    for (ExprIterator it = b; it != e; ++it) {
 		      _prob->setColumnObjective(it->first, it->second);
+		    }
+		  }
 		  void CbcMip::_getObjCoeffs(InsertIterator b) const {
 		    int num = _prob->numberColumns();
 		    for (int i = 0; i < num; ++i) {
 		      Value coef = _prob->getColumnObjective(i);
 		      if (coef != 0.0) {
 		        *b = std::make_pair(i, coef);
 		        ++b;
+		      }
+		    }
+		  }
 		  void CbcMip::_setObjCoeff(int i, Value obj_coef) {
 		    _prob->setColumnObjective(i, obj_coef);
+		  }
 		  CbcMip::Value CbcMip::_getObjCoeff(int i) const {
 		    return _prob->getColumnObjective(i);
+		  }
 		  CbcMip::SolveExitStatus CbcMip::_solve() {
 		    if (_osi_solver) {
 		      delete _osi_solver;
+		    }
 		#ifdef COIN_HAS_CLP
 		    _osi_solver = new OsiClpSolverInterface();
 		#elif COIN_HAS_OSL
 		    _osi_solver = new OsiOslSolverInterface();
 		#else
 		#error Cannot instantiate Osi solver
 		#endif
 		    _osi_solver->loadFromCoinModel(*_prob);
 		    if (_cbc_model) {
 		      delete _cbc_model;
+		    }
 		    _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);
 		    if (!_cbc_model->isInitialSolveAbandoned() &&
 		        _cbc_model->isInitialSolveProvenOptimal() &&
 		        !_cbc_model->isInitialSolveProvenPrimalInfeasible() &&
 		        !_cbc_model->isInitialSolveProvenDualInfeasible()) {
 		      CglProbing generator1;
 		      generator1.setUsingObjective(true);
 		      generator1.setMaxPass(3);
 		      generator1.setMaxProbe(100);
 		      generator1.setMaxLook(50);
 		      generator1.setRowCuts(3);
 		      _cbc_model->addCutGenerator(&generator1, -1, "Probing");
 		      CglGomory generator2;
 		      generator2.setLimit(300);
 		      _cbc_model->addCutGenerator(&generator2, -1, "Gomory");
 		      CglKnapsackCover generator3;
 		      _cbc_model->addCutGenerator(&generator3, -1, "Knapsack");
 		      CglOddHole generator4;
 		      generator4.setMinimumViolation(0.005);
 		      generator4.setMinimumViolationPer(0.00002);
 		      generator4.setMaximumEntries(200);
 		      _cbc_model->addCutGenerator(&generator4, -1, "OddHole");
 		      CglClique generator5;
 		      generator5.setStarCliqueReport(false);
 		      generator5.setRowCliqueReport(false);
 		      _cbc_model->addCutGenerator(&generator5, -1, "Clique");
 		      CglMixedIntegerRounding mixedGen;
 		      _cbc_model->addCutGenerator(&mixedGen, -1, "MixedIntegerRounding");
 		      CglFlowCover flowGen;
 		      _cbc_model->addCutGenerator(&flowGen, -1, "FlowCover");
 		#ifdef COIN_HAS_CLP
 		      OsiClpSolverInterface* osiclp =
 		        dynamic_cast<OsiClpSolverInterface*>(_cbc_model->solver());
 		      if (osiclp->getNumRows() < 300 && osiclp->getNumCols() < 500) {
 		        osiclp->setupForRepeatedUse(2, 0);
+		      }
 		#endif
 		      CbcRounding heuristic1(*_cbc_model);
 		      heuristic1.setWhen(3);
 		      _cbc_model->addHeuristic(&heuristic1);
 		      CbcHeuristicLocal heuristic2(*_cbc_model);
 		      heuristic2.setWhen(3);
 		      _cbc_model->addHeuristic(&heuristic2);
 		      CbcHeuristicGreedyCover heuristic3(*_cbc_model);
 		      heuristic3.setAlgorithm(11);
 		      heuristic3.setWhen(3);
 		      _cbc_model->addHeuristic(&heuristic3);
 		      CbcHeuristicFPump heuristic4(*_cbc_model);
 		      heuristic4.setWhen(3);
 		      _cbc_model->addHeuristic(&heuristic4);
 		      CbcHeuristicRINS heuristic5(*_cbc_model);
 		      heuristic5.setWhen(3);
 		      _cbc_model->addHeuristic(&heuristic5);
 		      if (_cbc_model->getNumCols() < 500) {
 		        _cbc_model->setMaximumCutPassesAtRoot(-100);
 		      } else if (_cbc_model->getNumCols() < 5000) {
 		        _cbc_model->setMaximumCutPassesAtRoot(100);
 		      } else {
 		        _cbc_model->setMaximumCutPassesAtRoot(20);
+		      }
 		      if (_cbc_model->getNumCols() < 5000) {
 		        _cbc_model->setNumberStrong(10);
+		      }
 		      _cbc_model->solver()->setIntParam(OsiMaxNumIterationHotStart, 100);
 		      _cbc_model->branchAndBound();
+		    }
 		    if (_cbc_model->isAbandoned()) {
 		      return UNSOLVED;
 		    } else {
 		      return SOLVED;
+		    }
+		  }
 		  CbcMip::Value CbcMip::_getSol(int i) const {
 		    return _cbc_model->getColSolution()[i];
+		  }
 		  CbcMip::Value CbcMip::_getSolValue() const {
 		    return _cbc_model->getObjValue();
+		  }
 		  CbcMip::ProblemType CbcMip::_getType() const {
 		    if (_cbc_model->isProvenOptimal()) {
 		      return OPTIMAL;
 		    } else if (_cbc_model->isContinuousUnbounded()) {
 		      return UNBOUNDED;
+		    }
 		    return FEASIBLE;
+		  }
 		  void CbcMip::_setSense(Sense sense) {
 		    switch (sense) {
 		    case MIN:
 		      _prob->setOptimizationDirection(1.0);
 		      break;
 		    case MAX:
 		      _prob->setOptimizationDirection(- 1.0);
 		      break;
+		    }
+		  }
 		  CbcMip::Sense CbcMip::_getSense() const {
 		    if (_prob->optimizationDirection() > 0.0) {
 		      return MIN;
 		    } else if (_prob->optimizationDirection() < 0.0) {
 		      return MAX;
 		    } else {
 		      LEMON_ASSERT(false, "Wrong sense");
 		      return CbcMip::Sense();
+		    }
+		  }
 		  void CbcMip::_setColType(int i, CbcMip::ColTypes col_type) {
 		    switch (col_type){
 		    case INTEGER:
 		      _prob->setInteger(i);
 		      break;
 		    case REAL:
 		      _prob->setContinuous(i);
 		      break;
 		    default:;
 		      LEMON_ASSERT(false, "Wrong sense");
+		    }
+		  }
 		  CbcMip::ColTypes CbcMip::_getColType(int i) const {
 		    return _prob->getColumnIsInteger(i) ? INTEGER : REAL;
+		  }
 		  void CbcMip::_clear() {
 		    delete _prob;
 		    if (_osi_solver) {
 		      delete _osi_solver;
 		      _osi_solver = 0;
+		    }
 		    if (_cbc_model) {
 		      delete _cbc_model;
 		      _cbc_model = 0;
+		    }
 		    _prob = new CoinModel();
 		    rows.clear();
 		    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

lemon/cbc.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2009
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		// -*- C++ -*-
 		#ifndef LEMON_CBC_H
 		#define LEMON_CBC_H
 		///\file
 		///\brief Header of the LEMON-CBC mip solver interface.
 		///\ingroup lp_group
 		#include <lemon/lp_base.h>
 		class CoinModel;
 		class OsiSolverInterface;
 		class CbcModel;
 		namespace lemon {
 		  /// \brief Interface for the CBC MIP solver
 		  ///
 		  /// This class implements an interface for the CBC MIP solver.
 		  ///\ingroup lp_group
 		  class CbcMip : public MipSolver {
 		  protected:
 		    CoinModel *_prob;
 		    OsiSolverInterface *_osi_solver;
 		    CbcModel *_cbc_model;
 		  public:
 		    /// \e
 		    CbcMip();
 		    /// \e
 		    CbcMip(const CbcMip&);
 		    /// \e
 		    ~CbcMip();
 		    /// \e
 		    virtual CbcMip* newSolver() const;
 		    /// \e
 		    virtual CbcMip* cloneSolver() const;
 		  protected:
 		    virtual const char* _solverName() const;
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual void _eraseCol(int i);
 		    virtual void _eraseRow(int i);
 		    virtual void _eraseColId(int i);
 		    virtual void _eraseRowId(int i);
 		    virtual void _getColName(int col, std::string& name) const;
 		    virtual void _setColName(int col, const std::string& name);
 		    virtual int _colByName(const std::string& name) const;
 		    virtual void _getRowName(int row, std::string& name) const;
 		    virtual void _setRowName(int row, const std::string& name);
 		    virtual int _rowByName(const std::string& name) const;
 		    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getRowCoeffs(int i, InsertIterator b) const;
 		    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getColCoeffs(int i, InsertIterator b) const;
 		    virtual void _setCoeff(int row, int col, Value value);
 		    virtual Value _getCoeff(int row, int col) const;
 		    virtual void _setColLowerBound(int i, Value value);
 		    virtual Value _getColLowerBound(int i) const;
 		    virtual void _setColUpperBound(int i, Value value);
 		    virtual Value _getColUpperBound(int i) const;
 		    virtual void _setRowLowerBound(int i, Value value);
 		    virtual Value _getRowLowerBound(int i) const;
 		    virtual void _setRowUpperBound(int i, Value value);
 		    virtual Value _getRowUpperBound(int i) const;
 		    virtual void _setObjCoeffs(ExprIterator b, ExprIterator e);
 		    virtual void _getObjCoeffs(InsertIterator b) const;
 		    virtual void _setObjCoeff(int i, Value obj_coef);
 		    virtual Value _getObjCoeff(int i) const;
 		    virtual void _setSense(Sense sense);
 		    virtual Sense _getSense() const;
 		    virtual ColTypes _getColType(int col) const;
 		    virtual void _setColType(int col, ColTypes col_type);
 		    virtual SolveExitStatus _solve();
 		    virtual ProblemType _getType() const;
 		    virtual Value _getSol(int i) const;
 		    virtual Value _getSolValue() const;
 		    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);
 		  };
+		}
 		#endif

lemon/circulation.h

Show inline comments

@@ -72,682 +72,682 @@
 		    /// The type of the map that stores the flow values.
 		    /// It must meet the \ref concepts::ReadWriteMap "ReadWriteMap" concept.
 		    typedef typename Digraph::template ArcMap<Value> FlowMap;
 		    /// \brief Instantiates a FlowMap.
 		    ///
 		    /// This function instantiates a \ref FlowMap.
 		    /// \param digraph The digraph, to which we would like to define
 		    /// the flow map.
 		    static FlowMap* createFlowMap(const Digraph& digraph) {
 		      return new FlowMap(digraph);
+		    }
 		    /// \brief The elevator type used by the algorithm.
 		    ///
 		    /// The elevator type used by the algorithm.
 		    ///
 		    /// \sa Elevator
 		    /// \sa LinkedElevator
 		    typedef lemon::Elevator<Digraph, typename Digraph::Node> Elevator;
 		    /// \brief Instantiates an Elevator.
 		    ///
 		    /// This function instantiates an \ref Elevator.
 		    /// \param digraph The digraph, to which we would like to define
 		    /// the elevator.
 		    /// \param max_level The maximum level of the elevator.
 		    static Elevator* createElevator(const Digraph& digraph, int max_level) {
 		      return new Elevator(digraph, max_level);
+		    }
 		    /// \brief The tolerance used by the algorithm
 		    ///
 		    /// The tolerance used by the algorithm to handle inexact computation.
 		    typedef lemon::Tolerance<Value> Tolerance;
 		  };
 		  /**
 		     \brief Push-relabel algorithm for the network circulation problem.
 		     \ingroup max_flow
 		     This class implements a push-relabel algorithm for the network
 		     circulation problem.
 		     It is to find a feasible circulation when lower and upper bounds
 		     are given for the flow values on the arcs and lower bounds
 		     are given for the supply values of the nodes.
 		     The exact formulation of this problem is the following.
 		     Let \f$G=(V,A)\f$ be a digraph,
 		     \f$lower, upper: A\rightarrow\mathbf{R}^+_0\f$,
 		     \f$delta: V\rightarrow\mathbf{R}\f$. Find a feasible circulation
 		     \f$f: A\rightarrow\mathbf{R}^+_0\f$ so that
 		     \f[ \sum_{a\in\delta_{out}(v)} f(a) - \sum_{a\in\delta_{in}(v)} f(a)
 		     \geq delta(v) \quad \forall v\in V, \f]
 		     \f[ lower(a)\leq f(a) \leq upper(a) \quad \forall a\in A. \f]
 		     \note \f$delta(v)\f$ specifies a lower bound for the supply of node
 		     \f$v\f$. It can be either positive or negative, however note that
 		     \f$\sum_{v\in V}delta(v)\f$ should be zero or negative in order to
 		     have a feasible solution.
 		     \note A special case of this problem is when
 		     \f$\sum_{v\in V}delta(v) = 0\f$. Then the supply of each node \f$v\f$
 		     will be \e equal \e to \f$delta(v)\f$, if a circulation can be found.
 		     Thus a feasible solution for the
 		     \ref min_cost_flow "minimum cost flow" problem can be calculated
 		     in this way.
 		     \tparam GR The type of the digraph the algorithm runs on.
 		     \tparam LM The type of the lower bound capacity map. The default
 		     map type is \ref concepts::Digraph::ArcMap "GR::ArcMap<int>".
 		     \tparam UM The type of the upper bound capacity map. The default
 		     map type is \c LM.
 		     \tparam DM The type of the map that stores the lower bound
 		     for the supply of the nodes. The default map type is
 		     \ref concepts::Digraph::NodeMap "GR::NodeMap<UM::Value>".
 		  */
 		#ifdef DOXYGEN
 		template< typename GR,
 		          typename LM,
 		          typename UM,
 		          typename DM,
 		          typename TR >
 		#else
 		template< typename GR,
 		          typename LM = typename GR::template ArcMap<int>,
 		          typename UM = LM,
 		          typename DM = typename GR::template NodeMap<typename UM::Value>,
 		          typename TR = CirculationDefaultTraits<GR, LM, UM, DM> >
 		#endif
 		  class Circulation {
 		  public:
 		    ///The \ref CirculationDefaultTraits "traits class" of the algorithm.
 		    typedef TR Traits;
 		    ///The type of the digraph the algorithm runs on.
 		    typedef typename Traits::Digraph Digraph;
 		    ///The type of the flow values.
 		    typedef typename Traits::Value Value;
 		    /// The type of the lower bound capacity map.
 		    typedef typename Traits::LCapMap LCapMap;
 		    /// The type of the upper bound capacity map.
 		    typedef typename Traits::UCapMap UCapMap;
 		    /// \brief The type of the map that stores the lower bound for
 		    /// the supply of the nodes.
 		    typedef typename Traits::DeltaMap DeltaMap;
 		    ///The type of the flow map.
 		    typedef typename Traits::FlowMap FlowMap;
 		    ///The type of the elevator.
 		    typedef typename Traits::Elevator Elevator;
 		    ///The type of the tolerance.
 		    typedef typename Traits::Tolerance Tolerance;
 		  private:
 		    TEMPLATE_DIGRAPH_TYPEDEFS(Digraph);
 		    const Digraph &_g;
 		    int _node_num;
 		    const LCapMap *_lo;
 		    const UCapMap *_up;
 		    const DeltaMap *_delta;
 		    FlowMap *_flow;
 		    bool _local_flow;
 		    Elevator* _level;
 		    bool _local_level;
 		    typedef typename Digraph::template NodeMap<Value> ExcessMap;
 		    ExcessMap* _excess;
 		    Tolerance _tol;
 		    int _el;
 		  public:
 		    typedef Circulation Create;
 		    ///\name Named Template Parameters
 		    ///@{
 		    template <typename T>
 		    struct SetFlowMapTraits : public Traits {
 		      typedef T FlowMap;
 		      static FlowMap *createFlowMap(const Digraph&) {
 		        LEMON_ASSERT(false, "FlowMap is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// FlowMap type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting FlowMap
 		    /// type.
 		    template <typename T>
 		    struct SetFlowMap
 		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                           SetFlowMapTraits<T> > {
 		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                          SetFlowMapTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph&, int) {
 		        LEMON_ASSERT(false, "Elevator is not initialized");
 		        return 0; // ignore warnings
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type. If this named parameter is used, then an external
 		    /// elevator object must be passed to the algorithm using the
 		    /// \ref elevator(Elevator&) "elevator()" function before calling
 		    /// \ref run() or \ref init().
 		    /// \sa SetStandardElevator
 		    template <typename T>
 		    struct SetElevator
 		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                           SetElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                          SetElevatorTraits<T> > Create;
 		    };
 		    template <typename T>
 		    struct SetStandardElevatorTraits : public Traits {
 		      typedef T Elevator;
 		      static Elevator *createElevator(const Digraph& digraph, int max_level) {
 		        return new Elevator(digraph, max_level);
+		      }
 		    };
 		    /// \brief \ref named-templ-param "Named parameter" for setting
 		    /// Elevator type with automatic allocation
 		    ///
 		    /// \ref named-templ-param "Named parameter" for setting Elevator
 		    /// type with automatic allocation.
 		    /// The Elevator should have standard constructor interface to be
 		    /// able to automatically created by the algorithm (i.e. the
 		    /// digraph and the maximum level should be passed to it).
 		    /// However an external elevator object could also be passed to the
 		    /// algorithm with the \ref elevator(Elevator&) "elevator()" function
 		    /// before calling \ref run() or \ref init().
 		    /// \sa SetElevator
 		    template <typename T>
 		    struct SetStandardElevator
 		      : public Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                       SetStandardElevatorTraits<T> > {
 		      typedef Circulation<Digraph, LCapMap, UCapMap, DeltaMap,
 		                      SetStandardElevatorTraits<T> > Create;
 		    };
 		    /// @}
 		  protected:
 		    Circulation() {}
 		  public:
 		    /// The constructor of the class.
 		    /// The constructor of the class.
 		    /// \param g The digraph the algorithm runs on.
 		    /// \param lo The lower bound capacity of the arcs.
 		    /// \param up The upper bound capacity of the arcs.
 		    /// \param delta The lower bound for the supply of the nodes.
 		    Circulation(const Digraph &g,const LCapMap &lo,
 		                const UCapMap &up,const DeltaMap &delta)
 		      : _g(g), _node_num(),
 		        _lo(&lo),_up(&up),_delta(&delta),_flow(0),_local_flow(false),
 		        _level(0), _local_level(false), _excess(0), _el() {}
 		    /// Destructor.
 		    ~Circulation() {
 		      destroyStructures();
+		    }
 		  private:
 		    void createStructures() {
 		      _node_num = _el = countNodes(_g);
 		      if (!_flow) {
 		        _flow = Traits::createFlowMap(_g);
 		        _local_flow = true;
+		      }
 		      if (!_level) {
 		        _level = Traits::createElevator(_g, _node_num);
 		        _local_level = true;
+		      }
 		      if (!_excess) {
 		        _excess = new ExcessMap(_g);
+		      }
+		    }
 		    void destroyStructures() {
 		      if (_local_flow) {
 		        delete _flow;
+		      }
 		      if (_local_level) {
 		        delete _level;
+		      }
 		      if (_excess) {
 		        delete _excess;
+		      }
+		    }
 		  public:
 		    /// Sets the lower bound capacity map.
 		    /// Sets the lower bound capacity map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& lowerCapMap(const LCapMap& map) {
 		      _lo = &map;
 		      return *this;
+		    }
 		    /// Sets the upper bound capacity map.
 		    /// Sets the upper bound capacity map.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& upperCapMap(const LCapMap& map) {
 		      _up = &map;
 		      return *this;
+		    }
 		    /// Sets the lower bound map for the supply of the nodes.
 		    /// Sets the lower bound map for the supply of the nodes.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& deltaMap(const DeltaMap& map) {
 		      _delta = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the flow map.
 		    ///
 		    /// Sets the flow map.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated map,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& flowMap(FlowMap& map) {
 		      if (_local_flow) {
 		        delete _flow;
 		        _local_flow = false;
+		      }
 		      _flow = &map;
 		      return *this;
+		    }
 		    /// \brief Sets the elevator used by algorithm.
 		    ///
 		    /// Sets the elevator used by algorithm.
 		    /// If you don't use this function before calling \ref run() or
 		    /// \ref init(), an instance will be allocated automatically.
 		    /// The destructor deallocates this automatically allocated elevator,
 		    /// of course.
 		    /// \return <tt>(*this)</tt>
 		    Circulation& elevator(Elevator& elevator) {
 		      if (_local_level) {
 		        delete _level;
 		        _local_level = false;
+		      }
 		      _level = &elevator;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the elevator.
 		    ///
 		    /// Returns a const reference to the elevator.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const Elevator& elevator() const {
 		      return *_level;
+		    }
 		    /// \brief Sets the tolerance used by algorithm.
 		    ///
 		    /// Sets the tolerance used by algorithm.
 		    Circulation& tolerance(const Tolerance& tolerance) const {
 		      _tol = tolerance;
 		      return *this;
+		    }
 		    /// \brief Returns a const reference to the tolerance.
 		    ///
 		    /// Returns a const reference to the tolerance.
 		    const Tolerance& tolerance() const {
 		      return tolerance;
+		    }
 		    /// \name Execution Control
 		    /// The simplest way to execute the algorithm is to call \ref run().\n
 		    /// If you need more control on the initial solution or the execution,
 		    /// first you have to call one of the \ref init() functions, then
 		    /// the \ref start() function.
 		    ///@{
 		    /// Initializes the internal data structures.
 		    /// Initializes the internal data structures and sets all flow values
 		    /// to the lower bound.
 		    void init()
+		    {
 		      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
 		      // worse performance for random digraphs
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    /// Initializes the internal data structures using a greedy approach.
 		    /// Initializes the internal data structures using a greedy approach
 		    /// to construct the initial solution.
 		    void greedyInit()
+		    {
 		      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;
+		        }
+		      }
 		      _level->initStart();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        _level->initAddItem(n);
 		      _level->initFinish();
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(_tol.positive((*_excess)[n]))
 		          _level->activate(n);
+		    }
 		    ///Executes the algorithm
 		    ///This function executes the algorithm.
 		    ///
 		    ///\return \c true if a feasible circulation is found.
 		    ///
 		    ///\sa barrier()
 		    ///\sa barrierMap()
 		    bool start()
+		    {
 		      Node act;
 		      Node bact=INVALID;
 		      Node last_activated=INVALID;
 		      while((act=_level->highestActive())!=INVALID) {
 		        int actlevel=(*_level)[act];
 		        int mlevel=_node_num;
 		        Value exc=(*_excess)[act];
 		        for(OutArcIt e(_g,act);e!=INVALID; ++e) {
 		          Node v = _g.target(e);
 		          Value fc=(*_up)[e]-(*_flow)[e];
 		          if(!_tol.positive(fc)) continue;
 		          if((*_level)[v]<actlevel) {
 		            if(!_tol.less(fc, exc)) {
 		              _flow->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;
+		            }
+		          }
 		          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
+		        }
 		        for(InArcIt e(_g,act);e!=INVALID; ++e) {
 		          Node v = _g.source(e);
 		          Value fc=(*_flow)[e]-(*_lo)[e];
 		          if(!_tol.positive(fc)) continue;
 		          if((*_level)[v]<actlevel) {
 		            if(!_tol.less(fc, exc)) {
 		              _flow->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;
+		            }
+		          }
 		          else if((*_level)[v]<mlevel) mlevel=(*_level)[v];
+		        }
-		        _excess->set(act, exc);
+		        (*_excess)[act] = exc;
 		        if(!_tol.positive(exc)) _level->deactivate(act);
 		        else if(mlevel==_node_num) {
 		          _level->liftHighestActiveToTop();
 		          _el = _node_num;
 		          return false;
+		        }
 		        else {
 		          _level->liftHighestActive(mlevel+1);
 		          if(_level->onLevel(actlevel)==0) {
 		            _el = actlevel;
 		            return false;
+		          }
+		        }
 		      next_l:
+		        ;
+		      }
 		      return true;
+		    }
 		    /// Runs the algorithm.
 		    /// This function runs the algorithm.
 		    ///
 		    /// \return \c true if a feasible circulation is found.
 		    ///
 		    /// \note Apart from the return value, c.run() is just a shortcut of
 		    /// the following code.
 		    /// \code
 		    ///   c.greedyInit();
 		    ///   c.start();
 		    /// \endcode
 		    bool run() {
 		      greedyInit();
 		      return start();
+		    }
 		    /// @}
 		    /// \name Query Functions
 		    /// The results of the circulation algorithm can be obtained using
 		    /// these functions.\n
 		    /// Either \ref run() or \ref start() should be called before
 		    /// using them.
 		    ///@{
 		    /// \brief Returns the flow on the given arc.
 		    ///
 		    /// Returns the flow on the given arc.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    Value flow(const Arc& arc) const {
 		      return (*_flow)[arc];
+		    }
 		    /// \brief Returns a const reference to the flow map.
 		    ///
 		    /// Returns a const reference to the arc map storing the found flow.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    const FlowMap& flowMap() const {
 		      return *_flow;
+		    }
 		    /**
 		       \brief Returns \c true if the given node is in a barrier.
 		       Barrier is a set \e B of nodes for which
 		       \f[ \sum_{a\in\delta_{out}(B)} upper(a) -
 		           \sum_{a\in\delta_{in}(B)} lower(a) < \sum_{v\in B}delta(v) \f]
 		       holds. The existence of a set with this property prooves that a
 		       feasible circualtion cannot exist.
 		       This function returns \c true if the given node is in the found
 		       barrier. If a feasible circulation is found, the function
 		       gives back \c false for every node.
 		       \pre Either \ref run() or \ref init() must be called before
 		       using this function.
 		       \sa barrierMap()
 		       \sa checkBarrier()
 		    */
 		    bool barrier(const Node& node) const
+		    {
 		      return (*_level)[node] >= _el;
+		    }
 		    /// \brief Gives back a barrier.
 		    ///
 		    /// This function sets \c bar to the characteristic vector of the
 		    /// found barrier. \c bar should be a \ref concepts::WriteMap "writable"
 		    /// node map with \c bool (or convertible) value type.
 		    ///
 		    /// If a feasible circulation is found, the function gives back an
 		    /// empty set, so \c bar[v] will be \c false for all nodes \c v.
 		    ///
 		    /// \note This function calls \ref barrier() for each node,
 		    /// so it runs in O(n) time.
 		    ///
 		    /// \pre Either \ref run() or \ref init() must be called before
 		    /// using this function.
 		    ///
 		    /// \sa barrier()
 		    /// \sa checkBarrier()
 		    template<class BarrierMap>
 		    void barrierMap(BarrierMap &bar) const
+		    {
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        bar.set(n, (*_level)[n] >= _el);
+		    }
 		    /// @}
 		    /// \name Checker Functions
 		    /// The feasibility of the results can be checked using
 		    /// these functions.\n
 		    /// Either \ref run() or \ref start() should be called before
 		    /// using them.
 		    ///@{
 		    ///Check if the found flow is a feasible circulation
 		    ///Check if the found flow is a feasible circulation,
 		    ///
 		    bool checkFlow() const {
 		      for(ArcIt e(_g);e!=INVALID;++e)
 		        if((*_flow)[e]<(*_lo)[e]||(*_flow)[e]>(*_up)[e]) return false;
 		      for(NodeIt n(_g);n!=INVALID;++n)
+		        {
 		          Value dif=-(*_delta)[n];
 		          for(InArcIt e(_g,n);e!=INVALID;++e) dif-=(*_flow)[e];
 		          for(OutArcIt e(_g,n);e!=INVALID;++e) dif+=(*_flow)[e];
 		          if(_tol.negative(dif)) return false;
+		        }
 		      return true;
+		    }
 		    ///Check whether or not the last execution provides a barrier
 		    ///Check whether or not the last execution provides a barrier.
 		    ///\sa barrier()
 		    ///\sa barrierMap()
 		    bool checkBarrier() const
+		    {
 		      Value delta=0;
 		      for(NodeIt n(_g);n!=INVALID;++n)
 		        if(barrier(n))
 		          delta-=(*_delta)[n];
 		      for(ArcIt e(_g);e!=INVALID;++e)
+		        {
 		          Node s=_g.source(e);
 		          Node t=_g.target(e);
 		          if(barrier(s)&&!barrier(t)) delta+=(*_up)[e];
 		          else if(barrier(t)&&!barrier(s)) delta-=(*_lo)[e];
+		        }
 		      return _tol.negative(delta);
+		    }
 		    /// @}
 		  };
+		}
 		#endif

lemon/clp.cc

Show inline comments

/* -*- mode: C++; indent-tabs-mode: nil; -*-
 *
 * This file is a part of LEMON, a generic C++ optimization library.
 *
 * Copyright (C) 2003-2008
 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 * (Egervary Research Group on Combinatorial Optimization, EGRES).
 *
 * Permission to use, modify and distribute this software is granted
 * provided that this copyright notice appears in all copies. For
 * precise terms see the accompanying LICENSE file.
 *
 * This software is provided "AS IS" with no warranty of any kind,
 * express or implied, and with no claim as to its suitability for any
 * purpose.
 *
 */

#include <lemon/clp.h>
#include <coin/ClpSimplex.hpp>

namespace lemon {

  ClpLp::ClpLp() {
    _prob = new ClpSimplex();
    _init_temporals();
    messageLevel(MESSAGE_NO_OUTPUT);
    messageLevel(MESSAGE_NOTHING);
  }

  ClpLp::ClpLp(const ClpLp& other) {
    _prob = new ClpSimplex(*other._prob);
    rows = other.rows;
    cols = other.cols;
    _init_temporals();
    messageLevel(MESSAGE_NO_OUTPUT);
    messageLevel(MESSAGE_NOTHING);
  }

  ClpLp::~ClpLp() {
    delete _prob;
    _clear_temporals();
  }

  void ClpLp::_init_temporals() {
    _primal_ray = 0;
    _dual_ray = 0;
  }

  void ClpLp::_clear_temporals() {
    if (_primal_ray) {
      delete[] _primal_ray;
      _primal_ray = 0;
    }
    if (_dual_ray) {
      delete[] _dual_ray;
      _dual_ray = 0;
    }
  }

  ClpLp* ClpLp::newSolver() const {
    ClpLp* newlp = new ClpLp;
    return newlp;
  }

  ClpLp* ClpLp::cloneSolver() const {
    ClpLp* copylp = new ClpLp(*this);
    return copylp;
  }

  const char* ClpLp::_solverName() const { return "ClpLp"; }

  int ClpLp::_addCol() {
    _prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);
    return _prob->numberColumns() - 1;
  }

  int ClpLp::_addRow() {
    _prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
    return _prob->numberRows() - 1;
  }


  void ClpLp::_eraseCol(int c) {
    _col_names_ref.erase(_prob->getColumnName(c));
    _prob->deleteColumns(1, &c);
  }

  void ClpLp::_eraseRow(int r) {
    _row_names_ref.erase(_prob->getRowName(r));
    _prob->deleteRows(1, &r);
  }

  void ClpLp::_eraseColId(int i) {
    cols.eraseIndex(i);
    cols.shiftIndices(i);
  }

  void ClpLp::_eraseRowId(int i) {
    rows.eraseIndex(i);
    rows.shiftIndices(i);
  }

  void ClpLp::_getColName(int c, std::string& name) const {
    name = _prob->getColumnName(c);
  }

  void ClpLp::_setColName(int c, const std::string& name) {
    _prob->setColumnName(c, const_cast<std::string&>(name));
    _col_names_ref[name] = c;
  }

  int ClpLp::_colByName(const std::string& name) const {
    std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
    return it != _col_names_ref.end() ? it->second : -1;
  }

  void ClpLp::_getRowName(int r, std::string& name) const {
    name = _prob->getRowName(r);
  }

  void ClpLp::_setRowName(int r, const std::string& name) {
    _prob->setRowName(r, const_cast<std::string&>(name));
    _row_names_ref[name] = r;
  }

  int ClpLp::_rowByName(const std::string& name) const {
    std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
    return it != _row_names_ref.end() ? it->second : -1;
  }


  void ClpLp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
    std::map<int, Value> coeffs;

    int n = _prob->clpMatrix()->getNumCols();

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (int i = 0; i < n; ++i) {
      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];

      const int* it = std::lower_bound(indices + begin, indices + end, ix);
      if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
        coeffs[i] = 0.0;
      }
    }

    for (ExprIterator it = b; it != e; ++it) {
      coeffs[it->first] = it->second;
    }

    for (std::map<int, Value>::iterator it = coeffs.begin();
         it != coeffs.end(); ++it) {
      _prob->modifyCoefficient(ix, it->first, it->second);
    }
  }

  void ClpLp::_getRowCoeffs(int ix, InsertIterator b) const {
    int n = _prob->clpMatrix()->getNumCols();

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (int i = 0; i < n; ++i) {
      CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
      CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];

      const int* it = std::lower_bound(indices + begin, indices + end, ix);
      if (it != indices + end && *it == ix) {
        *b = std::make_pair(i, elements[it - indices]);
      }
    }
  }

  void ClpLp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
    std::map<int, Value> coeffs;

    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (CoinBigIndex i = begin; i != end; ++i) {
      if (elements[i] != 0.0) {
        coeffs[indices[i]] = 0.0;
      }
    }
    for (ExprIterator it = b; it != e; ++it) {
      coeffs[it->first] = it->second;
    }
    for (std::map<int, Value>::iterator it = coeffs.begin();
         it != coeffs.end(); ++it) {
      _prob->modifyCoefficient(it->first, ix, it->second);
    }
  }

  void ClpLp::_getColCoeffs(int ix, InsertIterator b) const {
    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    for (CoinBigIndex i = begin; i != end; ++i) {
      *b = std::make_pair(indices[i], elements[i]);
      ++b;
    }
  }

  void ClpLp::_setCoeff(int ix, int jx, Value value) {
    _prob->modifyCoefficient(ix, jx, value);
  }

  ClpLp::Value ClpLp::_getCoeff(int ix, int jx) const {
    CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
    CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];

    const int* indices = _prob->clpMatrix()->getIndices();
    const double* elements = _prob->clpMatrix()->getElements();

    const int* it = std::lower_bound(indices + begin, indices + end, jx);
    if (it != indices + end && *it == jx) {
      return elements[it - indices];
    } else {
      return 0.0;
    }
  }

  void ClpLp::_setColLowerBound(int i, Value lo) {
    _prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
  }

  ClpLp::Value ClpLp::_getColLowerBound(int i) const {
    double val = _prob->getColLower()[i];
    return val == - COIN_DBL_MAX ? - INF : val;
  }

  void ClpLp::_setColUpperBound(int i, Value up) {
    _prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
  }

  ClpLp::Value ClpLp::_getColUpperBound(int i) const {
    double val = _prob->getColUpper()[i];
    return val == COIN_DBL_MAX ? INF : val;
  }

  void ClpLp::_setRowLowerBound(int i, Value lo) {
    _prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
  }

  ClpLp::Value ClpLp::_getRowLowerBound(int i) const {
    double val = _prob->getRowLower()[i];
    return val == - COIN_DBL_MAX ? - INF : val;
  }

  void ClpLp::_setRowUpperBound(int i, Value up) {
    _prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
  }

  ClpLp::Value ClpLp::_getRowUpperBound(int i) const {
    double val = _prob->getRowUpper()[i];
    return val == COIN_DBL_MAX ? INF : val;
  }

  void ClpLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
    int num = _prob->clpMatrix()->getNumCols();
    for (int i = 0; i < num; ++i) {
      _prob->setObjectiveCoefficient(i, 0.0);
    }
    for (ExprIterator it = b; it != e; ++it) {
      _prob->setObjectiveCoefficient(it->first, it->second);
    }
  }

  void ClpLp::_getObjCoeffs(InsertIterator b) const {
    int num = _prob->clpMatrix()->getNumCols();
    for (int i = 0; i < num; ++i) {
      Value coef = _prob->getObjCoefficients()[i];
      if (coef != 0.0) {
        *b = std::make_pair(i, coef);
        ++b;
      }
    }
  }

  void ClpLp::_setObjCoeff(int i, Value obj_coef) {
    _prob->setObjectiveCoefficient(i, obj_coef);
  }

  ClpLp::Value ClpLp::_getObjCoeff(int i) const {
    return _prob->getObjCoefficients()[i];
  }

  ClpLp::SolveExitStatus ClpLp::_solve() {
    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
  }

  ClpLp::SolveExitStatus ClpLp::solvePrimal() {
    return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
  }

  ClpLp::SolveExitStatus ClpLp::solveDual() {
    return _prob->dual() >= 0 ? SOLVED : UNSOLVED;
  }

  ClpLp::SolveExitStatus ClpLp::solveBarrier() {
    return _prob->barrier() >= 0 ? SOLVED : UNSOLVED;
  }

  ClpLp::Value ClpLp::_getPrimal(int i) const {
    return _prob->primalColumnSolution()[i];
  }
  ClpLp::Value ClpLp::_getPrimalValue() const {
    return _prob->objectiveValue();
  }

  ClpLp::Value ClpLp::_getDual(int i) const {
    return _prob->dualRowSolution()[i];
  }

  ClpLp::Value ClpLp::_getPrimalRay(int i) const {
    if (!_primal_ray) {
      _primal_ray = _prob->unboundedRay();
      LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided");
    }
    return _primal_ray[i];
  }

  ClpLp::Value ClpLp::_getDualRay(int i) const {
    if (!_dual_ray) {
      _dual_ray = _prob->infeasibilityRay();
      LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided");
    }
    return _dual_ray[i];
  }

  ClpLp::VarStatus ClpLp::_getColStatus(int i) const {
    switch (_prob->getColumnStatus(i)) {
    case ClpSimplex::basic:
      return BASIC;
    case ClpSimplex::isFree:
      return FREE;
    case ClpSimplex::atUpperBound:
      return UPPER;
    case ClpSimplex::atLowerBound:
      return LOWER;
    case ClpSimplex::isFixed:
      return FIXED;
    case ClpSimplex::superBasic:
      return FREE;
    default:
      LEMON_ASSERT(false, "Wrong column status");
      return VarStatus();
    }
  }

  ClpLp::VarStatus ClpLp::_getRowStatus(int i) const {
    switch (_prob->getColumnStatus(i)) {
    case ClpSimplex::basic:
      return BASIC;
    case ClpSimplex::isFree:
      return FREE;
    case ClpSimplex::atUpperBound:
      return UPPER;
    case ClpSimplex::atLowerBound:
      return LOWER;
    case ClpSimplex::isFixed:
      return FIXED;
    case ClpSimplex::superBasic:
      return FREE;
    default:
      LEMON_ASSERT(false, "Wrong row status");
      return VarStatus();
    }
  }


  ClpLp::ProblemType ClpLp::_getPrimalType() const {
    if (_prob->isProvenOptimal()) {
      return OPTIMAL;
    } else if (_prob->isProvenPrimalInfeasible()) {
      return INFEASIBLE;
    } else if (_prob->isProvenDualInfeasible()) {
      return UNBOUNDED;
    } else {
      return UNDEFINED;
    }
  }

  ClpLp::ProblemType ClpLp::_getDualType() const {
    if (_prob->isProvenOptimal()) {
      return OPTIMAL;
    } else if (_prob->isProvenDualInfeasible()) {
      return INFEASIBLE;
    } else if (_prob->isProvenPrimalInfeasible()) {
      return INFEASIBLE;
    } else {
      return UNDEFINED;
    }
  }

  void ClpLp::_setSense(ClpLp::Sense sense) {
    switch (sense) {
    case MIN:
      _prob->setOptimizationDirection(1);
      break;
    case MAX:
      _prob->setOptimizationDirection(-1);
      break;
    }
  }

  ClpLp::Sense ClpLp::_getSense() const {
    double dir = _prob->optimizationDirection();
    if (dir > 0.0) {
      return MIN;
    } else {
      return MAX;
    }
  }

  void ClpLp::_clear() {
    delete _prob;
    _prob = new ClpSimplex();
    rows.clear();
    cols.clear();
    _col_names_ref.clear();
    _clear_temporals();
  }

  void ClpLp::messageLevel(MessageLevel m) {
    _prob->setLogLevel(static_cast<int>(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

lemon/clp.h

Show inline comments

 		/* -*- mode: C++; indent-tabs-mode: nil; -*-
+		 *
 		 * This file is a part of LEMON, a generic C++ optimization library.
+		 *
 		 * Copyright (C) 2003-2008
 		 * Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
 		 * (Egervary Research Group on Combinatorial Optimization, EGRES).
+		 *
 		 * Permission to use, modify and distribute this software is granted
 		 * provided that this copyright notice appears in all copies. For
 		 * precise terms see the accompanying LICENSE file.
+		 *
 		 * This software is provided "AS IS" with no warranty of any kind,
 		 * express or implied, and with no claim as to its suitability for any
 		 * purpose.
+		 *
 		 */
 		#ifndef LEMON_CLP_H
 		#define LEMON_CLP_H
 		///\file
 		///\brief Header of the LEMON-CLP lp solver interface.
 		#include <vector>
 		#include <string>
 		#include <lemon/lp_base.h>
 		class ClpSimplex;
 		namespace lemon {
 		  /// \ingroup lp_group
 		  ///
 		  /// \brief Interface for the CLP solver
 		  ///
 		  /// This class implements an interface for the Clp LP solver.  The
 		  /// Clp library is an object oriented lp solver library developed at
 		  /// the IBM. The CLP is part of the COIN-OR package and it can be
 		  /// used with Common Public License.
 		  class ClpLp : public LpSolver {
 		  protected:
 		    ClpSimplex* _prob;
 		    std::map<std::string, int> _col_names_ref;
 		    std::map<std::string, int> _row_names_ref;
 		  public:
 		    /// \e
 		    ClpLp();
 		    /// \e
 		    ClpLp(const ClpLp&);
 		    /// \e
 		    ~ClpLp();
 		    /// \e
 		    virtual ClpLp* newSolver() const;
 		    /// \e
 		    virtual ClpLp* cloneSolver() const;
 		  protected:
 		    mutable double* _primal_ray;
 		    mutable double* _dual_ray;
 		    void _init_temporals();
 		    void _clear_temporals();
 		  protected:
 		    virtual const char* _solverName() const;
 		    virtual int _addCol();
 		    virtual int _addRow();
 		    virtual void _eraseCol(int i);
 		    virtual void _eraseRow(int i);
 		    virtual void _eraseColId(int i);
 		    virtual void _eraseRowId(int i);
 		    virtual void _getColName(int col, std::string& name) const;
 		    virtual void _setColName(int col, const std::string& name);
 		    virtual int _colByName(const std::string& name) const;
 		    virtual void _getRowName(int row, std::string& name) const;
 		    virtual void _setRowName(int row, const std::string& name);
 		    virtual int _rowByName(const std::string& name) const;
 		    virtual void _setRowCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getRowCoeffs(int i, InsertIterator b) const;
 		    virtual void _setColCoeffs(int i, ExprIterator b, ExprIterator e);
 		    virtual void _getColCoeffs(int i, InsertIterator b) const;
 		    virtual void _setCoeff(int row, int col, Value value);
 		    virtual Value _getCoeff(int row, int col) const;
 		    virtual void _setColLowerBound(int i, Value value);
 		    virtual Value _getColLowerBound(int i) const;
 		    virtual void _setColUpperBound(int i, Value value);
 		    virtual Value _getColUpperBound(int i) const;
 		    virtual void _setRowLowerBound(int i, Value value);
 		    virtual Value _getRowLowerBound(int i) const;
 		    virtual void _setRowUpperBound(int i, Value value);
 		    virtual Value _getRowUpperBound(int i) const;
 		    virtual void _setObjCoeffs(ExprIterator, ExprIterator);
 		    virtual void _getObjCoeffs(InsertIterator) const;
 		    virtual void _setObjCoeff(int i, Value obj_coef);
 		    virtual Value _getObjCoeff(int i) const;
 		    virtual void _setSense(Sense sense);
 		    virtual Sense _getSense() const;
 		    virtual SolveExitStatus _solve();
 		    virtual Value _getPrimal(int i) const;
 		    virtual Value _getDual(int i) const;
 		    virtual Value _getPrimalValue() const;
 		    virtual Value _getPrimalRay(int i) const;
 		    virtual Value _getDualRay(int i) const;
 		    virtual VarStatus _getColStatus(int i) const;
 		    virtual VarStatus _getRowStatus(int i) const;
 		    virtual ProblemType _getPrimalType() const;
 		    virtual ProblemType _getDualType() const;
 		    virtual void _clear();
 		    virtual void _messageLevel(MessageLevel);
 		  public:
 		    ///Solves LP with primal simplex method.
 		    SolveExitStatus solvePrimal();
 		    ///Solves LP with dual simplex method.
 		    SolveExitStatus solveDual();
 		    ///Solves LP with barrier method.
 		    SolveExitStatus solveBarrier();
 		    ///Returns the constraint identifier understood by CLP.
 		    int clpRow(Row r) const { return rows(id(r)); }
 		    ///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
 		#endif //LEMON_CLP_H

lemon/concepts/digraph.h

Show inline comments

@@ -40,448 +40,449 @@
 		    ///
 		    /// Note that actual digraph implementation like @ref ListDigraph or
 		    /// @ref SmartDigraph may have several additional functionality.
 		    ///
 		    /// \sa concept
 		    class Digraph {
 		    private:
 		      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
 		      ///Digraphs are \e not copy constructible. Use DigraphCopy() instead.
 		      ///
 		      Digraph(const Digraph &) {};
 		      ///\brief Assignment of \ref Digraph "Digraph"s to another ones are
 		      ///\e not allowed. Use DigraphCopy() instead.
 		      ///Assignment of \ref Digraph "Digraph"s to another ones are
 		      ///\e not allowed.  Use DigraphCopy() instead.
 		      void operator=(const Digraph &) {}
 		    public:
 		      ///\e
 		      /// Defalult constructor.
 		      /// Defalult constructor.
 		      ///
 		      Digraph() { }
 		      /// Class for identifying a node of the digraph
 		      /// This class identifies a node of the digraph. It also serves
 		      /// as a base class of the node iterators,
 		      /// thus they will convert to this type.
 		      class Node {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        Node() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Node(const Node&) { }
 		        /// Invalid constructor \& conversion.
 		        /// This constructor initializes the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        Node(Invalid) { }
 		        /// Equality operator
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are invalid.
 		        bool operator==(Node) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Node n)
 		        ///
 		        bool operator!=(Node) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of digraph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        ///
 		        /// \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<(Node) const { return false; }
 		      };
 		      /// This iterator goes through each node.
 		      /// This iterator goes through each node.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of nodes in digraph \c g of type \c Digraph like this:
 		      ///\code
 		      /// int count=0;
 		      /// for (Digraph::NodeIt n(g); n!=INVALID; ++n) ++count;
 		      ///\endcode
 		      class NodeIt : public Node {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        NodeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        NodeIt(const NodeIt& n) : Node(n) { }
 		        /// Invalid constructor \& conversion.
 		        /// Initialize the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        NodeIt(Invalid) { }
 		        /// Sets the iterator to the first node.
 		        /// Sets the iterator to the first node of \c g.
 		        ///
 		        NodeIt(const Digraph&) { }
 		        /// Node -> NodeIt conversion.
 		        /// Sets the iterator to the node of \c the digraph pointed by
 		        /// the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        NodeIt(const Digraph&, const Node&) { }
 		        /// Next node.
 		        /// Assign the iterator to the next node.
 		        ///
 		        NodeIt& operator++() { return *this; }
 		      };
 		      /// Class for identifying an arc of the digraph
 		      /// This class identifies an arc of the digraph. It also serves
 		      /// as a base class of the arc iterators,
 		      /// thus they will convert to this type.
 		      class Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        Arc() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Arc(const Arc&) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        Arc(Invalid) { }
 		        /// Equality operator
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are invalid.
 		        bool operator==(Arc) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Arc n)
 		        ///
 		        bool operator!=(Arc) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of digraph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        ///
 		        /// \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<(Arc) const { return false; }
 		      };
 		      /// This iterator goes trough the outgoing arcs of a node.
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in digraph \c g of type \c Digraph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for (Digraph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class OutArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        OutArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        OutArcIt(const OutArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        OutArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first outgoing arc.
 		        /// This constructor sets the iterator to the first outgoing arc of
 		        /// the node.
 		        OutArcIt(const Digraph&, const Node&) { }
 		        /// Arc -> OutArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        OutArcIt(const Digraph&, const Arc&) { }
 		        ///Next outgoing arc
 		        /// Assign the iterator to the next
 		        /// outgoing arc of the corresponding node.
 		        OutArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes trough the incoming arcs of a node.
 		      /// This iterator goes trough the \e incoming arcs of a certain node
 		      /// of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in digraph \c g of type \c Digraph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for(Digraph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class InArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        InArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        InArcIt(const InArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        InArcIt(Invalid) { }
 		        /// This constructor sets the iterator to first incoming arc.
 		        /// This constructor set the iterator to the first incoming arc of
 		        /// the node.
 		        InArcIt(const Digraph&, const Node&) { }
 		        /// Arc -> InArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        InArcIt(const Digraph&, const Arc&) { }
 		        /// Next incoming arc
 		        /// Assign the iterator to the next inarc of the corresponding node.
 		        ///
 		        InArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes through each arc.
 		      /// This iterator goes through each arc of a digraph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of arcs in a digraph \c g of type \c Digraph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Digraph::ArcIt e(g); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class ArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        ArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        ArcIt(const ArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        ArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first arc.
 		        /// This constructor sets the iterator to the first arc of \c g.
 		        ///@param g the digraph
 		        ArcIt(const Digraph& g) { ignore_unused_variable_warning(g); }
 		        /// Arc -> ArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        ArcIt(const Digraph&, const Arc&) { }
 		        ///Next arc
 		        /// Assign the iterator to the next arc.
 		        ArcIt& operator++() { return *this; }
 		      };
 		      ///Gives back the target node of an arc.
 		      ///Gives back the target node of an arc.
 		      ///
 		      Node target(Arc) const { return INVALID; }
 		      ///Gives back the source node of an arc.
 		      ///Gives back the source node of an arc.
 		      ///
 		      Node source(Arc) const { return INVALID; }
 		      /// \brief Returns the ID of the node.
 		      int id(Node) const { return -1; }
 		      /// \brief Returns the ID of the arc.
 		      int id(Arc) const { return -1; }
 		      /// \brief Returns the node with the given ID.
 		      ///
 		      /// \pre The argument should be a valid node ID in the graph.
 		      Node nodeFromId(int) const { return INVALID; }
 		      /// \brief Returns the arc with the given ID.
 		      ///
 		      /// \pre The argument should be a valid arc ID in the graph.
 		      Arc arcFromId(int) const { return INVALID; }
 		      /// \brief Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
 		      /// \brief Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      void first(Node&) const {}
 		      void next(Node&) const {}
 		      void first(Arc&) const {}
 		      void next(Arc&) const {}
 		      void firstIn(Arc&, const Node&) const {}
 		      void nextIn(Arc&) const {}
 		      void firstOut(Arc&, const Node&) const {}
 		      void nextOut(Arc&) const {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
 		      /// \brief The base node of the iterator.
 		      ///
 		      /// Gives back the base node of the iterator.
 		      /// It is always the target 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.
 		      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.
 		      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.
 		      Node runningNode(const OutArcIt&) const { return INVALID; }
 		      /// \brief The opposite node on the given arc.
 		      ///
 		      /// 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 T>
-		      class NodeMap : public ReadWriteMap< Node, T > {
+		      class NodeMap : public ReferenceMap<Node, T, T&, const T&> {
 		      public:
 		        ///\e
 		        NodeMap(const Digraph&) { }
 		        ///\e
 		        NodeMap(const Digraph&, T) { }
 		      private:
 		        ///Copy constructor
-		        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
 		        NodeMap(const NodeMap& nm) :
 		          ReferenceMap<Node, T, T&, const T&>(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };
-		      /// \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 T>
-		      class ArcMap : public ReadWriteMap<Arc,T> {
+		      class ArcMap : public ReferenceMap<Arc, T, T&, const T&> {
 		      public:
 		        ///\e
 		        ArcMap(const Digraph&) { }
 		        ///\e
 		        ArcMap(const Digraph&, T) { }
 		      private:
 		        ///Copy constructor
-		        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
 		        ArcMap(const ArcMap& em) :
 		          ReferenceMap<Arc, T, T&, const T&>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      template <typename _Digraph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<BaseDigraphComponent, _Digraph>();
 		          checkConcept<IterableDigraphComponent<>, _Digraph>();
 		          checkConcept<IDableDigraphComponent<>, _Digraph>();
 		          checkConcept<MappableDigraphComponent<>, _Digraph>();
+		        }
 		      };
 		    };
 		  } //namespace concepts
 		} //namespace lemon
 		#endif

lemon/concepts/graph.h

Show inline comments

@@ -116,648 +116,649 @@
 		        /// To allow the use of graph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        ///
 		        /// \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<(Node) const { return false; }
 		      };
 		      /// This iterator goes through each node.
 		      /// This iterator goes through each node.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of nodes in graph \c g of type \c Graph like this:
 		      ///\code
 		      /// int count=0;
 		      /// for (Graph::NodeIt n(g); n!=INVALID; ++n) ++count;
 		      ///\endcode
 		      class NodeIt : public Node {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        NodeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        NodeIt(const NodeIt& n) : Node(n) { }
 		        /// Invalid constructor \& conversion.
 		        /// Initialize the iterator to be invalid.
 		        /// \sa Invalid for more details.
 		        NodeIt(Invalid) { }
 		        /// Sets the iterator to the first node.
 		        /// Sets the iterator to the first node of \c g.
 		        ///
 		        NodeIt(const Graph&) { }
 		        /// Node -> NodeIt conversion.
 		        /// Sets the iterator to the node of \c the graph pointed by
 		        /// the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        NodeIt(const Graph&, const Node&) { }
 		        /// Next node.
 		        /// Assign the iterator to the next node.
 		        ///
 		        NodeIt& operator++() { return *this; }
 		      };
 		      /// The base type of the edge iterators.
 		      /// The base type of the edge iterators.
 		      ///
 		      class Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        Edge() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Edge(const Edge&) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        Edge(Invalid) { }
 		        /// Equality operator
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are invalid.
 		        bool operator==(Edge) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Edge n)
 		        ///
 		        bool operator!=(Edge) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of graph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        ///
 		        /// \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<(Edge) const { return false; }
 		      };
 		      /// This iterator goes through each edge.
 		      /// This iterator goes through each edge of a graph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of edges in a graph \c g of type \c Graph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::EdgeIt e(g); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class EdgeIt : public Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        EdgeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        EdgeIt(const EdgeIt& e) : Edge(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        EdgeIt(Invalid) { }
 		        /// This constructor sets the iterator to the first edge.
 		        /// This constructor sets the iterator to the first edge.
 		        EdgeIt(const Graph&) { }
 		        /// Edge -> EdgeIt conversion
 		        /// Sets the iterator to the value of the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the edge-set, the iteration order is the
 		        /// same.
 		        EdgeIt(const Graph&, const Edge&) { }
 		        /// Next edge
 		        /// Assign the iterator to the next edge.
 		        EdgeIt& operator++() { return *this; }
 		      };
 		      /// \brief This iterator goes trough the incident undirected
 		      /// arcs of a node.
 		      ///
 		      /// This iterator goes trough the incident edges
 		      /// of a certain node of a graph. You should assume that the
 		      /// loop arcs will be iterated twice.
 		      ///
 		      /// Its usage is quite simple, for example you can compute the
 		      /// degree (i.e. count the number of incident arcs of a node \c n
 		      /// in graph \c g of type \c Graph as follows.
 		      ///
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::IncEdgeIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class IncEdgeIt : public Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        IncEdgeIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        IncEdgeIt(const IncEdgeIt& e) : Edge(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        IncEdgeIt(Invalid) { }
 		        /// This constructor sets the iterator to first incident arc.
 		        /// This constructor set the iterator to the first incident arc of
 		        /// the node.
 		        IncEdgeIt(const Graph&, const Node&) { }
 		        /// Edge -> IncEdgeIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        IncEdgeIt(const Graph&, const Edge&) { }
 		        /// Next incident arc
 		        /// Assign the iterator to the next incident arc
 		        /// of the corresponding node.
 		        IncEdgeIt& operator++() { return *this; }
 		      };
 		      /// The directed arc type.
 		      /// The directed arc type. It can be converted to the
 		      /// edge or it should be inherited from the undirected
 		      /// arc.
 		      class Arc : public Edge {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        Arc() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        Arc(const Arc& e) : Edge(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        Arc(Invalid) { }
 		        /// Equality operator
 		        /// Two iterators are equal if and only if they point to the
 		        /// same object or both are invalid.
 		        bool operator==(Arc) const { return true; }
 		        /// Inequality operator
 		        /// \sa operator==(Arc n)
 		        ///
 		        bool operator!=(Arc) const { return true; }
 		        /// Artificial ordering operator.
 		        /// To allow the use of graph descriptors as key type in std::map or
 		        /// similar associative container we require this.
 		        ///
 		        /// \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<(Arc) const { return false; }
 		      };
 		      /// This iterator goes through each directed arc.
 		      /// This iterator goes through each arc of a graph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of arcs in a graph \c g of type \c Graph as follows:
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::ArcIt e(g); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class ArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        ArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        ArcIt(const ArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        ArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first arc.
 		        /// This constructor sets the iterator to the first arc of \c g.
 		        ///@param g the graph
 		        ArcIt(const Graph &g) { ignore_unused_variable_warning(g); }
 		        /// Arc -> ArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        ArcIt(const Graph&, const Arc&) { }
 		        ///Next arc
 		        /// Assign the iterator to the next arc.
 		        ArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes trough the outgoing directed arcs of a node.
 		      /// This iterator goes trough the \e outgoing arcs of a certain node
 		      /// of a graph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in graph \c g of type \c Graph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for (Graph::OutArcIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class OutArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        OutArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        OutArcIt(const OutArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        OutArcIt(Invalid) { }
 		        /// This constructor sets the iterator to the first outgoing arc.
 		        /// This constructor sets the iterator to the first outgoing arc of
 		        /// the node.
 		        ///@param n the node
 		        ///@param g the graph
 		        OutArcIt(const Graph& n, const Node& g) {
 		          ignore_unused_variable_warning(n);
 		          ignore_unused_variable_warning(g);
+		        }
 		        /// Arc -> OutArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        OutArcIt(const Graph&, const Arc&) { }
 		        ///Next outgoing arc
 		        /// Assign the iterator to the next
 		        /// outgoing arc of the corresponding node.
 		        OutArcIt& operator++() { return *this; }
 		      };
 		      /// This iterator goes trough the incoming directed arcs of a node.
 		      /// This iterator goes trough the \e incoming arcs of a certain node
 		      /// of a graph.
 		      /// Its usage is quite simple, for example you can count the number
 		      /// of outgoing arcs of a node \c n
 		      /// in graph \c g of type \c Graph as follows.
 		      ///\code
 		      /// int count=0;
 		      /// for(Graph::InArcIt e(g, n); e!=INVALID; ++e) ++count;
 		      ///\endcode
 		      class InArcIt : public Arc {
 		      public:
 		        /// Default constructor
 		        /// @warning The default constructor sets the iterator
 		        /// to an undefined value.
 		        InArcIt() { }
 		        /// Copy constructor.
 		        /// Copy constructor.
 		        ///
 		        InArcIt(const InArcIt& e) : Arc(e) { }
 		        /// Initialize the iterator to be invalid.
 		        /// Initialize the iterator to be invalid.
 		        ///
 		        InArcIt(Invalid) { }
 		        /// This constructor sets the iterator to first incoming arc.
 		        /// This constructor set the iterator to the first incoming arc of
 		        /// the node.
 		        ///@param n the node
 		        ///@param g the graph
 		        InArcIt(const Graph& g, const Node& n) {
 		          ignore_unused_variable_warning(n);
 		          ignore_unused_variable_warning(g);
+		        }
 		        /// Arc -> InArcIt conversion
 		        /// Sets the iterator to the value of the trivial iterator \c e.
 		        /// This feature necessitates that each time we
 		        /// iterate the arc-set, the iteration order is the same.
 		        InArcIt(const Graph&, const Arc&) { }
 		        /// Next incoming arc
 		        /// Assign the iterator to the next inarc of the corresponding node.
 		        ///
 		        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 T>
-		      class NodeMap : public ReadWriteMap< Node, T >
+		      class NodeMap : public ReferenceMap<Node, T, T&, const T&>
+		      {
 		      public:
 		        ///\e
 		        NodeMap(const Graph&) { }
 		        ///\e
 		        NodeMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
-		        NodeMap(const NodeMap& nm) : ReadWriteMap< Node, T >(nm) { }
 		        NodeMap(const NodeMap& nm) :
 		          ReferenceMap<Node, T, T&, const T&>(nm) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        NodeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Node, T>, CMap>();
 		          return *this;
+		        }
 		      };
-		      /// \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 T>
-		      class ArcMap : public ReadWriteMap<Arc,T>
+		      class ArcMap : public ReferenceMap<Arc, T, T&, const T&>
+		      {
 		      public:
 		        ///\e
 		        ArcMap(const Graph&) { }
 		        ///\e
 		        ArcMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
-		        ArcMap(const ArcMap& em) : ReadWriteMap<Arc,T>(em) { }
 		        ArcMap(const ArcMap& em) :
 		          ReferenceMap<Arc, T, T&, const T&>(em) { }
 		        ///Assignment operator
 		        template <typename CMap>
 		        ArcMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Arc, T>, CMap>();
 		          return *this;
+		        }
 		      };
-		      /// 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 T>
-		      class EdgeMap : public ReadWriteMap<Edge,T>
+		      class EdgeMap : public ReferenceMap<Edge, T, T&, const T&>
+		      {
 		      public:
 		        ///\e
 		        EdgeMap(const Graph&) { }
 		        ///\e
 		        EdgeMap(const Graph&, T) { }
 		      private:
 		        ///Copy constructor
-		        EdgeMap(const EdgeMap& em) : ReadWriteMap<Edge,T>(em) {}
 		        EdgeMap(const EdgeMap& em) :
 		          ReferenceMap<Edge, T, T&, const T&>(em) {}
 		        ///Assignment operator
 		        template <typename CMap>
 		        EdgeMap& operator=(const CMap&) {
 		          checkConcept<ReadMap<Edge, T>, CMap>();
 		          return *this;
+		        }
 		      };
 		      /// \brief Direct the given edge.
 		      ///
 		      /// Direct the given edge. The returned arc source
 		      /// will be the given node.
 		      Arc direct(const Edge&, const Node&) const {
 		        return INVALID;
+		      }
 		      /// \brief Direct the given edge.
 		      ///
 		      /// Direct the given edge. The returned arc
 		      /// represents the given edge and the direction comes
 		      /// from the bool parameter. The source of the edge and
 		      /// the directed arc is the same when the given bool is true.
 		      Arc direct(const Edge&, bool) const {
 		        return INVALID;
+		      }
 		      /// \brief Returns true if the arc has default orientation.
 		      ///
 		      /// Returns whether the given directed arc is same orientation as
 		      /// the corresponding edge's default orientation.
 		      bool direction(Arc) const { return true; }
 		      /// \brief Returns the opposite directed arc.
 		      ///
 		      /// Returns the opposite directed arc.
 		      Arc oppositeArc(Arc) const { return INVALID; }
 		      /// \brief Opposite node on an arc
 		      ///
 		      /// \return The opposite of the given node on the given edge.
 		      Node oppositeNode(Node, Edge) const { return INVALID; }
 		      /// \brief First node of the edge.
 		      ///
 		      /// \return The first node of the given edge.
 		      ///
 		      /// Naturally edges don't have direction and thus
 		      /// don't have source and target node. However we use \c u() and \c v()
 		      /// methods to query the two nodes of the arc. The direction of the
 		      /// arc which arises this way is called the inherent direction of the
 		      /// edge, and is used to define the "default" direction
 		      /// of the directed versions of the arcs.
 		      /// \sa v()
 		      /// \sa direction()
 		      Node u(Edge) const { return INVALID; }
 		      /// \brief Second node of the edge.
 		      ///
 		      /// \return The second node of the given edge.
 		      ///
 		      /// Naturally edges don't have direction and thus
 		      /// don't have source and target node. However we use \c u() and \c v()
 		      /// methods to query the two nodes of the arc. The direction of the
 		      /// arc which arises this way is called the inherent direction of the
 		      /// edge, and is used to define the "default" direction
 		      /// of the directed versions of the arcs.
 		      /// \sa u()
 		      /// \sa direction()
 		      Node v(Edge) const { return INVALID; }
 		      /// \brief Source node of the directed arc.
 		      Node source(Arc) const { return INVALID; }
 		      /// \brief Target node of the directed arc.
 		      Node target(Arc) const { return INVALID; }
 		      /// \brief Returns the id of the node.
 		      int id(Node) const { return -1; }
 		      /// \brief Returns the id of the edge.
 		      int id(Edge) const { return -1; }
 		      /// \brief Returns the id of the arc.
 		      int id(Arc) const { return -1; }
 		      /// \brief Returns the node with the given id.
 		      ///
 		      /// \pre The argument should be a valid node id in the graph.
 		      Node nodeFromId(int) const { return INVALID; }
 		      /// \brief Returns the edge with the given id.
 		      ///
 		      /// \pre The argument should be a valid edge id in the graph.
 		      Edge edgeFromId(int) const { return INVALID; }
 		      /// \brief Returns the arc with the given id.
 		      ///
 		      /// \pre The argument should be a valid arc id in the graph.
 		      Arc arcFromId(int) const { return INVALID; }
 		      /// \brief Returns an upper bound on the node IDs.
 		      int maxNodeId() const { return -1; }
 		      /// \brief Returns an upper bound on the edge IDs.
 		      int maxEdgeId() const { return -1; }
 		      /// \brief Returns an upper bound on the arc IDs.
 		      int maxArcId() const { return -1; }
 		      void first(Node&) const {}
 		      void next(Node&) const {}
 		      void first(Edge&) const {}
 		      void next(Edge&) const {}
 		      void first(Arc&) const {}
 		      void next(Arc&) const {}
 		      void firstOut(Arc&, Node) const {}
 		      void nextOut(Arc&) const {}
 		      void firstIn(Arc&, Node) const {}
 		      void nextIn(Arc&) const {}
 		      void firstInc(Edge &, bool &, const Node &) const {}
 		      void nextInc(Edge &, bool &) const {}
 		      // The second parameter is dummy.
 		      Node fromId(int, Node) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Edge fromId(int, Edge) const { return INVALID; }
 		      // The second parameter is dummy.
 		      Arc fromId(int, Arc) const { return INVALID; }
 		      // Dummy parameter.
 		      int maxId(Node) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Edge) const { return -1; }
 		      // Dummy parameter.
 		      int maxId(Arc) const { return -1; }
 		      /// \brief Base node of the iterator
 		      ///
 		      /// Returns the base node (the source in this case) of the iterator
 		      Node baseNode(OutArcIt e) const {
 		        return source(e);
+		      }
 		      /// \brief Running node of the iterator
 		      ///
 		      /// Returns the running node (the target in this case) of the
 		      /// iterator
 		      Node runningNode(OutArcIt e) const {
 		        return target(e);
+		      }
 		      /// \brief Base node of the iterator
 		      ///
 		      /// Returns the base node (the target in this case) of the iterator
 		      Node baseNode(InArcIt e) const {
 		        return target(e);
+		      }
 		      /// \brief Running node of the iterator
 		      ///
 		      /// Returns the running node (the source in this case) of the
 		      /// iterator
 		      Node runningNode(InArcIt e) const {
 		        return source(e);
+		      }
 		      /// \brief Base node of the iterator
 		      ///
 		      /// Returns the base node of the iterator
 		      Node baseNode(IncEdgeIt) const {
 		        return INVALID;
+		      }
 		      /// \brief Running node of the iterator
 		      ///
 		      /// Returns the running node of the iterator
 		      Node runningNode(IncEdgeIt) const {
 		        return INVALID;
+		      }
 		      template <typename _Graph>
 		      struct Constraints {
 		        void constraints() {
 		          checkConcept<BaseGraphComponent, _Graph>();
 		          checkConcept<IterableGraphComponent<>, _Graph>();
 		          checkConcept<IDableGraphComponent<>, _Graph>();
 		          checkConcept<MappableGraphComponent<>, _Graph>();
+		        }
 		      };
 		    };
+		  }
+		}
 		#endif

Changeset was too big and was cut off... Show full diff

0 comments (0 inline)

RhodeCode

Login to your account

Changeset was too big and was cut off... Show full diff

Changeset was too big and was cut off... Show full diff

1	1	/* -- mode: C++; indent-tabs-mode: nil; --
2	2	*
3	3	* This file is a part of LEMON, a generic C++ optimization library.
4	4	*
5	5	* Copyright (C) 2003-2008
6	6	* Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
7	7	* (Egervary Research Group on Combinatorial Optimization, EGRES).
8	8	*
9	9	* Permission to use, modify and distribute this software is granted
10	10	* provided that this copyright notice appears in all copies. For
11	11	* precise terms see the accompanying LICENSE file.
12	12	*
13	13	* This software is provided "AS IS" with no warranty of any kind,
14	14	* express or implied, and with no claim as to its suitability for any
15	15	* purpose.
16	16	*
17	17	*/
18	18
19	19	#include <lemon/clp.h>
20	20	#include <coin/ClpSimplex.hpp>
21	21
22	22	namespace lemon {
23	23
24	24	ClpLp::ClpLp() {
25	25	_prob = new ClpSimplex();
26	26	_init_temporals();
27		messageLevel(~~MESSAGE_NO_OUTPUT~~);
	27	messageLevel(MESSAGE_NOTHING);
28	28	}
29	29
30	30	ClpLp::ClpLp(const ClpLp& other) {
31	31	_prob = new ClpSimplex(*other._prob);
32	32	rows = other.rows;
33	33	cols = other.cols;
34	34	_init_temporals();
35		messageLevel(~~MESSAGE_NO_OUTPUT~~);
	35	messageLevel(MESSAGE_NOTHING);
36	36	}
37	37
38	38	ClpLp::~ClpLp() {
39	39	delete _prob;
40	40	_clear_temporals();
41	41	}
42	42
43	43	void ClpLp::_init_temporals() {
44	44	_primal_ray = 0;
45	45	_dual_ray = 0;
46	46	}
47	47
48	48	void ClpLp::_clear_temporals() {
49	49	if (_primal_ray) {
50	50	delete[] _primal_ray;
51	51	_primal_ray = 0;
52	52	}
53	53	if (_dual_ray) {
54	54	delete[] _dual_ray;
55	55	_dual_ray = 0;
56	56	}
57	57	}
58	58
59	59	ClpLp* ClpLp::newSolver() const {
60	60	ClpLp* newlp = new ClpLp;
61	61	return newlp;
62	62	}
63	63
64	64	ClpLp* ClpLp::cloneSolver() const {
65	65	ClpLp* copylp = new ClpLp(*this);
66	66	return copylp;
67	67	}
68	68
69	69	const char* ClpLp::_solverName() const { return "ClpLp"; }
70	70
71	71	int ClpLp::_addCol() {
72	72	_prob->addColumn(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX, 0.0);
73	73	return _prob->numberColumns() - 1;
74	74	}
75	75
76	76	int ClpLp::_addRow() {
77	77	_prob->addRow(0, 0, 0, -COIN_DBL_MAX, COIN_DBL_MAX);
78	78	return _prob->numberRows() - 1;
79	79	}
80	80
81	81
82	82	void ClpLp::_eraseCol(int c) {
83	83	_col_names_ref.erase(_prob->getColumnName(c));
84	84	_prob->deleteColumns(1, &c);
85	85	}
86	86
87	87	void ClpLp::_eraseRow(int r) {
88	88	_row_names_ref.erase(_prob->getRowName(r));
89	89	_prob->deleteRows(1, &r);
90	90	}
91	91
92	92	void ClpLp::_eraseColId(int i) {
93	93	cols.eraseIndex(i);
94	94	cols.shiftIndices(i);
95	95	}
96	96
97	97	void ClpLp::_eraseRowId(int i) {
98	98	rows.eraseIndex(i);
99	99	rows.shiftIndices(i);
100	100	}
101	101
102	102	void ClpLp::_getColName(int c, std::string& name) const {
103	103	name = _prob->getColumnName(c);
104	104	}
105	105
106	106	void ClpLp::_setColName(int c, const std::string& name) {
107	107	_prob->setColumnName(c, const_cast<std::string&>(name));
108	108	_col_names_ref[name] = c;
109	109	}
110	110
111	111	int ClpLp::_colByName(const std::string& name) const {
112	112	std::map<std::string, int>::const_iterator it = _col_names_ref.find(name);
113	113	return it != _col_names_ref.end() ? it->second : -1;
114	114	}
115	115
116	116	void ClpLp::_getRowName(int r, std::string& name) const {
117	117	name = _prob->getRowName(r);
118	118	}
119	119
120	120	void ClpLp::_setRowName(int r, const std::string& name) {
121	121	_prob->setRowName(r, const_cast<std::string&>(name));
122	122	_row_names_ref[name] = r;
123	123	}
124	124
125	125	int ClpLp::_rowByName(const std::string& name) const {
126	126	std::map<std::string, int>::const_iterator it = _row_names_ref.find(name);
127	127	return it != _row_names_ref.end() ? it->second : -1;
128	128	}
129	129
130	130
131	131	void ClpLp::_setRowCoeffs(int ix, ExprIterator b, ExprIterator e) {
132	132	std::map<int, Value> coeffs;
133	133
134	134	int n = _prob->clpMatrix()->getNumCols();
135	135
136	136	const int* indices = _prob->clpMatrix()->getIndices();
137	137	const double* elements = _prob->clpMatrix()->getElements();
138	138
139	139	for (int i = 0; i < n; ++i) {
140	140	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
141	141	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
142	142
143	143	const int* it = std::lower_bound(indices + begin, indices + end, ix);
144	144	if (it != indices + end && *it == ix && elements[it - indices] != 0.0) {
145	145	coeffs[i] = 0.0;
146	146	}
147	147	}
148	148
149	149	for (ExprIterator it = b; it != e; ++it) {
150	150	coeffs[it->first] = it->second;
151	151	}
152	152
153	153	for (std::map<int, Value>::iterator it = coeffs.begin();
154	154	it != coeffs.end(); ++it) {
155	155	_prob->modifyCoefficient(ix, it->first, it->second);
156	156	}
157	157	}
158	158
159	159	void ClpLp::_getRowCoeffs(int ix, InsertIterator b) const {
160	160	int n = _prob->clpMatrix()->getNumCols();
161	161
162	162	const int* indices = _prob->clpMatrix()->getIndices();
163	163	const double* elements = _prob->clpMatrix()->getElements();
164	164
165	165	for (int i = 0; i < n; ++i) {
166	166	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[i];
167	167	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[i];
168	168
169	169	const int* it = std::lower_bound(indices + begin, indices + end, ix);
170	170	if (it != indices + end && *it == ix) {
171	171	*b = std::make_pair(i, elements[it - indices]);
172	172	}
173	173	}
174	174	}
175	175
176	176	void ClpLp::_setColCoeffs(int ix, ExprIterator b, ExprIterator e) {
177	177	std::map<int, Value> coeffs;
178	178
179	179	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
180	180	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
181	181
182	182	const int* indices = _prob->clpMatrix()->getIndices();
183	183	const double* elements = _prob->clpMatrix()->getElements();
184	184
185	185	for (CoinBigIndex i = begin; i != end; ++i) {
186	186	if (elements[i] != 0.0) {
187	187	coeffs[indices[i]] = 0.0;
188	188	}
189	189	}
190	190	for (ExprIterator it = b; it != e; ++it) {
191	191	coeffs[it->first] = it->second;
192	192	}
193	193	for (std::map<int, Value>::iterator it = coeffs.begin();
194	194	it != coeffs.end(); ++it) {
195	195	_prob->modifyCoefficient(it->first, ix, it->second);
196	196	}
197	197	}
198	198
199	199	void ClpLp::_getColCoeffs(int ix, InsertIterator b) const {
200	200	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
201	201	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
202	202
203	203	const int* indices = _prob->clpMatrix()->getIndices();
204	204	const double* elements = _prob->clpMatrix()->getElements();
205	205
206	206	for (CoinBigIndex i = begin; i != end; ++i) {
207	207	*b = std::make_pair(indices[i], elements[i]);
208	208	++b;
209	209	}
210	210	}
211	211
212	212	void ClpLp::_setCoeff(int ix, int jx, Value value) {
213	213	_prob->modifyCoefficient(ix, jx, value);
214	214	}
215	215
216	216	ClpLp::Value ClpLp::_getCoeff(int ix, int jx) const {
217	217	CoinBigIndex begin = _prob->clpMatrix()->getVectorStarts()[ix];
218	218	CoinBigIndex end = begin + _prob->clpMatrix()->getVectorLengths()[ix];
219	219
220	220	const int* indices = _prob->clpMatrix()->getIndices();
221	221	const double* elements = _prob->clpMatrix()->getElements();
222	222
223	223	const int* it = std::lower_bound(indices + begin, indices + end, jx);
224	224	if (it != indices + end && *it == jx) {
225	225	return elements[it - indices];
226	226	} else {
227	227	return 0.0;
228	228	}
229	229	}
230	230
231	231	void ClpLp::_setColLowerBound(int i, Value lo) {
232	232	_prob->setColumnLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
233	233	}
234	234
235	235	ClpLp::Value ClpLp::_getColLowerBound(int i) const {
236	236	double val = _prob->getColLower()[i];
237	237	return val == - COIN_DBL_MAX ? - INF : val;
238	238	}
239	239
240	240	void ClpLp::_setColUpperBound(int i, Value up) {
241	241	_prob->setColumnUpper(i, up == INF ? COIN_DBL_MAX : up);
242	242	}
243	243
244	244	ClpLp::Value ClpLp::_getColUpperBound(int i) const {
245	245	double val = _prob->getColUpper()[i];
246	246	return val == COIN_DBL_MAX ? INF : val;
247	247	}
248	248
249	249	void ClpLp::_setRowLowerBound(int i, Value lo) {
250	250	_prob->setRowLower(i, lo == - INF ? - COIN_DBL_MAX : lo);
251	251	}
252	252
253	253	ClpLp::Value ClpLp::_getRowLowerBound(int i) const {
254	254	double val = _prob->getRowLower()[i];
255	255	return val == - COIN_DBL_MAX ? - INF : val;
256	256	}
257	257
258	258	void ClpLp::_setRowUpperBound(int i, Value up) {
259	259	_prob->setRowUpper(i, up == INF ? COIN_DBL_MAX : up);
260	260	}
261	261
262	262	ClpLp::Value ClpLp::_getRowUpperBound(int i) const {
263	263	double val = _prob->getRowUpper()[i];
264	264	return val == COIN_DBL_MAX ? INF : val;
265	265	}
266	266
267	267	void ClpLp::_setObjCoeffs(ExprIterator b, ExprIterator e) {
268	268	int num = _prob->clpMatrix()->getNumCols();
269	269	for (int i = 0; i < num; ++i) {
270	270	_prob->setObjectiveCoefficient(i, 0.0);
271	271	}
272	272	for (ExprIterator it = b; it != e; ++it) {
273	273	_prob->setObjectiveCoefficient(it->first, it->second);
274	274	}
275	275	}
276	276
277	277	void ClpLp::_getObjCoeffs(InsertIterator b) const {
278	278	int num = _prob->clpMatrix()->getNumCols();
279	279	for (int i = 0; i < num; ++i) {
280	280	Value coef = _prob->getObjCoefficients()[i];
281	281	if (coef != 0.0) {
282	282	*b = std::make_pair(i, coef);
283	283	++b;
284	284	}
285	285	}
286	286	}
287	287
288	288	void ClpLp::_setObjCoeff(int i, Value obj_coef) {
289	289	_prob->setObjectiveCoefficient(i, obj_coef);
290	290	}
291	291
292	292	ClpLp::Value ClpLp::_getObjCoeff(int i) const {
293	293	return _prob->getObjCoefficients()[i];
294	294	}
295	295
296	296	ClpLp::SolveExitStatus ClpLp::_solve() {
297	297	return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
298	298	}
299	299
300	300	ClpLp::SolveExitStatus ClpLp::solvePrimal() {
301	301	return _prob->primal() >= 0 ? SOLVED : UNSOLVED;
302	302	}
303	303
304	304	ClpLp::SolveExitStatus ClpLp::solveDual() {
305	305	return _prob->dual() >= 0 ? SOLVED : UNSOLVED;
306	306	}
307	307
308	308	ClpLp::SolveExitStatus ClpLp::solveBarrier() {
309	309	return _prob->barrier() >= 0 ? SOLVED : UNSOLVED;
310	310	}
311	311
312	312	ClpLp::Value ClpLp::_getPrimal(int i) const {
313	313	return _prob->primalColumnSolution()[i];
314	314	}
315	315	ClpLp::Value ClpLp::_getPrimalValue() const {
316	316	return _prob->objectiveValue();
317	317	}
318	318
319	319	ClpLp::Value ClpLp::_getDual(int i) const {
320	320	return _prob->dualRowSolution()[i];
321	321	}
322	322
323	323	ClpLp::Value ClpLp::_getPrimalRay(int i) const {
324	324	if (!_primal_ray) {
325	325	_primal_ray = _prob->unboundedRay();
326	326	LEMON_ASSERT(_primal_ray != 0, "Primal ray is not provided");
327	327	}
328	328	return _primal_ray[i];
329	329	}
330	330
331	331	ClpLp::Value ClpLp::_getDualRay(int i) const {
332	332	if (!_dual_ray) {
333	333	_dual_ray = _prob->infeasibilityRay();
334	334	LEMON_ASSERT(_dual_ray != 0, "Dual ray is not provided");
335	335	}
336	336	return _dual_ray[i];
337	337	}
338	338
339	339	ClpLp::VarStatus ClpLp::_getColStatus(int i) const {
340	340	switch (_prob->getColumnStatus(i)) {
341	341	case ClpSimplex::basic:
342	342	return BASIC;
343	343	case ClpSimplex::isFree:
344	344	return FREE;
345	345	case ClpSimplex::atUpperBound:
346	346	return UPPER;
347	347	case ClpSimplex::atLowerBound:
348	348	return LOWER;
349	349	case ClpSimplex::isFixed:
350	350	return FIXED;
351	351	case ClpSimplex::superBasic:
352	352	return FREE;
353	353	default:
354	354	LEMON_ASSERT(false, "Wrong column status");
355	355	return VarStatus();
356	356	}
357	357	}
358	358
359	359	ClpLp::VarStatus ClpLp::_getRowStatus(int i) const {
360	360	switch (_prob->getColumnStatus(i)) {
361	361	case ClpSimplex::basic:
362	362	return BASIC;
363	363	case ClpSimplex::isFree:
364	364	return FREE;
365	365	case ClpSimplex::atUpperBound:
366	366	return UPPER;
367	367	case ClpSimplex::atLowerBound:
368	368	return LOWER;
369	369	case ClpSimplex::isFixed:
370	370	return FIXED;
371	371	case ClpSimplex::superBasic:
372	372	return FREE;
373	373	default:
374	374	LEMON_ASSERT(false, "Wrong row status");
375	375	return VarStatus();
376	376	}
377	377	}
378	378
379	379
380	380	ClpLp::ProblemType ClpLp::_getPrimalType() const {
381	381	if (_prob->isProvenOptimal()) {
382	382	return OPTIMAL;
383	383	} else if (_prob->isProvenPrimalInfeasible()) {
384	384	return INFEASIBLE;
385	385	} else if (_prob->isProvenDualInfeasible()) {
386	386	return UNBOUNDED;
387	387	} else {
388	388	return UNDEFINED;
389	389	}
390	390	}
391	391
392	392	ClpLp::ProblemType ClpLp::_getDualType() const {
393	393	if (_prob->isProvenOptimal()) {
394	394	return OPTIMAL;
395	395	} else if (_prob->isProvenDualInfeasible()) {
396	396	return INFEASIBLE;
397	397	} else if (_prob->isProvenPrimalInfeasible()) {
398	398	return INFEASIBLE;
399	399	} else {
400	400	return UNDEFINED;
401	401	}
402	402	}
403	403
404	404	void ClpLp::_setSense(ClpLp::Sense sense) {
405	405	switch (sense) {
406	406	case MIN:
407	407	_prob->setOptimizationDirection(1);
408	408	break;
409	409	case MAX:
410	410	_prob->setOptimizationDirection(-1);
411	411	break;
412	412	}
413	413	}
414	414
415	415	ClpLp::Sense ClpLp::_getSense() const {
416	416	double dir = _prob->optimizationDirection();
417	417	if (dir > 0.0) {
418	418	return MIN;
419	419	} else {
420	420	return MAX;
421	421	}
422	422	}
423	423
424	424	void ClpLp::_clear() {
425	425	delete _prob;
426	426	_prob = new ClpSimplex();
427	427	rows.clear();
428	428	cols.clear();
429	429	_col_names_ref.clear();
430	430	_clear_temporals();
431	431	}
432	432
433		void ClpLp::messageLevel(MessageLevel m) {
434		_prob->setLogLevel(static_cast<int>(m));
	433	void ClpLp::_messageLevel(MessageLevel level) {
	434	switch (level) {
	435	case MESSAGE_NOTHING:
	436	_prob->setLogLevel(0);
	437	break;
	438	case MESSAGE_ERROR:
	439	_prob->setLogLevel(1);
	440	break;
	441	case MESSAGE_WARNING:
	442	_prob->setLogLevel(2);
	443	break;
	444	case MESSAGE_NORMAL:
	445	_prob->setLogLevel(3);
	446	break;
	447	case MESSAGE_VERBOSE:
	448	_prob->setLogLevel(4);
	449	break;
	450	}
435	451	}
436	452
437	453	} //END OF NAMESPACE LEMON