Componentes dirigidos fuertemente conexos
Divide un grafo dirigido de hasta 64 vértices en componentes fuertemente conexos.
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)
Revisa antes de aplicar
Compara el comportamiento real con el resultado esperado. Si una prueba falla, investiga la causa antes de hacer más cambios.
Modelos
Configura un endpoint compatible con OpenAI o Anthropic usando la URL base y, si hace falta, una clave API. Prueba la conexión. Un servidor local debe estar en ejecución; las herramientas remotas pueden enviar datos por separado.
Proyecto
Prueba ciclos, vértices aislados y vacío, rechazando miembros inválidos sin cambiar los conjuntos de adyacencia.
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)
Da a los grupos de dependencias un significado útil para la aplicación
ComponentWisp es un espacio de programación con IA para Windows destinado a desarrolladores que siguen relaciones a través de datos y código del proyecto. Aporta a la conversación la representación del grafo y el consumidor que necesita sus grupos. Pide al asistente que examine qué significa una arista dirigida antes de proponer un cambio de agrupación. Un resultado solo es útil cuando las relaciones que conserva coinciden con la pregunta que tu aplicación intenta responder.
Una tarea sobre strong_components.py podría examinar grupos cuyos vértices pueden alcanzarse mutuamente mediante caminos dirigidos. Usa un ejemplo pequeño de dependencias para distinguir la alcanzabilidad mutua de una conexión unidireccional, y revisa después la implementación y el orden de salida. Si aplicas el código a dependencias, explicita la correspondencia entre objetos reales y vértices; la función por sí sola no puede establecer qué significan esas dependencias.
Tras leer una propuesta, ejecuta las comprobaciones del proyecto con un ciclo, un enlace unidireccional y vértices aislados. Examina el consumidor para confirmar que trata los grupos resultantes de forma coherente. ComponentWisp se conecta a endpoints compatibles con OpenAI o de Anthropic admitidos, con credenciales cuando sean necesarias. Pueden seleccionarse modelos sin restricciones donde se ofrezcan, mientras que el modelo y el servidor determinan las restricciones, las herramientas y los límites de contexto. Mantén el significado de las aristas y los grupos esperados en la conversación para que las ediciones posteriores conserven el mismo requisito de software.
Preguntas sobre código de agrupación de dependencias
¿Basta una dependencia unidireccional para agrupar objetos?
No para un grupo definido por alcanzabilidad dirigida mutua. Indica la regla de agrupación prevista e incluye un ejemplo unidireccional para que la implementación propuesta no trate accidentalmente una relación dirigida como una conexión no dirigida.
¿Cómo deben corresponderse los objetos reales del proyecto con los vértices?
Mantén una correspondencia explícita que el consumidor pueda usar para interpretar los resultados. Examina qué sucede cuando se eliminan o reordenan objetos y prueba que los grupos devueltos sigan haciendo referencia a los objetos previstos del proyecto.
¿Agrupar dependencias decide un orden de ejecución?
Responde a una pregunta distinta. Tu aplicación puede necesitar lógica adicional para ordenar grupos o tratar ciclos. Identifica ese requisito por separado y examina el consumidor pertinente en vez de suponer que una partición es un plan de ejecución completo.
¿Por qué incluir vértices aislados en las comprobaciones?
Verifican que los objetos sin aristas sigan recibiendo la representación que espera tu aplicación. Comprueba tanto la salida de la función como la vista del consumidor, especialmente si una refactorización construye estructuras intermedias iterando solo sobre conexiones existentes.
ComponentWisp · Actualizado 2026-10-25