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 -------------------- GEOMETRIC GRAPH #nodes = 3.20e+08 #neighbours = 3 #edges = 5.96e+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: 7383.44906 sec., section time: 7383.44906 sec. - graph generated/imported total time: 7929.04561 sec., section time: 545.59655 sec. - edges distributed to external buckets total time: 8534.16612 sec., section time: 605.12051 sec. - nodes reduced total time: 8799.27429 sec., section time: 265.10817 sec. - Kruskal: edges sorted total time: 8802.36955 sec., section time: 3.09526 sec. - Kruskal: data structures initialized total time: 9558.31490 sec., section time: 755.94536 sec. - Kruskal: edges processed total time: 9558.45841 sec., section time: 0.14351 sec. - end -------------------- BUCKETS 106 #nodes=1.5e+06 #edges=3.7e+06 #edgesProcessed=3.7e+06 capacity=1.2e+07 (factor 3.2) #free blocks=2.2e+06 used memory=571 MB (64%) 105 #nodes=1.5e+06 #edges=5.6e+06 #edgesProcessed=5.6e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=571 MB (64%) 104 #nodes=1.5e+06 #edges=5.6e+06 #edgesProcessed=5.6e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=570 MB (64%) 103 #nodes=1.5e+06 #edges=5.6e+06 #edgesProcessed=5.6e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=570 MB (64%) 102 #nodes=1.5e+06 #edges=5.6e+06 #edgesProcessed=5.6e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=569 MB (64%) 101 #nodes=1.5e+06 #edges=5.6e+06 #edgesProcessed=5.7e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=569 MB (64%) 100 #nodes=1.5e+06 #edges=5.6e+06 #edgesProcessed=5.7e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=568 MB (64%) 99 #nodes=1.5e+06 #edges=5.7e+06 #edgesProcessed=5.7e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=568 MB (64%) 98 #nodes=1.5e+06 #edges=5.7e+06 #edgesProcessed=5.7e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=567 MB (64%) 97 #nodes=1.5e+06 #edges=5.7e+06 #edgesProcessed=5.7e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=567 MB (64%) 96 #nodes=1.5e+06 #edges=5.7e+06 #edgesProcessed=5.7e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=566 MB (64%) 95 #nodes=1.5e+06 #edges=5.7e+06 #edgesProcessed=5.7e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=566 MB (64%) 94 #nodes=1.5e+06 #edges=5.7e+06 #edgesProcessed=5.7e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=565 MB (64%) 93 #nodes=1.5e+06 #edges=5.7e+06 #edgesProcessed=5.7e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=564 MB (64%) 92 #nodes=1.5e+06 #edges=5.7e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=564 MB (63%) 91 #nodes=1.5e+06 #edges=5.7e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=563 MB (63%) 90 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=563 MB (63%) 89 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=562 MB (63%) 88 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=562 MB (63%) 87 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=561 MB (63%) 86 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=561 MB (63%) 85 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=560 MB (63%) 84 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=560 MB (63%) 83 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.8e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=559 MB (63%) 82 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=559 MB (63%) 81 #nodes=1.5e+06 #edges=5.8e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=558 MB (63%) 80 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=558 MB (63%) 79 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.1) #free blocks=2.2e+06 used memory=557 MB (63%) 78 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=557 MB (63%) 77 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=556 MB (63%) 76 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=556 MB (63%) 75 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=555 MB (63%) 74 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=555 MB (62%) 73 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=554 MB (62%) 72 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=5.9e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=554 MB (62%) 71 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=6.0e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=553 MB (62%) 70 #nodes=1.5e+06 #edges=5.9e+06 #edgesProcessed=6.0e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=553 MB (62%) 69 #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=552 MB (62%) 68 #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=552 MB (62%) 67 #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=551 MB (62%) 66 #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=551 MB (62%) 65 #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=550 MB (62%) 64 #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=550 MB (62%) 63 #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=549 MB (62%) 62 #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=549 MB (62%) 61 #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=548 MB (62%) 60 #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=548 MB (62%) 59 #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=547 MB (62%) 58 #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=547 MB (62%) 57 #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=546 MB (61%) 56 #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=546 MB (61%) 55 #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=545 MB (61%) 54 #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=545 MB (61%) 53 #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=544 MB (61%) 52 #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=544 MB (61%) 51 #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=543 MB (61%) 50 #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=542 MB (61%) 49 #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=542 MB (61%) 48 #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=541 MB (61%) 47 #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=541 MB (61%) 46 #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=540 MB (61%) 45 #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=540 MB (61%) 44 #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=539 MB (61%) 43 #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=539 MB (61%) 42 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=538 MB (61%) 41 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=538 MB (61%) 40 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=537 MB (60%) 39 #nodes=1.5e+06 #edges=6.1e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=537 MB (60%) 38 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=536 MB (60%) 37 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=536 MB (60%) 36 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=535 MB (60%) 35 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=535 MB (60%) 34 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=534 MB (60%) 33 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=534 MB (60%) 32 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=533 MB (60%) 31 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=533 MB (60%) 30 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=532 MB (60%) 29 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=532 MB (60%) 28 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=531 MB (60%) 27 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=531 MB (60%) 26 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 2.0) #free blocks=2.2e+06 used memory=530 MB (60%) 25 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=530 MB (60%) 24 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=529 MB (60%) 23 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=529 MB (59%) 22 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=528 MB (59%) 21 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=528 MB (59%) 20 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=527 MB (59%) 19 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=527 MB (59%) 18 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=526 MB (59%) 17 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=526 MB (59%) 16 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.2e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=525 MB (59%) 15 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=525 MB (59%) 14 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=524 MB (59%) 13 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=524 MB (59%) 12 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=523 MB (59%) 11 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=523 MB (59%) 10 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=522 MB (59%) 9 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=522 MB (59%) 8 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=521 MB (59%) 7 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=521 MB (59%) 6 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=520 MB (59%) 5 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=520 MB (58%) 4 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=519 MB (58%) 3 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=519 MB (58%) 2 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=518 MB (58%) 1 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=518 MB (58%) 0 #nodes=1.5e+06 #edges=6.2e+06 #edgesProcessed=6.3e+06 capacity=1.2e+07 (factor 1.9) #free blocks=2.2e+06 used memory=517 MB (58%) -1 #nodes=1.6e+08 #edges=3.3e+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 = 12108504 / max factor = 3.2 -------------------- RESULT Minimum Spanning Tree: total weight = 509248148003 #edges = 319366497 -------------------- PROCESSED EDGES reducing of nodes: #edges read or written = 2.214e+09 (42223 MB) #edges processed = 6.441e+08 expected #edges processed = 8.267e+08 -------------------- TIMING total time = 2.17501e+03 sec. time / m = 3.64743e-06 sec. time / (m ln m) = 1.80510e-07 sec. [m = #edges] -------------------- DUPLICATES #duplicates removed = 44353573 --------------------