search

ls-cwi / heinz

Single species module discovery
MIT License
13 stars 8 forks source link

Wrong answer #1

Closed alexloboda closed 9 years ago

alexloboda commented 9 years ago

Hi,

I think the latest version of your program give wrong answer on some tests. (Your release v2.0 doesn't suffer from this problems). Seems that problem in preprocessing. Nodes:

A 2.0
B 0.0
C 0.0
D 0.0

Edges:

B C 0.0
C D 0.0

It's clear to see that zero subgraph can't be maximum in a graph with positive vertex,

In second test case heinz give unconnected answer, that more weighted than optimum. Nodes:

2 7.0
5 14.0
6 -1.0
7 -3.0
8 -1.0
9 -6.0
10 0.0
11 -5.0
12 -4.0

Edges:

2 6 0.0
2 7 0.0
5 8 0.0
5 9 0.0
6 11 0.0
8 11 0.0
7 11 0.0
9 11 0.0
7 12 0.0
9 12 0.0

Thank you and excuse my bad English.

melkebir commented 9 years ago

Thank you for the bug report, I can reproduce it. It has to do with the enumeration scheme. More soon...

melkebir commented 9 years ago

Commit 0da737a1d8412e4f87351f0a8b9fee8c867fe4a3 resolves these two bugs. Thank you for the report and the small examples, they were very helpful.

The first bug had to do with a degenerate case in the divide-and-conquer scheme where all the nodes have nonpositive weight and are disconnected.

The second bug had to do with the gadget, which is only valid for triconnected components where the cut vertices are not adjacent.