如何使用位圖二維數組存儲圖的鄰接矩陣

我想存儲一個非常大的圖（約40k個節點）的鄰接矩陣。但是使用int和char數組會導致我由於內存限制而導致分段錯誤。使用malloc的動態分配在這裏也失敗了。任何人都可以提出一個方法來實現這個使用位圖二維數組？這裏在C到目前爲止，我的實現：如何使用位圖二維數組存儲圖的鄰接矩陣

#include <stdio.h> 
#include <stdlib.h> 

int MAX = 50000; 

void clustering(char adj[][MAX]); 

int count_neighbour_edges(int temp[], int len, char adj[][MAX]); 

int main() 
{ 
    int nol = 0, i, j, k;  
    FILE *ptr_file1,*ptr_file2; 

    struct community 
    { 
     int node; 
     int clust; 
    }; 
    struct community d; 

    ptr_file1 = fopen("community.txt","r"); 

    if (!ptr_file1) 
    return 1; 

    while(fscanf(ptr_file1,"%d %d",&d.node, &d.clust)!=EOF) //Getting total no. of nodes from here 
    { 
    nol++; 
    } 

    char adj[nol+1][nol+1];  //Getting segmentation fault here  

    struct adjacency 
    { 
     int node1; 
     int node2; 
    }; 
    struct adjacency a; 

    ptr_file2 = fopen("Email-Enron.txt","r"); 

    if (!ptr_file2) 
    return 1; 




    while(fscanf(ptr_file2,"%d %d",&a.node1, &a.node2)!=EOF) 
    { 
     adj[a.node1][a.node2] = '1'; 
     adj[a.node2][a.node1] = '1'; 
    } 

    clustering(adj); 
    return (0); 
}

來源

2014-10-03 Siddharth Ubana

你可能想嘗試的矩陣存儲在堆（使用malloc）。至少在64位系統上，您將需要大約1.6 GB的數據，這不應該是個問題。將矩陣存儲在堆棧上肯定會導致堆棧溢出。 – nwellnhof 2014-10-03 08:48:14

@nwellnhof我已經試過了。它沒有工作。 – 2014-10-03 09:01:28

這是不夠的？應該可以配置1.6G內存。如果你在linux下工作，我認爲'brk（2）'或'sbrk（2）'應該允許你提高分配的極限。或者更簡單的方法是使用'mmap（2）'。它允許你分配內存頁的looooooots。 – HuStmpHrrr 2014-10-03 13:36:09

你可以嘗試把陣列中的數據段。你可以通過聲明的任何函數外要這樣做，後來使用存儲區域作爲動態調整的二維數組：

char buffer[MY_MAX_SIZE]; 

int main() 
{ 

... 

    if ((nol+1)*(nol+1) > MY_MAX_SIZE) { 
     exit(1); // Too large to fit in buffer! 
    } 
    char (*adj)[nol+1] = buffer;  // Use the space in buffer as a dynamic 2-dimensional array.

略微直觀的聲明是因爲nol的大小是在編譯時未知的，所以我不能將緩衝區聲明爲所需大小的二維數組。

你需要對MY_MAX_SIZE適合的問題大小的值，並且您的平臺可以處理決定，例如

#define MY_MAX_SIZE (40000L * 40000L)

來源

2014-10-03 10:21:06

如何使用位圖二維數組存儲圖的鄰接矩陣

回答

相關問題