Lubię graficzne schematy. Parę kresek i kilka słów potrafi lepiej przedstawić jakąś informację niż wiele stron tekstu. Zarazem mam z nimi problem: o ile na kartce czy tablicy rysuję dość chętnie i łatwo (choć niezbyt pięknie), o tyle na komputerze idzie mi to opornie. Czy używam flowchartera, czy programu do grafiki wektorowej, czy narzędzia do UML - zamiast koncentrować się na treści, grzęznę w szczegółach. Walczę o właściwe rozmieszczenie strzałek i boksów, pracowicie przestawiam czcionki w kolejnych pudełkach, poszukuję obejść pozwalających na umieszczenia jakiejś adnotacji w odpowiednim miejscu... Chyba tylko mind-mapy są mniej pracochłonne.
Jakiś czas temu, w nieco zgryźliwym nastroju, postanowiłem puścić po firmie następujący obrazek.
Aby puścić, trzeba było zrobić. Spróbowałem graficznie (akurat w Inkscape ale w Dia sprawa jest równie beznadziejna). Węzły dały się namalować nawet dość szybko ale po paru próbach poukładania połączeń po prostu się poddałem. Czego by nie robić i jak by nie wyginać tych krzywych, albo zaczepiały o węzły, albo splatały się w nieczytelny kłąb (nie mówiąc o konieczności ciągłego przepinania).
A potem przypomniałem sobie o GraphVizie (szczęśliwie nieco wcześniej oglądanym w kontekście innego zastosowania) i w kilkanaście minut napisałem, co następuje:
digraph obsluga_zgloszenia {
// Wspólne cechy wszystkiego
size = "8.6,8.6";
concentrate = true;
node [shape=ellipse, fontsize=12, height=0.6, width=0.6, fixedsize=false];
edge [style=solid];
// Stany
start [ label="Czy bug jest przypisany do mnie?" ];
alok [ label="Czy jestem formalnie zaalokowany?" ];
zapyt [ label="Czy mogę się kogoś o coś spytać?" ];
probl [ label="Czy mam jakąkolwiek trudnosć,\nnp. źle ustawiona ścieżka czy chwilowy brak sieci" ];
pretn [ label="Czy mam pretekst by mieć do kogoś pretensje?" ];
flamestart [ label="Czy da się zacząć jakiś flamewar?" ];
uzup [ label="Czy upłynęło już dość czasu\nby spytać czy problem nadal występuje?" ];
przek [ label="Przekieruj i zapomnij" ];
flame [ label="Urraaaaa" ];
sen [ label="Ignoruj" ];
wait [ label="Poczekaj troszkę" ];
// Krawędzie
edge [ label="Tak" ];
start -> alok;
alok -> zapyt;
zapyt -> przek;
probl -> przek;
pretn -> przek;
flamestart -> flame;
uzup -> przek;
edge [ label="Nie" ];
start -> sen;
zapyt -> probl;
probl -> pretn;
pretn -> flamestart;
alok -> sen;
flamestart -> uzup;
uzup -> wait;
edge [ label="Tak, Nie, Nieważne" ];
flame -> flame;
edge [label = ""];
wait -> start;
}
Potem
$ dot -Tpng algorytm.dot > algorytm.png
i już.
Kilka słów o języku DOT
Mój powyższy kod nie jest przesadnie ładny (zastanawiałem się, czy go
na potrzeby artykułu nie wygładzić ale ostatecznie zostawiłem
autentyczny przykład). Komplikuje go zwłaszcza wprowadzenie
symbolicznych etykiet węzłów, które oszczędziły mi pisania przy
przestawianiu kolejności i dorzucaniu dodatkowych kroków. Czytając go
trzeba też pamiętać, że w języku DOT atrybuty ustawiane przy node
albo edge są globalne i obowiązują do czasu zmiany (dlatego
np. wszystkie krawędzie poniżej edge [label="Tak"] są opisane słowem
Tak).
Tak naprawdę w języku DOT chodzi jednak po prostu o zapisy połączeń (wszystkie te coś -> coś), cała reszta to uzupełnienia. Zupełnie sensowny diagram można zrobić pisząc po prostu:
digraph krolowie {
"Władysław Jagiełło" -> "Władysław Warneńczyk" [label="następca"];
"Władysław Jagiełło" -> "Kazimierz";
"Władysław Jagiełło" -> "Kazimierz Jagiellończyk";
"Kazimierz Jagiellończyk" -> "Jan Olbracht";
"Kazimierz Jagiellończyk" -> "Zygmunt Stary";
}
Czy wszystko da się tak namalować? Nie, choć bynajmniej nie tylko proste grafy. Trudniejsze przykłady wymagają jednak poświęcenia chwili czasu na lekturę dokumentacji (radzę zacząć od dotguide) na co nie każdy musi mieć ochotę. Przynajmniej jednak dla prostych schematów trudno mi sobie wyobrazić szybszą metodę niż ta - wymagająca de facto jedynie wypisania listy węzłów i połączeń.
Już używasz GraphViza
Ze względu na łatwość generowania plików .dot, wiele możliwych
formatów wynikowych, a także dostępność różnorakich
pomocniczych bibliotek
GraphViz jest używany w wielu webowych i desktopowych narzędziach.
Przykładowo, właśnie dzięki niemu można oglądać hierarchie zgłoszeń w
Bugzilli albo hierarchie klas w dokumentacji generowanej Doxygenem.
Emacs
Moje środowisko edycyjne do Graphviza wygląda następująco:
Zapewnia mi je graphviz-dot-mode.
Problem layoutu
GraphViz oszczędza mi klikania ale przede wszystkim rozwiązuje niebanalny problem, jakim jest automatyczne rozmieszczenie elementów grafu (tak by minimalizować przecięcia, uniknąć nachodzenia węzłów na siebie i rozmieścić całość w miarę równomiernie). To jest całkiem trudne (co przy okazji uzasadnia, czemu dla niebanalnych schematów niełatwo zrobić to ręcznie).
Fajną zabawą programistyczną jest próba zrobienia tego samemu (ja próbowałem, poniosłem klęskę ale doświadczenie uważam za pouczające). Napisz skrypt, który wczyta z wejścia listę stanów i połączeń i namaluje jak najładniejszy obrazek. Wejście może wyglądać np. tak:
A,C,E,F,H,I,J,L,M,N,O,P,R,T,V,Z A-C A-E A-R A-T C-F E-F E-H E-I E-V F-J H-Z I-O I-Z J-P L-J L-N M-J M-P M-Z N-P R-F R-J R-L T-F T-M V-Z Z-O Z-P
a w samym malowaniu obrazka może być przydatny np. poniższy skrawek kodu:
# -*- coding: utf-8 -*-
#
# Generacja pliku SVG z pomocą svgfig
# http://code.google.com/p/svgfig/
from svgfig import *
def make_point(x, y, txt):
circle = SVG("circle", cx=x, cy=y, r=30, fill="white")
txt = Text(x, y, txt, fill="black")
txt.attr["font-size"] = 16
txt.attr["text-anchor"] = "middle"
txt.attr["dominant-baseline"] = "middle"
return Fig(circle, txt)
line = Line(50, 50, 120, 170, fill="black")
point1 = make_point(50, 50," A")
point2 = make_point(120, 170, "B")
picture = canvas_outline(
Fig(line, point1, point2).SVG(),
width = "640px", height="640px", viewBox="1 1 640 640",
)
picture.attr["style"] = "stroke: black; fill: white; stroke-width: 1pt; stroke-linejoin:round; text-anchor: middle; font-weight:bold"
#picture.save("test.svg")
picture.firefox("test.svg") # Zapis do test.svg i podgląd w firefoksie
Najbardziej znany klasyczny algorytm jest opisany tutaj.
W praktyce warto jednak stosować gotowce. GraphViz nie jest jedynym, kilka algorytmów rozmieszczania grafu udostępnia boost.graph (patrz rozdział Layout Algorithms), kilkanaście OGDF, wspomnę jeszcze CCVisu oraz Microsoftowy MSAGL.