Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Possible bug in SimpleLocal #121

Open
kfoynt opened this issue Apr 30, 2020 · 4 comments
Open

Possible bug in SimpleLocal #121

kfoynt opened this issue Apr 30, 2020 · 4 comments

Comments

@kfoynt
Copy link
Owner

kfoynt commented Apr 30, 2020

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
Copy link
Collaborator

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
Copy link
Owner Author

kfoynt commented Apr 30, 2020

ok, so should we close this?

@MengLiuPurdue
Copy link
Collaborator

Yeah, I think so.

@kfoynt kfoynt closed this as completed Apr 30, 2020
@kfoynt kfoynt reopened this Apr 30, 2020
@kfoynt
Copy link
Owner Author

kfoynt commented Apr 30, 2020

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants