Categories: Без рубрики

graphviz/

Есть в юниксах такая полезная утилита под названием Graphviz , предназначенная для рисования графов. В этом посте я приведу пример ее использования. Тем, кто с ГрафВизом уже знаком, будет не интересно, лучше почитайте про Dracula . Остальных же, надеюсь, данный пост подтолкнет к более внимательному изучению данной программы.

Идея простая. Есть конфиг (файл .gv), с помощью которого дается описание графа. Конфиг этот примерно такого содержания:

digraph G {
«A» -> «B»;
«B» -> «C»;
«A» -> «C»;
}

Graphviz принимает такой конфиг на входе, а на выходе дает png|jpg|gif|svg файл с изображением графа. При желании можно дать более подробное описание графа. Например, указать форму и цвет вершин, толщину и направленность рёбер и так далее. Останавливаться на этом я не буду, в man-pages все детально расписано.

В состав Graphviz входит несколько программ, которые почему-то называются «фильтрами». С их помощью один и тот же граф можно нарисовать разными способами. Список и краткое описание программ:

dot — filter for drawing directed graphs
neato — filter for drawing undirected graphs
twopi — filter for radial layouts of graphs
circo — filter for circular layout of graphs
fdp — filter for drawing undirected graphs
sfdp — filter for drawing large undirected graphs

Примеры графов, нарисованных с их помощью, вы можете посмотреть на официальном сайте программы.

Давайте сделаем вид, как будто вы почитали маны и полистали сайт. Отлично, теперь можно попробовать решить с помощью графвиза какую-нибудь задачку.

Представим, что у нас есть несколько компаний, а у этих компаний есть клиенты. По каким-то причинам мы можем отслеживать, к какой компании обращается клиент, если он отказывается от услуг другой компании. В случае, скажем, с хостингом, это действительно не сложно сделать. Задача — построить граф, изображающий перемещения клиентов от компании к компании.

Вот скрипт, генерирующий .gv файл:

#!/usr/bin/perl

# gen-graph.pl
# (c) Alexandr A Alexeev 2010, http://remontka.com/

use strict ;
use List :: Util qw/max shuffle/ ;
use List :: MoreUtils qw/uniq/ ;
use DBI ;
use constant MIN_PERCENT => 5 ;

my %data ; # {from}{to} = cnt
my @sources ;

# генерируем легко различимые и не слишком темные цвета
my @colors ;
for my $c ( qw/8 D A 9 F 6/ ) {
for my $m ( qw/FF0000 00FF00 00FFFF FF00FF FFFF00/ ) {
my $t = $m ;
$t =~ s/F/$c/g ;
push @colors , $t ;
}
}

# забираем данные из БД
my $db = DBI -> connect (
«dbi:mysql:database:localhost» , «user» , «password» ,
{ PrintError => 0 , RaiseError => 0 }
) or die «ERROR: $! n » ;

my $query = qq {
select `from` , `to` , `count` from logs
where month = ‘201009’ ;
} ;

my $res = $db -> prepare ( $query ) ;
$res -> execute ( ) or die «Query failed: n n $query» ;

# начало описания графа
print «digraph G { n » ;
print qq {
nodesep = 2 ;
mindist = 2 ;
} ;
print » n » ;

# максимум клиентов перешло
my $max_cnt = 1 ;

# плюс и минус число клиентов для компании
my %plus ;
my %minus ;

while ( my ( $from , $to , $cnt ) = $res -> fetchrow_array ( ) ) {
$data { $from } { $to } = $cnt ;
$plus { $to } += $cnt ;
$minus { $from } += $cnt ;
$max_cnt = $cnt > $max_cnt ? $cnt : $max_cnt ;
push @sources , $from ;
push @sources , $to ;
}

# shuffle для того, чтобы можно было
# перерисовать граф немного по-другому
@sources = shuffle uniq @sources ;

my $i ;
for my $src ( @sources ) {
# отсекаем компании с небольшой «текучестью клиентов»
next if ( max ( $plus { $src } , $minus { $src } ) < $max_cnt *MIN_PERCENT / 100 ) ;

# берем очередной цвет
my $color = $colors [ $i ++ ] ;
my $delta = $plus { $src } — $minus { $src } ;
# описание вершины графа, соответствующей компании
print » » $src «» [label= «» $src \ n+»» . int ( $plus { $src } ) . «»-«» . int ( $minus { $src } ) . «»delta: $delta «» style= «» filled «»