Graf závislosti - Dependency graph

V matematice , informatice a digitální elektroniky , je závislost graf je orientovaný graf představující závislostí několika objektů vůči sobě navzájem. Z grafu závislostí je možné odvodit pořadí hodnocení nebo absenci pořadí hodnocení, které respektuje dané závislosti.

Definice

Vzhledem k tomu, soubor objektů a tranzitivní vztah s modelováním závislost „ závisí na b “ ( „ jen potřebuje b hodnocena jako první“), závislost graf je graf s k tranzitivní redukce z výzkumu . ${\ displaystyle S}$ ${\ displaystyle R \ subseteq S \ krát S}$ ${\ displaystyle (a, b) \ v R}$ ${\ displaystyle G = (S, T)}$ ${\ displaystyle T \ subseteq R}$

Předpokládejme například jednoduchou kalkulačku. Tato kalkulačka podporuje přiřazení konstantních hodnot k proměnným a přiřazení součtu přesně dvou proměnných ke třetí proměnné. Vzhledem k několika rovnicím jako „ A = B + C ; B = 5+ D ; C = 4; D = 2;“ pak a . Tuto relaci můžete odvodit přímo: A závisí na B a C , protože můžete přidat dvě proměnné právě tehdy, pokud znáte hodnoty obou proměnných. Tak, B musí být vypočtena před lze vypočítat. Hodnoty C a D jsou však známy okamžitě, protože se jedná o číselné literály. ${\ displaystyle S = \ {A, B, C, D \}}$ ${\ displaystyle R = \ {(A, B), (A, C), (B, D) \}}$

Uznání nemožných hodnocení

V grafu závislostí vedou cykly závislostí (nazývané také kruhové závislosti ) do situace, ve které neexistuje žádný platný pořadí vyhodnocení, protože žádný z objektů v cyklu nelze vyhodnotit jako první. Pokud závislostní graf nemá žádné kruhové závislosti, vytvoří směrovaný acyklický graf a pořadí hodnocení lze najít topologickým tříděním . Většina topologických třídicích algoritmů je také schopna detekovat cykly ve svých vstupech; může však být žádoucí provádět detekci cyklu odděleně od topologického třídění, aby bylo zajištěno vhodné zpracování detekovaných cyklů.

Předpokládejme jednoduchou kalkulačku dříve. Systém rovnic " A = B ; B = D + C ; C = D + A ; D = 12;" obsahuje některá kruhová závislost tvořený A , B a C , jak B, musí být vyhodnocen před A , C , musí být vyhodnocen před B a musí být vyhodnocen před C .

Odvození hodnotící objednávky

Správné vyhodnocení pořadí je číslování objektů, které tvoří uzlové body na grafu závislosti, takže následující rovnice platí: s . To znamená, že pokud číslování objednává dva prvky a tak, že budou vyhodnoceny dříve , pak nesmí záviset na . ${\ displaystyle n: S \ rightarrow \ mathbb {N}}$ ${\ displaystyle n (a) <n (b) \ Rightarrow (a, b) \ notin R}$ ${\ displaystyle a, b \ v S}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a}$ ${\ displaystyle b}$

Může existovat více než jedna správná objednávka hodnocení. Ve skutečnosti je správné číslování topologické pořadí a jakékoli topologické pořadí je správné číslování. Jakýkoli algoritmus, který odvozuje správné topologické pořadí, tedy odvozuje správné pořadí vyhodnocení.

Předpokládejme ještě jednou jednoduchou kalkulačku shora. Vzhledem k systému rovnic „ A = B + C ; B = 5+ D ; C = 4; D = 2;“ by bylo správné pořadí vyhodnocení ( D , C , B , A ). ( C , D , B , A ) je však také správné pořadí hodnocení.

Monoidní struktura

Acyklický graf závislosti odpovídá stopě stopového monoidu takto:

Funkce označí každý vrchol symbolem z abecedy ${\ displaystyle \ phi: S \ k \ Sigma}$ ${\ displaystyle \ Sigma}$
Existuje hrana nebo pokud a pouze pokud je v relaci závislosti . ${\ displaystyle a \ to b}$ ${\ displaystyle b \ to a}$ ${\ displaystyle (\ phi (a), \ phi (b))}$ ${\ displaystyle D}$
Dva grafy se považují za rovnocenné, pokud si jejich popisky a okraje odpovídají.

Řetězec skládající se ze štítků vrcholů seřazených podle správného pořadí vyhodnocení odpovídá řetězci stopy.

Monoidal operace trvá nesouvislý unii z vrcholů sad dva grafy, zachovává stávající hrany v každém grafu, a čerpá nové hrany z první do druhé, kde je vztah závislost umožňuje, ${\ displaystyle (S_ {12}, R_ {12}) = (S_ {1}, R_ {1}) \ odrážka (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 \ v S_ {1} \ land b \ v S_ {2} \ land (\ phi (a), \ phi (b)) \ ​​v D \}}

Identita je prázdný graf.

Příklady

Grafy závislosti se používají v:

Automatizovaní instalátoři softwaru : Procházejí graf a hledají softwarové balíčky, které jsou vyžadovány, ale ještě nejsou nainstalovány. Závislost je dána spojením balíků.
Softwarové skripty jako Unix Make , Node npm install, php composer, Twitter bower install nebo Apache Ant . Potřebují vědět, jaké soubory se změnily, takže je třeba překompilovat pouze správné soubory.
V technologii kompilátoru a implementaci formálního jazyka :
- Plánování instrukcí : Závislostní grafy se počítají pro operandy montážních nebo přechodných instrukcí a používají se k určení optimálního pořadí instrukcí.
- Odstranění mrtvého kódu : Pokud na straně proměnné nezávisí žádná vedlejší operace, je tato proměnná považována za mrtvou a může být odstraněna.
Dynamická analýza grafů: GraphBolt a KickStarter zachycují závislosti hodnot pro přírůstkové výpočty při změně struktury grafu.
Tabulkové kalkulačky. Musí odvodit správné pořadí výpočtu podobné tomu v příkladu použitém v tomto článku.
Standardy webových formulářů, jako je XForms, aby věděly, jaké vizuální prvky se mají aktualizovat, pokud se data v modelu změní.
Videohry, zejména logické a dobrodružné videohry , které jsou často koncipovány jako graf závislých vztahů mezi akcemi ve hře.

Závislostní grafy jsou jedním aspektem:

Typy výrobních závodů : Suroviny se zpracovávají na výrobky v několika závislých fázích.
Plánování pracovního místa : Sbírka souvisejících teoretických problémů v informatice.

Viz také

Reference

Balmas, Francoise (2001) Zobrazení závislostních grafů: hierarchický přístup , [1] wcre, str. 261, Eighth Working Conference on Reverse Engineering (WCRE'01)

Languages

In other projects