search

maxdan94 / HkS

C code to compute a Heaviest k-Subgraph or an approximation
MIT License
4 stars 0 forks source link

There is a problem with bb_dks #1

Open marcinmachura opened 6 years ago

marcinmachura commented 6 years ago

For the following graph: 0 0 30 1 2 10 2 1 10 4 4 0.1 command bb_dks 3 test.txt returns this: Reading weighted edgelist from file test.txt Relabeling edgelist Number of nodes = 4 Number of edges = 4 Building the graph structure Core value of the graph <= 2 Building the heap structure Computing DkS Printing results val: 3.0000000000e+01 size: 2

nodes: 0 0 Releasing memory

It is not working correctly if with edge being a looplf

maxdan94 commented 6 years ago

Thanks for your feedback. You are right, I have added "NO SELF-LOOP!" in the readme. I think it can be modified to work with self-loops if you need, but I do not have the time to do it now.

marcinmachura commented 6 years ago

Thanks! Is bb_dks really working on directed graphs? In this case: 0 1 0.328782 0 2 0.904175 0 3 0.297884 1 0 0.328782 1 2 0.967757 1 3 0.803399 2 0 0.904175 2 1 0.967757 2 3 0.345865 3 0 0.297884 3 1 0.803399 3 2 0.345865 it reports correct answer (1,2) with incorrect sum of 0.9.67 It just counts edge once.

maxdan94 commented 6 years ago

NO SELF-LOOP and ONLY SIMPLE EDGES! :)

marcinmachura commented 6 years ago

ok, apart from that it works exactly the same as my naïve python solution:)

maxdan94 commented 6 years ago

Nice! Have you tried on a large real graph (e.g. 100M weighted edges)? That is when our algorithm becomes useful.