Přepisování grafů - Graph rewriting
v počítačová věda, transformace grafunebo přepis grafu, se týká techniky vytváření nového graf z původního grafu algoritmicky. Má mnoho aplikací, od softwarové inženýrství (konstrukce softwaru a také softwarové ověření ) až algoritmy rozvržení a generování obrázků.
Transformace grafu lze použít jako abstrakci výpočtu. Základní myšlenkou je, že pokud lze stav výpočtu vyjádřit jako graf, lze další kroky v tomto výpočtu znázornit jako pravidla transformace v daném grafu. Tato pravidla se skládají z původního grafu, který se má shodovat s podgrafem v úplném stavu, a z nahrazujícího grafu, který nahradí odpovídající podgraf.
Formálně graf přepis systém obvykle sestává ze sady pravidel přepisování grafů ve formuláři , s se nazývá vzorový graf (nebo levá strana) a se nazývá náhradní graf (nebo pravá strana pravidla). Pravidlo přepsání grafu se použije na hostitelský graf vyhledáním výskytu vzorového grafu (porovnávání vzorů, čímž řeší problém izomorfismu podgrafu ) a nahrazením nalezeného výskytu instancí grafu nahrazení. Pravidla pro přepis lze dále upravit v případě označené grafy, například v řetězcem regulovaných grafových gramatikách.
Někdy grafová gramatika se používá jako synonymum pro systém přepisování grafů, zejména v kontextu formální jazyky; různé formulace se používají ke zdůraznění cíle konstrukcí, jako je výčet všech grafů z nějakého počátečního grafu, tj. generování jazyka grafu - namísto pouhé transformace daného stavu (hostitelského grafu) do nového stavu.
Přístupy k přepisování grafů
Algebraický přístup
The algebraický přístup přepis grafu je založen na teorie kategorií. Algebraický přístup se dále dělí na dílčí přístupy, z nichž nejběžnější jsou dvojí přístup (DPO) a single-pushout (SPO) přístup. Mezi další dílčí přístupy patří sesqui-pushout a zarazit přístup.
Z pohledu přístupu DPO je pravidlo přepisování grafů dvojice morfismy v kategorii grafů a homomorfismy grafů mezi nimi: (nebo ) kde je injekční. Nazývá se graf K. neměnný nebo někdy lepicí graf. A přepis krok nebo aplikace pravidla r až a hostitelský graf G je definováno dvěma vystrčit obě schémata pocházející ze stejného morfismus , kde D je a kontextový graf (tady je jméno dvojnásobek-pushhout pochází z). Další morfismus grafů modeluje výskyt L v G a nazývá se a zápas. Toto je praktické pochopení je podgraf, který odpovídá (vidět problém izomorfismu podgrafu ) a po nalezení shody, je nahrazen v hostitelském grafu kde slouží jako rozhraní obsahující uzly a hrany, které jsou při aplikaci pravidla zachovány. Graf je potřeba k připojení porovnávaného vzoru k jeho kontextu: pokud je prázdný, může shoda označit pouze celou připojenou součást grafu .
Naproti tomu je pravidlo přepisování grafů v přístupu SPO jediným morfismem v kategorii označené multigrafy a částečné mapování které zachovávají multigrafickou strukturu: . Krok přepisování je tedy definován jediným vystrčit diagram. Praktické pochopení je podobné přístupu DPO. Rozdíl je v tom, že neexistuje žádné rozhraní mezi hostitelským grafem G a grafem G ', který je výsledkem kroku přepisování.
Z praktického hlediska je klíčovým rozdílem mezi DPO a SPO to, jak se vypořádají s odstraněním uzlů se sousedními hranami, zejména jak se vyhnou tomu, aby takové delece mohly zanechat „visící hrany“. Přístup DPO odstraní uzel pouze tehdy, když pravidlo určuje také odstranění všech sousedních hran (toto visící stav lze zkontrolovat pro danou shodu), zatímco přístup SPO jednoduše disponuje sousedními hranami, aniž by vyžadoval výslovnou specifikaci.
Existuje také další algebraický přístup k přepisování grafů, založený hlavně na booleovské algebře a algebře matic, tzv. gramatiky maticového grafu.[1]
Určete přepis grafu
Ještě další přístup k přepisování grafů, známý jako určit přepisování grafů, vyšlo z logika a teorie databáze.[2] V tomto přístupu jsou grafy považovány za instance databáze a operace přepisování jako mechanismus pro definování dotazů a zobrazení; pro získání jedinečných výsledků je proto nutné veškeré přepisování (až do izomorfismu ), a toho je dosaženo současným uplatněním jakéhokoli pravidla přepisování v celém grafu, ať se použije kdekoli, a to takovým způsobem, aby byl výsledek skutečně jednoznačně definován.
Přepis termínu grafu
Další přístup k přepisování grafů je termínový graf přepis, který zahrnuje zpracování nebo transformaci termínových grafů (také známých jako abstraktní sémantické grafy) sadou pravidel syntaktického přepisování.
Termínové grafy jsou významným tématem výzkumu programovacího jazyka, protože pravidla pro přepisování termínových grafů jsou schopna formálně vyjádřit překladač operační sémantika. Termínové grafy se také používají jako abstraktní stroje schopné modelovat chemické a biologické výpočty a také grafické výpočty, jako jsou modely souběžnosti. Termínové grafy mohou fungovat automatické ověření a logické programování, protože jsou vhodné pro reprezentaci kvantifikovaných příkazů v logice prvního řádu. Software pro symbolické programování je další aplikace pro termínové grafy, které jsou schopné reprezentovat a provádět výpočty s abstraktními algebraickými strukturami, jako jsou skupiny, pole a prstence.
Konference TERMGRAPH[3] se plně zaměřuje na výzkum přepisování termínových grafů a jeho aplikací.
Třídy gramatiky grafů a systému přepisování grafů
Systémy přepisování grafů se přirozeně seskupují do tříd podle druhu zastoupení použitých grafů a způsobu vyjádření přepisů. Termín grafová gramatika, jinak ekvivalentní systému přepisování grafů nebo systému nahrazování grafů, se nejčastěji používá v klasifikacích. Některé běžné typy jsou:
- Přiřazené gramatiky grafů, obvykle formalizované pomocí buď single-pushout přístup nebo dvojitý přístup k charakterizaci náhrad, zmíněných ve výše uvedené části o algebraickém přístupu k přepisování grafů.
- Hypergrafické gramatiky, včetně přísnějších podtříd gramatiky portových grafů, lineární grafové gramatiky a interakční sítě.
Implementace a aplikace
Grafy jsou expresivní, vizuální a matematicky přesný formalismus pro modelování objektů (entit) propojených vztahy; objekty jsou reprezentovány uzly a vztahy mezi nimi hranami. Uzly a hrany jsou běžně zadávány a přiřazovány. Výpočty jsou v tomto modelu popsány změnami vztahů mezi entitami nebo změnami atributů prvků grafu. Jsou zakódovány v pravidlech přepisování grafů / transformaci grafů a prováděny systémy pro přepisování grafů / nástroji pro transformaci grafů.
- Nástroje, které jsou neutrální pro doménu aplikace:
- AGG, systém přiřazené gramatiky grafu (Jáva )
- GP (grafické programy) je programovací jazyk pro výpočet grafů pomocí cílené aplikace pravidel transformace grafů.
- GMTE, Engine shody a transformace grafů pro shoda grafu a transformace. Jedná se o implementaci rozšíření Messmerova algoritmu pomocí C ++.
- GrGen.NET, generátor přepisování grafů, emitující nástroj pro transformaci grafů C# -kód nebo sestavení .NET
- DRÁŽKA, sada nástrojů na bázi Java pro úpravy grafů a pravidel transformace grafů, zkoumání stavových prostorů gramatik grafů a kontrolu modelů těchto stavových prostorů; lze také použít jako motor pro transformaci grafů.
- Verigraf, systém specifikace a ověření softwaru založený na přepisování grafů (Haskell ).
- Nástroje, které řeší softwarové inženýrství úkoly (hlavně MDA ) s přepisem grafu:
- eMoflon, nástroj pro transformaci modelů kompatibilní s EMF s podporou pro Story-Driven Modeling a gramatiky trojitého grafu
- EMorF systém přepisování grafů založený na EMF, podpora na místě a model-to-model proměna
- Fujaba používá modelování založené na příběhu, jazyk přepisování grafů založený na PROGRESU
- Grafové databáze často podporují dynamické přepisování grafů
- Skvělý
- Skřítek, programovací jazyk založený na grafech (viz Přepisování grafů )
- Henshin, systém přepisování grafů založený na EMF, podpora na místě a model-to-model proměna, analýza kritických párů, a kontrola modelu
- POKROKY, integrované prostředí a jazyk na velmi vysoké úrovni pro PROgrammed Graph REwriting Systems
- VIATRA
- Nástroje pro strojírenství
- GraphSynth je prostředí tlumočníka a uživatelského rozhraní pro vytváření neomezených gramatických grafů a testování a vyhledávání výsledné jazykové varianty. Ukládá grafy a pravidla gramatiky grafů jako XML soubory a je zapsán v C#.
- Studio Soley, je integrované vývojové prostředí pro systémy transformace grafů. Jeho hlavním aplikačním zaměřením je datová analýza v oblasti strojírenství.
- Aplikace biologie
- Umělá inteligence / Zpracování přirozeného jazyka
- OpenCog poskytuje základní porovnávač vzorů (na hypergrafy ), který se používá k implementaci různých algoritmů AI.
- RelEx je analyzátor v anglickém jazyce, který k přepisu a. využívá přepis grafu analýza odkazu do analýza závislosti.
Viz také
Poznámky
Reference
Citace
- ^ Perez 2009 pokrývá tento přístup podrobně.
- ^ „Graficky orientovaný objektový model pro rozhraní koncového uživatele databáze“ (PDF).
- ^ „TERMGRAPH“.
Zdroje
- Rozenberg, Grzegorz (1997), Handbook of Graph Grammars and Computing by Graph Transformations, Svazky 1–3, Světové vědecké nakladatelství, ISBN 9810228848.
- Perez, P.P. (2009), Maticové grafové gramatiky: Algebraický přístup k dynamice grafů, VDM Verlag, ISBN 978-3-639-21255-6.
- Heckel, R. (2006). Stručně řečeno, transformace grafu. Elektronické poznámky v teoretické informatice 148 (1 SPEC. ISS.), S. 187–198.
- König, Barbara (2004). Analýza a verifikace systémů s dynamicky se rozvíjející strukturou. Habilitační práce, Universität Stuttgart, str. 65–180.
- Lobo, Daniel; Vico, Francisco J .; Dassow, Jürgen (01.10.2011). "Grafové gramatiky s řetězcově regulovaným přepisováním". Teoretická informatika. 412 (43): 6101–6111. doi:10.1016 / j.tcs.2011.07.004. ISSN 0304-3975.