How to optimize memory footprint of a graph with large amount of vertex?

Question

I was tasked my my prof to solve a graph question. However, he hinted that one of his hidden test cases that I failed have over 80k, my code would fail as it exceeded the amount of memory that was preassigned.

#include<stdio.h>
#include <stdlib.h>
  
int* city_population (int N, int* population, int** road, int Q, int** cities) ;

int main() {
    int N;
    scanf("%d", &N);
    int i_population;
    int *population = (int *)malloc(sizeof(int)*(N));
    for(i_population = 0; i_population < N; i_population++)
        scanf("%d", &population[i_population]);
    int i_road, j_road;
    int **road = (int **)malloc((N-1)*sizeof(int *));
    for(i_road = 0; i_road < N-1; i_road++)
    {
        road[i_road] = (int *)malloc((2)*sizeof(int));
    }
    for(i_road = 0; i_road < N-1; i_road++)
    {
        for(j_road = 0; j_road < 2; j_road++)
        {
            scanf("%d", &road[i_road][j_road]);
        }
    }
    int Q;
    scanf("%d", &Q);
    int i_cities, j_cities;
    int **cities = (int **)malloc((Q)*sizeof(int *));
    for(i_cities = 0; i_cities < Q; i_cities++)
    {
        cities[i_cities] = (int *)malloc((3)*sizeof(int));
    }
    for(i_cities = 0; i_cities < Q; i_cities++)
    {
        for(j_cities = 0; j_cities < 3; j_cities++)
        {
            scanf("%d", &cities[i_cities][j_cities]);
        }
    }

    int* out_ = city_population(N, population, road, Q, cities);
    printf("%d", out_[0]);
    int i_out_;
    for(i_out_ = 1; i_out_ < Q; i_out_++)
        printf("\n%d", out_[i_out_]);
}

This is my implementation of the function with adjacency matrix. However, it is not optimal but I do not know how to implement an optimized code to solve it. The comments above the code is what I had debunked from the template that my prof have provided in creating this question.

roads : they are the edges/link that ties the 2 cities/vertex together

cities: It is a Q x 3 matrix where Q is the number of query. so

cities[][0] denotes the start of a city/vertex

cities denotes the end of a city/vertex

cities[][2] denotes the condition to look for city between the 2 determined vertex that have <= cities[2]

What I did was I created an adjacency matrix to store the edges and implemented a depth first search to find out how many city between the 2 determined vertex have a population less than or equal to cities[][2]

// count[i] is the number of cities with population less than or equal to cities[i][2] 
// Start of city is denoted by cities[i][0] and end of city is denoted by cities[i][1]
// The road is undirected and there is only one road between two cities
// Traverse the start city to the end city with the road
// Traverse with depth first search with stack
// Return an array of count of cities that satisfy the above condition

//Consider N = 3 , population = [1,2,3], road = [[1,2],[2,3]], Q = 2, cities = [[1,3,2]]
// The given query is the number of cities in the path from 1 to 3 that have a population of at most2
//cities lie in the path are [1,2,3]. so the answer will return 2
int* city_population (int N, int* population, int** road, int Q, int** cities) 
{
   int i,j;
    // Count is the number of cities with population less than or equal to cities[i][2]
    int *count = (int *)malloc(sizeof(int)*Q);

     // Visited is to check if the city is visited or not
    int *visited = (int *)malloc(sizeof(int)*N);

    // Stack is the stack to traverse the cities
    int *sTemp = (int *)malloc(sizeof(int)*N);
    int top;

    // Adjacency matrix
    int **adjV = (int **)malloc((N)*sizeof(int *));
    for(i=0;i<N;i++)
        adjV[i] = (int *)malloc((N)*sizeof(int));
    for(i=0;i<N-1;i++){
        adjV[road[i][0]-1][road[i][1]-1] = 1;
        adjV[road[i][1]-1][road[i][0]-1] = 1;
    }

    // Traverse the cities with depth first search
    for(i=0;i<Q;i++){
        for(j=0;j<N;j++)
            visited[j] = 0;
        top = -1;
        sTemp[++top] = cities[i][0]-1;
        visited[cities[i][0]-1] = 1;
        count[i] = 0;
        while(top!=-1){
            int curC = sTemp[top];

            // Traverse the adjacency list of the current city
            if(curC == cities[i][1]-1)
                break;
            for(j=0;j<N;j++){
                if(adjV[curC][j] == 1 && visited[j] == 0)
                {
                    sTemp[++top] = j;
                    visited[j] = 1;
                    break;
                }
            }

            // If the current city is the last city in the adjacency list then pop the city from the stack
            if(j==N)
                top--;
        }
        
        // Count the number of cities with population less than or equal to cities[i][2]
        for(j=0;j<=top;j++){
            if(population[sTemp[j]]<=cities[i][2]){
                count[i]++;
            }
        }
    }
    return count;

}

I am genuinely seeking advice on how the ways to optimize my code. Thanks.

Answer 1

Note that the problem here is the adjacency matrix. For 80000 vertices, there will be 80000² pairs to record, which is 6.4 billion. You could optimize the way your adjacency matrix is stored, or rewrite your algorithm so it doesn't use adjacency matrix.

To optimize adjacency matrix, you could store bits instead on ints. 6.4 billion bits is 800 megabytes, which might be OK for your purposes. To allocate N² bits, note that that's equivalent to N²/8 bytes.

uint8_t *adjV = malloc(N * N / 8 + 1); // +1 to round up

To access this data structure, for example, at indices [curC][j], calculate a bit index as curC * N + j, convert it to a byte index (divide by 8) and then access the proper bit inside the byte. You might want to use uint32_t instead of uint8_t for more performance, but these are relatively unimportant implementation details.

You could cut the memory footprint by a factor of 2 because your edges are not directional, but that's a bit tricky to address, and a factor of 2 may be not good enough to bother. If 800 megabytes is still too much, you probably should rewrite your algorithm to work without adjacency matrix.