Avhengighetsgraf - Dependency graph

I matematikk , informatikk og digital elektronikk er en avhengighetsgraf en rettet graf som representerer avhengigheter av flere objekter mot hverandre. Det er mulig å utlede en evalueringsordre eller fraværet av en evalueringsordre som respekterer de gitte avhengighetene fra avhengighetsgrafen.

Definisjon

Gitt et sett av objekter og en transitive forbindelse med modellering av en avhengighet " en er avhengig av b " ( " a behov b evaluert første"), er avhengigheten grafen en graf med den transitive reduksjon av R . ${\ displaystyle S}$ ${\ displaystyle R \ subseteq S \ times S}$ ${\ displaystyle (a, b) \ i R}$ ${\ displaystyle G = (S, T)}$ ${\ displaystyle T \ subseteq R}$

Anta for eksempel en enkel kalkulator. Denne kalkulatoren støtter tildeling av konstante verdier til variabler og tildele summen av nøyaktig to variabler til en tredje variabel. Gitt flere ligninger som " A = B + C ; B = 5+ D ; C = 4; D = 2;", deretter og . Du kan utlede denne relasjonen direkte: A avhenger av B og C , fordi du kan legge til to variabler hvis og bare hvis du kjenner verdiene til begge variablene. Dermed må B beregnes før A kan beregnes. Verdiene til C og D er imidlertid kjent umiddelbart fordi de er tallbokstaver. ${\ displaystyle S = \ {A, B, C, D \}}$ ${\ displaystyle R = \ {(A, B), (A, C), (B, D) \}}$

Anerkjenner umulige evalueringer

I en avhengighetsgraf fører syklusene til avhengigheter (også kalt sirkulære avhengigheter ) til en situasjon der ingen gyldig evalueringsrekkefølge eksisterer, fordi ingen av objektene i syklusen kan evalueres først. Hvis en avhengighetsgraf ikke har noen sirkulære avhengigheter, danner den en rettet asyklisk graf , og en evalueringsrekkefølge kan bli funnet ved topologisk sortering . De fleste topologiske sorteringsalgoritmer er også i stand til å oppdage sykluser i deres innganger; det kan imidlertid være ønskelig å utføre syklusdeteksjon separat fra topologisk sortering for å tilveiebringe passende håndtering for de detekterte syklusene.

Anta den enkle kalkulatoren fra før. Ligningssystemet " A = B ; B = D + C ; C = D + A ; D = 12;" inneholder en sirkulær avhengighet dannet av A , B og C , som B må vurderes før A , C må vurderes før B og A må vurderes før C .

Utlede en evalueringsordre

En korrekt evalueringsrekkefølge er en nummerering av objektene som danner nodene i avhengighetsgrafen slik at følgende ligning holder: med . Dette betyr at hvis nummereringen bestiller to elementer og slik som vil bli evaluert før , så må ikke avhenge av . ${\ displaystyle n: S \ rightarrow \ mathbb {N}}$ ${\ displaystyle n (a) <n (b) \ Rightarrow (a, b) \ notin R}$ ${\ displaystyle a, b \ i S}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle b}$

Det kan være mer enn én korrekt evalueringsrekkefølge. Faktisk er en riktig nummerering en topologisk rekkefølge , og enhver topologisk rekkefølge er en riktig nummerering. Dermed får enhver algoritme som får en riktig topologisk rekkefølge en korrekt evalueringsrekkefølge.

Anta den enkle kalkulatoren ovenfra en gang til. Gitt ligningssystemet " A = B + C ; B = 5+ D ; C = 4; D = 2;", vil en korrekt evalueringsrekkefølge være ( D , C , B , A ). Imidlertid er ( C , D , B , A ) også en korrekt evalueringsrekkefølge.

Monoid struktur

En asyklisk avhengighetsgraf tilsvarer et spor av et spormonoid som følger:

En funksjon markerer hvert toppunkt med et symbol fra alfabetet ${\ displaystyle \ phi: S \ to \ Sigma}$ ${\ displaystyle \ Sigma}$
Det er en kant eller hvis og bare hvis det er i avhengighetsforholdet . ${\ displaystyle a \ to b}$ ${\ displaystyle b \ to a}$ ${\ displaystyle (\ phi (a), \ phi (b))}$ ${\ displaystyle D}$
To grafer anses å være like hvis etikettene og kantene samsvarer.

Deretter tilsvarer strengen som består av toppetiketter bestilt av en korrekt evalueringsrekkefølge, en streng av et spor.

Den monoide operasjonen tar den usammenhengende foreningen av toppunktene til to grafer, bevarer de eksisterende kantene i hver graf og trekker nye kanter fra første til andre der avhengighetsforholdet tillater, ${\ displaystyle (S_ {12}, R_ {12}) = (S_ {1}, R_ {1}) \ bullet (S_ {2}, R_ {2})}$ ${\ displaystyle S_ {12} = S_ {1} \ sqcup S_ {2}}$

{\ displaystyle R_ {12} = R_ {1} \ sqcup R_ {2} \ sqcup \ {(a, b) \ mid a \ in S_ {1} \ land b \ in S_ {2} \ land (\ phi (a), \ phi (b)) \ ​​i D \}}

Identiteten er den tomme grafen.

Eksempler

Avhengighetsgrafer brukes i:

Automatisert programvare montører : De går grafen jakt etter programvarepakker som er nødvendige, men ennå ikke installert. Avhengigheten er gitt av koblingen av pakkene.
Programvarebyggingsskript som Unix Make , Node npm install, php composer, Twitter bower install eller Apache Ant . De trenger å vite hvilke filer som er endret, så bare de riktige filene trenger å kompileres på nytt.
I kompilatorteknologi og formell språkimplementering:
- Instruksjonsplanlegging : Avhengighetsgrafer beregnes for operandene til montering eller mellominstruksjoner og brukes til å bestemme en optimal rekkefølge for instruksjonene.
- Eliminering av død kode : Hvis ingen sideeffekt er avhengig av en variabel, anses denne variabelen som død og kan fjernes.
Dynamisk grafanalyse: GraphBolt og KickStarter fanger opp avhengighetsverdier for inkrementell databehandling når grafstrukturen endres.
Regneark- kalkulatorer. De må utlede en korrekt beregningsrekkefølge som ligner den i eksemplet som brukes i denne artikkelen.
Web Forms standarder som XForms for å vite hvilke visuelle elementer som skal oppdateres hvis data i modellen endres.
Videospill, spesielt puslespill og eventyr-videospill , som ofte er utformet som en graf over avhengige forhold mellom handlinger i spillet.

Avhengighetsgrafer er et aspekt av:

Produserende anleggstyper : Råvarer behandles til produkter via flere avhengige stadier.
Jobbplanlegging : En samling relaterte teoretiske problemer innen informatikk.

Se også

Referanser

Balmas, Francoise (2001) Vis avhengighetsgrafer: en hierarkisk tilnærming , [1] wcre, s. 261, åttende arbeidskonferanse om reverseringsteknikk (WCRE'01)

Languages

In other projects