Componenti orientate fortemente connesse
Dividi un grafo orientato di massimo 64 vertici in componenti fortemente connesse.
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)
Controlla prima di applicare
Confronta il comportamento effettivo con il risultato atteso. Se una verifica fallisce, indaga la causa prima di altre modifiche.
Modelli
Configura un endpoint compatibile con OpenAI o Anthropic usando URL di base e chiave API, se necessaria. Prova la connessione. Il server locale deve essere in esecuzione; gli strumenti remoti possono trasmettere dati separatamente.
Progetto
Prova cicli, vertici isolati e vuoto, rifiutando membri errati senza cambiare gli insiemi di adiacenza.
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)
Dai ai gruppi di dipendenze un significato utilizzabile dall'applicazione
ComponentWisp è un ambiente di programmazione con IA per Windows per sviluppatori che seguono le relazioni attraverso dati e codice del progetto. Porta nella conversazione la rappresentazione del grafo e il codice utilizzatore che ha bisogno dei suoi gruppi. Chiedi all'assistente di esaminare cosa significa un arco orientato prima di proporre una modifica al raggruppamento. Un risultato è utile solo quando le relazioni che conserva corrispondono alla domanda a cui l'applicazione cerca di rispondere.
Un compito su strong_components.py potrebbe esaminare gruppi i cui vertici possono raggiungersi reciprocamente tramite cammini orientati. Usa un piccolo esempio di dipendenze per distinguere la raggiungibilità reciproca da una connessione unidirezionale, poi esamina l'implementazione e l'ordinamento dell'output. Se applichi il codice alle dipendenze, rendi esplicita la corrispondenza fra oggetti reali e vertici; la funzione da sola non può stabilire cosa significhino quelle dipendenze.
Dopo aver letto una proposta, esegui i controlli del progetto con un ciclo, un collegamento unidirezionale e vertici isolati. Esamina il codice utilizzatore per confermare che tratti coerentemente i gruppi risultanti. ComponentWisp si collega a endpoint supportati compatibili con OpenAI o Anthropic, con credenziali quando richieste. Si possono selezionare modelli senza restrizioni dove offerti, mentre modello e server determinano restrizioni, strumenti e limiti di contesto. Mantieni nella conversazione il significato degli archi e i gruppi attesi, così le modifiche successive conservano lo stesso requisito software.
Domande sul codice di raggruppamento delle dipendenze
Una dipendenza unidirezionale basta per raggruppare gli oggetti?
Non per un gruppo definito dalla raggiungibilità orientata reciproca. Indica la regola di raggruppamento desiderata e includi un esempio unidirezionale, così l'implementazione proposta non tratta accidentalmente una relazione orientata come una connessione non orientata.
Come devono corrispondere ai vertici gli oggetti reali del progetto?
Mantieni una corrispondenza esplicita che il codice utilizzatore possa usare per interpretare i risultati. Esamina cosa succede quando gli oggetti vengono rimossi o riordinati e verifica che i gruppi restituiti facciano ancora riferimento agli oggetti desiderati del progetto.
Raggruppare le dipendenze decide un ordine di esecuzione?
Risponde a una domanda diversa. L'applicazione può aver bisogno di logica aggiuntiva per ordinare i gruppi o gestire i cicli. Identifica separatamente quel requisito ed esamina il codice utilizzatore pertinente anziché presumere che una partizione sia un piano di esecuzione completo.
Perché includere vertici isolati nei controlli?
Verificano che gli oggetti senza archi ricevano comunque la rappresentazione attesa dall'applicazione. Controlla sia l'output della funzione sia la vista del codice utilizzatore, soprattutto se una ristrutturazione costruisce strutture intermedie iterando solo sulle connessioni esistenti.
ComponentWisp · Aggiornato 2026-10-25