Wizualizacja grafów w języku SVG (na przykładzie topologii sieci komputerowych)
1. Wprowadzenie do języka SVG
1.1. Język opisu grafiki wektorowej Scalable Vector Graphics
Język SVG (Scalable Vector Graphics) stanowi format opisu informacji wizualnej wykorzystujący składnię XML. Jego pierwotnym, zasadniczym przeznaczeniem jest zwarta, a zarazem czytelna dla człowieka reprezentacja tekstowa statycznej grafiki wektorowej. Obecnie, w składni SVG można opisać grafikę łączącą elementy wektorowe i tekstowe z rastrowymi, zaawansowane animacje wektorowe, oraz prezentacje wchodzące w interakcję z użytkownikiem, wykorzystujące proste elementy skryptowe. Specyfikacja języka SVG w wersji 1.1 (z początku 2003r.) ma status rekomendacji konsorcjum W3C, a obecnie dobiegają końca prace nad specyfikacją języka w wersji 1.2.
SVG jest jedynym formatem grafiki wektorowej ogólnego przeznaczenia promowanym przez konsorcjum W3C, m.in. ze względu na otwartość standardu oraz szeroki zakres zastosowań. SVG z jednej strony wykorzystywane jest z powodzeniem do wizualizacji danych o charakterze specjalistycznym (m.in. przy opracowywaniu map wektorowych na podstawie danych z systemów informacji przestrzennej, w profesjonalnej grafice wektorowej i geometrii wykreślnej), z drugiej natomiast – zyskuje popularność w aplikacjach ogólnego przeznaczenia, jako narzędzie do wygodnego opracowywania wykresów, diagramów, schematów blokowych i schematów przepływu. Darmowe pluginy do przeglądarek internetowych pozwalające na wizualizacje SVG (Adobe SVG Viewer dla Internet Explorer, natywny plugin SVG przeglądarki Mozilla) są obecnie na zaawansowanym etapie rozwoju, oferując funkcjonalność coraz bliższą komercyjnemu formatowi Macromedia Shockwave Flash (SWF).
Istnieje wreszcie poważna gałąź zastosowań, w których format SVG, dzięki swojej prostej, a zarazem łatwo rozszerzalnej, modularnej postaci stanowi najbardziej naturalną formę wizualizacji danych. SVG nadaje się doskonale do prezentacji wszelkich struktur grafowych, a w szczególności grafów obrazujących połączenia i przepływy pomiędzy węzłami. Przykładem takiego właśnie zastosowania SVG jest wizualizacja topologii sieci komputerowych, przedstawiona w rozdziale 2.
1.2. Struktura prostego dokumentu SVG
Podstawowe elementy języka SVG pozwalają opisać w składni XML dwuwymiarową grafikę złożoną z trzech rodzajów obiektów: elementów wektorowych (złożonych z odcinków prostych oraz krzywych kawałkami gładkich), odnośników do grafiki rastrowej oraz tekstu sformatowanego, wraz z opcjonalnymi definicjami symboli i kroju czcionek. Elementy graficzne budowane są poprzez tworzenie grup z mniejszych „cegiełek” (fragmentów), uzyskiwanych w wyniku:
- wykonania jednej z kilkunastu podstawowych operacji rysowania zdefiniowanych w SVG,
- osadzenia obiektu opisanego przez podgrupę elementów SVG, lub odnośnik do zewnętrznego dokumentu albo nazwanej grupy elementów,
- wstawienia elementu osadzonego przez użytkownika poza składnią SVG (np. w języku rozszerzeń sXBL w składni XML).
Przyjmuje się, że domyślnie elementy rysowane są w kolejności występowania na obszarze roboczym o przezroczystym tle. Każdy element grupy (jak również cała grupa) może być poddany transformacji poprzez przesunięcie, obrót, przycięcie według ścieżki, maskę kanału alfa czy zdefiniowany filtr. Dodatkowo, każda grupa może mieć przypisany opis (<desc>) oraz tytuł (<title>), ułatwiający prezentację obrazu na niestandardowych terminalach.
Dokument SVG zdefiniowany jest w obrębie głównego elementu ograniczonego przez znacznik <svg>. Definiuje on przynależność dokumentu SVG do odpowiedniej przestrzeni nazw, a także pozwala określić abstrakcyjny układ współrzędnych oderwany od rzeczywistych rozmiarów obszaru rysowania (poprzez atrybut viewBox, np.:
<svg width="10cm" height="3cm" viewBox="0 0 30 100" version="1.1"
xmlns="http://www.w3.org/2000/svg"
xmlns:xlink="http://www.w3.org/1999/xlink">
Zawartość elementu <svg> może być interpretowana jak zawartość dowolnej innej grupy, przy czym podelement <defs> pełni rolę specjalną, pozwalając na definiowanie wirtualnych drzew SVG, tj. elementów nazwanych nie poddawanych bezpośredniej wizualizacji w trakcie rysowania elementu <svg>, ale mogących wchodzić w skład innych grup elementów na skutek jawnego odwołania przez odnośnik.
Statyczne elementy grafiki tworzą hierarchiczną strukturę opisanej wcześniej postaci, przy czym zarówno elementy kontenerowe (znaczniki definiujące przez swoją zawartość grupę elementów), jak i elementy proste (znaczniki bez zawartości) mają zbliżony zestaw podstawowych atrybutów. Opisują one parametry rysowania elementu (np. fill – kolor wypełnienia, stroke-width – grubość linii brzegowej), jego umiejscowienie w bieżącym obszarze rysowania
(x,y – współrzędne lewego górnego rogu, width, height – szerokość i wysokość elementu), relacje względem innych elementów i przezroczystość w kanale alfa (opacity), oraz transformacje do wykonania po narysowaniu elementu (transform). Prosty przykład grafiki SVG złożonej z prostokąta (<rect>) o żółtym wypełnieniu oraz grupy (<g>) dwóch półprzezroczystych szarych prostokątów przedstawiono na rys. 1.
<?xml version="1.0" standalone="no"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN"
"http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd">
<svg width="10cm" height="3cm" viewBox="0 0 30 100"
version="1.1"
xmlns="http://www.w3.org/2000/svg"
xmlns:xlink="http://www.w3.org/1999/xlink">
<desc>Przykładowy rysunek wraz z obramowaniem i tłem</desc>
<rect x="0" y="5" width="30" height="80"
fill="lightyellow" stroke="black" />
<g stroke-width="0.4" transform="translate(20,15)">
<desc>Para półprzezroczystych prostokątów</desc>
<rect x="0" y="0" width="10" height="60"
fill="gray" stroke="black" opacity="0.6"
transform="translate(-10,0) rotate(-10,5,30)"/>
<rect x="0" y="0" width="10" height="60"
fill="gray" stroke="black" opacity="0.6"
transform="translate(-10,0) rotate(10,5,30)"/>
</g>
</svg>
Rys. 1. Prosty przykład hierarchicznej struktury grafiki SVG
1.3. Wirtualne drzewa elementów
SVG pozwala na zdefiniowanie grupy elementów w obrębie elementu <defs>, która pełni wówczas rolę szablonu – nie jest włączana bezpośrednio do dokumentu w miejscu wystąpienia, ale posiada unikalny atrybut identyfikujący id i może zostać przywołana z dowolnego miejsca tego samego lub innego dokumentu za pomocą znacznika <use>. Jedynie elementy z przypisanym identyfikatorem mogą być w wygodny sposób animowane.
Funkcjonalność SVG 1.2 jest rozszerzona o wsparcie dla języka sXBL, pozwalającego na rozszerzenie domyślnego języka znaczników za pomocą gotowych komponentów. Struktury sXBL definiowane są w obrębie SVG jako wirtualne drzewa elementów, o których implementacji SVG nic nie zakłada. Przykładowo, można w ten sposób zdefiniować i wykorzystywać komponenty do rysowania elementów nie wspieranych bezpośrednio przez sXBL, takich jak diagramy blokowe czy diagramy przepływów.
1.4. Dynamiczne aspekty SVG
Język SVG pozwala na tworzenie grafiki z predefiniowaną animacją (poprzez określenie przejść i zmian w czasie dla poszczególnych elementów), a także z elementami wchodzącymi w interakcję z użytkownikiem. Elementy dokumentów SVG mogą być adresowane poprzez mechanizmy struktury Document Object Model (DOM), zdefiniowanej w składni IDL dla dokumentów SVG. Korzystanie ze wszystkich elementów oraz ich atrybutów i właściwości poprzez DOM jest możliwe z poziomu wydzielonego języka skryptowego. Obiektom graficznym SVG może towarzyszyć kod oczekujący na określone zdarzenia ze strony użytkownika, np. na skutek akcji myszką (onmouseover lub onclick).
1.5. Postulat rozdzielenia prezentacji od treści
Konsorcjum W3C wydało szereg zaleceń dotyczących metod rozdzielania prezentacji od treści w językach składni XML. Zalecenie w przypadku SVG nie odbiega za bardzo od ogólnie przyjętej tendencji stosowania arkuszy styli CSS. W przypadku SVG wykorzystywane mechanizmy CSS2 pozwalają na ustalenie schematów barw i intensywności linii oraz wypełnień dla poszczególnych elementów dokumentu. Zalecane jest opracowywanie kilku sekcji arkusza stylu, przeznaczonych dla użytkowników korzystających z różnych urządzeń (np. komputerów przenośnych).
<?xml-stylesheet href="computer.css" type="text/css"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20000802//EN"
"http://www.w3.org/2000/svg-20000802.dtd">
<svg width="16cm" height="12cm" viewBox="0 0 600 450">
<defs>
<radialGradient id="screenGrad" cx="0" cy="0" r="1">
<stop class="s0" offset="0%" />
<stop class="s100" offset="100%"/>
</radialGradient>
<linearGradient id="discGrad">
<stop class="s0" offset="0%"/>
<stop class="s100" offset="100%"/>
</linearGradient>
<symbol id="terminal">
<desc>Komputer klasy PC</desc>
<g id="monitorStand" class="stand" transform="translate(40 121)">
<title>Podstawka pod monitor</title>
<path d="m0,0 C 0 0 10 10 40 12 C 70 10 80 0 80 0"/>
<path d="m0,20 L 10 10 S 40 12 70 10 L 80 20z"/>
</g>
<g id="monitor" transform="translate(0 0)">
<title>Monitor</title>
<rect class="outline" width="160" height="120"/>
<rect class="screen" width="138" height="95" x="11" y="12"
fill="url(#screenGrad)"/>
</g>
<g id="processor" class="computer" transform="translate(0 142)">
<title>Komputer</title>
<desc>Szara obudowa typu desktop</desc>
<rect class="outline" width="160" height="60"/>
<g id="discDrive" transform="translate(70 8)">
<title>Napęd dyskietek</title>
<rect class="disc" width="58" height="3" x="12" y="8"
fill="url(#discGrad)"/>
<rect class="light" width="8" height="2" x="12" y="15"/>
</g>
<circle cx="135" cy="40" r="5" class="button"/>
</g>
</symbol>
</defs>
<g id="Computer" transform="translate(180 65)">
<title>Computer</title>
<use class="terminal" xlink:href="#terminal"/>
</g>
</svg>
@media screen {
#screenGrad .s100 {stop-color: #AAF}
#screenGrad .s0 {stop-color: white}
#discGrad .s100 {stop-color: beige}
#discGrad .s0 {stop-color: black}
.stand {fill: #DDB}
.computer {fill: #DDD}
.light {fill: lightgreen}
.button {fill: gray}
.terminal {
fill: beige;
stroke: black;
stroke-width: 0.6
}
}
Rys. 2. Rozdzielenie prezentacji od treści w SVG (powyżej: kod SVG computer.svg, poniżej: kod CSS computer.css oraz efekt wizualizacji). Opracowano na podstawie przykładów podanych w [4]
Arkusze stylu dla SVG nie obejmują możliwości zmiany pozycji czy rozmiaru rysunku poprzez CSS. Prosty przykład wykorzystania arkusza stylu do zdefiniowania wyglądu stacji komputerowej przedstawiono na rys. 2.
1.6. Stosowanie elementów SVG jako szablonów
Hierarchiczna struktura elementów SVG, połączona z możliwością definiowania drzew wirtualnych, daje możliwość wielokrotnego wykorzystania jednego elementu kodu do prezentacji wielu fragmentów rysunku. Co więcej, dzięki możliwości stosowania transformacji przestrzennych i zmiany wyglądu poprzez CSS, fragmenty te mogą różnić się nawet znacznie wyglądem, rys. 3.
<?xml-stylesheet href="star.css" type="text/css"?>
<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 20000802//EN"
"http://www.w3.org/2000/svg-20000802.dtd">
<svg width="16cm" height="12cm" viewBox="0 0 1000 1000">
<defs>
<symbol id="star">
<g transform="translate(500 500)">
<use xlink:href="computer.svg#terminal"
transform="scale(0.4) translate(-72,-90)"/>
<line x1="50" x2="200" y1="0" y2="0" class="netcon"
transform="rotate(0)"/>
<line x1="50" x2="140" y1="0" y2="0" class="netcon"
transform="rotate(72)"/>
<line x1="50" x2="230" y1="0" y2="0" class="netcon"
transform="rotate(144)"/>
<line x1="50" x2="220" y1="0" y2="0" class="netcon"
transform="rotate(216)"/>
<line x1="50" x2="150" y1="0" y2="0" class="netcon"
transform="rotate(288)"/>
</g>
</symbol>
</defs>
<g id="star">
<title>Several computers in a spidered star network</title>
<use class="server" xlink:href="computer.svg#terminal"
transform="translate(715, 427) scale(0.5)"/>
<use class="node" xlink:href="#star"/>
<use class="node" xlink:href="#star" transform="translate(490, 165)"/>
<use class="node" xlink:href="#star" transform="translate(470, -225)"/>
</g>
</svg>
@media screen {
.node {
fill: beige;
stroke: black;
stroke-width: 0.6
}
.server {
fill: brown;
stroke: black;
stroke-width: 5.0
}
.netcon {
stroke: black;
stroke-width: 2.0;
}
}
Rys 3. Stosowanie szablonów w SVG (powyżej: kod SVG star.svg, poniżej: kod CSS star.css oraz efekt wizualizacji)
2. Wektorowe mapy topologii sieci komputerowych
Język SVG zyskuje coraz szerszą popularność jako format opisu map wektorowych, pozyskiwanych najczęściej z systemów SIP lub CAD, a przeznaczonych zasadniczo do wizualizacji wektorowej, z opcjonalnym zachowaniem pewnych ograniczonych możliwości przetwarzania zapisanych danych. W literaturze (np. [3]) najwięcej uwagi poświęca się zagadnieniom wizualizacji map na podstawie wielowarstwowej informacji wektorowej, związanym z koniecznością doboru odpowiedniego poziomu szczegółowości grafiki SVG w zależności od skali i rozmiaru prezentowanego wycinka informacji.
Specyfika zagadnienia wizualizacji topologii sieci komputerowych wymaga jednak nieco innego podejścia. Problem doboru wizualizowanych elementów informacji zazwyczaj nie występuje, ponieważ osoba zainteresowana analizą mapy jest w stanie dokładnie sprecyzować, które elementy topologii sieci ją interesują. W przypadku map interaktywnych wybór właściwej informacji odbywa się więc częściej drogą formułowania zapytania (np. o elementy szkieletowe sieci o dużej przepustowości) i wymagana jest możliwie efektywna wizualizacja wybranych w ten sposób danych.
W tym kontekście całkowicie naturalne wydaje się rozpatrywanie topologii sieci komputerowej jako pewnego abstrakcyjnego, zdefiniowanego przez użytkownika, widoku na sieć komputerową, i postawienie zagadnienia wizualizacji mapy jako przedstawienia całej informacji występującej w tak zdefiniowanym widoku w formie grafiki wektorowej. Zaletą SVG jest natomiast możliwość ukrycia części informacji (np. etykiet i opisów tekstowych, oznaczeń mało istotnych połączeń) dzięki wykorzystaniu interaktywnych skryptów.
2.1. Formalny opis topologii sieci komputerowej
Topologię sieci komputerowej definiuje się jako uogólnienie pojęcia grafu (lub digrafu skierowanego) G = (V, E), w którym każdy węzeł ze zbioru V jest rozumiany jako uporządkowany zbiór wartości liczbowych i ciągów znaków, natomiast każda krawędź ze zbioru E stanowi (uporządkowaną) parę węzłów ze zbioru V oraz zbiór uporządkowany wartości liczbowych i ciągów znaków reprezentujących tę krawędź. Węzły z V modelują węzły sieci, a krawędzie – bezpośrednie połączenia pomiędzy węzłami. Wizualizację topologii sieci można interpretować jako proces kilkuetapowy, wymagający:
- ustalenia lokalizacji każdego z węzłów ze zbioru V na dwuwymiarowej mapie,
- określenia wykresu krzywych odpowiadających krawędziom ze zbioru E, -
- wizualizacji węzłów w przyjętych dla nich lokalizacjach, wraz z informacjami pomocniczymi, w sposób uzależniony od parametrów węzła,
- narysowania krawędzi wzdłuż wytyczonych krzywych, wraz z pomocniczymi oznaczeniami, w sposób uzależniony od parametrów krawędzi.
Przedstawione powyżej podejście do modelowania topologii sieci jest obecnie w zasadzie jedynym stosowanym. Sam model nie narzuca dokładnej reprezentacji węzłów, choć zazwyczaj przyjmuje się, że węzły stanowią niewielkich rozmiarów (niemal punktowe) obrazy wektorowe. Nic nie stoi jednak na przeszkodzie, by węzły reprezentować jako odcinki lub prostokąty. Model ogranicza natomiast swobodę reprezentacji krawędzi, narzucając, iż musi ona odpowiadać w przybliżeniu wykresowi pewnej nierozgałęzionej krzywej.
Model pozwala przekazać informacje o nazwach węzłów, rodzaju i przepustowości połączeń między nimi, oraz o współrzędnych określających położenie węzłów i bieg krawędzi. Nie jest możliwe jednak bezpośrednie wyrażenie powiązań pomiędzy krawędziami (nie można np. wprost zażądać, aby struktura pierścieniowa występująca w sieci, reprezentowana w grafie przez cykl, miał krawędzie tworzące idealny okrąg).
2.2. Język opisu struktur grafowych GraphML
Język GraphML jest formatem opisu grafów w składni XML. Pozwala na opisanie węzłów oraz krawędzi grafu, wraz z dodatkowymi parametrami. Główny element pliku nazywa się <graphml> i zawiera listę elementów <graph>, z których każdy opisuje jeden graf, jednoznacznie identyfikowany przez atrybut id (poprzez dodatkowy atrybut można określić, czy graf ma skierowane krawędzie). Zawartością każdego elementu <graph> jest lista węzłów, podanych poprzez element <node> z atrybutem id identyfikującym węzeł. Krawędzie opisane są poprzez elementy postaci <edge source="id1" target="id2"> , gdzie id1 i id2 oznaczają identyfikatory węzłów łączonych przez krawędź.
Element <node> lub <edge> może zawierać listę parametrów opisujących dany węzeł lub krawędź. Każdy parametr jest postaci <data key="name">value</data>, gdzie name oznacza nazwę identyfikującą parametr, a value wartość tego parametru dla rozpatrywanego elementu. Deklaracja parametru następuje w obrębie głównego elementu <graphml> i ma postać:
<key id="identifier" for=["node"|"edge"] attr.name="name" attr.type="type">
<default> value </default>
</key>
gdzie type jest jednym z typów wbudowanych języka Java.
Zawartością elementu <node> może, oprócz wartości parametrów, być podgraf osadzony w tym węźle (zapisany w postaci zagnieżdżonego elementu <graph>. Taki mechanizm hierarchizacji danych w grafie pozwala później na łatwiejsze wydzielanie z grafiki wektorowej SVG informacji dającej się ukryć przez użytkownika.
W dalszym ciągu rozważań nad mapami topologii sieci komputerowej będziemy przyjmować, że topologia sieci zamodelowana jest w postaci grafu w języku GraphML. Metody wizualizacji grafu zależą w dużej mierze od tego, czy w postaci parametrów zostały narzucone współrzędne węzłów. Przypadki wizualizacji grafów o znanych współrzędnych oraz dla grafów o współrzędnych dowolnych zostały opisane w kolejnych paragrafach.
2.3. Mapy sieci komputerowych zachowujące współrzędne
Mapy sieci komputerowych wiernie oddające współrzędne węzłów mają charakter zbliżony do tradycyjnych map geograficznych. Ich niewątpliwą zaletą jest łatwość połączenia wizualizacji takiej mapy z mapą zabudowy czy ukształtowania terenu (lub mapą polityczną w przypadku sieci rozległych). Takie informacje uzupełniające mogą być zamieszczone albo jako warstwy grafiki wektorowej, albo osadzone jako grafika rastrowa stanowiąca tło dla reszty grafiki wektorowej SVG. Możliwe są dzięki temu analizy przestrzenne czy pomiary odległości występujących w sieci, co jest szczególnie istotne w przypadku planowania rozbudowy już istniejącej sieci.
Poważnym problemem jest reprezentacja krawędzi grafu, czyli połączeń pomiędzy węzłami. Istnieją sytuacje, w których konieczne jest również wierne oddanie biegu istniejących połączeń (wówczas problem rysowania sieci komputerowej _de facto _nie różni się od wizualizacji jakiejkolwiek innej sieci połączeń, np. sieci drogowej lub wodociągowej). W sytuacji, gdy bieg połączeń nie jest narzucony, prowadzi się je najczęściej po liniach prostych, lub krzywych gładkich w taki sposób, by zminimalizować liczbę występujących przecięć.
Wizualizacji oparta o połączenia prostoliniowe jest stosunkowo łatwa w realizacji i zazwyczaj prowadzi do zadawalającego efektu wizualnego. W przypadku sieci prostych topologii wizualizacja jest możliwa nawet poprzez proste przekształcenie XSLT z dokumentu GraphML do dokumentu SVG, rys. 4.
Metody prowadzanie krawędzi wzdłuż krzywych w celu minimalizacji liczby przecięć są słabo udokumentowane teoretycznie; najlepsze efekty uzyskuje się poprzez zastosowanie algorytmów metaheurystycznych (np. symulowanego wyżarzania), lub metody sprężynowe przy usztywnionych położeniach węzłów. Prawdziwy problem stanowią ustalone pozycje węzłów, przez co rozwiązania minimalizujące liczbę przecięć krawędzi często doprowadzają do nadmiernego wizualnego zagęszczenia połączeń w pobliżu pewnych węzłów (zjawisko to jest trudne do określenia ilościowo i trudne do uwzględnienia w funkcji przystosowania stosowanej heurystyki). Obniża to znacząco czytelność uzyskiwanej wizualizacji.
<graphml xmlns:g="http://graphml.graphdrawing.org/xmlns/graphml"
xmlns="http://graphml.graphdrawing.org/xmlns/graphml">
<key id="x" for="node"/>
<key id="y" for="node"/>
<key id="b" for="edge"/>
<key id="width" for="graph"/>
<key id="height" for="graph"/>
<graph>
<data key="width">320</data>
<data key="height">240</data>
<node id="n9">
<data key="x">177.58</data>
<data key="y">133.06</data>
</node>
<node id="n8">
<data key="x">145.99</data>
<data key="y">127.22</data>
</node>
(etc)
<node id="n0">
<data key="x">163.18</data>
<data key="y">119.83</data>
</node>
<edge id="e29" source="n5" target="n1">
<data key="b">10</data>
</edge>
<edge id="e28" source="n2" target="n0"/>
<edge id="e27" source="n8" target="n7"/>
<edge id="e26" source="n6" target="n4"/>
<edge id="e25" source="n8" target="n0"/>
<edge id="e24" source="n5" target="n0">
<data key="b">20</data>
</edge>
<edge id="e23" source="n3" target="n2"/>
(etc)
<edge id="e1" source="n6" target="n2"/>
<edge id="e0" source="n5" target="n2"/>
</graph>
</graphml>
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
xmlns:Math="java:java.lang.Math" exclude-result-prefixes="Math g"
xmlns:g="http://graphml.graphdrawing.org/xmlns/graphml"
xmlns:xlink="http://www.w3.org/1999/xlink"
xpath-default-namespace="http://graphml.graphdrawing.org/xmlns/graphml">
<xsl:output method="xml" indent="yes"/>
<xsl:namespace-alias stylesheet-prefix="g" result-prefix="#default"/>
<xsl:key name="node" match="node" use="@id"/>
<xsl:template match="desc|key|data"/>
<xsl:template match="/graphml/graph">
<xsl:processing-instruction name="xml-stylesheet">href="computer.css"
type="text/css"</xsl:processing-instruction>
<svg width="16cm" height="12cm"
viewBox="0 0 {data[@key='width']} {data[@key='height']}">
<xsl:apply-templates select="edge"/>
<xsl:apply-templates select="node"/>
</svg>
</xsl:template>
<xsl:template match="node">
<use class="terminal" xlink:href="computer.svg#terminal"
transform="translate({data[@key='x']} {data[@key='y']})
translate(-1.5 -2) scale(0.02)"/>
</xsl:template>
<xsl:template match="edge">
<xsl:choose>
<xsl:when test="data[@key='b']">
<line style="stroke:#77{data[@key='b'] mod 9}; stroke-width:{0.04 +
data[@key='b'] * 0.01}px; fill:none;"
x1="{key('node',@source)/data[@key='x']}"
y1="{key('node',@source)/data[@key='y']}"
x2="{key('node',@target)/data[@key='x']}"
y2="{key('node',@target)/data[@key='y']}"/>
<text x="{0.5 * (key('node',@source)/data[@key='x'] +
key('node',@target)/data[@key='x']) - 1.6}"
y="{0.5 * (key('node',@source)/data[@key='y'] +
key('node',@target)/data[@key='y'] )}"
font-family="Verdana" font-size="1" fill="blue"
stroke="white" stroke-width="0.01">
<xsl:value-of select = "data[@key='b']"/>Mbit
</text>
</xsl:when>
<xsl:otherwise>
<line style="stroke:black; stroke-width:0.05px; fill:none;"
x1="{key('node',@source)/data[@key='x']}"
y1="{key('node',@source)/data[@key='y']}"
x2="{key('node',@target)/data[@key='x']}"
y2="{key('node',@target)/data[@key='y']}"/>
</xsl:otherwise>
</xsl:choose>
</xsl:template>
</xsl:stylesheet>
Rys. 4. Przekształcenie pliku GraphML (u góry) przez arkusz XSLT (po środku) do formatu SVG oraz efekt wizualizacji (na dole). Przy opracowaniu XSLT wykorzystano fragmenty [11].
2.4. Osadzenia topologii sieci komputerowych na płaszczyźnie
Celem wizualizacji topologii sieci komputerowej bez narzuconych współrzędnych węzłów jest takie ich rozmieszczenie na płaszczyźnie, aby umożliwić możliwie łatwą analizę topologii sieci przez człowieka. Prawdopodobnie pierwszą komercyjnie udaną próbą odejścia od prób wizualizacji topologii rzeczywistej była mapa tras londyńskiego metra, sporządzona w 1933r. przez Harry’ego Becka (rys. 5).
a) 
b) 
Rys. 5. [6] Obrazy SVG przedstawiające: a) rzeczywistą topologię metra w Londynie, b) topologię przyjętą na powszechnie stosowanej mapie metra
W drugiej połowie XX w., wraz z rozwojem teorii grafów nastąpił rozwój algorytmów służących do osadzania grafów na płaszczyźnie zgodnie z różnymi funkcjami kryterialnymi jakości, popularnie zwanymi estetykami. Najbardziej znaną estetyką jest minimalizacja liczby przecięć krawędzi w rysunku grafu. Optymalne rozwiązanie w myśl tej estetyki można dla grafów planarnych, do których należą topologie typowych sieci, znaleźć w czasie liniowym (rysunek grafu bez przecinających się krawędzi jest uzyskiwany w czasie proporcjonalnym do liczby węzłów), natomiast dla grafów ogólnych problem ten jest NP-trudny. Spośród algorytmów rysowania grafów planarnych (rys. 6) najczytelniejszy rysunek wynikowy uzyskuje się zazwyczaj poprzez osadzenie wierzchołków na możliwie dużych cyklach (metoda Tutte circle, rys. 6_e_), bądź też rezygnację z założenia o wierzchołkach punktowych i krawędziach prostych (rys. 6_f_ i 7_a_).
a) 
b) 
c) 
d) 
e) 
f) 
Rys. 6. Wyniki działania optymalnych algorytmów rysowania planarnego na grafie Petersena pozbawionym dwóch krawędzi: a) rysunek wyjściowy, b) wynik algorytmu FPP Fary, c) wynik algorytmu Schnydera, d) wynik algorytmu Schnyder-V, e) wynik algorytmu cyrkularnego Tutte,_ f_) wynik algorytmu z krawędziami krzywymi
a) 
b) 
c) 
Rys. 7. Wyniki działania optymalnych algorytmów rysowania planarnego na grafie Petersena pozbawionym dwóch krawędzi: a) rysunek widoczności przedziałowej, b) rysunek widoczności przedziałowej FPP, c) rysunek widoczności przedziałowej globalnej
Wszystkie prezentowane metody wizualizacji topologii grafu mają jedną zasadniczą wadę – nie zachowują jakichkolwiek relacji przestrzennych, które występowały w pierwotnej konfiguracji węzłów. Nie są znane żadne wydajne optymalne algorytmy rysowania z zachowaniem tzw. własności mapy. Stosunkowo najlepiej radzi sobie popularna metoda heurystycznego przeszukiwania lokalnego, zwana przeszukiwaniem sprężynowym (rys. 8). Implementacja algorytmu sprężynowego jest na tyle prosta, że arkusz XSLT [11] przekształcający nieosadzony plik GraphML w osadzony na płaszczyźnie plik GraphML wykonuje w przeciągu sekundy kilkadziesiąt jego iteracji dla grafu 50-wierzchołkowego, co wystarcza, aby zapewnić regularne rozmieszczenie wierzchołków przy niezbyt dużej liczbie przecięć krawędzi. Kolejny krok przekształcenia (do formatu SVG) można już wykonać przy pomocy podanego w poprzednim rozdziale arkusza XSLT.
a) 
b) 
c) 
Rys. 8. Przykładowe osadzenia grafu z rys. 6_a_ algorytmem przeszukiwania sprężynowego (rysunek z lewej odpowiada ustawieniu inicjalnemu grafu z pozycji 6_a_)
Przy wizualizacji dużych sieci, z myślą o prezentacji w postaci cyfrowej, należy pamiętać o ograniczonej rozdzielczości urządzenia wyświetlającego. W związku z tym, gdy tylko jest to możliwe, korzystne wydaje się regularne rozmieszczanie węzłów sieci w niewielkich odległościach od siebie. Na podstawie wyników badań przedstawionych w [1] można dokonać szacunkowego obliczenia liczby węzłów, które da się z zachowaniem czytelności pomieścić na ekranie w przypadku sieci o topologii bardzo rzadkiej (lub wręcz o topologii drzewa). Przykładowe optymalne rozplanowanie układu wektorowej grafiki SVG dla korporacyjnej sieci komputerowej o kilkuset węzłach przedstawiono na rys. 9.
Rys. 9. [1] Maksymalne upakowanie węzłów sieci o strukturze drzewiastej przy wizualizacji na ekranie w rozdzielczości 800x600
2.5. Inne zastosowania SVG w modelowaniu sieci
Jedną z zalet języka SVG jest łatwość generowania dokumentów SVG przez programy napisane w językach wysokiego poziomu z dobrym wsparciem dla XML, takich jak Java lub Python. Nic więc dziwnego, że dla wielu sieciowych aplikacji o charakterze diagnostycznym format SVG jest domyślnym, wewnętrznym formatem opisu grafiki (następnie opcjonalnie konwertowanym do innego formatu). Przykładem aplikacji wykorzystującej potencjał SVG jest narzędzie do rysowania digrafów skierowanych Graphviz [9]. Za pomocą prostej aplikacji Scapy [12] służącej do diagnozowania ruchu sieciowego w systemie Linux, można uzyskać poprzez śledzenie połączeń fragmentaryczny opis topologii otaczającej sieci szkieletowej. Wyniki wizualizacji SVG takiego opisu przy pomocy Graphviz dla hosta znajdującego się na terenie Francji przedstawiono na rys. 10.
Rys. 10. [12] Wizualizacja SVG dla fragmentu topologii sieci szkieletowej operatorów francuskich, uzyskanego poprzez śledzenie tras
Bibliografia
- [1] Arshad A. et al: _Single Snapshot Exploratory Approach for Visualizing Very Large Network Topologies. _SVG Open – 3 rd Annual Conference on Scalable Vector Graphics, Tokyo, Japan, 2004.
- [2] Brandes U., Eiglsperger M., Lerner J_.: GraphML Primer_. http://graphml.graphdrawing.org/
- [3] Cecconi A., Galanda M.: Adaptive Zooming in Web Cartography. SVG Open – Conference on Interactive Vector-based Webgraphics, Online GIS and Webmapping, Zurich, Szwajcaria, http://kartoweb.itc.nl/2002.
- [4] Konsorcjum W3C: Scalable Vector Graphics (SVG) 1.1 Specification. W3C Recommendation 14 January 2003. http://www.w3.org/TR/SVG11/
- [5] Konsorcjum W3C: _Accessibility Features of SVG. __W3C Note 7 August 2000_. http://www.w3.org/TR/SVG-access
- [6] Kartografie in Nederland, SVG morph of London tube system, http://kartoweb.itc.nl/public_examples/UndergroundMorph.html.
- [7] de Fraysseix H., de Mendez P.O.: Public Implementation of a Graph Algorithm Library and Editor. http://pigale.sourceforge.net/.
- [8] Adobe: SVG Viewer for Internet Explorer. http:/www.adobe.com/svg/
- [9] AT&T: Graphviz - Graph Visualization Software. http://www.graphviz.org/
- [10] Pich C.: Style sheet for very small force directed graphs. http://graphml.graphdrawing.org/download/spring.xsl
- [11] Pich C.: Formatting a spring graph. http://graphml.graphdrawing.org/download/graphml2svg.xsl
- [12] Debian Linux: Scapy - A Powerful Interactive Packet Manipulation Tool. http://www.cartel-securite.fr/pbiondi/projects/scapy/
Do wizualizacji rys. 1-5 wykorzystano program [8]. Do wizualizacji rys. 6-8 wykorzystano program [7].
Aby dodawać komentarze musisz być zalogowany!