• À propos
• Fonctionnalités
• Installation
• Utilisation
• API REST
• Algorithmes
• Technologies
• Structure du projet
• Auteur
• Licence

CollectGraph est un projet académique de théorie des graphes appliquée à un problème concret : l'optimisation des tournées de collecte de déchets en milieu urbain. L'application combine la modélisation visuelle d'un réseau de routes (graphe pondéré) avec deux algorithmes classiques :

• 🛣️ Dijkstra pour trouver le chemin le plus court entre deux points
• 🎨 Coloration gloutonne pour répartir les zones de collecte entre équipes ou jours de la semaine

L'interface est entièrement interactive : on dessine le graphe à la souris sur un Canvas HTML5, on visualise les résultats en temps réel, et les données sont persistées dans une base PostgreSQL.

• 🗺️ Visualisation interactive du graphe sur Canvas HTML5
• ✏️ Édition dynamique : ajout/suppression de nœuds et arêtes à la souris
• ⚖️ Arêtes pondérées (distance/temps)
• 🛣️ Algorithme de Dijkstra : chemin optimal entre deux nœuds
• 🎨 Coloration de graphe : assignation automatique d'équipes/jours
• 💾 Persistance PostgreSQL : les modifications sont sauvegardées
• 🔄 API REST complète : intégration possible avec d'autres systèmes

• Python 3.8 ou supérieur
• PostgreSQL 12 ou supérieur
• pip

git clone https://github.com/SALLAH-JP/TG.git
cd TG

python -m venv venv
# Windows
venv\Scripts\activate
# Linux / macOS
source venv/bin/activate

pip install flask flask-cors psycopg2-binary

Créer la base et importer le schéma :

# Créer la base
createdb TG

# Importer le schéma (à la racine du repo)
psql -d TG -f TG.sql

Schéma simplifié :

CREATE TABLE nodes (
    id SERIAL PRIMARY KEY,
    name VARCHAR(50) UNIQUE NOT NULL,
    x FLOAT NOT NULL,
    y FLOAT NOT NULL
);

CREATE TABLE edges (
    id SERIAL PRIMARY KEY,
    from_node VARCHAR(50) NOT NULL,
    to_node VARCHAR(50) NOT NULL,
    weight INT NOT NULL,
    undirected BOOLEAN DEFAULT FALSE,
    FOREIGN KEY (from_node) REFERENCES nodes(name) ON DELETE CASCADE,
    FOREIGN KEY (to_node) REFERENCES nodes(name) ON DELETE CASCADE
);

Modifier les identifiants PostgreSQL dans server.py :

def get_connection():
    return psycopg2.connect(
        dbname="TG",
        user="postgres",
        password="VOTRE_MOT_DE_PASSE",
        host="localhost",
        port=5432
    )

python server.py

L'application est accessible sur http://localhost:5000

• Canvas central : visualisation du graphe (nœuds + arêtes pondérées)
• Barre d'outils : sélection de l'action en cours, choix source/destination
• Panneau latéral : légende des équipes et résultats des calculs

1. Sélectionner « Ajouter un nœud » dans le menu
2. Cliquer OK
3. Cliquer sur le canvas pour le placer
4. Entrer un nom (auto-incrémenté si vide) puis Entrée

1. Sélectionner « Supprimer un nœud » → OK
2. Cliquer sur le nœud à supprimer
3. Les arêtes liées sont supprimées en cascade

1. Sélectionner « Ajouter une arête » → OK
2. Cliquer sur le nœud source
3. Cliquer sur le nœud destination
4. Entrer le poids (distance/temps) → Entrée

1. Sélectionner « Supprimer une arête » → OK
2. Cliquer sur l'arête

1. Choisir la source et la destination dans les menus déroulants
2. Cliquer Rechercher (Dijkstra)
3. Le chemin est surligné sur le canvas et la distance affichée

1. Cliquer Colorier (jours/équipes)
2. Les nœuds sont automatiquement colorés selon leur assignation
3. La légende affiche la correspondance couleur ↔ équipe

Retourne le graphe complet.

{
  "nodes": [
    {"name": "N1", "x": 100, "y": 150},
    {"name": "N2", "x": 300, "y": 250}
  ],
  "edges": [
    {"from": "N1", "to": "N2", "weight": 50, "undirected": false}
  ]
}

Ajoute un nœud.

{ "name": "N3", "x": 400, "y": 300 }

Supprime un nœud (et ses arêtes en cascade).

{ "name": "N3" }

Ajoute une arête pondérée.

{ "from": "N1", "to": "N2", "weight": 50 }

Supprime une arête.

{ "from": "N1", "to": "N2" }

Calcule le plus court chemin.

{
  "path": ["N1", "N3", "N2"],
  "distance": 150
}

Coloration du graphe (assignation d'équipes).

{
  "N1": 1,
  "N2": 2,
  "N3": 1
}

Calcule le plus court chemin entre deux nœuds dans un graphe pondéré non-négatif.

• Complexité : O((V + E) log V) avec file de priorité
• Implémentation : logic.py
• Usage : optimisation des trajets de collecte entre deux points

Assigne des couleurs (= équipes ou jours) aux nœuds de façon à ce que deux nœuds adjacents n'aient jamais la même couleur.

• Stratégie : tri des nœuds par degré décroissant puis affectation gloutonne
• Objectif : minimiser le nombre d'équipes/jours nécessaires pour couvrir toute la ville
• Application : planification hebdomadaire des tournées

• Flask — micro-framework web Python
• Flask-CORS — gestion des requêtes cross-origin
• psycopg2 — driver PostgreSQL

• HTML5 / CSS3 — structure et styles
• Canvas API — rendu 2D interactif du graphe
• JavaScript vanilla — logique frontend, pas de framework
• Fetch API — communication avec le backend

• PostgreSQL — stockage des nœuds, arêtes et métadonnées

.
├── server.py              # Backend Flask + routes API
├── logic.py               # Algorithmes (Dijkstra, coloration)
├── TG.sql                 # Schéma SQL de la base
├── public/                # Frontend
│   ├── index.html         # Page principale
│   ├── app.js             # Logique Canvas + appels API
│   └── style.css          # Styles
├── projet final tg.docx   # Rapport du projet
└── LICENSE

Scénario : Optimiser la collecte des déchets dans une ville de 30 quartiers.

1. Modélisation — Créer un nœud par quartier, des arêtes pour chaque route (poids = distance ou temps de parcours)
2. Répartition — Lancer la coloration : la ville est divisée en zones distinctes, chacune attribuée à une équipe différente
3. Optimisation — Pour chaque zone, utiliser Dijkstra pour planifier le trajet le plus rapide entre le dépôt et chaque point
4. Persistance — Le réseau est sauvegardé en base, modifiable en temps réel par les opérateurs

psycopg2.OperationalError: could not connect to server → PostgreSQL n'est pas démarré, ou les identifiants dans server.py sont incorrects.

Canvas vide au démarrage → La base est vide. Ajouter des nœuds manuellement via l'interface, ou importer un jeu de données initial dans TG.sql.

Arête impossible à ajouter → Vérifier que les deux nœuds existent et que l'arête n'existe pas déjà entre eux.

• Requêtes paramétrées : protection contre les injections SQL
• CORS configuré pour limiter les origines autorisées
• Gestion des erreurs côté serveur

Ce projet a été réalisé dans le cadre du cours de Théorie des Graphes de la Licence Informatique Appliquée à l'Université des Mascareignes. Le rapport complet est disponible dans le dépôt (projet final tg.docx).

SALLAH Assiongbon Théodore Jean-Paul Étudiant en 3ème année — Licence Informatique Appliquée 🎓 Université des Mascareignes (Maurice)

Ce projet est distribué sous licence MIT — voir le fichier LICENSE.