igraph

Minimum s-t cut

Bug #291196 reported by Gábor Csárdi
2
Affects Status Importance Assigned to Milestone
igraph
Fix Released
High
Gábor Csárdi

Bug Description

The cut itself, not just the value. Basically this means calculating the actual maximum flow in the push-relabel algorithm, not just the flow value.

Related branches

lp:~igraph/igraph/0.6-maxflow (Merged)
Revision history for this message
Gábor Csárdi (gabor.csardi) wrote :

Continued from http://code.google.com/p/igraph/issues/detail?id=58

Changed in igraph:
assignee: nobody → gabor.csardi
importance: Undecided → High
status: New → Confirmed
Revision history for this message
Gábor Csárdi (gabor.csardi) wrote :

OK, the core of this is done, i.e. the igraph_maxflow function is now able to calculate the flow for directed graphs. Now other functions that call this should be updated as well, e.g. igraph_mincut, the undirected maximum flow solver, etc.

Changed in igraph:
status: Confirmed → In Progress
Revision history for this message
Gábor Csárdi (gabor.csardi) wrote :

OK, flow and cut calculation works for undirected graphs as well now.

Revision history for this message
Gábor Csárdi (gabor.csardi) wrote :

This seems to be complete. Will merge it to igraph-main.

Changed in igraph:
status: In Progress → Fix Committed
status: Fix Committed → Fix Released
Revision history for this message
Gábor Csárdi (gabor.csardi) wrote : Continue on github

The development of igraph has moved to github, so please do not comment on this bug here. You are of course welcome to comment on github, here:
https://github.com/igraph/igraph/issues/22

To post a comment you must log in.
This report contains Public information  
Everyone can see this information.
Subscribing...

Other bug subscribers

Remote bug watches

Bug watches keep track of this bug in other bug trackers.