/* Générateur de graphes - v1.7 - © Cyril Gavoille - Janvier 2010 (aide en ligne à la fin du source) */ // gcc gengraph.c -o gengraph -Os ; strip gengraph // gcc gengraph.c -o gengraph -Oz ; strip gengraph (MacOs) #include #include #include #define ARG(s) (strcmp(ARGV[i],s)==0) #define DIMAX 256 /* nb maximum de paramètres d'un graphe */ #define CMDMAX 512 /* nb maximum de caractères sur la ligne de commande */ int N; /* N=nb de sommets du graphes avant suppression */ int NF; /* nb de sommets final du graphes */ int *V; /* étiquette des sommets, en principe V[i]=i */ int *INC; /* INC[i]=deg(i). Si =0, alors i sommet isolé */ int SHIFT=0; /* début de la numérotation des sommets */ int PARAM[DIMAX];/* liste des paramètres du graphe */ double DELE=0.0; /* proba de supprimer une arêtes */ double DELV=0.0; /* proba de supprimer un sommet */ double REDIRECT=0.0; /* proba de rediriger une arête */ int PERMUTE=0; /* vrai ssi -permute */ int NOT=0; /* vrai ssi -not */ int FORMAT=0; /* type de la sortie, par défaut 0=standard */ int HEADER=0; /* par défaut pas de préambule, sinon HEADER=1 */ int EXTHEADER=0; /* vrai ssi affiche (et donc calcul) NBEDGES, MAXDEG, ...*/ int WIDTH=12; /* nb maximum d'arêtes/sommets isolés affichés par ligne */ int LIGNE=0; /* compteur d'arêtes/sommets isolés par ligne */ int LAST=-1; /* extrémité de la dernière arête affichée */ int NBEDGES; /* pour -header: compte le nb d'arêtes générées si format le permet*/ int MAXDEG,MINDEG; /* pour -header: calcule le degré max/min si format le permet */ char *STRsep; /* séparateur pour dot "" ou ";" pour dot */ char *STRedge; /* caractère pour une arête "-" ou "--" dot */ char *STRsep2; int ARGC; /* variable globale pour argc */ char **ARGV; /* variable globale pour argv */ int **MAT; /* pour le format de matrice d'ajacence */ int **REP; /* associe à chaque sommet une représentation sous forme de tableau d'entiers. Sert pour les représentations implicites de graphes, les arbres, les graphes d'intersections, etc. */ /*********************************** ROUTINES POUR FONCTIONS adj(i,j) ***********************************/ void Erreur(int error){ char *s; switch(error){ case 1: s="Erreur : nombre d'argument insuffisant."; break; case 2: s="Erreur : option non reconnue."; break; case 3: s="Erreur : espace mémoire insuffisant."; break; case 4: s="Erreur : nombre trop grand de paramètres."; break; case 5: s="Erreur : format de sortie inconnu."; break; case 6: s="Erreur : valeur de paramètre incorrecte."; break; default: s="Erreur : code d'erreur inconnue."; } printf("%s\n",s); exit(0); } int *AllocTab(int n){ /* Crée un tableau de n entiers */ int *p; p=malloc(n*sizeof(int)); if(p==NULL) Erreur(3); return p; } char *AllocString(int n){ /* Crée un tableau de n caractères */ char *p; p=malloc(n*sizeof(char)); if(p==NULL) Erreur(3); return p; } int **AllocMat(int n,int t){ /* Créer une matrice de n x t entiers, c'est-à-dire un tableau de n tableaux de t entiers. */ int **X,k; X=malloc(n*sizeof(int*)); if(X==NULL) Erreur(3); for(k=0;k=0, retourne 1 ssi i est adjacent à j Rem: adj(-1,j) doit toujours retourner le nb de sommets du graphe. Certaines fonctions adj() suppose que i1)? ((j%i)==0) : 0; } int paley(int i,int j){ int d,k,p,q; if(j<0) return 0; p=PARAM[0]; if(i<0){ N=p; return N; } d=abs(i-j); q=p/2; for(k=1;k<=q;k++) if(d==((k*k)%p)) return 1; return 0; } int wheel(int i,int j){ if(j<0) return 0; if(i<0){ N=PARAM[0]; return N; } return (abs(j-i)==1)||(i==0)||((i==1)&&(j==N-1)); } int ring(int i,int j){ int k; if(j<0) return 0; if(i<0){ N=PARAM[0]; return N; } for(k=0;k1)&&(WRAP[k])&&(((x==0)&&(y==p-1))||((y==0)&&(x==p-1)))) h=1; if(h==1) b++; i /= p; j /= p; k++; } return (b==1)&&(z==(d-1)); } int butterfly(int i,int j){ int d,x,y; if(j<0) return 0; if(i<0){ N=1; for(d=0;d (mot binaire,niveau) */ y=j/d;j=j%d; /* j -> (mot binaire,niveau) */ return (abs(x-y)==1) && ( (i==j) || ((i^j)==(1<<(PARAM[0]-x-1))) ); } int geo(int i,int j){ /* deux points peuvent avoir les même coordonnées */ int k,x,y; double d; if(j<0){ FreeMat(REP,N); return 0; } if(i<0){ N=PARAM[0]; REP=AllocMat(N,2); for(k=0;k=t-1) i++; /* on insère virtuellement le coin (0,2q+1) */ if(j>=t-1) j++; if(p%2==0){ /* si p est impair, on a rien à faire */ if(i>=p*t) i++; /* on insère virtuellement le coin (p,0) si p est pair */ if(j>=p*t) j++; } /* on calcule les coordonnées de i et j placés sur cette grille (avec les coins manquant) */ li=i/t;ci=i%t; lj=j/t;cj=j%t; /* utilise le fait que i=t)&&(j>=t)) return 0; /* on a i dans l'hexagone et j en dehors */ lj=(j-t)/q;cj=(j-t)%q; /* j est le centre de l'hexagone (lj,cj) */ t=2*q+2; /* longueur d'une ligne de l'hexagone */ /* on calcule les coordonnées de i dans l'hexagone */ if(i>=t-1) i++; /* on corrige */ if((p%2==0)&&(i>=p*t)) i++; /* on recorrige */ li=i/t;ci=i%t; /* (li,ci) coordonnées de i */ return ( ((li==lj)||(li==(lj+1))) && (abs(2*cj+1+(lj%2)-ci)<2) ); } int rpartite(int i,int j){ /* On se sert du fait que ipart(j). Pour celà, on fait une recherche dichotomique d'un indice k tq WRAP[k]<=i0)&&(k=WRAP[k]) return 1; /* i et j sont dans des parts différentes */ /* ic i0 */ REP=AllocMat(n,1); /* pour représentation implicite */ B=AllocTab(n-1); H=AllocTab(n+1); /* hauteurs possibles: 0...n */ n0=n-1; /* remplit B de valeurs dont la somme fait n0 */ for(i=0;ir, alors c'est un pas montant, et donc REP[s][0]=r. */ REP[r=i=0][0]=-1; /* pas de père pour la racine */ while(rr) REP[s][0]=r; r=s; } /* libère la mémoire */ if(f) free(TREE); free(B); free(H); } int arboricity(int i,int j){ /* Utilise REP pour la représentation implicite. REP[i][0...k-1] sont les k pères du sommet i. */ int k,t,v; int **P,*X; if(j<0){ FreeMat(REP,N); return 0; } if(i<0){ /* calcule N et REP[i][0..k-1] */ N=PARAM[0]; k=PARAM[1]; P=AllocMat(N,k); /* P est la représentation finale */ X=AllocTab(N); /* permutation aléatoire */ for(t=0;t0); /* si k=0, alors la hauteur est au plus 1 */ if(k<=1) N=1+r*h; else{ /* on alors k>1, h>0 et r>0 */ N=1; for(t=0;t0); /* y=prochain indice des pères pour P[t]. Si w=0 on saute le père */ while(xr)){ /* on commence à monter */ m=1-m; while(zj) { k=i; i=j; j=k; } /* maintenant i=n) return (j-i<=k); /* dans la même clique ? */ return (REP[j][0]==i); } int kneser(int i,int j){ int *B,n,k,r,v,x,y; if(j<0) { FreeMat(REP,N); return 0; } if(i<0){ n=PARAM[0]; k=PARAM[1]; r=PARAM[2]; /* Calcule l'entier N={n choose k}. Cela est nécessaire pour allouer le tableau REP. Et malheureusement, on ne peut pas le faire à la volée au moment où l'on génère les ensembles représentant les sommets, à part faire des realloc() mais sera au final bien plus lent que de calculer N. L'algorithme utilisé ici est en O(k). Il n'utilise que des multiplications et divisions entières sur des entiers en O(N). L'algorithme issu du Triangle de Pascal est lui en O(nk), utilise un espace (tableaux d'entiers en N) en O(k), mais n'utilise que des additions sur des entiers en O(N). Principe: N = n x (n-1) x ... x (n-k+1) / k x (k-1) x ... x 1 On réecrit en (((((n/1) x (n-1)) / 2) x (n-2)) / 3) ... c'est-à-dire en multipliant le plus grand numérateur et en divisant par le plus petit numérateur. Chaque terme est ainsi un certain binomial, et donc un entier. */ N=x=n; for(y=2;y<=k;y++){ x--; N=(N*x)/y; } REP=AllocMat(N,k); /* on connaît N */ /* Calcule tous les sous-ensembles à k éléments. L'idée est de maintenir une sorte de compteur B qui représente le sous-ensemble courant et qui va passer par tous les sous-ensembles possibles à k éléments. Au départ on part du plus "petit" ensemble, B=[0 1 2 ... k-1], les éléments étant rangés dans l'ordre croissant. La stratégie pour "incrémenter" B, c'est-à-dire pour passer au sous-ensemble suivant, est la suivante : on essaye d'incrémenter le plus petit élément de B, donc B[0], tout en restant strictement inférieur à l'élément suivant B[1]. Si cela n'est pas possible, on réinitialise B[0] à sa plus petite valeur, 0 ici, et on essaye d'incrémenter le second plus petit élément de B, soit B[1]. On arête si on a pas pu incrémenter B[k-1] sans dépasser la sentiennelle B[k]=n. Dès qu'on a trouvé un élément B[i] que l'on peut incrémenter on le fait, et on a donc généré le nouvel ensemble B. On recommence ensuite la méthode en essayant d'incrémenter le plus petit élement, etc. A priori l'algorithme est en O(N*k), mais de manière amortie c'est sans doute moins, on incrémente moins souvent B[j] que B[i] si j>i. Ceci dit on paye de toute façon une copie du tableau REP=B de taille k pour chacun des N sous-ensembles. Cela reste en O(N*k). */ B=AllocTab(k+1); for(x=0;x0 */ d=1+rand()%r; /* choisir un degré d pour x: d=[1,...,r] */ for(y=0;yj) { x=i; i=j; j=x; } /* maintenant i=0. Si k sommets ont été supprimés, alors les ** valeurs de V[] sont dans SHIFT+[0,n-k[ */ int i,j,k,seuil,r=0; /* r=n-(nb de sommets supprimés) */ seuil=(double)DELV*(double)RAND_MAX; for(i=0;i0) for(i=0;i=0) V[i] += SHIFT; return r; } void Header(){ /* Affiche/calcule le préambule */ int i; /* Il faut que le system(...date) soit en premier, sinon cela s'affiche après les printf du programme C même s'ils sont placés avant ?!? */ if((EXTHEADER)&&(FORMAT==0)) printf("//\n"); else system("printf '//\n// ' ; date"); printf("// gengraph"); for(i=1;i=0){ NBEDGES+=INC[i]; if(INC[i]>MAXDEG) MAXDEG=INC[i]; if((INC[i]>= 1; printf(" m=%i",NBEDGES); printf(" maxdeg=%i",MAXDEG); printf(" mindeg=%i",MINDEG); } printf("\n//\n"); } void Out(int i,int j){ /* Affiche l'arête i-j suivant le format FORMAT. Si i<0 et j<0, alors la fonction Out() est initialisée. Si i<0, alors c'est la terminaison de la fonction Out() Si j<0, alors affiche i seul (sommet isolé). */ char *s; int x,y,z; if((i<0)&&(j<0)){ /* initialise la fonction */ switch(FORMAT){ case 0: if(HEADER) Header(); STRsep=""; STRsep2=" "; STRedge="-"; return; case 1: case 2: case 3: EXTHEADER=1; MAT=AllocMat(NF,NF); /* réserve la matrice */ for(x=0;x0) printf("%s\n",STRsep); /* newline si fini avant la fin de ligne */ if(FORMAT==4) printf("}\n"); if(HEADER) { EXTHEADER=1; Header(); } return; case 1: case 2: /* affiche la matrice (ou la demi-matrice) */ if(HEADER) Header(); z=NF-1; for(x=0;x=0) printf("%s%i",STRedge,V[j]); LIGNE++; if(LIGNE==WIDTH){ LIGNE=0; LAST=-1; printf("%s\n",STRsep); } return; case 1: case 2: case 3: if(j>=0){ x=V[i]-SHIFT; y=V[j]-SHIFT; MAT[x][y]=MAT[y][x]=1; } return; default: Erreur(5); } } void Help(void){ /* Affiche l'aide en ligne */ char *s; s=AllocString(CMDMAX); strcat(s,"sed -n '/*[#] ###/,/### #/p' "); strcat(strcat(s,ARGV[0]),".c | "); strcat(s,"sed -e 's/\\/\\*[#] ###//g' -e 's/### [#]\\*\\///g' "); strcat(s,"-e 's/^[.][.][.][.]/ /g' | more"); system(s); free(s); exit(0); } void HelpGraph(void){ /* Aide courte: affiche les graphes possibles */ char *s; s=AllocString(CMDMAX); strcat(s,"sed -n '/*[#] ###/,/### #/p' "); strcat(strcat(s,ARGV[0]),".c | "); strcat(s,"sed -e 's/\\/\\*[#] ###//g' -e 's/### [#]\\*\\///g' | "); strcat(s,"grep '^[.][.][.][.].' | sed 's/[.][.][.][.]/ /g' | more"); system(s); exit(0); } void DotPdf(char *file, char *filtre){ int i; char *s; s=AllocString(CMDMAX); /* on réécrit la ligne de commande, sans -format dotpdf */ for(i=0;iDIMAX) Erreur(4); for(k=0;kDIMAX) Erreur(4); for(k=0;kDIMAX) Erreur(4); for(k=0;k=PARAM[0]-1) PARAM[1]=PARAM[0]-1; if(PARAM[1]<1) Erreur(6); goto fin; } if ARG("wheel"){ i++; adj=wheel; PARAM[0]=atoi(NextArg(&i)); goto fin; } if ARG("icosa"){ i++; adj=icosa; goto fin; } if ARG("dodeca"){ i++; adj=dodeca; goto fin; } if ARG("rdodeca"){ i++; adj=rdodeca; goto fin; } if ARG("cubocta"){ i++; adj=cubocta; goto fin; } if ARG("tutte"){ i++; adj=tutte; goto fin; } if ARG("interval"){ i++; adj=interval; PARAM[0]=atoi(NextArg(&i)); goto fin; } if ARG("permutation"){ i++; adj=permutation; PARAM[0]=atoi(NextArg(&i)); goto fin; } if ARG("kneser"){ i++; adj=kneser; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=atoi(NextArg(&i)); PARAM[2]=atoi(NextArg(&i)); if(PARAM[1]>PARAM[0]/2) PARAM[1]=PARAM[0]-PARAM[1]; goto fin; } if ARG("butterfly"){ i++; adj=butterfly; PARAM[0]=atoi(NextArg(&i)); goto fin; } if ARG("hexagon"){ i++; adj=hexagon; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=atoi(NextArg(&i)); goto fin; } if ARG("whexagon"){ i++; adj=whexagon; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=atoi(NextArg(&i)); goto fin; } if ARG("arytree"){ i++; adj=arytree; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=atoi(NextArg(&i)); PARAM[2]=atoi(NextArg(&i)); goto fin; } if ARG("geo"){ i++; adj=geo; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=atof(NextArg(&i)); goto fin; } /* graphes composés */ if ARG("tree"){ i++; adj=arboricity; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=1; goto fin; } if ARG("path"){ i++; adj=grid; PARAM[0]=1; PARAM[1]=atoi(NextArg(&i)); goto fin; } if ARG("torus"){ i++; adj=grid; PARAM[0]=2; PARAM[1]=-atoi(NextArg(&i)); PARAM[2]=-atoi(NextArg(&i)); goto fin; } if ARG("mesh"){ i++; adj=grid; PARAM[0]=2; PARAM[1]=atoi(NextArg(&i)); PARAM[2]=atoi(NextArg(&i)); goto fin; } if ARG("cycle"){ i++; adj=ring; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=PARAM[2]=1; goto fin; } if ARG("headwood"){ i++; adj=cage; PARAM[0]=14; PARAM[1]=2; PARAM[2]=5;PARAM[3]=-5; goto fin; } if ARG("pappus"){ i++; adj=cage; PARAM[0]=18; PARAM[1]=6; PARAM[2]=5;PARAM[3]=7;PARAM[4]=-7; PARAM[5]=7;PARAM[6]=-7;PARAM[7]=-5; goto fin; } if ARG("mcgee"){ i++; adj=cage; PARAM[0]=24; PARAM[1]=3; PARAM[2]=12;PARAM[3]=7;PARAM[4]=-7; goto fin; } if ARG("levi"){ i++; adj=cage; PARAM[0]=30; PARAM[1]=6; PARAM[2]=9;PARAM[3]=13;PARAM[4]=-13; PARAM[5]=-9;PARAM[6]=7;PARAM[7]=-7; goto fin; } if ARG("tutte-coexter"){ i++; adj=cage; PARAM[0]=30; PARAM[1]=4; PARAM[2]=9;PARAM[3]=13;PARAM[4]=-13;PARAM[5]=-9; goto fin; } if ARG("wagner"){ i++; adj=ring; PARAM[0]=8; PARAM[1]=2; PARAM[2]=1; PARAM[3]=4; goto fin; } if ARG("mobius"){ i++; adj=ring; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=2; PARAM[2]=1; PARAM[3]=PARAM[0]/2; goto fin; } if ARG("binary"){ i++; adj=arytree; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=PARAM[2]=2; goto fin; } if ARG("stable"){ i++; adj=ring; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=0; goto fin; } if ARG("clique"){ i++; adj=ring; NOT=1-NOT; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=0; goto fin; } if ARG("random"){ i++; adj=ring; NOT=1-NOT; PARAM[0]=atoi(NextArg(&i)); DELE=1.0-atof(NextArg(&i)); PARAM[1]=0; goto fin; } if ARG("tw"){ PARAM[2]=0; gototw: i++; adj=ktree; PARAM[0]=atoi(NextArg(&i)); PARAM[1]=atoi(NextArg(&i)); DELE=0.5; goto fin; } if ARG("pw"){ PARAM[2]=1; goto gototw; } if ARG("bipartite"){ i++; adj=rpartite; PARAM[0]=2; PARAM[1]=atoi(NextArg(&i)); PARAM[2]=atoi(NextArg(&i)); goto fin; } if ARG("petersen"){ i++; adj=kneser; PARAM[0]=5; PARAM[1]=2; PARAM[2]=0; goto fin; } fin: if(j==i) Erreur(2); /* option non trouvée */ } /*********************************** COEUR DU GENERATEUR ***********************************/ srand(seuil); /* initialise le générateur aléatoire */ adj(-1,0); /* initialisation du graphe, calcul N avant la suppression des sommets */ V=AllocTab(N); /* tableau des étiquettes des sommets, -1 si supprimé */ NF=InitVertex(N); /* initialise NF et les étiquettes V[] des sommets */ seuil=(double)(1.0-DELE)*(double)RAND_MAX; seuilr=(double)(REDIRECT)*(double)RAND_MAX; noredirect=(REDIRECT==0.0); /* pour accélérer le test */ INC=AllocTab(N); /* INC[i]=1 ssi i possède un voisin, 0 si sommet isolé */ for(i=0;i=0){ /* si i existe */ for(j=i+1;ji */ if(V[j]>=0) /* si j existe ... */ if((rand()=0)&&(k!=i)){ /* on affiche l'arête que si k existe et si k<>i */ /* Attention ! il ne faut toucher ni à i ni à j */ INC[i]++; INC[k]++; if(k=0)&&(INC[i]==0)) Out(i,-1); Out(-1,0); /* fin de l'affichage */ adj(0,-1); /* libère éventuellement la mémoire utilisée pour adj() */ free(V); free(INC); return 0; } /*# ### Générateur de graphes - v1.7 - © Cyril Gavoille - Janvier 2010 USAGE gengraph [-option] graph_name [parameter_list] DESCRIPTION Permet de générer un graphe non orienté sous la forme, par défaut, d'une liste d'arêtes. En paramètre figure le type de graphe ainsi que ses paramètres éventuels (nombre de sommets etc.). L'aide est affichée si aucune option ou graphe ne figure après la commande. S'il manque des paramètres pour un graphe donné, une aide sur ce graphe est affichée. Par défaut les sommets et arêtes du graphe sont affichés sur la sortie standard. Ex: gengraph tutte gengraph hypercube 8 gengraph mesh 7 3 -not gengraph -dotpdf graph.pdf neato rdodeca gengraph -dotpdf graph.pdf neato tree 50 gengraph -dotpdf graph.pdf neato mesh 20 20 -dele 0.2 gengraph -dotpdf graph.pdf neato geo 400 30 gengraph arytree 6 3 3 -format dot | dot -Nshape=circle -Nwidth=0.15 -Tpdf -o graph.pdf -Nlabel= -Kcirco LE FORMAT Le format par défaut (ou standard) est une liste d'arêtes écrit en texte simple. Le format minimaliste est très proche de celui du format "dot" de GraphViz. D'autres formats de sortie sont possibles (voir l'option -format). Les sommets sont numérotés consécutivement de 0 à n-1 où n est le nombre de sommets présents dans le graphe. Une arête entre i et j est représentée par i-j. Les sommets isolés sont simplement représentés par le numéro du sommet suivit d'un espace ou d'un retour de ligne. Pour résumer, le nombre de sommets du graphe est l'entier le plus grand + 1, et s'il y a i-j, alors il existe une arête entre les sommets i et j. Pour une représentation plus compacte, les arêtes consécutives d'un chemin du graphe peuvent être regroupées en blocs. Par exemple, les deux arêtes 3-5 et 5-8 peuvent être regroupées en 3-5-8. Mais ce n'est pas obligatoire. Les sommets isolés et les arêtes (ou les blocs d'arêtes) sont séparés par des espaces ou des sauts de ligne. Une boucle sur un sommet i est codée par i-i. Les arêtes multiples sont codées par la répétition d'une même arête, comme par exemple i-j i-j, ou encore i-j-i. Quelques exemples: Ex1: 0 1-2-3-1 représente un graphe à 4 sommets, composé d'un sommet isolé (0) et d'un cycle à trois sommets (1,2,3). En voici une représentation graphique possible: 0 1 / \ 3---2 Ex2: 4-2-1-0-3-2 représente un graphe à 5 sommets composé d'un cycle de longueur 4 et d'un sommet de degré 1 attaché à 2. En voici une représentation graphique possible: 1 / \ 4-2 0 \ / 3 COMMENT LE GENERATEUR FONCTIONNE ? Pour chaque graphe une fonction adj(i,j) est définie. Elle fournit l'adjacence entre les sommets de numéro i et j, entier entre 0 et n-1. Le graphe est affiché en générant toutes les paires {i,j} possibles, et en appelant adj(i,j). Les graphes sont ainsi générés de manière implicite. Les arêtes du graphe ne sont pas stockées en mémoire, mais affichées directement à la volée. Ceci permet de générer des graphes de très grande taille sans nécessiter de mémoire centrale. Pour certains graphes, comme les arbres ou les graphes d'intersections aléatoires, une structure de données en O(n) est cependant utilisée. Pour les formats d'affichage matrix, smatrix et list, une matrice de taille n x n est utilisée en interne. Pour la génération de très grand graphe, le format standard doit être privilégié pour des raisons de capacité mémoire. COMMANDES EXTERNES Le programme fait appel, pour certaines fonctions, aux commandes systèmes suivantes: sed, more, date, printf, dot. OPTIONS -help Affiche ce texte, c'est-à-dire l'aide en ligne, qui est contenue dans le fichier source (.c) du générateur. Pour cela, le fichier source doit être dans le même répertoire que la commande. -h Aide courte. Affiche la liste les graphes et leurs paramètres qu'il est possibles de générer. Notez qu'en omettant les paramètres d'un graphe (ex: gengraph mesh) on obtient une aide en ligne de ce graphe là. -dele p Permet de supprimer chaque arête du graphe générée avec probabilité p. -delv p Similaire à -dele p, mais concerne les sommets. Le sommet et ses arêtes incidentes sont alors supprimées. Si k sommets sont supprimés, alors le nom des sommets restant sont dans l'intervalle [0,n-k[ où n est le nombre de sommets initial du graphe. Les noms des sommets sont donc éventuellement renumérotés. Voir aussi les options -permute et -shift. Bien sûr la fonction d'adjacence adj(i,j) est appliquée sur les noms (i,j) originaux. -not Inverse la fonction d'adjacence, et donc affiche le complément du graphe. Cette option est prioritaire devant l'option -redirect. -redirect p Redirige chaque arête uniformément avec probabilité p. Plus précisément, si (i,j) est une arête du graphe original G, alors avec probabilité p l'arête affichée est (i,k) au lieu de (i,j) où k est un sommet choisit uniformément parmis les sommets du graphe G. Si l'arête (i,j) est supprimée par -dele ou si le sommet i est supprimé par -delv, la redirection n'a pas lieu. Cette option est appliquée après l'option -not, le graphe G tient donc compte de -not avant de rediriger ses arêtes. -seed s Permet d'initialiser le générateur aléatoire avec la graine s, permettant de générer plusieurs fois la même suite aléatoire. Par défaut, la graine est initialisée avec le numéro de processus de la commande, donc génère par défaut des suites différentes à chaque lancement. -width m Limite à m le nombre d'arêtes et de sommets isolés affichés par ligne. Cette option n'a pas de signification particulière en dehors des formats standard et dot. Par exemple, -width 1 affiche une arrête (ou un sommet isolé) par ligne. L'option -width 0 affiche tout sur une seule ligne. La valeur par défaut est 12. -shift s Permet de renuméroter les sommets à partir de l'entier s>=0. La valeur par défaut est -shift 0. L'intérêt de cette option est de pouvoir réaliser des unions de graphes simplement en renumérotant les sommets et en concaténant les fichiers (valable aussi pour le format list). Cette option n'a pas d'effets pour les formats de sortie de type matrice. -permute Permet de permuter aléatoirement le nom des sommets. Les numéros restent dans l'intervalle initial. En principe c'est [0,n[ où n est le nombre de sommets du graphe réellement généré, sauf si l'option -shift a été utilisée. -format type Spécifie le format de la sortie. Les valeurs possibles pour type sont: - standard : format standard (liste d'arêtes), c'est le plus compact. - dot : format de GraphViz qui est très proche du format standard. - matrix : matrice d'adjacence. - smatrix : affiche la matrice inférieure droite, diagonale comprise. - list : affiche la liste d'adjacence. Les formats matrix/smatrix/list nécessitent de stocker le graphe en mémoire, alors que les premiers (standard et dot) génère le graphe à la volée. Notez qu'à partir du format dot il est possible (via la commande dot) de générer du xfig. -dotpdf file filter Génère un fichier file (pdf) grâce à dot où "filter" est l'un des filtres de dot: dot, neato, twopi, circo, fdp, ... (faire dot -K ." pour afficher les filtres disponibles. Cette option n'est de plus qu'un raccourci pour "-format dot | dot -Nshape=circle -Nwidth=0.15 -Nlabel= -Tpdf -o file -K filter". -header Affiche un préambule donnant certaines informations sur le graphe, sous forme de commentaire à la C++ (//). Par défaut aucun préambule n'est affiché. Sont affichées: - la date - ligne de commande qui a produit la génération du graphe - le nombre de sommets (n), d'arêtes (m) - degrés maximum et minimum Remarque: pour le format standard et dot, le nombre d'arêtes n'est pas déterminé avant l'affichage du graphe. Pour cette raison ces nombres sont affichés après. GRAPHES Deux types de graphes sont possibles : les graphes de base et les graphes composés. Ces derniers peuvent être obtenus en modifiant, à l'aide des options, un graphe de base. GRAPHES DE BASE : ....grid d n_1 ... n_d .... Grille à d dimensions de taille n_1 x ... x n_d. Si la dimension n_i est négative, alors cette dimension est cyclique. Par exemple, "grid 1 -10" donnera un cycle à 10 sommets. ....ring n k c_1 ... c_k .... Anneaux de cordes à n sommets avec k cordes de longueur c_1,...,c_k. ....cage n k c_1 ... c_k .... Graphe cubic pouvant servir à la construction de graphes n-cage, c'est-à-dire aux plus petits graphes cubic à n sommets de maille donnée. Ils peuvent être vus comme des anneaux de cordes irréguliers. Ils sont construit à partir d'un cycle de longueur n découpé en n/k intervalles de k sommets. Le i-ème sommet de chaque intervalle, disons le sommet numéro j du cycle, est adjacent au sommet numéro j+c_i du cycle (modulo n). Les valeurs c_i peuvent être positives ou négatives. ....arboricity n k .... Graphe d'arboricité k aléatoire ayant n sommets. Le graphe est composé de l'union de k arbres aléatoires. Chacun des arbres est un arbre plan enraciné dont les sommets sont permutés aléatoirement, sauf le premier arbre dont les sommets forment un DFS de l'arbre, la racine étant numérotée 0. Ces graphes possèdent au plus k(n-1) arêtes, et pour k=1 il s'agit d'un arbre. ....arytree h k r .... Arbre de hauteur h où chaque noeud interne à exactement k fils, le degré de la racine étant de degré r. Notez que "arytree h 1 r" génère une étoile de degré r où chaque branche est de longueur h. ....outerplanar n .... Graphe planaire extérieur connexe à n sommets (plan et enraciné). Ils sont en bijection avec les arbres plans enracinés dont tous les sommets, sauf ceux de la dernière branche, sont bicolorés. ....ktree n k .... k-arbre aléatoire à n sommets. Il faut n>k, mais k=0 est possible. Il est généré à partir d'un arbre enraciné aléatoire à n-k noeuds grâce à "tree n-k". Cela constitue des "sacs" que l'on remplit avec les n sommets suivant un parcours en profondeur de l'arbre. Plus précisément, on met k+1 sommets dans le sac racine, puis un sommet différent pour chacun des autre sac. Ensuite, le sommet unique de ces sacs ajoute des arêtes vers exactement k sommets choisis aléatoirement dans le sac de son père, et ces k sommets sont ajoutés à son sac. ....kpath n k .... k-chemin aléatoire à n sommets. La construction est similaire à celle utilisée pour ktree. L'arbre aléatoire est remplacé par un chemin. Ces graphes sont des graphes d'intervalles particuliers (voir "interval n"). ....kneser n k r .... Graphe de Kneser généralisé. Le graphe de Kneser K(n,k) classic est obtenu avec r=0. Les sommets sont tous les sous-ensembles à k éléments de [0,n[. Les sommets i et j sont adjacents ssi leurs ensembles correspondant ont au plus r éléments en commun. Le nombre chromatique de K(n,k), établit par Lovasz, vaut n-2k+2 pour tout n>=2k-1>0. ....rpartite r a_1 ... a_d .... Graphe r-parti complet K_{a_1,...,a_r}. Ce graphe possède n=a_1+...+a_r sommets. Les sommets sont partitionnés en r parts comme suit: part 1 = [0,a_1[, part 2 = [a_1,a_1+a_2[, ... part r = [a_1+...+a_{r-1}, n[. Les sommets i et j sont adjacents ssi les parts de i et j sont différentes. ....interval n .... Graphe d'intersection de n intervalles d'entiers aléatoires uniforme de [0,2n[. Des graphes d'intervalles peuvent aussi être générés par "kpath n k". ....permutation n .... Graphe de permutation sur une permutation aléatoire uniforme de [0,n[. ....prime n .... Graphe à n sommets tel que i-j ssi i>1 et j divisible par i. ....paley n .... Graphe de Paley à n sommets. Deux sommets sont adjacents ssi leur différence est un carré modulo n. Il faut que n soit une puissance d'un nombre premier et que n=1 modulo 4. Les premières valeurs possibles pour n sont: 5, 9, 13, 17, 25, 29, 37, 41, 49, ... A noter que le complément d'un graphe de Paley d'ordre n est le graphe lui même. ....wheel n .... La roue à n sommets. Graphe composé d'un cycle et d'un sommet connecté à tous les autres. ....sat n m k .... Graphe issu de la réduction du problème k-SAT à Vertex Cover. Le calcul d'un Vertex Cover de taille minimum pour ce graphe est donc difficile pour k>2. Soit F une formule de k-SAT avec n variables x_i et m clauses de k termes. Le graphe généré par "sat n m k" possède un Vertex Cover de taille n+(k-1)m si et seulement si F est satisfiable. Ce graphe est composé d'une union de n arêtes et de m cliques de k sommets, plus des arêtes connectant certains sommets des cliques aux n arêtes. Les n arêtes représentent les n variables, une extrémité pour x_i, l'autre pour non(x_i). Ces sommets ont des numéros dans [0,2n[, x_i correspond au sommet 2(i-1) et non(x_i) au sommet 2i-1, i=1...n. Les sommets des cliques ont des numéros consécutifs >= 2n. Le j-ème sommet de la i-ème clique est connecté à l'une des extrémités de l'arête k ssi la j-ème variable de la i-ème clause est x_k (ou non(x_i)). Ces connexions sont aléatoires uniformes. ....kout n k .... Graphe à n sommets, au plus kn arêtes et k+1 coloriable, crée par le processus aléatoire suivant: les sommets sont ajoutés dans l'ordre croissant de leur numéro, i=0,1,...n-1. Le sommet i est connecté à d voisins qui sont pris aléatoirement uniforme parmi les sommets dont le numéro est < i. La valeur d est déterminée aléatoirement uniforme entre 1 et min{i,k}. Il faut k>0. Le graphe est connexe, et pour k=1, il s'agit d'un arbre. ....icosa .... Isocahèdre: graphe panaire 5-régulier à 12 sommets. Il possède 30 arêtes et 20 faces qui sont des triangles. C'est le dual du dodécahèdre. ....dodeca .... Dodécahèdre: graphe planaire 3-régulier (cubic) à 20 sommets. Il possède 30 arêtes et 12 faces qui sont des pentagones. C'est le dual de l'icosahèdre. ....cubocta .... Cuboctahèdre: graphe planaire 4-régulier à 12 sommets. Il possède 24 arêtes et 14 faces qui sont des triangles ou des carrés. C'est le dual du rhombicdodécahèdre. ....rdodeca .... Rhombic-dodécahèdre: graphe planaire à 14 sommets avec des sommets de degré 3 ou 4. Il possède 21 arêtes et 12 faces qui sont des carrés. C'est le dual du cuboctahèdron. ....tutte .... Graphe de Tutte. C'est un graphe cubic à 46 sommets qui n'est pas Hamiltonien. ....butterfly d .... Graphe Butterfly de dimension d. Les sommets sont les paires (w,p) où w est un mot binaire de d bits et p un entier de [0,d]. Le sommet (w,p) est adjacent à (w',p+1) ssi les bits de w sont identiques à ceux de w' sauf pour celui de numéro p à partir de la gauche, bit qui peut donc être éventuellement différent. Il possède (d+1)*2^d sommets de degré maximum 4. ....hexagon p q .... Graphe planaire composé de p rangées de q hexagones, le tout arrangé comme un nid d'abeille. Ce graphe peut aussi être vu comme un mur de p rangées de q briques, chaque brique étant représentée cycle de longueur 6. Il possède (p+1)*(2p+2)-2 sommets et est de degré maximum 3. ....whexagon p q .... Comme hexagonal p q sauf que chaque hexagone est remplacé par une roue de taille 6 (chaque hexagone possède un sommet connecté aux 6 sommets de l'hexagone). Il possède pq sommets de plus que l'hexagone p q. ....geo n d .... Graphe d'intersection de boule fermée de diamètre d centrée sur n points d'une grille discrète n x n. Il s'agit de boules fermées selon la norme L2. Le diamètre d n'est pas forcément un entier. Deux sommets peuvent coorespondre au même point de la grille. Ils seront dans ce cas adjacents. Le graphe devient connecté lorsque d ~ K*sqrt(n) avec K dans [1.5,2]. GRAPHES COMPOSES : ....mesh p q (= grid 2 p q) Grille 2D de p x q sommets. ....hypercube d (= grid d 2 ... 2) Hypercube de dimension d. ....path n (= grid 1 n) Chemin à n sommets. ....cycle n (= ring n 1 1) Cycle à n sommets. ....torus p q (= grid 2 -p -q) Tore à p x q sommets. ....stable n (= ring n 0) Stable à n sommets. ....clique n (= -not ring n 0) Graphe complet à n sommets. ....bipartite p q (= rpartite 2 p q) Graphe biparti complet K_{p,q}. ....tree n (= arboricity n 1) Arbre plan enraciné aléatoire à n sommets. Les sommets sont numérotés selon un parcours DFS (et plan) à partir de la racine. ....random n p (= -not ring n 0 -dele 1-p) Graphe aléatoire à n sommets et dont la probabilité d'avoir une arête entre chaque pair de sommets est p. L'option -dele étant déjà présente, il n'est pas conseillé de la réutiliser pour ce graphe. ....petersen (= kneser 5 2 0) Graphe de Kneser particulier. Il est cubic et possède 10 sommets. Il n'est pas Hamiltonien et c'est le plus petit graphe dont le nombre de croisements est 2. ....headwood (= cage 14 2 5 -5) Graphe de Headwood. C'est un graphe cubic à 14 sommets, de maille 6 et de diamètre 3. C'est le plus petit graphe dont le nombre de croisements est 3. ....pappus (= cage 18 6 5 7 -7 7 -7 5) Graphe de Pappus. C'est un graphe cubic à 18 sommets, de maille 6 et de diamètre 4. ....mcgee (= cage 24 3 12 7 -7) Graphe de McGee. C'est un graphe cubic à 24 sommets, de maille 7 et de diamètre 4. ....levi (= cage 30 6 9 13 -13 -9 7 -7) Graphe de Levi. C'est un graphe cubic à 30 sommets, de maille 8 et de diamètre 4. ....tutte-coexter (= cage 30 4 9 13 -13 -9) Graphe de Tutte-Coexter appelé aussi 8-cage de Tutte. C'est un graphe cubic à 30 sommets, de maille 8 et de diamètre 4. ....wagner (= ring 8 2 1 4) Graphe de Wagner, appelé aussi graphe W8. C'est un graphe cubic à 8 sommets qui n'est pas planaire. C'est aussi un graphe de Möbius. ....mobius n (= ring n 2 1 n/2) Echelle de Möbius. Il s'agit d'une échelle (grille 2xn) dont les bords de la première et la dernière ligne sont connectés avec un croisement d'arêtes. ....binary h (= arytree h 2 2) Arbre binaire de profondeur h possédant 2^(h+1)-1 sommets. La racine est de degré deux. ....tw n k (= ktree n k -dele .5) Graphe de largeur arborescente au plus k, aléatoire et avec n sommets. Il s'agit d'un k-arbre partiel aléatoire dont la probabilité d'avoir une arête est 1/2. L'option -dele étant déjà présente, il n'est pas conseillé de la réutiliser pour ce graphe. ....pw n k (= kpath n k -dele .5) Graphe de pathwidth au plus k, aléatoire et avec n sommets. A FAIRE : -theta n k: Theta-graph d'angle 2pi/k -Yao n k: Yoa-graph d'angle 2pi/k -dtheta6 n: demi-theta graphe -delaunay n: triangulation du plan suivant delaunay (donc planaire) -sub a b: subdivise chaque arête par un nombre d'arêtes x entier pris aléatoirement uniforme dans [a,b]. si a=b alors pas de random. problème: n n'est pas connu avant la construction. -line: calcule le line graphe. Cette fonction est calculée après toute les autres (-notP, -redirect, -del). Pour cela on calcule virtuellement le graphe (en modifiant Out(i,j)) puis on calcule le nouveau nb de sommets (=nb d'arêtes) et sort les nouvelles adjacences. -fast: utilise une procédure spécialisée (si elle existe) pour la génération de certain graphes peu denses, comme tree ou outerplanar, qui évite une complexité en O(n^2) graphes orientés: i->j (...) + (...): union de graphes (numéros de gauche à droite) (...) x (...): produit carthésien de graphes HISTORIQUE: v1.2 octobre 2007: - première version v1.3 octobre 2008: - options: -shift, -width - correction d'un bug pour les graphes de permutation - accélération du test d'ajacence pour les arbres, de O(n) à O(1) grâce à la représentation implicite - nouveau graphes: outerplanar, sat v1.4 novembre 2008: - format de sortie: matrix, smatrix, list - nouveau graphe: kout - correction d'un bug dans l'option -width - correction d'un bug dans la combinaison -format/shift/delv v1.5 décembre 2008: - correction d'un bug dans tree lorsque n=1 v1.6 décembre 2009: - nouveaux graphes: rpartite, bipartite v1.7 janvier 2010: - nouveaux graphes: icosa, dodeca, rdodeca, cubocta, geo, wheel, cage, headwood, pappus, mcgee, levi, butterfly, hexagon, whexagone, arytree, binary, ktree, tw, kpath, pw, arboricity, wagner, mobius, tutte-coexter, paley - format de sortie: dot - options: -header, -h, -redirect, -dotpdf - correction d'un bug dans kout, et dans tree lorsque n=0 - tree devient un cas particulier d'arboricity. - aide en ligne pour les paramètres des graphes. ### #*/