calculating minimum - cut in a directed weighted graph using maxflow algorithm

Question

i have calculated maximum flow using ford fulkerson algorithm,now i want to implement project selection problem for which i need to calculate max. no. of feasible projects.i need to find a min.cut containing no. of feasible projects with max profit. What should be the algorithm to find a min. cut *after knowing max.flow in graph.*How can i use max flow to determine cut containing i.e no. of nodes contributing to max flow.I need to select the optimal set of nodes so that revenue is maximisied. In my application each node is associated with a revenue,it can be positive and negative also. and there are precedence constraints also,eg.if a is selected than b&c also must be selected Can anybody tell me how to implement this?

---

I have transformed it in max flow graph as follows: if revenue(node)>0 add an edge from source->node else add an edge from node->sink and i have created a egde of infinite capacity for precedence constraints

Answer 1

we can calculate min.cut (A,B)by running dfs/bfs from source vertex, and then finding the saturated edges in final residual graph i.e.after there are no augmenting paths

Answer 2

Ford Fulkerson is somewhat of a meta-algorithm in that it can be implemented several different ways (Edmonds-Karp is an instantiation for the FF algorithm). Your question is difficult to answer without knowing which way you implemented it or what information you have.

Ideally, you are doing some type of Breadth First Search in the algorithm using a residual graph of some kind. When you are doing this, the algorithm should halt when your BFS can not find the sink. Once this has happened, the first set for your cut is all of the nodes you were able to find with your BFS, and the other set is all the nodes you could not find.

If you are using the labeling version of the algorithm, the sets that form the cut are the labeled set and the unlabeled set.

I hope this helps. Your question was admittedly a little difficult for me to parse. If you are unable to find sufficient help here, I would have the same recommendations as matcheek (look on Wikipedia or CLRS if you have that book available).