~~SLIDESHOW~~ ====== MIW 2010 hgviz ====== **Zrealizował:** [[|Przemysław Curzytek]] **(4RI)** [[pl:dydaktyka:miw:2010:hgviz:start|Powrót do głównej strony projektu...]] ===== Znalezione metody wizualizacji hipergrafów ===== {{:pl:dydaktyka:miw:2010:hgviz:5.gif?350x350 |}} {{ :pl:dydaktyka:miw:2010:hgviz:2.gif?380x350 |}} ===== Znalezione metody wizualizacji hipergrafów ===== {{:pl:dydaktyka:miw:2010:hgviz:3.gif?400x350 |}} {{ :pl:dydaktyka:miw:2010:hgviz:1.gif?350x350 |}} ===== Metody reprezentacji grafów w Prologu ===== * reprezentacja termowa * zbiór (lista) krawędzi \\ np. [ a<->b, c<->d, ... ] lub [ kr(a,b,etykieta1) kr(c,d,etykieta2), ... ] * listy sąsiedztwa \\ np. [ w(Wierzchołek, ListaSąsiadów) ... ] * macierz sąsiedztwa * reprezentacja klauzulowa * zbiór krawędzi \\ np. zbiór faktów typu: krawedz(a,b). * listy sąsiedztwa \\ np. zbiór faktów typu: krawedz(a, [ b, c ]). ===== Przykładowy graf i jego reprezentacje (termowe) ===== {{ :pl:dydaktyka:miw:2010:hgviz:przykladowy2.gif|}} * zbiór (lista) krawędzi [1 -> 2, 1 -> 3, 1 -> 4, 2 -> 3, 2 -> 4, 3 -> 4] * listy sąsiedztwa [w(1,[2,3,4]), w(2,[3,4]), w(3,[4]), w(4,[])] * macierz sąsiedztwa | ^ 1 ^ 2 ^ 3 ^ 4 ^ ^ 1 | 0 | 1 | 1 | 1 | ^ 2 | 0 | 0 | 1 | 1 | ^ 3 | 0 | 0 | 0 | 1 | ^ 4 | 0 | 0 | 0 | 0 | ===== Przykładowy graf i jego reprezentacje (klauzulowe) ===== {{ :pl:dydaktyka:miw:2010:hgviz:przykladowy2.gif|}} * zbiór krawędzi krawedz(1,2). krawedz(1,3). krawedz(1,4). krawedz(2,3). krawedz(2,4). krawedz(3,4). * listy sąsiedztwa krawedz(1, [2,3,4]). krawedz(2, [3,4]). krawedz(3, [4]). ===== Możliwości wizualizacji w GraphViz (dot)===== **dot** - umożliwia hierarchiczną (warstwową) wizualizację skierowanych grafów; dostarcza użytkownikowi dość sporą ilość atrybutów możliwych do ustawienia (m.in. kolor i wzór połączeń między węzłami, kształty węzłów); pozwala tworzyć podgrupy z krawędzi i węzłów. \\ {{ :pl:dydaktyka:miw:2010:hgviz:dot.gif?300x300 |}} \\ ===== Możliwości wizualizacji w GraphViz (neato)===== **neato** - umożliwia wizualizację grafów nieskierowanych; można umiejscawiać węzły w dowolnym miejscu (parametr //pos//).\\ {{ :pl:dydaktyka:miw:2010:hgviz:neato.gif?500x300 |}} \\ ===== Możliwości wizualizacji w GraphViz (fdp)===== **fdp** - umożliwia wizualizację grafów nieskierowanych wraz z tworzeniem podgrup z krawędzi i węzłów. \\ {{ :pl:dydaktyka:miw:2010:hgviz:fdp.gif?500x300 |}} ===== Zaproponowane metody reprezentacji HG w prologu ===== * nazwa(numer hiperkrawędzi,lista wierzchołków) Listy wierzchołków połączonych przez dane hiperkrawędzie. \\ Przykładowo: \\ h_przykladowy([v8]). h_przykladowy(e1,[v1,v7]). h_przykladowy(e2,[v1,v2,v6]). h_przykladowy(e3,[v5,v6]). h_przykladowy(e4,[v3,v4,v5]). ===== Zaproponowane metody reprezentacji HG w prologu ===== * zbiór połączeń Każde połączenie wiąże ze sobą węzeł i hiperkrawędź. \\ Przykładowo: \\ h_przykladowy(v8,[]). h_przykladowy(v1,e1). h_przykladowy(v7,e1). h_przykladowy(v1,e2). h_przykladowy(v2,e2). h_przykladowy(v6,e2). h_przykladowy(v5,e3). h_przykladowy(v6,e3). h_przykladowy(v3,e4). h_przykladowy(v4,e4). h_przykladowy(v5,e4). ===== Zaproponowane metody reprezentacji HG w prologu ===== * macierz sąsiedztwa W przeciwieństwie do zwykłych grafów, gdzie zarówno wiersze jak i kolumny reprezentowały węzły, w przypadku hipergrafów wiersze macierzy oznaczać będą krawędzie. \\ Przykładowo: \\ | ^ v1 ^ v2 ^ v3 ^ v4 ^ v5 ^ v6 ^ v7 ^ v8 ^ ^ e1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | ^ e2 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | ^ e3 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | ^ e4 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | ===== Generowanie tabeli do Latexu ===== Ze względu na trudności z generowaniem poprawnego pliku **//.tex//** bezpośrednio na podstawie stworzonej w Prologu bazy wiedzy na temat hipergrafu, generowałem w pierwszej kolejności plik **//.cpp//**, który po skompilowaniu tworzył interesujący nas od początku plik z macierzą koincydencji w Latexu. Plik [[pl:dydaktyka:miw:2010:hgviz:cgen_pl|cgen.pl]] Główny predykat tego plik (**//cGen/3//**) wymaga trzech argumentów: * nazwy pliku c++ * nazwy predykatu przechowującego fakty o hipergrafie * nazwy docelowego pliku LaTeX. ===== Generowanie tabeli do Latexu ===== Jego wywołanie dla przykładowego predykatu: hiperg(v4,[]). hiperg(v1,e1). hiperg(v3,e1). hiperg(v1,e2). hiperg(v2,e2). hiperg(v1,e3). hiperg(v5,e3). powoduje wygenerowanie pliku [[pl:dydaktyka:miw:2010:hgviz:cpp|macierz.cpp]] ===== Generowanie tabeli do Latexu ===== Po skompilowaniu tego pliku i uruchomieniu pliku wynikowego otrzymujemy gotowy do kompilacji plik [[pl:dydaktyka:miw:2010:hgviz:tex|macierz.tex]] Aby uprościć cały proces przygotowałem skrypt unixowy [[pl:dydaktyka:miw:2010:hgviz:sh|skrypt.sh]] Po jego uruchomieniu wystarczy podać nazwy plików wynikowych i cała reszta robi się automatycznie. Efektem działania skryptu jest plik {{:pl:miw:2010:miw10_hgviz:macierz.pdf|}} z macierzą incydencji naszego hipergrafu. ===== Wizualizacja w GraphViz ===== Zrealizowana przeze mnie graficzna forma reprezentacji odpowiada drugiej z podanych w przykładach. Stworzony predykat generuje plik **//.dot//**. Plik [[pl:dydaktyka:miw:2010:hgviz:dotgen_h_pl|dotgen_h.pl]] Główny predykat tego plik (dotGenH/2) wymaga trzech argumentów: * nazwy pliku dot * nazwy predykatu przechowującego fakty o hipergrafie ===== Wizualizacja w GraphViz ===== Jego wywołanie dla przykładu: ht(v8,[]). ht(v1,e1). ht(v7,e1). ht(v1,e2). ht(v2,e2). ht(v6,e2). ht(v5,e3). ht(v6,e3). ht(v3,e4). ht(v4,e4). ht(v5,e4). powoduje wygenerowanie pliku [[pl:dydaktyka:miw:2010:hgviz:dot|graf.dot]] ===== Wizualizacja w GraphViz ===== Po jego skompilowaniu otrzymujemy taki oto rysunek: {{ :pl:miw:2010:miw10_hgviz:graf.png?280x280| }} Również tutaj przygotowałem dla uproszczenia procesu skrypt unixowy [[pl:dydaktyka:miw:2010:hgviz:sh2|skrypt2.sh]] ===== Koniec ===== Przygotował: Curzytek Przemysław