1
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Commented Sep 9, 2013 at 8:47
  • $\begingroup$ Appears to be incorrect in version 9.0.0 and fixed in version 9.0.1. $\endgroup$ Commented Sep 26, 2013 at 17:07

1 Answer 1

Reset to default
2
$\begingroup$

"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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Commented Sep 9, 2013 at 8:35
  • 1
    $\begingroup$ @Thomas 1,4 wouldn't change anything for this specific graph. I recommend contacting Wolfram Support for version issue. $\endgroup$ Commented Sep 9, 2013 at 8:46
  • $\begingroup$ Just wanted to note that FindEdgeCut is totally unreliable with weights, even in 12.1 ... it's simply not safe to use because it's impossible to decide if it will return a correct result. It's one of those long-standing Graph bugs I keep complaining about. $\endgroup$ Commented Apr 3, 2020 at 11:19

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.