/*utf8* Graph Generator - v2.8 - © Cyril Gavoille - November 2011 Use: gengraph [-option] graph_name [parameter_list] A free command-line program to generate undirected graphs in many formats: plain text, .dot, .pdf, .fig, .svg ... Formats like .pdf or .fig are produced thanks to GraphViz and allow visualization. Easy to install, there is a single .c file to compile. There is a on-line manual available in the command (for the moment the manual is in French only and included at the end of the source). ----- Petit programme libre en ligne de commande permettant de générer des graphes non orientés dans plein de formats différents: texte, .dot, .pdf, .fig, .svg ... Certains formats (comme .pdf ou .jpg), produit grâce à GraphViz, permettent la visualiser des graphes. Très simple à installer, il n'y a qu'un seul fichier .c à compiler. Pour le reste il faut voir l'aide en ligne qui est aussi incluse à la fin du source. Comment l'installer / le compiler ? (Linux) gcc gengraph.c -lm -o gengraph (MacOs) gcc gengraph.c -o gengraph */ #include /* pour printf(), sprintf() ... */ #include /* pour system(), RAND_MAX ... */ #include /* pour strcomp() ... */ #include /* pour getpid() ... */ #include /* pour cos(), acos(), hypot() ... */ #include /* pour DBL_MAX ... */ #include /* pour strtod(), INT_MAX, LONG_MAX, DBL_MAX ... */ /* types */ /* graphe ou famille de graphes */ typedef struct _graph { int id; // numéro du graphe, utilisé pour les familles de graphes int n; // nb de sommets, <0 si non défini int m; // nb d'arêtes, <0 si non défini int sort; // vrai ssi les listes d'adjacences sont triées int *d; // tableau des degrés, =NULL si non défini int **L; // liste d'adjacence, =NULL si non défini // L[u][i]: i-ème voisin du sommet u int f; // nb de graphes de la famille, =0 si graphe normal int sym; // vrai ssi les listes d'adjacence du graphe sont symétriques double **W;// tableau de poids des arcs, =NULL si non défini // W[u][i]: poids du i-ème voisin du sommet u double *xpos,*ypos; // tableau de positions des sommets (graphe géométrique) struct _graph **G; // tableau de graphes, =NULL si non défini // les champs suivants sont utilisés pour communiquer des valeurs // ou des résultats à travers les appels de fonctions int int1; // paramètre: entier int* pint1;// paramètre: tableau d'entiers } graph; typedef int test(graph*); /* fonction de test sur un graphe */ /* chemin simple d'un graphe G */ typedef struct{ int n; /* nb de sommets du chemin */ int *P; /* liste ordonnée des sommets du chemin */ int *V; /* V[u]=i si le sommet u de G est le i-ème (i dans [0,G->n[) sommet du chemin (V[P[i]]=i), V[u]=-1 si u n'est dans le chemin */ int **aux; /* tableau auxiliaire utilisé (et géré) par NextPath() */ int nG; /* nb de sommets du graphe G, sert pour free_path() */ } path; typedef int adjacence(int,int); /* fonction d'adjacence */ typedef struct _list { int item,type; struct _list *next; } list; /* liste chaînée */ typedef struct { double x,y; } point; /* un point du plan */ typedef struct { int u,v; } edge; /* une arête */ typedef struct { unsigned int r:8,g:8,b:8; } color; /* une couleur est un int accessible par les champs r,g,b de 8 bits */ /* constantes */ #define DIMAX 32 /* nb maximum de paramètres pour un graphe */ #define CMDMAX 512 /* nb maximum de caractères sur la ligne de commande */ #define NAMEMAX 20 /* nb maximum de caractères d'un nom de sommet */ #define PARAMSIZE 1024 /* taille mémoire des buffers FPARAM et CPARAM (en octets) */ /* constantes pour le format dot (-visu) */ #define GRAPHPDF "g.pdf" /* nom du graphe de sortie par défaut */ #define VSIZESTD 0.05 /* taille standard des sommets */ #define VSIZEXY 0.12 /* taille des sommets pour les graphes géométriques */ #define VSIZEK 5.5 /* rapport entre taille max et min des sommets (-vsize) */ #define C32 32 /* Coefficient par lequel sont multipliées les coordonnées des points dans le cas des graphes géométriques pour le format dot. Plus la valeur est élevée, plus les sommets paraissent petits et les arêtes fines. */ /* codes pour les formats de sorties possibles */ #define F_standard 0 #define F_list 1 #define F_matrix 2 #define F_smatrix 3 #define F_dot 4 #define F_xy 5 #define F_no 6 /* codes pour les algorithmes possibles */ #define CHECK_BFS 2 #define CHECK_DFS 3 #define CHECK_DEGENERATE 4 #define CHECK_GCOLOR 5 #define CHECK_DEG 6 #define CHECK_PATHS 7 #define CHECK_ISO 8 #define CHECK_SUB 9 #define CHECK_ISUB 10 #define CHECK_MINOR 11 #define CHECK_TWDEG 12 #define CHECK_TW 13 #define CHECK_PS1 14 /* les valeurs PS1? doivent être consécutives */ #define CHECK_PS1b 15 #define CHECK_PS1c 16 #define CHECK_PS1x 17 #define CHECK_GIRTH 18 #define CHECK_PATHS2 19 #define CHECK_BELMAN 20 #define CHECK_MAINCC 21 /* macros utiles */ #define EQUAL(s) (strcmp(ARGV[i],s)==0) #define PREFIX(s) (strncmp(ARGV[i],s,strlen(s))==0) #define MIN(i,j) (((i)<(j))?(i):(j)) #define MAX(i,j) (((i)>(j))?(i):(j)) #define SWAP(x,y,z) do{z=x;x=y;y=z;}while(0) /* échange les valeurs x et y, via z */ #define VIDE(s) *s='\0' /* vide le tableau de caractères s */ #define ESTVIDE(s) (*s=='\0') /* vrai ssi s est vide */ #define NONVIDE(s) (*s!='\0') /* vrai ssi s est non vide */ #define RAND01 ((double)random()/(double)RAND_MAX) /* réel aléatoire dans [0,1[ */ #define COLORNB ((int)sizeof(COLORCHAR)-1) /* nb de couleur dans la palette de base */ #define MEM(mem,pos,type) (*(type*)(mem+pos)) /* écrit/lit la mémoire mem+pos */ /* alloue à la variable T un tableau de n cases de type t */ #define ALLOC(T,n,t) \ do{ \ if(((T)=(t*)malloc((n)*sizeof(t)))==NULL) Erreur(3); \ } while(0) /* comme ALLOC mais initialise le tableau avec z */ #define ALLOCZ(T,n,t,z) \ do{ \ if(((T)=(t*)malloc((n)*sizeof(t)))==NULL) Erreur(3); \ int _i;for(_i=0;_iL[u][G->d[u]++]=v; \ G->L[v][G->d[v]++]=u; \ }while(0) /* comme ADD_EDGE */ #define ADD_ARC(G,u) \ do{ \ G->L[u][G->d[u]++]=v; \ }while(0) /* macros de débuggage */ // affiche une variable int #define PRINT(v) \ do{ \ printf(#v " = %i\n",v); \ } while(0) // affiche un tableau #define PRINTT(T,n) \ do{ \ int _i; \ printf(#T " ="); \ if((T)==NULL) printf(" NULL"); else \ for(_i=0;_i<(n);_i++) printf(" %i",(T)[_i]); \ printf("\n"); \ } while(0) // affiche une liste chaînée #define PRINTLIST(L) \ do{ \ list *_L=L; \ printf(#L " = {"); \ while(_L!=NULL){ \ printf(" (%i,%i)",_L->item,_L->type); \ _L=_L->next; \ } printf(" }\n"); \ } while(0) #define PAUSE scanf("%*c") /* appuyer sur RETURN pour continuer */ #define STRTOI(s) ((int)strtol(s,NULL,10)) #define STRTOD(s) strtod(s,NULL) /* variables globales */ adjacence *adj; /* nom de la fonction d'adjacence */ int N; /* N=nb de sommets du graphes avant suppression */ int NF; /* nb de sommets final du graphes (donc après suppression) */ int *V; /* étiquette des sommets, en principe V[i]=i */ int *VF; /* VF[j] est l'indice i du j-ème sommet non supprimé */ int *INC; /* INC[i]=deg(i). Si =0, alors i est un sommet isolé */ int SHIFT=0; /* début de la numérotation des sommets */ int PARAM[DIMAX];/* liste des paramètres du graphe */ void* CPARAM=NULL; /* liste de paramètres (pointeur tout type, en octets) pour -check */ void* FPARAM=NULL; /* liste de paramètres (pointeur tout type, en octets) pour -filter */ int CVALUE; /* sert pour la valeur dans -filter */ int PVALUE; /* 1 ssi on affiche la valeur du paramètre dans -filter */ test *FTEST; /* pour l'option -filter */ double DPARAM[DIMAX]; /* idem PARAM, mais si paramètres de type double */ 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 DIRECTED=0; /* vrai ssi graphe orienté for(i=0 ... for(j=...) ) */ int LOOP=0; /* vrai ssi ont n'affiche pas les boucles */ int PERMUTE=0; /* vrai ssi -permute */ int NOT=0; /* vrai ssi -not */ int STAR=0; /* paramètre de -star */ int POS=0; /* vrai ssi -pos */ int LABEL=0; /* vrai ssi affiche les labels des sommets */ int CHECK=0; /* vrai ssi option -check */ int NORM=2; /* Norme pour les graphes géométriques: L_2 par défaut */ int FORMAT=F_standard; /* type de la sortie, par défaut le format standard */ int HEADER=0; /* par défaut pas de préambule, sinon HEADER=1 */ int EXTHEADER=0; /* vrai ssi affiche (et donc calcule) m,maxdeg,mindeg ...*/ 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 */ char *FILEXY=NULL; /* pointeur sur le nom de fichier */ char *DOTFILTER="neato"; /* pointeur sur le filtre "dot" par défaut */ char NAME[NAMEMAX]; /* nom du sommet retourné par adj(i,-2) */ char SPARAM[32]; /* un paramètre de graphe de type string */ char *STRsep1; /* séparateur d'arête: "" (pour standard) ou ";" (dot) */ char *STRsep2; /* autre séparateur */ char *STRedge; /* caractère pour une arête: "-" (pour standard) ou "--" (dot) */ int ARGC; /* variable globale pour argc */ char **ARGV; /* variable globale pour argv */ double *XPOS=NULL,*YPOS=NULL; /* tableaux (X,Y) pour les graphes géométriques */ double SCALEX=-1.0,SCALEY; /* pour le redimensionement: <0 signifie pas de redimen. */ double NOISEr=-1.0,NOISEp; /* paramètre pour -xy noise: <0 signifie pas de "noise". */ double XMIN=0,YMIN=0; /* Bounding Box par défaut */ double XMAX=1,YMAX=1; /* Bounding Box par défaut */ int ROUND=10; /* valeur impossible. L'arrondi de XPOS/YPOS à 10^-ROUND près */ int XYtype=1; /* type de génération des points, par défaut=1=uniforme */ int XYunique=0; /* =1 ssi on élimine les points doubles */ int SEEDk; /* nombre de graînes */ double SEEDp; /* loi puissance pour les graines */ double *XSEED=NULL,*YSEED=NULL; /* tableaux de doubles pour les graînes */ int WRAP[DIMAX]; /* WRAP[k]=1 ssi la dimension k est "torique" */ list *L0,*L1,*L2; /* listes utilisées pour -check (tête,dernier,avant-dernier) */ graph *LOAD=NULL; /* graphe pour "load file" */ graph *GF=NULL; /* graphe pour l'option -check */ graph *FAMILY=NULL; /* graphe pour l'option -filter */ int *TREE; /* tableau global pour les arbres (sert aussi pour les outerplanars) */ int **REP; /* Associe à chaque sommet i une représentation sous forme de tableau d'entiers (REP[i] est donc un tabeau). Sert pour les représentations implicites de graphes, les arbres, les graphes d'intersections, etc. */ double **DREP; /* comme REP mais avec des doubles */ int VSIZE=0; /* code pour la taille des sommets */ int VCOLOR=0; /* code couleur pour les sommets */ char COLORCHAR[]="redjykugfocatbhsqvmpinzxlw"; color COLORBASE[]={ /* HTML Color Names */ /* palette des couleurs de bases, l'ordre doit être celui de COLORCHAR */ {255,0,0}, // r=red {210,105,30}, // e=chocolate {255,140,0}, // d=darkorange {255,165,0}, // j=orange {255,255,0}, // y=yellow {240,230,140}, // k=khaki {154,205,50}, // u=yellowgreen {0,255,0}, // g=green (lime) {34,139,34}, // f=forestgreen {128,128,0}, // o=olive {0,255,255}, // c=cyan {127,255,212}, // a=aquamarine {0,128,128}, // t=teal {0,0,255}, // b=blue {255,105,180}, // h=hotpink {250,128,114}, // s=salmon {255,192,203}, // q=pink {238,130,238}, // v=violet {255,0,255}, // m=magenta {128,0,128}, // p=purple {75,0,130}, // i=indigo {0,0,128}, // n=navy {0,0,0}, // z=black {128,128,128}, // x=gray {230,230,250}, // l=lavender {255,255,255} // w=white }; color *PALETTE=COLORBASE; /* palette par défaut */ int NPAL=COLORNB; /* taille de la palette par défaut */ /*********************************** ROUTINES EN VRAC ***********************************/ void Erreur(int error){ char *s="Erreur : code d'erreur inconnue."; /* erreur par défaut, ne devrait jamais se produire */ switch(error){ case 1: s="Erreur : option -xy non reconnue."; 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; case 7: s="Erreur : ouverture du fichier impossible."; break; case 8: s="Erreur : tableau de coordonnées inexistant."; break; case 9: s="Erreur : option -vcolor non reconnue."; break; case 10: s="Erreur : nom de graphe inconnu."; break; case 11: s="Erreur : option -algo non reconnue."; break; case 12: s="Erreur : option -check non reconnue."; break; case 13: s="Erreur : format de famille de graphes invalide."; break; case 14: s="Erreur : option -filter non reconnue."; break; case 15: s="Erreur : graphe(s) non trouvé(s)."; break; case 16: s="Erreur : plage de valeurs incorrecte."; break; case 17: s="Erreur : nom de sommets trop grand."; break; } printf("%s\n",s); exit(EXIT_FAILURE); } int GraphFromArray(int i,int j,int *T){ /* Fonction générique pour générer des graphes fixés de petite taille. En gros, GraphFromArray(i,j,T)=1 ssi i et j se suivent dans le tableau T. On utilise le nombre de sommets N. Les arêtes du graphe sont ainsi couvertes par des chemins éventuellement non élémentaires. Les valeurs négatives du tableau ont des significations particulières. -1: fin d'un chemin ou d'une séquence. -2: fin du tableau et donc du graphe. -3: sommets consécutifs. Une suite "a,-3,n" est équivalent à "a,a+1,...,a+n,-1" -4: cycle hamiltonien, équivalent à "0,-3,N-1,0,-1" -5: étoile, "a,-5,a_1,...,a_n,-1" représente une étoile de centre a et de feuilles a_1...a_n. C'est équivalent à "a, a_1, a, a_2, a,..., a, a_n, -1." On peut remplacer le -1 par n'importe qu'elle valeur négative qui peut ainsi être enchaînée. -6: comme -5, sauf que les sommets a_i,a_{i+1} sont adjacents. Une bonne stratégie pour trouver un code assez court pour un graphe est de l'éplucher par degré maximum jusqu'à obtenir des chemins ou cycles, les sommets isolés n'ont pas à être codés. Les sommets enlevés peuvent être codés par -5 ou -6, les cycles et les chemins par -3. */ int k=0,a,n; while(T[k]!=-2){ if(T[k]==-3){ a=T[k-1]; n=T[++k]; if((a<=i)&&(i=0){ if((i==a)&&(j==T[k])) return 1; if((j==a)&&(i==T[k])) return 1; } continue; } if(T[k]==-6){ a=n=T[k-1]; while(T[++k]>=0){ if(((i==a)||(i==n))&&(j==T[k])) return 1; if(((j==a)||(j==n))&&(i==T[k])) return 1; n=T[k]; } continue; } if((i==T[k])&&(j==T[k+1])) return 1; if((j==T[k])&&(i==T[k+1])) return 1; next: k++; } return 0; } void Permute(int *T,int n){ /* Permute aléatoirement les n premiers éléments de T */ int i,j,k; for(i=0;i0, les lettres sont écrites dans le sens croissant des indices (de gauche à droite), si d<0 c'est dans le sens des indices décroissant. Ex: R={3,6,1}, n=3 et d=1. sep="," et par="{}": alors NAME={3,6,1} sep="-" et par="": alors NAME=3-6-1 sep="" et par="": alors NAME=361 */ int i; char s[NAMEMAX]; char vide[2]="\0\0"; /* vide=00 */ VIDE(NAME); for(i=0;i0) strcat(NAME,s); else{ strcat(s,NAME); strcpy(NAME,s); } if(i aux nombres de valeurs qu'il contient et le fichier contient un retour de ligne final. */ FILE *f=stdin; int n,i,r; if(strcmp(file,"-")) f=fopen(file,"r"); /* ouvre en lecture */ if(f==NULL) Erreur(7); i=fscanf(f,"%i",&n); /* lit n */ if((n<0)||(i<0)) n=0; ALLOC(XPOS,n,double); ALLOC(YPOS,n,double); for(i=0;(i0) continue; r=fscanf(f,"%lf %lf",XPOS+i,YPOS+i); } fclose(f); return i; /* i=minimum entre n et le nb de valeurs lues */ } list *Insert(list *p,int v,int t){ /* Ecrit (v,t) dans l'élément de la liste pointée par p, puis crée et retourne le prochain pointeur libre. Si p=NULL, alors on crée un nouvel élément que l'on retourne. */ list *l; ALLOC(l,1,list); l->next=NULL; if(p==NULL){ l->item=v; l->type=t; } else{ p->item=v; p->type=t; p->next=l; } return l; } graph *new_graph(int n){ /* Renvoie un objet de type "graph". Les champs sont initialisés. Si n>0, alors les tableaux ->d et ->L de taille n sont alloués. */ graph *G; ALLOC(G,1,graph); G->n=n; G->m=-1; G->sort=0; G->id=-1; G->d=NULL; G->L=NULL; G->W=NULL; G->xpos=NULL; G->ypos=NULL; G->f=0; G->sym=1; G->G=NULL; G->pint1=NULL; G->int1=-1; if(n>0){ ALLOC(G->d,n,int); ALLOC(G->L,n,int*); } return G; } void free_graph(graph *G) /* Libère tous les tableaux d'un graphe G. Dans le cas d'une famille, chaque graphe est aussi libéré. */ { if(G==NULL) return; /* Remarque: ce n'est pas grave de faire free() sur un ptr NULL */ int i; free(G->d); free(G->pint1); free(G->xpos); free(G->ypos); FREE2(G->L,G->n); FREE2(G->W,G->n); for(i=0;if;i++) free_graph(G->G[i]); free(G->G); free(G); } path *new_path(graph *G,int *P,int n){ /* Créer un chemin d'un graphe G, défini par une liste P de n sommets de G. Attention, le pointeur P est utilisé par le chemin (struct path) renvoyé. Il ne faut pas détruire P après cet appel. P sera libéré par free_path(). Si P=NULL, alors le champs ->P de taille n est alloué, et le champs ->n=0. C'est une façon de créer un chemin simple et vide. Dans ce cas n représente la longueur maximum d'un chemin de G. Le champs ->V (de taille G->n) est initialisé selon P, si P<>NULL, ou à -1 sinon. */ if(G==NULL) return NULL; path *Q; ALLOC(Q,1,path); ALLOCZ(Q->V,G->n,int,-1); Q->aux=NULL; Q->nG=G->n; if(P==NULL){ ALLOC(Q->P,n,int); Q->n=0; } else{ int i; Q->P=P; for(i=0;iV[P[i]]=i; Q->n=n; } return Q; } void free_path(path *P) { if(P==NULL) return; free(P->P); free(P->V); FREE2(P->aux,P->nG); free(P); } int fcmp_int(const void *P,const void *Q) /* Compare deux entiers, pour qsort(). */ { return (*(int*)P - *(int*)Q); } int fcmp_point(const void *P,const void *Q) /* Compare deux points, pour qsort(). */ { if(((point*)P)->x < ((point*)Q)->x) return -1; if(((point*)P)->x > ((point*)Q)->x) return 1; if(((point*)P)->y < ((point*)Q)->y) return -1; if(((point*)P)->y > ((point*)Q)->y) return 1; return 0; } int fcmp_profile(const void *P,const void *Q) /* Compare deux profiles, pour qsort(). Les profiles de plus grande longueur sont classés avant les plus courts, ceux-ci étant plus discriminant. */ { int* A=*(int**)P; int* B=*(int**)Q; if(*A>*B) return -1; /* si long(A)>long(B), alors AB */ /* ici, profiles de même longueur n=A[0] */ int u=2,n=*A; /* surtout ne pas utiliser A[1] */ for(;uB[u]) return 1; } return 0; } int fcmp_graphid(const void *P,const void *Q) /* Compare les identifiants de deux graphes. Sert pour qsort() et bsearch(). Ici, P et Q sont des pointeurs de (graph*). */ { return ( ((*(graph**)P)->id) - ((*(graph**)Q)->id) ); } int ReadRange(char *s,int *R) /* Lit une chaîne de caractères décrivant un intervalle de valeurs entières, et renvoie dans le tableau d'entiers R les valeurs et les codes correspondant pour que la fonction InRange(x,R) puisse fonctionner. On ignore les caractères non reconnus (pas d'erreur). On renvoie le nombre d'opérations décodées, c'est-à-dire le nombre de valeurs écrites dans le tableau R, nombre qui est aussi écrit dans la première entrée de R. Ex: s="1,-3,5-7,>30,<50" (on interprète les "," comme des "ou") => R={12,code=,1,code=,-3,code-,5,7,code>,30,code<,50} (12=taille(R)) La valeur des codes d'opérations (code=,code<...) sont données par la fonction InRange(). */ { if(R==NULL) return 0; if(s==NULL){ R[0]=0; return 0; } int i,r,p,x,start,c; i=x=c=0; r=start=p=1; /* r=indice de R[] */ /* i=indice de s[] */ /* x=valeur entière lue */ /* c=1 ssi le code d'opération a été détecté */ /* start=1 ssi on va commencer à lire un entier */ /* p=1 ou -1, signe de x */ while(s[i]!='\0'){ if(s[i]=='='){ R[r++]=0; c=start=p=1; } if(s[i]=='<'){ R[r++]=1; c=start=p=1; } if(s[i]=='>'){ R[r++]=2; c=start=p=1; } if(s[i]=='-'){ if(start) p=-p; else{ R[r++]=3; R[r++]=x; c=start=p=1; } } if(s[i]=='t'){ x=4; c=r=1; break; } /* t=true, pour avoir false faire "not" et "t" */ if(s[i]=='p') PVALUE=1; if(s[i]==','){ if(c==0) R[r++]=0; /* code '=' par défaut */ R[r++]=x; c=0; start=p=1; } if((s[i]>='0')&&(s[i]<='9')){ if(start) start=0; x=x*10+p*(s[i]-'0'); /* on lit x en base 10 en tenant compte du signe p */ } if(start) x=0; i++; } if(PVALUE==i){ x=4;c=1; } /* si s="p", alors comme "t" */ if(c==0) R[r++]=0; R[r++]=x; /* on ajoute le dernier opérande */ R[0]=r; return r; } int InRange(int x,int* R) /* Détermine si x appartient aux valeurs décrites par le "range" R. R[0] est la taille de R, R[0] compris. */ { int i,n,t; n=R[t=0]; i=1; CVALUE=x; while(iR[i++]); break; case 3: t=((R[i]<=x)&&(x<=R[i+1])); i+=2; break; case 4: return 1; default: Erreur(16); } if(t) break; } return t; } void PrintGraphList(graph *G) /* Affiche le graphe G sous la forme d'une liste d'adjacence. Tient compte de SHIFT. */ { if(G==NULL){ printf("NULL\n"); return; } int u,d,i,n=G->n; for(u=0;ud[u];iL[u][i]+SHIFT); } printf("\n"); } return; } void PrintGraphMatrix(graph *G) /* Affiche le graphe G sous la forme d'une matrice d'adjacence complète ou triangulaire supérieure (en tennant compte du FORMAT, smatrix ou matrix). La complexité en espace est seulement de O(n). */ { int u,d,i,z,t,n=G->n; int *M; ALLOCZ(M,n,int,0); t=(FORMAT==F_smatrix); for(u=z=0;ud[u];iL[u][i++]]=1); for(i=0;iL[u][i++]]=0); /* remet rapidement M[] tout à 0 */ printf("\n"); } free(M); return; } void PrintPath(graph *G,path *P) /* Affiche le chemin P d'un graphe G. Sert pour le débugage. */ { if((G==NULL)||(P==NULL)) printf("NULL\n"); int i,j,u,d; for(i=0;in;i++) if(P->V[P->P[i]]!=i) break; if(in) goto error; for(u=0;un;u++) if((P->V[u]>=0)&&(P->P[P->V[u]]!=u)) break; if(un) goto error; printf("P->aux:"); if(P->aux==NULL) printf(" NULL\n"); else{ printf("\n"); for(i=0;in;i++){ u=P->P[i]; d=P->aux[u][0]; printf(" %i:",u); for(j=1;j<=d;j++){ printf(" %i",P->aux[u][j]); } printf("\n"); } } return; error: printf("Chemin incohérent.\n"); return; } void SortGraph(graph *G) /* Trie la liste d'adjacence d'un graphe G, c'est-à-dire pour chaque sommet u, G->L[u] est une liste d'entier trié par ordre croissant. L'algo, simplissime et basé sur qsort(), est à peu près en O(n+m*log(m/n)). [A FINIR: Il faudrait améliorer la fonction pour enlever les boucles et arêtes multiples] */ { if(G==NULL) return; int u,n=G->n; for(u=0;uL[u],G->d[u],sizeof(int),fcmp_int); G->sort=1; return; } void GraphRealloc(graph *G,int *D) /* Redimensionne le graphe G à G->n sommets. On réajuste en premier les tableaux G->d et G->L pour qu'ils aient une taille G->n, puis réajuste les listes d'adjacences des sommets de G suivant le tableau des degrés D (qui doit être de taille au moins G->n). Si D[u] est plus petit que G->d[u], alors la liste G->L[u] est tronquée. Si D[u] est plus grand que G->d[u], alors G->L[u] est réajusté. Le degré G->d[u] est initialisé au minimum de G->d[u] et de D[u]. Pour plonger G dans un graphe complet faire: int *D=ALLOCZ(D,n,int,n-1); GraphRealloc(G,D); ... free(D); */ { int u,d,n=G->n; for(u=0;uL[u]=REALLOC(G->L[u],d,int); G->d[u]=MIN(G->d[u],d); } /* Il ne faut pas réajuster G->d et G->L avant la boucle for(u=...) car potentiellement on libère G->d et G->L. Or il est possible d'avoir D=G->d. */ G->d=REALLOC(G->d,n,int); G->L=REALLOC(G->L,n,int*); return; } graph *new_fullgraph(int n){ /* Retourne un graphe G comme new_graph(n), mais en plus alloue G->L[u] de taille MAX(n-1,1), et initialise G->d[u]=0 pour tous les sommets u. Une fois le graphe construit, on peut rédimensionner le graphe grâce à GraphRealloc, comme dans l'exemple: graph *G=new_fullgraph(n); ... ADD_EDGE(G,u1,v1); ADD_EDGE(G,u2,v2); ... GraphRealloc(G,G->d); ... free_graph(G); */ if(n<1) return NULL; graph *G=new_graph(n); int u,n1=MAX(n-1,1); for(u=0;ud[u]=0; ALLOC(G->L[u],n1,int); } return G; } graph *ExtractSubgraph(graph *G,int *T,int k,int code){ /* Construit, à partir d'un graphe G et d'une liste T de k sommets, un nouveau graphe S correspondant au sous-graphe de G induit par les sommets de T (code=1) ou de V(G)\T (si code=0). Les sommets de S sont dans [0,k[ (ou [0,n-k[ si code=0). Effet de bord: S->pint1 est alloué si T!=NULL. Dans ce cas on renvoie dans S->pint1 un tableau X de taille G->n indiquant la renumérotation de G: pour tout sommet u de G (u dans [0,G->n[) S->pint1[u]=0 si u est un sommet abscent de S et S->pint1[u]=d>0 si u est numéroté d-1>=0 dans S. Le nombre d'arêtes S->m du graphe S renvoyé est à jour. L'ordre relatif des listes de G est préservé. En particulier, si G->sort=1, alors le sous-graphe sera aussi trié. G->sym est aussi copié. Remarque: pour renvoyer une copie du graphe G, faire: graph *C=ExtractSubgraph(G,NULL,0,0); */ if(G==NULL) return NULL; int *X; int n=G->n; int u,v,d,i,s,ns,m; graph *S; ALLOC(X,n,int); for(u=1-code,i=0;i0 si i doit être renuméroté en d-1>=0 */ ns=(code)?k:n-k; S=new_fullgraph(ns); for(s=u=m=0;ud[u]; for(i=0;iL[u][i]; if(X[v]){ m++; S->L[s][S->d[s]++]=X[v]-1; } /* si v existe */ } s++; } /* réduit la taille des listes */ GraphRealloc(S,S->d); S->pint1=X; S->sort=G->sort; S->sym=G->sym; S->m=(m>>1); return S; } graph *List2Graph(list *L,int code){ /* Retourne un graphe à partir d'un graphe G défini par une liste (voir File2List() pour le codage précis du type "list"). Met à jour G->n, le nombre de sommets du graphe. Certaines opérations sont effectuées sur L en fonction de la valeur binaire de code (voir ci-dessous). Effet de bord: si code&16=0, alors L est libérée. Pour calculer le graphe (et sa liste d'adjacence) on effectue plusieurs passes sur L: 1) on détermine n; 2) les degrés; et 3) on remplit G et on vide la liste L. Les bits de "code" ont la signification suivante: - code&1 =1: optimisation des listes du graphe (tri par ordre croissant) =0: sans optimisation - code&2 =1: auto-détection du shift dans L (pour "load file") =0: pas d'auto-détection du shift - code&4 =1: gestion d'un sous-graphe (V,NF) => code&2=0 =0: pas de sous-graphe - code&8 =1: tri de la famille suivant les identifiants (sert pour List2Family) =0: pas de tri de la famille - code&16=1: ne libère pas la liste L (sert aussi pour List2Family) =0: libère la liste L (par défaut) - code&32=1: renvoie toujours un graphe, le 1er si c'est une famille =0: renvoie une famille si c'est une famille */ if(L==NULL) return NULL; /* si pas de cellule, ne rien faire */ int u,v,x,n,*D; graph *G; list *p; u=INT_MAX; if(code&4){ /* si sous-graphe */ p=L; while(p!=NULL){ p->item=V[p->item]-SHIFT; p=p->next; } n=NF; /* on connaît n */ } else{ /* sinon, on calcule n, et on lit les valeurs min (=u) et valeur max (=v) de L */ p=L; v=0; while(p!=NULL){ x=p->item; if(xv) v=x; p=p->next; } if(code&2){ /* on décale les valeurs dans [0,n[ */ p=L; while(p!=NULL){ p->item -= u; p=p->next; } n=v+1-u; } else n=v+1; } ALLOCZ(D,n,int,0); /* on lit les degrés (sortant) des sommets */ p=L; while(p!=NULL){ v=p->item; if(p->type==1){ D[u]++; D[v]++; } /* u-v */ if(p->type==4) D[u]++; /* u->v */ u=v; p=p->next; } /* on initialise la liste d'adjacence G */ /* on se sert de D[u] pour indiquer la prochaine position libre dans G[u][] */ G=new_graph(n); /* G->n=n, alloue G->d et G->L */ for(u=0;uL[u],D[u],int); /* alloue une liste pour chaque sommet */ G->d[u]=D[u]; /* G->d[u]=deg(u) */ D[u]=0; /* prochaine position libre dans G[u] */ } /* remplit G et libère en même temps L (si code&16=0). On pourrait tester à la volée si les listes sont triées et mettre à jour G->sort */ p=L; while(p!=NULL){ v=p->item; if(p->type==1){ G->L[u][D[u]++]=v; G->L[v][D[v]++]=u; } /* u-v */ if(p->type==4){ G->L[u][D[u]++]=v; G->sym=0; } /* u->v */ u=v; L=p; p=p->next; if(!(code&16)) free(L); } free(D); if(code&1) SortGraph(G); return G; } graph *List2Family(list *L,int code){ /* Transforme une liste en famille de graphes. Si L représente un graphe simple (pas de type 2 ou 3), alors un graphe simple est retournée (plutôt qu'une famille à un seul élément). Donc, List2Family() généralise List2Graph(). On utilise List2Graph() comme sous-routine. Pour "code" voir List2Graph(). Effet de bord: - la liste L est libérée si code&16=0 - la famille est triée par ID croissant si code&8=1 - on retourne un graphe si code&32=1 (plutôt qu'une famille) */ if(L==NULL) return NULL; if(L->type!=3) return List2Graph(L,code); int n=L->item; /* nb de graphes dans la liste */ if(n<=0) return NULL; /* potentiellement on ne libère pas L ... */ int i,id; graph *F=new_graph(0); list *T,*P; F->f=n; ALLOC(F->G,n,graph*); /* F->G[0..n[: tableau de n pointeurs de graphes */ T=L; L=L->next; if(!(code&16)) free(T); /* on libère l'élément (n,3), L=prochain élément */ for(i=0;itype!=2)) Erreur(13); id=L->item; /* identifiant du graph i */ T=L->next; if(!(code&16)) free(L); /* on libère l'élément (id,2) */ P=L=T; /* P=L=T=tête courante du graphe i */ while((L!=NULL)&&(L->type!=2)){ P=L; L=L->next; } /* cherche la fin du graphe i */ /* ici le graphe i va de T à P */ P->next=NULL; /* on coupe la liste */ F->G[i]=List2Graph(T,code); F->G[i]->id=id; } /* éventuellement trie la famille suivant les IDs */ if(code&8) qsort(F->G,F->f,sizeof(graph*),fcmp_graphid); /* extrait le premier graphe */ if(code&32){ graph *G=ExtractSubgraph(F->G[0],NULL,0,0); /* copie le premier graphe */ free_graph(F); /* libère complètement la famille F */ F=G; /* F=premier graphe */ } return F; } list *File2List(char *file){ /* Lit le fichier "file" de graphes au format standard orienté ou non (sans l'option -label 1, mais potentiellement avec -shift) et retourne le contenu dans une liste. Il est possible de spécifier un "range" pour "file" avec la forme: "file:range" où "range" est une liste de valeurs ayant la même signification que pour "-filter F id value". Par exemple, "file:5" spécifie le graphe d'identifiant 5, et "file:5-10" est la famille de graphes contenant les graphes d'identifiant 5 à 10. Notez que "-:5" est le graphe d'identifiant 5 de la famille lue depuis l'entrée standard. Chaque élément de la liste est une paire d'entiers (item,type). La signification de type est la suivante: -type=0: item est un sommet u -type=1: item est un sommet v connecté au précédent de la liste par une arête (u-v) -type=2: item est l'identifiant d'un nouveau graphe d'une famille -type=3: item est le nombre de graphes de la famille -type=4: item est un sommet v connecté au précédent de la liste par un arc (u->v) Si, par exemple, le graphe est "0-1 2 1-2-3 5->4" alors la liste retournée sera {(0,0), (1,1), (2,0), (1,0), (2,1), (3,1), (5,0), (4,4)}. La fonction est généralisée à la lecture d'une famille de graphes. Si le fichier contient "[5] 0-1 [8] 0->2-1" alors la liste contiendra {(2,3), (5,2), (0,0), (1,1), (8,2), (0,0), (2,4), (1,1)}, où le premier élément (n,3) signifie qu'il s'agit d'une famille de n graphes, et où (u,2) signifie que u est l'identifiant d'un nouveau graphe. */ FILE *f; list *T; /* tête de la liste */ list *L; /* élément courant */ list *P; /* sauvegarde le dernier élément */ int v,c=0,read=1; /* par défaut on lit tout */ char *r=NULL; int range[CMDMAX]={2,4}; /* par défaut: toujours vrai */ T=P=L=Insert(NULL,0,0); /* crée la liste */ /* ouverture du fichier: file ou file:range */ f=strcmp(file,"-")? fopen(file,"r"):stdin; if(f==NULL){ /* on a pas réussit à ouvrir file */ //fclose(f); /* il faut fermer le fichier, même si c'est NULL ! */ if((r=strchr(file,':'))==NULL) Erreur(7); *r='\0'; /* coupe file en (préfix,r=range) */ f=strcmp(file,"-")? fopen(file,"r"):stdin; if(f==NULL) Erreur(7); *r++ = ':'; /* rétablit le nom de fichier original de file */ ReadRange(r,range); } /* BUG: si on met "//% ..." dans fscanf() alors 1 commentaire sur 2 n'est pas enlevé correctement. Le format "->%i" dans fscanf() marche moins bien que ">%i" */ /* lecture du fichier */ while(!feof(f)){ if(fscanf(f," /%*[^\n]\n")>0) continue; /* commentaire */ if(fscanf(f," [%i] ",&v)>0){ read=InRange(v,range); if(read){ L=Insert(P=L,v,2); c++; } continue; } if(fscanf(f,"-%i ",&v)>0){ if(read) L=Insert(P=L,v,1); continue; } if(fscanf(f,">%i ",&v)>0){ if(read) L=Insert(P=L,v,4); continue; } if(fscanf(f," %i ",&v)>0){ if(read) L=Insert(P=L,v,0); continue; } v=fscanf(f,"%*c"); /* lit 1 caractère */ } fclose(f); /* on ferme le fichier */ free(L); /* supprime le dernier élément */ if(L==T) return NULL; /* si on a lu aucun élément */ P->next=NULL; if(c>0){ /* il s'agit d'une famille */ /* on ajoute un nouvelle élément en tête de la liste */ L=Insert(NULL,0,0); L->item=c; L->type=3; L->next=T; T=L; /* nouvelle tête */ } return T; /* on retourne la tête */ } graph *File2Graph(char *file,int code){ /* Renvoie un graphe (ou une famille) à partir d'un fichier. Pour "code" voir List2Graph(). La liste intermédiaire est toujours libérée. */ graph *G=List2Family(File2List(file),code&(63-16)); /* annule le bit-4 */ if(G==NULL) Erreur(15); return G; } double PosAspect(){ /* Donne le coefficient par lequel les positions XPOS/YPOS vont être multipliées pour le format dot pour permettre une taille de sommets raisonable. */ double w; w=C32*sqrt((double)N); /* la largeur est en sqrt(N) */ if(LABEL>0) w *= 3; /* augmente l'aspect si besoin des LABELs (et POS) */ return w; } void BoundingBox(){ /* Calcule XMIN,YMIN,XMAX,YMAX des tableaux XPOS/YPOS. */ int i; XMIN=XMAX=XPOS[0]; YMIN=YMAX=YPOS[0]; for(i=1;iXMAX) XMAX=XPOS[i]; if(YPOS[i]>YMAX) YMAX=YPOS[i]; } } void InitXY(void){ /* Initialise les tableaux XPOS et YPOS suivants les options éventuelles de -xy. La valeur de N est éventuellement recalculée (si -xy load), et les BoundingBox (XMIN,XMAX,YMIN,YMAX) mises à jour. */ int i,k; double sx,sy,tx,ty; if(FILEXY!=NULL) N=LoadXY(FILEXY); /* charge à partir d'un fichier et met à jour N */ else{ /* sinon, remplissage aléatoire dans [0,1[ */ if(N<0) N=0; ALLOC(XPOS,N,double); ALLOC(YPOS,N,double); if(XYtype==1) /* random uniforme dans [0,1[ */ for(i=0;i0.0){ /* "noise" doit être avant "scale" */ for(i=0;i0.0)&&(SCALEY>0.0)){ /* "scale" doit être après "noise" */ BoundingBox(); /* calcule les BB */ tx=(XMAX-XMIN); if(tx==0.0) tx=0.5; ty=(YMAX-YMIN); if(ty==0.0) ty=0.5; sx=2.0*sqrt(N+1); /* le +1 est pour être sûr d'avoir sx>0 */ tx /= sx; /* tx=largeur de la bande vide */ ty /= sx; /* ty=hauteur de la bande vide */ sx=SCALEX/(XMAX-XMIN+2.0*tx); /* sx ne peut pas être nul */ sy=SCALEY/(YMAX-YMIN+2.0*ty); /* sy ne peut pas être nul */ for(i=0;idu premier élément */ for(i=k=0;i1)||(NOISEr>0.0)) BoundingBox(); return; } color *GradColor(color *T,int n,int m){ /* Retourne un tableau de m couleurs formant un dégradé obtenu à partir d'un tableau de n couleurs. Pour avoir un dégradé simple d'une couleur T[0] à T[1] il faut initialiser T[0],T[1] et n=2. Pour avoir un dégradé cyclique, il faut répéter la couleur T[0] en dernière poition (et ajouter 1 à n). Il faut dans tous les cas n>1 et m>0. On peut avoir m= 2 */ m1=m-1; n1=n-1; /* utilisés souvent */ k=1; /* indice dans P de la prochaine couleur libre */ if(m<=n){ /* cas où il y a moins de couleurs demandées que dans T */ for(i=1;in. Soient B1,B2,...B_(n-1) les n-1>0 blocs de couleurs, B_i commençant juste après la couleurs T[i-1] et se terminant avec la couleur T[i]. On doit répartir m-1 couleurs dans ces n-1 blocs, la couleurs T[0] étant déjà dans P. On met alors floor((m-1)/(n-1)) couleurs par blocs, et une de plus si i<=(m-1)%(n-1). */ r=m1%n1; /* il reste r couleurs */ q=(m1/n1)+(r>0); /* nombre de couleurs par blocs (+1 au départ si r>0) */ for(i=j=1;i L_1 NORM=2 -> L_2 NORM=3 -> L_max NORM=4 -> L_min */ double x,y; x=XPOS[i]-XPOS[j]; y=YPOS[i]-YPOS[j]; if(NORM==2) return (double)(x*x) + (double)(y*y); /* norme L_2 */ /* x=fasb(x), y=fabs(y) */ if(x<0.0) x=-x; if(y<0.0) y=-y; if(NORM==1) return (x+y); /* norme L_1 */ if(NORM==3) return MAX(x,y); /* norme L_max */ if(NORM==4) return MIN(x,y); /* norme L_min */ return 0.0; /* si aucune NORM trouvée */ } double distgone(int u,int v,int i,int p,int k,double w){ /* Calcule la distance P_i(u,v). Il s'agit de la "distance p-gone" (un polygone régulier à p cotés) relative à la direction i (axe d'angle i*2pi/k) entre les points u et v, restreint au cône de visibilité d'angle w*(p-2)*pi/p (d'angle w*pi si p est infini, c'est-à-dire p<3), w=0...1 (voir aussi la définition du thetagone dans l'aide en ligne). Ici, k est le nombre de directions. L'algorithme est en O(1). Soient a_j (j=0...p-1) les sommets du p-gone P_i de rayon unité avec a_0=u et numérotés consécutivement en tournant dans le sense positif. Soit c le centre de P_i. Donc dist(u,c)=1, les a_j sont sur un cercle de rayon unité. On remarque que l'angle (u,a_j) est indépendant du rayon du p-gone. En fait, l'angle (a_j,u,a_{j+1}) vaut la moitié de l'angle (a_j,c,a_{j+1}), soit pi/p. Et donc l'angle entre deux cotés consécutifs d'un p-gone vaut (p-2)*pi/p. Pour le calcul de distgone(u,v) on fait: 1. Trouver la direction j tq (u,v) est dans le cône de visibilité et dans la région [(u,a_j),(u,a_{j+1})[. Si j n'existe pas, alors on renvoit une distance infinie. Si p est infini, a_j est simplement sur la droite (u,v). 2. On calcule l'intersection v' entre les droites (u,v) et (a_j,a_{j+1}). Si p est infini, v'=a_j. L'intersection existe forcément. Eventuellement v est sur la droite (u,a_j). 3. distgone(u,v)=dist(u,v)/dist(u,v'). */ int j; double xu,xv,dxc,dxa,dxb,dxv; double yu,yv,dyc,dya,dyb,dyv; double hv,A,Ac,Ap,Aw; xu=XPOS[u];yu=YPOS[u]; /* coordonnées de u */ xv=XPOS[v];yv=YPOS[v]; /* coordonnées de v */ Ac=(double)i*2.0*M_PI/(double)k; /* angle (u,c), c=centre de P_i */ dxc=cos(Ac);dyc=sin(Ac); /* coordonnées du centre c dans le repère u */ dxv=xv-xu;dyv=yv-yu; /* coordonnées de v dans repère u */ hv=hypot(dxv,dyv); /* |v-u|=dist(u,v) */ if(hv==0.0) return 0.0; /* si u,v ont les mêmes coordonnées */ /* Rappel: Si a et b sont deux vecteurs, alors le produit scalaire (dot product) est le réel a.b = xa*xb + ya*yb = |a|*|b|*cos(a,b), où |a|=sqrt(xa^2 + ya^2). Donc le signe de cos(a,b) est celui de xa*xb + ya*yb. Pour calculer sin(a,b) il faut faire une rotation de +pi/2 au vecteur a et calculer cos(a',b) où a'=(-ya,xa). Donc sin(a,b) = cos(a',b) = (-ya*xb + xa*yb) / (|a|*|b|). Et le signe de sin(a,b) est celui de xa*yb - ya*xb. */ /* Aw=demi-angle du cône de visibilité */ Aw=0.5*w*M_PI; /* si p infini */ if(p>2) Aw *= (double)(p-2)/(double)p; /* si p est fini */ /* Il faut bien sûr que (u,v) soit dans le cône de visibilité. La bissectrice de ce cône est l'axe (u,c) et son angle est w*(p-2)pi/p (w*pi si p infini). On note (w1,u,w2) le cône en question. Il faut que (u,v) soit entre (u,w1) (compris) et (u,w2) (non compris). Donc si sin(w1,u,v) < 0 ou si sin(w2,u,v) > 0 alors il n'existe pas de j (et donc on retourne une distance infinie). */ A=Ac-Aw; /* A=angle (c,w1) */ dxa=cos(A);dya=sin(A); /* coordonnées de w1 relatif à u */ if(dxa*dyv=dya*dxv) return DBL_MAX; /* v après ou sur w2 */ /* Ici v est dans le cône de visibilité et donc la droite (uv) intersecte P_i en un point v'. */ Ac -= M_PI; /* Ac=Ac-pi */ /* Cas p infini */ if(p<3){ /* On raisone dans le repère u. On pose c'=(dyc,-dxc), c'est-à-dire une rotation de -pi/2 de (u,v). On a |uc'|=1. On calcule l'angle A=(uv,uc'), en fait cos(A). On obtient v' en tournant autour de c d'un angle Ac-M_PI+2A ... */ A=acos((dxv*dyc-dyv*dxc)/hv); A=Ac+2.0*A; dxa=dxc+cos(A);dya=dyc+sin(A); return hv/hypot(dxa,dya); } /* Cas p fini. On cherche j de sorte qu'en tournant dans le sens positif, le vecteur (u,v) soit compris entre (u,a_j) (compris) et (u,a_{j+1}) (non compris). La droite (u,v) intersecte le segment [a_j, a_{j+1}[. L'indice j recherché est l'entier tq: (j-1)*pi/p <= angle(a_1,u,a_j) < j*pi/p. Et donc, j = 1 + floor{arcos(a_1,u,v)/(pi/p)}. */ Ap=2.0*M_PI/(double)p; /* valeur souvent utilisée */ A=Ac + Ap; /* angle (c,a_1) */ dxa=dxc+cos(A);dya=dyc+sin(A); /* coordonnées de a_1 relatif à u */ /* Aw=cos(a_1,u,v) = (a_1-u).(v-u) / dist(a_1,u)*dist(u,v) */ Aw=(dxa*dxv+dya*dyv)/(hypot(dxa,dya)*hv); j=(int)((acos(Aw)*(double)p)/M_PI); /* en fait, la variable j vaut "j-1" */ A += Ap*(double)j; /* angle (c,a_j): on part de a_1, donc on décale de j-1 cônes */ dxa=dxc+cos(A);dya=dyc+sin(A); /* coordonnées de a_j relatif à u */ A += Ap; /* angle (c,a_{j+1}) */ dxb=dxc+cos(A)-dxa;dyb=dyc+sin(A)-dya; /* vecteur (a_j,a_{j+1}) */ /* Calcule l'unique intersection entre la droite Dv définie par le vecteur (u,v) et la droite Dj définie par le vecteur (a_j,a_{j+1}). Dans le repère u, les équations sont: Dv: dyv*X - dxv*Y = 0 Dj: dyb*X - dxb*Y = B avec B=dyb*dxa-dxb*dya, car a_j=(dxa,dya) appartient à Dj. L'intersection (x0,y0) est, dans le repère u: en faisant dxv*Dj-dxb*Dv, on a: x0=dxv*B/(dxv*dyb-dxb*dyv) en faisant dyb*Dv-dyv*Dj, on a: y0=dyv*B/(dxv*dyb-dxb*dyv) */ A=(dyb*dxa-dxb*dya)/(double)(dxv*dyb-dxb*dyv); /* A=B/(...) */ return hv/hypot(dxv*A,dyv*A); } void TraverseRegTree(int h,int k,int r){ /* Parcoure récursivement un arbre régulier de profondeur h, degré interne k et de racine r. Cette fonction fixe REP des sommets de tous les sous-arbres du sommet dont le nom est N, c'est-à-dire REP[N][i]. Après l'appel N vaut le nombre de sommets de l'arbre parcouru, ou encore le nom du prochain sommet. La racine possèdera r fils, les autres k fils. */ int p,i; p=N++; /* Mémorise le nom du père, puis incrémente N. Après N vaut le nom du prochain sommet, et s'il n'y a plus personne, le nombre de sommets du graphe */ if(h==0) return; for(i=0;i=0 dont la somme fait n se qui représenté en unaire correspond à un mot de Dick. La racine (au début) du mot commence à l'indice r renvoyé par la fonction. Ex: pour n=4, on tire B=[0,1,2,1], ce qui en unaire (x -> 1^x0) donne le mot "01011010". Pour obtenir un mot de Dick, il faut décaler B cycliquement de r=1 positions vers la gauche. Ici r=1, pour avoir le mot "10110100". */ { int i,r,s,h; /* remplit B de valeurs dont la somme fait n */ for(i=0;i 1^x0) donne le mot de Dick "01011010". On décale le mot sur un minimum (r=1 pour ce B), d'où le mot "10110100": Mot 3 4 Arbre 0 / \ / \ / \ 1 2 2 2 1 2 / \ / \ / \ 0 0 0 3 4 Ici TREE=[0,1,0,2,3,2,4,2,0] (taille 2N-1): c'est la liste des sommets rencontrés sur une marche le long du mot. On remarque que i et j sont voisins ssi on trouve i,j voisins dans le tableau TREE. Si Si i0 */ if(T==NULL) ALLOCMAT(T,n,1,int); /* l'arbre final */ n1=n-1; ALLOC(B,n1,int); ALLOC(H,n+1,int); /* hauteurs possibles: 0...n */ r=Dick(B,n1); /* Remplissage de TREE: on parcours le mot à partir de la racine r. - H[h]=dernier sommet rencontré de hauteur h. - h=hauteur du dernier sommet de H - s=numéro du prochain sommet - t=index libre du tableau TREE. */ TREE[0]=H[0]=h=0; /* on traite le sommet 0 */ s=t=1; for(i=0;ir, alors c'est un pas montant, et donc T[s][0]=r. */ T[r=i=0][0]=-1; /* pas de père pour la racine */ while(rr) T[s][0]=r; r=s; } /* libère la mémoire */ if(code) free(TREE); return T; } int NextPermutation(int *P,int n,int *C) /* Génère, à partir d'une permutation P, la prochaine dans l'ordre lexicographique suivant les contraintes définies par le tableau C (voir ci-après). On renvoie 1 ssi la dernière permutation a été atteinte. Dans ce cas la permutation la plus petite selon l'ordre lexicographique est renvoyée. On permute les éléments de P que si leur positions sont entre C[j] et C[j+1] (exclu) pour un certain indice j. On peut initialiser P avec ALLOCZ(P,k,int,_i) ou si le tableau P existe déjà avec NextSet(P,-1,k). Ex: C={2,3,5}. Les permutations sous la contrainte C sont: (on peut permuter les indices {0,1}{2}{3,4}) 0 1 2 3 4 (positions dans P) P={a,b,c,d,e} {b,a,c,d,e} {a,b,c,e,d} {b,a,c,e,d} Evidemment, il y a beaucoup moins de permutations dès que les contraintes augmentent. Par exemple, si C contient k intervalles de même longueur, alors le nombre de permutations sera de (n/k)!^k au lieu de n!. Le rapport des deux est d'environ k^n. Concrêtement, pour: - n=9 et k=3, on a 216 permutations au lieu de 362.880 (k^n=19.683) - n=12 et k=3, on a 13.824 permutations au lieu de 479.001.600 (k^n=531.441) Le dernier élément de C doit être égale à n-1 (sentinelle), le premier étant omis car toujours = 0. Donc C est un tableau à au plus n éléments. Si C=NULL, alors il n'y a pas de contrainte particulière, ce qui est identique à poser C[0]=n. On se base sur l'algorithme classique (lorsque C=NULL, sinon on l'applique sur l'intervalle de positions [C[j],C[j+1][): 1. Trouver le plus grand index i tel que P[i] < P[i+1]. S'il n'existe pas, la dernière permutation est atteinte. 2. Trouver le plus grand indice j tel que P[i] < P[j]. 3. Echanger P[i] avec P[j]. 4. Renverser la suite de P[i+1] jusqu'au dernier élément. */ { int i,j,a,b,c,T[1]; if(C==NULL){ T[0]=n; C=T; } b=C[i=j=0]; /* j=indice de la prochaine valeur à lire dans C */ c=-1; /* étape 1: on cherche l'intervalle [a,b[ avec i tq P[i]i. */ int i=0,j,s; if(n<0){ for(;i=0 dont la somme fait s et dont la i-ème part S[i] ne dépasse pas C[i]. Il faut que s <= sum_{i=0}^(n-1) C[i], n=1 est possible. S est la suite courante de somme s et on renvoie dans S la prochaine suite (la fonction renvoie aussi S). On renvoie NULL si on a atteint la dernière suite, et on remplit S avec le première suite. Si S=NULL, alors S est allouée et initialisée à la première suite. La première suite de somme s est obtenue en remplissant autant que possible les parts S[n-1],S[n-2],... L'algorithme est le suivant: 1. on détermine le plus grand indice j tq S[j]>0 2. si j=0, alors on a fini: on fait 5. avec x=s+1 et i=-1 3. on détermine le plus grand indice i0 */ while((i>0)&&(S[i]==0)) i--; x=S[i--]; /* rem: si i=0, alors i -> -1 */ /* calcule le plus grand indice j=0)&&(S[i]==C[i])) x += S[i--]; if(i>=0){ S[i]++; s=x-1; } /* si cet indice n'existe pas i<0 => FIN */ /* écrit la première suite de somme s dans S[i+1]...S[n-1] */ for(j=n-1;j>i;j--){ x=MAX(s,0); x=MIN(C[j],x); S[j]=x; s -= x; } /* on retourne S sauf si i<0 et r=0 (<=> FIN ) */ return ((i<0)&&(!r))? NULL : S; } int SetCmp(int *T1,int *T2,int n1,int n2) /* Compare deux tableaux d'entiers T1 et T2 de taille n1 et n2 triés par ordre croissant. Les tableaux peuvent être de taille nulle. La valeur renvoyée est interprétée en binaire comme suit: bit-0: 1 ssi T1 intersecte T2 (possède un élément commun) bit-1: 1 ssi T1 égale T2 bit-2: 1 ssi T1 est strictement inclu dans T2 bit-3: 1 ssi T2 est strictement inclu dans T1 Les valeurs possibles sont donc: 0,1,2,3,4,5,8,9 (=[0,9]\{6,7}) La complexité est O(n1+n2). */ { if(n1==0) return (n2==0)? 2:4; if(n2==0) return 8; /* ici T1 et T2 contiennent au moins 1 élément */ if((T1[n1-1]T2 */ if(T1[i1]n2). La complexité est O(min{n1,n2}*log max{n1,n2}). */ { int u,*t,*tf; if(n1>n2){ SWAP(n1,n2,u); SWAP(T1,T2,t); } for(tf=(t=T1)+n1;t32. L'opération de tri dépend de la constante "code" qui est interprétée comme suit (la complexité est le nombre d'étapes dans les boucles "for"): v=valeur d'un élément, v dans [a,a+m[ d=nombre réel de valeurs v distinctes dans T, d<=m e=élément du tableau, e dans [0..n[, v=T[e] i=indice dans un tableau, i dans [0..n[, R[i]=T[e] r=rang dans un tableau, r dans [0..d[ - code=SORT_FREQv: renvoie le tableau F[0..m[ de fréquence où F[v] est le nombre de fois où la valeur v+a apparaît dans T. Le tableau R et la variable m ne sont pas modifiés. Complexité: m+n. - code=SORT_FREQe: renvoie dans R[0..n[ un tableau de fréquence où R[e] est le nombre de fois où la valeur T[e] apparaît dans T. La variable m n'est pas modifiée. Complexité: m+2n. - code=SORT_INDEXi: renvoie dans R[0..n[ un tableau d'indices où R[i] est l'élément e dans l'ordre i de T. Autrement dit, R est le tableau T trié. La variable m n'est pas modifiée. Complexité: 2m+2n. - code=SORT_INDEXe: renvoie dans R[0..n[ un tableau d'indices où R[e] est l'ordre i de l'élément e dans T. La variable m n'est pas modifiée. Complexité: 2m+2n. - code=SORT_RANKv: renvoie dans R[0..d[ un tableau de rangs où R[v] est le rang r de la valeur v+a dans T. Le tableau R est modifié et on renvoie d dans m. Complexité: 3m+n. - code=SORT_RANKe: renvoie dans R[0..n[ un tableau de rangs où R[e] est le rang r de l'élément e dans T. Le tableau R est modifié et on renvoie d dans m. Complexité: 3m+2n. BUG: Ne marche si a=0,m=n, T=2 1 2 3 2 5 6. Retourne R=1 0 1 2 1 5 4 (le 5 devrait être un 3). */ { int *F,i,r,t; int k=(m==NULL)? n:*m; ALLOCZ(F,k,int,0); for(i=0;i0;t--) R[r++]=i+a; free(F); return R; } if(code==SORT_DEC){ /* R=tableau T trié, ordre décroissant */ for(i=0,r=n;i0;t--) R[--r]=i+a; free(F); return R; } for(i=r=0;isort=1. */ { if(G==NULL){ printf("NULL\n"); return; } int u,v,i,k,n,ligne,nk=(G->f>0)?G->f:1; graph *H; int *P; for(k=0;kf>0){ H=G->G[k]; printf("[%i]",H->id); } else H=G; SortGraph(H); n=H->n; ALLOCZ(P,n,int,0); i=u=ligne=0; v=-1; while(id[u])) v=H->L[u][P[u]++]; if(v fin d'un chemin */ if(H->d[u]==0){ /* cas des sommets isolés */ printf(" %i",u); if(++ligne==WIDTH){ printf("\n"); ligne=0; } } u=(i+=(u==i)); v=-1; } else{ /* u a un voisin v>u */ if((u==i)||(ligne==0)) printf(" %i",u); /* on affiche la tête */ printf("-%i",v); /* on affiche v */ if(++ligne==WIDTH){ printf("\n"); ligne=0; } u=v; /* on continu avec v */ v=-1; } } /* fin du while */ if(ligne>0) printf("\n"); /* newline si fini avant la fin de ligne */ free(P); } G->sort=1; /* effet de bord */ return; } int NbEdges(graph *G) /* Retourne le nombre d'arêtes de G, G->m si positif. Si G->m<0, alors G->m est mis à jour à partir de la somme des G->d[i]. */ { int m=G->m; if(m<0){ int i,n=G->n; for(i=m=0;id[i]; G->m=(m>>=1); } return m; } int Degree(graph *G,int max) /* Renvoie le degré maximum (si max=1) ou minimum (si max=0) d'un graphe G. On renvoie -1 si G est nul ou est une famille de graphes. */ { if((G==NULL)||(G->f>0)) return -1; int i=1,n=G->n,d=G->d[0]; for(;id[i]); else d=MIN(d,G->d[i]); return d; } /*********************************** BFS, DFS, ... (DIJKSTRA) ***********************************/ typedef struct{ int root; /* racine du BFS. */ int rad; /* rad=eccentricité du sommet source s. */ int girth; /* girth=longueur (>2) plus petit cycle passant par root. Si girth<0, alors la girth est infinie. */ int nc; /* nombre de sommets parcourus */ int *D; /* D[u]=distance entre u et root. Les sommets u avec D[u]=-1 sont à une distance infinie de root. En entrée, les sommets avec D[u]=-1 doivent être considérés inexsitant dans G. Si D=NULL, D est alloué et initialisé à -1. */ int *P; /* P[u]=père de u dans un arbre BFS de racine root, avec P[root]=-1. Seuls les sommets u avec D[u]>=0 ont un père défini (sauf si u=root). Si P=NULL, alors P est alloué. */ } param_bfs; param_bfs *new_param_bfs(int n) /* Si n>0, alloue le tableau P. Le tableau D peut être utilisé pour effacer des sommets. */ { param_bfs *X; ALLOC(X,1,param_bfs); X->D=X->P=NULL; X->rad=X->nc=0; X->girth=X->root=-1; if(n>0) ALLOC(X->P,n,int); return X; } void free_param_bfs(param_bfs *X){ if(X==NULL) return; free(X->D); free(X->P); free(X); } param_bfs *bfs(graph *G,int source,param_bfs *X) /* Effectue un BFS sur G depuis source. Si X=NULL, X est alloué et renvoyé. On l'utilise comme ceci: param_bfs *p=bfs(G,s,NULL); // BFS depuis le sommet s ... // p->D[u]=distance entre s et u free_param_bfs(p); ou pour un BFS d'un sous-graphe de G évitant les sommets de T: param_bfs *p=new_param_bfs(G->n); ALLOCZ(p->D,G->n,int,-1); for(i=0;in;i++) p->D[T[i]]=-2; bfs(G,s,p); ... // p->D[u]=distance entre s et u dans G\T free_param_bfs(p); ALGO: - prendre le sommet u en tête de file - pour tout ses voisins v non marqués: - enfiler v - marquer v Si D<>NULL, alors D n'est pas initialisé et D[u]=-2 sert à supprimer u de G pendant le BFS. Pour déterminer la girth, on calcule la longueur L du premier cycle crée. On remarque que la girth peut être seulement L ou L-1. C'est L-1 seulement si u et v sont à la même hauteur. Une fois le niveau terminé, L ne peut plus être modifiée et la girth est déterminée. Pour aller plus vite, une variable g détermine si c'est la peine de calculer la girth. */ { int i,u,v,d,ff,tf,g,h,n=G->n; int *file; /* file */ if(X==NULL) X=new_param_bfs(n); if(X->D==NULL) ALLOCZ(X->D,n,int,-1); /* on initialise que si D==NULL */ for(u=0;uP[u]=-1; X->D[source]=0; /* distance=0 */ X->root=source; X->girth=-1; /* valeur par défaut */ g=1; /* g=vrai ssi X->girth n'est pas encore correcte */ h=n; /* h=hauteur en dessous de laquelle le premier cycle peut apparaître */ ALLOC(file,n,int); /* réserve une file */ tf=ff=0; /* tf=tête de file, pointe sur la tête, ff=fin de file, pointe sur prochain élément libre. */ file[ff++]=source; /* enfile le 1er sommet = la source */ while(tfd[u];iL[u][i]; if(X->D[v]==-1){ /* si v voisin non marqué, si =-2 on saute le sommet */ X->P[v]=u; /* père de v = u */ X->D[v]=X->D[u]+1; /* hauteur(v)=1+hauteur(père(v)) */ file[ff++]=v; /* enfile v */ }else /* si v a déjà été visité */ if(g){ /* si g=faux, pas la peine de regarder la girth */ if((X->D[u]P[u])){ /* sinon X->girth ne peut pas être modifiée */ if(X->girth<0) h=X->D[u]+1,X->girth=(h<<1); /* on suppose X->D[v]>X->D[u] */ if(X->D[v]girth--,g=0; /* la girth est + petite et donc g=0 */ } } } } X->nc=ff; /* nb de sommets parcourus */ X->rad=X->D[u]; /* hauteur du dernier sommet */ free(file); return X; } typedef struct{ int nc; // nc=nb de composantes connexes du graphe int na; // nombre de sommets d'articulation (ou cut-vertex) int *C; // C[u]=couleur de la composante de u, entier de [0,nc[ int *P; // P[u]=parent de u dans une forêt couvrante, P[racine]=-1 int *R; // R[i]=i-ème sommet racine dans la forêt couvrante, i dans [0,nc[ int *d; // d[u]=date de début de visite du sommet u, entier de [0,n[ int *A; // A[u]=vrai ssi u est un sommet d'articulation, u dans [0,n[ } param_dfs; param_dfs *new_param_dfs(int n) { param_dfs *X; ALLOC(X,1,param_dfs); X->C=X->P=X->R=X->A=X->d=NULL; X->nc=X->na=0; if(n>0){ ALLOC(X->P,n,int); ALLOC(X->R,n,int); ALLOC(X->A,n,int); ALLOC(X->d,n,int); } return X; } void free_param_dfs(param_dfs *X){ if(X==NULL) return; free(X->C); free(X->P); free(X->R); free(X->A); free(X->d); free(X); } param_dfs *dfs(graph *G,int source,param_dfs *X) /* Effectue un parcours en profondeur du graphe G depuis le sommet source. Version non récursive. On détermine également tous les sommets d'articulations (voir la définition de param_dfs pour lire le résultat). On l'utilise comme suit: param_dfs *p=dfs(G,s,NULL); // DFS dans G depuis s ... free_param_dfs(p); ou alors, pour un DFS dans G évitant les sommets de T: param_dfs *p=new_param_dfs(G->n); ALLOCZ(p->C,G->n,int,-1); for(i=0;in;i++) p->C[T[i]]=-2; dfs(G,s,p); ... free_param_dfs(p); Si p->C[u]=-2, alors le sommet u n'est pas parcouru (il est virtuellement supprimé de G). Les autres sommets v (non supprimés) doivent avoir p->C[v]=-1. Si p->C==NULL (par défaut), alors ce tableau est alloué et initialisé à -1. Il sera libéré par free_param_dfs(p). */ { if(G==NULL) return NULL; int u,i,d,v,k,t,n=G->n,r=0; int tete,nc,na,b; int *pile,*next,*level; if(X==NULL){ r=1; X=new_param_dfs(n); } if(X->C==NULL) ALLOCZ(X->C,n,int,-1); for(i=0;iA[i]=0; nc=na=0; ALLOC(pile,n,int); /* pile */ ALLOC(next,n,int); /* next[u]=prochain voisin de u à visiter */ ALLOC(level,n,int); /* level[u]=... */ t=tete=-1; for(k=0;kC[source]==-1){ /* si ==-2 ou >=0 alors on saute le sommet */ pile[++tete]=source; next[source]=0; /* premier voisin à visiter */ X->P[source]=-1; v=X->R[nc]=source; while(tete>=0){ /* tant que la pile n'est pas vide */ u=pile[tete]; /* u=sommet courant */ i=next[u]; /* indice du prochain voisin de u à visiter */ if(i==0){ X->C[u]=nc; /* couleur de la composante courante */ level[u]=X->d[u]=++t; /* date de début de visite */ } d=G->d[u]; /* degré de u */ b=1; /* sentiennelle pour savoir si on a trouvé un v */ while(iL[u][i++]; /* pour tous les voisins v de u */ if(X->C[v]==-1){ /* si v n'a jamais été visité */ if((u==source)&&(t>X->d[u])&&(!X->A[u])) na++,X->A[u]=1; /* u=cut-vertex */ X->P[v]=u; /* père(v)=u */ pile[++tete]=v; /* on empile v */ next[v]=b=0; /* le prochain voisin de v à visiter */ next[u]=i; /* le prochain voisin de u à visiter */ break; } else /* v existe et a déjà été visité */ if((X->C[v]>=0)&&(v!=X->P[u])) /* si (u,v) est un arc de retour */ level[u]=MIN(level[u],X->d[v]); } if(b){ --tete; /* il n'y a plus de voisin v: on dépile u pour toujours */ if((v=(X->P[u]))>=0){ /* si u n'est pas une racine, il a un père v */ level[v]=MIN(level[v],level[u]); /* met à jour level du père de u */ if((v!=source)&&(level[u]>=X->d[v])&&(!X->A[v])) na++,X->A[v]=1; /* v=cut-vertex */ } } } /* fin du while(inc=nc; X->na=na; free(pile); free(next); free(level); /* on réduit le tableau ->R au minimum que si dfs() l'a alloué. Sinon, il ne faut pas aux pointeurs de X */ if(r) X->R=REALLOC(X->R,nc,int); return X; } typedef struct{ int n; // nb de sommets du graphe int source; // source int *pere; // tableau des parents: pere[u] double *dist; // tableau de distance: dist[u] } param_belman; param_belman *new_param_belman(int n){ param_belman *p; ALLOC(p,1,param_belman); p->n=n; p->source=0; if(n>0){ ALLOC(p->pere,n,int); ALLOC(p->dist,n,double); } return p; } void free_param_belman(param_belman *p){ if(p==NULL) return; free(p->pere); free(p->dist); free(p); return; } param_belman *Belman_Ford(graph *G,int source){ /* Calcule les distances de source à tous les autres selon l'algorithme de Belman-Ford. On retourne un tableau ->pere et ->dist. Il permet d'avoir des poids négatifs sur les arcs. Il ne faut pas qu'il y ait de cycle absorbant. On utilise en interne 4 tableaux de taille n. A faire: gérer les sommets éteints. */ if(G==NULL) return NULL; if(G->W==NULL) return NULL; int u,v,n=G->n; int i,i1,i2,d; int *pile1,*pile2,*vec1,*vec2,*tmp; param_belman *p=new_param_belman(n); double w; ALLOC(pile1,n,int); ALLOC(pile2,n,int); ALLOCZ(vec1,n,int,1); /* vec1[u]=0 ssi u est dans pile1 */ ALLOCZ(vec2,n,int,1); /* idem mais pour vec2 */ for(u=0;udist[u]=DBL_MAX; p->pere[u]=-1; } p->dist[source]=0.0; p->pere[source]=p->source=source; i1=i2=0; pile1[i1++]=source; /* empile la source */ vec1[source]=0; /* source est dans la pile1 */ while(i1>0){ while(i1>0){ u=pile1[--i1]; /* dépile u */ vec1[u]=1; /* u n'est plus dans la pile1 */ d=G->d[u]; /* d=degré de u */ for(i=0;iL[u][i]; w=p->dist[u]+G->W[u][i]; if(wdist[v]){ p->pere[v]=u; p->dist[v]=w; if(vec2[v]){ /* si v pas dans P2, empiler v dans P2 */ pile2[i2++]=v; vec2[v]=0; } } } } SWAP(i1,i2,i); SWAP(pile1,pile2,tmp); SWAP(vec1,vec2,tmp); } free(pile1); free(pile2); free(vec1); free(vec2); return p; } /* Dijkstra(G,W,s): 1. Init(G,s) 2. S={} 3. Q=V(G) 4. while Q<>{} 5. do u=Extract-Min(Q) 6. S=S u {u} 7. for each v in Adj[u]: Relax(u,v,W) Init(G,s): 1. for each vertex v in V(G): 2. do d[v]=infinity 3. pi[v]=NULL 4. d[s]=0 Relax(u,v,W): 1. if d[v]>d[u]+W[u,v] 2. then d[v]=d[u]+W[u,v] 3. pi[v]=u Extract-Min(Q): extract vertex u with smallest d[v] */ int WeightGraph(graph *G){ /* Calcule les longueurs (poids) des arêtes dans le cas d'un graphe géométrique (tout en créant le tableau les tableaux G->W). Il faut que les tableaux XPOS,YPOS existent. Retourne 1 ssi tout c'est bien passé. */ if((G==NULL)||(G->xpos==NULL)) return 0; int u,v,i,d,n=G->n; double dx,dy; ALLOC(G->W,n,double*); for(u=0;ud[u]; ALLOC(G->W[u],d,double); for(i=0;iL[u][i]; dx=G->xpos[u]-G->xpos[v]; dy=G->ypos[u]-G->ypos[v]; G->W[u][i]=sqrt(dx*dx+dy*dy); } } return 1; } /*********************************** ISOMORPHISM, SUBGRAPH, MINOR, INDUCEDSUBGRAPH, PATHS, PS1, TREEWIDTH ... ***********************************/ int *Isomorphism(graph *G,graph *H) /* Renvoie un tableau P <> NULL ssi G est isomorphe à H. Si tel est le cas, le tableau P indique le morphisme de H vers G. Après l'appel, le graphe H est modifié: ses listes sont triées si H->sort est faux (sauf si G=H - même pointeur). Le graphe G n'est par contre pas modifié. Dans H->int1 est retourné le nombre de tests effectués. Moins le graphe possède de symétrie, plus faible est le nombre de tests (et rapide est la fonction). On applique l'algorithme suivant. Pour chacun des deux graphes et chaque sommet u, on calcule son "profile" un tableau noté profile[u]: profile[u][i+2] = le nombre de sommets à distance i de u, en commençant à partir de i=1. Donc, profile[u][3] est le degré de u. Ceci est calculé par un simple BFS, les indices 0,1,2 étant réservés. On utilise profile[u][0] pour coder la taille du tableau profile[u], profile[u][1] pour stocker le nom de u (plutôt que le nombre de sommet à distance 0 qui est toujours 1) et profile[u][2] pour stocker la longueur du plus petit cycle passant par u. Cette dernière information étant calculée "gratuitement" par le BFS. On ordonne ensuite les sommets des graphes suivant les profiles des sommets avec qsort(). On ne renumérote pas les sommets dans le graphe, mais plutôt on donne un ordre: c'est possible avec qsort() car le nom original u est dans profile[u][1] le sommet u. Si bien que profile[i][1] sera le sommet u de rang i. On priviligie les profiles le grande taille (que l'on classe en premier) ce qui est plus discriminant. Les isomorphismes (=permutations) à tester ne concernent que les sommets de même profile. On construit les contraintes dans un tableau C, C[j] indiquant que les sommets de rang C[j-1] à C[j] (exclu) ont même profile, et sur lequel se base NextPermutation(). Sur le même principe, on pourrait imaginer un profile plus complexe, comme suit: à chaque distance i et sommet u, on calcule le graphe G[u][i] induit par les sommets à distance i de u. On peut alors calculer le profile de chaque sommet de G[u][i] et ordonner les sommets selon celui-ci. */ { H->int1=0; /* par défaut, 0 tests */ if((G==NULL)||(H==NULL)) return NULL; if(G->n!=H->n) return NULL; int *P; /* isomorphisme final */ int n=G->n; if(G==H){ /* isomorphisme trivial si même emplacement mémoire */ ALLOCZ(P,n,int,_i); return P; } param_bfs *param=new_param_bfs(n); /* pour le BFS */ int **profile,**profileG=NULL,**profileH; int *R,*C; /* permutation et contraintes (sur les rangs) */ int u,v,t,r,i; graph *M; for(M=G;;){ /* on fait la même chose pour M=G puis M=H */ ALLOC(profile,n,int*); /* profile[u] */ for(u=0;uD */ t=3+param->rad; /* taille du tableau profile[u] */ ALLOCZ(profile[u],t,int,0); /* initialise le profile */ for(v=0;vD[v]; if(i>0) profile[u][i+2]++; /* compte les sommets à distance i>0 de v */ param->D[v]=-1; /* réinitialise les distances pour les BFS suivants */ } profile[u][0]=t; /* taille du profile */ profile[u][1]=u; /* nom du sommet, pour qsort() */ profile[u][2]=param->girth; /* maille */ } qsort(profile,n,sizeof(int*),fcmp_profile); /* trie les profiles */ if(M==H){ profileH=profile; break; } /* on s'arête si M=H */ profileG=profile; /* on refait la boucle pour H */ M=H; } free_param_bfs(param); /* on verifie que profileG "=" profileH */ for(u=0;usort) SortGraph(H); /* on trie H pour la recherche dichotomique */ H->int1=0; /* compte le nb de tests */ /* vérifie, pour chaque permutation P, que P(G)=H */ do{ H->int1++; /* calcule P en fonction de R */ for(r=0;rd[u];iL[v] */ if(bsearch(P+(G->L[u][i]),H->L[P[u]],t,sizeof(int),fcmp_int)==NULL){ /* alors élément non trouvé */ i=t;r=n; /* prochaine permutation à tester */ } } /* ici r=n (trouvé) ou n+1 (pas encore trouvé) */ if(r==n) goto fin_iso; /* on a trouvé un isomorphisme P */ } while(!NextPermutation(R,n,C)); /* si on arrive ici, c'est qu'on a pas trouvé l'isomorphisme */ free(P); P=NULL; fin_iso: free(R); free(C); fin_noniso: FREE2(profileG,n); FREE2(profileH,n); return P; } edge *ListEdges(graph *G){ /* Construit la liste des arêtes de G, chaque arête uv ne figure qu'une seule fois. On a, pour tout i, E[i].u < E[i].v. Le champs G->m est mis à jour. */ edge *E; int u,v,i,j,d; int m=NbEdges(G); int n=G->n; ALLOC(E,m,edge); for(u=j=0;ud[u];iL[u][i]; if(usort=1, - H->int1 contient le nombre total de tests effectués, - S->pint1 contient l'isomorphisme de S vers G, et donc de H vers G. L'algorithme est le suivant: on teste d'abord si la séquence des degrés de H est bien supérieure à celle de G (ceci prend un temps O(n)). Si c'est le cas, on effectue, pour tous les sous-graphes S de H qui ont autant d'arêtes que G, un test d'isomorphisme entre S et G grâce à isomorphisme(S,G). */ int n=H->n; H->int1=0; /* nb de tests = 0 par défaut */ if(n!=G->n) return NULL; /* pas le même nombre de sommets */ /* on trie en O(n) les deux listes */ int *Eh=SortInt(H->d,NULL,n,0,NULL,SORT_INC); int *Eg=SortInt(G->d,NULL,n,0,NULL,SORT_INC); int i; /* on s'arrête si, pour un rang i donné, degH(i)d et S->L */ edge *E=ListEdges(H); /* liste des arêtes de H: e_j=(u,v) -> E[j].u=u et E[j].v=v */ int *B; /* les arêtes de S, sous-ensemble d'indices d'arêtes de H */ int *P; /* isomorphisme S->G */ int u,v,j,d; /* réserve l'espace pour S, sous-graphe de H */ for(i=0;iL[i],H->d[i],int); /* initialise le sous-ensemble d'arêtes B de H avec mg arêtes */ ALLOC(B,mg,int); NextSet(B,-1,mg); d=0; /* d=compteur pour le nombre total de tests */ do{ /* remplit S avec les arêtes de B */ for(u=0;ud[u]=0; /* position libre pour le sommet u de S */ for(i=0;iL[u][S->d[u]++]=v; /* ajoute v comme voisin de u et incrémente deg(u) */ S->L[v][S->d[v]++]=u; /* ajoute u comme voisin de v et incrémente deg(v) */ } /* il vaut mieux que G soit le 2e paramètre, car il va être trié la première fois par Isomorphism(), puis plus jamais grâce au test de G->sort, alors que S serait trié à chaque appel */ P=Isomorphism(S,G); d += 1+G->int1; /* on ajoute 1 pour donner le nombre d'ensembles testés */ } while((P==NULL)&&(!NextSet(B,mh,mg))); H->int1=d; /* nombre total de tests */ if(P==NULL){ /* on a pas trouvé de sous-graphe de H isomorphe à G */ free_graph(S); S=NULL; } else S->pint1=P; /* S isomorphe à G, sous-graphe de H */ free(E); free(B); return S; } graph *MatrixToGraph(int **M,int n){ /* Renvoie le graphe correspondant à la matrice d'adjacence n x n symétrique où seule la partie inférieure est utilisée. Les listes du graphe de retour sont triées et les champs ->m et ->sort sont mise à jour. */ if((M==NULL)||(n<=0)) return NULL; int u,v,m; graph *G=new_fullgraph(n); for(u=m=0;ud); G->m=m; G->sort=1; return G; } graph *GraphOfColor(graph *G,int *col,int k){ /* Renvoie un graphe C dont les sommets sont les entiers de [0,k[ (les valeurs du tableau col[] qui doit avoir une taille G->n) et les arêtes les paires uv telle qu'il existe une arête xy de G avec col[x]=u et col[y]=v. La valeur C->m est mise à jour, et les listes de C sont triées (C->sort=1). */ if((k<0)||(col==NULL)||(G==NULL)) return NULL; int u,v,cu,cv,i,d,n=G->n; int **M; /* matrice d'adjacence du graphe des couleurs */ graph *C; /* le graphe des couleurs renvoyé */ /* matrice d'adjacence inférieure à 0 */ ALLOCMAT(M,k,k-1,int); for(u=0;ud[u];iL[u][i]; if(ucv) M[cu][cv]=1; if(cv>cu) M[cv][cu]=1; } } C=MatrixToGraph(M,k); FREE2(M,k); return C; } int FindSet(int x,int *p) /* routine pour UNION-FIND pour Minor() */ { if(x!=p[x]) p[x]=FindSet(p[x],p); return p[x]; } int *Minor(graph *H,graph *G) /* Détermine si H est un mineur de G. Si c'est le cas, un tableau T est renvoyé, sinon NULL est renvoyé. Le tableau T code un modèle du mineur de H dans G. Plus précisément, T[u]=c, où u est un sommet de G, est le nom du sommet c de H si bien que l'ensemble des sommets u de G tel que T[u]=c forme le super-noeud c. L'algorithme est le suivant: on effectue, pour tous les ensembles de contractions d'arêtes de G produisant un mineur avec autant de sommets que H, un test de sous-graphe grâce à Subgraph(). */ { graph *C; /* graphe des couleurs = graphe contracté */ graph *S=NULL; /* sous-graphe éventuellement isomorphe à C */ int *B; /* sous-ensemble (d'indices) d'arêtes de G à contracter */ int *couleur; /* les sommets de même couleurs seront contractés */ int *rang; /* pour union-find rapide */ edge e; int nh=H->n; int ng=G->n; int c=ng-nh; /* c=nb de contractions à effectuer */ int t; H->int1=t=0; /* initialise le nb de tests */ if(c<0) return NULL; /* pas de mineur */ edge *E=ListEdges(G); /* E=liste des arêtes de G, met à jour G->m */ int mg=G->m; if(c>mg){ /* fini s'il faut contracter plus d'arêtes qu'il y a dans G */ free(E); return NULL; } int i,u,v,x,y; int test=((c<<1)rang[y]) couleur[y]=x; else{ couleur[x]=y; if(rang[x]==rang[y]) rang[y]++; } } if(i==c){ /* si B est acyclique, on fait un test de sous-graphe */ if(test) /* on met à jour la couleur de chaque sommet. Suivant les valeurs respectives de c et ng (test) on met à jour soit suivant les arêtes ou suivant les sommets. */ for(i=0;iint1; free_graph(C); /* on a plus besoin du graphe des couleurs */ } } while((S==NULL)&&(!NextSet(B,mg,c))); H->int1=t; free(B); free(E); /* on a rien trouvé */ if(S==NULL){ free(couleur); free(rang); return NULL; } /* on a trouvé un mineur, on construit le modèle dans rang[] */ for(u=0;upint1[couleur[u]]; free_graph(S); free(couleur); return rang; } int *InducedSubgraph(graph *H,graph *G) /* Indique si H est un sous-graphe induit de G. La fonction renvoie un ensemble X de sommets tel que G[X] est ismomorphe à H. Evidemment |X|=H->n. On renvoie dans G->int1 le nombre de tests, et dans G->pint1 l'isomorphisme entre H et G[X]. L'algorithme consiste à générer tous les ensembles X possibles de |V(H)| sommets à tester l'isomorphisme entre G[X] et H. */ { if((G==NULL)||(H==NULL)) return NULL; int ng=G->n,nh=H->n; if(nh>ng) return NULL; graph *S; int *X,*P,t=0; ALLOC(X,nh,int); NextSet(X,-1,nh); /* premier sous-ensemble */ do{ t++; S=ExtractSubgraph(G,X,nh,1); P=Isomorphism(S,H); t += H->int1; free_graph(S); } while((P==NULL)&&(!NextSet(X,ng,nh))); G->int1=t; free(G->pint1); /* pour éviter les fuites mémoires */ G->pint1=P; if(P==NULL){ free(X); X=NULL; } return X; } int NextPath(graph *G,path *P,int j) /* Cette fonction (récursive) permet de trouver tous les chemins simples entre deux sommets. Si le code 1 est renvoyé, c'est que tout c'est bien passé, sinon on renvoie le code 0. On l'utilise comme ceci: path *P=new_path(G,NULL,G->n); // crée un chemin vide P mais avec G->n sommets possibles P->P[0]=x; // origine du chemin P->P[1]=y; // destination du chemin, y=x possible r=NextPath(G,P,-1); // crée le premier chemin, r=0 s'il n'existe pas, sinon r=1 r=NextPath(G,P,0); // calcule le chemin suivant, r=0 s'il n'existe pas, sinon r=1 r=NextPath(G,P,0); // calcule le chemin suivant, r=0 s'il n'existe pas, sinon r=1 ... free_path(P); // libère le chemin P Plus précisément, étant donnés un chemin P=x-...-v_j-...-y du graphe G et un sommet v_j du chemin (v_j=j-ème sommet du chemin), la fonction tente de compléter P par un autre chemin de v_j à y évitant x-...-v_(j-1). Si ce chemin à été trouvé, alors la partie de v_j à y de P est mise à jour et on renvoie 1. Sinon, le chemin est coupé après v_j et on renvoie 0. Dans tous les cas P est un chemin à jour de G. Si j<0, alors on initialise P par un chemin allant de x=P->P[0] à y=P->P[1]. Algorithme: on essaye d'améliorer en premier le sous-chemin de v_(j+1) à y (récursivement). Si cela n'est pas possible, on calcule un nouveau chemin de v_j à y passant par un autre voisin v de v_j (autre que v_(j+1)) et évitant le chemin x-...-v_j. On passe en revue ainsi tous les voisins v de v_j qui ne sont pas dans P[0]...P[j]. Si aucun des voisins n'a un tel chemin, on retourne 0. Comme il faut tester les voisins v de v_j qu'une seule fois (pour un chemin P[0]...P[j] donné), on utilise le champs aux[v_j][i] de P qui donne le i-ème voisin libre de v_j avec la convention que aux[v_j][0] est le nombre de voisins encore possibles. Effet de bord: P est mis à jour. */ { if((P==NULL)||(G==NULL)) Erreur(-1); /* ne devrait jamais arriver */ param_bfs *p; int i,x,y,u,v,n; if(j<0){ /* initialisation du premier chemin */ n=G->n; if(P->aux==NULL) ALLOCMAT(P->aux,n,n,int); for(u=0;uV[u++]=-1); /* vide le chemin */ x=P->P[0]; y=P->P[1]; if((x<0)||(y<0)||(x>=n)||(y>=n)){ P->n=0; p=NULL; goto fin_0; } /* sommets inexistant */ p=bfs(G,x,NULL); /* calcule le chemin */ i=p->D[y]; if(i<0){ P->V[x]=0; /* x est en première position dans P */ P->n=1; goto fin_0; } /* on initialise aux[x] et aux[y] qu'une seule fois */ P->aux[y][0]=0; j=-1; /* pour que la longueur soit correcte */ goto fin_1; } n=P->n; if(j+1==n) return 0; /* si x=y, alors pas de prochain chemin */ if(NextPath(G,P,j+1)) return 1; /* c'est le NextPath à partir du voisin de v_j */ /* Ici on ne peut pas augmenter v_(j+1)...y. Donc, il faut calculer un premier chemin depuis le prochain voisin v disponible de u=v_j et y qui évite x=P[0]-...-P[j]. Si cela ne marche pas avec le voisin v, il faut essayer le suivant, etc. */ /* efface depuis P la fin du chemin P[j+1]...P[n-1] */ /* pour ne garder que P[0]...P[j] */ for(i=j+1;iV[P->P[i]]=-1; /* rem: ici tn); ALLOC(p->D,G->n,int); y=P->P[n-1]; u=P->P[j]; i=-1; while((P->aux[u][0])&&(i<0)){ /* tant qu'il y a encore des voisins de u non testés */ v=P->aux[u][(P->aux[u][0])--]; /* lit et enlève le dernier voisin dispo */ if(P->V[v]>=0) continue; /* si le voisin est dans P[0] ... P[j] on le saute */ /* initialise p->D: on doit le faire à chaque appel */ for(i=0;in;i++) p->D[i]=-1; /* on enlève P[0]...P[j] du graphe pour le BFS */ for(i=0;i<=j;i++) p->D[P->P[i]]=-2; /* calcule un chemin de v à y dans G\(P[0]-...-P[j]) */ bfs(G,v,p); /* a-t-on trouvé un chemin ? */ i=p->D[y]; /* si i>=0, c'est oui */ } /* ici i=distance de u=v_j à y */ if(i<0){ /* on a pas trouvé de chemin */ fin_0: free_param_bfs(p); return 0; } /* on a trouvé un chemin, on met à jour P */ fin_1: P->n=i+j+2; /* nouvelle longueur */ /* ajoute à P[0]...P[j] le chemin de P[j+1] à y en partant de y */ while(i>=0){ P->P[i+j+1]=y; P->V[y]=i+j+1; y=p->P[y]; i--; } /* initialise aux[u] pour tous les sommets u de P[j+1] à y non compris. Pour P[j] on le fait au moment de la lecture de v dans aux[u], et pour y on le fait une seule fois à la création (avec aux[y][0]=0) */ for(i=j+1,n=P->n-1;iP[i]; P->aux[u][0]=0; for(v=0;vd[u];v++){ j=G->L[u][v]; /* j=voisin de u */ /* si pas dans P on l'ajoute comme voisin possible */ if(P->V[j]<0) P->aux[u][++P->aux[u][0]]=j; } } free_param_bfs(p); return 1; } int NextPath2(graph *G,path *P,int j) /* Comme NextPath(G,P,j) sauf que si le nouveau chemin P' renvoyé a le même ensemble de sommets sur les positions allant de j à n-1, on passe au chemin suivant. Donc on renvoie le prochain chemin de P (s'il existe) qui a un ensemble de sommets différents de P->P[j] à P->P[n-1]. */ { if(j<0) return NextPath(G,P,j); if(P==NULL) Erreur(-1); int *T,i,n=P->n,m=n-j; ALLOC(T,m,int); for(i=j;iP[i]; /* copie les n-j derniers sommets de P */ if(!NextPath(G,P,j)){ free(T); return 0; } if(n==P->n){ for(i=0;iV[T[i]]==-1){ /* ici on a un chemin différent */ free(T); return 1; } /* ici on a le même chemin qu'au départ */ free(T); return NextPath2(G,P,j); } free(T); /* ici on a un chemin différent */ return 1; } #define LCONF 9 /* nb de bits pour coder un sommet dans le graphe des conflits */ #define CONFMAX (1< CONFMAX. On s'en sert pour coder un type d'arête. Donc si u est un noeud et v=G->L[u][i], alors le voisin i de u est (v&CONFMASK) est le type de de l'arête est t=(v>>LCONF) */ } conflit; void PrintConflit(conflit *c) /* Affiche le graphe des conflits, et rien si c->G->n=0. */ { if(c->G->n==0) return; int u,v,i,t,d; char T1[]=".=<>"; char T2[]="-01"; char T3[]="_/."; // UTF-8: //char T3[]="━┛o"; // \xe2\x94\x80: ─ // \xe2\x94\x81: ━ // \xe2\x94\x98: ┘ // \xe2\x94\x99: ┙ // \xe2\x94\x9a: ┚ // \xe2\x94\x9b: ┛ printf("code (x,y) [comp] node-path-paire: node[type]\n"); for(u=0;uG->n;u++){ printf(" %c ",T2[1+c->code[u]]); if(c->paire[u]==u) printf("(%i,%i) [",c->x[u],c->y[u]); else printf("\t ["); for(v=0;vnbcomp[u];v++) printf("%i",c->comp[u][v]); printf("]\t%s%i",(v<5)?"\t":"",u); if(u>c->path[u]) printf("%c \t:",T3[1]); else{ printf("%c",T3[0]); if(u>c->paire[u]) printf("%c\t:",T3[1]); else{ printf("%c%c\t:",T3[0],T3[2]); } } for(i=0,d=MIN(c->G->d[u],WIDTH);iG->L[u][i]; t=v>>LCONF; printf(" %i%c",v&CONFMASK,T1[t]); } if(c->G->d[u]>WIDTH) printf("..."); printf("\n"); } printf("#nodes in conflict graph: %i\n",c->G->n); printf("#unspecified values: %i\n",c->nbi); if(c->outmem) printf("max. size exceeded (%i)\n",CONFMAX); return; } int ps1_push(int x,int v,conflit *c) /* Affecte la valeur v (=0 ou 1) à c->code[x] si c->code[x]<0, puis propage et vérifie ses voisins, éventuellement en propageant de nouveau aux voisins des voisins. Renvoie 1 s'il y a une contradiction, ou bien si tous les noeuds de la paire de x ont pour code 1. Sinon, on renvoie 0 (terminaison standard). Il faut appliquer cette fonction que si la paire de x est complète (donc ne pas l'appliquer si on vient d'ajouter x, car on n'ai pas sur de ne pas faire un Out of Memory plus tard). Effet de bord: met à jour plusieurs champs de la variable c, mais ne modifie pas le graphe c->G. */ { int i,d,y,t,tx; if(c->code[x]==v) return 0; /* rien à faire */ if(c->code[x]==1-v) return 1; /* contradiction */ c->code[x]=v; /* écrit la valeur, car on avait code[x]=-1 */ c->nbi--; /* et une valeur indéterminée en moins ! */ t=(c->nbc[c->paire[x]] -= v); /* diminue si on a écrit 1 */ if(t==0) return 1; /* la paire de x est bonne, elle contient que des 1 ! */ /* règle 1: si Tx<>Ty et v=0, alors écrire 1 dans y */ /* règle 2: si Tx=Ty, alors écrire v dans y */ /* règle 3: si TxTy et v=1, alors écrire 1 dans y */ /* règle 5: si Tx<>Ty, v=1 et |Tx|+|Ty|=n, alors écrire 0 dans y */ tx=c->G->n-c->nbcomp[x]; /* tx=n-|Tx| */ d=c->G->d[x]; for(i=0;iG->L[x][i]; /* i-ème voisin de x */ t=y>>LCONF; /* t=type de l'arc x->y: 0,1,2,3 */ /* rappel: t=0=>disjoint, t=1=>égalité, t=2=>TxTx>Ty */ y &= CONFMASK; /* y=numéro du noeud */ /* applique une des règles */ switch(t){ case 0: if((v==0)&&(ps1_push(y,1,c))) return 1; /* Tx<>Ty */ if((v==1)&&(tx==c->nbcomp[y])&&(ps1_push(y,0,c))) return 1; /* règle 5 */ break; case 1: if(ps1_push(y,v,c)) return 1; break; /* Tx=Ty */ case 2: if((v==0)&&(ps1_push(y,0,c))) return 1; break; /* TxTy */ } } return 0; } /* pour le débugage de PS1() */ #define PRINTS do{ \ int _i; \ printf("%03i:%02i ",POS,N); \ for(_i=0;_i<3*N;_i++) printf(" "); \ }while(0) #define DEBUG(I) //if(0){ I } int PS1(graph *G,path *P,int version) /* P est un chemin d'un graphe G, et G\P est formé d'une seule composante connexe. Il faut G et P <> NULL. Renvoie 1 si P peut "séparer" G. Il y a une optimisation avec le graphe des conflits si version>0. On utilise cette fonction comme ceci: path *P=new_path(G,NULL,G->n); // P=chemin vide, sans sommet int r=PS1(G,P); // r=0 ou 1 free_path(P); Plus précisément, PS1(G,P)=1 si G est vide, plus précisément si (G->n)-(P->n)<3, ou s'il existe deux sommets x,y de G où y notin P tels que pour tout chemin Q entre x et y dans G "compatible" avec P (P et Q s'intersectent en un segment) on a: (1) il n'y a pas d'arête entre G\(PuQ) et P\Q; et (2) pour toutes les composantes connexes C de G\(PuQ), PS1(CuQ,Q)=1. Pour le graphe des conflits, voir l'aide dans -filter. Effet de bord: G->int1 retourne le nombre de tests (nombre de paires, nombre de chemins testés, et nombre de passes dans le graphe des conflits). Les autres de champs de G et de P ne sont pas modifiés. Le paramètre "version" indique la variante: - version=0: sans le graphe des conflits - version=1: avec le graphe des conflits - version=2: comme version=1 mais sans le graphe des conflits lors de la récursivité - version=3: comme version=1 mais avec l'écriture de valeurs dans le graphe des conflits Améliorations possibles: - Pour tous les chemins possibles testés récursivement pour G, ne tester effectivement que ceux qui correspondent à des sous-ensembles de sommets différents puisque le résultat sera le même (mêmes composantes connexes). Pour cela, il faut gérer une table pour mémoriser les sous-ensembles testés. Notons que si un chemin est induit alors cela ne sert à rien de le mémoriser, il ne pourra jamais être rencontré de nouveau. - Si G n'est pas biconnexe, alors on pourrait tester si toutes ses composantes biconnexes sont bien évaluée à vraie. Si P n'intersecte pas une composante biconnexe B de G, alors il faut évaluer f(B,{}). - G\P étant connexe, on pourrait déjà supprimer les sommets de P qui (1) forment un segment de P contenant une extrémité de P, et (2) qui n'ont pas de voisin dans G\P. - On pourrait tester des cas simples pour G: arbre (tester si m=n-1, on sait que G est connexe), clique (tester si m=n(n-1)/2: si n<=4 sommets alors vraie, sinon faux). Plus dur: outerplanar. */ { G->int1=1; DEBUG( if(G==GF) {N=POS=0;} N++;POS++; PRINTS;printf("G=%p n=%i ",G,G->n);PRINTT(P->P,P->n); N--; ); int n=G->n; if(n-(P->n)<3) return 1; /* cas facile */ /* note: lors d'un appel récursif, le nb d'arêtes G->m est déjà mis à jour, et donc NbEdges(G) est calculé très rapidement */ if(NbEdges(G)<7) return 1; /* |E(G\P)|<10 ? à vérifier ... */ if(G->mm==(n*(n-1))>>1)&&(n>4)) return 0; /* clique avec >4 sommets */ DEBUG(N++;); int x,y,i,u,v,d,val; path *Q=new_path(G,NULL,n); path *R=new_path(G,NULL,n); param_dfs *p=new_param_dfs(n); /* p->C n'est pas alloué */ int *T,*M,*A,*B; graph *C; ALLOC(p->C,n,int); /* pour le DFS avec sommets supprimés */ ALLOC(T,n,int); /* pour la composante C de G */ ALLOC(M,n,int); /* pour la compatiblité des chemins P et Q */ int npaire,npath,w,etatxy,ver=version; conflit c; /* ensembles de variables pour gérér les conflits */ npaire=npath=0; if(version>0){ c.G=new_graph(CONFMAX); /* graphe des conflits, alloue G->d et G->L */ c.G->n=c.nbi=c.outmem=0; /* c.G->n=nb de noeuds déjà crées */ if(version==2) ver=0; /* récursion sans graphe des conflits */ if(version==3) ver=1; /* récursion avec graphe des conflits, mais sans écritures */ } /* pour toutes les paires de sommets x,y de G */ for(x=0;xV[y]>=0) continue; /* y ne doit pas être dans P */ if((P->V[x]<0)&&(y<=x)) continue; /* si x et y pas dans P, ne tester que le cas xint1++; Q->P[0]=x; Q->P[1]=y; /* initialise les extrémités du chemin */ val=NextPath(G,Q,-1); /* premier chemin entre x et y, normalement val=1 */ if(!val) goto fin0; /* fin si pas de chemin x->y, possible que si G est non connexe */ if((version>0)&&(!c.outmem)) c.nbc[npaire=c.G->n]=0; /* init. code de la paire x,y */ DEBUG(PRINTS;printf("Paire (%i,%i) G=%p n=%i\n",x,y,G,n);); do{ /* pour tous les chemins Q entre x et y */ G->int1++; DEBUG( PRINTS;printf("Essai (G=%p, P=",G); int z;for(z=0;zn;z++) printf(" %i",P->P[z]); printf(") du chemin ");PRINTT(Q->P,Q->n); ); /* Optimisation: si |G|-|Q|<2 alors on peut directement conclure que le chemin Q est correct car si |V(Q)|>=n-1 alors les conditions (1) et (2) seront vraie. En effet, si |V(Q)|=n, c'est clair. Sinon, il existe un sommet u dans G\Q. Soit u est dans P, et alors u ne peut avoir de voisin dans G\(PuQ). Soit u n'est pas dans P, mais alors P est inclu dans Q, et u ne peut avoir de voisin dans P\Q={}. Donc la condition (1) sera vraie. La condition (2) sera trivialement vraie aussi, car n-|V(Q)|=1 (<=2). Question: Peut-on mettre |G|-|Q|<3 ??? */ if(n-(Q->n)<2){ DEBUG(PRINTS;printf(" -> n-|Q|<=1.\n");); goto nextQ; } /* Optimisation: teste si PuQ = G. En effet, dans ce cas P et Q sont compatibles et G\Q est vide. Donc la condition (1) est vraie. Ensuite comme G\(PuQ) est vide, la condition (2) est vraie aussi. Pas besoin de changer etatxy. Rem: G\(PuQ) contient au moins une composante. */ for(u=0;uV[u]<0)&&(Q->V[u]<0)) break; if(u==n){ DEBUG(PRINTS;printf(" -> PuQ = G.\n");) goto nextQ; } /* Si (u==n) est vraie alors il n'y a pas de sommet u de G qui n'est ni dans P ni dans Q, c'est-à-dire que G = PuQ. */ /* On vérifie maintenant que Q est compatible avec P, c'est-à-dire qu'ils s'intersectent selon un segment (ou que P ou Q sont vides). Qu'ils soient compatibles ou non, on a pas à modifier etatxy. On peut en effet toujours se restreindre aux chemins compatibles. La complexité de ce test est en 6n. On pourrait faire en O(P->n*Q->n), ce qui peut être moins mais parfois plus. */ for(A=P->V,B=Q->V;;){ for(u=0;u=0)&&(B[u]>=0)) M[A[u]]=1; /* ici M représente les positions des sommets de A qui sont aussi dans B */ while((u>0)&&(!M[--u])); /* on se place sur le dernier sommet */ if(u==0) break; /* P et Q sont compatibles, ils ne s'intersectent pas */ while((u>0)&&(M[--u])); /* on vérifie que les positions sont consécutives */ while((u>0)&&(!M[--u])); if(u>0){ DEBUG(PRINTS;printf(" -> chemins non compatibles.\n");); goto nextQ; } /* A n'est pas un segment, etatxy inchangé */ if(A==Q->V) break; A=B; B=P->V; } DEBUG(PRINTS;printf(" -> chemin Q compatible avec ");PRINTT(P->P,P->n);); /* on vérifie la condition (1) <=> il n'y a pas d'arête entre P\Q et G\(PuQ). */ for(i=0;in;i++){ u=P->P[i]; /* u=i-ème sommet de P */ if(Q->V[u]<0){ /* on ne garde u que s'il n'est pas dans Q */ for(w=0,d=G->d[u];wL[u][w]; /* pour tous les voisins de u */ /* si u est dans P\Q et v ni dans P ni dans Q, alors le chemin Q n'est pas bon */ if((P->V[v]<0)&&(Q->V[v]<0)){ /* condition (1) fausse */ etatxy |= 1; /* condition (1) fausse */ DEBUG(PRINTS;printf(" -> condition (1) FAUSSE.\n");) if(version>0) goto nextQ; else goto nextxy; } } } } DEBUG(PRINTS;printf(" -> condition (1) VRAIE.\n");); /* on vérifie la condition (2), condition (1) étant vraie */ /* (2) <=> pour toutes les CC C de G\Q, PS1(CuQ,Q)=1 */ /* on enlève de G les sommets de PuQ pour calculer les CC de G\(PuQ) */ for(u=0;uV[u]>=0){ p->C[u]=-2; continue; } if(Q->V[u]>=0){ p->C[u]=-2; continue; } p->C[u]=-1; } dfs(G,0,p); /* calcule les CC de G\(PuQ) */ /* rem: il y a au moins une CC car G<>(PuQ) */ DEBUG(if(p->nc==0){PRINTS;printf("Erreur: 0 composante connexe !!!");exit(0);}); d=R->n=Q->n; /* nb de sommets du chemin Q */ for(u=0;uP[u]; /* T=liste des sommets de Q */ if((version>0)&&(!c.outmem)) npath=c.G->n; /* init. le chemin Q au sommet courant */ DEBUG( PRINTS;printf("Q = "); PRINTT(T,d); ); /* pour chaque CC de G\Q */ for(i=0;inc;i++){ /* T=composante No i de G\(PuQ) u Q */ for(u=0,v=d;uC[u]==i) T[v++]=u; /* rem: les sommets de T[d...v[ sont dans l'ordre croissant */ DEBUG(PRINTS;printf("C\\Q=CC(%i) = ",i);PRINTT(T+d,v-d);); C=ExtractSubgraph(G,T,v,1); /* crée C=G[T] avec v=|T| sommets */ /* Attention! Q n'est pas un chemin de C, mais de G. On crée donc un nouveau chemin R dans C qui est équivalent à Q */ for(u=0;uV[u]=-1; /* Attention! boucle avec v=C->n sommets */ for(u=0;uP[u]=C->pint1[Q->P[u]]-1; for(u=0;uV[R->P[u]]=u; u=PS1(C,R,ver); /* appel récursif */ G->int1 += C->int1; free_graph(C); /* libère C */ if(!u){ /* ici v=|T| et d=|Q|. Attention de ne surtout pas modifier d */ etatxy |= 2; /* condition (2) fausse pour la paire xy */ /* si pas le graphe des conflits, ou bien si Out of Memory */ if((version==0)||(c.outmem)) goto nextxy; /* avant d'ajouter le noeud w=c.G->n, on vérifie s'il n'existe pas déjà dans la paire de c.G->n. La composante de c.G->n est dans T[d...v[ et sa taille vaut v-d. */ for(u=npaire;un;u++) if(SetCmp(c.comp[u],T+d,c.nbcomp[u],v-d)&2) goto nexti; /* on va essayer d'ajouter un noeud au graphe des conflits */ if(c.G->n==CONFMAX){ /* Out of Memory */ c.outmem=1; if(npaire==c.paire[c.G->n-1]){ /* la paire xy n'est pas complète. On l'enlève, sinon l'analyse des conflits pourrait ne pas être correcte */ int j,z,k; for(u=npaire;un;u++){ /* on supprime tous les noeuds et tous les arcs de la paire courante, qui est donc incomplète */ for(j=0;jd[u];j++){ /* pour tous les arcs z->u */ z=c.G->L[u][j]&CONFMASK; /* z est le j-ème voisin de u */ if(zd[z];k++) /* on cherche et l'on supprime u de la liste de z */ if((c.G->L[z][k]&CONFMASK)==u) c.G->L[z][k]=c.G->L[z][--c.G->d[z]]; /* supprime u */ } free(c.G->L[u]); free(c.comp[u]); } /* on ré-initialise le nouveau nb de noeuds du graphe de conflit. npaire et npath sont corrects. */ c.G->n=npaire; } goto nextxy; } /* pas de problème de mémoire, donc on ajoute w */ /* attention! ne pas utiliser ps1_push(w,...) car on est pas certain que la paire de w sera complète ... */ G->int1++; w=c.G->n++; /* w=nouveau noeud crée */ c.x[w]=x; c.y[w]=y; /* mémorise la paire x,y (pour l'affichage) */ c.path[w]=npath; c.paire[w]=npaire; /* w rattaché à npath et à npaire */ c.code[w]=-1; c.nbi++; /* un noeud de plus à valeur = -1 */ (c.nbc[npaire])++; /* un noeud de plus à valeur < 1 pour cette paire */ c.G->d[w]=0; /* init. le degré de w */ ALLOC(c.G->L[w],CONFMAX,int); ALLOC(c.comp[w],v-d,int); c.nbcomp[w]=v-d; /* taille de la composante de w */ for(u=d;u=0){ /* on continue seulement si le max existe */ u=SetCmp(c.comp[u],c.comp[w],c.nbcomp[u],c.nbcomp[w]); if(u&12){ /* bit-2 ou bit-3 mis: T(u) sub T(w) ou le contraire */ /* rem: T(u)=T(w) est impossible */ if(u&4) c.max[npaire]=w; /* w contient u, et donc tous les autres */ } else c.max[npaire]=-1; /* alors il n'y a plus de max */ } } /* y'a-t'il des conflits avec les noeuds < w ? */ for(u=0;u=npath) v=0; /* test rapide: si u>=napth, alors clique */ else{ /* sinon calcule l'intersection des composantes */ v=SetCmp(c.comp[u],c.comp[w],c.nbcomp[u],c.nbcomp[w]); /* ici les valeurs possibles pour SetCmp: 0,1,3,5,9 car T1 et T2 != {} */ if(v==1) v=-2; /* si v=1, T1 intersecte T2, et donc pas d'arête u-w */ /* avant: v: 0=disjoint, 3=égalité, 5=T1 sub T2, 9=T2 sub T1 */ v >>= 1; v -= (v==4); /* rem: si avant v=-2, alors après v=-1 */ /* après: v: 0=disjoint, 1=égalité, 2=T1 sub T2, 3=T2 sub T1 */ } /* si v<0, alors pas d'arête */ if(v>=0){ /* ajoute les arcs u->w et w->u */ c.G->L[u][c.G->d[u]++]=(v<w */ if(v>1) v ^= 1; /* 2->3 et 3->2 */ c.G->L[w][c.G->d[w]++]=(v<u (asymétrie pour v=2,3) */ } } /* fin du for(u=...) */ } /* fin du if(!u) ... */ nexti:; /* prochaine CC */ } /* fin du for(i=0...) */ nextQ:; } while(NextPath(G,Q,0)); /* ici on a examiné tous les chemins Q pour la paire xy */ /* règle du max */ if(etatxy&2){ /* Si on a ajouté au moins 1 noeud au graphe des conflits. Rem: ici c.outmem=0 et c.G->n >= 1 */ u=c.max[c.paire[c.G->n-1]]; /* u=maximum de la paire du dernier noeud crée */ if((u>=0)&&(ps1_push(u,0,&c))) goto fin1; /* si max existe, on écrit 0 dans u */ } nextxy: /* cas où l'on a trouvé une bonne paire (x,y) */ /* rem: si version=0, alors forcément goodxy=0 */ if(etatxy==0) goto fin1; } /* fin du for(x,y=...) */ if(version==0) goto afterloop; /* on saute la partie "graphe des conflits" */ /* ici on essaie de mettre à jour les -1 qui restent */ loop_do: do{ G->int1++; if(c.nbi==0) break; /* fini: il ne reste plus de -1 à modifier */ x=c.nbi; /* mémorise le nb total de valeurs à -1 */ for(u=0;un;u++){ /* pour toute valeur à -1, faire ... */ if(c.code[u]>=0) continue; /* ici code[u]==-1. On vérifie s'il y a 1 paire avec 1 seule valeur <1 */ if((c.nbc[c.paire[u]]==1)&&(ps1_push(u,0,&c))) goto fin1; else /* on vérifie si les voisins ne peuvent pas influencer u */ for(i=0,d=c.G->d[u];iL[u][i]; w=v>>LCONF; /* w=type de l'arc u->v */ y=c.code[v&CONFMASK]; /* y=code[noeud v] */ if(y<0) continue; /* on ne déduit rien */ /* applique une des règles similaire à ps1_push() */ switch(w){ case 0: if((y==0)&&(ps1_push(u,1,&c))) goto fin1; /* Tu<>Tv */ if((y==1)&&(c.nbcomp[u]+c.nbcomp[v]==n)&&(ps1_push(u,0,&c))) goto fin1; break; case 1: if(ps1_push(u,y,&c)) goto fin1; break; /* Tu=Tv */ case 2: if((y==1)&&(ps1_push(u,1,&c))) goto fin1; break; /* TuTv */ } } } } while(c.nbi0){ /* lit les valeurs à l'envers */ u=MEM(CPARAM,(2*i-1)*sizeof(int),int); v=MEM(CPARAM,(2*i)*sizeof(int),int); MEM(CPARAM,0,int)--; if(ps1_push(u,v,&c)) goto fin1; goto loop_do; } } afterloop: /* ici il n'y a presque plus rien à faire */ val=0; /* on a pas trouvé de paire (x,y) */ goto fin0; fin1: val=1; fin0: if(version>0){ if(G==GF) PrintConflit(&c); /* affiche que le 1er niveau de récurrence et si -check */ for(u=0;un;u++) free(c.comp[u]); free_graph(c.G); /* c.G->L après c.G->n n'ont pas été alloués ou sont déjà libérés */ } free_path(Q); free_path(R); free_param_dfs(p); free(T); free(M); N--; return val; } void RemoveVertex(graph *G,int u) /* Supprime toutes les occurences de u dans G, sans renuméroter les sommets et sans réalouées les listes. Après cet appel, les listes de G ne sont plus forcément triées, mais la liste de G->L[u] existe toujours (G->d[u] est à zéro). Effet de bord: modifie G->sort, G->d[.], G->L[.]. Attention ! G->n n'est pas modifié. */ { int i,j,v,du=G->d[u],dv; G->d[u]=0; for(i=0;iL[u][i]; dv=G->d[v]; for(j=0;jL[v][j]==u) G->L[v][j]=G->L[v][--dv]; G->d[v]=dv; } G->sort=0; return; } int AdjGraph(graph *G,int u,int v) /* Return 1 ssi v apparaît dans la liste de u. */ { /* recherche dichotomique si le graphe est trié */ if(G->sort) return (bsearch(&v,G->L[u],LOAD->d[u],sizeof(int),fcmp_int)!=NULL); /* sinon, recherche linéaire */ int i; for(i=G->d[u];i>0;) if(G->L[u][--i]==v) return 1; /* on a trouvé v dans la liste de u */ return 0; } int Treewidth(graph *H,int code) /* Calcul approché ou excate de la treewidth de H. Si code=0, on calcule une borne supérieure (heuristique degmin). Si code=1 on calcule la valeur exacte. H n'est pas modifié. Dans H->int1 on renvoie le nb de tests effectués. */ { if(H==NULL) return 0; int *P,*D; int n,j,t,tw,l,v,n1; int d,r,i,u,k; int d0,r0,i0,u0; graph *G; H->int1=0; n=H->n; n1=n-1; tw=(code==1)? Treewidth(H,0) : MIN(n1,NbEdges(H)); /* tw=upper bound sur tw. On a intérêt d'avoir la valeur la plus faible possible, car on va alors éliminer les mauvais ordres d'éliminations plus rapidement. tw max en fonction du nb m d'arêtes: m=0 => tw=0 m=1 => tw=1 m=2 => tw=1 m=3 => tw<=2 m=4 => tw<=2 m=5 => tw<=2? m=6 => tw<=3 ... */ ALLOCZ(P,n,int,_i); /* permutation initiales des sommets */ ALLOCZ(D,n,int,n1); do{ G=ExtractSubgraph(H,NULL,0,0); /* on copie H */ GraphRealloc(G,D); /* plonge G dans le graphe complet */ k=0; /* tw par défaut si G sans d'arêtes */ for(j=0;jint1++; u0=P[i0=j]; d0=r0=G->d[u0]; if(code==0){ for(i=j;id[u]; if(d<=d0){ /* calcule r=nb d'arêtes dans N(u) */ for(r=l=0;lL[u][l],G->L[u][t]); if((d=tw) goto nextP; /* on ne fera pas moins */ RemoveVertex(G,u0); /* supprime u */ /* remplace N(u) par une clique */ for(i=0;iL[u0][i]; for(t=i+1;tL[u0][t]; if(!AdjGraph(G,u,v)) ADD_EDGE(G,u,v); } } } /* fin for(j=...) */ tw=MIN(tw,k); nextP: free_graph(G); if((code==0)||(tw<2)) break; /* si tw(G)=0 ou 1, alors on ne trouvera pas plus petit */ } while(!NextPermutation(P,n,NULL)); free(D); free(P); return tw; } int *Prune(graph *G,int *z) /* Algorithme permettant de supprimer les sommets du graphe G par dégrés minimum. Un ordre d'élémination des sommets est renvoyé sous la forme d'un tableau de taille n. Plus précisément, on renvoie un tableau de sommets T de sorte que u=T[i] est un sommet de degré minimum du graphe G\(T[0]...T[i-1]). La complexité est linéaire, i.e. O(n+m). Si *z<>NULL, on retourne dans z le degré maximum rencontré donc la dégénérescence du graphe. */ { int i,j,u,v,d,k,p,r,t,c,n1,n=G->n; int *T,*R,*D,*P; /* 1. On construit les tableaux suivants: T[0..n[ = tableau de sommets triés par degré croissant (le résultat) R[0..n[ = tableau de positions dans T des sommets D[0..n[ = tableau des degrés des sommets P[0..n[ = tableau des positions dans T du premier sommet de degré donné 2. On traite les sommets dans l'ordre T[0],T[1],... Supposons que u=T[i]. Alors, pour chaque voisin v dans G, encore existant (donc situé après i dans le tableau T), on met à jour la structure T,R,D,P. */ /* initialise T,R,D,P */ if(n<1) return NULL; ALLOCZ(D,n,int,G->d[_i]); R=SortInt(D,NULL,n,0,NULL,SORT_INDEXe); ALLOC(T,n,int); for(u=0;u=0;i--) P[D[T[i]]]=i; /* i=n-1,...,0 */ for(c=i=0;ic) c=D[u]; /* mémorise le plus grand degré rencontré */ d=G->d[u]; /* d = deg(u) */ for(j=0;jL[u][j]; /* v=voisin de u */ r=R[v]; /* v=T[r]; */ if(r>i){ /* mettre à jour que si v existe encore */ k=D[v]--; /* le degré de v diminue, k=D[v] juste avant */ p=P[k--]++; /* on va échanger v et T[p]. Les sommets de degré k commencent juste après */ if(P[k]<0) P[k]=p; /* y'a un sommet de degré k en plus */ if(p>i){ /* si p est avant i, ne rien faire. Cel arrive que si k=0 */ t=T[p]; /* t = 1er sommet de de degré k */ T[p]=v; /* dans T, on avance v en position p (à la place de t donc) */ T[r]=t; /* on met t à la place de v */ R[v]=p; /* on met à jour la nouvelle position de v dans T */ R[t]=r; /* on met à jour la nouvelle position de t dans T */ } } } } if(z!=NULL) *z=c; /* retourne la dégénérescence */ free(R); free(D); free(P); return T; } int *GreedyColor(graph *G,int *R) /* Algorithme permettant de colorier de manière gloutonne un graphe G à n sommets. La complexité en temps est linéaire, i.e. O(n+m). On renvoie un tableau C[0..n[ où C[u] est la couleur du sommet u, un entier entre 0 et n-1. Le tableau R[0..n[ donne un ordre (inverse) de visite des sommets: On colorie le sommet u avec la plus petite couleur possible dans le graphe induit par les sommets situé après u dans R (on commence donc avec R[n-1]). Si R=NULL, alors l'ordre R[i]=i est utilisé. On renvoie dans G->int1 la couleur maximum utilisée (donc le nb de couleurs-1). */ { int i,j,u,d,l,c,n=G->n; int *C,*M,*L; /* On utilise 3 tableaux: C[0..n[ = tableau final des couleurs, au départ =-1 L[0..n-1[ = liste de couleurs utilisées par le sommet courant M[0..n-1[, M[i]=1 ssi la couleur i est utilisée par un voisin du sommet courant, au départ =0. On met une sentiennelle à M si bien que toujours on M[n-1]=0. */ if(n<1) return NULL; ALLOCZ(C,n,int,-1); ALLOCZ(M,n,int,0); i=n-1; G->int1=0; ALLOC(L,i,int); for(;i>=0;i--){ /* en partant de la fin */ u=(R==NULL)? i : R[i]; d=G->d[u]; /* d = deg(u) */ /* on liste dans L et M les couleurs rencontrées */ for(j=l=0;jL[u][j]]; /* c=couleur du voisin v */ if(c>=0){ /* voisin déjà colorié ? */ L[l++]=c; /* on ajoute la couleur c à la liste */ M[c]=1; /* la couleur c n'est pas à prendre */ G->int1=MAX(G->int1,c); } } /* on cherche la 1ère couleur à 1 (=non-rencontrée) */ j=0; while(M[j]) j++; /* s'arrête toujours à cause de la sentiennelle */ C[u]=j; /* j est la couleur recherchée pour u */ /* il faut ré-initialiser rapidement M */ for(j=0;j=0, retourne 1 ssi i est adjacent à j 4. adj(i,-2): construit l'étiquette du sommet i (via la variable NAME). Rem: adj(-1,j) doit toujours retourner le nb de sommets du graphe et fixer la variable N à cette valeur. Certaines fonctions adj() suppose que isort, le test est linéaire ou logarithmique en min{deg(i),deg(j)}. */ { if(j<0){ if(j==-1) free_graph(LOAD); return 0; } if(i<0){ LOAD=File2Graph(SPARAM,2); /* remplit LOAD à partir du fichier */ if(LOAD->f>0){ /* si c'est une famille, on sélectionne le premier graphe */ graph *G=ExtractSubgraph(LOAD->G[0],NULL,0,0); /* copie le premier graphe */ free_graph(LOAD); /* libère complètement la famille LOAD */ LOAD=G; /* LOAD=premier graphe */ } if(!LOAD->sym) DIRECTED=1; /* si le graphe est asymétrique, affichage DIRECTED */ return N=LOAD->n; } int k; /* pour avoir du min{deg(i),deg(j)} en non-orienté */ if((!DIRECTED)&&(LOAD->d[i]>LOAD->d[j])) SWAP(i,j,k); return AdjGraph(LOAD,i,j); } int prime(int i,int j){ if(j<0) return 0; if(i<0){ N=PARAM[0]; return N; } return (i>1)? ((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 mycielski(int i,int j){ // suppose i>1); if(j==i) return 0; if(i=k)&&(i!=(j-k))); /* utilise i1)&&(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 ggosset(int i,int j){ /* ggosset p k d_1 v_1 ... d_k v_k mais PARAM = p k d d_1 v_1 ... d_k v_k Sommet: permutations du vecteur (v_1...v_1, ..., v_k...v_k) (ou de son opposé) telles que le nombre de valeurs entières v_t est d_t. On pose REP[i] = vecteur du sommet i qui est de taille d=d_1+...+d_k. On a l'arête i-j ssi le produit scalaire entre REP[i] et REP[j] vaut p. Pour calculer tous les vecteurs de taille d (les sommets) à partir de (v_1...v_1,...,v_k...v_k) on procède comme suit (codage d'un multi-ensemble à k valeurs): On choisit les positions de v_1 (il y en a Binom(d,d_1) possibles, puis on choisit les positions de v_2 parmi les d-d_1 restantes (il y en a Binom(d-d_1,d_2)), puis les positions de v_3 parmi les d-d_1-d_2 retantes, etc. Pour chaque t, les positions des d_t valeurs v_t sont codées par un sous-ensemble S[t] de [0,d-1] de taille d_t. */ int t,p,d=PARAM[2]; if(j<0){ if(j==-1) FREE2(REP,N); if(j==-2) NAME_Vector(REP[i],d,",","[]",1); return 0; } if(i<0){ int m,u,v,c,**S,*P,k=PARAM[1]; /* Calcule N */ m=d; N=2; for(t=3;m>0;t += 2){ p = PARAM[t]; /* p=d_i */ N *= Binom(m,p); m -= p; } ALLOCMAT(REP,N,d,int); /* vecteur de taille d représentant les sommets */ ALLOC(P,d,int); /* tableau intermédiaire */ ALLOCMAT(S,k,d,int); /* on réserve k tableaux (sous-ensembles) de taille <= d */ for(t=0;t0){ if(P[v]<0){ c--; if(c==0) P[v]=t; /* écrit t et passe à la casse suivante */ } v++; } } } /* Remplit REP[u] et REP[u+1] grâce au tableau P (et incrémenter u) */ for(t=0;t (mot binaire,niveau) */ y=j/d;j=j%d; /* j -> (mot binaire,niveau) */ return (abs(x-y)==1) && ( (i==j) || ((i^j)==(1<<(b-x-1))) ); } int debruijn(int i,int j){ int d,b,k,x,y; if(j<0) return 0; b=PARAM[1]; if(i<0){ N=1; d=PARAM[0]; for(k=0;k=r); r=s; q=q/t; x=x*b+r; } REP[l][0]=x; } return N; } N=PARAM[2]; /* modifie le nb de sommets */ x=debruijn(REP[i][0],REP[j][0]); N=PARAM[3]; /* rétablit le nb de sommets */ return x; } int gpstar(int i,int j) /* REP[i][0...n-1] = représentation de la permutation du sommet i. */ { int n,k,c; n=PARAM[0]; if(j<0){ if(j==-1) FREE2(REP,N); if(j==-2){ if(n<10) NAME_Vector(REP[i],n,"","",1); else NAME_Vector(REP[i],n,",","()",1); } return 0; } if(i<0){ int *P; for(N=1,k=2;k<=n;k++) N *= k; ALLOCMAT(REP,N,n,int); ALLOCZ(P,n,int,_i); /* initialise P */ /* génère toutes les permutations */ for(c=0;c>1; /* on rétablit la valeur initiale de PARAM[1] */ } if(j==-2){ if(m<10) NAME_Vector(REP[i],t,"","",1); else NAME_Vector(REP[i],t,",","()",1); } return 0; } if(i<0){ int *S,*P; t=(t<<1)+1; PARAM[1]=t; for(N=1,k=m-t+1;k<=m;k++) N *= k; /* calcul N */ ALLOCMAT(REP,N,t,int); ALLOCZ(S,t,int,_i); ALLOCZ(P,t,int,_i); for(u=0;u=x); /* si x=y, on incrémente y */ } } return N; } return linial(i,j); } int pancake(int i,int j){ /* REP[i][0...n-1] = représentation de la permutation du sommet i. */ int n,k,l; if((j<0)||(i<0)) return gpstar(i,j); /* Test d'adjacence à partir de REP[i] et REP[j] */ n=l=PARAM[k=0]; while(REP[i][k]==REP[j][k]) k++; /* i<>j, donc on s'arrête sans dépasser k */ while((kj) return 0; return thetagone(j,i); } int udg(int i,int j){ /* Deux points peuvent avoir les même coordonnées. */ if(j<0) return thetagone(0,-1); if(i<0){ if(NORM==2) DPARAM[0] *= DPARAM[0]; /* si norme L_2, alors r=r^2 */ return thetagone(-1,0); } return (Norme(i,j)<=DPARAM[0]); } int gabriel(int i,int j){ /* Adjacence en O(N). */ int z; double r,xi,yi; if((j<0)||(i<0)) return thetagone(i,j); xi=XPOS[i]; yi=YPOS[i]; /* on sauvegarde les positions de i */ XPOS[i]=(xi+XPOS[j])/2.0; /* on change les positions de i */ YPOS[i]=(yi+YPOS[j])/2.0; /* i <- milieu du segment i-j */ r=Norme(i,j); /* rayon du disque centré en c */ for(z=0;zj) return 0; return nng(j,i); } int hexagon(int i,int j){ /* Utilise le fait que i=t-1) i++; /* on insère virtuellement le coin (0,2q+1) */ if(j>=t-1) j++; if((p&1)==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=(q<<1)+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&1)==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&1)-ci)<2) ); } int hanoi(int i,int j){ /* Adjacence: on écrit i (et j) en base b, mot de n lettres. i et j sont adjacents ssi i=Puv...v et j=Pvu...u où P est un préfixe commun, et u,v des lettres qui se suivent (modulo b). */ int n,b,ri,rj,u,v,k; n=PARAM[0]; b=PARAM[1]; if(j<0){ if(j==-2){ if(b<10) NAME_Base(i,b,n,"","",1); else NAME_Base(i,b,n,",","",1); } return 0; } if(i<0){ if(b<2) return N=0; for(N=k=1;k<=n;k++) N *= b; /* calcule le nombre de sommets N=b^n */ return N; } /* on égraine les chiffres en base b */ for(ri=rj=k=0;k1, les autres sommets commenceront tous par 0. On a alors 3 autres triangles, numérotés 0,1,2, le triangle i à pour sommet le sommet i. Les 3 sommets internes sont 00,01,02. Le sommet 00 partage les triangles 0 et 1, 01 les triangles 1 et 2, 02 les triangles 2 et 0. Si n>2, tous les autres sommets commenceront par 00, 01 ou 02 suivant le sous-triangle auquel ils appartiennent. Dans le sous-triangle 0, les 3 sommets internes seront 000, 001, 002. Etc. Ex: n=2 b=3 0 / \ 00 -- 02 / \ / \ 1 -- 01 -- 2 Adjacence: CAS 1: extrémité (|i|=1 et |j|=n) Si i=x et n>1, alors il est voisin de: - 0 x^{n-2} x - 0 x^{n-2} (x-1) Si i=x et n=1, alors c'est le CAS 2. Soit P=le plus préfixe commun entre i et j, et k=|P| CAS 2: sommet du triangle le plus interne (|i|=|j|=n) Si i=Px, k=n-1, et n>0, alors il est voisin de: - P (x+1) - P (x-1) CAS 3: sommet entre deux triangles (1<|i|1)&&(REP[j][0]==0)){ x=REP[i][0]; for(c=t=1;t<=n-2;t++) if(REP[j][t]!=x) { c=0; break; } if(c){ /* c=vrai ssi j=0x^(n-2) */ if(REP[j][n-1]==x) return 1; if(REP[j][n-1]==((x-1+b)%b)) return 1; } } /* calcule k=longueur du préfixe commun */ for(k=0;(kj, alors on ne fait rien */ } int rpartite(int i,int j) /* On se sert du fait que ipart(j). Pour celà, on fait une recherche dichotomique de la part de i (c'est-à-dire d'un k tq WRAP[k]<=i=WRAP[k]) return 1; /* i et j sont dans des parts différentes */ r=k; /* ici i>1; }else{ /* ici WRAP[k]<=i>1; } } return (j>=WRAP[k+1]); /* ici i est dans la part k. On vérifie si j aussi */ } int aqua(int i,int j) /* On se sert de REP[i][0..n], n=PARAM[0]. */ { int n=PARAM[0]; /* n=nb de paramètres */ if(j<0){ if(j==-1) FREE2(REP,N); if(j==-2) NAME_Vector(REP[i],n,",","",1); return 0; } int k,x,y; int *C=PARAM+1; /* C=tableau de contraintes */ if(i<0){ x=*C; /* s=PARAM[1]=premier terme=la somme */ int *S=NextPart(NULL,n,x,C); N=0; /* calcule d'abord N pour ALLOCREP() */ do N++; while(NextPart(S,n,x,C)!=NULL); ALLOCMAT(REP,N,n,int); N=0; /* calcule les sommets */ do{ for(k=0;k=0)&&(y>=0)) return 0; /* si plus de 2 différences, alors pas d'arc */ if(x<0) x=k; else if(y<0) y=k; } /* soit on a versé x vers y */ /* k=quantité que l'on peut verser de x à y */ k=MIN(C[y],REP[i][x]+REP[i][y])-REP[i][y]; if((REP[j][y]==REP[i][y]+k)&&(REP[j][x]==REP[i][x]-k)) return 1; /* soit on a versé y vers x */ /* k=quantité que l'on peut verser de y à x */ k=MIN(C[x],REP[i][y]+REP[i][x])-REP[i][x]; if((REP[j][x]==REP[i][x]+k)&&(REP[j][y]==REP[i][y]-k)) return 1; return 0; } int theta0(int i,int j){ int T[]={0,-3,5,5,0,6,3,-2}; if(j<0) return 0; if(i<0) return N=7; return GraphFromArray(i,j,T); } int icosa(int i,int j){ int T[]={ 5,0,1,2,3,4,5,6,7,8, 9,10,11,6,4,7,3,8,2, 9,1,10,5,1,2,0,3,4,0, 5,6,10,9,11,9,11,8,11,7,-2}; if(j<0) return 0; if(i<0) return N=12; return GraphFromArray(i,j,T); } int rdodeca(int i,int j){ int T[]={ 0,1,2,3,4,5,0,6, 7,1,7,8,2,8,9,3,9, 10,4,10,11,5,11,6, 7,12,9,12,11,-1, 0,13,2,13,4,-2}; if(j<0) return 0; if(i<0) return N=14; return GraphFromArray(i,j,T); } int cubocta(int i,int j){ int T[]={ 0,1,2,3,4,5,0,6,7,2, 8,9,5,6,10,7,1,11,0,-1, 3,10,4,9,11,8,3,-2}; if(j<0) return 0; if(i<0) return N=12; return GraphFromArray(i,j,T); } int tutte(int i,int j){ int T[]={ 0,-3,8, 4,8,9,3,9,10,11,2, 11,12,1,12,13,14,10, 14,7,6,15,13,-1, 0,16,-3,7, 23,19,23,24,18,24,25,26,17, 26,27,16,27,28,29,25, 29,22,21,30,28,-1, 0,31,-3,7, 38,34,38,39,33,39,40,41,32, 41,42,31,42,43,44,40, 44,37,36,45,43,-1, 15,20,-1, 30,35,-1,45,5,-2}; if(j<0) return 0; if(i<0) return N=46; return GraphFromArray(i,j,T); } int fritsch(int i,int j){ int T[]={-4,0,4,6,3,7,2,4,-1,1,8,1,7,6,8,5,0,2,-2}; if(j<0) return 0; if(i<0) return N=9; return GraphFromArray(i,j,T); } int soifer(int i,int j){ int T[]={-4,0,6,4,2,6,0,7,5,8,1,3,8,5,3,-2}; if(j<0) return 0; if(i<0) return N=9; return GraphFromArray(i,j,T); } int poussin(int i,int j){ int T[]={ -4,0,2,4,6,8,10,12,14,2, 0,13,11,9,5,8,12,7,3,14,7,-1, 4,1,9,0,11,-1,1,5,-1,3,6,-2}; if(j<0) return 0; if(i<0) return N=15; return GraphFromArray(i,j,T); } int errara(int i,int j){ int T[]={ 0,-5,10,9,5,15,11,16,-1, 1,-5,6,16,12,13,4,7,-1, 2,-6,6,7,8,9,10,-1, 3,-6,11,12,13,14,15,11,-1, 4,-5,7,8,5,14,13,-1, 5,-5,8,9,14,15,-1, 16,-5,6,11,12,10,-2}; if(j<0) return 0; if(i<0) return N=17; return GraphFromArray(i,j,T); } int kittell(int i,int j){ int T[]={ 0,-3,22, 10,12,14,5,13,11,3,10,2,9,1,6,0, 5,16,6,17,7,1,8,22,20,18,7,-1, 5,15,21,14,22,9,12,-1, 9,14,-1,18,8,20,-1, 19,-5,15,16,17,21,-1, 2,0,3,0,4,13,4,11,-2}; if(j<0) return 0; if(i<0) return N=23; return GraphFromArray(i,j,T); } int moser(int i,int j){ int T[]={0,1,2,3,0,4,5,6,0,-1,1,3,2,5,4,6,-2}; if(j<0) return 0; if(i<0) return N=7; return GraphFromArray(i,j,T); } int markstrom(int i,int j){ int T[]={ 8,0,-3,12,5,13,-3,7, 3,21,22,23,0,23,1,2,21,22,18,-1, 15,20,14,13,4,-1, 6,12,7,-1,17,19,-1, 9,11,10,16,-2}; if(j<0) return 0; if(i<0) return N=24; return GraphFromArray(i,j,T); } int robertson(int i,int j){ int T[]={-4,0,4,8,13,17,2,6,10,14,0, 1,9,16,5,12,1,-1,3,11,18,7,15,3,-2}; if(j<0) return 0; if(i<0) return N=19; return GraphFromArray(i,j,T); } /* -1: fin d'un chemin. -2: fin du tableau, donc du graphe. -3: sommets consécutifs. Une suite "a,-3,n" est équivalent à "a,a+1,...,a+n,-1" -4: cycle hamiltonien, équivalent à "0,-3,N-1,0,-1" -5: étoile, "a,-5,a_1,...,a_n,-1" représente une étoile de centre a et de feuilles a_1...a_n. C'est équivalent à "a, a_1, a, a_2, a,..., a, a_n, -1." On peut remplacer le -1 par n'importe qu'elle valeur négative qui peut ainsi être enchaînée. -6: comme -5, sauf que les sommets a_i,a_{i+1} sont adjacents. */ int headwood4(int i,int j){ int T[]={ 0,-6,1,5,4,3,13,12,2,-1, 1,-6,5,6,7,8,2,-1, 2,-6,8,9,10,11,-1, 16,-6,4,15,17,19,5,-1, 12,-6,11,20,19,18,-1, 14,15,3,14,13,18,17,14,18,-1, 22,-6,6,21,24,23,7,-1, 5,20,6,11,21,10,24,9,23,8,-2}; if(j<0) return 0; if(i<0) return N=25; return GraphFromArray(i,j,T); } int wiener_araya(int i,int j){ int T[]={ 0,-5,1,4,12,15,-1, 1,-3,39, 41,-5,20,23,36,-1, 18,36,35,16,17,1,2,19,-1, 3,21,22,5,4,8,7,26,27,9,10,29,28,39,25,24,6,-1, 8,12,11,31,32,13,14,34,33,37,38,23,-1, 30,40,33,-2}; if(j<0) return 0; if(i<0) return N=42; return GraphFromArray(i,j,T); } int flower_snark(int i,int j){ if(j<0){ if(j==-2) sprintf(NAME,"%c%i",((i&3)==0)? 'c' : 't'+(i&3),i>>2); return 0; } int k=PARAM[0]; if(i<0) return N=(k<<2); int u=(j>>2)-(i>>2); /* i=0 */ i &= 3; j &= 3; if(u==0) return (i==0); if((u==1)&&(i==j)) return (i>0); if(u!=(k-1)) return 0; i*=j; return ((i==1)||(i==6)); } int clebsch(int i,int j){ if((i<0)||(j<0)) return grid(i,j); if(((i|j)==N-1)&&((i&j)==0)) return 1; /* sommets opposés */ return grid(i,j); } 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. */ { if(j<0) return kautz(0,-1); int k=PARAM[1],t; if(i<0){ /* calcule N et REP[i][0..k-1] */ int v,*X,**T; N=PARAM[0]; ALLOCMAT(REP,N,k,int); /* REP est la représentation finale */ ALLOCMAT(T,N,1,int); /* T=arbre aléatoire */ ALLOCZ(X,N,int,_i); /* permutation aléatoire */ for(t=0;t0) c=random()%N; else c=0; T[0][0]=0; /* père de racine = 0 plutôt que -1, car X[-1] n'existe pas ! */ for(t=0;tr)){ /* on commence à monter */ t=1-t; while(z0); /* 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(xj) { k=i; i=j; j=k; } /* maintenant i=n) return (j-i<=k); /* dans la même clique ? */ return (REP[j][0]==i); } int gpetersen(int i,int j){ /* u_i dans [0,n[ et v_i dans [n,2n[, N=2n. Utilise le fait que ii */ if(j==(i+n)) return 1; /* sinon, par d'arête entre u_i et v_j */ if((i0 */ d=1+random()%r; /* choisir un degré d pour x: d=[1,...,r] */ for(y=0;yj) { x=i; i=j; j=x; } /* maintenant i= N0 sont ceux de degré 1. Se sert du fait que i0) star_tab[t]=random()%N0; else star_tab[t]=t/(-STAR); } POS=0; /* il ne faut pas afficher les positions, cela na pas de sens */ return N; /* valeur de retour pour star() */ } if(j<0){ simule(adj0,i,j,N0); if(j==-1) free(star_tab); return 0; /* valeur de retour pour star() */ } if((i=N0)&&(j>=N0)) return 0; /* les sommets ajoutés ne sont pas voisins */ /* ici i=0. Si k sommets ont été supprimés, alors les valeurs de V[] sont dans SHIFT+[0,n-k[. Initialise aussi le tableau VF[j], avec j=0...n-k, de sorte que VF[j]=i si VF[i] est le j-ème sommet non supprimé. Il est important que VF[] ait une taille de N au départ. Un realloc() le redimensionne plus tard dans la fonction. */ int i,j,k,r; /* r=n-(nb de sommets supprimés) */ long seuil; /* supprime les sommets */ if(DELV<0.0){ /* ici on en supprime exactement |DELV| sommets */ if(DELV<-N) DELV=-N; for(i=0;i=0) { VF[r]=i; V[i]=r++; } } else{ /* ici on supprime chaque sommet avec proba DELV */ seuil=(double)DELV*(double)RAND_MAX; for(i=r=0;i0) for(i=0;i*dmax) *dmax=d; if(d<*dmin) *dmin=d; } *m >>= 1; return; } void Header(){ /* Affiche et calcule le préambule (date, nom du graphe, nb d'arêtes ...). */ 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==F_standard)||(FORMAT==F_dot))) printf("//\n"); else i=system("printf '//\n// ' ; date"); printf("// gengraph"); for(i=1;iNAMEMAX) Erreur(17); return NAME; } 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é). Si HEADER=1, alors Out() doit se charger d'afficher l'en-tête. Si CHECK<>0 alors elle doit aussi se charger de créer et de remplir la liste d'adjacence du graphe GF et de son nombre de sommets NF. */ int x,y,z; double w; char fmt[15]="%lf %lf\n"; /* format de précision par défaut de XPOS/YPOS */ /*----------------------- Initialise la fonction -------------------------*/ if((i<0)&&(j<0)){ if(CHECK) L0=L1=L2=Insert(NULL,0,0); /* initialise la liste */ switch(FORMAT){ case F_standard: if(HEADER) Header(); STRsep1=""; STRsep2=" "; STRedge=(DIRECTED)?"->":"-"; return; case F_dot: if(HEADER) Header(); printf("%sgraph {\n",(DIRECTED)?"di":""); if(VCOLOR&0x10){ printf("\tgraph [layout=nop, splines=line];\n"); printf("\tnode [height=1.0, width=0.4, style=filled, shape=rectangle];\n"); return; } if(POS){ w=PosAspect(); /* layout=nop: pour dire à dot de ne pas re-calculer les positions */ printf("graph [layout=nop, splines=line, bb=\"%.2lf,%.2lf,%.2lf,%.2lf\"];\n", w*XMIN-2*VSIZEK*VSIZEXY,w*YMIN-2*VSIZEK*VSIZEXY, w*XMAX+2*VSIZEK*VSIZEXY,w*YMAX+2*VSIZEK*VSIZEXY); /* si on ne met pas le "2*" on a des sommets tronqués ... */ } printf("node ["); if(LABEL==0) printf("label=\"\", shape=point, "); /* sans label */ w=POS?VSIZESTD:VSIZEXY; /* taille des sommets */ printf("height=%.2lf, width=%.2lf];\n",w,w); STRsep1=";"; STRsep2="; "; STRedge=(DIRECTED)?"->":"--"; } return; } /*-------------------- Termine la fonction ----------------------*/ if(i<0){ if(CHECK){ free(L1); /* supprime le dernier élément de L0 */ if(L0==L1) GF=new_graph(0); else{ L2->next=NULL; /* coupe la liste à l'avant dernier élément */ GF=List2Graph(L0,4); /* initialise GF et NF */ } NF=GF->n; } switch(FORMAT){ case F_standard: case F_dot: if((VCOLOR&0x10)==0){ /* court-circuite l'affichage du graphe si "-vcolor list" */ if(LIGNE>0) printf("%s\n",STRsep1); /* newline si fini avant la fin de ligne */ if(FORMAT==F_standard) return; if(POS||(LABEL>0)){ w=PosAspect(); printf("\n"); for(y=0;y0){ VIDE(NAME); /* on vide NAME avant de le calculer */ if(LABEL==1){ adj(x,-2); /* calcule le nom dans NAME */ if(strlen(NAME)>NAMEMAX) Erreur(17); } printf("%slabel=\"%s\"",(POS?", ":""),(NONVIDE(NAME)? NAME : "\\N")); } printf("];\n"); } } if(VSIZE&&(NF>0)){ /* taille en fonction du degré */ double alpha,smin; ScanINC(&x,&z,&y); /* x=degmax, z=degmin */ smin=POS?VSIZESTD:VSIZEXY; alpha=(x==z)? 0.0 : smin*(VSIZEK-1)/((double)(x-z)); printf("\n"); for(y=0;y0)){ color c={0,0,0},*P; int *D; if(VCOLOR&0x8){ /* on initialise la PALETTE */ NPAL=strlen(SPARAM); if(NPAL==1) { /* SPARAM=x alors SPARAM=xx */ SPARAM[1]=SPARAM[0]; SPARAM[2]='\0'; NPAL=2; } ALLOC(PALETTE,NPAL,color); for(y=z=0;y2){ /* si "degm" ou "randg" */ int *T; if((VCOLOR&07)==3) T=Prune(GF,&y); /* si "degm" */ else{ ALLOCZ(T,NF,int,_i); /* si "randg" */ Permute(T,NF); } D=GreedyColor(GF,T); /* calcule les couleurs */ free(T); /* plus besoin de T */ for(x=y=0;xy) y=D[x]; /* calcule le max sur D */ y++; /* y=nb de couleurs */ } else{ ScanINC(&x,&z,&y); /* calcule x=degmax, z=degmin */ y=x-z+1; /* nb a priori de couleurs nécessaires */ ALLOCZ(D,NF,int,INC[VF[_i]]-z); if((VCOLOR&0x7)==2){ /* si "degr" */ int *R=SortInt(D,NULL,N,0,&y,SORT_RANKe); /* après SortInt(), y=nb de degré différents */ free(D); D=R; /* on substitue R à D */ } } /* ici D[x]=indice de la couleur du sommet x, et y nb de couleurs */ P=GradColor(PALETTE,NPAL,y); /* calcule un palette P de y couleurs. NB: ici NPAL>1 */ printf("\n"); if(VCOLOR&0x10){ /* si "-vcolor list" */ char s[6],cc; for(x=0;x 0 */ } for(y=0;y=0) L1=Insert(L2=L1,j,(DIRECTED)?4:1); /* on ajoute ->j ou -j */ if(VCOLOR&0x10) return; /* ne rien faire d'autre si "-vcolor list". NB: CHECK>0 dans ce cas */ } if((FORMAT==F_standard)||(FORMAT==F_dot)){ if(j<0) LAST=-1; /* sommet isolé, donc LAST sera différent de i */ if(i!=LAST) printf("%s%s",(LIGNE==0)? "" : STRsep2,ComputeNAME(i)); LAST=j; /* si i=LAST, alors affiche ...-j. Si j<0 alors LAST<0 */ if(j>=0) printf("%s%s",STRedge,ComputeNAME(j)); if(++LIGNE==WIDTH){ LIGNE=0; LAST=-1; printf("%s\n",STRsep1); } } /* si format matrix, smatrix etc., ne rien faire (c'est fait à la fin) */ return; } double CheckProba(double v){ /* Retourne une probabilité entre [0,1]. */ if(v<0.0) return 0.0; if(v>1.0) return 1.0; return v; } void Grep(char *mot) /* Cherche "^....mot" dans l'aide contenu dans le source du programme, puis termine par exit(). */ { char *s; ALLOC(s,CMDMAX,char); strcat(s,"sed -n '/*[#] ###/,/### #/p' "); strcat(strcat(s,*ARGV),".c|"); /* rem: sed -E n'est pas standard ... */ strcat(strcat(strcat(s,"sed -nE '/^[.][.][.][.]"),mot),"(($)|( ))/,/^$/p'|"); strcat(s,"sed 's/^[.][.][.][.]/ /g'"); printf("\n"); int i=system(s); free(s); exit(EXIT_SUCCESS); } char *NextArg(int *i) /* Retourne ARGV[i] s'il existe et incrémente i. Si l'argument n'existe pas, on affiche l'aide en ligne sur le dernier argument demandé et s'arrête. */ { if(((*i)==ARGC)||(strcmp(ARGV[*i],"?")==0)) Grep(ARGV[(*i)-1]); return ARGV[(*i)++]; } void CheckHelp(int *i) /* Incrémente i puis vérifie si le prochain argument est "?". Si tel est le cas, une aide est affichée. Cette fonction devrait être appellée lorsqu'on vérifie l'aide pour un graphe sans paramètre. Sinon c'est fait par NextArg(). */ { (*i)++; if(((*i)!=ARGC)&&(strcmp(ARGV[*i],"?")==0)) Grep(ARGV[(*i)-1]); return; } void Help(int i) /* Affiche l'aide complète. */ { char *s; ALLOC(s,CMDMAX,char); strcat(s,"sed -n '/*[#] ###/,/### #/p' "); strcat(strcat(s,*ARGV),".c | "); strcat(s,"sed -e 's/\\/\\*[#] ###//g' -e 's/### [#]\\*\\///g' "); if((++i==ARGC)||(ARGV[i][0]=='?')) strcat(s,"-e 's/^[.][.][.][.][.]*/ /g'|more"); else{ strcat(s,"|awk 'BEGIN{x=\".....\"}/^[.][.][.][.]./{x=$0} /"); strcat(strcat(s,ARGV[i]),"/{if(x!=\".....\")print substr(x,5)}'|sort -u"); } i=system(s); free(s); exit(EXIT_SUCCESS); } void ListGraph(void){ /* Affiche les graphes possibles et sort. */ char *s; ALLOC(s,CMDMAX,char); strcat(s,"sed -n '/*[#] ###/,/### #/p' "); strcat(strcat(s,*ARGV),".c| "); strcat(s,"sed -e 's/\\/\\*[#] ###//g' -e 's/### [#]\\*\\///g'| "); strcat(s,"grep '^[.][.][.][.][^-.]'| sed 's/^[.][.][.][.]//g'"); int i=system(s); free(s); exit(EXIT_SUCCESS); } void PipeDot(int j){ /* Gère l'option "-format dot" Ici on a: ARGV[j]="dot" Rem: on pourrait utiliser popen() au lieu de réécrire la ligne de commande et de lancer system() */ int i; char *s; char type[5]; CheckHelp(&j);j--; strcpy(type,ARGV[j]+3); /* type= */ ARGV[j][3]='\0'; /* ARGV[j]="dot" plutôt que "dot" */ /* On réécrit la ligne de commande: 1. en remplaçant -format dot par -format dot 2. puis en ajoutant à la fin: | dot -T -K ... */ ALLOC(s,CMDMAX,char); for(i=0;ij0 i1->j1 ... i8->j8 i9->j8 ... */ { const int k=8; /* nb de "->" affichés par ligne */ int i; printf("%s",s); /* normalement printf(s) est ok, mais Warning sur certain system */ for(i=0;i%i%s",i,P[i],(((i%k)<(k-1))&&(if;i++){ P=Isomorphism(G,F->G[i]); free(P); if(P!=NULL) return 0; } return 1; } int ftest_minus_id(graph *G) /* Retourne VRAI ssi F2 ne contient aucun graphe d'identifiant égale à celui de G. La complexité est en O(log|F2|). Il est important que F2 soit triée par ordre croissant des ID. */ { graph *F=MEM(FPARAM,0,graph*); if(F==NULL) return 0; return (bsearch(&G,F->G,F->f,sizeof(graph*),fcmp_graphid)==NULL); } int ftest_unique(graph *G) /* Retourne VRAI ssi la sous-famille F allant des indices i+1 à F->f ne contient pas G, où i=MEM(FPARAM,0,int). Effet de bord: MEM(FPARAM,0,int) est incrémenté. */ { int i = (MEM(FPARAM,0,int) += 1); int *P; for(;if;i++){ P=Isomorphism(G,FAMILY->G[i]); free(P); if(P!=NULL) return 0; } return 1; } int ftest_minor(graph *G) /* Retourne VRAI ssi H est mineur de G. */ { int *T=Minor(MEM(FPARAM,0,graph*),G); if(T==NULL) return 0; free(T); return 1; } int ftest_minor_inv(graph *G) { int *T=Minor(G,MEM(FPARAM,0,graph*)); if(T==NULL) return 0; free(T); return 1; } int ftest_sub(graph *G) /* Retourne VRAI ssi H est sous-graphe de G avec même nb de sommets. */ { graph *C=Subgraph(MEM(FPARAM,0,graph*),G); if(C==NULL) return 0; free_graph(C); return 1; } int ftest_sub_inv(graph *G) { graph *C=Subgraph(G,MEM(FPARAM,0,graph*)); if(C==NULL) return 0; free_graph(C); return 1; } int ftest_isub(graph *G) /* Retourne VRAI ssi H est sous-graphe induit de G. */ { int *C=InducedSubgraph(MEM(FPARAM,0,graph*),G); if(C==NULL) return 0; free(C); return 1; } int ftest_isub_inv(graph *G) { int *C=InducedSubgraph(G,MEM(FPARAM,0,graph*)); if(C==NULL) return 0; free(C); return 1; } int ftest_iso(graph *G) /* Retourne VRAI ssi H est isomorphe à G. Aucun intérêt de faire programmer iso-inv. */ { int *T=Isomorphism(MEM(FPARAM,0,graph*),G); if(T==NULL) return 0; free(T); return 1; } int ftest_id(graph *G) { return InRange(G->id,FPARAM); } int ftest_vertex(graph *G) { return InRange(G->n,FPARAM); } int ftest_edge(graph *G) { return InRange(NbEdges(G),FPARAM); } int ftest_degmax(graph *G) { return InRange(Degree(G,1),FPARAM); } int ftest_degmin(graph *G) { return InRange(Degree(G,0),FPARAM); } int ftest_deg(graph *G) { int u,b=1,n=G->n; for(u=0;(ud[u],FPARAM); return b; } int ftest_degenerate(graph *G) { int x; int *T=Prune(G,&x); free(T); return InRange(x,FPARAM); } int ftest_gcolor(graph *G) { int *T=Prune(G,NULL); int *C=GreedyColor(G,T); free(T); free(C); return InRange(1+G->int1,FPARAM); } int ftest_component(graph *G) { param_dfs *p=dfs(G,0,NULL); int x=p->nc; free_param_dfs(p); return InRange(x,FPARAM); } int ftest_cutvertex(graph *G) { param_dfs *p=dfs(G,0,NULL); int x=p->na; free_param_dfs(p); return InRange(x,FPARAM); } int ftest_biconnected(graph *G) { param_dfs *p=dfs(G,0,NULL); int b=(p->nc==1)&&(p->na==0)&&(G->n>2); free_param_dfs(p); return b; } int ftest_ps1xx(graph *G, int version) { path *P=new_path(G,NULL,G->n); int v=PS1(G,P,version); free_path(P); return v; } int ftest_ps1(graph *G) { return ftest_ps1xx(G,0); } int ftest_ps1b(graph *G) { return ftest_ps1xx(G,1); } int ftest_ps1c(graph *G) { return ftest_ps1xx(G,2); } int ftest_ps1x(graph *G) { return ftest_ps1xx(G,3); } int ftest_radius(graph *G) { param_bfs *p; int x=G->n; int u; for(u=0;un;u++){ p=bfs(G,u,NULL); if(x>=0){ if(p->ncn) x=-1; else x=MIN(x,p->rad); } free_param_bfs(p); } return InRange(x,FPARAM); } int ftest_girth(graph *G) { param_bfs *p; int x=1+G->n; int u; for(u=0;un;u++){ p=bfs(G,u,NULL); if(p->girth>0) x=MIN(x,p->girth); free_param_bfs(p); } if(x>G->n) x=-1; return InRange(x,FPARAM); } int ftest_diameter(graph *G) { param_bfs *p; int x=-1; int u; for(u=0;un;u++){ p=bfs(G,u,NULL); if(p->nc==G->n) x=MAX(x,p->rad); free_param_bfs(p); } return InRange(x,FPARAM); } int ftest_hyperbol(graph *G) { param_bfs *p; int **D; int n=G->n,h=0; int u,v,x,y,d1,d2,d3,t; ALLOC(D,n,int*); /* calcule la matrice de distances */ for(u=0;uD; if(p->ncD[v]<0) p->D[v]=INT_MAX; } p->D=NULL; free(p); /* efface p, mais pas p->D */ } /* pour tous les quadruplets {u,v,x,y} */ for(u=0;uh) h=d1-d2; } FREE2(D,n); /* efface la matrice de distances */ if(h==INT_MAX) h=-1; /* cela ne peut jamais arriver */ return InRange(h,FPARAM); } int ftest_tw(graph *G) { return InRange(Treewidth(G,1),FPARAM); } int ftest_tw2(graph *G) { return (Treewidth(G,0)<=2); } int ftest_rename(graph *G) { G->id=SHIFT++; return 1; } graph *Filter(graph *F,test *f,int code){ /* Etant donnée une famille de graphes et une fonction de test, renvoie une sous-famille de graphes G de F telle que f(G) est vraie (si code=0) ou faux (si code=1). Attention! si on libère F, cela détruit la sous-famille renvoyée. Effet de bord: si PVALUE est vrai, alors dans les graphes filtrés G on met dans G->int1 la valeur du paramètre, CVALUE. */ if((F==NULL)||(F->f==0)) return NULL; int i,j,n=F->f; graph *R; R=new_graph(0); ALLOC(R->G,n,graph*); /* a priori R est de même taille que F */ for(i=j=0;iG[i])^code){ R->G[j++]=F->G[i]; if(PVALUE) F->G[i]->int1=CVALUE; } } R->G=REALLOC(R->G,j,graph*); R->f=j; return R; } graph *Graph2Family(graph *G){ /* Renvoie une famille composée d'un seul graphe G. Effet de bord: met G->id=0. */ graph *F=new_graph(0); ALLOC(F->G,1,graph*); F->G[0]=G; F->f=1; G->id=0; return F; } void ApplyFilter(int code,int index) /* Applique le filtre FTEST (avec le code=0 ou 1) à la famille de graphes FAMILY (voir un graphe seul), et affiche la famille résultante. On affiche aussi le nombre de graphes obtenus et la ligne de commande (sous forme de commentaire). Si index>=0, alors ARGV[index] donne le paramètre. Effet de bord: FAMILY est libérée. */ { graph *R; int i; if(FAMILY->f==0) FAMILY=Graph2Family(FAMILY); /* transforme en famille si graphe simple */ R=Filter(FAMILY,FTEST,code); /* calcule la sous-famille */ printf("// #graphs: %i\n// generated by:",(R==NULL)?0:R->f); for(i=0;i=0)&&(PVALUE)) /* on affiche la valeur */ for(i=0;if;i++) printf("[%i] %s: %i\n",R->G[i]->id,ARGV[index],R->G[i]->int1); else PrintGraph(R); /* on affiche le graphe */ /* ! aux free() de famille de graphes ! */ free_graph(FAMILY); /* libère en premier la famille */ free(R->G); /* libère la sous-famille */ free(R); return; } /*********************************** MAIN ***********************************/ int main(int argc, char *argv[]){ int i,j,k,noredirect; long seuil,seuilr; ARGC=argc; ARGV=argv; if(ARGC==1) Help(0); /* aide si aucun argument */ /* valeurs par défaut */ adj=ring; PARAM[0]=0; VIDE(NAME); /* chaîne vide */ seuil=(long)getpid(); /* seuil par défaut */ i=1; /***************************************** ANALYSE DE LA LIGNE DE COMMANDE Il faut éviter de faire des traitements trop coûteux en temps dans l'analyse de la ligne de commande car on peut être amené à refaire cette analyse une deuxième fois à cause de -visu et à cause de la réécriture de la ligne de commande. *****************************************/ while(i1.0) DELV=1.0; goto fin; } if EQUAL("-dele"){ i++; DELE=CheckProba(STRTOD(NextArg(&i))); goto fin; } if EQUAL("-redirect"){ i++; REDIRECT=CheckProba(STRTOD(NextArg(&i))); goto fin; } if EQUAL("-star"){ i++; STAR=STRTOI(NextArg(&i)); goto fin; } if EQUAL("-vcolor"){ i++;NextArg(&i);i--; /* pour l'aide en ligne */ /* bit 0,1,2: code la fonction de couleur=1,2,3,4 bit 3: "pal" bit 4: "list" */ if EQUAL("deg"){ i++; VCOLOR=(VCOLOR|0x7)^0x7; /* efface les 3 derniers bits */ VCOLOR |= 1; goto fin; } if EQUAL("degr"){ i++; VCOLOR=(VCOLOR|0x7)^0x7; VCOLOR |= 2; goto fin; } if EQUAL("degm"){ i++; VCOLOR=(VCOLOR|0x7)^0x7; VCOLOR |= 3; CHECK |= 1; goto fin; } if EQUAL("randg"){ i++; VCOLOR=(VCOLOR|0x7)^0x7; VCOLOR |= 4; CHECK |= 1; goto fin; } if EQUAL("pal"){ i++; VCOLOR |= 0x8; /* set bit-3 */ strcpy(SPARAM,NextArg(&i)); /* SPARAM=ARGV[i] */ goto fin; } if EQUAL("list"){ i++; VCOLOR |= 0x10; CHECK |= 1; FORMAT = F_dot; goto fin; } Erreur(9); } if EQUAL("-format"){ i++;NextArg(&i);i--; /* pour l'aide en ligne */ FORMAT=-1; /* pour savoir si on a trouvé le FORMAT */ if EQUAL("standard") FORMAT=F_standard; if EQUAL("matrix") { FORMAT=F_matrix; CHECK |= 1;} if EQUAL("smatrix"){ FORMAT=F_smatrix;CHECK |= 1;} if EQUAL("list") { FORMAT=F_list; CHECK |= 1;} if EQUAL("xy") FORMAT=F_xy; if EQUAL("no") FORMAT=F_no; if PREFIX("dot"){ /* si "dot" ou "dot" */ if EQUAL("dot") FORMAT=F_dot; /* si "dot" seul */ else PipeDot(i); /* se termine par exit() */ } if(FORMAT<0) Erreur(5); /* le format n'a pas été trouvé */ i++; goto fin; } if EQUAL("-xy"){ i++;NextArg(&i);i--; /* pour l'aide en ligne */ POS=1; /* il faut POS=1 */ if EQUAL("load"){ i++; FILEXY=NextArg(&i); /* pointe sur le nom du fichier */ goto fin; } if EQUAL("noise"){ i++; NOISEr=STRTOD(NextArg(&i)); NOISEp=STRTOD(NextArg(&i)); goto fin; } if EQUAL("scale"){ i++; SCALEX=STRTOD(NextArg(&i)); SCALEY=STRTOD(NextArg(&i)); goto fin; } if EQUAL("seed"){ i++; SEEDk=abs(STRTOI(NextArg(&i))); SEEDp=STRTOD(NextArg(&i)); XYtype=2; goto fin; } if EQUAL("round"){ i++; ROUND=STRTOI(NextArg(&i)); goto fin; } if EQUAL("permutation"){ CheckHelp(&i); ROUND=0; /* a priori coordonnées entières dans ce cas */ XYtype=3; goto fin; } if EQUAL("unique"){ CheckHelp(&i); XYunique=1; goto fin; } Erreur(1); /* l'option après -xy n'a pas été trouvée */ } if EQUAL("-algo"){ i++;NextArg(&i);i--; /* pour l'aide en ligne */ Erreur(11); /* l'option après -algo n'a pas été trouvée */ } if EQUAL("-filter"){ i++;NextArg(&i);i--; /* pour l'aide en ligne */ FAMILY=File2Graph(NextArg(&i),2); /* lit une famille ou un graphe */ if(FPARAM==NULL) ALLOC(FPARAM,PARAMSIZE,void*); NextArg(&i);i--; /* vérifie s'il y a bien un autre argument */ PVALUE=0; /* par défaut, on affiche pas "value" mais les graphes */ if EQUAL("not"){ k=1; i++;NextArg(&i);i--; } else k=0; /* vérifie s'il y a bien un autre argument */ if EQUAL("rename"){ FTEST=ftest_rename; i++; SHIFT=STRTOI(NextArg(&i)); ApplyFilter(0,-1); goto fin; } if EQUAL("biconnected"){ FTEST=ftest_biconnected; filter0: i++; ApplyFilter(k,-1); goto fin; } if EQUAL("id"){ FTEST=ftest_id; filter1: i++; ReadRange(NextArg(&i),FPARAM); ApplyFilter(k,i-2); goto fin; } int c; /* code pour File2Graph() */ if EQUAL("minor"){ FTEST=ftest_minor; c=34; /* détection du shift et charge toujours un graphe */ filter2: i++; MEM(FPARAM,0,graph*)=File2Graph(NextArg(&i),c); ApplyFilter(k,-1); free_graph(MEM(FPARAM,0,graph*)); goto fin; } if EQUAL("ps1x"){ i++; FTEST=ftest_ps1x; MEM(CPARAM,0,int)=STRTOI(NextArg(&i)); for(c=MEM(CPARAM,0,int);c>=1;c--){ /* met les arguments à l'envers */ MEM(CPARAM,(2*c-1)*sizeof(int),int)=STRTOI(NextArg(&i)); MEM(CPARAM,(2*c)*sizeof(int),int)=STRTOI(NextArg(&i)); } i--; goto filter0; } if EQUAL("ps1"){ FTEST=ftest_ps1; goto filter0; } if EQUAL("ps1b"){ FTEST=ftest_ps1b; goto filter0; } if EQUAL("ps1c"){ FTEST=ftest_ps1c; goto filter0; } if EQUAL("tw2"){ FTEST=ftest_tw2; goto filter0; } if EQUAL("unique"){ FTEST=ftest_unique; MEM(FPARAM,0,int)=0; goto filter0; } if EQUAL("vertex"){ FTEST=ftest_edge; goto filter1; } if (EQUAL("edge")||EQUAL("edges")){ FTEST=ftest_edge; goto filter1; } if EQUAL("deg"){ FTEST=ftest_deg; goto filter1; } if EQUAL("degenerate"){ FTEST=ftest_degenerate; goto filter1; } if EQUAL("degmax"){ FTEST=ftest_degmax; goto filter1; } if EQUAL("degmin"){ FTEST=ftest_degmin; goto filter1; } if EQUAL("gcolor"){ FTEST=ftest_gcolor; goto filter1; } if EQUAL("component"){ FTEST=ftest_component; goto filter1; } if EQUAL("cut-vertex"){ FTEST=ftest_cutvertex; goto filter1; } if EQUAL("radius"){ FTEST=ftest_radius; goto filter1; } if EQUAL("girth"){ FTEST=ftest_girth; goto filter1; } if EQUAL("diameter"){ FTEST=ftest_diameter; goto filter1; } if EQUAL("hyperbol"){ FTEST=ftest_hyperbol; goto filter1; } if EQUAL("tw"){ FTEST=ftest_tw; goto filter1; } if EQUAL("minor-inv"){ FTEST=ftest_minor_inv; c=34; goto filter2; } if EQUAL("sub"){ FTEST=ftest_sub; c=34; goto filter2; } if EQUAL("sub-inv"){ FTEST=ftest_sub_inv; c=34; goto filter2; } if EQUAL("isub"){ FTEST=ftest_isub; c=34; goto filter2; } if EQUAL("isub-inv"){ FTEST=ftest_isub_inv; c=34; goto filter2; } if EQUAL("iso"){ FTEST=ftest_iso; c=34; goto filter2; } if EQUAL("minus"){ FTEST=ftest_minus; c=2; goto filter2; } if EQUAL("minus-id"){ FTEST=ftest_minus_id; c=10; goto filter2; } /* alias */ if EQUAL("connected"){ FTEST=ftest_component; ReadRange("1",FPARAM); goto filter0; } if EQUAL("bipartite"){ FTEST=ftest_gcolor; ReadRange("<3",FPARAM); goto filter0; } if EQUAL("forest"){ FTEST=ftest_degenerate; ReadRange("<2",FPARAM); goto filter0; } if EQUAL("all"){ FTEST=ftest_vertex; ReadRange(">0",FPARAM); goto filter0; } Erreur(14); /* l'option après -filter n'a pas été trouvée */ } if EQUAL("-check"){ i++;NextArg(&i);i--; /* pour l'aide en ligne */ if(CPARAM==NULL) ALLOC(CPARAM,PARAMSIZE,void*); if EQUAL("bfs"){ CHECK=CHECK_BFS; check0: i++; MEM(CPARAM,0,int)=STRTOI(NextArg(&i)); goto fin; } if EQUAL("iso"){ CHECK=CHECK_ISO; check1: MEM(CPARAM,0,int)=++i; NextArg(&i); /* pour vérifier si i existe */ goto fin; } if(EQUAL("deg")||EQUAL("edge")||EQUAL("edges")){ CHECK=CHECK_DEG; check2: i++; goto fin; } if EQUAL("paths"){ CHECK=CHECK_PATHS; check3: i++; MEM(CPARAM,0,int)=STRTOI(NextArg(&i)); MEM(CPARAM,sizeof(int),int)=STRTOI(NextArg(&i)); goto fin; } if EQUAL("ps1x"){ i++; CHECK=CHECK_PS1x; MEM(CPARAM,0,int)=STRTOI(NextArg(&i)); for(k=MEM(CPARAM,0,int);k>=1;k--){ /* met les arguments à l'envers */ MEM(CPARAM,(2*k-1)*sizeof(int),int)=STRTOI(NextArg(&i)); MEM(CPARAM,(2*k)*sizeof(int),int)=STRTOI(NextArg(&i)); } goto fin; } if EQUAL("dfs"){ CHECK=CHECK_DFS; goto check0; } if EQUAL("belman"){ CHECK=CHECK_BELMAN; goto check0; } if EQUAL("sub"){ CHECK=CHECK_SUB; goto check1; } if EQUAL("isub"){ CHECK=CHECK_ISUB; goto check1; } if EQUAL("minor"){ CHECK=CHECK_MINOR; goto check1; } if EQUAL("degenerate"){ CHECK=CHECK_DEGENERATE; goto check2; } if EQUAL("gcolor"){ CHECK=CHECK_GCOLOR; goto check2; } if EQUAL("ps1"){ CHECK=CHECK_PS1; goto check2; } if EQUAL("ps1b"){ CHECK=CHECK_PS1b; goto check2; } if EQUAL("ps1c"){ CHECK=CHECK_PS1c; goto check2; } if EQUAL("twdeg"){ CHECK=CHECK_TWDEG; goto check2; } if EQUAL("tw"){ CHECK=CHECK_TW; goto check2; } if EQUAL("girth"){ CHECK=CHECK_GIRTH; goto check2; } if EQUAL("maincc"){ CHECK=CHECK_MAINCC; goto check2; } if EQUAL("paths2"){ CHECK=CHECK_PATHS2; goto check3; } Erreur(12); /* l'option après -check n'a pas été trouvée */ } /* graphes de base */ if EQUAL("tutte"){ adj=tutte; param0: CheckHelp(&i); goto fin; } if EQUAL("prime"){ adj=prime; param1: i++; PARAM[0]=STRTOI(NextArg(&i)); goto fin; } if EQUAL("arboricity"){ adj=arboricity; param2: i++; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=STRTOI(NextArg(&i)); goto fin; } if EQUAL("sat"){ adj=sat; param3: i++; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=STRTOI(NextArg(&i)); PARAM[2]=STRTOI(NextArg(&i)); goto fin; } if EQUAL("ktree"){ PARAM[2]=0; gotoktree: i++; adj=ktree; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=STRTOI(NextArg(&i)); if(PARAM[0]<=PARAM[1]) Erreur(6); goto fin; } if EQUAL("kpath"){ PARAM[2]=1; goto gotoktree; } if EQUAL("hypercube"){ adj=grid; gotohypercube: i++; PARAM[0]=STRTOI(NextArg(&i)); if(PARAM[0]+1>DIMAX) Erreur(4); for(k=1;k<=PARAM[0];k++) PARAM[k]=2; goto fin; } if EQUAL("ggosset"){ adj=ggosset; i++; int k,d=0; PARAM[0]=STRTOI(NextArg(&i)); /* copie p */ PARAM[1]=STRTOI(NextArg(&i)); /* copie k */ for(k=0;k<(PARAM[1]<<1);k++) PARAM[k+3]=STRTOI(NextArg(&i)); /* il est important de calculer la dimension d pour accélérer l'ajacence */ for(k=0;kDIMAX) Erreur(4); for(k=1;k<=PARAM[0];k++) PARAM[k]=STRTOI(NextArg(&i)); goto fin; } if EQUAL("rpartite"){ adj=rpartite; goto gotogrid; } if EQUAL("aqua"){ adj=aqua; DIRECTED=1; goto gotogrid; } if EQUAL("ring"){ adj=ring; gotoring: i++; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=STRTOI(NextArg(&i)); if(PARAM[1]+2>DIMAX) Erreur(4); for(k=0;k=PARAM[0]-1) PARAM[1]=PARAM[0]-1; if(PARAM[1]<1) Erreur(6); goto fin; } if EQUAL("kneser"){ i++; adj=kneser; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=STRTOI(NextArg(&i)); PARAM[2]=STRTOI(NextArg(&i)); if(PARAM[1]>PARAM[0]) PARAM[1]=PARAM[0]; goto fin; } if EQUAL("udg"){ i++; adj=udg; POS=1; PARAM[0]=STRTOI(NextArg(&i)); DPARAM[0]=STRTOD(NextArg(&i)); /* !!! lecture d'un double */ if(DPARAM[0]<0) DPARAM[0]=sqrt(log((double)PARAM[0])/((double)PARAM[0])); /* Threshold théorique r0 (cf. [EMY07]): pour n=10, r0=0.4798 pour n=100, r0=0.2145 pour n=1000, r0=0.08311 pour n=10000, r0=0.03034 */ goto fin; } if EQUAL("rplg"){ i++; adj=rplg; PARAM[0]=STRTOI(NextArg(&i)); DPARAM[0]=STRTOD(NextArg(&i)); goto fin; } if EQUAL("thetagone"){ i++; adj=thetagone; POS=1; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=STRTOI(NextArg(&i)); PARAM[2]=STRTOI(NextArg(&i)); DPARAM[0]=CheckProba(STRTOD(NextArg(&i))); /* !!! lecture d'un double */ goto fin; } if PREFIX("load"){ i++; adj=load; strcpy(SPARAM,NextArg(&i)); /* SPARAM=ARGV[i] */ goto fin; } if EQUAL("theta0"){ adj=theta0; goto param0; } if EQUAL("icosa"){ adj=icosa; goto param0; } if EQUAL("rdodeca"){ adj=rdodeca; goto param0; } if EQUAL("cubocta"){ adj=cubocta; goto param0; } if EQUAL("fritsch"){ adj=fritsch; goto param0; } if EQUAL("soifer"){ adj=soifer; goto param0; } if EQUAL("poussin"){ adj=poussin; goto param0; } if EQUAL("errara"){ adj=errara; goto param0; } if EQUAL("kittell"){ adj=kittell; goto param0; } if EQUAL("moser"){ adj=moser; goto param0; } if EQUAL("markstrom"){ adj=markstrom; goto param0; } if EQUAL("robertson"){ adj=robertson; goto param0; } if EQUAL("headwood4"){ adj=headwood4; goto param0; } if EQUAL("wiener_araya"){ adj=wiener_araya; goto param0; } if EQUAL("pstar"){ adj=pstar; PARAM[1]=2; goto param1; } if EQUAL("paley"){ adj=paley; goto param1; } if EQUAL("mycielski"){ adj=mycielski; goto param1; } if EQUAL("wheel"){ adj=wheel; goto param1; } if EQUAL("windmill"){ adj=windmill; goto param1; } if EQUAL("interval"){ adj=interval; goto param1; } if EQUAL("permutation"){ adj=permutation; goto param1; } if EQUAL("pancake"){ adj=pancake; goto param1; } if EQUAL("crown"){ adj=crown; goto param1; } if EQUAL("flower_snark"){ adj=flower_snark; goto param1; } if EQUAL("gabriel"){ adj=gabriel; POS=1; goto param1; } if EQUAL("rng"){ adj=rng; POS=1; goto param1; } if EQUAL("nng"){ adj=nng; POS=1; goto param1; } if EQUAL("gpetersen"){ adj=gpetersen; goto param2; } if EQUAL("butterfly"){ adj=butterfly; goto param2; } if EQUAL("debruijn"){ adj=debruijn; goto param2; } if EQUAL("kautz"){ adj=kautz; goto param2; } if EQUAL("gpstar"){ adj=gpstar; goto param2; } if EQUAL("hexagon"){ adj=hexagon; goto param2; } if EQUAL("whexagon"){ adj=whexagon; goto param2; } if EQUAL("hanoi"){ adj=hanoi; goto param2; } if EQUAL("sierpinski"){ adj=sierpinski; goto param2; } if EQUAL("kpage"){ adj=kpage; goto param2; } if EQUAL("rarytree"){ adj=rarytree; goto param2; } if EQUAL("line-graph"){ adj=linegraph; goto param2; } if EQUAL("linial"){ adj=linial; goto param2; } if EQUAL("linialc"){ adj=linialc; goto param2; } if EQUAL("arytree"){ adj=arytree; goto param3; } /* graphes composés */ if EQUAL("tree"){ adj=arboricity; PARAM[1]=1; goto param1; } if EQUAL("cycle"){ adj=ring; PARAM[1]=PARAM[2]=1; goto param1; } if EQUAL("binary"){ adj=arytree; PARAM[1]=PARAM[2]=2; goto param1; } if EQUAL("rbinary"){ adj=rarytree; PARAM[1]=2; goto param1; } if EQUAL("stable"){ adj=ring; PARAM[1]=0; goto param1; } if EQUAL("clique"){ adj=ring; NOT=1-NOT; PARAM[1]=0; goto param1; } if EQUAL("outerplanar"){ adj=kpage; PARAM[1]=1; goto param1; } if EQUAL("prism"){ adj=gpetersen; PARAM[1]=1; goto param1; } if EQUAL("td-delaunay"){ adj=thetagone; POS=1; PARAM[1]=PARAM[2]=3; DPARAM[0]=1.0; goto param1; } if EQUAL("theta"){ i++; adj=thetagone; POS=1; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=3; PARAM[2]=STRTOI(NextArg(&i)); DPARAM[0]=6.0/(double)PARAM[2]; goto fin; } if EQUAL("dtheta"){ i++; adj=thetagone; POS=1; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=3; PARAM[2]=STRTOI(NextArg(&i))/2; DPARAM[0]=3.0/(double)PARAM[2]; goto fin; } if EQUAL("yao"){ i++; adj=thetagone; POS=1; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=0; PARAM[2]=STRTOI(NextArg(&i)); DPARAM[0]=2.0/(double)PARAM[2]; goto fin; } if EQUAL("path"){ i++; adj=grid; PARAM[0]=1; PARAM[1]=STRTOI(NextArg(&i)); goto fin; } if EQUAL("torus"){ i++; adj=grid; PARAM[0]=2; PARAM[1]=-STRTOI(NextArg(&i)); PARAM[2]=-STRTOI(NextArg(&i)); goto fin; } if EQUAL("mesh"){ i++; adj=grid; PARAM[0]=2; PARAM[1]=STRTOI(NextArg(&i)); PARAM[2]=STRTOI(NextArg(&i)); goto fin; } if EQUAL("mobius"){ i++; adj=ring; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=2; PARAM[2]=1; PARAM[3]=PARAM[0]/2; goto fin; } if EQUAL("star"){ i++; adj=rpartite; PARAM[0]=2; PARAM[1]=1; PARAM[2]=STRTOI(NextArg(&i)); goto fin; } if EQUAL("random"){ i++; adj=ring; NOT=1-NOT; PARAM[0]=STRTOI(NextArg(&i)); DELE=1.0-STRTOD(NextArg(&i)); PARAM[1]=0; goto fin; } if EQUAL("tw"){ PARAM[2]=0; gototw: i++; adj=ktree; PARAM[0]=STRTOI(NextArg(&i)); PARAM[1]=STRTOI(NextArg(&i)); DELE=0.5; goto fin; } if EQUAL("pw"){ PARAM[2]=1; goto gototw; } if EQUAL("bipartite"){ i++; adj=rpartite; PARAM[0]=2; PARAM[1]=STRTOI(NextArg(&i)); PARAM[2]=STRTOI(NextArg(&i)); goto fin; } if EQUAL("claw"){ i++; adj=rpartite; PARAM[0]=2;PARAM[1]=1;PARAM[2]=3; goto fin; } if EQUAL("cylinder"){ i++; adj=grid; PARAM[0]=2; PARAM[1]=STRTOI(NextArg(&i)); PARAM[2]=-STRTOI(NextArg(&i)); goto fin; } if EQUAL("caterpillar"){ i++; adj=grid; k=STRTOI(NextArg(&i)); /* nb de sommets total */ srandom(seuil); /* initialise le générateur aléatoire */ STAR=random()%k; /* entre 0...k-1 sommets de deg=1. Active l'opération star() */ PARAM[0]=1; PARAM[1]=k-STAR; /* PARAM[0]=nb de sommets du chemin, qui est >=1 */ goto fin; } if EQUAL("sunlet"){ i++; adj=grid; PARAM[0]=1; PARAM[1]=-STRTOI(NextArg(&i)); STAR=-1; goto fin; } /* graphes sans paramètres, donc commençant par CheckHelp() */ if EQUAL("cube"){ CheckHelp(&i); adj=crown; PARAM[0]=4; goto fin; } if EQUAL("tietze"){ CheckHelp(&i); adj=flower_snark; PARAM[0]=3; goto fin; } if EQUAL("hajos"){ CheckHelp(&i); adj=sierpinski; PARAM[0]=2; PARAM[1]=3; goto fin; } if EQUAL("gosset"){ CheckHelp(&i); adj=ggosset; PARAM[0]=8; PARAM[1]=2; PARAM[2]=2;PARAM[3]=3; PARAM[4]=6;PARAM[5]=-1; goto fin; } if EQUAL("diamond"){ CheckHelp(&i); adj=cage; PARAM[0]=4; PARAM[1]=2; PARAM[2]=2;PARAM[3]=0; goto fin; } if EQUAL("headwood"){ CheckHelp(&i); adj=cage; PARAM[0]=14; PARAM[1]=2; PARAM[2]=5;PARAM[3]=-5; goto fin; } if EQUAL("franklin"){ CheckHelp(&i); adj=cage; PARAM[0]=12; PARAM[1]=2; PARAM[2]=5;PARAM[3]=-5; goto fin; } if EQUAL("pappus"){ CheckHelp(&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 EQUAL("mcgee"){ CheckHelp(&i); adj=cage; PARAM[0]=24; PARAM[1]=3; PARAM[2]=12;PARAM[3]=7;PARAM[4]=-7; goto fin; } if EQUAL("tutte-coexter"){ CheckHelp(&i); adj=cage; PARAM[0]=30; PARAM[1]=6; PARAM[2]=-7;PARAM[3]=9;PARAM[4]=13; PARAM[5]=-13;PARAM[6]=-9;PARAM[7]=7; goto fin; } if EQUAL("gray"){ CheckHelp(&i); adj=cage; PARAM[0]=54; PARAM[1]=6; PARAM[2]=7;PARAM[3]=-7; PARAM[4]=25;PARAM[5]=-25; PARAM[6]=13;PARAM[7]=-13; goto fin; } if EQUAL("chvatal"){ CheckHelp(&i); adj=cage; PARAM[0]=PARAM[1]=12; PARAM[2]=PARAM[4]=PARAM[7]=PARAM[10]=PARAM[12]=PARAM[13]=3; PARAM[3]=PARAM[5]=PARAM[6]=PARAM[8]=6; PARAM[9]=PARAM[11]=-3; goto fin; } if EQUAL("house"){ CheckHelp(&i); adj=grid; NOT=1-NOT; PARAM[0]=1; PARAM[1]=5; goto fin; } if EQUAL("wagner"){ CheckHelp(&i); adj=ring; PARAM[0]=8; PARAM[1]=2; PARAM[2]=1; PARAM[3]=4; goto fin; } if EQUAL("grotzsch"){ CheckHelp(&i); adj=mycielski; PARAM[0]=4; goto fin; } if EQUAL("nauru"){ CheckHelp(&i); adj=pstar; PARAM[0]=4; PARAM[1]=2; /* important ! sinon pstar ne marche pas */ goto fin; } if EQUAL("petersen"){ CheckHelp(&i); adj=kneser; PARAM[0]=5; PARAM[1]=2; PARAM[2]=0; goto fin; } if EQUAL("desargues"){ CheckHelp(&i); adj=gpetersen; PARAM[0]=10; PARAM[1]=3; goto fin; } if EQUAL("durer"){ CheckHelp(&i); adj=gpetersen; PARAM[0]=6; PARAM[1]=2; goto fin; } if EQUAL("dodeca"){ CheckHelp(&i); adj=gpetersen; PARAM[0]=10; PARAM[1]=2; goto fin; } fin: if(j==i){ if PREFIX("-") Erreur(2); /* option non trouvée */ Erreur(10); /* graphe non trouvé */ } } /*********************************** COEUR DU GENERATEUR ***********************************/ srandom(seuil); /* initialise le générateur aléatoire */ if(STAR) { adj0=adj; adj=star; } /* le graphe est maintenant star() */ adj(-1,0); /* initialisation du graphe, calcule N avant la suppression des sommets */ if((FILEXY!=NULL)&&(XPOS==NULL)) InitXY(); /* il faut charger les positions */ if((POS)&&(XPOS==NULL)) Erreur(8); /* il faut que XPOS contiennent des valeurs ! */ if(LABEL==1) PERMUTE=0; /* si on souhaite les labels, on ne permute rien */ ALLOC(V,N,int); /* V[i]=étiquette du sommet i, -1 si i est supprimé */ ALLOC(VF,N,int); /* VF[j]=indice du j-ème sommet non supprimé */ NF=InitVertex(N); /* initialise V[i]/VF[i] et retourne NF=#sommets final */ ALLOC(INC,N,int); /* INC[i]=1 ssi i possède un voisin, 0 si sommet isolé */ for(j=0;j=0){ /* si i existe */ for(j=(DIRECTED)?0:i+1-LOOP;ji */ if((V[j]>=0)&&((!DIRECTED)||(i!=j)||(LOOP))) /* si j existe ... */ if((random()=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])) Out(i,-1); Out(-1,0); /* fin de l'affichage, doit être fait AVANT adj(0,-1) */ if((CHECK)&&(POS)){ /* mémorise XPOS,YPOS qui vont être supprimées par adj(0,-1) */ ALLOC(GF->xpos,NF,double); ALLOC(GF->ypos,NF,double); for(i=0;ixpos[i]=XPOS[VF[i]]; GF->ypos[i]=YPOS[VF[i]]; } } adj(0,-1); /* libère éventuellement la mémoire utilisée pour adj() */ adj=NULL; /* ici adj() n'est plus définie */ free(V); free(VF); free(INC); /*********************************** FIN DU GENERATEUR Le graphe est GF Le nombre de sommets est NF ***********************************/ if(CHECK){ if(CHECK==CHECK_MAINCC){ param_dfs *p=dfs(GF,MEM(CPARAM,0,int),NULL); graph *C; int u,d0,d1,n,c; int *T; for(i=c=n=d0=d1=0;inc;i++){ /* détermine la plus grosse cc */ /* d1-d0=nb de sommets de la cc numéro i */ if(i+1nc) d1=p->d[p->R[i+1]]; else d1=NF; if(d1-d0>n){ n=d1-d0; c=i; } /* n=nb de sommets de cc max */ d0=d1; } c=p->C[p->R[c]]; /* c=couleur de la composante max */ ALLOC(T,n,int); /* T=sommet de GF à garder */ for(i=j=0;iC[i]==c) T[j++]=i; free_param_dfs(p); /* p ne sert plus à rien */ C=ExtractSubgraph(GF,T,n,1); /* construit le cc max */ free(T); /* T ne sert plus à rien */ CHECK=0; /* pour ne pas restocker le graphe */ PrintGraph(C); free_graph(C); } if(CHECK==CHECK_BFS){ param_bfs *p=bfs(GF,MEM(CPARAM,0,int),NULL); int t,c; printf("root=%i\n",p->root); printf("rad[%i]=%i\n",p->root,p->rad); printf("girth[%i]=%i\n",p->root,p->girth); printf("#vertices traversed=%i\n",p->nc); printf("distance:\n"); for(k=1;k<=p->rad;k++){ printf(" %i:",k); for(c=t=0;tD[t]==k){ c++; printf(" %i",t); } printf(" (%i)\n",c); } printf("vertices not connected:"); for(t=c=0;tD[t]<0){ c++; printf(" %i",t); } if(c==0) printf(" none\n"); else printf(" (%i)\n",c); printf("parent:"); for(k=0;kP[k]); printf("\n"); free_param_bfs(p); } if(CHECK==CHECK_DFS){ param_dfs *p=dfs(GF,MEM(CPARAM,0,int),NULL); printf("source: %i\n",MEM(CPARAM,0,int)); printf("#component: %i%s\n",p->nc,(p->nc==1)?" (connected)":""); printf("#cut-vertex: %i%s\n",p->na,((p->nc==1)&&(p->na==0)&&(NF>2))?" (biconnected)":""); printf("root:"); for(i=0;inc;i++) printf(" %i",p->R[i]); if(p->na) printf("\ncut-vertex:"); for(i=0;iA[i]) printf(" %i",i); printf("\ncolor:"); for(i=0;iC[i]); printf("\nparent:"); for(i=0;iP[i]); printf("\n"); free_param_dfs(p); } if(CHECK==CHECK_BELMAN){ if(!WeightGraph(GF)) printf("Seulement possible pour les graphes géométriques !\n"); else{ double dx,dy,s=-1.0; int u; param_belman *p=Belman_Ford(GF,MEM(CPARAM,0,int)); printf("source=%i\n",p->source); for(k=0;kxpos[p->source]-GF->xpos[k]; dy=GF->ypos[p->source]-GF->ypos[k]; dx=sqrt(dx*dx+dy*dy); dy=(p->source!=k)? p->dist[k]/dx : 0.0; if(dy>s){ s=dy; u=k; } printf("dist[%i]=%lf parent=%i stretch=%lf (%lf)\n",k,p->dist[k],p->pere[k],dy,dx); } printf("stretch max: %lf\n",s); while(u!=p->source){ printf("%i->",u); u=p->pere[u]; } printf("%i\n",u); free_param_belman(p); } } if(CHECK==CHECK_DEG){ int *F; printf("#edges: %i\n",NbEdges(GF)); printf("degmin: %i degmax: %i\n",Degree(GF,0),Degree(GF,1)); k=NF; F=SortInt(GF->d,NULL,NF,0,&k,SORT_FREQv); printf("deg:"); for(k=0;kint1); PrintMorphism("Coloring (node->color):\n",T,GF->n); free(T); } if((CHECK>=CHECK_PS1)&&(CHECK<=CHECK_PS1x)){ int c=0; if(CHECK==CHECK_PS1b) c=1; if(CHECK==CHECK_PS1c) c=2; if(CHECK==CHECK_PS1x) c=3; path *P=new_path(GF,NULL,NF); int v=PS1(GF,P,c); printf("#tests: %i\nPS1: %s\n",GF->int1,v?"yes":"no"); free_path(P); } if(CHECK==CHECK_TWDEG){ int *T=Prune(GF,&k); printf("treewidth <= %i\n",Treewidth(GF,0)); printf("treewidth >= %i\n",k); free(T); } if(CHECK==CHECK_TW){ k=Treewidth(GF,1); printf("#tests: %i\ntreewidth: %i\n",GF->int1,k); } if(CHECK==CHECK_GIRTH){ param_bfs *p; int u,x=1+NF; for(u=0;ugirth>0) x=MIN(x,p->girth); free_param_bfs(p); } if(x>NF) x=-1; printf("girth: %i\n",x); } if((CHECK==CHECK_PATHS)||(CHECK==CHECK_PATHS2)){/* Sort tous les chemins de x à y */ int (*f)(graph*,path*,int)=(CHECK==CHECK_PATHS)? NextPath : NextPath2; path *P=new_path(GF,NULL,NF); /* chemin vide */ P->P[0]=MEM(CPARAM,0,int); P->P[1]=MEM(CPARAM,sizeof(int),int); int u,v=f(GF,P,-1); /* initialise le premier chemin */ while(v){ for(u=0;un;u++) printf("%i ",P->P[u]); printf("\n"); v=f(GF,P,0); } free_path(P); } if(CHECK==CHECK_ISO){ char *s=ARGV[MEM(CPARAM,0,int)]; graph *H=File2Graph(s,34); int *P=Isomorphism(GF,H); printf("H: %s\n#tests: %i\n",s,H->int1); if(P==NULL) printf("Non-isomorphic.\n"); else{ PrintMorphism("Isomorphism G->H:\n",P,NF); free(P); } free_graph(H); } if(CHECK==CHECK_SUB){ char *s=ARGV[MEM(CPARAM,0,int)]; graph *H=File2Graph(s,34); graph *S=Subgraph(GF,H); printf("H: %s\n#tests: %i\n",s,H->int1); if(S==NULL) printf("G is not a subgraph of H.\n"); else{ printf("Subgraph S of H isomorphic to G:\n"); PrintGraph(S); PrintMorphism("Isomorphism S->G:\n",S->pint1,S->n); free_graph(S); } free_graph(H); } if(CHECK==CHECK_MINOR){ char *s=ARGV[MEM(CPARAM,0,int)]; graph *H=File2Graph(s,34); int *C=Minor(H,GF); printf("H: %s\n#tests: %i\n",s,H->int1); if(C==NULL) printf("H is not a minor of G.\n"); else{ int c,u; printf("Model of H in G:\n"); for(c=0;cn;c++){ /* pour chaque couleur c */ printf("%i -> {",c); for(u=0;uint1); if(X==NULL) printf("H is not an induced subgraph of G.\n"); else{ int u; printf("Vertices of the induced subgraph S:"); for(u=0;un;u++) printf(" %i",X[u]); for(u=0;un;u++) GF->pint1[u]=X[u]; PrintMorphism("\nIsomorphism H->S:\n",GF->pint1,H->n); free(X); } free_graph(H); } free_graph(GF); free(CPARAM); } /* fin if(CHECK) */ //if(FILTER){ //switch(FILTER){ //default: break; //} //free_graph(GF); //free(FPARAM); //} /* fin if(FILTER) */ return 0; } /* Quelques règles pour la rédaction de l'aide: Le nom d'une option doit commencer par "-". Cela ne doit pas être le cas pour un graphe. Un paragraphe commence par "...." (les "...." ne sont pas affichés) et se termine par une ligne vide. Donc il faut ajouter "...." pour avoir un saut de ligne dans un même paragraphe. Le "....." (x5) devant "HISTORIQUE" est là pour stopper la recherche d'un mot clef ("?"). */ /*# ### Générateur de graphes - v2.8 - © Cyril Gavoille - Novembre 2011 USAGE gengraph [-option] graph_name [parameter_list] DESCRIPTION Génére sur la sortie standard un graphe. Par défaut le graphe est non orienté et affiché selon une liste d'arêtes (en texte), mais d'autres formats sont possibles: liste d'adjacence, dot de GraphViz, xfig ou pdf par exemple. En paramètre figure le nom du graphe ainsi que ses paramètres éventuels (nombre de sommets etc.). La commande appelée seule affiche l'aide sur le générateur. Si les paramètres d'une option ou d'un graphe sont absents ou remplacés par "?", une aide spécfique est affichée. Ex: gengraph -help gengraph -list | sort gengraph tree ? gengraph ? arbre gengraph tutte gengraph hypercube 8 gengraph mesh 7 3 -not gengraph mesh 20 20 -dele .2 gengraph rdodeca -visu gengraph tree 100 -visu gengraph gabriel 50 -visu gengraph sierpinski 7 3 -visu gengraph udg 400 .1 -visu gengraph udg 400 .1 -xy seed 3 1.5 -visu gengraph udg 400 -1 -vsize -vcolor deg -visu gengraph rplg 600 3.1 -vsize -vcolor deg -visu gengraph arytree 6 3 3 -dotfilter circo -visu gengraph arboricity 100 2 -vcolor degr -visu gengraph prime 6 -directed -noloop -visu gengraph aqua 3 3 2 1 -label 1 -directed -dotfilter dot -visu echo "0->1->2->0" | gengraph load - -check bfs 0 gengraph tutte | gengraph -filter - diameter p LE FORMAT STANDARD Le format par défaut (ou standard) est une liste d'arêtes ou de chemins écrits en texte simple. Ce format minimaliste est très proche de celui du format "dot" de GraphViz. D'autres formats de sortie sont possibles, notamment le format "dot" (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 (en fait cela peut être changé avec l'option -shift). Une arête entre i et j est représentée par i-j, un arc de i vers j 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. Dit autrement, le nombre de sommets du graphe est l'entier le plus grand + 1, et s'il y a i-j (ou i->j), alors il existe une arête (ou un arc) 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 (même convention pour les arcs 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-5 représente un graphe à 6 sommets composé d'un cycle de longueur 4 et de deux sommets de degré 1 attaché à 2. En voici une représentation graphique possible: 1 / \ 4-2 0 / \ / 5 3 COMMENT LE GENERATEUR FONCTIONNE ? Pour chaque graphe une fonction adj(i,j) est définie. Elle fournit l'adjacence (0 ou 1) entre les sommets i et j, entiers 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) (ou tous les couples (i,j) possibles dans le cas orientés). 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 à la volée. Ceci permet de générer des graphes de très grande taille sans nécessiter O(n^2) espace de mémoire centrale. Pour certains graphes cependant, comme les arbres, les graphes d'intersections, ou les graphes géométriques, une structure de données en O(n) est utilisée. Pour les formats d'affichage liste, matrix, et smatrix une structure de données de taille linéaire (en O(n+m) où m est le nombre d'arêtes) est utilisée en interne. Ces trois derniers formats sont donc à éviter. Pour la génération de très grand graphe, le format standard ou dot doit être privilégié. COMMANDES EXTERNES Le programme fait appel, pour certaines fonctions, aux commandes systèmes suivantes: sed, grep, awk, more, sort, date, printf, dot. OPTIONS ....-help [word] or ? [word] .... Affiche l'aide en ligne qui est contenue dans le fichier source (.c) du générateur. Pour cela, le source doit être dans le même répertoire que la commande. Si "word" est précisé, alors les options et noms de graphes contenant "word" sont affichés. Une aide détaillée sur chaque option (ou graphe) ainsi affichée peut alors être fourni par "gengraph option ?". La forme ? peut ne pas fonctionner si un fichier d'un seul caractère existe dans le répertoire courant (à cause de l'interprétation du shell). Il faut alors utiliser '?' au lieu de ?. .... Ex: gengraph ? arbre gengraph ktree ? ....-list .... Affiche la liste des graphes et leurs paramètres qu'il est possibles de générer, d'abord les graphes de bases puis les composés. On obtient une aide sur un graphe particulier si son nom est suivit d'un "?" ou si ses paramètres éventuelles sont abscents (dans ce cas il doit être le dernier mot de la ligne de commande). ....-directed ....-undirected .... Produit le graphe orienté en testant les n(n-1) arcs possibles, l'option -undirected permettant de revenir à la situation par défaut (voir aussi -(no)loop). En format standard où en dot, un arc apparaît comme x->y au lieu de x-y. Tous les graphes ne sont pas forcément définis pour fonctionner correctement avec cette option. La plupart des graphes vont apparaître comme orientés symétriques. ....-noloop ....-loop .... Ne produit pas les boucles pour les graphes (-noloop). C'est l'option par défaut pour les graphes non-orientés. L'option -loop les autorise. C'est l'option par défaut pour les graphes orientés. Cette option doit être placée après -(un)directed. ....-not .... Inverse la fonction d'adjacence, et donc affiche le complément du graphe. Cette option est prioritaire devant l'option -redirect. ....-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és. Si p est un entier <0, alors exactement -p sommets sont supprimés. Si k sommets sont supprimés, alors le nom des sommets restant est 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. ....-star n .... Ajoute n sommets pendant (degré 1) aux sommets du graphe. Si n>0, alors n représente le nombre total de sommets ajoutés, chacun des n sommets étant connectés aléatoirement uniforménent aux sommets du graphe original. Si n<0, alors -n sommets sont ajoutés à chacun des sommets du graphe. Cette opération est appliquée en priorité. ....-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 choisi 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 positif. 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 aux formats standard ou list. Cette option n'a pas d'effets pour les formats de sortie de type matrice. ....-permute .... Permute aléatoirement uniformément le nom des sommets lorsqu'ils sont affichés. Les numéros restent dans l'intervalle initial qui, sauf si l'option -shift a été utilisée, est [0,n[ où n est le nombre de sommets du graphe réellement généré. Voir aussi l'option -label. ....-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é. Les informations affichées sont: - la date - la ligne de commande qui a produit la génération du graphe - le nombre de sommets et d'arêtes - degrés maximum et minimum Remarque: pour les formats standard et dot, le nombre d'arêtes n'est pas déterminé avant l'affichage du graphe. Pour cette raison ces nombres ne sont pas affichés. ....-check [parameters] .... Stocke en mémoire le graphe généré sous la forme d'une liste d'adjacence et lui applique un algorithme. Cette option nécessite un espace supplémentaire en O(n+m) pour le stockage du graphe. Utiliser "-format no" pour ne pas afficher le graphe généré. .... -check bfs s .... Effectue un parcours en largeur d'abord sur le graphe généré depuis le sommet s. La distance depuis s est affichée, ainsi que l'arborescence (-1 indique que le sommet n'a pas de père). La longueur du plus petit cycle passant par s est aussi donnée. Elle vaut -1 s'il n'existe pas. .... -check dfs s .... Effectue un parcours en profondeur d'abord sur le graphe généré depuis le sommet s. Le nombre de composantes ainsi que l'arborescence (-1 indique que le sommet n'a pas de père) sont donnés. .... -check deg -check edge -check edges .... Affiche la distribution des degrés et le nombre d'arêtes du graphe. .... -check degenerate .... Donne la dégénérescence du graphe, ainsi que l'ordre d'élimination correspondant des sommets. .... -check girth .... Donne la maille du graphe, -1 si c'est l'infini. .... -check gcolor .... Donne une borne supérieure sur le nombre chromatique du graphe en utilisant l'heuristique du degré minimum. .... -check ps1 -check ps1b -check ps1c -check ps1x n u_1 v_1 ... u_n v_n .... Applique le test ps1 ou l'une de ses variantes (voir -filter ps1 pour plus de détail sur ce test). Affiche aussi le nombre de tests réalisés (nombre de paires de sommets et de chemins testés). .... -check paths x y -check paths2 x y .... Liste tous les chemins simples entre les sommets x et y. N'affiche rien si x et y ne sont pas connectés. L'ordre est défini suivant le premier plus court chemins dans l'ordre des sommets depuis le sommet x. La variante paths2 est similaire sauf que les paths renvoyés n'ont que des ensembles de sommets différents. .... -check iso H .... Teste si le graphe généré G est isomorphe à H. Si oui, l'isomorphisme de G à H est donné. Le nombre de tests affichés est le nombre de fois où les graphes sont comparés, la comparaison prend un temps linéaire en la taille des graphes). Plus les graphes sont symétriques (comme un cycle ou un hypercube), plus le nombre de tests sera important. .... Tester l'isomorphisme entre deux cycles de 8 sommets étiquetés aléatoirement prends environ 4 mille tests, et entre deux cycles de 12 sommets, 30 millions de tests soit 9" environ. Pour deux arbres à 75 sommets (aléatoires mais isomorphes), moins de 20 tests suffisent. .... -check sub H .... Teste si le graphe généré G est un sous-graphe couvrant de H (donc avec le même nombre de sommets). S'ils ont le même nombre d'arêtes, le test est équivalent à l'isomorphisme. Le nombre de tests est le nombre total de fois où deux graphes sont comparés. On peut tester si H est Hamiltonien en prennant pour G un cycle. .... Tester un cycle de longueur 12 dans une grille 3x4 prend jusqu'à environ 32 millions de tests (parfois bien moins), soit < 10" environ. .... -check minor H .... Teste si le graphe G généré contient H comme mineur. Les graphes peuvent être non connexes. S'ils ont le même nombre de sommets le test est équivalent à celui du sous-graphe (voir -check sub). Dans le cas positif, un modèle de H dans G est fourni. .... Le principe consiste à contracter des arêtes de G, de toutes les manières possibles, et à tester si H est un sous-graphe du graphe contracté. Le nombre de tests affichés est le nombre de contractions plus le nombre total de tests réalisés par les tests de sous-graphe. Pour H=K_4 il est préférable d'utiliser -check twdeg qui donne 2 ssi le graphe ne contient pas K_4 comme mineur. .... -check twdeg .... Donne une borne supérieure et inférieure sur la treewidth du graphe. Pour la borne supérieure, on utilise l'heuristique du sommet de degré minimum que l'on supprime et dont on complète le voisinage par une clique. En cas d'égalité (même degré) on sélectionne le sommet dont il faut rajouter le moins d'arêtes. La borne inférieure qui est donnée provient de la dégénérescence. La treewidth est exacte si 0,1 ou 2 est retournée. L'algorithme est en O(n^2). .... -check tw .... Calcule la treewidth du graphe en analysant tous les ordres d'éliminations. La complexité est donc en n!. Il ne faut l'utiliser que si le nombre de sommets est < 12 (Ex: gengraph random 12 .5 -check tw donne 5 en environ 750 millions de tests). Parfois, l'utilisation de -permute peut accélérer le traitement, car partir d'un ordre d'élimination déjà bon permet d'éliminer rapidement beaucoup d'ordres possibles. .... -check maincc .... Affiche, dans le mode standard seulement, le graphe correspondant à la composante connexe la plus grande en nombre de sommets. Les sommets sont éventuellement renumérotés. En principe cette option s'utilise avec -format no, sinon le graphe initial est aussi affiché. Avec "-format no | ./gengraph load -" on peut alors afficher le graphe dans le format souhaité, et ajouter aussi -visu. ....-filter family[:range] [not] test [parameters] .... Affiche les graphes d'une famille pour lesquels le test est vrai (ou faux si "test" est précédé de "not"). Le paramètre "family" est un nom de fichier ou "-" pour l'entrée standard. Il contient la famille de graphes (ou un graphe seul) au format standard. L'affichage est influencé par l'option -width qui doit être placée avant -filter. La variante "family:range" permet de sélectionner les graphes de la famille dont les identifiants sont spécifiés par "range", un ensemble de valeurs selon le format "value" décrit ci-après. La variante "-:range" est possible. .... Dans la suite, la présence de "value" dans les paramètres d'une option représente un ensemble de valeurs possibles. Par exemple, -filter F vertex '>5' filtre les graphes de F comportant plus de 5 sommets. De manière générale, "value" est une suite d'intervalles d'entiers sépararés par des "," chaque intervalle étant codé comme suit: .... x ........ valeur supérieure à x x ou =x ... valeur égale à x x-y ....... valeur dans l'intervalle [x,y] t ......... toujours vrai (intervalle infini) p ......... affiche la valeur plutôt que le graphe .... Ex1: -filter F vertex '5,7-13,>100' Ex2: -filter F vertex '5-10,p' Ex3: -filter F edge p Ex4: -filter F id 5,7 .... L'exemple 1 filtre les graphes ayant n sommets avec soit n=5, soit n dans [7,13], ou soit n>100. L'exemple 2 affiche le nombre de sommets des graphes ayant entre 5 et 10 sommets. L'exemple 3 affiche le nombre d'arêtes de chaque graphe. L'exemple 4 affiche les graphes d'identifant 5 et 7 de la famille. .... Pour avoir le maximum/minimum de "value" faire: ... -filter ... p | grep '^\[' | sort -rnk 3 | head ... -filter ... p | grep '^\[' | sort -nk 3 | head .... Si "value" contient le symbole > ou < il est alors préférable de mettre des quotes ('>14' par exemple) pour que la commande soit correctement interprétée par le shell. .... La différence principale avec -check est que le résultat de -filter est non verbeux alors que -check, qui ne s'applique pas a priori sur des familles de graphes mais sur un graphe seul, donne des explications sur l'exécution de l'algorithme. Avec -check l'algorithme s'applique au graphe généré, alors qu'avec -filter c'est toujours à partir d'un fichier. .... -filter F id value .... Filtre les graphes de F dont l'identifiant est déterminé par value. Cela permet d'extraire un ou plusieurs graphes donnés. C'est équivalent à "-filter F:value all". .... -filter F rename shift .... Affiche tous les graphes de la famille en renumérotant les graphes à partir de l'entier "shift". .... -filter F vertex value .... Filtre les graphes de F d'un nombre de sommets déterminé par value. .... -filter F edge value -filter F edges value .... Filtre les graphes de F d'un nombre d'arêtes déterminé par value. .... -filter F all (= vertex >0) .... Affiche tous les graphes de F ce qui permet en particulier de les compter. .... -filter F1 minus F2 .... Affiche F1\F2, c'est-à-dire tous les graphes de F1 qui ne sont pas isomorphes F2 (si F2 est un graphe) ou à l'un des graphes F2 (dans le cas d'une famille). .... -filter F1 minus-id F2 .... Comme "minus" mais concerne les identifiants: supprime de F1 les graphes dont l'identifiant existe dans F2 (qui peut être un graphe ou une famille de graphe). La complexité est environ (|F1|+|F2|)log|F2|, alors que pour "minus" elle est en |F1|*|F2|*T où T est le temps pour décider si deux graphes pris dans F1 et F2 sont isomorphes. .... -filter F minor[-inv] H .... Filtre les graphes de F contenant H comme mineur. La variante minor-inv filtre les graphes de F qui sont mineurs de H. Si H=K_4, il est préférable d'utiliser -filter tw2. .... -filter F sub[-inv] H .... Filtre les graphes de F contenant H comme sous-graphe, chaque graphe de F devant avoir le même nombre de sommets que H. La variante sub-inv filtre les graphes de F qui sont un sur-graphe de H. .... -filter F isub[-inv] H .... Filtre les graphes de F contenant H comme sous-graphe induit. La variante isub-inv filtre les graphes de F qui sont sous-graphes induits de H. .... -filter F iso H .... Filtre les graphes de F isomorphes à H. .... -filter F degenerate value .... Filtre les graphes de F de dégénérescence déterminée par value. .... -filter F forest (= degenerate <2) .... Filtre les graphes de F qui sont des forêts. .... -filter F degmax/degmin value .... Filtre les graphes de F de degré maximum (ou minimum) déterminé par value. .... -filter F deg value .... Filtre les graphes de F où tous les sommets ont un degré déterminé par value. Ainsi -filter deg 4-7 filtre les graphes avec un degré minimum au moins 4 et un degré maximum au plus 7. .... -filter F gcolor value .... Filtre les graphes de F dont le nombre de couleurs obtenu selon l'heuristique du degré minimum est déterminé par value. .... -filter F bipartite (= gcolor <3) .... Filtre les graphes de F qui sont bipartis. .... -filter F component value .... Filtre les graphes de F dont le nombre de composantes connexes est déterminé par value. .... -filter F connected (= component 1) .... Filtre les graphes de F qui sont connexes. .... -filter F biconnected .... Filtre les graphes de F qui sont 2-connexes. Un graphe G est k-connexe s'il n'y a pas d'ensemble avec F; ./gengraph clique 5 >> F echo "[1]" >> F; ./gengraph wagner >> F echo "[2]" >> F; ./gengraph prism 5 >> F echo "[3]" >> F; ./gengraph hajos >> F ; echo "0-1-2-0" >> F cat G |./gengraph -filter F minor-inv - -format no .... -filter F tw2 .... Affiche les graphes de treewidth <= 2. L'algorithme est en O(n^2). Ce test peut être utilisé pour tester (plus rapidement qu'avec -filter minor) les graphes sans mineur K_4. .... -filter F hyperbol value .... Filtre les graphes de F selon leur hyperbolicité. Il s'agit de la valeur (entière) maximum, surtout des quadruplets de sommets {u,v,x,y}, de la différence des deux plus grandes sommes parmi les sommes de distance: uv+xy, ux+vy et uy+vx. La complexité est en O(n^4). ....-format type .... Spécifie le format de sortie. Il est préférable d'utiliser cette option en dernier sur la ligne de commande. Les valeurs possibles pour "type" sont: .... - standard: format standard (liste d'arêtes), c'est le plus compact. - list: liste d'adjacence. - matrix: matrice d'adjacence. - smatrix: matrice supérieure, diagonale comprise. - dot: format de GraphViz qui est très proche du format standard. - dot: dessine le graphe avec GraphViz et converti au format . - xy: positions X,Y qui ont été utilisées pour le graphe géométrique. - no: n'affiche rien, à utiliser en combinaison avec -header ou -check. .... Les formats matrix/smatrix/list nécessitent de stocker le graphe en mémoire, donc nécessite un espace en O(n+m), alors que le graphe est généré à la volée pour les formats standard ou dot. Les formats pour dot les plus utilisés sont: pdf, fig, svg, ps, jpg, gif, png (voir man dot). .... L'option -format dot est équivalent à "-format dot | dot -T ...". Elle doit donc être utilisée en dernier sur la ligne de commande. Le filtre dot utilisé pour dessiner le graphe peut être spécifié par l'option -dotfilter. L'affichage des noms de sommets est contrôlé par l'option -label. .... Remarque: les positions affichées dans le format dot ([pos="..."]) diffèrent d'un facteur proportionnel à sqrt(n) par rapport aux positions originales du graphe (qui peuvent être affichées par -format xy). Ce facteur permet de garder une taille raisonable pour les sommets car sous dot les sommets ont une taille fixe minimale. ....-vcolor option [parameters] .... Ces options permettent de modifier la couleur des sommets. Ces options n'ont d'effets qu'avec le format dot (et ses variantes comme -visu). Par défaut les sommets sont des points noirs. Notez que les attributs par défaut des sommets (couleurs, formes, etc.) peuvent être modifiés directement par dot (voir l'option -N de dot). Cependant l'option -vcolor permet d'individualiser la couleur d'un sommet, en fonction de son degré par exemple. Il peut avoir plusieurs options -vcolor sur la ligne de commande. .... -vcolor deg[r] .... La couleur dépend du degré du sommet (deg) ou du rang du degré du sommet (degr). Ainsi, les sommets de plus petit degré obtiennent la première couleur de la palette, les sommets de plus grand degré la dernière couleur de la palette, et les autres sommets une couleur intermédiaire de la palette. Donc une seule couleur est utilisée si le graphe est régulier. .... -vcolor degm .... Effectue une coloration propre (deux sommets voisins ont des couleurs différentes) suivant l'heuristique du degré minimum: récursivement, le sommet de degré minimum obtient la plus petite couleur qui n'est pas utilisée par ses voisins. Cela donne des colorations avec assez peu de couleurs pour les graphes de faible arboricité (planaire, tw, pw, kout, ...) ou de faible degré. Avec cette technique, les graphes bipartis (tree, crown, ...) sont coloriés avec deux couleurs. Cette option nécessite un espace et un temps en O(n+m). .... -vcolor randg .... Effectue une coloration propre en utilisant un algorithme glouton sur un ordre aléatoire des sommets: récursivement, le sommet d'indice i obtient la plus petite couleur qui n'est pas utilisée par ses voisins d'indice j g.pdf". ....-dotfilter filter .... Spécifie le filtre de GraphViz, c'est-à-dire l'algorithme de dessin utilisé par dot. Par défaut, le filtre est "neato". Les filtres principaux sont: dot, neato, twopi, circo, fdp, sfdp, ... Faire "dot -K ." pour afficher les filtres disponibles. ....-pos b .... Active (b=1) ou désactive (b=0) la génération des positions des sommets pour le format dot. Cela sert à indiquer à l'algorithme de dessin dot de respecter les coordonnées des sommets. L'option par défaut est -pos 0, mais cette option est activée pour tous les graphes géométriques (udg, gabriel, thetagone ...). ....-label b .... Active (b>0) ou désactive (b=0) l'affichage du nom des sommets pour les formats dot et standard. Si b=1, il s'agit du nom original du sommet. Cette représentation n'est pas implémentée pour tous les graphes. Par défaut les noms sont les entiers de [0,n[, n nombre de sommets du graphe généré. L'option -label 1 -visu permet alors de dessiner le nom des sommets, car par défaut les noms ne sont pas dessinés (b=0). L'option -label 2 -visu force l'affichage des noms sous-forme d'entiers. Comme cette option influence l'option -format dot, l'option -label doit être placée avant -format. L'option -label 1 annule l'option -permute, mais pas -label 2. Pour avoir la correspondance entre l'indice et le nom du sommet faire simplement: ... -label 1 -format dot | grep label ....-norm l .... Fixe la norme pour l'adjacence de certains graphes géométriques (udg, gabriel, rng, nng). Les valeurs possibles pour l sont 1,2,3,4 pour respectivement les normes L_1, L_2, L_max, L_min. La norme par défaut est L_2, la norme euclidienne. ....-xy option [parameters] .... Ces options contrôlent la façon dont sont générées les coordonnées des sommets d'un graphe géométrique. Par défaut les positions sont tirées aléatoirement uniformément dans le carré [0,1[ x [0,1[, mais cela peut être changé. Notez bien que, même si c'est très improbable, deux sommets peuvent avoir les mêmes positions (voir l'option -xy unique). .... -xy load file .... Charge les positions à partir du fichier "file" ou de l'entrée standard si file=-. Cela permet de tester les adjacences d'un graphe géométrique à partir de positions pré-déterminées. .... Ex: gengraph gabriel 10 -xy load file.pos .... Le nombre de sommets du graphe est déterminé par le fichier et non pas par les paramètres du graphe. Cette option n'a d'effet que pour les graphes géométriques. La structure du fichier au format texte doit être: .... n x_1 y_1 x_2 y_2 ... x_n y_n .... où n est le nombre de positions. Les positions x_i y_i ne sont pas forcément dans l'intervalle [0,1[. Notez qu'avec l'option -format xy, il est possible d'effectuer la transformation d'un fichier de positions. L'exemple suivant normalise les coordonnées du fichier g.pos dans le carré unité: gengraph -xy load g.pos -xy scale 1 1 -format xy .... -xy scale a b .... Effectue un redimensionement des positions de sorte quelles se situent dans le rectangle [0,a] x [0,b]. En prenant a=b=1, les coordonnées seront renormalisées dans le carré [0,1[ x [0,1[. Cette opération est effectuée juste avant la génération des arêtes, en particulier après avoir effectué l'opération -xy noise (voir ci-après) et/ou -xy load. Les positions sont recadrées pour laisser une fine bande vide sur le bord du rectangle. Cette bande a une largeur ~ a/sqrt(n) et une hauteur ~ b/sqrt(n) où n est le nombre de points. .... -xy noise r p .... Effectue une pertubation aléatoire sur les positions des sommets. Le déplacement de chaque sommet est effectué dans sa boule de rayon r (pour p>0) selon une loi en puissance de paramètre p. Prendre p=1 pour une pertubation uniforme dans cette boule, p>1 pour une concentration des valeurs vers le centre et p<1 pour un écartement du centre. Les valeurs <0 de p donne des écartements au delà du rayon r. .... Plus précisément, une direction (angle de 0 à 2pi) est choisie aléatoirement uniformément, puis, selon cette direction, un décalage aléatoire est effectué selon une loi en puissance: si x est uniforme dans [0,1[, le décalage sera d(x)=r*x^p. Après cette opération, il est possible que les points ne soient plus dans le rectangle d'origine, ce qui peut bien sûr être corrigé par -xy scale. .... -xy seed k p .... Fixe k graines pour la génération aléatoire des coordonnées. Les graines sont choisies uniformément dans le carré [0,1[ x [0,1[ puis centrées par rapport à leur barycentre. Chaque point est alors tiré aléatoirement autour d'une des graînes et à une distance variant selon une loi en puissance de paramètre p avec un rayon r ~ sqrt(ln(k)/k) (voir "noise"). .... -xy permutation .... Génère les points correspondant à une permutation P aléatoire uniforme. Le points i à aura pour positions (i,P(i)). .... -xy round p .... Arrondi les coordonnées à 10^-p près. Il faut p entier <10. Donc p=0 arrondi à l'entier le plus proche. Cet opérateur est appliqué après "scale". Il sert aussi à préciser le nombre de décimales à afficher pour l'option "-format xy" (par défaut p=6). Par exemple, la combinaison -xy scale 100 100 -xy round -1 permet d'avoir des coordonnées multiples de 10. .... -xy unique .... Supprime les sommets en double, correspondant aux mêmes positions. Cela peut être utile lorsqu'on utilise -xy round. Cette opération est appliquée après toutes les autres, notamment après scale et round. Ceci est réalisé en temps O(nlogn). GRAPHES Deux types de graphes sont possibles : les graphes de base et les graphes composés. Ces derniers sont obtenus en paramétrant un graphe de base. Une catégorie importante de graphes sont les graphes géométriques (qui peuvent être composé ou de base). L'adjacence est déterminée par les coordonnées associées aux sommets. De nombreuses options s'y refèrent. Ils activent tous par défaut l'option -pos. Les graphes orientés activent quant à eux tous l'option -directed. 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 sont toujours Hamiltonien. Ils peuvent être vus comme des anneaux de cordes irréguliers. Ils sont construits à 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. Cette fonction permet aussi de construire des graphes avec des sommets de degré 4 comme "cage 8 2 0 2" (voir aussi le graphe de Chvátal) ou avec des sommets de degré 2 comme "cage 4 2 2 0". ....arboricity n k .... Graphe d'arboricité k aléatoire à n sommets. Ce graphe est composé de l'union de k arbres aléatoires. Il est donc toujours connexe. 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, 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 aléatoire. ....rarytree n b .... Arbre b-aire plan aléatoire uniforme à n noeuds internes. Il possède bn+1 sommets. La racine est de degré b, les autres sommets sont de degré b+1 (soit b fils) ou 1 (=feuille). Si b=1, le graphe est une union de chemin. Si n=1, alors le graphe est une étoile à b feuilles. ....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. ....kpage n k .... Graphe k-pages aléatoire. Par définition on peut positionner les sommets en cercle, dessiner les arêtes comme des segments de droites, et colorier les arêtes en k couleurs de façon à ce que les arêtes de chaque couleur induisent un dessin de graphe planaire-extérieur. Les graphes 1-page sont les graphes planaires-extérieurs, et les 2-pages sont les sous-graphes de graphes planaires hamiltoniens. .... Ces graphes sont construits par le processus aléatoire suivant. On génère k graphes planaires-extérieurs aléatoires uniformes connexes à n sommets (plan et enraciné) grâce à une bijection avec les arbres plans enracinés dont tous les sommets, sauf ceux de la dernière branche, sont bicolorés. On fait ensuite l'union de ces k graphes en choisissant aléatoirement la racine des arbres, sauf celui du premier planaire-extérieur (ce qui correspond à une permutation circulaire des sommets sur la face extérieure). ....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[ (il faut donc 0<=k<=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. ....gpetersen n r .... Graphe de Petersen généralisé P(n,r), r2 ou n<>5 (modulo 6). P(n,r) est isomorphe à P(n,(n-2r+3)/2)). P(4,1) est le cube, P(5,2) le graphe de Petersen, P(6,2) le graphe de Dürer, P(8,2) le graphe de Möbius-Kantor, P(10,2) le dodécahèdre, P(10,3) le graphe de Desargues, P(12,5) le graphe de Nauru, P(n,1) un prisme. ....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 i et j appartiennent à des parts différentes. ....ggosset p k d_1 v_1 ... d_k v_k .... Graphe de Gosset généralisé. Les sommets sont tous les vecteurs entiers de dimension d = d_1 + ... + d_k dont les coordonnées comprennent, pour i=1...k, exactement d_i fois la valeur v_i. Il existe une arête entre les vecteurs u et v si et seulement le produit scalaire entre u et v vaut l'entier p. Des valeurs intéressantes sont par exemple: 1 2 2 -1 2 0, 8 2 2 3 6 -1, ... ....crown n .... Graphe biparti à 2n sommets où le i-ème sommet de la première partie est voisin au j-ème sommet de la seconde partie ssi i<>j. Pour n=3, il s'agit du cycle à 6 sommets, pour n=4, il s'agit du cube (à 8 sommets). ....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 est adjacent à 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 est le graphe lui même. ....mycielski k .... Graphe de Mycielski de paramètre (nombre chromatique) k. C'est un graphe sans triangle, k-1 (sommets) connexe, de nombre chromatique k. Le premier graphe de la série est M2 = K2, puis on trouve M3=C5, M4 est le graphe de Grötzsch à 11 sommmets. ....wheel n .... La roue à n sommets. Graphe composé d'un cycle à n sommets et d'un sommet connecté à tous les autres. ....windmill n .... Graphe composé de n cycles de longueur trois ayant un sommet commun. ....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 uniformément parmi les sommets dont le numéro est < i. La valeur d est choisie aléatoirement uniformément 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. ....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 planaire cubic à 46 sommets qui n'est pas Hamiltonien. ....theta0 .... Graphe Theta_0. C'est un graphe à 7 sommets série-parallèle obtenu à partir d'un cycle de longueur 6 et en connectant deux sommets antipodaux par un chemin de longueur 2. C'est un "unit distance graph". ....fritsch .... Graphe de Fritsch. Il est planaire maximal à 9 sommets qui peut être vu comme un graphe de Hajós dans un triangle. C'est, avec le graphe de Soifer, le plus petit contre-exemple à la procédure de Kempe pour la 4-coloration. ....soifer .... Graphe de Soifer. Il est planaire maximal à 9 sommets. C'est, avec le graphe de Fritsch, le plus petit contre-exemple à la procédure de Kempe pour la 4-coloration. ....poussin .... Graphe de Poussin. Il est planaire maximal à 15 sommets. C'est un contre-exemple à la procédure de Kempe pour la 4-coloration. L'option -vcolor degm donne 5 couleurs. ....headwood4 .... Graphe de Headwood pour la conjecture des 4 couleurs, contre exemple de la preuve de Kempe. Il est planaire maximal avec 25 sommets, est de nombre chromatique 4, de diamètre 5, de rayon 3 et Hamiltonien. L'option -vcolor degm donne 5 couleurs. ....errara .... Graphe d'Errara. Il est planaire maximal à 17 sommets. C'est un contre-exemple à la procédure de Kempe pour la 4-coloration. ....kittell .... Graphe de Kittell. Il est planaire maximal à 23 sommets. C'est un contre-exemple à la procédure de Kempe pour la 4-coloration. ....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é au plus 4. ....line-graph n k .... Line-graphe aléatoire à n sommets et de paramètre k, entier >0. Plus k est petit, plus le graphe est dense, le nombre d'arêtes étant proportionnel à (n/k)^2. Si k=1, il s'agit d'une clique à n sommets. Ces graphes sont obtenus en choisissant, pour chaque sommet, deux couleurs parmi {1,...,k}, et deux sommets sont adjacents ssi ils possèdent la même couleur. Ces graphes sont claw-free (sans K_{1,3} induit). Comme les graphes claw-free, les line-graphes connexes avec un nombre pair de sommets possède toujours un couplage parfait. On rappel qu'un graphe G est le line-graphe d'un graphe H si les sommets de G correspondent aux arêtes de H et où deux sommets de G sont adjacents ssi les arêtes correspondantes dans H sont incidentes. Pour parle parfois de graphe adjoint. ....debruijn d b .... Graphe de De Bruijn de dimension d et de base b. Il a b^d sommets qui sont tous les mots de d lettres sur un alphabet de b lettres. Le sommet (x_1,...,x_d) est voisin des sommets (x_2,...,x_d,*). Ce graphe est Hamiltonien, de diamètre d et le degré de chaque sommet est 2b, 2b-1 ou 2b-2. Pour d=3 et b=2, le graphe est planaire. ....kautz d b .... Graphe de Kautz de dimension d et de base b. Il a b*(b-1)^(d-1) sommets qui sont tous les mots de d lettres sur un alphabet de b lettres avec la contrainte que deux lettres consécutives doivent être différentes. L'adjacence est celle du graphe de De Bruijn. C'est donc un sous-graphe. Il est Hamiltonien, de diamètre d et le degré de chaque sommet est 2b-2 ou 2b-3. Pour d=b=3 le graphe est planaire. ....linial n t .... Neighborhood graph des cycles introduit par Linial. C'est le graphe de voisinage à distance t d'un cycle orienté à n sommets ayant des identifiants uniques. Il faut n>2t. Le nombre chromatique de ce graphe est k ssi il existe un algorithme distribué qui en temps t peut colorier en k couleurs tout cycle à n sommets orienté avec une orientation et ayant des identifiants uniques. Les sommets sont les (2t+1)-uplets (x_1,...,x_{2t+1}) d'entiers tous distincts de [0,n[. Les sommets (x_1,...,x_{2t+1}) et (y_1,...,y_{2t+1}) sont adjacents ssi (x_1,...,x_{2t}) = (y_2,...,y_{2t+1}). C'est un sous-graphe induit du graphe De Bruijn et de linialc n t. Le nombre de sommets est m(m-1)...(m-2t). Certaines propriétés se déduisent du graphe linialc n t. ....linialc m t .... Neighborhood graph des cycles colorés. Il s'agit d'une variante du graphe linial n t. La différence est les sommets du cycle n'ont pas forcément des identitiés uniques, mais seulement une une m-coloration, avec m<=n. L'adjacence est identique, mais les sommets sont les (2t+1)-uplets (x_1,...,x_{2t+1}) d'entiers de [0,m[ tels que x_i<>x_{i+1}. Le graphe linial m t est donc un sous-graphe induit de linialc m t qui est lui-même un sous-graphe induit du graphe de De Bruijn. Le nombre de sommets est m(m-1)^{2t} et son degré maximum est 2(m-1). La taille de la clique maximum est 3 pour si m>2 et t>1. Le nombre chromatique de ce graphe est 3 pour m=4, 4 pour 5<=m<=24. Pour 25<=m<=70 c'est au moins 4 et au plus 5, la valeur exacte n'étant pas connue. ....pancake n .... Graphe "pancake" de dimension n. Il a n! sommets qui sont les permutations de {1,...,n}. Les sommets x=(x_1,...,x_n) et y=(y_1,...,y_n) sont adjacents s'il existe un indice k tel que y_i=x_i pour tout i>k et si y_i=x_{k-i} pour tout 1<=i<=k. Dit autrement la permutation de y doit être obtenue en retournant un préfixe de x. Le graphe est (n-1)-régulier. Son diamètre qui est linéaire en n n'est pas précisément connu. Les premières valeurs connues, pour n=1...17, sont: 0, 1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 19. Donc les diamètres 2, 6, 12 n'existent pas. ....gpstar n d .... Graphe "permutation star" généralisé de dimension n. Il a n! sommets qui sont les permutations de {1,...,n}. Deux sommets sont adjacents si leurs permutations diffèrent par d positions. C'est un graphe régulier. ....pstar n .... Graphe "permutation star" de dimension n. Il a n! sommets qui sont les permutations de {1,...,n}. Deux sommets sont adjacents si une permutation est obtenue en échangeant le premier élément avec un autre. Le graphe est (n-1)-régulier. Le graphe est biparti et de diamètre floor(3(n-1)/2). C'est un sous-graphe induit d'un gpstar n 1. ....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 par un cycle de longueur 6. Il possède (p+1)*(2p+2)-2 sommets et est de degré maximum 3. Sont dual est le graphe whexagon. ....whexagon p q .... Comme le graphe hexagon p q sauf que chaque hexagone est remplacé par une roue de taille 6 (chaque hexagone possède un sommet connecté à ses 6 sommets). C'est le dual de l'hexagone. Il possède pq sommets de plus que l'hexagone p q. ....hanoi n b .... Graphe de Hanoï généralisé, le graphe classique est obtenu avec b=3. Il est planaire avec b^n sommets et est défini de manière récursive. Le niveau n est obtenu en faisant b copies du niveau n-1 qui sont connectés comme un cycle par une arête, le niveau 0 étant le graphe à un sommet. Il faut b>1. Lorsque n=2, on obtient un sorte de soleil. ....sierpinski n b .... Graphe de Sierpiński généralisé, le graphe classique, le triangle Sierpiński qui est planaire, est obtenu avec b=3. Il a ((b-2)*b^n+b)/(b-1) sommets et est défini de manière récursive. Le niveau n est obtenu en faisant b copies du niveau n-1 qui sont connectés comme un cycle, le niveau 1 étant un cycle de b sommets. Il faut b>2 et n>0. A la différence du graphe d'Hanoï, les arêtes du cycle sont contractées. Le graphe de Hajós est obtenu avec n=2 et b=3. ....moser .... Graphe "Moser spindle" découvert par les frères Moser. C'est un "unit distance graph" du plan (deux points sont adjacents s'ils sont à distance exactement 1) de nombre chromatique 4. Il est planaire et possède 7 sommets. On ne connaît pas d'unit distance graphe avec un nombre chromatique supérieur. ....markstrom .... Graphe de Markström. Il est cubic planaire à 24 sommets. Il n'a pas de cycle de longueur 4 et 8. ....robertson .... Graphe de Robertson. C'est le plus petit graphe 4-régulier de maille 5. Il a 19 sommets, est 3-coloriable et de diamètre 3. ....wiener_araya .... Graphe de Wiener-Araya. C'est le plus petit graphe hypo-hamiltonien connu (découvert en 2009), c'est-à-dire qu'il n'est pas Hamiltonien, alors la suppression de n'importe quel sommet le rend Hamiltonien. Il est planaire, possède 42 sommets et 67 arêtes. ....clebsch n .... Graphe de Clebsch d'ordre n. Il est construit à partir d'un hypercube de dimension n en ajoutant des arêtes entres les sommets opposés, c'est-à-dire à distance n. Le graphe classique de Clebsch est réalisé pour n=4 dont le diamètre est deux. ....flower_snark n .... Graphe cubic à 4n sommets construit de la manière suivante: 1) on part de n étoiles disjointes à 3 feuilles, la i-ème ayant pour feuilles les sommets notés u_i,v_i,w_i, i=1..n; 2) pour chaque x=u,v ou w, x_1-x_2-...-x_n induit un chemin; et 2) sont adjacents: u_0-u_n, v_0-w_n et w_0-v_n. Pour n>1, ces graphes sont non planaires, non hamiltoniens, 3-coloriables et de maille au plus 6. ....udg n r .... Graphe géométrique aléatoire (random geometric graph) sur n points du carré [0,1[ x [0,1[. Deux sommets sont adjacents si leurs points sont à distance <= r. Il s'agit de la distance selon la norme L_2 (par défaut), mais cela peut être changée par l'option -norm. Le graphe devient connexe avec grande probabilité lorsque r=rc ~ sqrt(ln(n)/n). Si r<0, alors le rayon est initialisé à rc. Un UDG (unit disk graph) est normalement un graphe d'intersection de disques fermés de rayon 1. ....gabriel n .... Graphe de Gabriel. Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[ x [0,1[. Les points i et j sont adjacents ssi le plus petit disque (voir -norm) passant par i et j ne contient aucun autre point. Ce graphe est planaire et connexe. C'est un sous-graphe du graphe de Delaunay d'étirement non borné. ....rng n .... Graphe du proche voisinage (Relative Neighborhood Graph). Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[ x [0,1[. Les points i et j sont adjacents ssi il n'existe aucun point k tel que max(d(k,i),d(k,j)) < d(i,j) où d est la distance (L_2 par défaut, voir -norm). Dit autrement, la "lune" définie par i et j doit être vide. Ce graphe est planaire et connexe. C'est un sous-graphe du graphe de Gabriel. ....nng n .... Graphe du plus proche voisin (Nearest Neighbor Graph). Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[ x [0,1[. Le point i est connecté au plus proche autre point (par défaut selon la norme L_2, voir -norm). Ce graphe est une forêt couvrante du graphe rng de degré au plus 6 (si la norme est L_2). ....thetagone n p k v .... Graphe géométrique défini à partir d'un ensemble de n points du carré [0,1[ x [0,1[. En général le graphe est planaire et connexe avec des faces internes de longueur au plus p (pour k diviseur de p et v=1). On peut interpréter les paramètres comme suit: p le nombre de cotés d'un polygone régulier, k le nombre d'axes (ou de direction), et v le cône de visibilité décrit par un réel entre 0 et 1. Toute valeur de p<3 est interprétée comme une valeur infinie, et le polygone régulier correspondant interprété comme un cercle. L'adjacence entre une paire de sommet est déterminée en temps O(k*n). .... Plus formellement, pour tous points u et v, et entier i, on note P_i(u,v) le plus petit p-gone (polygone régulier à p cotés) passant par u et v dont u est un sommet, et dont le vecteur allant de u vers son centre forme un angle de i*2pi/k avec l'axe des abscisses, intersecté avec un cône de sommet u et d'angle v*(p-2)*pi/p (v*pi si p est infini) et dont la bissectrice passe par le centre du p-gone. Alors, u est voisin de v s'il un existe au moins un entier i dans [0,k[ tel que l'intérieur de P_i(u,v) est vide. La distance entre u et le centre du p-gone définit alors une de distance (non symétrique) de u à v. .... Si v=1 (visibilité maximale), P_i est précisément un p-gone. Si v=0 (visibilité minimale), P_i est l'axe d'angle i*2pi/k pour un entier i. Si v=.5, P_i est un cône formant un angle égale à 50% de l'angle défini par deux cotés consécutifs du p-gone, angle vallant (p-2)pi/p. Si v=2p/((p-2)k) (ou simplement 2/k si p est infini) alors la visibilité correspond à un cône d'angle 2pi/k, l'angle entre deux axes. Comme il faut v<=1, cela implique que k>=2p/(p-2) (k>=2 si p infini). On retrouve le Theta_k-Graph pour chaque k>=6 en prenant p=3 et v=6/k, le demi-Theta-Graph pour tout k>=3 en prenant p=3 et v=3/k, le Yao_k-Graph pour chaque k>=2 en prenant p=0 (infini) et v=2/k, et la triangulation de Delaunay si p=0 (infini), k très grand et v=1. En fait, ce n'est pas tout-à-fait le graph Yao_k, pour cela il faudrait que u soit le centre du polygone (c'est-à-dire du cercle). ....rplg n t .... Random Power-Law Graph. Graphe à n sommets où les degrés des sommets suivent une loi de puissance. L'espérance du degré du sommet i=0...n-1 est (n/(i+1))^(1/(t-1)). En général il faut prendre t dans ]2,3[, la valeur communément observée pour le réseau Internet étant t=2.1. ....load file[:range] .... Graphe défini à partir du fichier "file" ou de l'entrée standard si file vaut "-". Si "file" est une famille de graphes, alors il est possible la variante "file:range" permettant de préciser l'identifiant du graphe (sinon le premier graphe est chargé). Le graphe (ou la famille) doit être au format standard, les sommets numérotés par des entiers positifs. Les caractères qui ne sont pas des chiffres ou des arêtes ("-") sont ignorés. Ceux situés sur une ligne après // sont ignorés, ce qui permet de mettre des commentaires. Le temps de chargement et l'espace de stockage sont en O(n+m). Notez que la suite d'options "load file -format ..." permet de convertir "file" au format souhaité. Ce graphe active l'option -directed si le file correspond à un graphe est orienté, et donc -undirected n'a pas d'effet dans ce cas. .... Pour savoir comment le fichier est chargé en mémoire, lisez les quelques lignes de la fonction File2List du code source avec: sed -n '/^list [*]File2List(/,/^}$/p' gengraph.c GRAPHES ORIENTES : ....aqua n c_1 ... c_n .... Graphe orienté dont les sommets sont les suites de n entiers positifs dont la somme fait c_1 et dont le i-ème élément est au plus c_i. Cela peut être interprété comme les façons de répartir un liquide (en quantité c_1) dans n récipients de capacité c_1 ... c_n. Il y a un arc entre u->v s'il existe i et j tels que le récipient c_i de u a été versé dans le récipient c_j de v (ou inversement de c_j vers c_i). 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}. ....claw (= rpartite 2 1 3) .... Graphe biparti complet K_{1,3}. ....star n (= rpartite 2 1 n) .... Arbre (étoile) à n feuilles et de profondeur 1. ....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. ....caterpillar n (= grid 1 n-r -star r, r=random()%n) .... Arbre à n sommets dont les sommets internes (de degré > 1) induisent un chemin. Il est obtenu à partir d'un chemin de longueur n-r (où r est un nombre aléatoire entre 0 et n-1) et en appliquant l'option -star r. Pour des raisons techniques, l'option -seed, si elle est utilisée, doit être placée avant caterpillar. ....outerplanar n (= kpage n 1) .... Graphe planaire extérieur aléatoire 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. ....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. ....sunlet n (= grid 1 -n -star -1) .... Cycle à n sommets avec un sommet pendant à chacun d'eux. Un sunlet 3 est parfois appelé "net graph". ....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 (crossing number) est 2. ....tietze (= flower_snark 3) .... Graphe de Tietze. Il est cubic avec 12 sommets. Il possède un chemin hamiltonien, mais pas de cycle. Il peut être plongé sur un ruban de Möbius, a un diamètre et une maille de 3. Il peut être obtenu à partir du graphe de Petersen en appliquant une opération Y-Delta. ....mobius-kantor (= gpetersen 8 2) .... Graphe de Möbius-Kantor. Graphe cubic à 16 sommets de genre 1. Il est Hamiltonien, de diamètre 4 et de maille 6. ....dodeca (= gpetersen 10 2) .... Dodécahèdre: graphe planaire cubic à 20 sommets. Il possède 30 arêtes et 12 faces qui sont des pentagones. C'est le dual de l'icosahèdre. ....desargues (= gpetersen 10 3) .... Graphe de Desargues. Il est cubic à 20 sommets. Il est Hamiltonien, de diamètre 5 et de maille 6. ....durer (= gpetersen 6 2) .... Graphe de Dürer. Graphe cubic planaire à 12 sommets de diamètre 4 et de maille 3. Il peut être vu comme un cube avec deux sommets opposés tronqués. ....prism n (= gpetersen n 1) .... Prisme, c'est-à-dire le produit cartésien d'un cycle à n sommets et d'un chemin à deux sommets. ....cylinder p q (= grid p -q) .... Produit cartésien d'un chemin à p sommets et d'un cycle à q sommets. Cela généralise le prisme (prism n = cylinder n 3). Un cube est un cylinder 2 4. ....nauru (= pstar 4) .... Graphe de Nauru. C'est un graphe cubic à 24 sommets. Il s'agit d'un graphe "permutation star" de dimension 4. C'est aussi un graphe de Petersen généralisé P(12,5). ....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 (crossing number) est 3. ....franklin (= cage 12 2 5 -5) .... Graphe de Franklin. C'est un graphe cubic à 12 sommets, de maille 4 et de diamètre 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. ....tutte-coexter (= cage 30 6 -7 9 13 -13 -9 7) .... 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. C'est un graphe de Levi mais surtout un graphe de Moore, c'est-à-dire un graphe d-régulier de diamètre k dont le nombre de sommets est 1+d*S(d,k) (d=impair) ou 2*S(d,k) (d=pair) avec S(d,k)=sum_{i=0}^(k-1) (d-1)^i. ....gray (= cage 54 6 7 -7 25 -25 13 -13) .... Graphe de Gray. C'est un graphe cubic à 54 sommets qui peut être vu comme le graphe d'incidence entre les sommets d'une grille 3x3x3 et les 27 lignes droites de la grille. Il est Hamiltonien, de diamètre 6, de maille 8, et de genre 7. Il est arête-transitif et régulier sans être sommet-transitif. ....grotzsch (= mycielski 4) .... Graphe de Grötzsch. C'est le plus petit graphe sans triangle de nombre chromatique 4. Il possède 11 sommets et 20 arêtes. Comme le graphe de Chvátal, il est non-planaire de diamètre 2, de maille 4 et Hamiltonien. C'est le graphe de Mycielskian du cycle à 5 sommets. ....hajos (= sierpinski 2 3) .... Graphe de Hajós. Il est composé de trois triangles deux à deux partageant deux sommets. On peut le voir aussi comme un triangle dans un triangle. Il est planaire et possède 6 sommets. C'est un graphe de Sierpinski ou encore le complémentaire d'un "sunlet 3". ....house (= -not grid 1 5) .... Graphe planaire à 5 sommets en forme de maison. C'est le complémentaire d'un chemin à 5 sommets. ....wagner (= ring 8 2 1 4) .... Graphe de Wagner appelé aussi graphe W_8. C'est un graphe cubic à 8 sommets qui n'est pas planaire mais sans K_5. 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. ....cube (= crown 4) .... Hypercube de dimension 3. ....diamond (= cage 4 2 2 0) .... Clique à quatre sommets moins une arête. ....gosset (= ggosset 8 2 2 3 6 -1) .... Graphe de Gosset. Il est 27-régulier avec 56 sommets et 756 arêtes, de diamètre, de rayon et de maille 3. Il est 27-arête-connexe et 27-sommet-connexe. C'est localement un graphe de Schläfli, c'est-à-dire que pour tout sommet le sous-graphe induit par ses voisins est isomorphe au graphe de Schläfli, qui lui-même localement un graphe de Clebsch. ....binary h (= arytree h 2 2) .... Arbre binaire de profondeur h possédant 2^(h+1)-1 sommets. La racine est de degré deux. ....rbinary n (= rarytree 2 n) .... Arbre binaire plan aléatoire uniforme à n noeuds internes. Il possède 2n-1 sommets. ....tw n k (= ktree n k -dele .5) .... Graphe de largeur arborescente au plus k aléatoire à 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. ....td-delaunay n (= thetagone n 3 3 1) .... Triangulation de Delaunay utilisant la distance triangulaire (TD=Triangular Distance). Il s'agit d'un graphe planaire défini à partir d'un ensemble de n points aléatoires du carré [0,1[ x [0,1[. Ce graphe a un étirement de 2 par rapport à la distance euclidienne entre deux sommets du graphe. Ce graphe, introduit par Chew en 1986, est le même que le graphe "demi-theta_6", qui est un "theta-graph" utilisant 3 des 6 cônes. La dissymétrie qui peut apparaître entre le bord droit et gauche du dessin est lié au fait que chaque sommet n'a qu'un seul axe dirigé vers la droite, alors qu'il y en a deux vers la gauche. ....theta n k (= thetagone n 3 k 6/k) .... Theta-graphe à k secteurs réguliers défini à partir d'un ensemble de n points du carré [0,1[ x [0,1[. Les sommets u et v sont adjacents si le projeté de v sur la bissectrice de son secteur est le sommet le plus proche de u. Ce graphe n'est pas planaire en général, mais c'est un spanner du graphe complet euclidien. Le résultat est valide seulement si k>=6. ....dtheta n k (= thetagone n 3 k/2 6/k) .... Demi-Theta-graphe à k secteurs réguliers défini à partir d'un ensemble de n points du carré [0,1[ x [0,1[. La définition est similaire au Theta-graphe excepté que seul 1 secteur sur 2 est considéré. Il faut k pair. Le résultat est valide seulement si k>=6. Pour k=6, ce graphe coïncide avec le graphe td-delaunay. ....yao n k (= thetagone n 0 k 2/k) .... Graphe de Yao à k secteurs réguliers défini à partir d'un ensemble de n points du carré [0,1[ x [0,1[. Les sommets u et v sont adjacents si v est le sommet le plus proche de u (selon la distance euclidienne) de son secteur. Ce graphe n'est pas planaire en général, mais c'est un spanner du graphe complet euclidien. Le résultat est valide seulement si k>=2. En fait, ce n'est pas tout à fait le graphe de Yao (voir thetagone). ..... 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 - nouveau format de sortie: -format dot - nouvelles 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. v1.8 juillet 2010: - nouveaux graphes: chvatal, grotzsch, debruijn, kautz gpstar, pstar, pancake, nauru, star, udg, gpetersen, mobius-kantor, desargues, durer, prism, franklin, gabriel, thetagone, td-delaunay, yao, theta, dtheta - suppression du graphe geo (remplacé par udg) - nouvelles options: -pos, -norm, -label, -dotfilter - nouvelle famille d'options: -xy file/noise/scale/seed - définition plus compacte dodeca (non explicite) - utilisation du générateur random() plutôt que rand(). - correction d'un bug dans "-format standard" qui provoquait une erreur. - correction d'un bug dans kneser pour k=0, n=0 ou k>n/2. - nouveaux formats: -format dot, -format xy - suppression de -dotpdf (qui est maintenant: -format dotpdf) - labeling pour: gpetersen, gpstar, pstar, pancake, interval, permutation v1.9 août 2010: - renome -h en -list - renome -xy file en -xy load - centrage des positions sur le barycentre des graines (-xy seed) - nouvelles options: -star, -visu, -xy round - les graphes peuvent être stockés en mémoire, sous la forme d'une liste d'adjacence grâce à l'option -check. - généralisation de -delv p avec p<0 - nouveaux graphes: caterpillar, hajos, hanoi, sierpinski sunlet, load file - labeling pour: hanoi, sierpinski - aide sur toutes les options (nécessitant au moins un paramètre) et non plus seulement pour les graphes - nouvelle famille d'options: -vcolor deg/degr/pal - correction d'un bug pour l'aide dans le cas de commande préfixe (ex: pal & paley) v2.0 septembre 2010: - nouvelles options: -vcolor degm/list/randg, -xy unique/permutation, -check bfs, -algo iso/sub - l'option -xy round p admet des valeurs négatives pour p. - les options "load file" et "-xy load file" permettent la lecture à partir de l'entrée standard en mettant file="-", la lecture de famille de graphes, et supporte les commentaires. - les formats list/matrix/smatrix utilisent un espace linéaire O(n+m) contre O(n^2) auparavant. - les sommets sur le bord (graphes géométriques) ne sont plus coupés (bounding-box (bb) plus grandes). - nouveaux graphes: kpage, outerplanar n (=kpage n 1), rng, nng fritsch, soifer, gray, hajos (qui avait été définit mais non implémenté !), crown, moser, tietze, flower_snark, markstrom, clebsch, robertson, kittell, rarytree, rbinary, poussin, errara - les graphes de gabriel (et rng,nng) dépendent maintenant de -norm. - "wheel n" a maintenant n+1 sommets, et non plus n. - aide en ligne améliorée avec "?". Ex: gengraph tutte ? / -visu ? - les options -help et ? permettent la recherche d'un mot clef. Ex: gengraph -help planaire / ? arbre - description plus compacte de tutte (et des graphes à partir d'un tableau) - correction d'un bug pour rpartite (qui ne marchait pas) v2.1 octobre 2010: - nouvelles options: -check degenerate/gcolor/edge/dfs/ps1/paths/paths2/iso/sub/minor/isub -filter minor/sub/iso/vertex/edge/degenerate/ps1 -filter degmax/degmin/deg/gcolor/component/radius/girth/diameter -filter cut-vertex/biconnected/isub/all/minor-inv/isub-inv/sub-inv - suppression de -algo iso/sub: l'option -algo est réservée à la mis au point de -check - extension de -label b à b=2 qui force l'affiche des noms sous forme d'entiers même avec -permute. - correction d'un bug pour house (qui ne marchait pas) - nouveau graphe: windmill v2.2 novembre 2010: - gestion des graphes orientés: lecture d'un fichier de graphe (ou d'une famille avec arcs et arêtes) - nouvelles options: -(un)directed, -(no)loop, -check twdeg/tw, -filter tw/id/hyperbol/rename - permet l'affichage de la "value" (p) dans l'option -filter - nouveau graphe: aqua - correction du graphe tutte-coexter et suppression du graphe levi (qui en fait était le graphe de tutte-coexter). - généralisation de l'option "load" à load:id family v2.3 décembre 2010: - nouvelles options: -check ps1bis/edge, -filter ps1bis/tw2 -filter minus/minus-id/unique/connected/bipartite/forest -check ps1ter - remplacement de atof()/atoi() par strtod()/strtol() qui sont plus standards. - remplacement de LONG_MAX par RAND_MAX dans les expressions faisant intervenir random() qui est de type long mais qui est toujours dans [0,2^31[, même si sizeof(long)>4. Il y avait un bug pour les architectures avec sizeof(long)=8. - nouveau graphe: cylinder - suppression de la variante "load:id" au profit de la forme plus générale "file:range" valable pour load, -filter, etc. v2.4 janvier 2011: - correction d'un bug dans -filter minus-id - correction d'un bug dans rpartite (incorrect à partir de r>5 parts) - correction d'un bug dans whexagon (nb de sommets incorrects) - nouvelles options: -check ps1x/girth, -filter ps1c/ps1x - renomage: ps1bis -> ps1b, ps1ter -> ps1c - nouveau graphe: mycielski - la graphe grotzsch est maintenant défini à partir du graphe mycielski (la définition précédante était fausse) - bug détecté: td-delaunay 500 -check gcolor -format no -seed 7 | grep '>6' qui donne jusqu'à 7 couleurs; le nb de couleurs affiché dans -check gcolor est erroné v2.5 mars 2011: - nouveaux graphes: line-graph, claw v2.6 juin 2011: - amélioration du test -filter ps1: détection de cliques et d'arbres v2.7 octobre 2011: - nouvelle option: -check belman (pour les géométriques seulement) - ajoût des champs xpos,ypos à la structure "graph". - nouveaux graphes: linial, linialc, cube, diamond, theta0, v2.8 novembre 2011: - nouveaux graphes: ggosset, gosset, rplg, wiener_araya, headwood4 - correction d'un bug pour "-xy seed k n" lorsque k=1. - nouvelles options: -check maincc, -maincc (non documentée) ### #*/