# INF7440, Automne 2004.
# Coloration de graphes : calcul de toutes les colorations valides

resource coloration()

procedure PROMETTEUR(int i, int couleurs[*], int G[*][*], int n) returns int r {
  r = 1;
  for [ j = 1 to i-1 ] {
    if ( G[j][i] == 1 & couleurs[j] == couleurs[i] ) { r = 0; }
  }
}

procedure COLORATION_REC(int i, ref int couleurs[*], int G[*][*], int n, int m) {
  int j;
  if ( PROMETTEUR(i, couleurs, G, n) == 1 ) {
    if ( i == n ) { 
      for [ j = 1 to n ] { 
        printf("%d ", couleurs[j]); 
      } 
      printf("\n");
    }
    else {
      for [ c = 1 to m ] {
        couleurs[i+1] = c;
        COLORATION_REC(i+1, couleurs, G, n, m);
      }
    }
  }
}

# Le graphe
int n = 5;
int G[n][n];

int i, j;
for [ i = 1 to n , j = 1 to n ] { G[i][j] = 0; }
G[1][2] = 1; G[1][3] = 1; G[1][4] = 1; G[2][3] = 1; G[2][5] = 1; G[3][4] = 1; G[3][5] = 1; G[4][5] = 1;

# La coloration
int m = 3;
int couleurs[n];

# Appel a la procedure de coloration
COLORATION_REC(0, couleurs, G, n, m);

end