Attribution de fréquences - Coloration

Dans une ville on place des antennes GSM. Ces antennes sont plus ou moins puissantes et elles sont placées au gré des accords avec les résidents des immeubles où elles sont implantées. Elles ne sont donc pas placées avec la régularité d'un quadrillage. De plus, on peut être amené à placer plus d'antennes dans les zones de forte affluence.

Nous disposons des données concernant les antennes. En voici un aperçu – 10 premières lignes :

Téléchargez : antennes.csv

Le fichier indique, pour chaque antenne, sa localisation en latitude et longitude, sa portée et un identifiant.

Le calcul de la distance entre deux points, tenant compte des positions en latitude et longitude, relève d'un calcul de trigonométrie. Je vous donne la formule, avec les latitudes et longitudes exprimées en degrés :

$$x = (longitude_1 - longitude_2)\cdot\cos\left(\frac{latitude_1 + latitude_2}{2}\cdot \frac{2\pi}{360}\right) \cdot 111\,120$$ $$y = (latitude_1 - latitude_2) \cdot 111\,120$$ $$distance = \sqrt{x^2 + y^2}$$

Les antennes disposent d'un ensemble de fréquences pour communiquer. Certaines zones sont couvertes par plusieurs antennes en même temps et il faut alors que ces antennes aient une fréquence différente afin d'éviter les interférences.

On aimerait limiter le nombre de fréquences utilisées.

On cherche donc à attribuer une fréquence à chaque antenne, en choisissant une fréquence différente pour deux antennes couvrant une même zone, mais en limitant le nombre de fréquences utilisées.

C'est un problème de coloration de graphe.

Écrire un programme Python qui :

1. ouvre le fichier antennes.csv et en extrait les données,
2. produit un graphe dans lequel chaque sommet est une antenne et chaque arête représente une interférence possible entre deux antennes,
3. réalise la coloration de graphe afin de déterminer quelles antennes peuvent avoir la même fréquence. On pourra attribuer un numéro pour identifier chaque fréquence / couleur
4. écrit un fichier antennes.out.csv dans lequel on aura une colonne FREQ supplémentaire, indiquant une fréquence pour chaque antenne.

Vous pouvez ajouter – en guise de divertissement – une représentation graphique montrant les différentes antennes avec leur couleurs. Pour cela,

• calculer pour chaque antennes la position $(x;y)$ avec les formules :

$$x = longitude \cdot\cos\left(latitude\cdot \frac{2\pi}{360}\right) \cdot 111\,120$$ $$y = latitude \cdot 111\,120$$

• On obtient donc une liste de x, une liste de y, on a déjà une liste de fréquences f et une liste de portées p.

Le code est alors :

import matplotlib.pyplot as plt

plt.scatter(x,y, c=f, s=p) # supposant les list x, y, f, p définies préalablement
plt.show()