Search-02b : Théorie des Graphes avec NetworkX (C#)

Navigation : << Search-2 C# (Recherche non informée) | Index | Search-2c (QuikGraph) >>

Twin C# (.NET Interactive) de Search-02b-NetworkX.ipynb — marathon #4956 (parite .NET <-> Python).

NetworkX est la librairie de reference pour la théorie des graphes en Python (200+ algorithmes). Ce twin C# (.NET 9, 0 NuGet) reimplemente from-scratch les moteurs algorithmiques centraux : construction de graphe (adjacency list pondere), parcours (BFS/DFS), plus courts chemins (Dijkstra avec priority queue), centralites (degré, proximite, intermediaire, PageRank), et flot maximum (Ford-Fulkerson). Les internes (queue FIFO du BFS, relaxation du Dijkstra, accumulation des chemins pour l’intermediaire, itération de puissance du PageRank) sont visibles — c’est tout l’intérêt pedagogique.

Plan pedagogique

  1. Graphe pondere — modèle adjacency list (oriente / non-oriente)
  2. Parcours BFS / DFS — exploration du graphe
  3. Plus courts chemins — Dijkstra (tas de priorite, relaxation)
  4. Centralites — qui est important ? (degré, proximite, intermediaire, PageRank)
  5. Flot maximum — Ford-Fulkerson (chemin augmentant BFS)
  6. Exercices

Parite #4956 : la version Python s’appuie sur networkx (boite noire industrielle, 200+ algos) pour TOUT. Ce twin C# (BCL .NET 9, 0 NuGet) traduit les moteurs from-scratch (le coeur algorithmique). networkx = RECOVERABLE-MACHINE : pas d’equivalent C# du même niveau en une seule lib pour ce notebook pedagogique ; le from-scratch engine EST la substance. Louvain (communautes) et matching pondere (Hongrois) — couverts par networkx cote Python mais complexes au-dela du coeur — deviennent des exercices cote C#.

1. Graphe pondere : modèle adjacency list

Un graphe \(G = (V, E)\) : un ensemble de sommets \(V\) et d’aretes \(E\). On modelise ici une adjacency list : pour chaque sommet, la liste de ses voisins (avec poids). Le graphe peut etre oriente ou non-oriente. Les poids servent aux plus courts chemins (Dijkstra) et au flot (capacites).

using System.Linq;
using System.Text;
using System.Collections.Generic;

static void Show(string s) { s.Display(); }

// Arete ponderee : destination + poids (cout ou capacite).
public record Edge(string To, double Weight);

// Graphe oriente ou non-oriente, adjacency list.
public class Graph
{
    public bool Directed;
    public Dictionary<string, List<Edge>> Adj = new();

    public Graph(bool directed = false) { Directed = directed; }

    public Graph AddNode(string v)
    {
        if (!Adj.ContainsKey(v)) Adj[v] = new List<Edge>();
        return this;
    }

    public Graph AddEdge(string from, string to, double weight = 1.0)
    {
        AddNode(from); AddNode(to);
        Adj[from].Add(new Edge(to, weight));
        if (!Directed) Adj[to].Add(new Edge(from, weight));
        return this;
    }

    public IEnumerable<string> Nodes => Adj.Keys.OrderBy(k => k);
    public int NodeCount => Adj.Count;
}

// Graphe de test (reseau de villes, poids = distance). Reponses analytiques connues.
//     A --4-- B --3-- C
//     |       |       |
//     2       1       5
//     |       |       |
//     D --6-- E --2-- F
var g = new Graph(directed: false)
    .AddEdge("A","B",4).AddEdge("B","C",3)
    .AddEdge("A","D",2).AddEdge("B","E",1).AddEdge("C","F",5)
    .AddEdge("D","E",6).AddEdge("E","F",2);

$"Graphe de test : {g.NodeCount} sommets, oriente={g.Directed}".Display();
var sb = new StringBuilder();
sb.AppendLine("Adjacency list :");
foreach (var v in g.Nodes)
    sb.AppendLine($"  {v} -> [{string.Join(", ", g.Adj[v].OrderBy(e=>e.To).Select(e => $"{e.To}:{e.Weight}"))}]");
Show(sb.ToString());
Graphe de test : 6 sommets, oriente=False
Adjacency list :
  A -> [B:4, D:2]
  B -> [A:4, C:3, E:1]
  C -> [B:3, F:5]
  D -> [A:2, E:6]
  E -> [B:1, D:6, F:2]
  F -> [C:5, E:2]

2. Parcours BFS et DFS

Deux facons fondamentales d’explorer un graphe depuis une source :

  • BFS (Breadth-First Search) — explore par couches (tous les voisins d’abord, puis les voisins des voisins). Trouve les plus courts chemins en nombre d’aretes. Structure : queue FIFO.
  • DFS (Depth-First Search) — plonge le plus profond possible avant de revenir (backtracking). Utilise pour la detection de cycles, la tri-topologique. Structure : pile LIFO (ou recursion).
#nullable enable
// BFS : retourne l'ordre de visite + les distances (en nombre d'aretes) depuis la source.
public static (List<string> order, Dictionary<string,int> dist) BFS(Graph g, string source)
{
    var order = new List<string>();
    var dist = new Dictionary<string,int>();
    var q = new Queue<string>();
    var seen = new HashSet<string>();
    q.Enqueue(source); seen.Add(source); dist[source] = 0;
    while (q.Count > 0)
    {
        var u = q.Dequeue();
        order.Add(u);
        foreach (var e in g.Adj[u].OrderBy(e => e.To))   // deterministe (tri par voisin)
            if (seen.Add(e.To))
            {
                dist[e.To] = dist[u] + 1;
                q.Enqueue(e.To);
            }
    }
    return (order, dist);
}

// DFS iteratif (pile) : retourne l'ordre de visite.
public static List<string> DFS(Graph g, string source)
{
    var order = new List<string>();
    var seen = new HashSet<string>();
    var st = new Stack<string>();
    st.Push(source);
    while (st.Count > 0)
    {
        var u = st.Pop();
        if (!seen.Add(u)) continue;
        order.Add(u);
        // empiler dans l'ordre inverse pour visiter les voisins dans l'ordre (deterministe).
        foreach (var e in g.Adj[u].OrderBy(e => e.To).Reverse())
            if (!seen.Contains(e.To)) st.Push(e.To);
    }
    return order;
}

var (bfsOrder, bfsDist) = BFS(g, "A");
$"BFS depuis A : ordre = [{string.Join(", ", bfsOrder)}]".Display();
$"Distances (nb aretes) : {string.Join("  ", bfsDist.OrderBy(kv=>kv.Key).Select(kv => $"{kv.Key}={kv.Value}"))}".Display();
$"  -> A=0, B=D=1, C=E=2, F=3 (attendu : 3 sauts A-B-E-F ou A-B-C-F)".Display();
$"DFS depuis A : ordre = [{string.Join(", ", DFS(g, "A"))}]".Display();
BFS depuis A : ordre = [A, B, D, C, E, F]
Distances (nb aretes) : A=0  B=1  C=2  D=1  E=2  F=3
  -> A=0, B=D=1, C=E=2, F=3 (attendu : 3 sauts A-B-E-F ou A-B-C-F)
DFS depuis A : ordre = [A, B, C, F, E, D]

3. Plus courts chemins : Dijkstra

L’algorithme de Dijkstra (1959) trouve les plus courts chemins depuis une source vers tous les sommets, sur un graphe a poids positifs. Principe :

  1. Initialiser dist[source]=0, tous les autres a \(+\infty\).
  2. Extraire le sommet non-finalise de plus petite distance (priority queue).
  3. Relacher chaque arete sortante : si dist[u] + poids < dist[v], mettre a jour dist[v] et enregistrer le predecesseur.
  4. Marquer u finalise, repeter.

Le tas de priorite (min-heap) est la cle de l’efficacite : \(O((V+E) \log V)\).

#nullable enable
// Dijkstra : plus courts chemins depuis source (poids positifs).
// Retourne (distances, predecesseurs).
public static (Dictionary<string,double> dist, Dictionary<string,string?> prev) Dijkstra(Graph g, string source)
{
    var dist = new Dictionary<string,double>();
    var prev = new Dictionary<string,string?>();
    foreach (var v in g.Nodes) { dist[v] = double.PositiveInfinity; prev[v] = null; }
    dist[source] = 0;

    // Min-heap simulé : (distance, sommet). On retire les entries stale (deja finalisees).
    var pq = new PriorityQueue<string, double>();
    pq.Enqueue(source, 0);
    var finalized = new HashSet<string>();

    while (pq.Count > 0)
    {
        var u = pq.Dequeue();
        if (!finalized.Add(u)) continue;   // deja finalise -> skip (entry stale)
        foreach (var e in g.Adj[u])
        {
            double nd = dist[u] + e.Weight;
            if (nd < dist[e.To])
            {
                dist[e.To] = nd;
                prev[e.To] = u;
                pq.Enqueue(e.To, nd);
            }
        }
    }
    return (dist, prev);
}

// Reconstruire le chemin source -> cible depuis les predecesseurs.
public static List<string> ReconstructPath(Dictionary<string,string?> prev, string target)
{
    var path = new List<string>();
    string? cur = target;
    while (cur != null) { path.Add(cur); cur = prev[cur]; }
    path.Reverse();
    return path;
}

var (djDist, djPrev) = Dijkstra(g, "A");
var sb2 = new StringBuilder();
sb2.AppendLine("Dijkstra depuis A :");
foreach (var v in g.Nodes)
    sb2.AppendLine($"  dist(A -> {v}) = {djDist[v]}   chemin = [{string.Join(" -> ", ReconstructPath(djPrev, v))}]");
Show(sb2.ToString());
$"Verification analytique : A->F = 7 (A-B-E-F : 4+1+2), A->C = 7 (A-B-C : 4+3).".Display();
Dijkstra depuis A :
  dist(A -> A) = 0   chemin = [A]
  dist(A -> B) = 4   chemin = [A -> B]
  dist(A -> C) = 7   chemin = [A -> B -> C]
  dist(A -> D) = 2   chemin = [A -> D]
  dist(A -> E) = 5   chemin = [A -> B -> E]
  dist(A -> F) = 7   chemin = [A -> B -> E -> F]
Verification analytique : A->F = 7 (A-B-E-F : 4+1+2), A->C = 7 (A-B-C : 4+3).

4. Centralites — qui est important dans le reseau ?

Différentes centralites mesurent l’importance d’un sommet selon des critères distincts :

  • Degré : nombre de voisins. Simple, local.
  • Proximite (closeness) : \(C_C(v) = (n-1) / \sum_u d(v,u)\). Eleve si \(v\) est proche de tous les autres.
  • Intermediaire (betweenness) : \(C_B(v) = \sum_{s \neq v \neq t} \sigma_{st}(v)/\sigma_{st}\) — fraction des plus courts chemins passant par \(v\).
  • PageRank : vecteur propre de la matrice de transition (Page et al. 1999). Approxime par itération de puissance : \(\pi_{k+1} = (1-d)\mathbf{1}/n + d \, A^T \pi_k\), \(d=0{,}85\).
#nullable enable
// Centralite de degre (non-oriente : nombre de voisins).
public static Dictionary<string,int> DegreeCentrality(Graph g)
    => g.Nodes.ToDictionary(v => v, v => g.Adj[v].Count);

// Centralite de proximite : (n-1) / somme des distances depuis v.
public static Dictionary<string,double> ClosenessCentrality(Graph g)
{
    var res = new Dictionary<string,double>();
    int n = g.NodeCount;
    foreach (var v in g.Nodes)
    {
        var (d, _) = Dijkstra(g, v);
        double total = d.Values.Where(x => x != double.PositiveInfinity && x > 0).Sum();
        res[v] = total > 0 ? (n - 1) / total : 0;
    }
    return res;
}

// Centralite intermediaire : fraction des plus courts chemins (s,t) passant par v.
// Brandes algorithm (2001) — O(VE) au lieu de O(V^3).
public static Dictionary<string,double> BetweennessCentrality(Graph g)
{
    var bet = g.Nodes.ToDictionary(v => v, v => 0.0);
    foreach (var s in g.Nodes)
    {
        // single-source shortest paths (BFS sur graphe non ponderé equivalente via Dijkstra)
        var (dist, prev) = Dijkstra(g, s);
        // compter les plus courts chemins et l'intermediaire par accumulation des dependances.
        var stack = new List<string>();
        var P = g.Nodes.ToDictionary(v => v, v => new List<string>());
        var sigma = g.Nodes.ToDictionary(v => v, v => 0.0);
        sigma[s] = 1;
        // ordre par distance croissante
        var ordered = g.Nodes.OrderBy(v => dist[v]).ToList();
        foreach (var w in ordered)
        {
            if (dist[w] == double.PositiveInfinity) continue;
            stack.Add(w);
            foreach (var e in g.Adj[w])
                if (dist[e.To] == dist[w] + e.Weight)
                {
                    P[e.To].Add(w);
                    sigma[e.To] += sigma[w];
                }
        }
        var delta = g.Nodes.ToDictionary(v => v, v => 0.0);
        foreach (var w in Enumerable.Reverse(stack))
            foreach (var p in P[w])
                delta[p] += (sigma[p] / sigma[w]) * (1 + delta[w]);
            // (on retire le facteur s lui-meme : convention standard)
        foreach (var w in stack)
            if (w != s) bet[w] += delta[w];
    }
    // Normaliser pour graphe non-oriente : diviser par 2 (chaque paire comptee 2 fois).
    if (!g.Directed) foreach (var k in bet.Keys.ToList()) bet[k] /= 2;
    return bet;
}

// PageRank : iteration de puissance avec damping factor d=0.85.
public static Dictionary<string,double> PageRank(Graph g, double d = 0.85, int iters = 100)
{
    int n = g.NodeCount;
    // Construire la matrice de transition : M[j,i] = 1/outdeg(i) si i->j.
    var pr = g.Nodes.ToDictionary(v => v, v => 1.0 / n);
    var outDeg = g.Nodes.ToDictionary(v => v, v => g.Adj[v].Count);
    for (int it = 0; it < iters; it++)
    {
        var next = g.Nodes.ToDictionary(v => v, v => (1 - d) / n);
        foreach (var u in g.Nodes)
        {
            if (outDeg[u] == 0)
            {
                // dangling node : redistribuer uniformement.
                foreach (var v in g.Nodes) next[v] += d * pr[u] / n;
                continue;
            }
            foreach (var e in g.Adj[u])
                next[e.To] += d * pr[u] / outDeg[u];
        }
        pr = next;
    }
    return pr;
}

var deg = DegreeCentrality(g);
var clo = ClosenessCentrality(g);
var bet = BetweennessCentrality(g);
var pr  = PageRank(g);

var sb3 = new StringBuilder();
sb3.AppendLine($"{"Node",-5} {"Deg",-4} {"Closeness",-10} {"Between",-10} {"PageRank",-9}");
sb3.AppendLine(new string('-', 42));
foreach (var v in g.Nodes)
    sb3.AppendLine($"{v,-5} {deg[v],-4} {clo[v],-10:F3} {bet[v],-10:F3} {pr[v],-9:F4}");
Show(sb3.ToString());
$"Attendu : B a la betweenness la plus haute (5.0, carrefour central sur 5 plus courts chemins A-C/A-E/A-F/C-D/C-E), E 2e (3.0).".Display();
Node  Deg  Closeness  Between    PageRank 
------------------------------------------
A     2    0,200      2,000      0,1460   
B     3    0,294      5,000      0,2080   
C     2    0,179      0,000      0,1460   
D     2    0,161      0,000      0,1460   
E     3    0,278      3,000      0,2080   
F     2    0,200      0,000      0,1460   
Attendu : B a la betweenness la plus haute (5.0, carrefour central sur 5 plus courts chemins A-C/A-E/A-F/C-D/C-E), E 2e (3.0).

5. Flot maximum : Ford-Fulkerson

Le flot maximum de \(s\) a \(t\) sur un graphe de capacites : la quantite maximale qu’on peut acheminer. Ford-Fulkerson (1956) procede par augmentation :

  1. Tant qu’il existe un chemin augmentant de \(s\) a \(t\) dans le graphe residuel (trouve par BFS = variante Edmonds-Karp).
  2. Calculer la capacite residuelle minimale bottleneck sur ce chemin.
  3. Augmenter le flot de bottleneck, mettre a jour les aretes residuelles.

Theoreme max-flow/min-cut (Ford-Fulkerson) : le flot maximum = la capacite de la coupe minimale.

#nullable enable
// Flot maximum (Ford-Fulkerson / Edmonds-Karp : chemin augmentant via BFS).
public static double MaxFlow(Graph g, string source, string sink)
{
    // Graphe residuel : capacites[u][v].
    var cap = new Dictionary<string, Dictionary<string,double>>();
    foreach (var u in g.Nodes)
    {
        cap[u] = new();
        foreach (var e in g.Adj[u]) cap[u][e.To] = e.Weight;
        foreach (var v in g.Nodes) if (!cap[u].ContainsKey(v)) cap[u][v] = 0;
    }
    double maxFlow = 0;

    while (true)
    {
        // BFS pour un chemin augmentant dans le graphe residuel.
        var parent = new Dictionary<string,string?>();
        var q = new Queue<string>();
        q.Enqueue(source); parent[source] = null;
        while (q.Count > 0 && !parent.ContainsKey(sink))
        {
            var u = q.Dequeue();
            foreach (var v in cap[u].Keys)
                if (!parent.ContainsKey(v) && cap[u][v] > 0)
                {
                    parent[v] = u;
                    q.Enqueue(v);
                }
        }
        if (!parent.ContainsKey(sink)) break;   // plus de chemin augmentant

        // bottleneck = capacite residuelle minimale sur le chemin.
        double bottleneck = double.PositiveInfinity;
        string? cur = sink;
        while (parent[cur!] != null) { var p = parent[cur!]!; bottleneck = Math.Min(bottleneck, cap[p][cur!]); cur = p; }

        // augmenter.
        cur = sink;
        while (parent[cur!] != null) { var p = parent[cur!]!; cap[p][cur!] -= bottleneck; cap[cur!][p] += bottleneck; cur = p; }
        maxFlow += bottleneck;
    }
    return maxFlow;
}

// Graphe de test pour le flot (capacites). max-flow s->t = 5 (analytique).
//     s --4-- a --3-- t
//      \      |       /
//       2     1      2
//        \   |    /
//         b --2-- c
var flowG = new Graph(directed: true)
    .AddEdge("s","a",4).AddEdge("a","t",3)
    .AddEdge("s","b",2).AddEdge("b","c",2).AddEdge("c","t",2)
    .AddEdge("a","b",1);

double mf = MaxFlow(flowG, "s", "t");
$"Flot maximum s -> t = {mf}   (attendu : 5 = min(coupe sortie s=6, coupe entree t=5))".Display();
Flot maximum s -> t = 5   (attendu : 5 = min(coupe sortie s=6, coupe entree t=5))

5.1 Visualisation ASCII du graphe

En Python, networkx + matplotlib produisent une figure. En C# headless, on dessine le graphe en ASCII (les sommets et leurs aretes ponderees) pour valider la structure visuellement.

// Dessin ASCII du graphe : chaque noeud + ses aretes.
var sbDraw = new StringBuilder();
sbDraw.AppendLine("Graphe de test (reseau de villes) :");
sbDraw.AppendLine();
sbDraw.AppendLine("    A --4-- B --3-- C");
sbDraw.AppendLine("    |       |       |");
sbDraw.AppendLine("    2       1       5");
sbDraw.AppendLine("    |       |       |");
sbDraw.AppendLine("    D --6-- E --2-- F");
sbDraw.AppendLine();
sbDraw.AppendLine("Adjacency detail (verification structure) :");
foreach (var v in g.Nodes)
{
    var nbrs = g.Adj[v].OrderBy(e => e.To).Select(e => $"{e.To}({e.Weight})");
    sbDraw.AppendLine($"  [{v}] -> {string.Join(", ", nbrs)}");
}
Show(sbDraw.ToString());
Graphe de test (reseau de villes) :

    A --4-- B --3-- C
    |       |       |
    2       1       5
    |       |       |
    D --6-- E --2-- F

Adjacency detail (verification structure) :
  [A] -> B(4), D(2)
  [B] -> A(4), C(3), E(1)
  [C] -> B(3), F(5)
  [D] -> A(2), E(6)
  [E] -> B(1), D(6), F(2)
  [F] -> C(5), E(2)

Tranche 2 : parité lib-vs-lib via QuikGraph (moteur .NET natif)

La tranche 1 (§1-5.1) a valorisé la réimplémentation pédagogique : Graph, BFS/DFS, Dijkstra, centralités et Ford-Fulkerson écrits à la main. Cette tranche 2 valorise l’autre versant de la parité cross-langage — celui qu’occupe networkx côté Python — en invoquant un moteur .NET de production, la bibliothèque QuikGraph (déjà utilisée par le notebook suivant, Search-02c-QuikGraph).

L’enjeu n’est pas de remplacer la tranche 1 mais de la compléter : on rejoue la même instance concrète (le réseau de 6 villes, mêmes poids) avec le moteur réel, et l’on vérifie que les deux implémentations atteignent les mêmes réponses. C’est la parité lib vs lib — deux moteurs de production, un par écosystème (Python/networkx et .NET/QuikGraph) — que l’owner prend pour modèle nominal (PyMC vs Infer.NET dans la série Probas).

// Tranche 2 : QuikGraph 2.5.0 (moteur .NET natif) sur la MEME instance que la tranche 1.
#r "nuget: QuikGraph, 2.5.0"
using QuikGraph;
using QuikGraph.Algorithms.ShortestPath;
using QuikGraph.Algorithms.Observers;

// On reconstruit le reseau de 6 villes comme graphe oriente bidirectionnel
// (chaque arete non-orientee -> deux aretes orientees), memes poids qu'en tranche 1.
STaggedEdge<string,double> QE(string a, string b, double w) => new(a, b, w);
var qg = new[]
{
    QE("A","B",4), QE("B","A",4),  QE("B","C",3), QE("C","B",3),
    QE("A","D",2), QE("D","A",2),  QE("B","E",1), QE("E","B",1),
    QE("C","F",5), QE("F","C",5),  QE("D","E",6), QE("E","D",6),
    QE("E","F",2), QE("F","E",2)
}.ToBidirectionalGraph<string, STaggedEdge<string,double>>();

// Dijkstra via le moteur QuikGraph : un seul .Compute reconstitue l'arbre des plus courts chemins.
var dijkstra = new DijkstraShortestPathAlgorithm<string, STaggedEdge<string,double>>(qg, e => e.Tag);
// Observateur canonique : enregistre l'arbre des predecesseurs pendant le calcul (condition
// d'optimalite GetDistance(u) + poids(u, v) = GetDistance(v) encapsulee — parite tranche 1 §3).
var rec = new VertexPredecessorRecorderObserver<string, STaggedEdge<string, double>>();
rec.Attach(dijkstra);
dijkstra.Compute("A");

"QuikGraph 2.5.0 charge -- Dijkstra depuis A (distances) :".Display();
foreach (var v in qg.Vertices.OrderBy(x => x))
{
    double dv = dijkstra.GetDistance(v);
    $"  dist(A, {v}) = {dv:0.#}".Display();
}

// Reconstruction du chemin A -> F via l'observateur (API Attach + TryGetPath, aretes ->
// projection en sommets) — parite avec la tranche 1, section 3.
string Retrace(string target)
{
    if (target == "A") return "A";
    if (!rec.TryGetPath(target, out var aretes)) return target;
    return string.Join(" -> ", new[] { aretes.First().Source }.Concat(aretes.Select(a => a.Target)));
}
string cheminF = Retrace("F");
double distF = dijkstra.GetDistance("F");
$"Chemin A -> F (QuikGraph) : {cheminF} = {distF:0.#}".Display();
"Tranche 1 (from-scratch, section 3) : A -> B -> E -> F = 7  ==>  parite lib-vs-lib OK".Display();
Installing Packages
  • QuikGraph
QuikGraph 2.5.0 charge -- Dijkstra depuis A (distances) :
  dist(A, A) = 0
  dist(A, B) = 4
  dist(A, C) = 7
  dist(A, D) = 2
  dist(A, E) = 5
  dist(A, F) = 7
Chemin A -> F (QuikGraph) : A -> B -> E -> F = 7
Tranche 1 (from-scratch, section 3) : A -> B -> E -> F = 7  ==>  parite lib-vs-lib OK

Interprétation : deux implémentations, une seule réponse

Le moteur QuikGraph retrouve exactement les distances de la tranche 1 (dist(A,F) = 7, chemin A -> B -> E -> F) : la parité est vérifiée chiffre à chiffre, pas seulement annoncée. C’est tout l’intérêt de garder les deux tranches :

  • la tranche 1 rend l’algorithme lisible (on voit le tas de priorité, la relaxation, la reconstruction du chemin) — c’est l’apport pédagogique ;
  • la tranche 2 délègue au moteur de production (QuikGraph.Algorithms : Dijkstra, Bellman-Ford, A*, Kruskal, flot maximum Edmonds-Karp) — c’est l’apport ingénieur, le même rôle que networkx joue côté Python.

QuikGraph apporte en sus, sans code supplémentaire de notre part, des algorithmes que la tranche 1 n’implémente pas (arbre couvrant minimum de Kruskal, composantes connexes, tri topologique). La parité lib vs lib avec le jumeau Python est ainsi atteinte du côté .NET par le moteur natif, tandis que le jumeau Python l’atteint du sien par networkx.

6. Exercices

Convention C.1 : les stubs s’executent sans erreur (jamais throw). Remplir le corps, re-executer, verifier.

Exercice 1 — Detection de cycles (DFS 3 couleurs)

Implementer la detection de cycles dans un graphe oriente via DFS a 3 couleurs (BLANC/GRIS/NOIR). Un cycle existe si on atteint un sommet GRIS pendant le DFS.

Indice : marquer GRIS en entrant, NOIR en sortant ; si un voisin est GRIS -> cycle.

#nullable enable
// Exercice 1 : detection de cycle (DFS 3 couleurs) sur graphe oriente.
// TODO etudiant : retourner true si le graphe contient un cycle.
static bool HasCycle(Graph g)
{
    // Indice : BLANC=non visite, GRIS=en cours (dans la pile DFS), NOIR=termine.
    //          si on atteint un voisin GRIS -> cycle.
    return false;   // TODO etudiant
}

// Tests (sur 2 graphes : un sans cycle, un avec).
var acyclic = new Graph(directed: true).AddEdge("a","b").AddEdge("b","c").AddEdge("a","c");
var cyclic  = new Graph(directed: true).AddEdge("a","b").AddEdge("b","c").AddEdge("c","a");
$"HasCycle(acyclique) = {HasCycle(acyclic)}   (attendu False)".Display();
$"HasCycle(cyclique)  = {HasCycle(cyclic)}   (attendu True)".Display();
HasCycle(acyclique) = False   (attendu False)
HasCycle(cyclique)  = False   (attendu True)

Exercice 2 — A* avec heuristique

Implementer A* (A-star) sur un graphe pondere avec une heuristique admissible \(h(v) \leq h^*(v)\) (distance reelle vers la cible). A* etend Dijkstra en priorisant les sommets par g(v) + h(v).

Indice : même structure que Dijkstra, mais la priority queue ordonne par dist[u] + h(u).

#nullable enable
// Exercice 2 : A* avec heuristique admissible.
// TODO etudiant : plus court chemin source->target avec heuristique.
static double AStar(Graph g, string source, string target, Dictionary<string,double> heuristic)
{
    // Indice : priority queue ordonnee par dist[u] + h[u] ; stop des que target est finalise.
    return 0.0;   // TODO etudiant
}

$"Exercice a completer (tester avec heuristique = distance euclidienne approchee vers F).".Display();
Exercice a completer (tester avec heuristique = distance euclidienne approchee vers F).

Exercice 3 — Detection de communautes (Louvain)

Louvain (Blondel et al. 2008) est l’algorithme SOTA de detection de communautes (maximisation de modularite). networkx l’offre en une ligne ; l’implementer from-scratch depasse le coeur de ce notebook.

Indice : la modularite \(Q = \frac{1}{2m}\sum_{ij}\left[A_{ij} - \frac{k_i k_j}{2m}\right]\delta(c_i, c_j)\). Louvain optimise \(Q\) en deux phases repetees : (1) deplacer chaque noeud vers la communaute qui maximise le gain de modularite, (2) construire le meta-graphe des communautes.

#nullable enable
// Exercice 3 : modularite d'un partitionnement (brique de base de Louvain).
// TODO etudiant : calculer Q pour un partitionnement donne.
static double Modularity(Graph g, Dictionary<string,int> community)
{
    // Indice : Q = (1/2m) * sum_ij [ A_ij - k_i*k_j/(2m) ] * delta(c_i, c_j)
    return 0.0;   // TODO etudiant
}

$"Exercice a completer (Louvain complet = meta-graphe + iteration, hors scope coeur).".Display();
Exercice a completer (Louvain complet = meta-graphe + iteration, hors scope coeur).

Conclusion

Ce que vous avez appris

  • Modèle de graphe — adjacency list ponderee (oriente / non-oriente), la structure de données universelle.
  • Parcours BFS / DFS — queue FIFO vs pile LIFO ; BFS donne les plus courts chemins en nombre d’aretes.
  • Dijkstra — plus courts chemins a poids positifs via priority queue et relaxation des aretes.
  • Centralites — degré (local), proximite (moyenne), intermediaire (carrefour, algorithme de Brandes), PageRank (vecteur propre par itération de puissance).
  • Flot maximum — Ford-Fulkerson / Edmonds-Karp : chemins augmentants BFS dans le graphe residuel ; theoreme max-flow/min-cut.

Pont avec la version Python

La version Python (Search-02b-NetworkX.ipynb) utilise networkx (200+ algorithmes, boite noire industrielle) et matplotlib pour la visualisation. Ce twin C# (BCL .NET 9, 0 NuGet) reimplemente from-scratch les moteurs centraux (adjacency list, BFS/DFS, Dijkstra, centralites, Ford-Fulkerson) — les internes algorithmiques sont visibles. networkx reste l’outil SOTA cote Python (RECOVERABLE-MACHINE) : pas d’equivalent C# du même niveau en une seule lib pedagogique. Louvain (communautes) et le matching pondere (Hongrois), couverts par networkx cote Python, sont laisses en exercices (complexite au-dela du coeur).

Parite #4956

Twin de parite legitime (Prong B) : les deux langages couvrent les mêmes concepts (graphe, parcours, plus courts chemins, centralites, flot). Ou Python s’appuie sur networkx, le C# rend visible la mecanique de chaque algorithme. Le notebook Search-03-Informed-CSharp couvre A* en detail (point de complement).

Marathon #4956 (parite .NET <-> Python).

Retour au sommet