Opened 13 years ago

Closed 13 years ago

Last modified 12 years ago

#3929 closed enhancement (duplicate)

Merge the max-flow min-cut code from Scott Clifford and Jerin Schneider

Reported by: jason Owned by: rlm
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: graph theory Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Change History (6)

comment:1 Changed 13 years ago by jason

See #1317 for this request. I think implementing this might close #1317

comment:2 Changed 13 years ago by rlm

Jason,

You need to stop polluting trac like this. If there was already a ticket for this, you should have put your comments there. Also, I'd like to point out how annoying it is when someone opens a bunch of wishlist tickets with no intention of supplying any patches.

-- Robert

comment:3 follow-up: Changed 13 years ago by rlm

Also, based on the presentation I saw from these two people, it is questionable whether we want to find a more standard implementation of this algorithm (as they are a dime a dozen, and maybe not all of them were undergraduate projects...).

comment:4 Changed 13 years ago by jason

  • Milestone changed from sage-3.1.2 to sage-wishlist
  • Resolution set to duplicate
  • Status changed from new to closed

Sorry. I didn't remember there was already a ticket for this until I was going through tickets the other day; apparently I should have searched more carefully. The reason I opened a few tickets is because I saw that it looked like there was work that could be included and didn't want to lose the reference (especially for this ticket, which is something that would be nice to have).

However, I think in this case a post to sage-devel asking about the projects from the wiki page would have been better than to create tickets for each one. Sorry for the annoyance.

Third, I do intend to post patches eventually, if someone else doesn't beat me to it. As I have time, I go through all the tickets I've entered and work on patches. The reason to put them up on trac is to make sure that the idea doesn't get lost. I do agree that I opened up a lot of wishlist tickets (probably too many) when I first started with Sage in my eagerness, but I tried to assign them to the wishlist milestone, which has the purpose: "We have many tickets for enhancements in trac that depend on somebody with time to make them happen. In order not to lose them we collect them under this milestone. If you are interested in working on one of the tickets in this category please let us know or retag that ticket to an appropriate milestone." (maybe I ought to put more tickets under this wishlist, though...)

Given your comments, I'm going to close this as a duplicate, though, and note the link on #1317. Thanks.

comment:5 Changed 13 years ago by mabshoff

  • Milestone changed from sage-wishlist to sage-duplicate/invalid

comment:6 in reply to: ↑ 3 Changed 12 years ago by mvngu

Replying to rlm:

Also, based on the presentation I saw from these two people, it is questionable whether we want to find a more standard implementation of this algorithm (as they are a dime a dozen, and maybe not all of them were undergraduate projects...).

From my reading of the source code, it looks like the code is using the Ford-Fulkerson algorithm, which is pretty bad for some corner cases. And its complexity is in general not polynomial. Of course, one obvious way to get polynomial complexity is to use the modified algorithm by Edmonds and Karp. Chapter 6 from the following text is very relevant to this ticket.

  • D. Jungnickel. Graphs, Networks and Algorithms. 3rd edition, Springer, 2008.
Note: See TracTickets for help on using tickets.