MIW 2010 hgviz
Znalezione metody wizualizacji hipergrafów
Znalezione metody wizualizacji hipergrafów
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)
[1 -> 2, 1 -> 3, 1 -> 4, 2 -> 3, 2 -> 4, 3 -> 4]
[w(1,[2,3,4]), w(2,[3,4]), w(3,[4]), w(4,[])]
| 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)
krawedz(1,2).
krawedz(1,3).
krawedz(1,4).
krawedz(2,3).
krawedz(2,4).
krawedz(3,4).
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.
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).
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.
Zaproponowane metody reprezentacji HG w prologu
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
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
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 cgen.pl
Główny predykat tego plik (cGen/3) wymaga trzech argumentów:
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 macierz.cpp
Generowanie tabeli do Latexu
Po skompilowaniu tego pliku i uruchomieniu pliku wynikowego otrzymujemy gotowy do kompilacji plik macierz.tex
Aby uprościć cały proces przygotowałem skrypt unixowy skrypt.sh
Po jego uruchomieniu wystarczy podać nazwy plików wynikowych i cała reszta robi się automatycznie.
Efektem działania skryptu jest plik 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 dotgen_h.pl
Główny predykat tego plik (dotGenH/2) wymaga trzech argumentów:
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 graf.dot
Wizualizacja w GraphViz
Po jego skompilowaniu otrzymujemy taki oto rysunek:
Również tutaj przygotowałem dla uproszczenia procesu skrypt unixowy skrypt2.sh
Koniec
Przygotował: Curzytek Przemysław