search

kfoynt / LocalGraphClustering

MIT License
136 stars 46 forks source link

Possible bug in SimpleLocal #121

Open kfoynt opened 4 years ago

kfoynt commented 4 years ago

A student of mine is working on the SimpleLocal code. He mentioned to me the following:

"There is a bug in STAGEFLOW method in SimpleLocal.cpp. When the graph is being constructed at each stage, 4 edges are added between vertices instead of two (i.e., two edges are added from u to v and two edges are added from v to u)."

You might want to have a look at this.

MengLiuPurdue commented 4 years ago

That's because the maxflow code I referenced was initially designed for directed graphs. So I think of each undirected edge as two directed edges and add on forward edge and one backward edge for each directed edge. It might be possible to use only two edges, but I just find this is easier to understand and implement.

kfoynt commented 4 years ago

ok, so should we close this?

MengLiuPurdue commented 4 years ago

Yeah, I think so.

kfoynt commented 4 years ago

Meng, here is the reply that I got

"But even for the case of directed edges, it is still wrong, because it adds two edges (one forward edge and one backward edge) each of capacity C for each directed edge in the graph. The backward edge (i.e., the one that does not exist in the input graph) should have the capacity of 0."

Any feedback on this?