- Boost - lists.boost.org

[STL/Algorithm]Addin Combination against std::permutation?
by 雄杰陈 05 Aug '06

05 Aug '06

Hi! I wrote a Combination which is against to std::permutation. It can enumerate all result of a combination, such as selecting 3 chars from "ABCDE", by `dictionary order'. It's just like the std::permutation. The code is published at http://www.bxmy.org/code/combination.cpp. And I wrote a article about this Combination Algorithm in Chinese, http://www.bxmy.org/article/combination.pdf. Also, the code can be found in the enclosure. The combination has at least three functions: combination_adjust: should be called for initialize the sequence; next_combination: get next combination, like next_permutation; prev_combination: get previous combination, like prev_permutation. This algorithm separates all elements into two parts. One is [first, middle), the elements selected in. Other is [middle, last), the elements selected out. The steps are: 1) find the first element `Pout' in [first, middle) which should be selected out. 2) find the first element `Qin' in [middle, last) which should be selected in. 3) iter_swap(Pout, Qin). 4) merge [Pout+1, middle) and [Qin+1, last). It's simple and compatible with std::permutation well. I hope that it can be add into the STL. They are couple. Thanks. Ben T. Bear

1 0

array_count - preliminary submission
by Gennaro Prota 05 Aug '06

05 Aug '06

Hi guys, attached is a first cut at the array count facility I proposed here. It still lacks compile-fail tests and tests for the multidimensional case; and I made no attempt to extend it to tr::array<> (the main issue being supporting tr::array<>s with size 0 --it can be done, but the machinery involved would be something to be likely hidden from the user via a macro; instead, no macro is used so far). Any feedback appreciated, though likely only Dave will be interested ;) The enclosed test file should be just compiled. It does nothing if actually run. -- [ Gennaro Prota, C++ developer for hire ] [ resume: available on request ] begin 644 array_count proposal v.0.1.zip M4$L#!`H``````-.<Z#0````````````````5````;&EB<R]G<'-?87)R87E? M8V]U;G0O4$L#!!0````(`)")Z#0!^SHOFP(``,4(```D````;&EB<R]G<'-? M87)R87E?8V]U;G0O87)R87E?8V]U;G0N8W-SI551:]LP$'YNH?_A:!ALH7:= M-$D3[VGL86,P&&SLM2C6V1:3)2,K;;.Q_UY9EA*[L5M#[R7)Z4[Z[KOO+M=3 MN'N379Q?G,-S^RS+O6)9KN$+"D&4A!]*:@+?=GP/:YA'T<KEO?[`2P;3Z_J> MB_/KJ;E+[C2J0E8:$BDT80(5O&<BX3N*%90D0\B14.,E(a)D(JI0G_`.Z.L\DQ MZ9_Y"?#`J,YCF$71NX_6D9J`("4%X_L8?J.B1)`K^*08X5?P%?D]:I883T5$ M%52H6-KD)9)+%<-D9:WQ;4GR)U-R)VC@CA]RIM&>_6_5U&-U(8$KI-)[;FH[ M,5^3"^L4M%FX>DI"*1-9L)5:RR*&1?G8'!1$94P$'%,=PTV[^HK]14/)RE/B M2UML-DNZ'"J-B=RPH5T*1V)\YM'\6.T!:>FP.@A:EN:Y<(E%#[*%][:@+3VR MUU`XX!MK8VC?2KJWPM$D&^+=TVYC7U*1X]$XVT^?Y3.7U2>9=N*L5Y.7OQ1N M=TF.&K[_O!PCS6$9'B#-1T**EGV0W@+!:X,X!.-:VO%I?-0!Q40JHID4,0@I M1@V972$H]."$U=;>''5L`]./57=\O->N1:/=4S6L?>A6*C,*C?:C<(X%5)(S M"I/Y[>J&+#M!?G9[XEH,'A"6SS#Z])D?I9-K9\=KJ;51[+&BWK8O<7=@CYC@ MS'?8OG[:I3,3$A:,4HZ=_6``EH\0FD4`P2R,S)J`Z*C=(73-YA^';N*".[3% M8&F)(+RI/QKFN/GK,&NY:6_/L&^\SVJ2<)89^(EI"JJ3Q=@1M!V'H5F9I.DZ MB:(.61XSZ;!Z[+6AC)KO2$\F[9`9Y_+^4'7O$/7*I;[:BF5X(@>'N`4CY,P0 M4^&=PA05BL1WO47G[=RN3IOP!%!+`P04````"``$C.@T]#-;HR`!``"*`@`` M*0```&QI8G,O9W!S7V%R<F%Y7V-O=6YT+V%R<F%Y7V-O=6YT7W1E<W0N8W!P MI5#!2L-`$+T'\@]#]9`6V4T]>*@W:Q%!1"C8WI;M9IHL-KMA=D(,XK^;5*JV M*A5\AV$.[[UY;^0HCF`+]6_$T<[K$,ET"%-?M63S@N$&G=/DX8$\:SA/TPNQ M+[VV@<FN:L8,:I<A`1<(5]X'AKE?<Z,)X<X:=`'/X!$I6.]@+%+Q+4`R1P1M MC"\K[5KK<EC;32>^G<[NYS,U5JG@9P9/8+I\H/F7"@5S-9&R:1JQZG,(3[D\ M<!E^MCC^K&/X\%HL%I.?SV_L*LC3)*^"6G8[:6J7RND2A[)7C[;SQ#JSJ3.$ M0<_;BJ4FTJTROG8LBJH:_(T%4H(IT#R!S;"L/*,S[?Z)+Q+%&';N<60=0ZFM M2[H?O;P7(^2:'*27<?3:4]X`4$L#!!0````(`#&2Z#3)3^[C6P8``(,7```I M````;&EB<R]G<'-?87)R87E?8V]U;G0O87)R87E?8V]U;G1?=&5S="YH<'"U M6'MOVD@0_[]2O\-<<JIL1'CU>B>1-!4E;HJ.``62-)>+K,5>P*KC]7G7H;2Z M[WZS?F$[-M"DMXJ"O3OSVYG9>:T/K3G\\GXXG$SUT4CO3?3>5!MWIKW!^<L7 M]<K+%Q`,_=GCY8L8*S^4K@I=YJX]:[$4<$X=AW(a),1AX3!%J-QN^U+.N9Q85G MS7Q!3?`=DWH@EA3>,\8%3-A<K(A'H6\9U.&T"E?4XQ9SH%EKU!X)H$PH!6(8 M[-XESMIR%C"W;&3N=;7!1-.;>J,FO@I@'A@H'Q!1HL)2"+==KZ]6J]I,RE%C MWJ*>0U$W6NPVUJZ1MLCU]76[6`+;FO'ZK\K"Y?IG?/:(M_ZL.^2>JG4)4`G^ M'R*$-4<[SB'T@LYXW+G1N\/+P52?:CCQ$?WB?*3+HVC\T6B%+$AO.71OEF0G MQ[!]D\*!%"J0M$X\CZQU(a)_F.J"U=]R!'&!+=NW:=<$Z]'32621UAB75$A2Y< M!\5R@-CNDLQJ>)3H,&HAN^M1UV,&Y9QY=8-LV2A#.2>&95O"HKQ.7-=>[\EF M">H1@9X9/=$]^83OVK1.;7J?J!BZ`BIZA`,Z,/,=8PEL#F+M4@X^IW/?ACEZ ML:!<\)@\_!44S8;;GTABZ1LP/0U7,,I\0P#&FO%EK?NF@.\;I[,<`<[QYEUR M2Q>:0@5<AJO4T^5<BH2Y4D^4(KT.BHJQY7"1(IS"JX3X]D[APFRWN?6-ZN(Q M;0:KDK"]RL'^>QR;*=&W3,N3!V:9T>(>"DOJGZ"SA*G\3*T?Z1W):S)_9E.E M$D:=G&W>-AMW*@:)4(^SM'.;$0%IVM;MFSM5TA]GO2AROCW'QFD/LVFD&V:/ MX4#O7@6*-G>036]&&JZW4D'`9H+(@`?CX>@?G]C6W,(2,5OC"9KTZS:\A%IQ M5-(a)Z_DZ.(BF<G=&H?Z-LY7HT-C"00II>COJ:KO6UBSWA,C`X?JN"4RVAW3+R M,$HBT:#7KX(2>):*#P\,`PCKI!I/0C*CYF!VV''+V,`\'0/2,/5*6.^"YSK& M/?$$$,>$*/\">T`_23L-+W(6V2.%#1*ZWZ@S[EQ,]&;I]JG]%3P6I5&%UU4X M2)4\7>;D()57BZ(@:]%0!_ET&->(G%2:HF9*@D?O42^PF4%LN">&QV*M_'3) MST=`5+"I8V)WB##Q;@N?>&:X*)=M3H/5L)8YBUJMEMH;W[#QREDT;#>*C'FF MC:8?,8.]?2O#?N-%B.2P%3AH)SPO2`HGX-^,H`1AF;O%CJ(-?,E\VP1BFG!@ M,VSHY#\T[<I8$LR70(51NPNED*,P#X1I92+76V]VT$H!PC2\:^3"ZQF)(Q^H M3T\=CY``BFVQ,YT4(4%*L@\8*-KFL)7"3*Y62Y`411Z?S#>^PZV%@YU_/)%^ MS7$5RH0LV%79/Y94RI#0V[P@)<KBB3_2V;8CER$E>B60R4R$G;Q'FY0A!45; M,H25/A8K*OQ%TI4AI5H$-?/:*M.Q#"G?7>VV_AY(\LA/U>Q<QCW";?9`RO!D ME]#XB;1[:@>5/$B(a),U0V6N^!E&.OG$*AU?9`DIVK;-EV6'T/I)1#;`,KR05/ M&"5(6`:##+^D>-/'DEA$DQO_KTQ/:U$>(3VYT\DA/:-CRB+%/5-A"2SJA%I9 M`.5UV/,4U]<C:);U0KE&,I0CEF)7ZX-]"7884"1FJL=H%2CVJ?1&`*7CV94/ MF[Q2E!\\R?)XJ6>Z0GD)CKI!.,*^*?-)AW^+V)J-%,MT29$#+U;RC,`E`MLP M!Y0E=F;WQ%D'W3-6'I,'4?E.#1F#?#A7@N\8[3;>O-OM^`O-2=[822MU6HFX M4]=OG\NO<Q%.Z"QL?IQN$V7V!FP#I?QW\!:^0R-U_96C=,-0)^3$ZS:;0PRO M<%4B%=L4X=%J22=[/1S_V1D/+P=GT0%?3*ZZ53C!7K;5:*C2@FCGQ'57S/M" M/-S'?+>!KT*C["_NQ3?$FZ>LDM'NH[[>F4RTL13D7%'0)NCR>?VDVBK6JO## MW?"#?M/3^F?:F=X9Z+U!=S@>:]VI?M7I7VH8QZ7F4R'^</"C`G"Y^T5O<M&9 M=C_J[[7IM:8-],E?*,"9GD@UV;UY*E7@U<YW78]R#BOB.>@V?+.*MSYA&;I! M>%25483C;<N!B>*/2-'W1#S(.&^$EZA/R8T(IZ)SVER2XCL4I_;\:'-[P9NS M\)@M:?X#4$L#!!0````(`!B)Z#1`?)CDM@$``)T%```A````;&EB<R]G<'-? M87)R87E?8V]U;G0O8W!P7V-O9&4N8W-SK5/+;MLP$#P[0/YA`:,7![;IH*EE MZ9A#@9[Z!P8EKB0B)%>@Z#AJT'^OJ(<MN9:+H%D"DD`N9V=FM>L%[/\K[N_N M[^`RGJFHK,QR!]_1&&X)?EIR''X<5`4!/#+VK;OW[P*W`A9KC].N]>*"1<Q+ M_(M:'_[F;)600'BOOP!2,FZ9<BU5%8(F0V7!$ZR/?D_`*VZR`\\07K`ZDA57 MX/N3MD+,DY?,TL&(94**;`C2Y&BEBYKC;F^^W0;!;A>=21W16QE"3$K<X//\ M\`"-GFO1R2T*SV6"S3S=^C5D,R)XE,+E(7QEJ*,>I%:'=EFZ2F$(A@P.'B4I M*:)A7H>P*=Y&VZ?Z*7]BK,<NN!#29"&PU08UL.Z].5=OW"GEK[KTYI%].7LS M&YF3(_=5#-=7O&F,X:LV9]_D3'5KGC[5BXVZU1G4EYX-<,*<7M'>0&-^W4*[ M%.([C&]<%VI*2/-#K_J<]XD>G=BVZ=(H:?KLD^N-V>-']+E2$M(:C9N6TAY_ M:'AV=03!8'@ZV=)Q)9,I-BE/I)).8@DQUNI!4'+PQ5'T;.J=O<ME^5$ZC#$V M,<NC&8C).=+C_OP!4$L#!!0````(`*F+Z#0T][$,H`8``-X1```?````;&EB M<R]G<'-?87)R87E?8V]U;G0O:6YD97@N:'1M;+58>6_C1!3_FTK]#F^-M$J@ MB1,J(;9-NEK:!58JRXIV.52J:&*_Q*../69FG`/8[\Y[XR-V:4HEV+:)?,R[ M?^_JY.4F5;!"8Z7.IL%X.`H`LTC',EM.(a)$M!E\%+\\.#R;/+GXXO_[UW6M( M'!&\>__UY9MS"`9A^//Q>1A>7%_`+]]=?W$Q`&NG)&1"\/7;X/#`Z"?('$N M/PG#]7H]7!\/M5F&US^&&V8U9MKJ<F`]X3!V<<`RO2C2+[/3!SB,7[QX41(& MH`2KBUG`QT^:NS,6/TE0Q&>E(A,GG<+J!N"5,6(+Y[K('%S*N1%F6YT+VP<G M*3H!K,$`?R_D:AJ<Z\QAY@;7VQP#B,J[:66LPXT+6:]3B!)A++IIZ4@(:X9* M9G=@4$T#Z[8*;8+H`D@,+J:!8*5F$2LUC*P-P)&0:<G5WS^)2Y3GQ"/&QUA, MPL8UD[F.MW15<8[E"F1,7,@R(3,T0>.SR;/!`/[C[V#'K9;$FK3%5(*N4)@H M@;G>O&R3T5N9+L&::!H,AR']S;6V;IAGRP"$<M/@:[X'I9>:T*&S98PVFN[( M`YF*)<[XJ9&Y(_#;H=N0]R(E+,$ME7&LD!VU'R1>C;RE$]#[9>+6R-]'!(LT MEPH'3J9X!#ZLX,,*"Q%))=T6%MK`O)#*#636YN,/6]`+NII+QS+!B.RN)3C< M29Z$Y,4F>!\M1!7,.S%*QAW[KXHT[?HGI!/7"<)$U*XM(SW+1(H56%MA*8.Y MS.W,!S1L)T.2Y\%9\/#S22A:#@"PNC`1PH+\#S$N",(6W%K#HL@BCC8X3',E M'#VVA71B3N<H&#L&!JD6X8K*(#A2/RO2.1H."-^API0\408HJT(K+%WO&$AR MUM((Q=7!.D%1QTUNT'*A'>X%$+LJI8P#F>9&K[R84JHD:52GO?PU*C6XR_2Z M`YJ)S4F9RLN4_\#Y3WI0F2"5-X(,1@[>)_Q3T5CY!^I%SUO0#]MW-Z/;_B1D MEAT%92QU"J2,2X0#R5B6RL):NJ1EH/=,KMD'QA>?(V@[EP">;4&3*>7;DERP MJZI6!$[3?9L#,>CX%T#G:(33YN:V">L0OBD,LTVU0=:.*AYFL?5>:[+.Z3:; MM%".K")/LV`*6)5\(HMA*U'%?`EH#"D@R_CGY&*,VTP:^AHIB<AS>L)VS)&^ M-?4HLT3HX7`Y9#Z,&\<H=!WW6@I_S`15J6!QQR9N"6#,P;RM\3\J1[\-L#!_ M+&&WF<ZMM/<RMHU/<N0.4X'/L@[2[G"[UH8Z-F<TO8BP@@WX5(4_F5F;XO!@ M1U.G84WR7+E3Z^*3$X;BS+'91_N)"18LM":^/H(V;?9\Z4[O"]]1<V^N*7O/ M*3M.[\F)=33CO`O.&E]7YWO7)4'_)KOM]^&&\MO)2"BU'7#1+QS&@Y50!=Z> MED7I80WN&<^V_S=3_Q=C/>YF>O&@K?1%<CX0!$("QB/`>F^IOS[0!PJ+=145 M<RIH#U5DF:VT6J'/VA:+!PTK2U9M6ET2CK@:2Z4*FBB)92M5J;3Z6J"5TFNN M[E5AM"=[,5_6T58!/3SX5&:1*N@IQXQ`;E"D90@Z;^3#K_;T,&:\TC*&1:]_ M>.#3IK"LHC]^<E('I@HTAQ0LW,!X!+<PA3]A!!\\WB77#:34NZGJ.]2D/=OO MG/T'8`B^:=/CP\_J3E<5(^*TJT,C^"QL-0@/1SKFO.7\@8`#7C9'5H?J=$)A M"=HP@=WIWCU=H<=$_?Z>XT'3A8>_94%E2ZP+[N2;F_'H]N8+^AR/;KU+'C-T MGZF,DY[\?-P?4'/:V=VQVC?W3BK&Y-[QZ3Z/7#1L@MW3N&T5"=X\R4\5*AK% M^&7,2.MMGNHT\*GL*_J_I/.KB,<-A?&R)'^D7W3H+@2E^"L:FA.1\JBU7%), M,2YSL,ABP=RHY_*&-:")AR:F-"7,MWFD(DIX!^'&S7-1%2<_$C4]G3SZT_F7 MOFF7<\7<Z#OLS`O5/&[LGNY8C]'5W<<9HA=:NW+/V>LS&I7+':[:>:F3R)BK M6KWY1@E&=R\+(Z=T#`VS\\MWF\EN#^?1&/ZB!2;?&EY,X'E$EZ?P+6:9,!K> M&4W;[1>CT9==MTSFIEDU2RWKW"EM`"4C0A[.2B6R"(-NZ"6O\W-NAD"1KD;7 M<B^[T@NW%E1E+TL>1_!3-?>1WL,VE]X54@V).'8T,W(U]#/]Y9OSUV^O7L_& MLQ'O;3P<LE4T4C7N:W-I__N@W!39C_>8-+/Q4PZS5_M=AWU<')7\2MZ>9[.; MUSB;A-42/_'_?:!@_`U02P,$%`````@`-G[>-*:\<7@$`0``[`$``"D```!L M:6)S+V=P<U]A<G)A>5]C;W5N="]T<F%N<VQA=&EO;E]U;FET+F-P<*6/,4O$ M0!"%^X/[#\-ID1RRF[.PT,YXB"`B!&S#9C-)%I+9,)D0@_C?S9Z(>'J5KY@I M=M^;[^GM>@4'Y?_6>O65=:PHC2'U_<RN;@3ND<BPAV?V8N`R2:[43^N=&X1= M,0J6,%*)#-(@W'H_"&2^DLDPPJ.S2`->P`ORX#S!3B7J%T"4(8*QUG>]H=E1 M#95K%_-#NG_*]ODN3Y2\"G@&N_"!D1,5&I'^6NMIFE01.)3G6A^EQ*'%MS]< M_M/6NF+0Y]&RV/"<D^DPUE`M#*6W8X<D1I9"ZC-NJ\,\<V3;L438U/V0'[*T M839S;OU(HIJ^WX1_C@0ZXRB*X0T8962"Y`;>P]L'4$L#!`H``````*N<Z#0` M```````````````%````;&EB<R]02P,$%`````@`1Y/H-,I_\*E2!@``CA,` M`!D```!G<'-?8F]O<W0O87)R87E?8V]U;G0N:'!PK5=M;]LV$/X^H/_AF@RN M'3B6LP[]H+@9;"?(@G5.$*M-MZP@:(FVB<J22U)VW)?_ON.+;"E^2[NQ(a)*.* M=\=[>>[AR3MZ]A.81?[S>O93;BM?U6X-NNET(?AHK."2)0D5*=R(5%&HP#F= M\0C:`T''="+AEV;S5:-LXYQ+)?@@4RR"+(F8`#5FT$E3J:"?#M6<"@9O>,@2 MR>KPC@G)TP1.&LW&8T^@VF<,:!BFDRE-%CP9P9#'J'S5O>CU+\@):3;4@X)4 M0(@.`U5K%NP:*S7U/6\^GS<&VH]&*D;>(RNU513[L[9O%3-R=W?G;_8@Y@/I M_5P=325YC\^"BL5[DM`)JWG:P!'^'O(AIG`(G>OK?D#:M[?MOTCW^FTO(+_? MW)#+&Z(+T'SULHFB*,<3]A11_>^0)V&<10Q:H501ZIZ5WAX8-[TP389\U!A/ MIP?KFQ%3E,?>/!4?$2)8:R,'G@<8DK:&3\=;E]GN&OL9(B+-A&3QC$G]WKHR MA"K8H"(7U9_]=UVH5-S_[JYO_VC?8HCGU=5VW6T&%_W@XIRT@^K)K\UFK08U M^`>+\O7KFM%.MT-NVK?!5?L-Z=]<=/'OU=_MX.JZ1SIO+U%OYUHS2LAE[VV7 M$.WG\KD%+VLZ,7*<9G$$$?8(PCGC<@P'@M'X`$9A"&,FV.D6#&]::!!BIEY( MF%.N8)C:7DO8'"8T%*F$>ZS$ATV%G4QCC\UH3/AP2W6U!(]8HKA:;!%1BRDC M2N#9TN.24"'H4T0%FZ0S1@8:,M+)HP9L!7"2$JEUD9`(1[^,.$LB/MR+LKW+ M63"(];R\B4+T39%T6'VPY9?\,TL1CP\UVSVZ2^64A@Q,>/`E;ZIM[;H>@BZ? M_84P9C2IPTW0/QY0B1B:659<":W.LTUG#]2>*8;6J,(^QC;V?>TH4770^=9* M9U8*S\Y"A;B;(.VB96("/-UI1$NO#$%0A^)FLM-RR^@&]\D')_9E!6NIJ.(A MICC!Q!5-(APS!J_+#;#!\/$)FC[S?2/O^N7;AEA^T/7FCSH.2<F9;[JTB%)7 MLO\AU^&8"JA6E@Y7@VJEAJXBN]W;0WQ_>R%<PCZL96IOHMRYRZ98'HL_IP[Y MP&+)=,0:W0Q]T,G"BQU)G87*@-FA/1ASF2,<YH8/D0WC&`9,9Q+'BZ&YT1/\ M,T&6S)L$IP"\_85L0"=3,,=62),7^$`3I6EO`BJ%*5WD-.C4(H:Q(8V%G$DW MJ:PW4^&5(3&;N[S)='IT5\]2]`WWF<P[9U7+,*920MLDS#XO"]'4[Y8P<B!J M`SVU[B'?<).I)%4@V*>,"V2`XV.*R-&O='PLRM4ML_0#O)^Z2"T]?.H%U5+K M:R1:OJK2^R96R3D[S08Q#_W<4AZ5*ZZ-6[^LW3OM=LTS:,D!78ZXA-XZK"?` MY)")4O0LR2:8;EOFUY!?&JUVCDYS5$D6\XB2T?K&5+"9WL']WZ!J>*$&/C3! M.\(?Q%C"$&60:4(]\@H,X>"T]*Z8C64KE"XIXY_>0I0;;)]NU</T^+Z[64G8 M6K&'H3)X_AJ:Q7?UW)&6B:>>'P!G92EC-K^.6P5PH6LKV=Q+9].4\W'UBSD8 ML_`C:*!AS^!<'ND6VI>8'0$^-W7=Y;CMGIVQ%7U?"ZP0T"9,6N`%1LVQNXF1 MB7(3K@45^/ZJ`6#U6$`_F)1U4A'KA.FNE$@S"#,Y92''P#]32W.'`#BZKL;! MSO7MFW;O7(^!^:!A?,C9MWP;Y?ZV--NLWT&/N:CHI_7T4#>(&XV,]X_N(6DW M]!:^3Z,H7N!NFHW&]65T(=7,.J$)'3$S4FHJACE78Z=&(:@@V0K,'=:J#@/- MR/@=((V049FD@AG2CMF#TW+W!K:_X"Y9^8"SAU=L29?ERB^[`EG[_C)SQ2IO M%[=?&'O6QBKBRH_(FS=:WK'Z4+U[5D+4^I5M*[5OZ4MUTUE/.:ABB?^P@(;# MW<#$#Y!XBI1I/AXT%^"-K.G3J&Z?SO5LLWU[8#%EIMYJ.".?,AK7['<3;*M[ MLJI[,1M.1]]8A6G$V83B5+*FXQT=>3GW[?%Q8X2UTR?IFMGPB;*S%`/'B>9[ M3$-1";.>;?G<*&KN$$OL6*I!L@3:9C;][N;;J^#0W"RC^3&>5S.G@7,)S);G M]LV<AO[L5]IRRMN9N^U?F^8H]UT[RO"^U+?IOU!+`P0*``````"KG.@T```` M````````````"@```&=P<U]B;V]S="]02P,$"@``````=GKG-&)R,3FD&``` MI!@```D```!B;V]S="YP;F>)4$Y'#0H:"@````U)2$12```!%0```%8(`@`` M`&XWE<,````$9T%-00``K\@W!8KI````&71%6'13;V9T=V%R90!!9&]B92!) M;6%G95)E861Y<<EE/```&#9)1$%4>-KL75V0',5][YG9V9W].NWI3G`'$M)A MX#AP"`*%F./#1N%!D@.I0E%([.)!H2JN,J&H.'ZA</*0,N8EIHHB<<4/1`\4 ME`D?%>-"4L5$KL+H5"X+G<!!AT!PD(a)#=G;2G.^W7[,[NSN0_,[NS<S/3/3V[ ML[NZH_\U6O7T]'3/3?]__?_H?_=PFJ8A1HP8M44<PP\C1@P_C!@Q_#!BQ/#C M(,HF.(YC_<&(X2<`9AB<&#'\A`D;!B1&7T7\D.NA:86,$X8B1FL3/[@:VJZ9 M`!6&(D9K!S^4R*%OP@$/3[0P"#%:"_CQO-&>Z2[@>8L;#_8<!B%&:Q`_9&R0 M440O@JPT0Q&CM8,?`G@\D=/&_(\G<LB2BA&C58D?-TX<B:#X(208BABM;OR0 MP4,^#80?2C@Q%#%:-?BA`8_[MQ/\,!0Q6IOXH0$/0;7S5=MZCZ)G?O[&NT=G MW/G7;1Y][D=_RWAEM=!K!X_L>_U0;_HQ$BYX*%'DJ-9D=RM!$%#NPF:=CAL] M,WWIU)DYS_SK-H\PIEQ%-'=AJ6?]&.GD9AQX/.&$B/.M07G=Q)(%$L\:@E8[ M?V'9,W]TPR!CRE5$O>S'2""HD!4V-WAH1)`=`/9?G/"Q?ATHZE`0'9^9Q5UB M\F=U$:XK+SOYXX"3&SQ*'2E$BIP:"4#<XU_R/:_GBK)2HJO=$.=\X40;M`" M&AEF\F?5"Y\N]6.D;;1XBAT[>("*=2DA<IKNIK`#!:T\:^6*4;&F5"*\1F\4 M4:ISOO7@E.940AK9D&%\N5H(9\1VJ1\[E3\XY`!55"X6%2#_V)?HQ!S2N9?3 M?_6#;R20(9G,TUTWH%2$*W+QI%ITPX!&J2-[(\(a)0.G5F'B/T1QE3KB;YDUWN M93_R08T?Y!55H'F17($/%J4M0^_A`+Z@32K?"M'_U'U],=9_9(4%2I:!&Y7 M5=6JRIYV:XE!W16!QBUF_*PN^J2W_<@'*NT&DF>.KKE5!2FF"Y_WSQIE3+0@ M&VQ<$/ID$5TL(X'CZH*$`P\92`CC2<<]OT6%4AD.STOI9)PQY1JP?[K4CWQ[ MM^&$CY6C\E&H>CZG?7Y1M>6WD--*H)9<>G_>%$&\C&(F6H(""?E%WWE"""=\ MF/Q9,_9/E_HQTC9R/*.P3<I5Q7A<%SY3G]8TP\S1;0_#B6`ZW#2;%TXS2N@Y M*OKZE2:FN4A,JI5D@><"^=#<?CG*>W'&#]"M$V.,*5<+$28ANM2/_O$[A%`# M-X%8J-6U"I\4(]R7R]JO9^J<SKFZQX#CFDF;"Z%URJ'MUZ$K$D@WA52]N;(L M2YILQ>]8Y#AUY%AIA(_]02X']_,O[C_XSG3;+S&5D,`\W7K3V-VW3W3NY`$- M!/A@[L(2H!JT2L>`"GR02DK7;QZ%`35<GNAVNU#Y;X_.0.4$:4]#+_SD,>LE M/_7LRP3,^!+4`[7UVO^&"\,Q\POU6"+*%17T/Q]6=5%@"!E.4S5#5S2E$,<U M-#=+%HT-&N#1M$(N']-D*!'E.-4&!DN,T$P*>;KFVE":*0FX#7H1CGVO']J[ M>_M?[KBSO4H`PP:'S?D.L6:<'N#V[FT3>W9,=@+:'K0+KQ=&J$X8W<'T-(HW M#77NE&O3?^UV6YMI146QF%[GQPOU!A^;"&E"J.E<7J'%06+B"CU=+-?@I!8; M`LNH*3TL9+3D!F?>Q:&(6I6XFGO7!$\($8`45M<"`81@"'_\D5U!.?C5`U,X M'P;Y1C@`L7MV3@);MW%[M]L%%@<I$;0)&C6,X/6AI.M[C!^"_\U,EVJQ1(2[ M6%2/G5:<!H\QU>-I"&W;B`9B"!0_M7PI/C`4%1R`<`F9YG_E*J?5JYY2B&SV MV"]U.(:YR50%*2'TVL$C;7"PNY+C,Z<??V0G_8#:FW;#!4^XPD>O;3C37?S0 M+$!H:6X*;_JLI\\J%E`TN[VQ4HLSD9"(H6O7&\-)H<2)*0!/7D'98M,UV`S] M,>4.Q[60MR6-))$OU:,)37$+'T0=6=>A\H:#T-:),5!RR*/X,__Q1EBBS^34 MIW_P'5\(];+=YU\\$")XT,H84(+7IPTT]EI_<R>JFB!RJ%!1/UL`RX<W52S+ MW,$90G=N1J*`9*6NU4KI]#``X]-%]%&V%9=@]S'8TXD(NB*.(F*T7JD(//(, M64`4P:.X&>M.%;DW#A'P$_K`;`(#^)6\Q*67[<(@$KILM[NA<2%7EZG]XW;$ M.7*20K52C21C_#WCTF]/0@_Q*V(ZO0RA+>O12$IW&Y1SRV)J$'(7931SO@&5 MAJ7$V7Y;<T7H\#FT8PN*"UR1CR<UF;`RC^Q"P,U8P^"T\][;<'?Y&MP@UH"! M=MR[M6TFAMZ]=6*+.?&7+\J(a)*?FR(Q0`G0KGP.AQNZ\>G,+5OW?W?9T[#\%Z M&=W=$D?3)V8]A2JN'X.:BV'*'T]<17BM6%&BHG3MALCT&;Y804XMSF4(W3RB MYQ1*5<A*2(;N=V[%C!"((#/:U,PTVFN<`LWFT$V#2(I&JHH0-=W>*P6..ZC4 M'2"'8P[H8((G#2Y!;SW_XGZ"^C<],^O&#["O+Q/#79[>+6@+Q)KG(MD6UQZ8 M\GSL'K<+;]7SS0#7@K(7"N\ZWJTNCF8"]V.'Q'=N_-AE45I4RI4ZZ&/?')<T MS8@\:$;OK`CV,2[==HV6B:.:JJG%K)3.@`JV4$0+^8;8L8?&K8CW0<BJYN1% M=$G10WZJ?-PSC)72N^JK:N,`]O0_?)?`"IX,![8'@8G--<://[++4S6'S">_ M]]#>W=O)VM3ET"Y(+1S3AP*>$/NQ6_@A>*X]&;2!I5H9_AO-\'`X(&3S-F@" MKWYM2#\OY`I:-!T7A4H=O7/*.S3.(V2N>?QA4:\U(7)E+DK`#"Z_PV5SP%AD MKG((-]#HB"V.TC@`8#0E>R;<&FGOVP5MRK/,UINZ%<_1RV5S_OBAC+QTQYXE MA*HLUR!]Q]<DX[+JG"DR?K>/\Y*(RHJJ5BXEDRDH\=DBJM0\H((L""';;[/` M^2*Z4#9TM$A,=1EF;0]:B'JY%0RH!#>.8\C'F00F%.D5F[T/D4'K=$SUJ]WV MRH0H?%"7ES_ZVS^^RAMRA?;P:K&NKMN0XF\?BQD@Y9OSGHV`&IY#5PV`*8)* MN24A,21&N%P%'3W3-'M<H7%-/X#3$#(+3\VAG9M13.!*-2FI5>Q."X<OP>U( M"&79W-VW3X#U3./4)G0SZ$[TB@T\&X@+2N]6O]K%F4FA1QZAGB^;:]-_X*F\ MN6.?HZA6D"L#R=C6S5'.8Z%VXZ104I!:2Z>@\[29.<Z*Z'%ZW(a)P_.%*-P%*; M_\T"0JV&3N?0#1D4BXKULL+S@=Y[",OF*&/C#^!#[("?@K(4<"$E'_>EW512 MP@GDIYY]&5ZO+VBA(3!=0&.D@7>/E\WYX(?^`R2XO41B]5RAE.'X%8"QW8;J MJJK*2['4!I!%"WET<D$S@^7<H7$(X2%DRB0._5\6C231@,C)D41$*]%ONQ-* MN#M-87=$IIUV>KFYR41I%O>KW:T38P1_'0T"37MFW^N']NR<]'6@?=*GY8]\ M)\J;,R(;H7PU4JC'X%"TN%J5ZV6Y+I?J<K$F%^"HEO1#@4,NJ'*.U^IQ20?P MJ06?-4(TAM#,13TG+O*R)E+^\6$MFR-H1];8>?S$+*$,V2[W),+LH5UCZ5>[ M8!:&,O9#!P&$GG]Q?WM=T.WEC\'F3\G*6UX1DZEX0['R"%I;H<BI*LHMSN>* MY4Q*NOEJ[E06NT:H&0'D8P@)1@$-A;!F.^BX1?8+DQ6,MG4,`FCM(J)?[1J6 MU<ZP8AW`A(/*"5+HU.4C?]I3WJIU+1K3O06+A7JV4+^8K^=D-5?6CWQ9+534 M?./0\F7]`"LEDAKB2@O5FI:)<W>,-6'I$#@K$[@9(:`;C;Z3E7J<JW9H_*"` MRZUPOEI[)9^$O<25TO/>KW91TRT>UFP/(=JU]\OFJ.0/&3D.Y:U4EY(2GY?K M_S6U:)@?YFHYD_A&&IDY_)69R`-_'$O%Q8O%5#Z?7S\X<.T0?_Q,75&=:X0X MKJ6M$0RA>S:BI*A/Q4IJF1-HC1^<*A+(8V,N_O&V`6QS'85BN4/W`R7'.`1+ MO]JU<EYXYC&0'@?>.=;Y(BLPJ#SCH7`U]V#C,2K]S?>S"Y4J+\5UJ^/],S*R MNXD-!+3BWQJQ/.K"<NV+97%CAD\,9)3E+V0E&8\*WQSG?WV"M$8(!R%)0%<F M]4N*4DUQWGO+!5)%`LT8'"1YM[9TJ=NF\58-I<.J9^U")NA=-!$TY@)5POO$ MR1]<?@\VO@S@/R!8/F5.7[.S<*GZP>F"M2>(K8#6FCEMQ/*H!]^72XHF1?EZ M;$C.7X1"5PUPF];#57W/$(]M1E9J:W;ZQD;]MU+34ES%OEK;L<8;N6*Q:>2& M[Z`(>@5N\*,T,/)%N0U[@.#XHJRD7^T2=*W'']E%CN<(A.KNQ3K0XH?&\KE4 MX1*2+GP.S^0:F0V8:8ZT(Y;GY$(=?@=225Y5\B5]#<^MFP33`>`PA-P6D64( M79U&&^)Z!#>J5NS(Z<3XH5]6]?R+^W&#WYX=D]1*T>E`+_^U@T=PC09RJ?6K M73+M".Y2QSD/.E\>%Q@_-)L/KMR\"O&B!-QZ]F)E;DEI%?""T,KZU?<^JRP6 M5$%`?&(#*F7!>ED?Y[9>PYO1I6Y?`O+:>/'F#7I^65$E3B$@QV/97);*#TOF M)]P4!]1`SP>X4&6<SHF3>#IH@ZSB[E>[X1)A$@(WA]M3^4..R%RN\)+(%ROU MMWZ7Q6EWE@=`LT)(FUK<>V=TR"438IV+%@HEW>+<P!M75T`(839>O/E*M"ZF MNPUBMCE33\W-#20"Z]#H7;B/-.&$#]G9M>^-0Y2\\LS/WR`(`3=H^]5NVT28 ML/*T)PF3$-U86=RI_F:'4U751,-G_=&Y4LVNI-DP0S:$SERHGENJ\QR2TH,1 M9:E<59,BNG]"L"#4JLG+$+IVT!0^-9%#OH!Q7#IUMLW('9`Y3SW[,@$\H,>[ M^8D\;0]U$BJTN`':);"+9R1;O]IM6YB\BHDDI+<G+7KUX%2X*VW;][]Y+EC( M*V(BSF7SM:D3RZBQ-*T9?6.>-N-K+&?:BO`<PQWW]H?EO_K3I!3EER.9>C$G M93(;UW&#26VIB,@;+WYK#"5$I-2T)%?FO(B@O!'&K?D+2\`N!)V'W"7`29X[ MAX!Y`)Q*N!<$VGQV>>]#V]W:(\U&.8!83PND7^VV(WGT#<!^@^L7PEI@`O*? M^/$+H`MTSR?)^?JF<923Z[KEPW,'IA=/G2LUYW8:"Z_Y9A2G-0ODF!'2+_&\ M>=?D#?&;KXK4:IJ2.X\2PPDILI#7JBJR>:(;>UEQJ+6%R-4#^F]%KB0%A>=Y MW`:+"/,IU3__NY]TXX4^_8/OX.;LR"J?70`&73X-_/'D]QYJ3]4,O5U=TRL& M'O7)`Q-@^[D?/>J)`4`=8;QSTRO/_6.(6&I__;:BB7&>.[=4.?5ET9KFU)K1 M.XYETJU?@X4;5YO"9>IC>71=<GV2EV/K>26G10='TARRPZ<9N^.(#*HH:BI2 M;<S/VJ2-VV?M`$^(&[XY-!G"A#<,U333B,!)@18(0+5DGV^/VR4O\V[[Q>*8 M/I!2!Y6$*XBHUF][DB#H]\XO*2U[IBFP<(:0K5JG(512]#F?:%2(<;5"4<Z7 M=(]VO@A'M0!'J5J4]:.@'S4XBN5:J5P3C=4^GC('$7?>6<A>"K>#3;6-;$9# M&1BMP^T_X&!?\Z.7[79C8"*/2H&\%Z$O9R#AASR+4JOJKK,;KTY$!:'E57,C MA&)&:##%;\SHDE`IET$32_*E),JGN`(<:;Z0%HII7C\&A-*ZB+Q.*&4B<B92 MSH@525`;ZJ"7_H83/BB,K8\<O0)J&TTOAA@29JX;I=P9HV?MAKZ\U'=4,KV= ME']:Z.&D`?0WQ[K.]7&T7*DE8I&==VSXY9%YNSZ&7!M'D7T)]XSK.G>I7`<- MSG=+^$`)O/,@G&Z&;J-9G>)@Y1>>>0P,DK9WK`<.!HX)ZC+N3;MMQ#00W)A[ M=]]'(S%,2(/=Y:NCAKZ7")7_P.%(L+Z]LUQ212D._/G?OSM_]KS<"A)M<K&% M@D9CAE.AX3PPI`8D)C;&[QV/0R.54E[B:YX?5J#'">7'%QY^XJ>=>#:O,SY# M</WFT4[F/:"SP2QY][T9RFD*X!)@*=]M3?O;;H<?1+#>[3W;)H*&3IO>0MPN M<+[>G=[AQPZAK"PD)?%\3OG%.W,M;QL&0IZ^N+^9S`S$^4))2?.E-H0/X1<G M@NA7I_:&@(_U4(#L,@S>#L$(G)1.QD>&]:F/T*.)^]7N6B)__"#BUW[D*JKQ MT0C/OS.S=/S37(,UK0_]-)@5"Z%OW[YNTWI1J:I"-2<*7"#A@\,)0?)<AN!A MM*J)#^H\<#BXXB*J5(S0SRT#5JC!B@W?$'+(,<M_D);X38,BI&I*18>@019^ MK+0[0?B6%@,/HW[B!\=P;M>P=9H65:6F#L2%![\QTH*0#3<(N42<D7_?U]-P MH5RNI\6J&S:!D..)&8861GV3/Y3#-ER*B7Q=44!?VS(L#::B+8009H1`PQZ- MCV;T[]0+6MD!#S=:?)'C2'@^,X,3H_[@QZ&\N6E]$LEE?<_1;]TR9%]L0)@1 MVC:60+K/NIH4-5_,^"+'+2H9>!CUP7^`7-^F]_3"N9T*.5D5HKHO^]V/ENR[ MC39]":U)(3B)1_E;MR1J-36*9)$GN0U\O0(T%HYG9DFN?#&_:*8WC@PEXK'+ MI$L^G\O"[Z;189J2<EFY8>PJ7(&/9\]9Z;@4)=1I?QLF$:HU:7$YO[B4]WUU M]F?P?=50F/R<5KMF>F@P/91)TY3T+=P>13RYS?-;.IZ?IK(R!^+\A5(U*8EW MWSCHV("`<R>-_Y5*-97@*3^@[?9$MXT<H*EC'[VRO[4:C/S-*2@\/#A`PT_' M3\S^V>0M'7;)KPX=A=_O?W<'3<F3L^<(#__O+QVTGSZX?1ON\0`\CL+C8U>1 MG^&5MPY#ZX0Z/9\A$8_^T_?WX"`$A<GM_NK0[]^>^H-UNG?W?3A(O++_\-2Q MD_:<AW=-3MYV8]?Q@T.4_;N\%HKL$%H7J^?+G*=*Z-[#%^X:C*N^WFI?Y)!M M,]P@!^"A?YM0^#$*;@;P`#]UCA^3*2E+COL)'Q-=(%Z>_.E+9%%F,:Y9^.1* MN>$>4SZ?SP+OGC6D)<TS`/WK"[_\?&X1L.HY&)F%"7_1_TY]`.#Q1:SYYP!X MX/'^^>_W=%59B-`@QS/'KD$U]NR-\+&(ZEQYZO4=Q28D>!Q@:+2U-I!CTO3, M++Q9&O#L>_T0*$B0>//0[T&I>'C77=[(F9F%WLHNY>5*Y6<O';Q_\A9?8440 M8J:N15D2=!)<@>R2OAW%SXSAOU2N;!H=NG/K.+;P<A[P8!;.&CK/_9-_1%#V M@(_OOU-GXK>/?$!X2,<S`'C@,7`OQRQ,^-L/&_($@&UA&R>IH']!T,$K>N+' M_TDI3L/$C^,KO)Z?X'4G"#6X.=LWZ*8-KS2EDP!TXN%!*CWXFM%A8"PTJV\N M0^C7A!2#[LDNG=PT,@R)H<'VE6Q37P=UD=),&B9J_\"LYG`.G`?8)A@>4)OY M\#"XP(WD[RL>F3X)90`/@+22K.CW8BP6*`:L#-6"F`*F!TP^L/U/R","P?BQ M:O-].?"7@I9H672_,%1-D&]MCVL=Z6^>0'(CQZWF>7Y$Q(&?SI$3U+<&2/CX M]#D0&L#W9(L6]`30&:##R`H#]`H<;QXZ^M??OJO#'C+'X.EF!!?!Y#611N`V M8[`?;A8XZ8?&1=!1X>&A/!@AP&TX_``3PU\*R(1;++T+]QA0YJ[;QN'M@<B" M=SY]XC0!/V:%A+\(7@6,`O!.S(XCC%-N=PB((^CHWNEO;A'D"2%?R!'RW;*( M$+<6HDL:]"OHJGVO_\8\_>&C#Q(&9NBDR<%QWSJAPT`O[[R'@&N!=T$;-&U? M@JYO&AZ$%D$?,ZLRN>>!^[:119E9%4`(Q@NX"]Z2)W1?>>LPY/_PT;\P3__E MWUXEF$#P#).WC9L"`?0]`!X83CC-&0H#+`DO!X8GD"16QQ%>#DC(-PTWC`4\ MT+V[X6+E*/>I0OC0.$3WI52<"A>*AYH1H[X01UYD2@,A]RDE?I!?N#2;!F6T MNO'C"Z&@PH<L(a)AAX&*UQ_.!P0BE\?#UR##R,UA1^R!`*BAP<'LA.-@8>1JL8 M/SA@M(<<&A0Q\#!:4_BA1%$;^AM##J.O"GX0]7<9VI,_##R,UCA^Z*'B6::3 M65=&C-8(?CJQ>1AR&#'\A`8DAAE&7W7\T$"+X801PP\C1HP8?A@Q8OAAQ*B_ M]/\"#`#D)'YC&MVN60````!)14Y$KD)@@E!+`0(4``H``````-.<Z#0````` M```````````5````````````$0!M00````!L:6)S+V=P<U]A<G)A>5]C;W5N M="]02P$"%``4````"`"0B>@T`?LZ+YL"``#%"```)``````````!`"$`)($S M````;&EB<R]G<'-?87)R87E?8V]U;G0O87)R87E?8V]U;G0N8W-S4$L!`A0` M%`````@`!(SH-/0S6Z,@`0``B@(``"D``````````0`A`"2!$`,``&QI8G,O M9W!S7V%R<F%Y7V-O=6YT+V%R<F%Y7V-O=6YT7W1E<W0N8W!P4$L!`A0`%``` M``@`,9+H-,E/[N-;!@``@Q<``"D``````````0`A`"2!=P0``&QI8G,O9W!S M7V%R<F%Y7V-O=6YT+V%R<F%Y7V-O=6YT7W1E<W0N:'!P4$L!`A0`%`````@` M&(GH-$!\F.2V`0``G04``"$``````````0`A`"2!&0L``&QI8G,O9W!S7V%R M<F%Y7V-O=6YT+V-P<%]C;V1E+F-S<U!+`0(4`!0````(`*F+Z#0T][$,H`8` M`-X1```?``````````$`(0`D@0X-``!L:6)S+V=P<U]A<G)A>5]C;W5N="]I M;F1E>"YH=&UL4$L!`A0`%`````@`-G[>-*:\<7@$`0``[`$``"D````````` M`0`A`"2!ZQ,``&QI8G,O9W!S7V%R<F%Y7V-O=6YT+W1R86YS;&%T:6]N7W5N M:70N8W!P4$L!`A0`"@``````JYSH-`````````````````4````````````1 M`&U!-A4``&QI8G,O4$L!`A0`%`````@`1Y/H-,I_\*E2!@``CA,``!D````` M`````0`A`"2!614``&=P<U]B;V]S="]A<G)A>5]C;W5N="YH<'!02P$"%``* M``````"KG.@T````````````````"@```````````!$`;4'B&P``9W!S7V)O M;W-T+U!+`0(4``H``````'9ZYS1B<C$YI!@``*08```)````````````(0`D D@0H<``!B;V]S="YP;F=02P4&``````L`"P`?`P``U30````` ` end

3 4

[bgl] tsp 2-approximation
by Matyas W Egyhazy 05 Aug '06

05 Aug '06

Hello, I posted earlier on the boost-users list regarding an implementation of the tsp 2-approximation that I have implemented using the BGL. I have fixed it up a bit since my initial post simplifying both the interface and the implementation. The approximation algorithm runs in polynomial time and solves the TSP problem with the worst possible solution producing a path twice as long as the optimal solution. More information can be found regarding the algorithm/heuristic on page 1028 in "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein. A slightly different description can be found on Wikipedia: http://en.wikipedia.org/wiki/Traveling_salesperson_problem#Triangle_inequal… I have attached a newer version and test driver. Comments are welcome. Thanks, Matt 1,2 2,4 10,20 45,20 15,1 17,20 20,25 30,20 //Main test harness for the tsp_2_approximation solution generator #include <iostream> #include <vector> #include <fstream> #include <boost/lexical_cast.hpp> #include <boost/graph/simple_point.hpp> #include <boost/graph/tsp_2_approx.hpp> int main(int argc, char** argv) { using namespace boost; using namespace std; typedef vector<simple_point<double> > PositionVec; ifstream fin("graph.txt"); if (!fin) { cerr << "To run this program properly please place a " << "file called graph.txt" << endl << "into the current working directory." << endl << "Each line of this file should be a coordinate specifying the" << endl << "location of a vertex" << endl << "For example: " << endl << "1,2" << endl << "20,4" << endl << "15,7" << endl << endl << "The output of the program will be a TSP tour of the graph" << endl; return -1; } string line; PositionVec position_vec; int n(0); while (getline(fin, line)) { simple_point<double> vertex; size_t idx(line.find(",")); string xStr(line.substr(0, idx)); string yStr(line.substr(idx + 1, line.size() - idx)); vertex.x = lexical_cast<double>(xStr); vertex.y = lexical_cast<double>(yStr); position_vec.push_back(vertex); n++; } fin.close(); vector<int> tour(n + 1); tsp_2_approximation(position_vec, &tour.front()); for (vector<int>::const_iterator itr = tour.begin(); itr != tour.end(); ++itr) { cout << *itr << " "; } return 0; } //======================================================================= // Copyright 2006 Virginia Tech // Author: Matyas W Egyhazy // // Distributed under the Boost Software License, Version 1.0. (See // accompanying file LICENSE_1_0.txt or copy at // http://www.boost.org/LICENSE_1_0.txt) //======================================================================= // //tsp_2_approximation //Takes a sequence of simple_points and performs 2-approximation //triangle inequality to generate an approximate tour solution for //the traveling salesperson problem in polynomial time. #ifndef BOOST_GRAPH_TSP_2APPROX_HPP #define BOOST_GRAPH_TSP_2APPROX_HPP #include <vector> #include <complex> #include <boost/graph/graph_as_tree.hpp> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/prim_minimum_spanning_tree.hpp> namespace boost { //tour is the TSP approximation tour //pos is a coordinate map of the vertices represented as simple_points template<typename PositionMap, typename Tour> void tsp_2_approximation(const PositionMap& pos, Tour tour) { using namespace boost; using namespace std; typedef adjacency_list <vecS, vecS, directedS, property<vertex_distance_t, int>, property <edge_weight_t, double> >Graph; typedef graph_traits<Graph>::vertex_descriptor Vertex; typedef graph_traits <Graph>::edge_descriptor Edge; typedef iterator_property_map<vector<Vertex>::iterator, property_map<Graph, vertex_index_t>::type> ParentMap; typedef graph_as_tree<Graph, ParentMap> Tree; typedef tree_traits<Tree>::node_descriptor Node; int n(pos.size()); bool inserted; Edge e; Graph g(n); property_map<Graph, edge_weight_t>::type weight_map(get(edge_weight, g)); //add edges to the graph (for each node connect it to all other nodes) for (int q(0); q < n; ++q) { for (int i(q); i < n; ++i) { if (q != i) { //triangle distance double weight(sqrt(pow(static_cast<double>(pos[q].x - pos[i].x), 2.0) + pow(static_cast<double>(pos[i].y - pos[q].y), 2.0))); tie(e, inserted) = add_edge(q, i, g); weight_map[e] = weight; } } } //extract the mst using prim's minimum spanning tree algorithm vector<Vertex> mst_preds(num_vertices(g)); prim_minimum_spanning_tree(g, &mst_preds.front()); Graph mst(n); //build mst graph using the predecessor map from prim's mst algorithm int cnt(0); for (vector<Vertex>::const_iterator vi(mst_preds.begin()); vi != mst_preds.end(); ++vi, ++cnt) { if (*vi != cnt) { add_edge(*vi, cnt, mst); } } vector<Vertex> parent(num_vertices(mst)); Tree t(mst, 0, make_iterator_property_map(parent.begin(), get(vertex_index, mst))); //create tour using a preorder traversal of the mst PreorderTraverser<Node, Tree> vis; traverse_tree_ref(0, t, vis); cnt = 0; for (PreorderTraverser<Node, Tree>::const_iterator curr(vis.begin()); curr != vis.end(); ++curr, ++cnt) { tour[cnt] = *curr; } tour[cnt] = tour[0]; } } //boost namespace { //Recursive function that traverses a tree with a custom visttor template <class Tree, class TreeVisitor> void traverse_tree_ref(typename boost::tree_traits<Tree>::node_descriptor v, const Tree& t, TreeVisitor& visitor) { visitor.preorder(v, t); typename boost::tree_traits<Tree>::children_iterator i, end; tie(i, end) = children(v, t); if (i != end) { traverse_tree_ref(*i++, t, visitor); visitor.inorder(v, t); while (i != end) { traverse_tree_ref(*i++, t, visitor); } } else { visitor.inorder(v, t); } visitor.postorder(v, t); } //Tree visitor that keeps track of a preorder traversal of a tree template<typename Node, typename Tree> class PreorderTraverser { private: std::vector<Node> path_; public: typedef typename std::vector<Node>::const_iterator const_iterator; void preorder(Node n, const Tree& t) { path_.push_back(n); } void inorder(Node n, const Tree& t) const {} void postorder(Node, const Tree& t) const {} typename PreorderTraverser<typename Node, typename Tree>::const_iterator begin() const { return path_.begin(); } typename PreorderTraverser<typename Node, typename Tree>::const_iterator end() const { return path_.end(); } }; } // anonymous #endif //BOOST_GRAPH_TSP_2APPROX_HPP

1 0

Re: [boost] back_inserter and pointer container library
by Thorsten Ottosen 04 Aug '06

04 Aug '06

gast128 wrote: > Dear all, > > it seems that the pointer container library does not interfere well with > back_inserter, i.e. > > boost::ptr_vector<int> v2; > std::back_insert_iterator< boost::ptr_vector<int> > b(v2); > b.operator=(new int); //forget it [remark: I assume you only use int as example?] > This is unfortunate, because now a lot of STL (or our own adapters) containers > can't be used (e.g. std::transform, std::generate_n) This is because the concept of a PtrContainer is not the same as a Container. Specifically, back_inserter() will try to call push_back() which does not take a T& parameter, but a T* parameter. operator=() in back_insert_iterator will on the other take a T& parameter. After the review, the T& overloads for push_back() etc were removed because people felt they weren't needed. I see two ways to solve the problem: 1. overload push_back(), push_front(), insert() etc for T& parameters 2. provide a new function: template< class PtrCont > ptr_back_insert_iterator<PtrCont> ptr_back_inserter( PtrCont& c ) { return ptr_back_insert_iterator<PtrCont>(c); } template< class PtrCont > class ptr_back_insert_iterator<PtrCont> { ... ptr_back_insert_iterator& operator=( typename PtrCont::reference r ) { c_.push_back( new_clone(r) ); return *this; } }; Have I overlooked something? I think I would favor option 1. However, this should be discussed in the developer list first. I'm also planning to drop the forced non-copyability (by providing cc and ca) since we have discussed in a couple of times and both times I seemed to be the only one who favors the current design. -Thorsten

1 0

[Boost-bugs] [ boost-Support Requests-1534701 ] Having some trouble building boost
by SourceForge.net 04 Aug '06

04 Aug '06

Support Requests item #1534701, was opened at 2006-08-04 17:58 Message generated for change (Tracker Item Submitted) made by Item Submitter You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=207586&aid=1534701&group_… Please note that this message will contain a full copy of the comment thread, including the initial issue submission, for this request, not just the latest update. Category: Building Boost Group: None Status: Open Resolution: None Priority: 5 Submitted By: Sp4cedOut (sp4cedout) Assigned to: Nobody/Anonymous (nobody) Summary: Having some trouble building boost Initial Comment: Platform: Windows XP C++ Compiler: MinGW (from Dev-C++) Python Version: Python 2.4 (C:\Python24) I've unzipped all the boost files to C:\boost, and put bjam in the same directory. my command line looks like: C:\boost>bjam "-sMINGW_ROOT_DIRECTORY=C:\Dev-Cpp" "-sTOOLS=mingw" install ... MkDir1 C:\Boost\lib spawn: No such file or directory I've ckecked all the tutorials on the boost site, and I can't seem to find anything on this. Any help would be appreciated. ---------------------------------------------------------------------- You can respond by visiting: https://sourceforge.net/tracker/?func=detail&atid=207586&aid=1534701&group_… ------------------------------------------------------------------------- Take Surveys. Earn Cash. Influence the Future of IT Join SourceForge.net's Techsay panel and you'll get the chance to share your opinions on IT & business topics through brief surveys -- and earn cash http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV _______________________________________________ Boost-bugs mailing list Boost-bugs(a)lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/boost-bugs

1 0

[quickbook] Including source files in the document
by Julio M. Merino Vidal 04 Aug '06

04 Aug '06

Hi, I've just started adding example programs to my SoC project and I was wondering if there was a way to bundle their code into the documentation (which I'm writing with Quickbook). Of course I can hyperlink to the source file, but this could be useless in printed documentation. Also I'd copy&paste the C++ code in the qbk file, but that is asking for trouble (desyncronization). Hence, I think it'd be useful to be able to include this code in the final document straight from the qbk file. I tried with the [include ...] command but it did not work as I expected. And indenting it in the .qbk file so that it was formatted as source code made things worse because the inclusion had no effect at all. Similarly, [xinclude ...] cannot work either for obvious reasons (source code is not XML). So... I added a 'cinclude' tag (standing for code include) to quickbook which, given a file, includes it in the documentation marked up (and colored!) appropriately. The implementation is attached. It can very well be flawed as it is basically a copy&paste of other parts of the code, but so far seems to work. Any chance this -- or something similar -- can be integrated? Thanks. -- Julio M. Merino Vidal <jmmv84(a)gmail.com> The Julipedia - http://julipedia.blogspot.com/

7 12

Boost regression notification (2006-08-04 [RC_1_34_0])
by Douglas Gregor 04 Aug '06

04 Aug '06

Boost Regression test failures Report time: 2006-08-02T06:38:31Z This report lists all regression test failures on release platforms. Detailed report: http://engineering.meta-comm.com/boost-regression/CVS-RC_1_34_0/developer/i… 268 failures in 24 libraries algorithm/string (1) concept_check (1) filesystem (4) graph (5) io (1) iostreams (10) mpl (6) numeric/conversion (4) numeric/interval (1) numeric/ublas (7) parameter (22) program_options (9) python (85) random (1) rational (4) regex (1) serialization (25) signals (16) spirit (1) test (2) tr1 (51) typeof (9) utility (1) xpressive (1) |algorithm/string| regex: borland-5_6_4 |concept_check| class_concept_check_test: vc-7_1-stlport |filesystem| mbcopy: sun-5.8 operations_test: vc-7_1-stlport operations_test_dll: vc-7_1-stlport wide_test: sun-5.8 |graph| adjacency_matrix_test: vc-7_0 csr_graph_test: sun-5.8 graphviz_test: msvc-8.0 msvc-8.0 vc-7_1-stlport |io| ios_state_unit_test: gcc-4.1.0_linux_x86_64 |iostreams| bzip2_test: msvc-7.1 msvc-8.0 compose_test: borland-5_6_4 example_test: vc-6_5-stlport filtering_stream_test: vc-7_1-stlport finite_state_filter_test: cw-9.4 gzip_test: msvc-7.1 msvc-8.0 zlib_test: msvc-7.1 msvc-8.0 |mpl| multiset: gcc-4.0.3_linux gcc-4.1.0_linux gcc-4.1.0_linux_x86_64 gcc-4.1.1_sunos_i86pc gcc-4_0_3_tru64 vector_c: sun-5.8 |numeric/conversion| converter_test: borland-5_8_2 traits_test: borland-5_8_2 udt_example_0: borland-5_8_2 udt_support_test: borland-5_8_2 |numeric/interval| test_float: vc-7_1-stlport |numeric/ublas| concepts: vc-7_1-stlport vc-7_1-stlport test1: vc-7_1-stlport test2: vc-7_1-stlport test4: vc-7_1-stlport test5: vc-7_1-stlport vc-7_1-stlport |parameter| basics: borland-5_6_4 borland-5_8_2 duplicates: borland-5_6_4 borland-5_8_2 maybe: vc-6_5 vc-6_5-stlport vc-7_0 preprocessor: borland-5_6_4 borland-5_8_2 sun-5.8 vc-6_5 vc-6_5-stlport python-parameter-test: vc-6_5 vc-6_5-stlport vc-7_0 sfinae: borland-5_8_2 vc-6_5-stlport singular: borland-5_6_4 borland-5_8_2 unnamed_fail: vc-6_5 vc-6_5-stlport vc-7_0 |program_options| cmdline_test_dll: cw-9.4 options_description_test_dll: cw-9.4 parsers_test_dll: cw-9.4 positional_options_test_dll: cw-9.4 unicode_test_dll: borland-5_8_2 cw-9.4 variable_map_test_dll: borland-5_8_2 cw-9.4 winmain_dll: cw-9.4 |python| andreas_beyer: sun-5.8 args: sun-5.8 auto_ptr: sun-5.8 back_reference: sun-5.8 bases: gcc-3_4_4_tru64 gcc-4_0_3_tru64 sun-5.8 ben_scott1: sun-5.8 bienstman1: sun-5.8 bienstman2: sun-5.8 bienstman3: sun-5.8 borrowed: sun-5.8 callbacks: sun-5.8 const_argument: sun-5.8 crossmod_exception: sun-5.8 data_members: sun-5.8 defaults: sun-5.8 dict: sun-5.8 docstring: sun-5.8 enum: sun-5.8 exception_translator: sun-5.8 exec: cw-9.4 darwin-4.0.1 gcc-3_4_4_tru64 gcc-4_0_3_tru64 msvc-8.0 qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_gpp qcc-3.3.5_gpp sun-5.8 extract: sun-5.8 implicit: sun-5.8 indirect_traits_test: sun-5.8 injected: sun-5.8 iterator: sun-5.8 keywords: sun-5.8 list: sun-5.8 long: sun-5.8 minimal: sun-5.8 multi_arg_constructor: sun-5.8 nested: sun-5.8 numpy: sun-5.8 object: sun-5.8 object_manager: sun-5.8 opaque: sun-5.8 operators: sun-5.8 pearu1: sun-5.8 pickle1: sun-5.8 pickle2: sun-5.8 pickle3: sun-5.8 pickle4: sun-5.8 pointee: gcc-3_4_4_tru64 gcc-4_0_3_tru64 sun-5.8 pointer_type_id_test: gcc-3_4_4_tru64 gcc-4_0_3_tru64 sun-5.8 pointer_vector: sun-5.8 polymorphism: sun-5.8 polymorphism2: sun-5.8 polymorphism2_auto_ptr: sun-5.8 properties: sun-5.8 raw_ctor: sun-5.8 return_arg: sun-5.8 select_arg_to_python_test: sun-5.8 select_from_python_test: darwin-4.0.1 sun-5.8 select_holder: sun-5.8 shared_ptr: sun-5.8 slice: sun-5.8 staticmethod: sun-5.8 stl_iterator: sun-5.8 str: sun-5.8 string_literal: sun-5.8 test_pointer_adoption: sun-5.8 try: sun-5.8 tuple: sun-5.8 upcast: gcc-3_4_4_tru64 gcc-4_0_3_tru64 sun-5.8 vector_indexing_suite: sun-5.8 virtual_functions: sun-5.8 voidptr: sun-5.8 wrapper_held_type: sun-5.8 |random| random_test: intel-linux-9.0 |rational| rational_test: borland-5_6_4 vc-6_5 vc-6_5-stlport vc-7_0 |regex| regex_regress_threaded: gcc-4_0_3_tru64 |serialization| test_class_info_load_text_warchive: vc-6_5 test_non_default_ctor2_text_archive: qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_cpp test_non_default_ctor2_text_archive_dll: qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_cpp test_non_default_ctor2_text_warchive: qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_cpp test_non_default_ctor2_text_warchive_dll: qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_cpp test_reset_object_address: vc-7_0 test_reset_object_address_dll: vc-7_0 test_set_text_archive_dll: msvc-8.0 test_simple_class_binary_archive_dll: vc-6_5 test_simple_class_text_archive_dll: vc-6_5 test_simple_class_text_warchive_dll: vc-6_5 test_simple_class_xml_archive_dll: vc-6_5 test_simple_class_xml_warchive_dll: vc-6_5 test_variant_xml_archive: borland-5_8_2 test_variant_xml_archive_dll: borland-5_8_2 test_variant_xml_warchive: borland-5_8_2 test_variant_xml_warchive_dll: borland-5_8_2 |signals| dead_slot_test: gcc-3.3.6 gcc-3.3.6_linux qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_gpp qcc-3.3.5_gpp qcc-3.3.5_gpp trackable_test: gcc-3.3.6 gcc-3.3.6_linux qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_gpp qcc-3.3.5_gpp qcc-3.3.5_gpp |spirit| mix_and_match_trees: sun-5.8 |test| parameterized_test_test: vc-6_5 vc-6_5-stlport |tr1| run_random: sun-5.8 std_run_complex_overloads: sun-5.8 std_run_random: sun-5.8 std_test_bind: sun-5.8 std_test_complex: sun-5.8 std_test_function: sun-5.8 std_test_hash: sun-5.8 std_test_mem_fn: sun-5.8 std_test_random: sun-5.8 std_test_reference_wrapper: sun-5.8 std_test_reference_wrapper_tricky: gcc-3.2.3_linux gcc-3.3.6_linux gcc-3.4.5_linux gcc-3.4.5_linux_x86_64 gcc-4.0.3_linux gcc-4.1.0_linux_x86_64 intel-linux-9.0 mingw-3_4_2 msvc-7.1 msvc-8.0 qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_gpp qcc-3.3.5_gpp vc-7_1-stlport std_test_result_of: sun-5.8 std_test_shared_ptr: sun-5.8 std_test_tuple: sun-5.8 std_test_tuple_tricky: sun-5.8 std_test_type_traits: sun-5.8 test_boost: vc-7_1-stlport test_hash: vc-7_1-stlport test_random: sun-5.8 vc-7_1-stlport test_reference_wrapper_tricky: gcc-3.2.3_linux gcc-3.3.6_linux gcc-3.4.5_linux gcc-3.4.5_linux_x86_64 gcc-4.0.3_linux gcc-4.1.0_linux_x86_64 intel-linux-9.0 mingw-3_4_2 msvc-7.1 msvc-8.0 qcc-3.3.5_cpp qcc-3.3.5_cpp qcc-3.3.5_gpp qcc-3.3.5_gpp test_regex: vc-7_1-stlport test_type_traits: sun-5.8 tr1_tky_function_type_test: sun-5.8 |typeof| function_binding_emulation: sun-5.8 function_binding_native: vc-6_5 vc-6_5-stlport vc-7_0 nested_typedef_emulation: cw-9.4 odr_no_uns: vc-6_5 vc-6_5-stlport vc-7_0 template_tpl_emulation: sun-5.8 |utility| operators_test: gcc-3.4.5_linux_x86_64 |xpressive| test7: msvc-8.0

1 0

Re: [boost] Spurious warning in lexical_cast.hpp
by Martin Bonner 04 Aug '06

04 Aug '06

From: Paul A Bristow > From: Alexander Nasonov >> >> I have not get a chance to study the subject yet but I wonder why >> don't you just set a precision to some huge number, say 32767 or >> INT_MAX? > > This would be hugely wasteful as it would convert everything with > 32767 decimal digits, of which, even with 256-bit floating point, > 32267 digits would be noise! <Nit>That implies 500 decimal digits would be non-noise. Actually the formula suggests that a 256 bit mantissa would only need 79 decimal digits. -- Martin Bonner Martin.Bonner(a)Pitechnology.com Pi Technology, Milton Hall, Ely Road, Milton, Cambridge, CB4 6WZ, ENGLAND Tel: +44 (0)1223 203894

2 1

Re: [boost] Portable signbit macro/function?
by Martin Bonner 04 Aug '06

04 Aug '06

----Original Message---- From: boost-bounces(a)lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Peter Dimov Sent: 04 August 2006 11:39 To: boost(a)lists.boost.org Subject: Re: [boost] Portable signbit macro/function? > Johan Råde wrote: > >> I still find it hard to believe that the volatile are needed ;-) > > It is not. If volatile is not present, then you can't instantiate the template with T="volatile float" for example. (Similarly you need the "const" so that you can invoke with T="const float".) I suspect that for this application that doesn't matter, but that Gennaro was so used to using the safe form: reinterpret_cast<const volatile char*>(&s) to get at the bytes of an object in a template, that he just wrote it automatically. -- Martin Bonner Martin.Bonner(a)Pitechnology.com Pi Technology, Milton Hall, Ely Road, Milton, Cambridge, CB4 6WZ, ENGLAND Tel: +44 (0)1223 203894

4 6

Re: [boost] Portable signbit macro/function?
by Martin Bonner 04 Aug '06

04 Aug '06

----Original Message---- From: boost-bounces(a)lists.boost.org [mailto:boost-bounces@lists.boost.org] On Behalf Of Guillaume Melquiond Sent: 03 August 2006 17:16 To: boost(a)lists.boost.org Subject: Re: [boost] Portable signbit macro/function? > Le jeudi 03 août 2006 à 17:49 +0200, Johan Råde a écrit : > >> All I need to do is to get my hands on the bit patterns of 1.0f, >> -1.0f and x. Do I really have to copy the memory to do that? >> That seems like overkill. > > You don't have to copy the memory, you can simply read the bit > patterns > char by char, if you prefer. Any other kind of access will produce > wrong > assembly code on compilers with "strong" optimizers. > >> Can't I just form pointers to the float constants, cast the pointers >> to int pointers, and dereference them? > > No you can't. See paragraph 3.10/15 of the C++ standard. > > Best regards, > > Guillaume ... and of course this whole masking approach wouldn't work for an architecture where the sign of a floating point number was indicated by setting the sign bit such that the parity of all the bits in the number was odd for positive and even for negative! That is not to say that the bit test via mask is not potentially useful, just that one should be aware of its limitations. -- Martin Bonner Martin.Bonner(a)Pitechnology.com Pi Technology, Milton Hall, Ely Road, Milton, Cambridge, CB4 6WZ, ENGLAND Tel: +44 (0)1223 203894

5 14