Diskret matematik: grafer och relationer

En graf är noder (punkter) och kanter (linjer mellan dem). Det är en av de mest användbara modellerna som finns: vänskaper, vägar, webblänkar, beroenden mellan uppgifter — och den här plattformens kunskapskarta.

• Oriktad: kanten går åt båda håll (vänskap).
• Riktad: kanten har riktning (A är förkunskap till B).
• Cykel: en väg som kommer tillbaka till sig själv.
• DAG (riktad acyklisk graf): riktad utan cykler — då går den att topologiskt sortera, alltså lägga i en ordning där varje nod kommer efter allt den beror på.

AI-grafen måste vara en DAG. En cykel skulle betyda «A kräver B som kräver A» — omöjligt att lära sig i någon ordning.

graf = {"vektorer": [], "matriser": ["vektorer"],
        "neuronnat": ["matriser", "derivata"], "derivata": [],
        "backprop": ["neuronnat"]}          # nod -> förkunskaper

def topologisk(g):
    besokt, ordning, pagaende = set(), [], set()
    def besok(n):
        if n in besokt: return
        if n in pagaende: raise ValueError(f"cykel vid {n}")
        pagaende.add(n)
        for f in g[n]:
            besok(f)
        pagaende.discard(n); besokt.add(n); ordning.append(n)
    for n in g: besok(n)
    return ordning

print(topologisk(graf))
# ['vektorer', 'matriser', 'derivata', 'neuronnat', 'backprop']

Varje förkunskap kommer före den nod som kräver den. Det är precis så lärvägarna i plattformen byggs — och pagaende-mängden är cykelkontrollen som grafinvarianterna kör vid varje import.