Componente orientate tare conexe
Împarte un graf orientat de cel mult 64 de vârfuri în componente tare conexe.
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)
Verifică înainte de aplicare
Compară comportamentul real cu rezultatul așteptat. Dacă o verificare eșuează, cercetează cauza înainte de alte modificări.
Modele
Configurează un endpoint compatibil OpenAI sau Anthropic cu URL-ul de bază și cheia API, dacă este necesară. Testează conexiunea. Serverul local trebuie să ruleze; instrumentele externe pot transmite date separat.
Proiect
Testează cicluri, vârfuri izolate și intrare goală, respinge membri invalizi fără schimbarea mulțimilor de adiacență.
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ă grupurilor de dependențe un sens utilizabil de aplicație
ComponentWisp este un spațiu de programare cu IA pentru Windows destinat dezvoltatorilor care urmăresc relații în datele și codul proiectului. Adu în conversație reprezentarea grafului și consumatorul care are nevoie de grupurile sale. Cere asistentului să examineze sensul unei muchii orientate înainte de a propune o modificare a grupării. Un rezultat este util doar când relațiile păstrate corespund întrebării la care încearcă să răspundă aplicația.
O sarcină legată de strong_components.py ar putea examina grupuri ale căror vârfuri sunt reciproc accesibile prin drumuri orientate. Folosește un exemplu mic de dependențe pentru a distinge accesibilitatea reciprocă de o conexiune unidirecțională, apoi analizează implementarea și ordinea ieșirii. Dacă aplici codul dependențelor, explicitează maparea obiectelor reale la vârfuri; funcția auxiliară singură nu poate stabili sensul acelor dependențe.
După citirea unei propuneri, rulează verificările proiectului cu un ciclu, o legătură unidirecțională și vârfuri izolate. Examinează consumatorul pentru a confirma că tratează consecvent grupurile rezultate. ComponentWisp se conectează la endpointuri compatibile OpenAI sau Anthropic acceptate, cu acreditări când sunt necesare. Modelele fără restricții pot fi selectate unde sunt oferite, iar modelul și serverul determină restricțiile, instrumentele și limitele contextului. Păstrează în conversație sensul muchiilor și grupurile așteptate, astfel încât modificările ulterioare să păstreze aceeași cerință software.
Întrebări despre codul de grupare a dependențelor
Este suficientă o dependență unidirecțională pentru a grupa obiectele?
Nu pentru un grup definit prin accesibilitate orientată reciprocă. Precizează regula de grupare intenționată și include un exemplu unidirecțional, astfel încât implementarea propusă să nu trateze accidental o relație orientată ca pe o conexiune neorientată.
Cum trebuie mapate obiectele reale ale proiectului la vârfuri?
Păstrează o mapare explicită pe care consumatorul o poate folosi pentru interpretarea rezultatelor. Examinează ce se întâmplă când obiectele sunt eliminate sau reordonate și testează dacă grupurile returnate se referă în continuare la obiectele intenționate ale proiectului.
Gruparea dependențelor decide o ordine de execuție?
Răspunde altei întrebări. Aplicația poate necesita logică suplimentară pentru ordonarea grupurilor sau tratarea ciclurilor. Identifică separat această cerință și examinează consumatorul relevant, fără a presupune că o partiționare este un plan complet de execuție.
De ce să includ vârfuri izolate în verificări?
Ele verifică dacă obiectele fără muchii primesc totuși reprezentarea așteptată de aplicație. Verifică atât ieșirea funcției, cât și vizualizarea consumatorului, mai ales dacă o refactorizare construiește structuri intermediare iterând doar conexiunile existente.
ComponentWisp · Actualizat 2026-10-25