Composantes orientées fortement connexes
Partitionnez un graphe orienté d’au plus 64 sommets en composantes fortement connexes.
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)
Vérifiez avant d’appliquer
Comparez le comportement observé au résultat attendu. Si une vérification échoue, cherchez la cause avant de poursuivre les modifications.
Modèles
Configurez un endpoint compatible OpenAI ou Anthropic avec son URL de base et une clé API si nécessaire. Testez la connexion. Un serveur local doit fonctionner ; les outils distants peuvent transmettre des données séparément.
Projet
Testez cycles, sommets isolés et vide, en rejetant les membres invalides sans modifier les ensembles d’adjacence.
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)
Donnez aux groupes de dépendances un sens exploitable par l’application
ComponentWisp est un espace de programmation assistée par IA sous Windows pour les développeurs qui suivent les relations dans les données et le code d’un projet. Fournissez la représentation du graphe et le code utilisateur de ses groupes dans la conversation. Demandez à l’assistant d’examiner le sens d’une arête dirigée avant de proposer une modification du regroupement. Un résultat n’est utile que si les relations préservées correspondent à la question de votre application.
Une tâche autour de strong_components.py pourrait examiner des groupes dont les sommets peuvent se rejoindre mutuellement par des chemins dirigés. Utilisez un petit exemple de dépendances pour distinguer l’accessibilité mutuelle d’une connexion à sens unique, puis examinez l’implémentation et l’ordre de sortie. Si vous appliquez le code à des dépendances, explicitez la correspondance entre objets réels et sommets ; la fonction seule ne peut établir le sens de ces dépendances.
Après lecture d’une proposition, exécutez les vérifications du projet avec un cycle, un lien à sens unique et des sommets isolés. Examinez le code utilisateur pour confirmer qu’il traite les groupes de façon cohérente. ComponentWisp se connecte aux points de terminaison compatibles OpenAI ou Anthropic pris en charge, avec des identifiants si nécessaire. Des modèles sans restrictions peuvent être sélectionnés lorsqu’ils sont proposés ; le modèle et le serveur déterminent les restrictions, outils et limites de contexte. Gardez le sens des arêtes et les groupes attendus dans la conversation afin que les modifications ultérieures préservent la même exigence logicielle.
Questions sur le code de regroupement des dépendances
Une dépendance à sens unique suffit-elle à regrouper des objets ?
Pas pour un groupe défini par l’accessibilité dirigée mutuelle. Énoncez la règle de regroupement souhaitée et incluez un exemple à sens unique pour que l’implémentation proposée ne traite pas accidentellement une relation dirigée comme une connexion non dirigée.
Comment faire correspondre les objets réels du projet aux sommets ?
Conservez une correspondance explicite que le code utilisateur peut exploiter pour interpréter les résultats. Examinez ce qui se passe lorsque des objets sont supprimés ou réordonnés et vérifiez que les groupes renvoyés désignent toujours les objets voulus.
Le regroupement des dépendances détermine-t-il un ordre d’exécution ?
Il répond à une autre question. Votre application peut nécessiter une logique supplémentaire pour ordonner les groupes ou gérer les cycles. Identifiez cette exigence séparément et examinez le code utilisateur pertinent plutôt que de supposer qu’une partition constitue un plan d’exécution complet.
Pourquoi inclure des sommets isolés dans les vérifications ?
Ils vérifient que les objets sans arêtes reçoivent tout de même la représentation attendue. Vérifiez la sortie de la fonction et la vue du code utilisateur, surtout si une refactorisation construit des structures intermédiaires en parcourant uniquement les connexions existantes.
ComponentWisp · Mis à jour 2026-10-25