Directionality of mincut on a flow network
I'm not sure if I have a misunderstanding of mincut, but I've wrote a mincut algorithm using edmond-karps followed by a BFS on the flow network.
If I tell it to do a mincut from A to B, it works, since the residual flow A->B = 0, so it produces the set {A}, with a cut of A->B (1).
However, if I tell it to do a mincut from B to A, it doesn't get to augment any edges (since there are no edges from C), so the resulting set is {C}, with a cut of B->C (2).
The way I see it, I could be misunderstanding this in 1 of 2 ways. Firstly, the mincut from B to A could be correct, as only the edges from B's set would be counted, not the edges to (meaning mincut is asking "what is the minimum to not allow B to connect to A", rather than "what is the minimum to split the graph into 2 partitions).
Or, if you are asked to find mincut on a flow network (a general min-cut, where I'm currently using a "pick an arbitrary source, try all other nodes" method), it must require equal flow in both directions on any edge.
The 'correct' min-cut for "source=B, sink=A" is 0, since there is no edge B->A (equivalently, c(B, A) = 0); it looks like your implementation might be answering a different question. Are you checking each potential shortest path in the BFS stage to ensure it ends at the sink?
(meaning mincut is asking "what is the minimum to not allow B to connect to A", rather than "what is the minimum to split the graph into 2 partitions).
Yes, the first one: we only care about bottlenecks from the source to the sink (max-flow min-cut theorem). Min-cut does "partition" the graph in two, but there is an additional requirement that the source and the sink are in separate sets.
(a general min-cut, where I'm currently using a "pick an arbitrary source, try all other nodes" method)
If you are saying "treat all the other nodes as sinks," this is a simple degree calculation on the outward edges of the source.
edit: it's not exactly a degree calculation since the edges are weighted, but it's just adding up edge weights, no search necessary.
it must require equal flow in both directions on any edge.
No such requirement exists (flow networks are directed graphs - any undirected edges are mapped to two anti-parallel edges, and for a particular flow problem, only one of the edges is used).