CONFIGURATION internal memory for sorting = 650 MB EdgeVector default block size = 2048 KB EdgeVector default #pages = 1 EdgeVector default page size = 4 block(s) MST vector block size = 2048 KB MST vector #pages = 1 MST vector page size = 4 block(s) external bucket block size = 512 KB external bucket page size = 1 block(s) internal buckets: no of blocks = 2200000 internal buckets: edges per block = 8 Duplicates are removed. The input is randomized. -------------------- STXXL-DISK-CONFIGURATION (.stxxl) disk=/mnt/hdq/stxxl,70000,syscall disk=/mnt/hdi/stxxl,70000,syscall disk=/mnt/hdk/stxxl,70000,syscall disk=/mnt/hde/stxxl,70000,syscall -------------------- RANDOM GRAPH #nodes = 3.20e+08 #edges = 6.40e+08 #buckets = 108 #nodes which fit in internal memory = 1.60e+08 -------------------- EVENTS total time: 0.00000 sec., section time: 0.00000 sec. - begin total time: 750.22016 sec., section time: 750.22016 sec. - graph generated/imported total time: 1350.96816 sec., section time: 600.74800 sec. - edges distributed to external buckets total time: 2202.53378 sec., section time: 851.56562 sec. - nodes reduced total time: 2611.60974 sec., section time: 409.07596 sec. - Kruskal: edges sorted total time: 2614.69397 sec., section time: 3.08423 sec. - Kruskal: data structures initialized total time: 3523.46360 sec., section time: 908.76963 sec. - Kruskal: edges processed total time: 3523.60633 sec., section time: 0.14272 sec. - end -------------------- BUCKETS 106 #nodes=1.5e+06 #edges=4.0e+06 #edgesProcessed=4.0e+06 capacity=1.2e+07 (factor 3.0) #free blocks=2.2e+06 used memory=567 MB (64%) 105 #nodes=1.5e+06 #edges=6.0e+06 #edgesProcessed=6.0e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=566 MB (64%) 104 #nodes=1.5e+06 #edges=6.0e+06 #edgesProcessed=6.0e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=566 MB (64%) 103 #nodes=1.5e+06 #edges=6.0e+06 #edgesProcessed=6.0e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=565 MB (64%) 102 #nodes=1.5e+06 #edges=6.0e+06 #edgesProcessed=6.1e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=565 MB (64%) 101 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.1e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=564 MB (64%) 100 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.1e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=564 MB (63%) 99 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.1e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=563 MB (63%) 98 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.1e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=563 MB (63%) 97 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.1e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=562 MB (63%) 96 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.1e+06 used memory=562 MB (63%) 95 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.1e+06 used memory=561 MB (63%) 94 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.1e+06 used memory=561 MB (63%) 93 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.1e+06 used memory=560 MB (63%) 92 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.1e+06 used memory=560 MB (63%) 91 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.1e+06 used memory=559 MB (63%) 90 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.1e+06 used memory=559 MB (63%) 89 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=558 MB (63%) 88 #nodes=1.5e+06 #edges=6.3e+06 #edgesProcessed=6.3e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=558 MB (63%) 87 #nodes=1.5e+06 #edges=6.3e+06 #edgesProcessed=6.3e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=557 MB (63%) 86 #nodes=1.5e+06 #edges=6.3e+06 #edgesProcessed=6.3e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=557 MB (63%) 85 #nodes=1.5e+06 #edges=6.3e+06 #edgesProcessed=6.3e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=556 MB (63%) 84 #nodes=1.5e+06 #edges=6.3e+06 #edgesProcessed=6.4e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=556 MB (63%) 83 #nodes=1.5e+06 #edges=6.3e+06 #edgesProcessed=6.4e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=555 MB (63%) 82 #nodes=1.5e+06 #edges=6.4e+06 #edgesProcessed=6.4e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=555 MB (62%) 81 #nodes=1.5e+06 #edges=6.4e+06 #edgesProcessed=6.4e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=554 MB (62%) 80 #nodes=1.5e+06 #edges=6.4e+06 #edgesProcessed=6.4e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=554 MB (62%) 79 #nodes=1.5e+06 #edges=6.4e+06 #edgesProcessed=6.4e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=553 MB (62%) 78 #nodes=1.5e+06 #edges=6.4e+06 #edgesProcessed=6.5e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=553 MB (62%) 77 #nodes=1.5e+06 #edges=6.5e+06 #edgesProcessed=6.5e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=552 MB (62%) 76 #nodes=1.5e+06 #edges=6.5e+06 #edgesProcessed=6.5e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=552 MB (62%) 75 #nodes=1.5e+06 #edges=6.5e+06 #edgesProcessed=6.5e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=551 MB (62%) 74 #nodes=1.5e+06 #edges=6.5e+06 #edgesProcessed=6.5e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=551 MB (62%) 73 #nodes=1.5e+06 #edges=6.5e+06 #edgesProcessed=6.6e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=550 MB (62%) 72 #nodes=1.5e+06 #edges=6.6e+06 #edgesProcessed=6.6e+06 capacity=1.3e+07 (factor 2.0) #free blocks=2.1e+06 used memory=550 MB (62%) 71 #nodes=1.5e+06 #edges=6.6e+06 #edgesProcessed=6.6e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=549 MB (62%) 70 #nodes=1.5e+06 #edges=6.6e+06 #edgesProcessed=6.6e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=549 MB (62%) 69 #nodes=1.5e+06 #edges=6.6e+06 #edgesProcessed=6.6e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=548 MB (62%) 68 #nodes=1.5e+06 #edges=6.6e+06 #edgesProcessed=6.7e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=548 MB (62%) 67 #nodes=1.5e+06 #edges=6.7e+06 #edgesProcessed=6.7e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=547 MB (62%) 66 #nodes=1.5e+06 #edges=6.7e+06 #edgesProcessed=6.7e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=547 MB (62%) 65 #nodes=1.5e+06 #edges=6.7e+06 #edgesProcessed=6.7e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=546 MB (61%) 64 #nodes=1.5e+06 #edges=6.7e+06 #edgesProcessed=6.8e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=546 MB (61%) 63 #nodes=1.5e+06 #edges=6.7e+06 #edgesProcessed=6.8e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=545 MB (61%) 62 #nodes=1.5e+06 #edges=6.8e+06 #edgesProcessed=6.8e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=545 MB (61%) 61 #nodes=1.5e+06 #edges=6.8e+06 #edgesProcessed=6.8e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=544 MB (61%) 60 #nodes=1.5e+06 #edges=6.8e+06 #edgesProcessed=6.8e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=544 MB (61%) 59 #nodes=1.5e+06 #edges=6.8e+06 #edgesProcessed=6.9e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=543 MB (61%) 58 #nodes=1.5e+06 #edges=6.9e+06 #edgesProcessed=6.9e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=543 MB (61%) 57 #nodes=1.5e+06 #edges=6.9e+06 #edgesProcessed=6.9e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=542 MB (61%) 56 #nodes=1.5e+06 #edges=6.9e+06 #edgesProcessed=6.9e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=542 MB (61%) 55 #nodes=1.5e+06 #edges=6.9e+06 #edgesProcessed=7.0e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=541 MB (61%) 54 #nodes=1.5e+06 #edges=7.0e+06 #edgesProcessed=7.0e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.1e+06 used memory=541 MB (61%) 53 #nodes=1.5e+06 #edges=7.0e+06 #edgesProcessed=7.0e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=540 MB (61%) 52 #nodes=1.5e+06 #edges=7.0e+06 #edgesProcessed=7.0e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=540 MB (61%) 51 #nodes=1.5e+06 #edges=7.0e+06 #edgesProcessed=7.1e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=539 MB (61%) 50 #nodes=1.5e+06 #edges=7.1e+06 #edgesProcessed=7.1e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=539 MB (61%) 49 #nodes=1.5e+06 #edges=7.1e+06 #edgesProcessed=7.1e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=538 MB (61%) 48 #nodes=1.5e+06 #edges=7.1e+06 #edgesProcessed=7.1e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=538 MB (61%) 47 #nodes=1.5e+06 #edges=7.1e+06 #edgesProcessed=7.2e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=537 MB (60%) 46 #nodes=1.5e+06 #edges=7.2e+06 #edgesProcessed=7.2e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=537 MB (60%) 45 #nodes=1.5e+06 #edges=7.2e+06 #edgesProcessed=7.2e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=536 MB (60%) 44 #nodes=1.5e+06 #edges=7.2e+06 #edgesProcessed=7.3e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=536 MB (60%) 43 #nodes=1.5e+06 #edges=7.2e+06 #edgesProcessed=7.3e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=535 MB (60%) 42 #nodes=1.5e+06 #edges=7.3e+06 #edgesProcessed=7.3e+06 capacity=1.3e+07 (factor 1.9) #free blocks=2.0e+06 used memory=535 MB (60%) 41 #nodes=1.5e+06 #edges=7.3e+06 #edgesProcessed=7.3e+06 capacity=1.4e+07 (factor 1.9) #free blocks=2.0e+06 used memory=534 MB (60%) 40 #nodes=1.5e+06 #edges=7.3e+06 #edgesProcessed=7.4e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=534 MB (60%) 39 #nodes=1.5e+06 #edges=7.4e+06 #edgesProcessed=7.4e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=533 MB (60%) 38 #nodes=1.5e+06 #edges=7.4e+06 #edgesProcessed=7.4e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=533 MB (60%) 37 #nodes=1.5e+06 #edges=7.4e+06 #edgesProcessed=7.5e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=532 MB (60%) 36 #nodes=1.5e+06 #edges=7.5e+06 #edgesProcessed=7.5e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=532 MB (60%) 35 #nodes=1.5e+06 #edges=7.5e+06 #edgesProcessed=7.5e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=531 MB (60%) 34 #nodes=1.5e+06 #edges=7.5e+06 #edgesProcessed=7.6e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=531 MB (60%) 33 #nodes=1.5e+06 #edges=7.6e+06 #edgesProcessed=7.6e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=530 MB (60%) 32 #nodes=1.5e+06 #edges=7.6e+06 #edgesProcessed=7.6e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=530 MB (60%) 31 #nodes=1.5e+06 #edges=7.6e+06 #edgesProcessed=7.7e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=529 MB (60%) 30 #nodes=1.5e+06 #edges=7.7e+06 #edgesProcessed=7.7e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=529 MB (59%) 29 #nodes=1.5e+06 #edges=7.7e+06 #edgesProcessed=7.7e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=528 MB (59%) 28 #nodes=1.5e+06 #edges=7.7e+06 #edgesProcessed=7.8e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=528 MB (59%) 27 #nodes=1.5e+06 #edges=7.8e+06 #edgesProcessed=7.8e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=527 MB (59%) 26 #nodes=1.5e+06 #edges=7.8e+06 #edgesProcessed=7.8e+06 capacity=1.4e+07 (factor 1.8) #free blocks=2.0e+06 used memory=527 MB (59%) 25 #nodes=1.5e+06 #edges=7.8e+06 #edgesProcessed=7.9e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=526 MB (59%) 24 #nodes=1.5e+06 #edges=7.9e+06 #edgesProcessed=7.9e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=526 MB (59%) 23 #nodes=1.5e+06 #edges=7.9e+06 #edgesProcessed=8.0e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=525 MB (59%) 22 #nodes=1.5e+06 #edges=7.9e+06 #edgesProcessed=8.0e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=525 MB (59%) 21 #nodes=1.5e+06 #edges=8.0e+06 #edgesProcessed=8.0e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=524 MB (59%) 20 #nodes=1.5e+06 #edges=8.0e+06 #edgesProcessed=8.1e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=524 MB (59%) 19 #nodes=1.5e+06 #edges=8.1e+06 #edgesProcessed=8.1e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=523 MB (59%) 18 #nodes=1.5e+06 #edges=8.1e+06 #edgesProcessed=8.2e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=523 MB (59%) 17 #nodes=1.5e+06 #edges=8.1e+06 #edgesProcessed=8.2e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=522 MB (59%) 16 #nodes=1.5e+06 #edges=8.2e+06 #edgesProcessed=8.2e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=522 MB (59%) 15 #nodes=1.5e+06 #edges=8.2e+06 #edgesProcessed=8.3e+06 capacity=1.4e+07 (factor 1.8) #free blocks=1.9e+06 used memory=521 MB (59%) 14 #nodes=1.5e+06 #edges=8.3e+06 #edgesProcessed=8.3e+06 capacity=1.4e+07 (factor 1.7) #free blocks=1.9e+06 used memory=521 MB (59%) 13 #nodes=1.5e+06 #edges=8.3e+06 #edgesProcessed=8.4e+06 capacity=1.4e+07 (factor 1.7) #free blocks=1.9e+06 used memory=520 MB (59%) 12 #nodes=1.5e+06 #edges=8.4e+06 #edgesProcessed=8.4e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.9e+06 used memory=520 MB (58%) 11 #nodes=1.5e+06 #edges=8.4e+06 #edgesProcessed=8.5e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.9e+06 used memory=519 MB (58%) 10 #nodes=1.5e+06 #edges=8.4e+06 #edgesProcessed=8.5e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.9e+06 used memory=519 MB (58%) 9 #nodes=1.5e+06 #edges=8.5e+06 #edgesProcessed=8.6e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.9e+06 used memory=518 MB (58%) 8 #nodes=1.5e+06 #edges=8.5e+06 #edgesProcessed=8.6e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.9e+06 used memory=518 MB (58%) 7 #nodes=1.5e+06 #edges=8.6e+06 #edgesProcessed=8.7e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.9e+06 used memory=517 MB (58%) 6 #nodes=1.5e+06 #edges=8.6e+06 #edgesProcessed=8.7e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.8e+06 used memory=517 MB (58%) 5 #nodes=1.5e+06 #edges=8.7e+06 #edgesProcessed=8.7e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.8e+06 used memory=516 MB (58%) 4 #nodes=1.5e+06 #edges=8.7e+06 #edgesProcessed=8.8e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.8e+06 used memory=516 MB (58%) 3 #nodes=1.5e+06 #edges=8.8e+06 #edgesProcessed=8.9e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.8e+06 used memory=515 MB (58%) 2 #nodes=1.5e+06 #edges=8.9e+06 #edgesProcessed=8.9e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.8e+06 used memory=515 MB (58%) 1 #nodes=1.5e+06 #edges=8.9e+06 #edgesProcessed=9.0e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.8e+06 used memory=514 MB (58%) 0 #nodes=1.5e+06 #edges=9.0e+06 #edgesProcessed=9.0e+06 capacity=1.5e+07 (factor 1.7) #free blocks=1.8e+06 used memory=514 MB (58%) -1 #nodes=1.6e+08 #edges=4.8e+08 #edgesProcessed=0.0e+00 capacity=0.0e+00 (factor 0.0) #free blocks=-1.0e+00 used memory=0 MB (58%) max total capacity = 15131176 / max factor = 3.0 -------------------- RESULT Minimum Spanning Tree: total weight = 88565703078876 #edges = 313664603 -------------------- PROCESSED EDGES reducing of nodes: #edges read or written = 2.647e+09 (50486 MB) #edges processed = 7.660e+08 expected #edges processed = 8.872e+08 -------------------- TIMING total time = 2.77339e+03 sec. time / m = 4.33342e-06 sec. time / (m ln m) = 2.13711e-07 sec. [m = #edges] -------------------- DUPLICATES #duplicates removed = 8 --------------------