skiminok: (xkcd)
[personal profile] skiminok
Пакет инструментов gtools, входящий в состав nauty, отлично подходит для генерирования графов и различных их характеристик, а также манипулирования графами тучей разных способов. Собирается на Cygwin без малейших затруднений.

Пример: сгенерировать все связные графы из 5 вершин с максимальной степенью вершины 4 и диаметром 2, записать в файл в формате g6.

$ ./geng -cD4 5 | ./pickg --e -Z2 - "output.g6"
>A ./geng -cd1D4 n=5 e=4-10
>Z 21 graphs generated in 0.00 sec
>A ./pickg --e -Z2 - output.g6
1 graphs : e=4
2 graphs : e=5
4 graphs : e=6
4 graphs : e=7
2 graphs : e=8
1 graphs : e=9
>Z 21 graphs read from stdin; 14 written to output.g6; 0.000 sec


После чего полученный файл можно загрузить в Wolfram Mathematica и любоваться результатами.

Import["output.g6"]


С этим дальше можно играться. Например, получить представление в виде списка ребер для всех графов с 7 ребрами из этого файла.

EdgeRules /@ Select[Import["output.g6"], EdgeCount[#] == 7 &] // Column
{1->4,1->5,2->4,2->5,3->4,3->5,4->5}
{1->3,1->4,1->5,2->4,2->5,3->5,4->5}
{1->3,1->4,1->5,2->5,3->4,3->5,4->5}
{1->3,1->4,1->5,2->3,2->4,2->5,3->5}
From:
Anonymous
OpenID
Identity URL: 
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

skiminok: (Default)
skiminok

Most Popular Tags

July 2011

S M T W T F S
     12
3456789
10111213141516
17181920212223
242526272829 30
31