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 <iostream>
#include <limits.h>
#include <string.h>
#include <queue>
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>
using namespace std;
#define DEBUG 0
typedef pair<int,int> 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<vector<int> > 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 <int> 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<vector<int> > 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<PII> minCut(vector<vector<int> > graph, int s, int t)
{
int u, v;
vector<PII> ans;
// Create a residual graph and fill the residual graph with
// given capacities in the original graph as residual capacities
// in residual graph
vector<vector<int> > 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<vector<int> > 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<int> vv(npcs);
vector<PII> 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

Best,

Bruno