×

 1 Hi guys, I'm now experimenting with Ford-Fulkerson Algorithm, which I am using to print the min-cut (as in, edges which comprise the min-cut). However, I am having some issues with memory and I wanted to translate this code to use only adjacency lists representation, instead of adjacency matrix... If someone could help me I'd be really glad, as I've spent over 72 hours with this problem... :/ // C++ program for finding minimum cut using Ford-Fulkerson #include #include #include #include #include #include #include #include #include using namespace std; #define DEBUG 0 typedef pair PII; /* Returns true if there is a path from source 's' to sink 't' in residual graph. Also fills parent[] to store the path */ int bfs(vector > rGraph, int s, int t, int parent[]) { // Create a visited array and mark all vertices as not visited bool visited[rGraph.size()]; memset(visited, 0, sizeof(visited)); // Create a queue, enqueue source vertex and mark source vertex // as visited queue q; q.push(s); visited[s] = true; parent[s] = -1; // Standard BFS Loop while (!q.empty()) { int u = q.front(); q.pop(); for (int v=0; v< (int) rGraph.size(); v++) { if (visited[v]==false && rGraph[u][v] > 0) { q.push(v); parent[v] = u; visited[v] = true; } } } // If we reached sink in BFS starting from source, then return // true, else false return (visited[t] == true); } // A DFS based function to find all reachable vertices from s. The function // marks visited[i] as true if i is reachable from s. The initial values in // visited[] must be false. We can also use BFS to find reachable vertices void dfs(vector > rGraph, int s, bool visited[]) { visited[s] = true; for (int i = 0; i < (int) rGraph.size(); i++) if (rGraph[s][i] && !visited[i]) dfs(rGraph, i, visited); } // Prints the minimum s-t cut vector minCut(vector > graph, int s, int t) { int u, v; vector ans; // Create a residual graph and fill the residual graph with // given capacities in the original graph as residual capacities // in residual graph vector > rGraph; // rGraph[i][j] indicates residual capacity of edge i-j //<---------------------------------------------------------------------------------------------------------- rGraph.resize(graph.size()); for(int i = 0; i < (int) graph.size(); i++) { rGraph[i].resize(graph.size()); } //--------------------------------------------------------------------------------------------------------> for (u = 0; u < (int) graph.size(); u++) for (v = 0; v < (int) graph.size(); v++) rGraph[u][v] = graph[u][v]; int parent[rGraph.size()]; // This array is filled by BFS and to store path // Augment the flow while tere is path from source to sink while (bfs(rGraph, s, t, parent)) { // Find minimum residual capacity of the edhes along the // path filled by BFS. Or we can say find the maximum flow // through the path found. int path_flow = INT_MAX; for (v=t; v!=s; v=parent[v]) { u = parent[v]; path_flow = min(path_flow, rGraph[u][v]); } // update residual capacities of the edges and reverse edges // along the path for (v=t; v != s; v=parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; } } // Flow is maximum now, find vertices reachable from s bool visited[rGraph.size()]; memset(visited, false, sizeof(visited)); dfs(rGraph, s, visited); // Print all edges that are from a reachable vertex to // non-reachable vertex in the original graph for (int i = 0; i < (int) rGraph.size(); i++) for (int j = 0; j < (int) rGraph.size(); j++) if (visited[i] && !visited[j] && graph[i][j]) { //cout << i << " - " << j << endl; ans.push_back(make_pair(i,j)); } return ans; } // Driver program to test above functions int main() { // Let us create a graph shown in the above example /* int graph[V][V] = { {0, 16, 13, 0, 0, 0}, {0, 0, 10, 12, 0, 0}, {0, 4, 0, 0, 14, 0}, {0, 0, 9, 0, 0, 20}, {0, 0, 0, 7, 0, 4}, {0, 0, 0, 0, 0, 0} };*/ int n,m; cin >> n >> m; vector > G; G.resize(n); for(int i = 0; i < n; i++) { G[i].resize(n); } //for(int i = 0; i < n; i++) //{ //for(int j = 0; j < n; j++) //{ //cin >> G[i][j]; //} //} //reads edge for(int i = 0; i < m; i++) { int u,v; cin >> u >> v; G[u][v] = 1; //all vertexes are assumed to have weight 1 G[v][u] = 1; } int h; cin >> h; for(int i = 0; i < h; i++) { int npcs; cin >> npcs; vector vv(npcs); vector p; for(int i = 0; i < npcs; i++) { //int pc; cin >> vv[i]; } int answer = INT_MAX; for(int i = 1; i < (int) vv.size(); i++) { p = minCut(G,vv[0],vv[i]); answer = min(answer,(int) p.size()); } cout << answer << endl; } //prints filled matrix for debug purposes... TODO: Add debug flag if(DEBUG){ for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { cout << G[i][j] << " "; } cout << endl; } } //minCut(G, 1, 0); //cout << p.size() << endl; return 0; }  Note: my main issue seems to be how can I use C++ iterators to "pass" the adjacency list to both DFS and BFS in order not to get lots of segfaults... As I've rarely used adjacency lists and as my iterator knowledge is poor, I'd like some guidance :D Best, Bruno asked 31 Mar '14, 23:11 3★kuruma 17.7k●72●143●209 accept rate: 8%

 1 Here is a bfs implemented using adjacency list: http://ideone.com/amqg4O Basically in adjacency list you store only vertices adjacent to a given vertex. This saves up on space. In the above code, vector < vector < int > >g is an adjacency list where g[i] stores vertices adjacent to the i'th vertex. To iterate over the list of adjacent vertices of the i'th vertex you can just use the following loop: for(int i = 0 ; i < g[i].size() ; i++) { /do necessary stuff/ }. As for passing the adjacency list to a function, you can do that in exactly the same way as you pass the adjacency matrix in your code. No segfaults will occur. If you need more clarifications, feel free to comment :) Regards answered 31 Mar '14, 23:25 783●5●10●20 accept rate: 0%
 1 Hi, Thanks for your help in the first place :) However, I don't think I can do it that way, mostly because I need to "entwine" the DFS and the BFS together, as you might see here:  while (bfs(rGraph, s, t, parent)) { // Find minimum residual capacity of the edhes along the // path filled by BFS. Or we can say find the maximum flow // through the path found. int path_flow = INT_MAX; for (v=t; v!=s; v=parent[v]) { u = parent[v]; path_flow = min(path_flow, rGraph[u][v]); } // update residual capacities of the edges and reverse edges // along the path for (v=t; v != s; v=parent[v]) { u = parent[v]; rGraph[u][v] -= path_flow; rGraph[v][u] += path_flow; } } // Flow is maximum now, find vertices reachable from s bool visited[rGraph.size()]; memset(visited, false, sizeof(visited)); dfs(rGraph, s, visited); // Print all edges that are from a reachable vertex to // non-reachable vertex in the original graph for (int i = 0; i < (int) rGraph.size(); i++) for (int j = 0; j < (int) rGraph.size(); j++) if (visited[i] && !visited[j] && graph[i][j]) { //cout << i << " - " << j << endl; ans.push_back(make_pair(i,j)); } return ans; }  The main issues I have are three: 1) I only want to print the edges which will be "crossed" by the min-cut; 2) I need to have both a DFS and BFS running "synced" and both with the same graph structure; 3) I can't seem to figure out a way of doing the double for loop in the end when I do not have a square matrix. Obviously if Graph[i][j] is 0 in an Adjacency Matrix representation, it might not even exist in an Adjacency List one... Also, last but not least, my graph needs to be weighted (I'm giving a specfic weight to the edges, say 1); For that I use a vector > Graph; where an edge is denoted as Graph[i] - Graph[i][j].first ... Something like this: vector > G; G.resize(n); //reads edge for(int i = 0; i < m; i++) { int u,v; cin >> u >> v; G[u].push_back(make_pair(v,1)); //all vertexes are assumed to have weight 1 G[v].push_back(make_pair(u,1)); }  How would I use this structure in the above code? answered 01 Apr '14, 01:57 3★kuruma 17.7k●72●143●209 accept rate: 8%
 1 Thanks! But, maybe I didnt make myself too clear, I know how to convert between both representations, in fact, the weighted adjacency list idea is given above... My issue seems to be with how that representation will interfere with the general algorithm of Ford-Fulkerson, as I can't print the edges in a direct adjacency list representation... For the example graph in the code as comment, the output should be: 1 - 3 4 - 3 4 - 5  I cant manage to reproduce it with the adjacency list representation... :( answered 01 Apr '14, 04:53 3★kuruma 17.7k●72●143●209 accept rate: 8%
 0 check this link. imho, the results from dreamincode or carnegie-mellon u(cmu.edu) gonna help you. or stackoverflow. answered 01 Apr '14, 03:53 1★garakchy 1.1k●16●30●48 accept rate: 1%
 0 Printing is the required ans is trivial. It can be done using the following code (graph[i] is the adjacency list of i'th vertex): for(int i=0;i
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,699
×17
×1
×1

question asked: 31 Mar '14, 23:11

question was seen: 9,824 times

last updated: 01 Apr '14, 16:16