Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

If I want to find a minimum cut between two nodes in a weighted graph, I would use FindEdgeCut as follows:

g = Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 1 \[UndirectedEdge] 3, 
    3 \[UndirectedEdge] 4}, EdgeWeight -> {2, 3, 5, 123}];
FindEdgeCut[g,1,4]

This function, however, returns the edge 3-4, so obviously the edge weights have not been considered.

I can find the minimum cut by using the maximum flow and so on, but I was wondering whether this error is more easily fixable or maybe it's just me and I don't see the error.

share|improve this question
    
Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the FAQs! 3) When you see good Q&A, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. ALSO, remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign –  Vitaliy Kaurov Sep 9 '13 at 8:47
    
Appears to be incorrect in version 9.0.0 and fixed in version 9.0.1. –  Daniel Lichtblau Sep 26 '13 at 17:07
add comment

1 Answer

"so obviously the edge weights have not been considered"

The edge weights have been considered. It can be seen from careful reading the Details section of documentation on FindEdgeCut and comparing different examples. So what does FindEdgeCut do?

  • An edge cut of a graph g is a set of edges whose deletion from g disconnects g.
  • For weighted graphs, FindEdgeCut gives an edge cut with the smallest sum of edge weights.

Now if you compare this

Graph[{1 <-> 2, 2 <-> 3, 1 <-> 3, 3 <-> 4}, EdgeWeight -> {2, 3, 5, 123}] // FindEdgeCut

{1 <-> 2, 2 <-> 3}

with this

Graph[{1 <-> 2, 2 <-> 3, 1 <-> 3, 3 <-> 4}, EdgeWeight -> {2, 3, 5, 1}] // FindEdgeCut

{3 <-> 4}

you will understand how the EdgeWeight is taken account.

share|improve this answer
    
Then maybe this is a version issue, I am using Mathematica 9.0.0.0 and while your second example does work, the first one does not. Also, I noticed a slight error in my question. What I actually wanted to do was FindEdgeCut[g,1,4], if that changes anything. –  Thomas Sep 9 '13 at 8:35
1  
@Thomas 1,4 wouldn't change anything for this specific graph. I recommend contacting Wolfram Support for version issue. –  Vitaliy Kaurov Sep 9 '13 at 8:46
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.