Omezovací graf (rozložení) - Constraint graph (layout)

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: Rozvržení „graf omezení“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Dubna 2011) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

V některých úkolech uspořádání integrovaných obvodů design vyvstává nutnost optimalizovat umístění nepřekrývajících se objektů v rovině. Obecně je tento problém extrémně těžký a pro jeho řešení pomocí počítačových algoritmů jsou stanoveny určité předpoklady o přípustných umístěních a o operacích povolených při úpravách umístění. Omezovací grafy zachytit omezení relativních pohybů objektů umístěných v rovině. Tyto grafy, i když sdílejí společnou myšlenku, mají jinou definici v závislosti na konkrétním úkolu návrhu nebo jeho modelu.

Půdorys

v plánování, model půdorysu z integrovaný obvod je sada izotetické obdélníky zvané „bloky“ ve větším obdélníku zvaném „hranice“ (např. „čip hranice ","buňka hranice").

Možná definice omezovacích grafů je následující. Omezovací graf pro daný půdorys je a řízený graf se sadou vrcholů je sada bloků podlahových plánů a existuje hrana z bloku b1 do b2 (nazývá se horizontální omezení), pokud je b1 zcela nalevo od b2 a existuje hrana z bloku b1 do b2 (nazývá se vertikální omezení), pokud je b1 úplně pod b2.

Pokud jsou uvažována pouze horizontální omezení, získá se horizontální omezení graf. Pokud jsou uvažována pouze vertikální omezení, získá se graf vertikálního omezení.

Podle této definice může mít omezující graf tolik ${ displaystyle O (n ^ {2})}$ hrany, kde n je počet bloků. Proto se uvažuje o jiných, méně hustých grafech omezení. The horizontální viditelnost graf je graf horizontálního omezení, ve kterém horizontální omezení mezi dvěma bloky existuje, pouze pokud existuje segment vodorovné čáry, který spojuje dva bloky a neprotíná žádné další bloky. Jinými slovy, jeden blok je potenciální „okamžitou překážkou“ pro horizontální pohyb jiného. The graf vertikální viditelnosti je definován podobným způsobem.

Směrování kanálu

Příklad směrování kanálu

Směrování kanálu je problém směrování sady sítí N které mají pevné terminály na dvou protilehlých stranách obdélníku („kanál“). V této souvislosti horizontální omezení graf je neorientovaný graf se sadou vrcholů N a dvě sítě jsou spojeny hranou tehdy a jen tehdy, pokud se musí horizontální segmenty trasy překrývat. V uvedeném příkladu pouze sítě 5 a 6 nemají mezi sebou horizontální omezení. The graf vertikálního omezení je řízený graf se sadou vrcholů N a dvě sítě jsou spojeny hranou tehdy a jen tehdy, pokud jsou na stejné svislé čáře dva kolíky z různých sítí a hrana je směrována ze sítě pomocí kolíku na horním okraji kanálu. Tento směr znamená, že tato síť musí být vedena na vodorovné trati nad vodorovnými tratěmi druhé sítě. V uvedeném příkladu mají vertikální omezení pouze sítě 1 a 3.^[1]

Reference