Converting adjacency matrix to adjacency lists

help
, , ,
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… :confused:

// 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 :smiley:
Best,

Bruno

1 Like
2

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 :slight_smile:

Regards

1 Like
3

Hi,

Thanks for your help in the first place :slight_smile:

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<vector > Graph;

where an edge is denoted as Graph[i] - Graph[i][j].first …

Something like this:

vector<vector<PII> > 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?

1 Like
4

check this link. imho, the results from dreamincode or carnegie-mellon u(cmu.edu) gonna help you. or stackoverflow.

5

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… :frowning:

1 Like
6

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<graph.size();i++)
{
 for(int j=0;j<graph[i].size();j++)
  {
   if(visited[i] && !visited[j])
    {
         cout<<i<<"-"<<j<<endl; 
	 ans.push_back(make_pair(i,j));
    }
  }
}