graph reduction in Clojure
This is an old version of a Clojure solution to a puzzle. It looks like I hacked span-population to trade time for space or something. For instance, this version continually rescans the head of the edge sequence instead of conjing it up on a 'front' vector.
If you get tired of waiting for 'lein run large' to finish, you can run 'lein uberjar' in the project root, and copy the exported jarfile onto a beefier machine and run it on a better provisioned Java.
Here's a transcript of 'lein run small'.
tbl.local # ls
README.md src
test project.clj
tbl.local # lein deps
Copying 1 file to tbl3rd@gmail.com/Clojure/bvg/lib
tbl.local # ls
README project.clj
src classes
test lib
tbl.local # lein run small
-main
Got: bitvectors-genes.data.small.gz
Got: bitvectors-genes.data.small
Got: bitvectors-parents.data.small.txt
write-bitvector-genealogy bitvectors-parents.data.small
extract-genealogy-from-genes-file bitvectors-genes.data.small
find-relations 20 500 bitvectors-genes.data.small
#span-population 500
... <lotsa .s and #s edited out of here> ...#..#.#Adding edge 3 : [7 51]
Adding edge 4 : [51 472]
Adding edge 5 : [7 401]
Adding edge 6 : [51 493]
Adding edge 7 : [75 493]
Adding edge 8 : [75 139]
Adding edge 9 : [7 179]
Adding edge 10 : [179 202]
Adding edge 11 : [73 202]
Adding edge 12 : [73 217]
Adding edge 13 : [179 460]
Adding edge 14 : [43 460]
Adding edge 15 : [179 431]
Adding edge 16 : [107 179]
Adding edge 17 : [40 217]
Adding edge 18 : [73 272]
Adding edge 19 : [179 360]
Adding edge 20 : [260 360]
Adding edge 21 : [260 419]
Adding edge 22 : [371 419]
Adding edge 23 : [394 419]
Adding edge 24 : [251 394]
Adding edge 25 : [304 394]
Adding edge 26 : [360 399]
Adding edge 27 : [37 399]
Adding edge 28 : [419 436]
Adding edge 29 : [35 260]
Adding edge 30 : [35 343]
Adding edge 31 : [125 399]
Adding edge 32 : [125 284]
Adding edge 33 : [284 395]
Adding edge 34 : [112 125]
Adding edge 35 : [125 289]
Adding edge 36 : [289 354]
Adding edge 37 : [125 294]
Adding edge 38 : [198 294]
Adding edge 39 : [231 294]
Adding edge 40 : [125 305]
Adding edge 41 : [199 305]
Adding edge 42 : [242 305]
Adding edge 43 : [242 283]
Adding edge 44 : [215 305]
Adding edge 45 : [57 284]
Adding edge 46 : [57 412]
Adding edge 47 : [57 461]
Adding edge 48 : [284 457]
Adding edge 49 : [245 457]
Adding edge 50 : [245 414]
Adding edge 51 : [294 322]
Adding edge 52 : [322 453]
Adding edge 53 : [410 453]
Adding edge 54 : [125 281]
Adding edge 55 : [281 316]
Adding edge 56 : [151 395]
Adding edge 57 : [151 449]
Adding edge 58 : [147 449]
Adding edge 59 : [138 147]
Adding edge 60 : [138 239]
Adding edge 61 : [147 426]
Adding edge 62 : [203 449]
Adding edge 63 : [110 151]
Adding edge 64 : [110 330]
Adding edge 65 : [12 330]
Adding edge 66 : [135 330]
Adding edge 67 : [61 151]
Adding edge 68 : [126 147]
Adding edge 69 : [239 327]
Adding edge 70 : [151 335]
Adding edge 71 : [265 395]
Adding edge 72 : [300 354]
Adding edge 73 : [323 412]
Adding edge 74 : [57 352]
Adding edge 75 : [91 352]
Adding edge 76 : [87 125]
Adding edge 77 : [87 279]
Adding edge 78 : [265 309]
Adding edge 79 : [254 309]
Adding edge 80 : [102 198]
Adding edge 81 : [142 412]
Adding edge 82 : [151 328]
Adding edge 83 : [254 285]
Adding edge 84 : [259 322]
Adding edge 85 : [33 265]
Adding edge 86 : [33 341]
Adding edge 87 : [114 341]
Adding edge 88 : [33 99]
Adding edge 89 : [46 453]
Adding edge 90 : [46 234]
Adding edge 91 : [110 192]
Adding edge 92 : [192 342]
Adding edge 93 : [29 192]
Adding edge 94 : [342 488]
Adding edge 95 : [125 456]
Adding edge 96 : [295 456]
Adding edge 97 : [284 385]
Adding edge 98 : [18 385]
Adding edge 99 : [18 468]
Adding edge 100 : [52 385]
Adding edge 101 : [52 444]
Adding edge 102 : [137 385]
Adding edge 103 : [137 332]
Adding edge 104 : [137 368]
Adding edge 105 : [69 368]
Adding edge 106 : [69 255]
Adding edge 107 : [319 368]
Adding edge 108 : [84 368]
Adding edge 109 : [137 144]
Adding edge 110 : [176 368]
Adding edge 111 : [176 455]
Adding edge 112 : [103 176]
Adding edge 113 : [176 312]
Adding edge 114 : [176 380]
Adding edge 115 : [69 407]
Adding edge 116 : [308 407]
Adding edge 117 : [137 466]
Adding edge 118 : [319 358]
Adding edge 119 : [137 273]
Adding edge 120 : [248 380]
Adding edge 121 : [248 314]
Adding edge 122 : [248 353]
Adding edge 123 : [53 353]
Adding edge 124 : [368 438]
Adding edge 125 : [144 246]
Adding edge 126 : [134 246]
Adding edge 127 : [93 134]
Adding edge 128 : [166 246]
Adding edge 129 : [86 134]
Adding edge 130 : [246 429]
Adding edge 131 : [380 421]
Adding edge 132 : [457 475]
Adding edge 133 : [18 359]
Adding edge 134 : [282 359]
Adding edge 135 : [136 380]
Adding edge 136 : [137 435]
Adding edge 137 : [15 435]
Adding edge 138 : [15 42]
Adding edge 139 : [326 435]
Adding edge 140 : [326 383]
Adding edge 141 : [22 326]
Adding edge 142 : [8 22]
Adding edge 143 : [8 235]
Adding edge 144 : [22 184]
Adding edge 145 : [22 194]
Adding edge 146 : [189 284]
Adding edge 147 : [189 286]
Adding edge 148 : [63 189]
Adding edge 149 : [63 372]
Adding edge 150 : [204 372]
Adding edge 151 : [189 377]
Adding edge 152 : [286 369]
Adding edge 153 : [369 370]
Adding edge 154 : [286 463]
Adding edge 155 : [63 85]
Adding edge 156 : [9 63]
Adding edge 157 : [297 343]
Adding edge 158 : [28 457]
Adding edge 159 : [42 432]
Adding edge 160 : [63 454]
Adding edge 161 : [392 454]
Adding edge 162 : [227 392]
Adding edge 163 : [448 454]
Adding edge 164 : [276 454]
Adding edge 165 : [71 360]
Adding edge 166 : [71 489]
Adding edge 167 : [423 489]
Adding edge 168 : [48 423]
Adding edge 169 : [151 195]
Adding edge 170 : [195 440]
Adding edge 171 : [218 440]
Adding edge 172 : [95 440]
Adding edge 173 : [171 395]
Adding edge 174 : [171 263]
Adding edge 175 : [23 263]
Adding edge 176 : [171 433]
Adding edge 177 : [77 433]
Adding edge 178 : [204 315]
Adding edge 179 : [255 494]
Adding edge 180 : [50 494]
Adding edge 181 : [153 494]
Adding edge 182 : [273 492]
Adding edge 183 : [241 492]
Adding edge 184 : [36 241]
Adding edge 185 : [156 241]
Adding edge 186 : [186 492]
Adding edge 187 : [36 474]
Adding edge 188 : [186 408]
Adding edge 189 : [241 471]
Adding edge 190 : [97 471]
Adding edge 191 : [66 97]
Adding edge 192 : [284 417]
Adding edge 193 : [365 417]
Adding edge 194 : [417 437]
Adding edge 195 : [149 437]
Adding edge 196 : [149 291]
Adding edge 197 : [220 417]
Adding edge 198 : [296 417]
Adding edge 199 : [437 465]
Adding edge 200 : [311 465]
Adding edge 201 : [161 311]
Adding edge 202 : [311 411]
Adding edge 203 : [288 411]
Adding edge 204 : [32 417]
Adding edge 205 : [32 121]
Adding edge 206 : [121 165]
Adding edge 207 : [60 437]
Adding edge 208 : [21 60]
Adding edge 209 : [5 60]
Adding edge 210 : [5 67]
Adding edge 211 : [56 121]
Adding edge 212 : [11 60]
Adding edge 213 : [11 497]
Adding edge 214 : [445 497]
Adding edge 215 : [11 129]
Adding edge 216 : [129 173]
Adding edge 217 : [60 366]
Adding edge 218 : [289 441]
Adding edge 219 : [6 465]
Adding edge 220 : [6 373]
Adding edge 221 : [15 307]
Adding edge 222 : [18 74]
Adding edge 223 : [50 299]
Adding edge 224 : [174 471]
Adding edge 225 : [207 352]
Adding edge 226 : [148 207]
Adding edge 227 : [94 148]
Adding edge 228 : [30 207]
Adding edge 229 : [148 478]
Adding edge 230 : [148 340]
Adding edge 231 : [175 340]
Adding edge 232 : [148 357]
Adding edge 233 : [26 357]
Adding edge 234 : [175 301]
Adding edge 235 : [207 344]
Adding edge 236 : [311 490]
Adding edge 237 : [88 490]
Adding edge 238 : [379 490]
Adding edge 239 : [313 379]
Adding edge 240 : [275 379]
Adding edge 241 : [55 275]
Adding edge 242 : [387 490]
Adding edge 243 : [362 387]
Adding edge 244 : [226 362]
Adding edge 245 : [111 387]
Adding edge 246 : [11 268]
Adding edge 247 : [23 249]
Adding edge 248 : [42 222]
Adding edge 249 : [222 464]
Adding edge 250 : [111 224]
Adding edge 251 : [137 363]
Adding edge 252 : [363 446]
Adding edge 253 : [187 446]
Adding edge 254 : [128 187]
Adding edge 255 : [34 187]
Adding edge 256 : [34 390]
Adding edge 257 : [150 446]
Adding edge 258 : [231 256]
Adding edge 259 : [289 403]
Adding edge 260 : [80 403]
Adding edge 261 : [80 90]
Adding edge 262 : [90 250]
Adding edge 263 : [65 80]
Adding edge 264 : [80 302]
Adding edge 265 : [20 302]
Adding edge 266 : [80 225]
Adding edge 267 : [157 225]
Adding edge 268 : [157 317]
Adding edge 269 : [105 317]
Adding edge 270 : [2 317]
Adding edge 271 : [59 157]
Adding edge 272 : [59 104]
Adding edge 273 : [14 20]
Adding edge 274 : [5 169]
Adding edge 275 : [15 182]
Adding edge 276 : [182 450]
Adding edge 277 : [47 450]
Adding edge 278 : [24 47]
Adding edge 279 : [15 274]
Adding edge 280 : [145 274]
Adding edge 281 : [25 399]
Adding edge 282 : [25 163]
Adding edge 283 : [25 388]
Adding edge 284 : [98 388]
Adding edge 285 : [98 155]
Adding edge 286 : [98 434]
Adding edge 287 : [4 434]
Adding edge 288 : [25 498]
Adding edge 289 : [122 498]
Adding edge 290 : [122 181]
Adding edge 291 : [181 418]
Adding edge 292 : [172 418]
Adding edge 293 : [96 388]
Adding edge 294 : [54 129]
Adding edge 295 : [64 144]
Adding edge 296 : [64 89]
Adding edge 297 : [89 480]
Adding edge 298 : [89 113]
Adding edge 299 : [113 168]
Adding edge 300 : [98 262]
Adding edge 301 : [124 129]
Adding edge 302 : [144 158]
Adding edge 303 : [158 355]
Adding edge 304 : [19 355]
Adding edge 305 : [260 398]
Adding edge 306 : [356 388]
Adding edge 307 : [356 491]
Adding edge 308 : [362 428]
Adding edge 309 : [162 428]
Adding edge 310 : [395 422]
Adding edge 311 : [422 473]
Adding edge 312 : [0 84]
Adding edge 313 : [0 83]
Adding edge 314 : [0 232]
Adding edge 315 : [232 320]
Adding edge 316 : [10 320]
Adding edge 317 : [159 320]
Adding edge 318 : [11 196]
Adding edge 319 : [101 387]
Adding edge 320 : [146 385]
Adding edge 321 : [146 278]
Adding edge 322 : [146 364]
Adding edge 323 : [364 406]
Adding edge 324 : [351 406]
Adding edge 325 : [406 413]
Adding edge 326 : [271 413]
Adding edge 327 : [3 278]
Adding edge 328 : [186 393]
Adding edge 329 : [393 396]
Adding edge 330 : [317 416]
Adding edge 331 : [39 94]
Adding edge 332 : [115 465]
Adding edge 333 : [115 287]
Adding edge 334 : [116 414]
Adding edge 335 : [116 243]
Adding edge 336 : [116 487]
Adding edge 337 : [306 487]
Adding edge 338 : [214 360]
Adding edge 339 : [214 462]
Adding edge 340 : [140 214]
Adding edge 341 : [100 214]
Adding edge 342 : [251 264]
Adding edge 343 : [264 350]
Adding edge 344 : [41 364]
Adding edge 345 : [49 54]
Adding edge 346 : [71 476]
Adding edge 347 : [16 476]
Adding edge 348 : [68 476]
Adding edge 349 : [68 258]
Adding edge 350 : [68 382]
Adding edge 351 : [164 476]
Adding edge 352 : [44 476]
Adding edge 353 : [333 476]
Adding edge 354 : [333 400]
Adding edge 355 : [382 495]
Adding edge 356 : [78 278]
Adding edge 357 : [78 82]
Adding edge 358 : [92 457]
Adding edge 359 : [119 151]
Adding edge 360 : [70 119]
Adding edge 361 : [70 177]
Adding edge 362 : [70 143]
Adding edge 363 : [143 485]
Adding edge 364 : [70 238]
Adding edge 365 : [470 485]
Adding edge 366 : [119 318]
Adding edge 367 : [119 424]
Adding edge 368 : [127 424]
Adding edge 369 : [127 458]
Adding edge 370 : [447 458]
Adding edge 371 : [62 127]
Adding edge 372 : [62 481]
Adding edge 373 : [127 178]
Adding edge 374 : [197 458]
Adding edge 375 : [197 409]
Adding edge 376 : [381 409]
Adding edge 377 : [31 62]
Adding edge 378 : [238 338]
Adding edge 379 : [62 378]
Adding edge 380 : [310 378]
Adding edge 381 : [137 329]
Adding edge 382 : [133 329]
Adding edge 383 : [152 329]
Adding edge 384 : [13 329]
Adding edge 385 : [206 416]
Adding edge 386 : [236 265]
Adding edge 387 : [248 405]
Adding edge 388 : [75 298]
Adding edge 389 : [209 242]
Adding edge 390 : [267 342]
Adding edge 391 : [191 267]
Adding edge 392 : [267 397]
Adding edge 393 : [233 397]
Adding edge 394 : [32 451]
Adding edge 395 : [443 451]
Adding edge 396 : [57 292]
Adding edge 397 : [277 292]
Adding edge 398 : [292 479]
Adding edge 399 : [292 467]
Adding edge 400 : [292 469]
Adding edge 401 : [237 277]
Adding edge 402 : [229 237]
Adding edge 403 : [361 467]
Adding edge 404 : [293 361]
Adding edge 405 : [290 293]
Adding edge 406 : [190 237]
Adding edge 407 : [72 190]
Adding edge 408 : [219 479]
Adding edge 409 : [219 430]
Adding edge 410 : [125 280]
Adding edge 411 : [79 280]
Adding edge 412 : [160 260]
Adding edge 413 : [120 160]
Adding edge 414 : [120 346]
Adding edge 415 : [346 386]
Adding edge 416 : [386 484]
Adding edge 417 : [120 213]
Adding edge 418 : [228 385]
Adding edge 419 : [221 228]
Adding edge 420 : [1 228]
Adding edge 421 : [1 167]
Adding edge 422 : [325 437]
Adding edge 423 : [38 325]
Adding edge 424 : [38 477]
Adding edge 425 : [38 81]
Adding edge 426 : [33 188]
Adding edge 427 : [193 245]
Adding edge 428 : [193 339]
Adding edge 429 : [236 324]
Adding edge 430 : [373 376]
Adding edge 431 : [137 420]
Adding edge 432 : [17 420]
Adding edge 433 : [17 337]
Adding edge 434 : [17 459]
Adding edge 435 : [17 389]
Adding edge 436 : [348 420]
Adding edge 437 : [17 131]
Adding edge 438 : [17 499]
Adding edge 439 : [17 482]
Adding edge 440 : [244 482]
Adding edge 441 : [321 482]
Adding edge 442 : [106 482]
Adding edge 443 : [106 266]
Adding edge 444 : [208 321]
Adding edge 445 : [208 331]
Adding edge 446 : [208 425]
Adding edge 447 : [132 420]
Adding edge 448 : [27 132]
Adding edge 449 : [132 483]
Adding edge 450 : [45 132]
Adding edge 451 : [252 459]
Adding edge 452 : [17 261]
Adding edge 453 : [261 270]
Adding edge 454 : [123 208]
Adding edge 455 : [348 374]
Adding edge 456 : [170 482]
Adding edge 457 : [260 439]
Adding edge 458 : [117 321]
Adding edge 459 : [230 353]
Adding edge 460 : [294 486]
Adding edge 461 : [183 486]
Adding edge 462 : [130 183]
Adding edge 463 : [185 486]
Adding edge 464 : [334 486]
Adding edge 465 : [185 404]
Adding edge 466 : [384 486]
Adding edge 467 : [384 415]
Adding edge 468 : [336 415]
Adding edge 469 : [183 427]
Adding edge 470 : [185 240]
Adding edge 471 : [210 334]
Adding edge 472 : [76 84]
Adding edge 473 : [76 205]
Adding edge 474 : [76 442]
Adding edge 475 : [109 394]
Adding edge 476 : [109 349]
Adding edge 477 : [109 345]
Adding edge 478 : [180 345]
Adding edge 479 : [176 200]
Adding edge 480 : [118 200]
Adding edge 481 : [28 211]
Adding edge 482 : [119 347]
Adding edge 483 : [58 347]
Adding edge 484 : [223 347]
Adding edge 485 : [58 367]
Adding edge 486 : [58 216]
Adding edge 487 : [58 257]
Adding edge 488 : [212 216]
Adding edge 489 : [257 303]
Adding edge 490 : [347 391]
Adding edge 491 : [154 347]
Adding edge 492 : [154 269]
Adding edge 493 : [154 375]
Adding edge 494 : [201 375]
Adding edge 495 : [269 402]
Adding edge 496 : [141 367]
Adding edge 497 : [108 216]
Adding edge 498 : [257 496]
Adding edge 499 : [452 496]
Adding edge 500 : [253 452]
extract-genealogy-from-graph 500
prune-leaves 248 500
prune-leaves 106 252
prune-leaves 57 146
prune-leaves 34 89
prune-leaves 26 55
prune-leaves 14 29
prune-leaves 6 15
prune-leaves 5 9
prune-leaves 3 4
"Elapsed time: 5687.469 msecs"
tbl.local # ls
README classes
bitvectors-genes.data.small lib
bitvectors-genes.data.small.gz project.clj
bitvectors-parents.data.small src
bitvectors-parents.data.small.txt test
tbl.local #