Puisque la question revient :
Cette méthode (calculer la puissance stepMax de la matrice d’adjacence de la TdC et compter les coefficients non nuls correspondant à un membre référent sur la ligne du candidat) a plusieurs avantages :
- le temps de calcul de la puissance ne dépend que de N (O(N^2)), alors que l’exploration du graphe est plus ou moins longue et est en temps exponentiel dans le pire des cas
- le calcul se fait sur tous les membres en même temps
- possibilité d’exploiter le GPU et le SIMD (mais est-ce possible dans le runtime ? si non, dans un oracle ?)
- si on regroupe tous les R membres référents d’un côté de la matrice, il suffit de vérifier, pour chaque ligne correspondant à un candidat, que dans l’ensemble de colonnes des référents, il y a moins de 20% de zéros (O(R))
Dites si ce n’est pas clair, je peux faire un schéma.
Edit: puisque ce calcul est long mais rentable si besoin de calculer plein de règles de distance en même temps, il pourrait être fait par intervalle minimal de X blocs. On n’a aucun besoin de valider une règle de distance en 30 secondes.
Edit2: en fait il faut recompter les référents accessibles pour chaque puissance 1,2,3,4,5. Cette opération prend donc plus d’espace. Au total, ça nous fait un temps O(stepMax.N²+stepMax.C.R) et un espace O(N²+C.R).
Par contre stocker bêtement les coefficients de la matrice prend trop de place (23Mo pour 5000 membres, 1Go pour 33000 membres). Donc il faut la stocker sous une forme compressée, ce qui ralentit les calculs.