search

cmuparlay / parlaylib

A Toolkit for Programming Parallel Algorithms on Shared-Memory Multicore Machines
MIT License
320 stars 60 forks source link

Puzzle: Confused about the kcore reordering used in CliqueCounting #64

Closed xisalt closed 1 year ago

xisalt commented 1 year ago

In benchmarks/CliqueCounting/Clique.h, I tried to get the reordered graph after relabel_graph like this. image

And I got the following log after running cmd: bazel run benchmarks/CliqueCounting:Clique_main -- -rounds 1 -k 4 --directType KCORE --parallelType VERT -s /root/gbbs/inputs/com-lj.ungraph.adj

image

What makes me confused is that k_{max} = 360, but the max_degree in reordered graph is 9022. Also, in one paper, it says that the com-lj's max degree is 360 after KCORE pre-processing. (Actually, I haven't fully understood what KCORE does to reduce the max degree, so I am quite confused.)

Hope that you could help me clarify my confusion. Thanks!

xisalt commented 1 year ago

Sorry, I issued under the wrong repository. Please just ignore it.