Stark verbundene gerichtete Komponenten
Zerlege einen gerichteten Graphen mit höchstens 64 Knoten in stark verbundene Komponenten.
def strong_components(graph):
if type(graph) is not list or len(graph) > 64:
raise ValueError("scc.graph")
n = len(graph)
if any(type(row) is not set or any(type(v) is not int or not 0 <= v < n for v in row) for row in graph):
raise ValueError("scc.edge")
seen, order = set(), []
for start in range(n):
if start in seen:
continue
seen.add(start)
stack = [(start, iter(sorted(graph[start])))]
while stack:
node, edges = stack[-1]
target = next(edges, None)
if target is None:
order.append(node)
stack.pop()
elif target not in seen:
seen.add(target)
stack.append((target, iter(sorted(graph[target]))))
reverse = [set() for _ in graph]
for node, edges in enumerate(graph):
for target in edges:
reverse[target].add(node)
seen, result = set(), []
for start in reversed(order):
if start in seen:
continue
group, pending = [], [start]
seen.add(start)
while pending:
node = pending.pop()
group.append(node)
for target in reverse[node]-seen:
seen.add(target)
pending.append(target)
result.append(sorted(group))
return sorted(result)
Vor dem Anwenden prüfen
Vergleichen Sie das tatsächliche Verhalten mit dem erwarteten Ergebnis. Klären Sie fehlgeschlagene Prüfungen vor weiteren Änderungen.
Modelle
Richten Sie einen OpenAI-kompatiblen oder Anthropic-Endpunkt mit Basis-URL und gegebenenfalls API-Schlüssel ein. Testen Sie die Verbindung. Ein lokaler Modellserver muss laufen; entfernte Werkzeuge können Daten separat übertragen.
Projekt
Teste Zyklen, isolierte Knoten und Leere, lehne ungültige Elemente ohne Änderung der Adjazenzmengen ab.
def strong_components(graph):
if type(graph) is not list or len(graph) > 64:
raise ValueError("scc.graph")
n = len(graph)
if any(type(row) is not set or any(type(v) is not int or not 0 <= v < n for v in row) for row in graph):
raise ValueError("scc.edge")
seen, order = set(), []
for start in range(n):
if start in seen:
continue
seen.add(start)
stack = [(start, iter(sorted(graph[start])))]
while stack:
node, edges = stack[-1]
target = next(edges, None)
if target is None:
order.append(node)
stack.pop()
elif target not in seen:
seen.add(target)
stack.append((target, iter(sorted(graph[target]))))
reverse = [set() for _ in graph]
for node, edges in enumerate(graph):
for target in edges:
reverse[target].add(node)
seen, result = set(), []
for start in reversed(order):
if start in seen:
continue
group, pending = [], [start]
seen.add(start)
while pending:
node = pending.pop()
group.append(node)
for target in reverse[node]-seen:
seen.add(target)
pending.append(target)
result.append(sorted(group))
return sorted(result)
Geben Sie Abhängigkeitsgruppen eine nutzbare Bedeutung
ComponentWisp ist ein KI-Programmierarbeitsbereich für Windows für Entwickler, die Beziehungen durch Projektdaten und Code verfolgen. Bringen Sie Graphendarstellung und den Empfänger, der ihre Gruppen benötigt, ins Gespräch. Lassen Sie den Assistenten vor einer Gruppierungsänderung prüfen, was eine gerichtete Kante bedeutet. Ein Ergebnis ist nur nützlich, wenn die erhaltenen Beziehungen zur Frage passen, die Ihre Anwendung beantworten will.
Eine Aufgabe zu strong_components.py könnte Gruppen untersuchen, deren Knoten einander über gerichtete Pfade erreichen können. Unterscheiden Sie anhand eines kleinen Abhängigkeitsbeispiels gegenseitige Erreichbarkeit von einer einseitigen Verbindung und prüfen Sie dann Implementierung und Ausgabereihenfolge. Wenden Sie den Code auf Abhängigkeiten an, machen Sie die Zuordnung realer Objekte zu Knoten ausdrücklich; die Hilfsroutine allein kann die Bedeutung dieser Abhängigkeiten nicht festlegen.
Führen Sie nach dem Lesen eines Vorschlags Projektprüfungen mit einem Zyklus, einer einseitigen Verbindung und isolierten Knoten aus. Prüfen Sie den Empfänger auf einheitliche Behandlung der resultierenden Gruppen. ComponentWisp verbindet sich mit unterstützten OpenAI-kompatiblen oder Anthropic-Endpunkten, bei Bedarf mit Zugangsdaten. Uneingeschränkte Modelle können gewählt werden, sofern angeboten; Modell und Server bestimmen Einschränkungen, Werkzeuge und Kontextgrenzen. Halten Sie Kantenbedeutung und erwartete Gruppen im Gespräch fest, damit spätere Änderungen dieselbe Softwareanforderung erhalten.
Fragen zum Code für Abhängigkeitsgruppen
Genügt eine einseitige Abhängigkeit für eine gemeinsame Gruppe?
Nicht bei einer Gruppe, die durch gegenseitige gerichtete Erreichbarkeit definiert ist. Nennen Sie die beabsichtigte Gruppierungsregel und geben Sie ein einseitiges Beispiel an, damit die Implementierung eine gerichtete Beziehung nicht versehentlich als ungerichtete Verbindung behandelt.
Wie sollten reale Projektobjekte Knoten zugeordnet werden?
Halten Sie eine ausdrückliche Zuordnung bereit, mit der der Empfänger Ergebnisse interpretieren kann. Prüfen Sie, was beim Entfernen oder Umordnen von Objekten geschieht, und testen Sie, dass zurückgegebene Gruppen weiterhin die beabsichtigten Projektobjekte bezeichnen.
Bestimmt die Gruppierung von Abhängigkeiten eine Ausführungsreihenfolge?
Sie beantwortet eine andere Frage. Ihre Anwendung kann zusätzliche Logik zur Gruppenordnung oder Zyklusbehandlung benötigen. Benennen Sie diese Anforderung separat und prüfen Sie den relevanten Empfänger, statt eine Aufteilung für einen vollständigen Ausführungsplan zu halten.
Warum isolierte Knoten in die Prüfungen aufnehmen?
Sie prüfen, dass Objekte ohne Kanten weiterhin die erwartete Darstellung erhalten. Prüfen Sie sowohl Hilfsroutinenausgabe als auch Empfängeransicht, besonders wenn eine Umstrukturierung Zwischenstrukturen nur durch Iteration über vorhandene Verbindungen erzeugt.
ComponentWisp · Aktualisiert 2026-10-25