9. Systém pro generování grafů a jeho uživatelské rozhraní

Ing. Petr Hrubý, Praha


9.1 Úvod

9.1.1 Cíl práce

Cílem této práce je navrhnout a implementovat uživatelské rozhraní, které by umožňovalo nevidomým uživatelům interaktivně vytvářet obrázky. Termín obrázek se zde chápe jako planární graf z teorie grafů (viz dále). Systém by měl umožňovat:

Program je v podstatě určen pouze pro nevidomé uživatele (byl vypracován v těsné spolupráci s panem Kučerou, který je nevidomý). Proto je potřeba ovládání programu plně podřídit komunikačním možnostem (vstupní a výstupní zařízení), které nevidomý uživatel při svém kontaktu s počítačem používá.

Při vlastní implementaci by měl být program vytvářen se zřetelem na jeho pozdější úpravy a rozšiřování jeho možností. Program by měl být dobře strukturovaný a měly by být odděleny části týkající se uživatelského rozhraní a algoritmy generující výsledný obrázek.

9.2 Teorie grafů a její uplatnění v programu

9.2.1Grafy

Většina jednoduchých obrázků typu adresářové struktury, vývojové diagramy, E-R, diagramy, diagramy datových toků, kontextové diagramy atd. mají při bližším zkoumání některé společné vlastnosti. Obsahují množství uzlů, které jsou různým způsobem pospojovány hranami. Když půjdeme ještě dále, tak můžeme říci, že i lomená čára je jakýmsi grafem, ve kterém se uzly chápou pouze jako body. Pomocí lomené čáry je možné nakreslit i skutečné obrázky čárového charakteru – např. domeček. Vraťme se ale k původním příkladům. Všechny zmíněné příklady jsou tedy orientovanými, nebo neorientovanými grafy z hlediska teorie grafů.

9.2.2 Grafická forma grafů

Definice grafů nic neříká o konkrétní grafické formě nakresleného grafu. Člověk, který se chystá nakreslit např. adresářovou strukturu, ví, že nahoře by měl být hlavní adresář (kořen) a dole soubory (listy). Kromě toho je však třeba nějakým způsobem přidat do grafu informaci o umístění jednotlivých grafických objektů. Když ale například zadáme absolutní souřadnice uzlů v souřadnicích používaných v Postscriptu (jazyk pro popis tištěných stránek viz. podkapitola 5.2), tak jednak může být tento údaj dosti nepřehledný (řekněme dvě trojciferná čísla) a jednak se při změně struktury grafu mohou souřadnice podstatně změnit.

Právě z důvodu změny struktury grafu je nutné používat "relativní" grafické informace, které se vztahují k bezprostřednímu okolí grafického objektu (např. sousední spoje uzlu). Tyto informace pak zůstávají zachovány při změnách v jiných místech grafu. Absolutní souřadnice (v našem případě postscriptové) jsou vygenerovány v později zmíněném algoritmu až těsně před vlastním vytištěním obrázku do postscriptového souboru.

Uvažujeme nejbližší okolí každého spoje. Tímto okolím jsou jeho dva krajní uzly – počáteční a koncový. Existuje několik možností, jak a v kterých místech napojit k počátečnímu uzlu spoj a také jak a kde tento spoj u koncového uzlu zakončit. V našem systému jsme se omezili pouze na 8 "připojovacích" míst, které odpovídají osmi světovým stranám (S, SV, V, JV, J, JZ,Z, SZ). Ke každému spoji přidáváme vedle informace o počátečním a koncovém uzlu také informaci o světových stranách, kterými se spoj napojuje k uzlu.

Obě světové strany, které se udávají u spoje musí být "protilehlé". To znamená, že nelze sestrojit spoj vedoucí z uzlu u1 ze severu do uzlu u2 na jihozápad, ale pouze na jih. Vytvářejí se tak vždy dvojice protilehlých stran (S-J, JV-SZ, V-Z, …). Obr 9.1 ukazuje 8 uzlů, které sousedí s uzlem 1. Světové strany uváděné u dotyku spoje a uzlu se uvádějí u každého spoje.

Počet připojených spojů k jednomu uzlu se tedy omezil na 8 – vždy pouze jeden spoj na jednu světovou stranu. Toto omezení však platí pouze pro tzv. obecné grafy – nikoliv pro stromy. Tyto dva pojmy budou vysvětleny později.

Co se týče grafické formy grafu, je potřeba ještě zdůraznit, že spoje chápeme pouze jako úsečky. Není tedy možné vytvářet jakési oblouky, různě zaoblené křivky nebo lomené čáry.

příklad grafu

Obrázek 9.1: Příklad grafu

9.3 Přístup nevidomého uživatele k systému Představa uživatele byla taková, že interaktivní zadávání uzlů a spojů se bude podobat jednoduchým textovým hrám. Celý graf je jakýsi labyrint složený z místností (uzlů), které mají celkem 8 dveří (odpovídá 8 světovým stranám). Mezi jednotlivými místnostmi jsou různě dlouhé chodby (spoje).

Pro nevidomého uživatele má interaktivní procházení grafem velký význam. Nevidomý se prý dokáže představit graf s nejvýše osmi až deseti uzly, které jsou hustě pospojovány hranami. Při větším počtu uzlů v grafu se dokáže soustředit jen na určitý podgraf – řekněme o pěti uzlech. Z toho tedy vyplývá požadavek na poskytování lokálních informací – např. uzly, do kterých se dostanu z daného uzlu přes maximálně jeden spoj. Nevidomý uživatel by se bez informací mohl rychle v grafu "ztratit".

První verze systému neobsahovala interaktivní ovládání a sloužila pouze pro převod dat, která popisují graf, do postscriptového souboru. Systém byl pro nevidového uživatele použitelný jen pro malé množství grafických objektů (uzlů a spojů). Uživatel se mohl soustředit pouze na graf jako celek. Teprve s pomocí interaktivního ovládání se může uživatel soustředit na malé podgrafy, pracovat pouze s lokálními informacemi a odklonit se od globálního pohledu na graf. Je však samozřejmě možné se dotazovat i na globální vlastnosti grafu, např. počet nepřipojených uzlů.

9.4 Komunikace programu s uživatelem

Nevidomý uživatel má pro ovládání programu k dispozici pouze jedno vstupní zařízení – klávesnici a pouze jedno výstupní zařízení – zvukovou kartu se sluchátky (neuvažujeme zde moderní systémy, které je možné ovládat mikrofonem). Zvuková karta (např. Sound Blaster) obsahuje převodník textu na odpovídající signál, který pak posílá do sluchátek. V počítači běží rezidentní program, který zachytává všechny textové výstupy na obrazovku, a posílá je na zvukovou kartu. Nejsou to jenom výstupy, které jsou zachytávány rezidentním program, ale i vstupy s odezvou – např. zadávání textu z klávesnice při současném výstupu zadaného textu na obrazovku.

Z programátorského hlediska může uživatel rozhraní pro nevidomé uživatele používat pro vstupy a výstupy pouze příkazy Read a Write známe z Pascalu, resp. Scanf a Printf známé z jazyka C.

Informační výstup systému je nutné podřídit zmíněnému rezidentnímu programu. Mám tím na mysli např. používání nealfanumerických znaků (znak "(" je převeden do sluchátek jako "levá závorka" a řetězec "(A/N)" zazní ve sluchátkách takto: "levá závorka a lomeno a pravá závorka"). Pro uživatele, který se systémem začíná, může častější používání těchto znaků sloužit k lepšímu porozumění problému. Naproti tomu pro uživatele, který systém používá denně, je jejich používání spíše zdržováním. Proto je potřeba při jejich používání zvolit určitý kompromis.

V novějších rezidentních programech je možné nejen zachytávat poslední výstup na obrazovku, ale je zde i možnost tzv. "lezení po obrazovce" screen reader). To znamená, že obrazovka, která má 25 řádků a 80 sloupců, slouží jako mřížka, po které je možné se pohybovat pomocí šipkových kláves. Zavádí se pomyslný kurzor, který udává aktuální řádku a aktuální sloupec. Do sluchátek se posílá slovo, které se nachází na místě pomyslného kurzoru. Nevidomému uživateli to pomáhá při zjišťování historie příkazů a jejich odezev. Tato historie je ale omezena právě 25 řádky obrazovky.

V našem systému se tedy při výstupu informací na obrazovku musíme snažit maximálně zaplňovat jednotlivé řádky dlouhými informacemi a přecházet na další řádek (v případě delších zpráv), až když už se slovo nevejde na řádek. Zvětší se tím počet příkazů, které se vejdou na obrazovku, a tím i zmíněná historie.

V původním návrhu se uvažovalo o možnosti použít akustického navádění myší. Mělo se jednat o určitou modifikaci hry “samá voda, přihořívá, hoří”, kdy má být tímto způsobem uživatel naveden na požadovaný uzel. Při pohybu myši se mělo ozývat pípání, které mělo být silnější se snižující se vzdáleností od uzlu. Tento návrh byl zamítnut z toho důvodu, že nevidomí uživatelé myš vůbec nepoužívají a museli by si ji pořizovat jenom pro tento program.

9.5 Reprezentace výsledků obrázku

Jedním z hlavních požadavků nevidomého uživatele byl výstup do postscriptového souboru, ale ne přímo na tiskárnu. Důvod je ten, že pro některé nevidomé uživatele (mezi nimiž je i náš uživatel) je Postscript jazykem číslo 1 pro grafickou reprezentaci svých obrázků, grafů a diagramů. Většina dnešních tiskáren je "postscriptových".

To znamená, že je možné takovou tiskárnu přepnout do postscriptového režimu a poslat na tiskárnu přímo soubor *.PS. V postscriptových tiskárnách je speciální tiskový procesor, který funguje jako interpret postscriptového jazyka.

Hlavní výhodou Postscriptu ve vztahu k nevidomým uživatelům (a samozřejmě nejen k nim) je nejen možnost popsat obrázek pomocí grafických primitiv (čára, kružnice, text apod.) a jejich atributů (barva – případně stupně šedi, typ čáry, stíny), ale také pracovat s Postscriptem jako s plnohodnotným programovacím jazykem.

Je možné definovat procedury, proměnné a lze používat klasické jazykové konstrukce, jako jsou cykly, podmíněné příkazy atd. začínajícím uživatelům může dělat problémy postfixová notace všech příkazů a volání procedur (oproti běžné infixové), ale pro zkušené uživatele je soubor v Postscriptu již snadno čitelný.

V našem sytému byly rovněž použity procedury pro kreslení uzlů a spojů, a to hned z několika důvodů. Hlavním důvodem je zkrácení a zpřehlednění výsledného postscriptového souboru. Těžko by se mohl dále zpracovávat soubor, ve kterém by bylo popsáno umístění sto čar a dvaceti textů v postscriptových souřadnicích. Dalším důvodem je například nemožnost zjistit v programu (napsaném např. v jazyce C) některé grafické informace, jako je třeba přesná šířka různě dlouhého textu v postscriptových souřadnicích (zvláště, když se jedná o proporcionální písmo). Nevidomý uživatel může postscriptový soubor vygenerovaný naším programem dále upravovat – např. měnit velikosti papíru, celkové natočení grafu, intenzitu vykreslování. Nevidomý uživatel může dokonce změnit námi vytvořené postscriptové procedury podle svých představ a tím budou od tohoto okamžiku všechny obrázky vypadat tak, jak definují nové postscriptové procedury. Je možné také nastavovat další parametry, které jsou potřebné pro tisk na speciální tiskárně určené pro nevidomé uživatele a na kterých se místo tisku mění povrchová úprava papíru (např. různé vrypy a výstupky).

9.6 Hardwarové a softwarové požadavky systému

Náš systém nevyžaduje žádné zvláštní požadavky na hardware, ani na software. Co se týče softwaru, tak pracuje pod operačním systémem MS DOS. Systém byl odladěn na počítači 386SX/25 a pro jednoduché grafy běžel velice rychle. Při vytváření složitějších grafů (např. spirály zmíněné v kapitole 2.3.2 přiložené diplomové práce [4] (též příloha D – viz tabulka doby generování spirály pro různý počet uzlů) se může zdát takováto konfigurace nevyhovující. V tom případě doporučujeme počítač řady 486 a vyšší. Systém je, co se týče paměti, velice skromný a vystačí s pamětí 640K. Existence i jen velice malé vyrovnávací paměti v počítači (Cache) výrazně přispěje ke zrychlení běhu algoritmů.

9.7 Závěr

9.7.1 Hodnocení práce

Může se říci, že úkol byl ve smyslu zadání splněn. Vzhledem k tomu, že se jedná o jedno z prvních uživatelských rozhraní pro nevidomé uživatele, nebyla ještě přesně stanovena kritéria pro tato rozhraní. Toto rozhraní bylo vytvářeno v těsné spolupráci s nevidomým uživatelem, a proto, zejména pokud jde o interaktivní ovládání, byly jednotlivé příkazy uskutečňovány pokud možno co nejvíce podle jeho přání.

Spolupráce s naším nevidomým uživatelem byla velmi usnadněna tím, že tento uživatel přesně ví, co můžeme od počítače a programu na něm provozovaném očekávat, co je na něm realizovatelné a co nikoliv. Jeho požadavky byly proto formulovány přibližně stejným způsobem, jak byly i později realizovány. Náš uživatel občas i programuje, takže systém byl řešen i s ohledem na tento fakt – například možnost změn postscriptových procedur nezávisle na systému samotném.

Je možné, že jiný nevidomý uživatel by formuloval požadavky na ovládání programu trochu jiným způsobem, nicméně vlastní jádro a algoritmy v něm by zůstaly. V další kapitole jsou vyjmenovány některé možnosti rozšíření, o kterých jsme s naším uživatelem diskutovali, ale které se již do této diplomové práce nevešly. Tento systém se bude i nadále rozvíjet a některé tyto možnosti budou v dalších verzích systému již obsaženy.

9.7.2 Možnosti rozšíření

Jak už to u softwarových produktů bývá, program není nikdy definitivně hotov.

Vždy se najdou buď chyby, nebo možnosti vylepšování, anebo možnosti rozšiřování. Jinak tomu není ani u našeho systému. Věřím, že chyb je v programu co možná nejméně, a jsou-li tam nějaké, tak takové, které nemohou výraznějším způsobem omezit, nebo dokonce znehodnotit práci uživatele. Všimněme si proto některých možností vylepšování a rozšiřování podle modulů popsaných v kapitole 3.3.1 diplomové práce [4].

INTERAKTIVNÍ OVLÁDÁNÍ

Nevidomí uživatelé jsou zvyklí používat příkazové systémy – např. operační systémy MS-DOS nebo UNIX. Náš systém má sice zabudovány jednotlivé příkazy, ale jejich spouštění je pomocí menu. Nabízí se tedy možnost spojit oba způsoby ovládání. Asi nejúspěšnějším takovým pokusem se stal Norton Comander – nadstavba nad operačním systémem pro práci se soubory. V tomto systému je uživateli umožněno pomocí šipkových kláves pohybovat se po seznamech souborů v adresářích a po menu, zároveň na spodním řádku obrazovky zadávat z klávesnice normální DOSovské příkazy. Proto se nabízí možnost používat šipkové a horké klávesy v našem systému stejným způsobem jako v nynější verzi, ale po zadání nějakého znaku z klávesnice (řekněme znak "!") přepnout do příkazového režimu. Příkazový řádek – např. pro vytvoření nového uzlu – by vypadal následovně:

Novy uzel generuj 'mail' oval F10

Slovo generuj znamená, že se má vygenerovat identifikátor uzlu – viz kapitola 4.3.2 diplomové práce [4]. Po provedení příkazu by buď došlo k návratu do menu, nebo by zůstal aktuální příkazový režim, za kterého by opět pomocí nějaké klávesy došlo k přepnutí do menu.

VSTUPY A VÝTUPY

Jedno z možností rozšíření, které navrhl nevidomý uživatel, je používat náš systém jako jakýsi objektový editor. Jednotlivé objekty (byly by opět typu uzel nebo spoj) by byly popsány v knihovně. V této knihovně by musely být popsány následující záležitosti: způsob vykreslení objektu – např. ve formě postscriptové procedury, pomocí nějakého jednoduchého jazyka by byly popsány jednotlivé atributy, které by se u objektu zadávaly v našem systému – např. velikost objektu, definice rozhraní našeho systému s výsledným postscriptovým souborem (volání jednotlivých postscriptových procedur s jejich parametry atd.), definice rozhraní našeho systému s definičním souborem grafu – např. uzel Počítač z knihovny Komponenty, …

Takovými předdefinovanými objekty umístěnými v knihovně by byly obrázky přístrojů používaných v lokálních sítích (servery, terminály, bridge, …) a taková knihovna by se mohla nazývat např. Síť.

ZMĚNY VE STRUKTUŘE GRAFU

Zde by se zřejmě nejednalo o změny typu vytvoř uzel apod., ale mohly by zde být definovány procedury typu "podstrom s kořenem 'Aplikace' ulož pod jménem Aplikace.xnd", nebo naopak umístění podstromu pod nějaký uzel atd.

ALGORITMY PRO GENEROVÁNÍ A TESTOVÁNÍ VÝSLEDNÉHO OBRÁZKU

U této části si popišme jen jednu možnost rozšíření, a sice modifikaci algoritmu zpětného procházení, kterým není možné např. vykreslit graf popsaný v odstavci 2.3.3 diplomové práce [4]. Kdyby se v mřížce čtverečků použité u algoritmu zpětného procházení použily přímo identifikátory uzlů, zjistili bychom, že nám ve vykreslení nového uzlu A na obr. 9.2 "překáží" uzel 3. Tento uzel bychom tedy dočasně zvolili jako kořen a spoj vedoucí opačným směrem by se na skoro uzavřené cestě ke kořeni vždy našel.
přidávání uzlu
Obrázek 9.2: Přidávání uzlu
 Je zřejmé, že zde nemůžeme uvést ucelený seznam možných rozšíření a vylepšení programu. Proto je potřeba brát několik zmíněných bodů pouze jako několik příkladů. Nicméně kdyby takový systém všechny zmíněné body obsahoval, jednalo by se zřejmě o větší projekt, který by muselo řešit více programátorů.



Příloha D



Příklady výstupů generátoru grafů

Počet uzlů 14 15 16 17 18 19 20 21 22 23 24
Čas (M:S) 0:11 0:27 0:36 0:45 1:13 1:40 3:40 4:28 16:24 20:40 24:59


Tabulka D.1: Dosažené časy v závislosti na počtu generovaných uzlů


spirála


Obrázek D.1: Spirála


spirála s 21 uzly


Obrázek D.2: Spirála s 21 uzly


strom


Obrázek D.3: Strom


PŘEDCHOZÍ KAPITOLA OBSAH  NÁSLEDUJÍCÍ KAPITOLA


[Domů  | Zpět]
Náměty a připomínky zasílejte na: web@braillnet.cz
Copyright © 1995 - 1999 SONS