View page as slide show

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)

  • 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)

  • 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.

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

  • 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 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 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:

  • 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 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

pl/miw/2010/miw10_hgviz/prezentacja.txt · ostatnio zmienione: 2019/06/27 15:50 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0