Discussion :

[Korrigan5]

Bonjour,

Je planche actuellement sur un algo de recherche dans un graphe, j'aurais besoin de conseils, savoir si je suis bien parti ou pas.

Voici le problème :
- Soit un réseau d'équipement avec une topologie étoilée (graphe connexe non directionnel).
- Chaque équipement travaille sur une fréquence donnée, mais pour ne pas brouiller les équipements voisins, la même fréquence ne doit pas être ré-utilisée à moins de 5 équipements voisins.
- Mon problème consiste à trouver les couples d'équipements qui travaillent avec la même fréquence alors qu'ils sont distants de moins de 5 relations de voisinages.

Voici ce que je pensais faire :
- J'ai un tableau de couples équipement / fréquence
- J'ai fait une matrice des équipements voisins de premier niveau (voisin direct)
ex :
A : B,C,F
B : A,C,E,F
C : A,B
- A partir de cette matrice des équipements voisins de premier niveau je calcule la même matrice pour les voisins de 5ème niveaux
- Puis je fais la vérification à partir de mon tableau équipement / fréquence

J'ai peur que cela ne soit très long et pas très optimisé , Avez-vous des conseils à me donner pour améliorer cela svp ?

Merci.

[kwariz]

Hello,

Si tu peux représenter ton graphe avec un matrice d'adjacence M, alors la kième puissance de M te donneras le nombre de chemins de longueur k d'un noeud à un autre . Les Mi,j non nuls te donnerons les couples problématiques à vérifier.

[Korrigan5]

Merci pour ta réponse.

Au début c'est bien vers cette solution que je m'orientais mais j'ai oublié de préciser dans mon précédent post que mon graphe est constitué de 13000 à 15000 nœuds d'ordre 32 au maximum.
Du coup ma matrice d'adjacence est énorme et contient beaucoup de 0 (info non significative dans mon cas), et j'ai peur que cela soit vraiment très long.
C'est pourquoi pour faire un programme plus léger j'ai préféré (jusqu'à présent) partir d'un tableau des nœuds voisins puis récursivement sur ce tableau trouver pour chaque nœud tous les nœuds voisins de 5 niveaux. Puis terminer avec la comparaison des fréquences.

Malgré tout je pense que cet algo risque d'être long tout de même et je cherche à l'améliorer car j'ai des contraintes temporelles fortes sur cet algo.

[Alexis.M]

Utilise des bibliothèques d'algèbre linéaire pour les matrices creuses (sparse matrices), c'est en général très efficace.