DistanceAnalyzer.java

package fr.univ.dblp.analysis;

import fr.univ.dblp.export.DataExporter;
import fr.univ.dblp.export.ResultsPrinter;
import fr.univ.dblp.utils.RandomSampler;
import org.graphstream.graph.Edge;
import org.graphstream.graph.Graph;
import org.graphstream.graph.Node;

import java.util.*;

/**
 * Analyse les distances moyennes dans un réseau (Question 5).
 *
 * Cette classe calcule la distance moyenne entre les nœuds du réseau
 * par échantillonnage et parcours en largeur (BFS). Elle permet également
 * de vérifier l'hypothèse des "six degrés de séparation" et de comparer
 * avec un réseau aléatoire théorique.
 *
 * @author Hamadou BA
 * @see <a href="https://www-apps.univ-lehavre.fr/forge/bh243413/tp2-ri-mesures-de-reseaux-interaction.git">Dépôt Git</a>
 */
public class DistanceAnalyzer {

    private static final int SAMPLE_SIZE = 1000;

    /**
     * Calcule la distance moyenne par échantillonnage et parcours BFS.
     *
     * Pour éviter de calculer toutes les paires de nœuds (O(N²)), cette méthode
     * échantillonne aléatoirement SAMPLE_SIZE nœuds et effectue un BFS depuis
     * chacun pour estimer la distance moyenne.
     *
     * @param g Le graphe à analyser
     * @return La distance moyenne estimée
     */
    public static double computeAverageDistance(Graph g) {
        ResultsPrinter.printInfo(
            String.format("Échantillonnage de %d nœuds pour estimer la distance moyenne...", SAMPLE_SIZE));

        List<Node> sampledNodes = RandomSampler.sampleNodes(g, SAMPLE_SIZE);

        // Utilisation de somme et compteur au lieu de stocker toutes les distances
        double sum = 0.0;
        long count = 0;

        int progress = 0;
        for (Node source : sampledNodes) {
            Map<String, Integer> distancesFromSource = bfsDistances(g, source.getId());

            for (int dist : distancesFromSource.values()) {
                if (dist > 0) { // Exclure la distance à soi-même
                    sum += dist;
                    count++;
                }
            }

            progress++;
            if (progress % 100 == 0) {
                ResultsPrinter.printInfo(
                    String.format("  Progression: %d/%d nœuds traités", progress, SAMPLE_SIZE));
            }
        }

        if (count == 0) {
            return 0.0;
        }

        return sum / count;
    }

    /**
     * Calcule la distribution des distances à partir de nœuds échantillonnés.
     *
     * Cette méthode retourne une map associant chaque distance au nombre
     * de paires de nœuds séparées par cette distance.
     *
     * @param g Le graphe à analyser
     * @return Map distance -> fréquence
     */
    public static Map<Integer, Integer> computeDistanceDistribution(Graph g) {
        ResultsPrinter.printInfo("Calcul de la distribution des distances...");

        List<Node> sampledNodes = RandomSampler.sampleNodes(g, SAMPLE_SIZE);
        Map<Integer, Integer> distribution = new HashMap<>();

        for (Node source : sampledNodes) {
            Map<String, Integer> distancesFromSource = bfsDistances(g, source.getId());

            for (int dist : distancesFromSource.values()) {
                if (dist > 0) {
                    distribution.put(dist, distribution.getOrDefault(dist, 0) + 1);
                }
            }
        }

        return distribution;
    }

    /**
     * Effectue un parcours en largeur (BFS) depuis un nœud source.
     *
     * Cette méthode privée calcule les distances depuis un nœud source
     * vers tous les nœuds atteignables du graphe.
     *
     * @param g Le graphe
     * @param sourceId Identifiant du nœud source
     * @return Map associant chaque nœud atteignable à sa distance depuis la source
     */
    private static Map<String, Integer> bfsDistances(Graph g, String sourceId) {
        Map<String, Integer> distances = new HashMap<>();
        Queue<String> queue = new LinkedList<>();

        queue.add(sourceId);
        distances.put(sourceId, 0);

        while (!queue.isEmpty()) {
            String currentId = queue.poll();
            int currentDist = distances.get(currentId);

            Node currentNode = g.getNode(currentId);
            if (currentNode == null) continue;

            for (Edge edge : currentNode.edges().toArray(Edge[]::new)) {
                Node neighbor = edge.getOpposite(currentNode);
                String neighborId = neighbor.getId();

                if (!distances.containsKey(neighborId)) {
                    distances.put(neighborId, currentDist + 1);
                    queue.add(neighborId);
                }
            }
        }

        return distances;
    }

    /**
     * Calcule la distance moyenne théorique pour un réseau aléatoire.
     *
     * Pour un réseau aléatoire, la distance moyenne théorique est:
     * l ≈ ln(N) / ln(<k>)
     *
     * @param n Nombre de nœuds
     * @param avgDegree Degré moyen
     * @return Distance moyenne théorique
     */
    public static double theoreticalRandomDistance(int n, double avgDegree) {
        if (avgDegree <= 1) {
            return Double.POSITIVE_INFINITY;
        }
        return Math.log(n) / Math.log(avgDegree);
    }

    /**
     * Exporte la distribution des distances pour visualisation avec gnuplot.
     *
     * @param dist Distribution des distances (distance -> fréquence)
     * @param filePath Chemin du fichier de sortie
     */
    public static void exportDistanceDistribution(Map<Integer, Integer> dist, String filePath) {
        DataExporter.exportDistanceDistribution(dist, filePath);
    }

    /**
     * Effectue l'analyse complète de la Question 5.
     *
     * Cette méthode calcule la distance moyenne, la compare avec un réseau
     * aléatoire théorique, vérifie l'hypothèse des "six degrés de séparation"
     * et exporte la distribution des distances.
     *
     * @param g Le graphe à analyser
     * @param networkName Nom du réseau (pour l'affichage)
     * @param baseFilename Nom de base pour les fichiers de sortie
     */
    public static void analyze(Graph g, String networkName, String baseFilename) {
        long startTime = System.currentTimeMillis();
        ResultsPrinter.printHeader("QUESTION 5: Distance moyenne - " + networkName);

        // Calcul de la distance moyenne
        double avgDistance = computeAverageDistance(g);
        ResultsPrinter.printMetric("Distance moyenne (expérimentale)", avgDistance);

        // Comparaison avec un réseau aléatoire théorique
        int n = g.getNodeCount();
        double avgDegree = BasicMetrics.getAverageDegree(g);
        double theoreticalDist = theoreticalRandomDistance(n, avgDegree);

        ResultsPrinter.printSeparator();
        ResultsPrinter.printInfo("Comparaison avec réseau aléatoire théorique:");
        ResultsPrinter.printMetric("Distance théorique (aléatoire)", theoreticalDist);
        ResultsPrinter.printMetric("Différence", Math.abs(avgDistance - theoreticalDist));

        // Vérification de l'hypothèse des "six degrés de séparation"
        ResultsPrinter.printSeparator();
        if (avgDistance <= 7.0) {
            ResultsPrinter.printSuccess(
                "Hypothèse des 'six degrés de séparation' CONFIRMÉE! (distance ≈ " +
                String.format("%.1f", avgDistance) + ")");
        } else {
            ResultsPrinter.printInfo(
                "Distance moyenne: " + String.format("%.1f", avgDistance) +
                " (légèrement supérieure à 6)");
        }

        // Calcul et export de la distribution
        ResultsPrinter.printSeparator();
        Map<Integer, Integer> distribution = computeDistanceDistribution(g);

        String distFile = "output/data/" + baseFilename + "_distances.dat";
        exportDistanceDistribution(distribution, distFile);

        // Recherche de la distance maximale
        int maxDistance = distribution.keySet().stream().max(Integer::compareTo).orElse(0);
        ResultsPrinter.printMetric("Distance maximale observée", maxDistance);

        ResultsPrinter.printInfo("C'est un réseau 'petit monde' (small world)!");

        ResultsPrinter.printElapsedTime(startTime);
    }
}