Sterk verbonden gerichte componenten
Verdeel een gerichte graaf met maximaal 64 knopen in sterk verbonden componenten.
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)
Controleer vóór het toepassen
Vergelijk het werkelijke gedrag met het verwachte resultaat. Onderzoek een mislukte controle voordat je verdergaat met wijzigingen.
Modellen
Stel een OpenAI-compatibel of Anthropic-endpoint in met de basis-URL en zo nodig een API-sleutel. Test de verbinding. Een lokale modelserver moet actief zijn; externe hulpmiddelen kunnen apart gegevens versturen.
Project
Test cycli, losse knopen en leegte, en weiger verkeerde leden zonder de aangrenzingsverzamelingen te wijzigen.
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)
Geef afhankelijkheidsgroepen een betekenis die de toepassing kan gebruiken
ComponentWisp is een AI-programmeerwerkruimte voor Windows voor ontwikkelaars die relaties door projectgegevens en code volgen. Neem de graafrepresentatie en de afnemer die de groepen nodig heeft mee in het gesprek. Vraag de assistent te onderzoeken wat een gerichte kant betekent voordat hij een groepswijziging voorstelt. Een resultaat is alleen nuttig wanneer de relaties die het behoudt aansluiten bij de vraag die je toepassing probeert te beantwoorden.
Een taak rond strong_components.py kan groepen onderzoeken waarvan de knopen elkaar via gerichte paden kunnen bereiken. Gebruik een klein afhankelijkheidsvoorbeeld om wederzijdse bereikbaarheid te onderscheiden van een eenrichtingsverbinding en beoordeel vervolgens de implementatie en uitvoervolgorde. Maak bij toepassing op afhankelijkheden de koppeling tussen echte objecten en knopen expliciet; de hulpfunctie alleen kan niet vaststellen wat die afhankelijkheden betekenen.
Voer na het lezen van een voorstel de projectcontroles uit met een cyclus, een eenrichtingsverbinding en geïsoleerde knopen. Onderzoek de afnemer om te bevestigen dat die de resulterende groepen consequent behandelt. ComponentWisp verbindt met ondersteunde OpenAI-compatibele of Anthropic-eindpunten, met inloggegevens waar vereist. Onbeperkte modellen kunnen worden geselecteerd waar ze worden aangeboden, terwijl het model en de server beperkingen, tools en contextlimieten bepalen. Houd de betekenis van kanten en de verwachte groepen in het gesprek, zodat volgende wijzigingen dezelfde software-eis behouden.
Vragen over code voor afhankelijkheidsgroepen
Is een eenrichtingsafhankelijkheid voldoende om objecten samen te voegen?
Niet voor een groep die door wederzijdse gerichte bereikbaarheid is gedefinieerd. Vermeld de bedoelde groepsregel en neem een eenrichtingsvoorbeeld op, zodat een voorgestelde implementatie een gerichte relatie niet per ongeluk als een ongerichte verbinding behandelt.
Hoe moeten echte projectobjecten aan knopen worden gekoppeld?
Houd een expliciete koppeling bij die de afnemer kan gebruiken om resultaten te interpreteren. Onderzoek wat er gebeurt wanneer objecten worden verwijderd of anders geordend en test dat de geretourneerde groepen nog naar de bedoelde projectobjecten verwijzen.
Bepaalt het groeperen van afhankelijkheden een uitvoeringsvolgorde?
Het beantwoordt een andere vraag. Je toepassing kan aanvullende logica nodig hebben om groepen te ordenen of cycli af te handelen. Identificeer die eis afzonderlijk en onderzoek de relevante afnemer in plaats van aan te nemen dat een opdeling een volledig uitvoeringsplan is.
Waarom geïsoleerde knopen in de controles opnemen?
Ze verifiëren dat objecten zonder kanten nog steeds de representatie krijgen die je toepassing verwacht. Controleer zowel de uitvoer van de hulpfunctie als de weergave bij de afnemer, vooral als een refactoring tussenstructuren opbouwt door alleen bestaande verbindingen te doorlopen.
ComponentWisp · Bijgewerkt 2026-10-25