Componentes dirigidos fortemente conexos
Separe um grafo dirigido de até 64 vértices em componentes fortemente 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)
Revise antes de aplicar
Compare o comportamento real com o resultado esperado. Se uma verificação falhar, investigue a causa antes de fazer outras alterações.
Modelos
Configure um endpoint compatível com OpenAI ou Anthropic com a URL base e uma chave API, quando necessária. Teste a conexão. O servidor local precisa estar em execução; ferramentas remotas podem transmitir dados separadamente.
Projeto
Teste ciclos, vértices isolados e vazio, rejeitando membros inválidos sem alterar os conjuntos de adjacência.
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)
Dê aos grupos de dependências um significado útil para a aplicação
ComponentWisp é um ambiente de programação com IA para Windows para desenvolvedores que rastreiam relações em dados e código do projeto. Traga para a conversa a representação do grafo e o consumidor que precisa dos grupos. Peça ao assistente que examine o significado de uma aresta dirigida antes de propor uma mudança no agrupamento. Um resultado só é útil quando as relações que preserva correspondem à pergunta que a aplicação tenta responder.
Uma tarefa com strong_components.py pode examinar grupos cujos vértices alcançam uns aos outros por caminhos dirigidos. Use um pequeno exemplo de dependências para distinguir alcançabilidade mútua de uma conexão unidirecional e revise a implementação e a ordenação da saída. Se aplicar o código a dependências, explicite o mapeamento entre objetos reais e vértices; a função sozinha não estabelece o significado dessas dependências.
Após ler uma proposta, execute as verificações do projeto com um ciclo, uma ligação unidirecional e vértices isolados. Examine o consumidor para confirmar que trata os grupos resultantes de maneira consistente. ComponentWisp conecta-se a endpoints compatíveis com OpenAI ou da Anthropic que sejam suportados, com credenciais quando necessário. Modelos sem restrições podem ser selecionados onde forem oferecidos, enquanto o modelo e o servidor determinam restrições, ferramentas e limites de contexto. Mantenha na conversa o significado das arestas e os grupos esperados para que edições posteriores preservem o mesmo requisito de software.
Perguntas sobre código de agrupamento de dependências
Uma dependência unidirecional basta para agrupar objetos?
Não para um grupo definido por alcançabilidade dirigida mútua. Declare a regra de agrupamento pretendida e inclua um exemplo unidirecional para que uma implementação proposta não trate acidentalmente uma relação dirigida como uma conexão não dirigida.
Como objetos reais do projeto devem corresponder a vértices?
Mantenha um mapeamento explícito que o consumidor possa usar para interpretar os resultados. Examine o que acontece quando objetos são removidos ou reordenados e teste se os grupos retornados ainda se referem aos objetos pretendidos do projeto.
Agrupar dependências determina uma ordem de execução?
Isso responde a outra pergunta. A aplicação pode precisar de lógica adicional para ordenar grupos ou tratar ciclos. Identifique esse requisito separadamente e examine o consumidor relevante, em vez de presumir que uma partição seja um plano completo de execução.
Por que incluir vértices isolados nas verificações?
Eles verificam se objetos sem arestas ainda recebem a representação esperada pela aplicação. Confira tanto a saída da função quanto a visão do consumidor, especialmente se uma refatoração constrói estruturas intermediárias iterando apenas sobre conexões existentes.
ComponentWisp · Atualizado 2026-10-25