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) Duplicates are removed. The input is randomized. buckets implementation external bucket block size = 512 KB external bucket page size = 1 block(s) internal buckets: no of blocks = 1500000 internal buckets: edges per block = 8 -------------------- 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 = 6 #edges = 1.13e+09 #nodes which fit in internal memory = 1.60e+08 -------------------- EVENTS total time: 0.00000 sec., section time: 0.00000 sec. - begin total time: 16245.43214 sec., section time: 16245.43214 sec. - graph generated/imported total time: 17275.35417 sec., section time: 1029.92202 sec. - edges distributed to external buckets total time: 18472.77855 sec., section time: 1197.42439 sec. - nodes reduced total time: 19047.54629 sec., section time: 574.76774 sec. - Kruskal: edges sorted total time: 19050.69434 sec., section time: 3.14805 sec. - Kruskal: data structures initialized total time: 20371.33538 sec., section time: 1320.64104 sec. - Kruskal: edges processed total time: 20371.48124 sec., section time: 0.14586 sec. - end -------------------- BUCKETS 88 #nodes=1.8e+06 #edges=1.1e+07 #edgesProcessed=1.1e+07 capacity=1.6e+07 (factor 1.4) #free blocks=1.3e+06 used memory=515 MB (58%) 87 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.6e+07 (factor 1.3) #free blocks=1.3e+06 used memory=515 MB (58%) 86 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.6e+07 (factor 1.3) #free blocks=1.3e+06 used memory=514 MB (58%) 85 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.6e+07 (factor 1.3) #free blocks=1.3e+06 used memory=513 MB (58%) 84 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.6e+07 (factor 1.3) #free blocks=1.3e+06 used memory=513 MB (58%) 83 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.6e+07 (factor 1.3) #free blocks=1.3e+06 used memory=512 MB (58%) 82 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.6e+07 (factor 1.3) #free blocks=1.2e+06 used memory=512 MB (58%) 81 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=511 MB (58%) 80 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=511 MB (57%) 79 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=510 MB (57%) 78 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=510 MB (57%) 77 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=509 MB (57%) 76 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=509 MB (57%) 75 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=508 MB (57%) 74 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=508 MB (57%) 73 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=507 MB (57%) 72 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.3e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.2e+06 used memory=507 MB (57%) 71 #nodes=1.8e+06 #edges=1.3e+07 #edgesProcessed=1.4e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.1e+06 used memory=506 MB (57%) 70 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.1e+06 used memory=506 MB (57%) 69 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.1e+06 used memory=505 MB (57%) 68 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.1e+06 used memory=505 MB (57%) 67 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.7e+07 (factor 1.3) #free blocks=1.1e+06 used memory=504 MB (57%) 66 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.1e+06 used memory=504 MB (57%) 65 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.1e+06 used memory=503 MB (57%) 64 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.1e+06 used memory=503 MB (57%) 63 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.1e+06 used memory=502 MB (57%) 62 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.1e+06 used memory=502 MB (56%) 61 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.1e+06 used memory=501 MB (56%) 60 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.1e+06 used memory=501 MB (56%) 59 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.0e+06 used memory=500 MB (56%) 58 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.0e+06 used memory=500 MB (56%) 57 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.0e+06 used memory=499 MB (56%) 56 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.0e+06 used memory=499 MB (56%) 55 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.0e+06 used memory=498 MB (56%) 54 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.0e+06 used memory=498 MB (56%) 53 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=1.0e+06 used memory=497 MB (56%) 52 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.8e+07 (factor 1.3) #free blocks=9.9e+05 used memory=497 MB (56%) 51 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.9e+05 used memory=496 MB (56%) 50 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.8e+05 used memory=496 MB (56%) 49 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.7e+05 used memory=495 MB (56%) 48 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.6e+05 used memory=495 MB (56%) 47 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.5e+05 used memory=494 MB (56%) 46 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.5e+05 used memory=494 MB (56%) 45 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.4e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.4e+05 used memory=493 MB (55%) 44 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.3e+05 used memory=493 MB (55%) 43 #nodes=1.8e+06 #edges=1.4e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.3e+05 used memory=492 MB (55%) 42 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.2e+05 used memory=492 MB (55%) 41 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.1e+05 used memory=491 MB (55%) 40 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.1e+05 used memory=491 MB (55%) 39 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=9.0e+05 used memory=490 MB (55%) 38 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=8.9e+05 used memory=490 MB (55%) 37 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=8.9e+05 used memory=489 MB (55%) 36 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=8.8e+05 used memory=489 MB (55%) 35 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=8.8e+05 used memory=488 MB (55%) 34 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=1.9e+07 (factor 1.3) #free blocks=8.7e+05 used memory=488 MB (55%) 33 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.6e+05 used memory=487 MB (55%) 32 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.6e+05 used memory=487 MB (55%) 31 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.5e+05 used memory=486 MB (55%) 30 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.5e+05 used memory=486 MB (55%) 29 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.4e+05 used memory=485 MB (55%) 28 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.3e+05 used memory=485 MB (55%) 27 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.3e+05 used memory=484 MB (54%) 26 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.2e+05 used memory=484 MB (54%) 25 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.2e+05 used memory=483 MB (54%) 24 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.1e+05 used memory=483 MB (54%) 23 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.1e+05 used memory=482 MB (54%) 22 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.0e+05 used memory=482 MB (54%) 21 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=8.0e+05 used memory=481 MB (54%) 20 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.9e+05 used memory=481 MB (54%) 19 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.9e+05 used memory=480 MB (54%) 18 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.8e+05 used memory=480 MB (54%) 17 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.8e+05 used memory=479 MB (54%) 16 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.8e+05 used memory=479 MB (54%) 15 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.7e+05 used memory=478 MB (54%) 14 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.7e+05 used memory=478 MB (54%) 13 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.6e+05 used memory=477 MB (54%) 12 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.6e+05 used memory=477 MB (54%) 11 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.6e+05 used memory=476 MB (54%) 10 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.5e+05 used memory=476 MB (53%) 9 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.5e+05 used memory=475 MB (53%) 8 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.4e+05 used memory=475 MB (53%) 7 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.3) #free blocks=7.4e+05 used memory=474 MB (53%) 6 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.0e+07 (factor 1.4) #free blocks=7.4e+05 used memory=474 MB (53%) 5 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.1e+07 (factor 1.4) #free blocks=7.4e+05 used memory=473 MB (53%) 4 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.1e+07 (factor 1.4) #free blocks=7.3e+05 used memory=473 MB (53%) 3 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.1e+07 (factor 1.4) #free blocks=7.3e+05 used memory=472 MB (53%) 2 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.1e+07 (factor 1.4) #free blocks=7.3e+05 used memory=472 MB (53%) 1 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.1e+07 (factor 1.4) #free blocks=7.2e+05 used memory=471 MB (53%) 0 #nodes=1.8e+06 #edges=1.5e+07 #edgesProcessed=1.5e+07 capacity=2.1e+07 (factor 1.4) #free blocks=7.2e+05 used memory=471 MB (53%) -1 #nodes=1.6e+08 #edges=6.8e+08 #edgesProcessed=0.0e+00 capacity=0.0e+00 (factor 0.0) #free blocks=-1.0e+00 used memory=0 MB (53%) max total capacity = 20615728 / max factor = 1.4 -------------------- RESULT Minimum Spanning Tree: total weight = 505785604224 #edges = 319999916 -------------------- PROCESSED EDGES reducing of nodes: #edges read or written = 4.345e+09 (82882 MB) #edges processed = 1.275e+09 expected #edges processed = 1.564e+09 -------------------- TIMING total time = 4.12605e+03 sec. time / m = 3.65616e-06 sec. time / (m ln m) = 1.75404e-07 sec. [m = #edges] -------------------- DUPLICATES #duplicates removed = 204136368 --------------------