Algorithm Animation Pages
WinSANAL System Home Page

STRESZCZENIE

WinSanal to system animacji algorytmow sterowany danymi. Zawiera pewne mechanizmy programu uruchamiajacego (debuggera) z interfejsem graficznym. Daje mozliwosc plynnej prezentacji w postaci graficznej zawartosci struktur danych przetwarzanych przez program i ich zmian. Umozliwia inspekcje danych i modyfikowanie ich wartosci za posrednictwem okienek dialogowych i przez interakcje z elementami graficznymi reprezentujacymi dane. Najistotniejsza czescia przygotowania prezentacji w systemie jest zaprojektowanie i skonfigurowanie sciezek przeplywu danych od zmiennych w programie do elementow graficznych na ekranie, w obecnej wersji systemu wykonywane recznie. W referacie przedstawiono przyklady mozliwosci systemu przy tworzeniu i badaniu zachowania modeli kolejkowych oraz modeli systemow ewolucyjnych.

WSTEP

Jednym z cenniejszych elementow, jakie wnosza komputery do badan naukowych w roznych dziedzinach, jest mozliwosc wizualizacji obiektow, zjawisk i procesow, ktorych mierzalne wlasnosci poddawane sa analizie lub stanowia podstawe do tworzenia modeli i symulacji ich dzialania. Poszczegolne grupy tematow badan moga wymagac zastosowania specyficznych reprezentacji graficznych nawiazujacych do obserwowalnych realiow badz wyobrazen na temat rozpatrywanych obiektow i zjawisk. Dobor srodkow prezentacji zalezy tez od charakteru, ilosci i organizacji danych opisujacych problem. Przeglad problematyki mozna znalezc w [1]. Szczegolna sytuacja zachodzi w przypadku szeregu prac z zakresu informatyki, gdzie przedmiotem zainteresowania sa czesto struktury danych jako takie, przeksztalcenia, jakim sa poddawane, a takze sam proces obliczeniowy, algorytm, w oparciu o ktory jest on realizowany, wzglednie program stanowiacy implementacje tego algorytmu. Przy wykonywaniu takich prac moga byc pomocne systemy wizualizacji algorytmow (lub programow). Jednym z nich jest system WinSanal. Tworzony pierwotnie glownie dla potrzeb dydaktyki informatyki (m.in. nauki programowania i analizy algorytmow), jest stopniowo wyposazany w mechanizmy ulatwiajace wykorzystanie go w eksperymentach zwiazanych z tworzeniem i modyfikacja programow w celach naukowych i wynikajacych z praktyki inzynierskiej.

CHARAKTERYSTYKA SYSTEMU WINSANAL

System WinSanal stanowi nowa, gruntownie zmieniona wersje systemu Sanal opracowanego w Instytucie Informatyki Politechniki Slaskiej w 1989 r. i rozwijanego do r. 1996 [4, 5]. Podobnie, jak system XTango [7, 8] i inne systemy nowej generacji, jest systemem sterowanym danymi. Pracuje w srodowisku MS-Windows i umozliwia wizualizacje programow napisanych w jezyku C++. Zostal zrealizowany z zastosowaniem techniki obiektowej. Jego roboczy opis mozna znalezc w [6].

Z punktu widzenia uzytkownika – obserwatora projekcji, tj. przebiegow zwizualizowanych programow, WinSanal laczy cechy dosc typowego systemu wizualizacji algorytmow, jak Balsa [2, 3] lub wspomniany wyzej system XTango, i programu wspomagajacego uruchamianie (debuggera) sterowanego graficznie. Zadaniem jego jest przedstawienie w trakcie projekcji zawartosci wybranych struktur danych programu w odpowiednio dobranej, sugestywnej formie graficznej. Prezentowane dane graficzne sa przyporzadkowane tzw. widokom, ktorych zawartosc jest wyswietlana w oddzielnych okienkach. System pozwala na umieszczenie obrazow tych samych danych pierwotnych w kilku widokach. Roznicujac reprezentacje graficzna lub uklad obrazu mozna dzieki temu wyeksponowac rozne aspekty danych programu i procesu ich przetwarzania. Dla ulatwienia obserwacji, zmiany danych, w swojej istocie skokowe, prezentowane sa w sposob plynny, przypominajacy animacje filmowa; wizualizacje uwzgledniajaca taka animacje na poziomie zmian okresla sie od pewnego czasu jako animacje programow lub algorytmow [Ze swojej strony prowadzi to do niejednoznacznoœci terminologicznej: o animacji programu mowilo sie [2], gdy wyswietlany obraz odzwierciedlal aktualny stan jego danych i w zwiazku z tym w toku wykonania programu zmienial sie, nawet skokowo] .

W czasie projekcji uzytkownik moze wchodzic z systemem w interakcje. Korzystajac z okienek inspekcyjnych moze badac i precyzyjnie ustawiac wartosci zmiennych, ktorych obraz wskaze w okienku. Dzieki temu, ze dane pierwotne sa dwustronnie sprzezone z reprezentujacymi je elementami graficznymi, zmiane wybranej danej moze on tez wymusic zmieniajac przy pomocy myszki np. rozmiary jej odpowiednika. Oczywiscie, precyzja takich manipulacji jest ograniczona. Aby skopiowac wartosci lub zmienic uklad elementow wizualizowanej struktury mozna uzyc techniki "pociagnij i upusc" (ang. drag and drop).

Wykorzystane w systemie mechanizmy nie ograniczaja a priori (zgodnie z postulatem przedstawionym w [3]) dziedziny zastosowan. System wzglednie latwo moze byc dostosowywany do wymogow prezentacji konkretnego problemu w roznych dzialach informatyki, i nie tylko.

BUDOWA SYSTEMU

System WinSanal, a scislej biorac ta jego czesc, ktora jest odpowiedzialna za realizacje projekcji, ma strukture warstwowa. Poszczegolne warstwy grupuja obiekty systemu odpowiedzialne za poszczegolne etapy przetwarzania danych na drodze od ich zrodla — programu — do widoku i zwiazanego z nim okienka. Sciezke przeplywu danych na tle przekroju warstw systemu przedstawia rys. 1.

Cienie — obiekty zlokalizowane w warstwie cieni (naleza one do klasy CShadow) przechowuja adresy zmiennych oddanych pod nadzor systemu i informacje o ich typie. Za ich posrednictwem system odczytuje lub modyfikuje dane przechowywane w zmiennej.

W warstwie translatorow sa umieszczone translatory (obiekty nalezace do klasy CTranslator). Ich zadaniem jest przeksztalcenie wartosci zmiennej na wartosc aspektu graficznego (np. na wysokosc prostokata reprezentujacego wartosc zmiennej). Niektore translatory moga dokonywac tlumaczenia odwrotnego. Translatory w razie potrzeby mozna laczyc kaskadowo.

W warstwie plynnej animacji zlokalizowane sa obiekty typu CPacer — generatory sekwencji. Wlasnie ich zadaniem jest przedstawienie skokowych zmian wartosci zmiennych w postaci kilku nastepujacych po sobie obrazow posrednich. W zwiazku z generowaniem takich sekwencji obrazow nastepuje rozdzielenie sciezki przeplywu danych na sciezke aspektu glownego elementu graficznego i sciezke aspektu pomocniczego. Aspekt glowny jest zwiazany z wartoscia prezentowanej danej. Aspekt pomocniczy wykorzystuje sie do uwidocznienia kolejnych mikroetapow przemiany ilustrowanej przez generator sekwencji. Jesli na przyklad jako aspekt pomocniczy przyjmiemy numer koloru wypelniajacego element graficzny, to zmiany wartosci reprezentowanych przez wielkosc elementu graficznego (aspekt glowny) mozemy podkreslic powodujac rozblysk koloru, zmieniajac z fazy na faze jego numer. Zauwazmy, ze w warstwie plynnej animacji w sciezke moga byc wlaczone kolejne translatory.

Sciezke przeplywu danych konczy obiekt nazywany przez nas grelem, zawierajacy opis okreslonego elementu graficznego. Grele naleza do klasy CGrel i wchodza w sklad warstwy interfejsu uzytkownika. Wewnetrznymi skladowymi greli sa wartosci aspektow graficznych. W trakcie projekcji funkcje koordynacyjne w stosunku do grup greli spelniaja nie pokazane na rysunku obiekty odpowiadajace widokom, a te z kolei sa podporzadkowane obiektowi – zarzadcy projekcji.

Na obecnym etapie prac w systemie zostaly zaimplementowane klasy cieni odpowiadajacych podstawowym typom skalarnym (liczbowym) i strukturalnym (tablice, rekordy), translatory o charakterystyce przejscia liniowej i sinusoidalnej, klasy greli prostokatnych, eliptycznych i liniowych.

PRZYGOTOWANIE WIZUALIZACJI

Przygotowanie wizualizacji programu zaczynamy od wyboru zmiennych, ktorych wartosci maja byc prezentowane. Dla kazdej z nich ze zbioru dostepnych reprezentacji graficznych wybieramy najbardziej odpowiednia. Nastepnie dla kazdej zmiennej zestawiamy schemat sciezki przeplywu danych, dobierajac wlasciwy typ cienia, potrzebne translatory wartosci dla poczatkowej i koncowej czesci sciezki, oraz generator sekwencji; sciezke rejestrujemy w systemie. Na koniec ustawiamy parametry obiektow wchodzacych w sklad sciezek. Wreszcie rozmieszczamy w programie wywolania funkcji powodujacych odczytanie przez system aktualnego stanu okreslonej czesci danych programu, ich przetworzenie i wygenerowanie niezbednej sekwencji obrazow.

W chwili pisania tego artykulu przygotowanie programu do projekcji jest wykonywane "recznie", przy czym prace moga byc czesciowo zmechanizowane: opracowano wzorcowe pliki konfiguracyjne zawierajace zestawy danych opisujacych wlasciwosci podstawowych rodzajow greli. Przygotowujac wlasna wizualizacje wystarczy powielic i odpowiednio zmodyfikowac istniejace wzorce. Co jest najbardziej uciazliwe, uzytkownik musi sam rozmiescic w tekscie instrukcje nakazujace systemowi odczytanie aktualnych wartosci wizualizowanych danych i zobrazowanie zmienionej sytuacji. Zaawansowane sa prace nad zautomatyzowaniem przygotowania projekcji. Zamiarem autorow systemu jest stworzenie preprocesora, ktory po przeprowadzeniu analizy tekstu programu i sformalizowanej specyfikacji wymagan dotyczacych tego, jakie dane i w jakiej formie maja byc przedstawiane, sam rozmieszczalby w tekscie odwolania do procedur systemowych i konfigurowal pomocnicze struktury danych. Oczywiscie, w przypadku koniecznosci przygotowania projekcji odbiegajacych od szablonu, uzytkownik musialby sam wprowadzic niezbedne uzupelnienia.

PRZYKLADY WYKORZYSTANIA SYSTEMU

Przedstawimy teraz dwa przyklady mozliwosci zastosowania systemu WinSanal do wizualizacji programow; wybrane programy sa proste, sadzimy jednak, ze rowniez one po wyposazeniu ich w dodatkowe funkcje moga byc pomocne przy organizowaniu interesujacych eksperymentow.

Przyklad pierwszy, pokazany na rys. 2, to wizualizacja dzialania kolejkowego modelu prostego systemu komputerowego zawierajacego trzy stanowiska obslugi: procesor P, stacje dyskow D i drukarke DR. Zadania dla systemu sa generowane przez zrodlo o pewnej charakterystyce. Stanowiska obslugi reprezentowane sa przez grele eliptyczne, polaczenia — przez grele liniowe, zadania — przez grele prostokatne, wreszcie kolejki zadan oczekujacych na obsluge — przez zespoly — tablice greli prostokatnych. System wizualizacji pozwala sledzic, jak prostokaciki reprezentujace zadania przesuwaja sie do kolejki oczekiwania na dostep do procesora, z kolejki — do stanowiska obslugi, po czym opuszczaja system lub trafiaja do nastepnej kolejki, sa obslugiwane, itd. Uzytkownik w czasie projekcji moze modyfikowac parametry zrodla zadan i stanowisk obslugi, badac tozsamosc procesow, ktore sa aktualnie obslugiwane i tych, ktore czekaja w kolejkach, itd. Moze tez np. zmieniac polozenie zadan w kolejce lub przesuwac je miedzy kolejkami.

Na rys. 2a widac okienko inspekcyjne otwarte po wskazaniu przez uzytkownika zadania nr 1 czekajacego w kolejce do drukarki. Celem interwencji bylo przeniesienie zadania nr 1 do kolejki procesora; osiagnieto to zmieniajac wartosc numeru kolejki z 3 (drukarka) na 1 (procesor). Rysunek 2b pokazuje sytuacje w chwile po wznowieniu pracy programu: widac prostokacik odpowiadajacy zadaniu nr 1 wedrujacy na koniec kolejki procesora. Zauwazmy, ze interwencja nastapila w momencie, gdy prostokacik zadania 5 zaczal sie przesuwac w strone kolejki drukarki; na rys. 2b jest juz bliski swego celu.

Przyklad drugi jest zwiazany z wizualizacja programu symulujacego procesy rozwoju w systemach ewolucyjnych. Obszerny opis problemu mozna znalezc w [9]. W skrocie, rozwoj struktur plaskich o specyficznej konstrukcji (dla ktorych analogie mozna wskazac wsrod organizmow zywych lub ich czesci) mozna przedstawic jako ciag operacji punktowych na elementach wchodzacych w sklad struktury. Wyroznia sie szesc rodzajow elementarnych operacji punktowych; podajemy je stosujac przyjeta w [9] notacje. Sa to:

• stagnacja (a –> a): element a w wyniku operacji nie zmienia sie

• transformacja (a –> b): element a zmienia sie w element b

• bifurkacja (rozszczepienie) (a –> bc): element a zastepowany jest dwoma innymi, polaczonymi ze soba elementami b i c

• generacja liniowa (a –> ba): specyficzne rozszczepienie: drugi z powstajacych elementow jest taki sam, jak element, ktory ulegl podzialowi

• bifurkacja ze zmiana kierunku (a –> b(c)): rozszczepienie powodujace powstanie odgalezienia struktury i umieszczenie w nim elementu c

• generacja spiralna (a –> b(a)): odmiana generacji liniowej; powielony element dolaczany jest w zmienionym kierunku, a nie na przedluzeniu dotychczasowego

Program symulujacy przebieg procesu ewolucyjnego tworzy drzewiasta, rozbudowujaca sie strukture danych. W zaproponowanej wizualizacji kazdy wezel odpowiadajacy elementowi struktury jest reprezentowany przez grel eliptyczny, a polaczenia — przez grele liniowe. Wizualizacja moze byc realizowana w dwoch wariantach: jako wizualizacja czastkowa, pokazujaca operacje punktowe rozpatrywane kolejno, wezel po wezle, lub jako wizualizacja etapowa, gdzie na raz pokazywany jest efekt wszystkich operacji punktowych, jakie mialy miejsce w danym kroku ewolucji.

W trakcie projekcji uzytkownik ma mozliwosc ingerencji w przebieg wykonania programu i modyfikacji zmiennych. Rysunek 3 przedstawia charakterystyczne elementy pokazu zrealizowanego dla modelu opartego o zbior elementarnych operacji punktowych [9, s. 69]:

d –> ed f –> s(a) a –> mb b –> mc c –> md

e –> sf s –> s m –> sg g –> s(h) h –> sh (1)

i slowa poczatkowego a. Rysunek 3a przedstawia sytuacje, gdy uzytkownik wstrzymal wykonanie programu po trzecim etapie rozwoju (struktura zawiera wtedy symbole ss(h)sgmd), bada dane dla wezla odpowiadajacego symbolowi h (kod 9) i rozwaza zmiane h na a (kod 4). Rysunek 3b obrazuje probe zmiany na tym samym etapie symbolu g (kod 8) na s (kod 3). Na rys. 3c i 3d widac obraz struktury, jaka sie uformowala po 13 etapach rozwoju — odpowiednio — bez zmian wymuszonych z zewnatrz i z uwzglednieniem omowionych defektow wprowadzonych po etapie trzecim. Jako ciekawostke podajemy, ze porownujac rys. 3c z [9, rys. 3-5, s.70] zauwazylismy nieznaczna niekonsekwencje w recznie wykonanym podrecznikowym obrazie tej samej struktury w czwartej od szczytu galezi struktury (inny niz wszedzie indziej kierunek pierwszego odgalezienia). Szanse wykrycia tej usterki, skadinad malo istotnej, bez odwolania sie do automatycznej wizualizacji sa niewielkie.

Na rys. 4 przedstawione sa fragmenty programu symulujacego rozwoj struktury z uzupelnieniami wykonanymi dla potrzeb wizualizacji. W programie pozostawiono operacje dotyczace greli reprezentujacych wezly struktury, usuwajac operacje na grelach reprezentujacych polaczenia. W wyjsciowym programie z przedstawionych funkcji wystepowala funkcja handleNode, odpowiadajaca za wykonanie operacji punktowej. Pozostale dwie, CreateGraphStr i ElModifPlay, tworza siostrzana strukture drzewiasta, w ktorej zgromadzone sa dane elementow konstrukcji graficznej (wspolrzedne wezlow, kierunki polaczen), a ponadto ustawiaja systemowe sciezki przeplywu danych i nakazuja systemowi przedstawienie aktualnego wygladu struktury.

Jak mozna posrednio wywnioskowac z rys. 4, w obecnym stanie systemu naklad pracy niezbedny do przygotowania wizualizacji, mierzony iloscia dodatkowego kodu programu, jest duzy. Moze on ulec zmniejszeniu po zaimplementowaniu zmian sygnalizowanych w sekcji poswieconej przygotowaniu wizualizacji. Duza poprawe moze dac rowniez opracowanie wyspecjalizowanych srodkow do prezentacji kolejnych rodzajow struktur danych, w omawianym przykladzie — struktur grafowych.

// ustawienie wspolrzednych elementow graficznych, 
// i przedstawienie zmian w strukturze 
void ElModifPlay(struct GraphStructEl *pGS, float x, float y) 
{ 
  if (! pGS) return; 
  if (Find(pGS->primaryElP->mainSuccP)) 
    ElModifPlay(Find(pGS->primaryElP->mainSuccP),x,y); 
  if (Find(pGS->primaryElP->auxSuccP)) 
    ElModifPlay(Find(pGS->primaryElP->auxSuccP),x,y); 
  pGS->xPos += x; pGS->yPos += y; 
  Play( &(pGS->xPos) ); Play( &(pGS->yPos) ); // ——> WinSanal 
  Play( &(pGS->primaryElP->symb) ); // ——> WinSanal 
} 

// uzupelnienie pomocniczej struktury ze wspolrzednymi elementow 
// graficznych; uzupelnienie sciezek; wyswietlenie 
void CreateGraphStr(struct EvolStructEl* oldStr, 
            struct EvolStructEl* newStr, int type) 
{ struct GraphStructEl *pGS, *pNewGS, *pAux; 

  pGS = Find(oldStr); 
  if (! pGS) return; 
  pNewGS = new struct GraphStructEl; 

  int f = oldStr->phase; 

  switch(type) 
  { // ... 
    case 5: // bifurkacja ze zmiana kierunku 
      pNewGS->xPos = pGS->xPos; pNewGS->yPos = pGS->yPos; 
      pNewGS->mainDirection = pGS->mainDirection + f*mainAngle; 
      pAux = pGS->pNext; 
      pGS->pNext = pNewGS; 
      pNewGS->pNext = pAux; pNewGS->primaryElP = newStr; 
      PSElem.pVarAddr = &(pNewGS->xPos); 
      PSElem.sVarId = "El_X"; 
      PSElem.iMainAspectCode = AC_XCOORD; 
      GSElem.iXCoord = (int)pGS->xPos; 
      GSElem.iYCoord = (int)pGS->yPos; 
      CreatePath(&PSElem, pGrel, pShadow); // ——> WinSanal 
      PSSym.pVarAddr = &(pNewGS->primaryElP->symb); 
      CreatePathToGrel(&PSSym, pGrel, pShadow); // ——> WinSanal 
      PSElem.pVarAddr = &(pNewGS->yPos); 
      PSElem.sVarId = "El_Y"; 
      PSElem.iMainAspectCode = AC_YCOORD; 
      CreatePathToGrel(&PSElem, pGrel, pShadow); // ——> WinSanal 
      Play(&(pGS->primaryElP->symb)); // ——> WinSanal 
      ElModifPlay(pNewGS, mainStep*cos((pGS->mainDirection + f*mainAngle)*PI/180), 
      mainStep*sin((pGS->mainDirection + f*mainAngle)*PI/180)); 
      WaitForFinish(); // ——> WinSanal 
      break; 
      // ... 
  } 
} 

// przeksztalcanie wezla i fragmentu struktury z nim polaczonego 
void handleNode( EvolStructEl * elP ) 
{ int cSymb, nType; 
  EvolStructEl * newElP; 
  if (! elP) return; 
  cSymb = elP->symb; nType = symbDTable [cSymb].ruleType; 
  handleNode( elP->mainSuccP ); handleNode( elP->auxSuccP ); 

  switch( nType ) 
  { // ... 
    case 5 : // bifurkacja ze zmiana kierunku 
      elP->symb = symbDTable [cSymb].succ1; 
      newElP = new EvolStructEl; 
      newElP->symb = symbDTable [cSymb].succ2; 
      newElP->phase = 1; 
      newElP->mainSuccP = NULL; newElP->auxSuccP = NULL; 
      elP->auxSuccP = newElP; 
      SetPhase(elP); 
      CreateGraphStr(elP, newElP, nType); 
      break; 
      // ... 
  } 
} 

UWAGI KONCOWE

W systemie WinSanal udalo sie polaczyc szereg rozwiazan istotnych dla uzytkownika systemu — aktywnego obserwatora prezentacji: dosc obszerny zestaw srodkow graficznych, mechanizmy animacji zmian, mozliwosc interakcyjnego modyfikowania danych. Konieczne sa dalsze prace, ktorych efektem bedzie zmniejszenie pracochlonnosci przygotowywania wizualizacji w systemie.

BIBLIOGRAFIA

[1] K.W.Brodlie i in. (red.), "Scientific Visualization. Techniques and Applications", Springer-Verlag, Heidelberg 1992.

[2] M.H.Brown, R.Sedgewick, "A System for Algorithm Animation", Computer Graphics; SIGGRAPH’84 Conference Proceedings, Minneapolis, Minn. 18(3), July 23-27 1984, pp. 177-186.

[3] M.H.Brown, "Exploring Algorithms Using Balsa-II", Computer, Vol. 21, May 1988, pp. 14-36.

[4] J.Francik, P.Szmal, "Wizualizacja synchroniczna algorytmow — realizacja w systemie SANAL". Zeszyty Naukowe Politechniki Slaskiej, seria Informatyka z.27, Gliwice, 1994.

[5] J.Francik, P.Szmal, "Wizualizacja algorytmow z wykorzystaniem systemu SANAL", X Konferencja "Informatyka w szkole", Materialy konferencyjne, Torun, wrzesien 1994.

[6] M.Nowak, "Mechanizmy prezentowania danych w postaci symbolicznej i interakcyjnego wprowadzania danych dla systemu animacji algorytmow SANAL", Praca dyplomowa magisterska, Politechnika Slaska, Instytut Informatyki, Gliwice 1996.

[7] J.Stasko, "A Framework and System for Algorithm Animation", Computer, September 1990.

[8] J.Stasko, "Animating Algorithms with XTANGO", SIGACT News, Vol.23, Iss.2, Spring 1992, pp. 67-71.

[9] S.Wegrzyn, J.-C.Gille, P.Vidal,

"Developmental Systems. At the Crossroads of System Theory, Computer Science, and Genetic Engineering", Springer-Verlag, New York 1990.

[Jaroslaw Francik: strona domowa]

Copyright © 1997 by Jaroslaw Francik.
Revised: April 15, 1997

This site is a part of personal pages of Jaroslaw Francik. Go back to his  home page
Copyright © 2000 by Jaroslaw Francik
Last modified: 21/02/00