Modeling network as directed graph

Question

I have a network that could look like this:

Basically, I want to know the minimum number of green circles that can disconnect the source and drain if removed/disabled. (in this case 1)
I have already succesfully implemented the Edmonds-Karp algrorithm, but I don't know how to model the network with directed edges, so I get the desired result.
If I just replace each connection between the nodes with two opposite directed edges with capacity 1, I get a max flow of 2 with EdmondsKarp, but I only need to remove 1 green circle to break the network.
How do I model my network as nodes and directed edged?

Answer 1

You can reduce this problem to the standard s–t cut problem in directed graphs, which can then solved e.g. by the Edmonds–Karp algorithm. For each vertex v, create two vertices v_in and v_out and a directed edge (v_in, v_out), and for each edge {v,w}, add two directed edges (v_out ,w_in) and (w_out , v_in). It is then not hard to see that a maximum flow from s_in to t_out corresponds to a minimum vertex cut between s and t.