{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "# Séance 2 — Parcours & distances (BFS / DFS)\n",
        "\n",
        "## Objectifs pédagogiques\n",
        "- Comprendre les notions de **chemin**, **distance** et ** composantes connexes**.\n",
        "- Distinguer **BFS** (parcours en largeur) et **DFS** (parcours en profondeur).\n",
        "- Utiliser `networkx` pour calculer des plus courts chemins dans un graphe **non pondéré**.\n",
        "- Relier les distances à des interprétations sociologiques (proximité, relais, \"six degrés\").\n",
        "\n",
        "## Rappels\n",
        "- Dans un **graphe non pondéré**, un **plus court chemin** est le chemin avec le **moins d'arêtes**.\n",
        "- **BFS** explore par **couches** (distance croissante) et permet de trouver un plus court chemin.\n",
        "- **DFS** explore en **profondeur** (par branches) ; utile pour détecter des cycles/composantes mais **ne garantit pas** un plus court chemin.\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# %pip install networkx matplotlib\n",
        "\n",
        "import networkx as nx\n",
        "import matplotlib.pyplot as plt\n",
        "from collections import deque"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 1) Graphe de départ : petit réseau social"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Vous pouvez modifier/étendre ce graphe\n",
        "G = nx.Graph()\n",
        "G.add_edges_from([\n",
        "    (\"Alice\",\"Bob\"),\n",
        "    (\"Bob\",\"Claire\"),\n",
        "    (\"Claire\",\"Emma\"),\n",
        "    (\"Alice\",\"David\"),\n",
        "    (\"David\",\"Emma\"),\n",
        "    (\"Emma\",\"Fanny\"),\n",
        "    (\"Bob\",\"Gaston\"),\n",
        "])\n",
        "\n",
        "# Visualisation simple\n",
        "plt.figure()\n",
        "nx.draw(G, with_labels=True)\n",
        "plt.show()\n",
        "\n",
        "print(\"Nœuds :\", list(G.nodes()))\n",
        "print(\"Arêtes:\", list(G.edges()))\n",
        "print(\"Composantes connexes:\", nx.number_connected_components(G))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "**Question :** Y a-t-il un unique groupe connecté, ou plusieurs ? Impact sociologique : des individus isolés auront des distances infinies vers le reste."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 2) Plus courts chemins et distances avec NetworkX"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "source, cible = \"Alice\", \"Fanny\"\n",
        "chemin = nx.shortest_path(G, source=source, target=cible)  # plus court chemin (non pondéré)\n",
        "dist = nx.shortest_path_length(G, source=source, target=cible)\n",
        "print(f\"Plus court chemin de {source} à {cible} :\", chemin)\n",
        "print(f\"Distance (nombre d'arêtes) :\", dist)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "**Exercice 2.1** : testez 3 autres paires (par ex. `('Gaston','Fanny')`, `('Alice','Claire')`, `('David','Bob')`).\n",
        "\n",
        "**Exercice 2.2** : si vous supprimez l'arête `('David','Emma')`, que devient la distance `Alice→Fanny` ?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 3) Implémenter un BFS pédagogique (pour comprendre l'ordre d'exploration)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "def bfs_layers(graph, start):\n",
        "    \"\"\"Retourne l'ordre de visite et les couches de distance (dict: noeud -> distance)\n",
        "    BFS avec file d'attente (deque).\n",
        "    \"\"\"\n",
        "    visited = set([start])\n",
        "    dist = {start: 0}\n",
        "    order = []\n",
        "    q = deque([start])\n",
        "\n",
        "    while q:\n",
        "        u = q.popleft()\n",
        "        order.append(u)\n",
        "        for v in graph.neighbors(u):\n",
        "            if v not in visited:\n",
        "                visited.add(v)\n",
        "                dist[v] = dist[u] + 1\n",
        "                q.append(v)\n",
        "    return order, dist\n",
        "\n",
        "order, dist = bfs_layers(G, \"Alice\")\n",
        "print(\"Ordre BFS depuis Alice:\", order)\n",
        "print(\"Distances depuis Alice:\", dist)"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "**Exercice 3.1** : Comparez les **distances** renvoyées par `bfs_layers` et `nx.shortest_path_length` pour 3 nœuds.\n",
        "\n",
        "**Exercice 3.2** : Quel nœud est le plus proche (distance minimale) d'**Alice** ? Le plus lointain ?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 4) Implémenter un DFS (ordre d'exploration par branches)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "def dfs_order(graph, start, visited=None, order=None):\n",
        "    if visited is None: visited = set()\n",
        "    if order is None: order = []\n",
        "    visited.add(start)\n",
        "    order.append(start)\n",
        "    for v in graph.neighbors(start):\n",
        "        if v not in visited:\n",
        "            dfs_order(graph, v, visited, order)\n",
        "    return order\n",
        "\n",
        "print(\"Ordre DFS depuis Alice:\", dfs_order(G, \"Alice\"))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "**Exercice 4.1** : Pourquoi **l'ordre DFS** diffère-t-il souvent de l'ordre BFS ?\n",
        "\n",
        "**Exercice 4.2** : DFS trouve-t-il un plus court chemin ? Expliquez avec un contre-exemple si possible."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 5) Distances globales : diamètre & distance moyenne (si connexe)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "if nx.is_connected(G):\n",
        "    # Diamètre = plus longue distance entre deux nœuds\n",
        "    d = nx.diameter(G)\n",
        "    # Distance moyenne (longueur moyenne des plus courts chemins)\n",
        "    apl = nx.average_shortest_path_length(G)\n",
        "    print(\"Diamètre:\", d)\n",
        "    print(\"Distance moyenne:\", apl)\n",
        "else:\n",
        "    print(\"Le graphe n'est pas connexe : diamètre et distance moyenne ne sont pas définis globalement.\")"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "**Exercice 5.1** : Ajoutez/supprimez une arête et observez l'effet sur la distance moyenne. Interprétez sociologiquement (ex. apparition d'un **pont** qui réduit les distances)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 6) Étude guidée : \"six degrés de séparation\" (mini-expérience)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "metadata": {},
      "outputs": [],
      "source": [
        "# Construisons un graphe en anneau + quelques liens longue portée pour réduire drastiquement les distances\n",
        "H = nx.cycle_graph(12)  # 12 individus en cercle (0..11)\n",
        "H = nx.relabel_nodes(H, {i: f\"P{i}\" for i in range(12)})\n",
        "H.add_edge(\"P0\",\"P6\")   # raccourci longue portée\n",
        "H.add_edge(\"P3\",\"P9\")   # autre raccourci\n",
        "\n",
        "plt.figure()\n",
        "nx.draw(H, with_labels=True)\n",
        "plt.show()\n",
        "\n",
        "print(\"Connexe:\", nx.is_connected(H))\n",
        "print(\"Distance moyenne:\", nx.average_shortest_path_length(H))"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "**Questions**\n",
        "1. Que se passe-t-il si on **retire** les liens longue portée ?\n",
        "2. Pourquoi quelques liens inter-groupes peuvent-ils **réduire fortement** les distances ?\n",
        "3. Donnez une interprétation en termes de diffusion d'une rumeur/idée."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": [
        "## 7) Synthèse écrite\n",
        "- Comparez BFS et DFS sur votre graphe.\n",
        "- Donnez 2 exemples de distances pertinentes en sociologie (ex. accès à l'information, recrutement).\n",
        "- Proposez une **hypothèse** : l'ajout d'un lien entre deux groupes réduira X ; comment le tester ?"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "75d566ac",
      "metadata": {},
      "source": []
    }
  ],
  "metadata": {
    "kernelspec": {
      "display_name": "Python 3",
      "language": "python",
      "name": "python3"
    },
    "language_info": {
      "name": "python",
      "version": "3.x"
    }
  },
  "nbformat": 4,
  "nbformat_minor": 5
}