Format du fichier de configurations


Le fichier de configurations contient une description des 633 configurations de Seymour et al. Ce fichier est une suite de 633 blocs, séparés par des lignes vides. Chaque bloc représente une configuration C, avec le format suivant :

    Carte ccc
    perimetre pp
    contrat { ee ff ...}
    ss segments
    ...
    jj jonctions
    ...
    rr regions
    ...
    Fin
ccc est le numéro de la configuration C (sur trois chiffres,  entre 1 et 633),  pp est son périmètre p (sur deux chiffres,  entre 6 et 14),  ss son nombre de segments et demi-segments s (sur deux chiffres),  jj son nombre de point de jonction et d'interface j (sur deux chiffres),  et rr son nombre de régions r (sur deux chiffres). Pour un fragment de carte planaire cubique,  on doit avoir s > p,  j > p,  r > p,  2s+2p = 3j,  et 2r = j+2.

Les p demi-segments,  points d'interface,  et régions partielles de la configurations sont indicés de 0 à p-1. Plus précisément,  le demi-segment d'indice e se termine au point d'interface d'indice e et sépare les régions partielles d'indices e et e',  où e' = e-1 modulo p. Les indices des segment complets,  points de jonction ternaires,  et régions complètes vont de p à s-1,  j-1,  et r-1,  respectivement.

Après la ligne ss segments on trouve s lignes décrivant les s segments et demi-segments de C. Chaque ligne est de la forme

    ee (ii - kk) ]pp | qq[
ee est l'indice du segment (qui va de 0 à s-1),  ii et kk les indices des extrémités du segment (points de jonction,  ou éventuellement d'interface pour les demi-segments),  et pp et qq les indices des deux régions séparées par le segment (pour un demi-segment,  ce sont des régions partielles).

Après la ligne jj points,  on trouve j lignes de la forme

    ii @ (xxx yyy)
donnant les coordonnées (sur trois chiffres) des j points d'interface et de jonction de C. Enfin,  après la ligne rr regions,  on trouve r lignes de la forme
    pp @ (xxx yyy)
donnant les coordonnées de «capitales» situées au milieu de chaque région de C (ou à la frontière,  pour les régions partielles).

Enfin,  la ligne contrat { ee ff ...} donne le contrat de la configuration C. Ce contrat est vide pour les configurations D-réductibles,  sinon il comporte de un à quatre indices de segments (sur deux chiffres).

Noter qu'il suffit de connaître les indices des extrémités des segments pour tester la réductibilité de la configuration (avec le contrat). Les indices des régions adjacentes permettent de vérifier que la carte est bien planaire,  et peuvent aussi aider à accélérer le coloriage de C (par exemple,  en commençant par colorier les segments communs aux trois régions ayant le plus de côtés). Les coordonnées ne servent que pour l'affichage des cartes.

Enfin,  si les cartes obtenues ont l'air un peu «biscornues»,  c'est qu'elles ont été obtenues par une transformation automatique à partir d'un placement de leur graphe dual (c'est-à-dire des «capitales» des régions entières) qui lui est bien régulier.