Sélectionner une révision Git
-
Louis Fourcade a rédigéLouis Fourcade a rédigé
adjarray.c 2,91 Kio
/*
Maximilien Danisch
September 2017
http://bit.ly/danisch
maximilien.danisch@gmail.com
Info:
Feel free to use these lines as you wish. This program loads a graph in main memory.
To compile:
"gcc adjlist.c -O9 -o adjlist".
To execute:
"./adjlist edgelist.txt".
"edgelist.txt" should contain the graph: one edge on each line (two unsigned long (nodes' ID)) separated by a space.
The prograph will load the graph in main memory and then terminate.
Note:
If the graph is directed (and weighted) with selfloops and you want to make it undirected unweighted without selfloops, use the following linux command line.
awk '{if ($1<$2) print $1" "$2;else if ($2<$1) print $2" "$1}' net.txt | sort -n -k1,2 -u > net2.txt
Performance:
Up to 200 million edges on my laptop with 8G of RAM: takes more or less 4G of RAM and 30 seconds (I have an SSD hardrive) for 100M edges.
*/
#include <stdlib.h>
#include <stdio.h>
#include <time.h>//to estimate the runing time
#define NLINKS 100000000 //maximum number of edges for memory allocation, will increase if needed
typedef struct {
unsigned long s;
unsigned long t;
} edge;
//edge list structure:
typedef struct {
unsigned long n;//number of nodes
unsigned long e;//number of edges
edge *edges;//list of edges
unsigned long *cd;//cumulative degree cd[0]=0 length=n+1
unsigned long *adj;//concatenated lists of neighbors of all nodes
} adjlist;
//compute the maximum of three unsigned long
inline unsigned long max3(unsigned long a,unsigned long b,unsigned long c){
a=(a>b) ? a : b;
return (a>c) ? a : c;
}
//reading the edgelist from file
adjlist* readedgelist(char* input){
unsigned long e1=NLINKS;
FILE *file=fopen(input,"r");
adjlist *g=malloc(sizeof(adjlist));
g->n=0;
g->e=0;
g->edges=malloc(e1*sizeof(edge));//allocate some RAM to store edges
char line[1000];
while (fgets(line, sizeof line, file)) {
// ignore les commentaires #
if (*line == '#') {continue;}
// récupère les données
if (sscanf(line, "%lu %lu", &(g->edges[g->e].s), &(g->edges[g->e].t))==2) {
g->n=max3(g->n,g->edges[g->e].s,g->edges[g->e].t);
if (++(g->e)==e1) {//increase allocated RAM if needed
e1+=NLINKS;
g->edges=realloc(g->edges,e1*sizeof(edge));
}
}
}
fclose(file);
g->n++;
g->edges=realloc(g->edges,g->e*sizeof(edge));
return g;
}
//building the adjacency matrix
void mkadjlist(adjlist* g){
unsigned long i,u,v;
unsigned long *d=calloc(g->n,sizeof(unsigned long));
for (i=0;i<g->e;i++) {
d[g->edges[i].s]++;
d[g->edges[i].t]++;
}
g->cd=malloc((g->n+1)*sizeof(unsigned long));
g->cd[0]=0;
for (i=1;i<g->n+1;i++) {
g->cd[i]=g->cd[i-1]+d[i-1];
d[i-1]=0;
}
g->adj=malloc(2*g->e*sizeof(unsigned long));
for (i=0;i<g->e;i++) {
u=g->edges[i].s;
v=g->edges[i].t;
g->adj[ g->cd[u] + d[u]++ ]=v;
g->adj[ g->cd[v] + d[v]++ ]=u;
}
free(d);
//free(g->edges);
}
//freeing memory
void free_adjlist(adjlist *g){
free(g->edges);
free(g->cd);
free(g->adj);
free(g);
}