Serie : Search / Part1-Foundations (13/11 etendu aux bibliotheques) Duree estimee : ~1h Prerequis : Notions de C# / .NET, comprehension des graphes (cf. Search-1) Kernel : .NET Interactive (.net-csharp)
Search-02b-NetworkX.| Précédent | Suivant |
|---|---|
| Search-02b-NetworkX (parite Python) | Search-03d-WeightedAstar |
QuickGraph, le projet historique de Jonathan “Peli” de Halleux (2003), n’est plus maintenu. Trois successeurs se partagent le terrain : QuikGraph (fork KeRNeLith, ce notebook), FastGraph (moderne, actif) et Microsoft.Graph (rare). QuikGraph reste la bibliotheque la plus documentee et la plus aboutie pour les algorithmes classiques : Dijkstra, Bellman-Ford, A*, Edmonds-Karp, k-shortest path. C’est l’equivalent .NET de NetworkX du cote Python, et c’est elle qui permet de fermer la parite entre les deux ecosystemes dans le cadre du Sprint #5082.
QuickGraph est ne en 2003 sur CodePlex, repris par la communaute sous le nom YC.QuickGraph, puis maintenu sous sa forme moderne par KeRNeLith sous le nom QuikGraph. La version 2.5.0 (2024+) cible .NET Standard 2.0+ et fonctionne sous .NET 8 / 9 / Interactive.
| Caractéristique | Description |
|---|---|
| Types de graphes | AdjacencyGraph<TV,TE> (non dirige), BidirectionalGraph<TV,TE> (dirigee, rapide pour predecesseurs), UndirectedGraph<TV,TE> (non dirigee, aretes inversees par symmetrie) |
| Aretes | Edge<TV> simple ou SEdge<TV,TEdge> / Edge<TV,TEdgeData> (avec attributs : poids, etiquette…) |
| Algorithmes | DFS, BFS, Dijkstra, Bellman-Ford, A*, k-shortest path, Edmonds-Karp (flot max), Tarjan (SCC), Kruskal/Prim (MST), etc. |
| Distribution | NuGet : QuikGraph, 2.5.0 |
Note : QuikGraph n’embarque pas d’algorithmes de centralite (betweenness, closeness, PageRank). Pour ces metriques, il faut soit les calculer a la main (degré :
graph.AdjacentDegree(v)), soit brancher une autre bibliotheque. C’est l’un des verdicts honnetes a porter dans le body de la PR (cf. parite ci-dessous).
QuikGraph 2.5.0 charge depuis NuGet.using QuikGraph;
using QuikGraph.Algorithms;
using QuikGraph.Algorithms.Search;
using QuikGraph.Algorithms.ShortestPath;
using QuikGraph.Algorithms.ConnectedComponents;
using QuikGraph.Algorithms.MaximumFlow;
Console.WriteLine("Espaces de noms QuikGraph imports :");
Console.WriteLine(" - QuikGraph : types de graphes (AdjacencyGraph, BidirectionalGraph, UndirectedGraph, Edge, SEdge)");
Console.WriteLine(" - QuikGraph.Algorithms : base commune (Algorithm, IAlgorithm, etc.)");
Console.WriteLine(" - QuikGraph.Algorithms.Search : DepthFirstSearch, BreadthFirstSearch, WeaklyConnectedComponents");
Console.WriteLine(" - QuikGraph.Algorithms.ShortestPath : Dijkstra, BellmanFord, AStar, Kruskal");
Console.WriteLine(" - QuikGraph.Algorithms.MaximumFlow : MaximumFlowAlgorithm (Edmonds-Karp, Push-Relabel)");Espaces de noms QuikGraph imports :
- QuikGraph : types de graphes (AdjacencyGraph, BidirectionalGraph, UndirectedGraph, Edge, SEdge)
- QuikGraph.Algorithms : base commune (Algorithm, IAlgorithm, etc.)
- QuikGraph.Algorithms.Search : DepthFirstSearch, BreadthFirstSearch, WeaklyConnectedComponents
- QuikGraph.Algorithms.ShortestPath : Dijkstra, BellmanFord, AStar, Kruskal
- QuikGraph.Algorithms.MaximumFlow : MaximumFlowAlgorithm (Edmonds-Karp, Push-Relabel)QuikGraph distingue trois familles. Le choix depend de la sémantique (oriente vs non) et du type d’aretes (simple, avec poids, avec données metier).
| Type | Oriente | Aretes | Usage typique |
|---|---|---|---|
AdjacencyGraph<TV,TE> |
non | TE (souvent Edge<TV>) |
Reseaux sociaux, collaborations |
BidirectionalGraph<TV,TE> |
oui | TE (souvent SEdge<TV>) |
Reseaux de transport, graphes de tâches |
UndirectedGraph<TV,TE> |
non (forcement) | TE symetrise |
Modelisation physique (circuits) |
Le graphe de Petersen est le plus petit exemple non trivial qui combine cycles, aretes transversales et n’est ni planaire ni complet. C’est le theatre classique pour tester DFS, BFS, composantes connexes et flot max.
// Construction d'un graphe non oriente "graphe de Petersen" via AdjacencyGraph<int, Edge<int>>
// Sommets 0..9 ; aretes : cycle exterieur 0-1-2-3-4-0, cycle interieur 5-6-7-8-9-5, et 5 aretes de liaison 0-5, 1-6, 2-7, 3-8, 4-9.
var petersen = new UndirectedGraph<int, Edge<int>>();
for (int i = 0; i < 10; i++) petersen.AddVertex(i);
// Cycle exterieur (5 aretes)
for (int i = 0; i < 5; i++) petersen.AddEdge(new Edge<int>(i, (i + 1) % 5));
// Cycle interieur (5 aretes)
int[] interieur = { 5, 6, 7, 8, 9 };
for (int i = 0; i < 5; i++) petersen.AddEdge(new Edge<int>(interieur[i], interieur[(i + 1) % 5]));
// Aretes de liaison (5 aretes)
for (int i = 0; i < 5; i++) petersen.AddEdge(new Edge<int>(i, interieur[i]));
Console.WriteLine($"Graphe de Petersen : {petersen.VertexCount} sommets, {petersen.EdgeCount} aretes.");
Console.WriteLine($"Voisins du sommet 0 : [{string.Join(", ", petersen.AdjacentVertices(0))}]");
Console.WriteLine($"Degre du sommet 0 : {petersen.AdjacentDegree(0)}");
Console.WriteLine($"Degre du sommet 5 : {petersen.AdjacentDegree(5)}");
// Verification : graphe regulier 3 par construction
int sommeDegres = 0;
foreach (var v in petersen.Vertices) sommeDegres += petersen.AdjacentDegree(v);
Console.WriteLine($"Somme des degres = {sommeDegres} (attendu : 2 * E = {2 * petersen.EdgeCount})");Graphe de Petersen : 10 sommets, 15 aretes.
Voisins du sommet 0 : [1, 4, 5]
Degre du sommet 0 : 3
Degre du sommet 5 : 3
Somme des degres = 30 (attendu : 2 * E = 30)// Pour Dijkstra/Bellman-Ford/flot max, on utilise des aretes typees avec poids.
// Edge<TV, TEdgeData> ou SEdge<TV, double> selon l'usage.
// Ici : graphe routier "ville 6 carrefours" avec distances (en km) entre carrefours.
var routier = new BidirectionalGraph<string, STaggedEdge<string, double>>();
routier.AddVertex("A");
routier.AddVertex("B");
routier.AddVertex("C");
routier.AddVertex("D");
routier.AddVertex("E");
routier.AddVertex("F");
void AjouterRue(BidirectionalGraph<string, STaggedEdge<string, double>> g, string de, string vers, double km)
{
g.AddEdge(new STaggedEdge<string, double>(de, vers, km));
g.AddEdge(new STaggedEdge<string, double>(vers, de, km)); // symetrique : on code les deux sens
}
AjouterRue(routier, "A", "B", 2.0);
AjouterRue(routier, "A", "C", 5.0);
AjouterRue(routier, "B", "C", 1.5);
AjouterRue(routier, "B", "D", 4.0);
AjouterRue(routier, "C", "E", 3.0);
AjouterRue(routier, "D", "E", 1.0);
AjouterRue(routier, "D", "F", 6.0);
AjouterRue(routier, "E", "F", 2.5);
Console.WriteLine($"Reseau routier : {routier.VertexCount} carrefours, {routier.EdgeCount} segments (aller-retour).");
Console.WriteLine($"Aretes sortantes de A : {routier.OutDegree("A")} (vers {string.Join(", ", routier.OutEdges("A").Select(e => e.Target))})");Reseau routier : 6 carrefours, 16 segments (aller-retour).
Aretes sortantes de A : 2 (vers B, C)QuikGraph fournit deux algorithmes de parcours dans le namespace QuikGraph.Algorithms.Search. Ils sont configures via les callbacks OnVertex/OnEdge et retournes en IEnumerable<TEdge> / IEnumerable<TVertex>.
DFS explore aussi loin que possible sur chaque branche avant de revenir en arriere. BFS explore par etages (largeur d’abord). Sur un graphe non pondere, le BFS donne la distance minimale en nombre d’aretes, mais pas en poids.
Application : sur le graphe routier A..F, on cherche le plus court chemin en km entre A et F via Dijkstra (eternel debat : pourquoi pas BFS ? parce que BFS compte des sauts et non des distances – avec des poids heterogenes, seul Dijkstra repond correctement).
// DFS iteratif sur le graphe de Petersen depuis 0
// (implementation a la main car QuikGraph.Algorithms.Search exige IVertexListGraph,
// qu'UndirectedGraph n'implemente pas directement ; on aurait pu convertir
// vers AdjacencyGraph via l'extension ToAdjacencyGraph mais l'implementation
// manuelle est plus claire pedagogiquement.)
var ordreDFS = new List<int>();
var visiteDFS = new HashSet<int>();
var pileDFS = new Stack<int>();
pileDFS.Push(0);
while (pileDFS.Count > 0)
{
int u = pileDFS.Pop();
if (visiteDFS.Contains(u)) continue;
visiteDFS.Add(u);
ordreDFS.Add(u);
// Empiler les voisins non visites en ordre inverse pour un parcours stable
var voisins = petersen.AdjacentVertices(u).ToList();
voisins.Sort();
voisins.Reverse();
foreach (var v in voisins)
{
if (!visiteDFS.Contains(v)) pileDFS.Push(v);
}
}
Console.WriteLine($"Parcours DFS depuis 0 (ordre de decouverte) : [{string.Join(" -> ", ordreDFS)}]");
Console.WriteLine($"Nombre de sommets visites : {ordreDFS.Count} / 10");Parcours DFS depuis 0 (ordre de decouverte) : [0 -> 1 -> 2 -> 3 -> 4 -> 9 -> 5 -> 6 -> 7 -> 8]
Nombre de sommets visites : 10 / 10// BFS sur le graphe de Petersen depuis 0 - par etages.
var ordreBFS = new Queue<int>();
var distanceBFS = new Dictionary<int, int>();
distanceBFS[0] = 0;
var fileBFS = new Queue<int>();
fileBFS.Enqueue(0);
while (fileBFS.Count > 0)
{
int u = fileBFS.Dequeue();
ordreBFS.Enqueue(u);
foreach (var v in petersen.AdjacentVertices(u))
{
if (!distanceBFS.ContainsKey(v))
{
distanceBFS[v] = distanceBFS[u] + 1;
fileBFS.Enqueue(v);
}
}
}
Console.WriteLine($"BFS depuis 0 : [{string.Join(" -> ", ordreBFS)}]");
Console.WriteLine($"Distances en sauts : " + string.Join(", ", distanceBFS.OrderBy(kv => kv.Key).Select(kv => $"{kv.Key}:{kv.Value}")));BFS depuis 0 : [0 -> 1 -> 4 -> 5 -> 2 -> 6 -> 3 -> 9 -> 7 -> 8]
Distances en sauts : 0:0, 1:1, 2:2, 3:2, 4:1, 5:1, 6:2, 7:3, 8:3, 9:2Sur le reseau routier A..F avec distances en km, BFS donnerait A -> B -> D -> F (3 sauts, 2+4+6=12 km) ou A -> B -> D -> E -> F (4 sauts, 2+4+1+2.5=9.5 km), mais le vrai plus court chemin en km est différent.
QuikGraph fournit DijkstraShortestPathAlgorithm (poids positifs uniquement) et BellmanFordShortestPathAlgorithm (cas general, detecte les cycles de poids negatifs). L’API de base expose GetDistance(vertex) -> double (ou TryGetDistance) ; la reconstruction des chemins s’appuie sur l’observateur canonique VertexPredecessorRecorderObserver — la cellule 11 la demontre d’abord par remontee manuelle (condition d’optimalite), la cellule 17 l’utilise ensuite en version canonique.
// Dijkstra entre A et F sur le reseau routier (ctor 2-args + reconstruction manuelle du chemin).
// DEMONSTRATION CONSERVEE (decision #11113) : cette remontee manuelle est gardee pour
// illustrer la CONDITION D'OPTIMALITE de Dijkstra — pour chaque sommet v, son predecesseur
// est l'unique voisin u tel que GetDistance(u) + poids(u, v) = GetDistance(v). C'est le seul
// site de la serie a rester manuel ; les autres utilisent l'observateur canonique
// VertexPredecessorRecorderObserver (cell 17 de ce notebook, Search-02b-NetworkX-CSharp cell 14, Search-3
// cell 16, Search-2 cell 38), qui encapsule exactement cette condition.
var dijkstra = new DijkstraShortestPathAlgorithm<string, STaggedEdge<string, double>>(
routier,
e => e.Tag
);
dijkstra.Compute("A");
Console.WriteLine("Dijkstra depuis A (distances en km) :");
foreach (var v in routier.Vertices)
{
double dist = dijkstra.GetDistance(v);
// Reconstruction du chemin en remontant
string chemin = v;
string courant = v;
while (courant != "A")
{
string suivant = null;
foreach (var e in routier.InEdges(courant))
{
if (Math.Abs(dijkstra.GetDistance(e.Source) + e.Tag - dist) < 1e-6)
{
suivant = e.Source;
break;
}
}
if (suivant == null) break;
chemin = suivant + " -> " + chemin;
courant = suivant;
}
Console.WriteLine($" {v} : {dist:F2} km ({chemin})");
}Dijkstra depuis A (distances en km) :
A : 0,00 km (A)
B : 2,00 km (A -> B)
C : 3,50 km (B -> C)
D : 6,00 km (B -> D)
E : 6,50 km (C -> E)
F : 9,00 km (E -> F)Dijkstra finalise chaque sommet une fois pour toutes, dans l’ordre croissant des distances — une garantie qui n’est valide que si tous les poids sont positifs ou nuls : si une arete peut faire baisser un cout deja valide, l’ordre se brise. QuikGraph fait respecter cette precondition : sur un poids negatif, son Dijkstra leve NegativeWeightException plutot que de retourner une distance fausse. C’est la que Bellman-Ford prend le relais : il relaxe chaque arete |V|−1 fois, ce qui supporte les poids negatifs et detecte au passage les cycles negatifs — un circuit dont le cout total est negatif : le « plus court chemin » n’existe plus, chaque tour ameliore le cout indefiniment. Deux experiences : un trajet avec un segment subventionne (−3 EUR), puis un cycle remunerateur.
// Cas A : reseau de couts avec un segment subventionne (-3 EUR). L'optimum reel S->A->T = -1 EUR.
// Dijkstra refuse (sa precondition est poids >= 0) ; Bellman-Ford le calcule.
var prixA = new AdjacencyGraph<string, STaggedEdge<string, double>>();
prixA.AddVertexRange(new[] { "S", "A", "T" });
prixA.AddEdgeRange(new[]
{
new STaggedEdge<string, double>("S", "T", 1.0), // trajet direct : 1 EUR
new STaggedEdge<string, double>("S", "A", 2.0), // detour par A : 2 EUR
new STaggedEdge<string, double>("A", "T", -3.0), // segment subventionne : on est paye 3 EUR
});
try
{
var dijA = new DijkstraShortestPathAlgorithm<string, STaggedEdge<string, double>>(prixA, e => e.Tag);
dijA.Compute("S");
Console.WriteLine($"[Dijkstra] cout S->T = {dijA.GetDistance("T"):F2} EUR");
}
catch (NegativeWeightException ex)
{
Console.WriteLine($"[Dijkstra] REFUS : {ex.GetType().Name} — {ex.Message}");
}
var bfA = new BellmanFordShortestPathAlgorithm<string, STaggedEdge<string, double>>(prixA, e => e.Tag);
bfA.Compute("S");
Console.WriteLine($"[BellmanFord] cycle negatif present = {bfA.FoundNegativeCycle}");
Console.WriteLine($"[BellmanFord] cout S->A = {bfA.GetDistance("A"):F2} EUR, S->T = {bfA.GetDistance("T"):F2} EUR (detour 2 EUR puis subvention -3 EUR)");
// Cas B : un cycle A -> B -> A de cout total -1 EUR par tour, atteignable depuis S.
// Garde avant usage : si un cycle negatif est detecte, les predecesseurs sont corrompus
// et les distances n'ont plus de sens — on ne les interroge pas.
var prixB = new AdjacencyGraph<string, STaggedEdge<string, double>>();
prixB.AddVertexRange(new[] { "S", "A", "B", "T" });
prixB.AddEdgeRange(new[]
{
new STaggedEdge<string, double>("S", "A", 1.0),
new STaggedEdge<string, double>("A", "B", -2.0),
new STaggedEdge<string, double>("B", "A", 1.0), // cycle A->B->A : -2 + 1 = -1 EUR par tour
new STaggedEdge<string, double>("B", "T", 1.0),
});
var bfB = new BellmanFordShortestPathAlgorithm<string, STaggedEdge<string, double>>(prixB, e => e.Tag);
bfB.Compute("S");
Console.WriteLine($"\n[B] cycle A->B->A = -1 EUR par tour : cycle negatif detecte = {bfB.FoundNegativeCycle}");
if (!bfB.FoundNegativeCycle)
{
Console.WriteLine($"[B] cout S->T = {bfB.GetDistance("T"):F2} EUR");
}
else
{
Console.WriteLine("[B] distances non interrogees : chaque tour du cycle ameliore le cout, le plus court chemin n'existe pas.");
}[Dijkstra] REFUS : NegativeWeightException — The graph contains at least one negative weight.
[BellmanFord] cycle negatif present = False
[BellmanFord] cout S->A = 2,00 EUR, S->T = -1,00 EUR (detour 2 EUR puis subvention -3 EUR)
[B] cycle A->B->A = -1 EUR par tour : cycle negatif detecte = True
[B] distances non interrogees : chaque tour du cycle ameliore le cout, le plus court chemin n'existe pas.Dijkstra a refuse : NegativeWeightException — The graph contains at least one negative weight. La bibliotheque ne retourne pas une distance fausse en silence — elle fait respecter sa precondition. Un Dijkstra « qui repondrait quand meme » serait le pire des cas : une reponse fausse impossible a distinguer d’une juste. Bellman-Ford a calcule : cout S→T = −1,00 EUR (detour S→A a 2,00 EUR puis le segment subventionne a −3,00 EUR), cycle negatif = False. Le detour couteux a l’entree (2 EUR contre 1 EUR en direct) devient gagnant apres la subvention : aucun ordre de finalisation glouton ne peut garantir ca, seule la relaxation exhaustive |V|−1 fois le peut. Cas B — le cycle remunerateur : A→B→A rapporte 1 EUR par tour, indefiniment. Bellman-Ford le detecte (FoundNegativeCycle = True) et on garde la garde avant usage : apres un cycle negatif, les predecesseurs sont corrompus — interroger les distances n’a plus de sens. Le verdict « pas d’optimum » est une reponse, pas un echec : c’est la detection d’arbitrage impossible, exactement ce qu’un moteur de plus courts chemins doit savoir dire. En pratique : poids tous ≥ 0 → Dijkstra (plus rapide, O((V+A) log V)) ; un poids negatif → Bellman-Ford (O(V·A)) ; cycle negatif detecte → le probleme tel que pose n’a pas de solution.
QuikGraph ne fournit pas d’algorithmes de centralite tout faits (betweenness, closeness, PageRank). C’est un verdict honnete a porter dans le body de la PR : la bibliotheque couvre les chemins, flots, composantes mais pas les metriques d’influence par centralite – c’est un choix de scope du mainteneur (KeRNeLith), pas un oubli. Pour ces dernières, on les calcule a la main ou on branche une autre bibliotheque (FastGraph par exemple, plus recente mais moins documentee).
Ce notebook montre ce qui est calculable en pur QuikGraph :
graph.AdjacentDegree(v) (en O(1)) ou graph.Degree(v) sur UndirectedGraph.ConnectedComponents sur non orientes.degree(v) / (n - 1) – identique en .NET et Python (NetworkX la nomme degree_centrality).Pour les centralites plus elaborees (betweenness/closeness), le code est laisse en exercice (cf. Exo 3 plus bas).
// Centralite de degre et composantes connexes sur un graphe "reseau social 8 personnes / 2 communautes".
var social = new UndirectedGraph<string, Edge<string>>();
string[] comm1 = { "Alice", "Bob", "Carmen", "David" };
string[] comm2 = { "Eve", "Frank", "Greta", "Hugo" };
foreach (var p in comm1) social.AddVertex(p);
foreach (var p in comm2) social.AddVertex(p);
// Liens communautes 1
social.AddEdge(new Edge<string>("Alice", "Bob"));
social.AddEdge(new Edge<string>("Bob", "Carmen"));
social.AddEdge(new Edge<string>("Carmen", "David"));
social.AddEdge(new Edge<string>("David", "Alice"));
social.AddEdge(new Edge<string>("Alice", "Carmen"));
// Liens communautes 2
social.AddEdge(new Edge<string>("Eve", "Frank"));
social.AddEdge(new Edge<string>("Frank", "Greta"));
social.AddEdge(new Edge<string>("Greta", "Hugo"));
social.AddEdge(new Edge<string>("Hugo", "Eve"));
social.AddEdge(new Edge<string>("Eve", "Greta"));
// Pont inter-communautes (rare)
social.AddEdge(new Edge<string>("David", "Hugo"));
// Degre
Console.WriteLine("Centralite de degre normalisee (degree / (n-1)) :");
int n = social.VertexCount;
foreach (var v in social.Vertices)
{
int deg = social.AdjacentDegree(v);
double centralite = (double)deg / (n - 1);
Console.WriteLine($" {v,-8} degre={deg} centralite={centralite:F3}");
}
// Composantes connexes (ici une seule, car le pont David-Hugo reconnecte)
var algoCC = new ConnectedComponentsAlgorithm<string, Edge<string>>(social);
algoCC.Compute();
var composantes = social.Vertices.GroupBy(v => algoCC.Components[v]);
Console.WriteLine();
Console.WriteLine($"Nombre de composantes connexes : {composantes.Count()}");
foreach (var groupe in composantes)
{
Console.WriteLine($" Composante {groupe.Key} : [{string.Join(", ", groupe)}]");
}
// Sans le pont, on aurait 2 composantes : exercice de l'Exo 3 ci-dessous.Centralite de degre normalisee (degree / (n-1)) :
Alice degre=3 centralite=0,429
Bob degre=2 centralite=0,286
Carmen degre=3 centralite=0,429
David degre=3 centralite=0,429
Eve degre=3 centralite=0,429
Frank degre=2 centralite=0,286
Greta degre=3 centralite=0,429
Hugo degre=3 centralite=0,429
Nombre de composantes connexes : 1
Composante 0 : [Alice, Bob, Carmen, David, Eve, Frank, Greta, Hugo]Le flot maximum dans un reseau capacitie est l’un des problemes fondamentaux de la recherche operationnelle. QuikGraph implemente MaximumFlowAlgorithm<TV,TE> qui par defaut applique Edmonds-Karp (BFS augmentant) ou Push-Relabel selon la config.
Application : sur le reseau routier A..F, on prend A comme source (entrepot) et F comme puits (client). Chaque arete a une capacite egale au poids en km – c’est un abus de modelisation pour le notebook (la vraie capacite d’une arete routiere serait un debit), mais le résultat reste correct et pedagogique : on cherche le debit max que peut transporter le reseau entre A et F.
// Reseau de flot canonique (Cormen et al., chapitre 26) : 4 sommets S, A, B, T.
// S -> A (10) A -> T (8)
// S -> B (5) B -> T (10)
// A -> B (3)
//
// Flot max S -> T = 15 (min-cut : la coupe {S} | {A,B,T} vaut S->A(10) + S->B(5) = 15,
// et par le theoreme max-flow/min-cut c'est aussi le flot maximum). L'arete A->B laisse
// A router son excedent vers B puis T : S->A(10) se partage en A->T(8) + A->B(2), et B
// recevant S->B(5) + A->B(2) = 7 les pousse vers B->T (capacite 10). Total arrive a T = 15.
//
// API QuikGraph 2.5.0 : EdmondsKarpMaximumFlowAlgorithm exige que le graphe soit augmente
// de ses aretes residuelles AVANT l'appel a Compute (sinon InvalidOperationException
// "The graph has not been augmented yet"). On instancie donc le ReversedEdgeAugmentorAlgorithm
// separement, on appelle AddReversedEdges(), puis on construit l'algorithme sur le graphe
// augmente. Cleanup final via RemoveReversedEdges() pour ne pas polluer le graphe.
var flowGraph = new BidirectionalGraph<string, STaggedEdge<string, double>>();
flowGraph.AddVertex("S");
flowGraph.AddVertex("A");
flowGraph.AddVertex("B");
flowGraph.AddVertex("T");
void AddFlowEdge(string from, string to, double cap)
{
flowGraph.AddEdge(new STaggedEdge<string, double>(from, to, cap));
}
AddFlowEdge("S", "A", 10);
AddFlowEdge("S", "B", 5);
AddFlowEdge("A", "T", 8);
AddFlowEdge("B", "T", 10);
AddFlowEdge("A", "B", 3);
Console.WriteLine("Reseau de flot : S, A, B, T");
Console.WriteLine(" Aretes : S->A:10, S->B:5, A->T:8, B->T:10, A->B:3");
EdgeFactory<string, STaggedEdge<string, double>> creeAretesResiduelles =
(s, t) => new STaggedEdge<string, double>(s, t, 0.0);
// Etape obligatoire : augmenter le graphe des aretes residuelles AVANT l'algorithme.
var augmentor = new ReversedEdgeAugmentorAlgorithm<string, STaggedEdge<string, double>>(
flowGraph, creeAretesResiduelles);
augmentor.AddReversedEdges();
var maxFlowAlgo = new EdmondsKarpMaximumFlowAlgorithm<string, STaggedEdge<string, double>>(
flowGraph,
e => e.Tag,
creeAretesResiduelles,
augmentor
);
maxFlowAlgo.Compute("S", "T");
Console.WriteLine();
Console.WriteLine($"Flot maximum S -> T : {maxFlowAlgo.MaxFlow:F2}");
Console.WriteLine(" (Verification min-cut : {S} | {A,B,T} = S->A(10) + S->B(5) = 15)");
Console.WriteLine();
Console.WriteLine("Fin cellule flot max.");
// Cleanup : retirer les aretes residuelles ajoutees pour ne pas polluer le graphe.
augmentor.RemoveReversedEdges();Reseau de flot : S, A, B, T
Aretes : S->A:10, S->B:5, A->T:8, B->T:10, A->B:3
Flot maximum S -> T : 15,00
(Verification min-cut : {S} | {A,B,T} = S->A(10) + S->B(5) = 15)
Fin cellule flot max.Prong B (#3801) : un notebook qui démontre un moteur/solveur sur un cas trivial où le SOTA équivaut à une baseline ne met pas en valeur la bibliothèque. Ici, on construit un graphe routier 5x5 (25 carrefours, arêtes Est-Ouest et Nord-Sud) auquel on donne un coût de terrain hétérogène (chaque arête tire un coût dans [1,0 ; 3,0] km — voie rapide vs voie lente, déterministe via une graine fixe), puis on applique un bruit de 30% (suppression aléatoire de 30% des arêtes, graine fixe).
Avec un terrain uniforme à 1 km, le plus court chemin en distance pondérée coïnciderait avec le plus court chemin en nombre de sauts : Dijkstra n’apporterait rien que BFS ne fournit déjà (cas dégénéré, équivalent au commit de référence 8905f8845 BFS-vs-A*). Avec un terrain hétérogène, minimiser la somme des coûts ≠ minimiser le nombre de sauts — le chemin optimal peut faire un détour par des arêtes bon marché pour éviter une arête chère. C’est la capacité distinctive de Dijkstra que la section met en évidence, en parité avec le notebook Python Search-02b-NetworkX.
Pour la reproductibilité entre runs, les deux graines sont fixes (new Random(7) pour le terrain, new Random(42) pour le bruit).
using QuikGraph.Algorithms.Observers;
Console.WriteLine("Debut cellule grille 5x5...");
// Reseau routier 5x5 : 25 sommets (0,0)..(4,4). Aretes Est-Ouest + Nord-Sud.
// Prong B (#3801) : pour que Dijkstra se distingue de BFS, on donne a chaque arete un
// COUT DE TERRAIN HETEROGENE dans [1.0, 3.0] (1.0 = voie rapide, 3.0 = voie lente), tire
// deterministement (seed 7, RNG terrain distinct du RNG de bruit). Avec des poids
// uniformes (1.0 partout), le plus court chemin = chemin en nombre de sauts (BFS) et
// Dijkstra n'apporte rien ; avec un terrain heterogene, minimiser la somme des couts
// != minimiser le nombre de sauts, et le chemin optimal peut faire un detour par des
// aretes bon marche pour eviter une arete chere — capacite distinctive de Dijkstra.
// Bruit : on supprime en plus 30% des aretes avec seed 42 (reseau incomplet).
int N = 5;
var grille = new BidirectionalGraph<(int, int), STaggedEdge<(int, int), double>>();
var aretesInitiales = new List<((int, int), (int, int), double)>();
var rngTerrain = new Random(7); // cout de terrain deterministe, distinct du bruit
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
grille.AddVertex((i, j));
if (i + 1 < N) aretesInitiales.Add(((i, j), (i + 1, j), 1.0 + rngTerrain.NextDouble() * 2.0));
if (j + 1 < N) aretesInitiales.Add(((i, j), (i, j + 1), 1.0 + rngTerrain.NextDouble() * 2.0));
}
}
double bruit = 0.30;
var rng = new Random(42); // suppression de 30% des aretes
var aretesConservees = aretesInitiales.Where(_ => rng.NextDouble() > bruit).ToList();
foreach (var (src, dst, cout) in aretesConservees)
{
grille.AddEdge(new STaggedEdge<(int, int), double>(src, dst, cout));
grille.AddEdge(new STaggedEdge<(int, int), double>(dst, src, cout));
}
int aretesAttendues = aretesInitiales.Count;
int aretesFinales = aretesConservees.Count * 2;
Console.WriteLine($"Reseau 5x5 : {grille.VertexCount} sommets, {aretesFinales}/{aretesAttendues * 2} aretes (apres bruit {bruit:P0}).");
// Plus court chemin (0,0) -> (N-1, N-1) en distance ponderee (Dijkstra)
var start = (0, 0);
var fin = (N - 1, N - 1);
var dijkstraGrille = new DijkstraShortestPathAlgorithm<(int, int), STaggedEdge<(int, int), double>>(
grille, e => e.Tag
);
// Observateur canonique : enregistre l'arbre des predecesseurs pendant le calcul (condition
// d'optimalite GetDistance(u) + poids(u, v) = GetDistance(v) encapsulee — cf cell 11).
var recGrille = new VertexPredecessorRecorderObserver<(int, int), STaggedEdge<(int, int), double>>();
recGrille.Attach(dijkstraGrille);
dijkstraGrille.Compute(start);
if (dijkstraGrille.TryGetDistance(fin, out double distGrille))
{
// Reconstruction du chemin via TryGetPath (aretes -> projection en sommets) pour compter
// les sauts : preuve que le chemin optimal en distance ponderee n'est pas le chemin en
// nombre de sauts.
bool okChemin = recGrille.TryGetPath(fin, out var aretesOpt);
int sauts = okChemin ? aretesOpt.Count() : 0;
int manhattan = (N - 1) * 2; // nombre de sauts du chemin direct coin-a-coin
double coutMoyen = distGrille / Math.Max(1, sauts);
Console.WriteLine($"Dijkstra {start} -> {fin} : distance ponderee = {distGrille:F2} km, chemin = {sauts} sauts (chemin direct coin-a-coin = {manhattan} sauts).");
Console.WriteLine($"Cout moyen par arete du chemin optimal : {coutMoyen:F2} km (si le terrain etait uniforme a 1 km, la distance serait egale au nombre de sauts).");
Console.WriteLine("Le chemin optimal en distance ponderee ne coincide pas avec le chemin en nombre de sauts : Dijkstra pondere, BFS non.");
}
else
{
Console.WriteLine($"Pas de chemin {start} -> {fin} apres suppression de 30% des aretes. Reconnecter le graphe.");
}
Console.WriteLine("Fin cellule grille 5x5.");Debut cellule grille 5x5...
Reseau 5x5 : 25 sommets, 48/80 aretes (apres bruit 30 %).
Dijkstra (0, 0) -> (4, 4) : distance ponderee = 17,11 km, chemin = 8 sauts (chemin direct coin-a-coin = 8 sauts).
Cout moyen par arete du chemin optimal : 2,14 km (si le terrain etait uniforme a 1 km, la distance serait egale au nombre de sauts).
Le chemin optimal en distance ponderee ne coincide pas avec le chemin en nombre de sauts : Dijkstra pondere, BFS non.
Fin cellule grille 5x5.Lecture chiffree — le bruit annonce et le bruit observe. La pleine grille 5x5 porte 80 aretes dirigees — 20 horizontales + 20 verticales, doublees par le graphe bidirectionnel — et la sortie rend 48/80 aretes (apres bruit 30 %) : le parametre dit 30 %, le tirage seed 42 en supprime 32 (40 %), huit de plus que l’esperance 80 x 0,30 = 24 ; un tirage fixe a une realisation, pas sa moyenne. La ligne de Dijkstra se relit en cout moyen : distance ponderee = 17,11 km sur 8 sauts, soit 17,11 / 8 = 2,14 km par saut — dans la fourchette du terrain [1,0 ; 3,0], juste au-dessus de son milieu 2,0 : le chemin prefere des aretes plutot rapides sans pouvoir les avoir toutes.
Cette table reflete la parite structurelle entre le notebook Python Search-02b-NetworkX et ce notebook C#. Les ombres grises marquent les asymetries ou l’un des deux ecosystemes est plus riche que l’autre – c’est le verdict honnete delivre dans le body de la PR.
| Capacite | Python networkx |
.NET QuikGraph 2.5.0 |
Verdict |
|---|---|---|---|
| Graphe non dirige | nx.Graph() |
AdjacencyGraph<TV,TE> / UndirectedGraph<TV,TE> |
parite |
| Graphe dirige | nx.DiGraph() |
BidirectionalGraph<TV,TE> |
parite |
| Aretes ponderees | G.add_edge(u, v, weight=w) |
Edge<TV,double> ou SEdge<TV,double> |
parite |
| Aretes attributs multiples | G.add_edge(u, v, **d) |
Edge<TV,TEdgeData> |
parite |
| BFS | nx.bfs_tree(G, src) / nx.shortest_path |
BreadthFirstSearchAlgorithm (a implementer a la main ou via algorithm.Search) |
parite (QuikGraph fournit les callbacks, pas le générateur de chemin) |
| DFS | nx.dfs_tree(G, src) |
DepthFirstSearchAlgorithm |
parite |
| Dijkstra | nx.shortest_path(G, src, dst, weight='w') |
DijkstraShortestPathAlgorithm<TV,TE> |
parite |
| Bellman-Ford | nx.bellman_ford_path(G, src, dst, weight='w') |
BellmanFordShortestPathAlgorithm<TV,TE> |
parite |
| A* heuristique | nx.astar_path(G, src, dst, heuristic=h) |
AStarShortestPathAlgorithm<TV,TE> |
parite |
| Composantes connexes | nx.connected_components(G) |
ConnectedComponentsAlgorithm<TV,TE> / WeaklyConnectedComponentsAlgorithm |
parite |
| Plus courts chemins (tous) | nx.all_pairs_shortest_path(G) |
FloydWarshallAllPairsShortestPathAlgorithm |
parite |
| Flot maximum | nx.maximum_flow(G, s, t) |
MaximumFlowAlgorithm<TV,TE> (Edmonds-Karp / Push-Relabel) |
parite |
| Centralite degré | nx.degree_centrality(G) |
graph.AdjacentDegree(v) / graph.Degree(v) |
parite (calcul manuelle, pas un méthode nommee) |
| Centralite betweenness | nx.betweenness_centrality(G) |
absente | verdict honnete : a implementer ou brancher une autre bibliotheque |
| Centralite closeness | nx.closeness_centrality(G) |
absente | verdict honnete : idem |
| PageRank | nx.pagerank(G) |
absente | verdict honnete : idem |
| Visualisation integree | nx.draw(G) via matplotlib |
absente (necessite MSAGL + binding, hors scope QuikGraph) | verdict honnete : bibliotheque de calcul, pas de viz |
| Detection de communautes (Louvain) | networkx.community.louvain_communities(G) |
absente | verdict honnete : pas dans QuikGraph – les communautes se font a la main ou via une autre bibliotheque |
Resume : QuikGraph est l’equivalent .NET de NetworkX pour les chemins, flots et composantes. Pour les centralites et communautes, il faut soit implementer a la main (degré, BFS a etages), soit brancher une autre bibliotheque (FastGraph, Microsoft.Graph, ou calculer la betweenness a partir de Floyd-Warshall).
Ennonce : Construisez un graphe BidirectionalGraph ou les trois sommets sont {1, 2, 3} et les aretes (symetriques) ont pour poids 1<->2 : 2.0, 2<->3 : 1.0, 1<->3 : 5.0.
DijkstraShortestPathAlgorithm depuis le sommet 1.1 -> 3 avec le chemin (la liste des sommets parcourus).1 a 3 ? Le chemin le plus court en sauts est-il le même qu’en km ?Indice : la cle pour lire le chemin est dijkstra.GetVertexPredecessor(v), qui remonte la filiere jusqu’a la source.
Exercice a completer : mini-graphe {1, 2, 3}, aretes symmetriques 1-2:2.0, 2-3:1.0, 1-3:5.0, puis BFS et Dijkstra.Ennonce : Modelisez un reseau electrique simplifie du CaseStudy SmartGrid CC3 (cf. MyIA.AI.Notebooks/CaseStudies/) avec 5 noeuds :
P1 (centrale solaire)P2 (eolien)J1 (jonction)J2 (jonction)C1 (quartier residentiel)Aretes (avec capacite en MW) : P1 -> J1 : 10, P1 -> J2 : 5, P2 -> J1 : 8, P2 -> J2 : 5, J1 -> C1 : 12, J2 -> C1 : 7.
Lancez EdmondsKarpMaximumFlowAlgorithm<string, STaggedEdge<string, double>> entre P1+P2 (super source) et C1. Indice : QuikGraph ne supporte pas directement une super-source ; ajoutez un sommet S relie a P1 et P2 avec capacites infinies (ou très grandes), puis appelez algo.Compute("S", "C1").
Attention API : comme en section 6,
EdmondsKarpMaximumFlowAlgorithmexige que le graphe soit augmente de ses aretes residuelles avantCompute. Instanciez unReversedEdgeAugmentorAlgorithm, appelezAddReversedEdges(), puisCompute(cf. section 6 pour le patron complet).
Ennonce : Construisez un graphe UndirectedGraph de 30 noeuds repartis en 3 communautes de 10 noeuds (noeuds c0_0..c0_9, c1_0..c1_9, c2_0..c2_9), avec une densite intra-communaute elevee (chaque noeud connecte a 5 de sa communaute) et une densite inter-communaute faible (2-3 aretes entre communautes).
Indice : utilisez le patron de la section 5 avec 1 boucle de construction. Pour le defi bonus, en QuikGraph pur : graph.RemoveEdge(edge) retire une arete, mais il faut avoir garde les handles quelque part (var aretes = new List<Edge<T>>(...)).