Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Визуализация планарных графов / 22 сообщений из 22, страница 1 из 1
21.10.2009, 17:49
    #36265159
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
У кого есть graphviz покажите каким он нарисует граф Татта (Tutte's graph)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
 46   69      ------- 46 вершин, 69 ребер;
 0   1 
 0   2 
 0   3 
 1   26 
 1   4 
 2   10 
 2   11 
 3   18 
 3   19 
 4   5 
 4   33 
 5   29 
 5   6 
 6   27 
 6   7 
 7   8 
 7   14 
 8   9 
 8   38 
 9   10 
 9   37 
 10   39 
 11   12 
 11   39 
 12   35 
 12   13 
 13   14 
 13   15 
 14   34 
 15   16 
 15   22 
 16   17 
 16   44 
 17   18 
 17   43 
 18   45 
 19   20 
 19   45 
 20   41 
 20   21 
 21   22 
 21   23 
 22   40 
 23   24 
 23   27 
 24   32 
 24   25 
 25   26 
 25   31 
 26   33 
 27   28 
 28   32 
 28   29 
 29   30 
 30   33 
 30   31 
 31   32 
 34   35 
 34   38 
 35   36 
 36   37 
 36   39 
 37   38 
 40   41 
 40   44 
 41   42 
 42   43 
 42   45 
 43   44 
...
Рейтинг: 0 / 0
21.10.2009, 20:55
    #36265454
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
Если выбрать случайные координаты вершин на плоскости,
то получается вот такая мешанина (это граф Татта). И как ее распутать?
...
Рейтинг: 0 / 0
21.10.2009, 22:14
    #36265552
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
Я щас изучаю библиотеку grappa. Насколько разобрался, она родственная с graphviz. Вот только успехов пока особых нету. Но если сегодня-завтра будет свободные минут 20 - попробую нарисовать чё-нить.
...
Рейтинг: 0 / 0
21.10.2009, 22:29
    #36265567
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
Бум ждать
...
Рейтинг: 0 / 0
21.10.2009, 22:54
    #36265592
junior  idiot
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
Вот здесь: http://www.graphdrawing.org/literature/gd-constraints.pdf очень хорошая статья на эту тему (кратко, сжато перечислены основные алгоритмы отрисовки разных графов в разных задачах, а дальше уже можно использовать гугл); я, правда, призняться, ничего кроме пары-тройки самых тривиальных алгоритмов не осваивал и не применял, но про отрисовку планарных графов без пересечений там рассказано.
...
Рейтинг: 0 / 0
21.10.2009, 23:12
    #36265617
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
Модератор: Вложение удалено.
...
Рейтинг: 0 / 0
21.10.2009, 23:14
    #36265619
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
neato.exe

Модератор: Вложение удалено.
...
Рейтинг: 0 / 0
21.10.2009, 23:17
    #36265621
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
maytonЯ щас изучаю библиотеку grappa. Насколько разобрался, она родственная с graphviz. Вот только успехов пока особых нету. Но если сегодня-завтра будет свободные минут 20 - попробую нарисовать чё-нить.
а чем она лучше чем графиз?
...
Рейтинг: 0 / 0
21.10.2009, 23:21
    #36265625
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
пардон не туда стрелочки поставил
circo
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
digraph world {

0 ->  1    ;
0 ->  2    ;
0 ->  3    ;
1 ->  26   ;
1 ->  4    ;
2 ->  10   ;
2->   11   ;
3->   18   ;
3->   19   ;
4 ->  5    ;
4 ->  33   ;
5 ->  29   ;
5 ->  6    ;
6 ->  27   ;
6 ->  7    ;
7->   8    ;
7->   14   ;
8->   9    ;
8 ->  38   ;
9 ->  10   ;
9 ->  37   ;
10  -> 39  ;
11  -> 12  ;
11  -> 39  ;
12 ->  35  ;
12 ->  13  ;
13 ->  14  ;
13 ->  15  ;
14 ->  34  ;
15 ->  16  ;
15 ->  22  ;
16 ->  17   ;
16 ->  44   ;
17->   18   ;
17->   43   ;
18->   45   ;
19 ->  20   ;
19 ->  45   ;
20 ->  41   ;
20 ->  21   ;
21 ->  22   ;
21 ->  23   ;
22->   40   ;
23->   24   ;
23->   27   ;
24 ->  32   ;
24 ->  25   ;
25 ->  26   ;
25 ->  31   ;
26 ->  33   ;
27 ->  28   ;
28->   32   ;
28->   29   ;
29->   30   ;
30 ->  33   ;
30 ->  31   ;
31 ->  32   ;
34 ->  35   ;
34 ->  38   ;
35 ->  36   ;
36   ->  37   ;
36   ->  39   ;
37   ->  38   ;
40  ->  41   ;
40  ->  44   ;
41  ->  42   ;
42 ->   43   ;
42 ->    45   ;
43 ->   44   ;

}



...
Рейтинг: 0 / 0
21.10.2009, 23:22
    #36265627
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
neato
...
Рейтинг: 0 / 0
21.10.2009, 23:23
    #36265628
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
dot
...
Рейтинг: 0 / 0
21.10.2009, 23:29
    #36265636
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
tchingizа чем она лучше чем графиз?
А хрен его знает. Я первую не использовал. Просто grappa привлекает тем, что реализована на java.
...
Рейтинг: 0 / 0
22.10.2009, 15:37
    #36267239
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
I'm back!
Красивая и очень качественная картинка от neato.
Я тут нашкодил на питоне отрисовку дерева с корнем.
Так ви знаете не так-то просто сообразить как подбирать
Х координаты вершин одного уровня, чтобы овалы не налазили
друг на друга
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
# Список пар имен "родитель - рибеног":
t = (\
    ('H','E'),('A','S'),('A','B'),('C','I'),('C','J'),('C','U'),
    ('Z','C'),('Z','F'),('Z','M'),('M','R'),('M','A'),('M','T'),
    ('F','H'),('F','W'),('W','N'),('H','O'),('H','P'),('M','K'),
    ('R','G'),('R','Y'),('R','V'),('V','D'),('V','X')
    )


from Tkinter import *

def show_tree(a):
    map1, map2, names = {}, {}, set([])
    for ai in a:
        names.add(ai[ 0 ])
        names.add(ai[ 1 ])
        if map1.has_key(ai[ 0 ]):
            map1[ai[ 0 ]].add(ai[ 1 ])
        else:
            map1[ai[ 0 ]] = set([ai[ 1 ]])
        if map2.has_key(ai[ 1 ]):
            map2[ai[ 1 ]].add(ai[ 0 ])
        else:
            map2[ai[ 1 ]] = set([ai[ 0 ]])            
    for name in names:
        if not map2.has_key(name):
            root = name
            break

    WIDTH =  1000 
    HEIGHT =  800 
    NODE_DX =  14 
    NODE_DY =  10 
    NODE_COLOR = 'white'
    EDGE_COLOR = 'blue'
    TEXT_COLOR = 'red'
    
    rt = Tk()
    rt.resizable(True, True)
    rt.title('my_graphviz_tree')
    left = (rt.winfo_screenwidth() - WIDTH) /  2 
    top = (rt.winfo_screenheight() - HEIGHT) /  2 
    rt.geometry('%dx%d+%d+%d' % (WIDTH, HEIGHT, left, top))
    pic = Canvas(rt, width=WIDTH, height=HEIGHT, background='white')
    pic.pack()
    pic.delete(ALL)

    map3 = {}
    root_x, root_y = WIDTH /  2 ,  40 
    map3[root] = [root_x, root_y]

    def foo(parent, x, y, lev):
        if not map1.has_key(parent):
            return
        children = map1[parent]
        y1 = y +  120  *  0 . 8 **lev
        dx =  240  *  0 . 33 **lev
        if len(children) !=  1 :
            x1 = x - dx * (len(children) -  1 ) /  2 
        else:
            x1 = x
        for child in children:
            map3[child] = [x1, y1]
            foo(child, x1, y1, lev +  1 )
            x1 += dx

    def draw_edges(parent):
        if not map1.has_key(parent):
            return
        children = map1[parent]
        x1, y1 = map3[parent]
        for child in children:
            x2, y2 = map3[child]
            pic.create_line((x1, y1, x2, y2), fill=EDGE_COLOR, width= 2 )
            draw_edges(child)

    def draw_nodes():
        for key in map3.keys():
            x, y = map3[key]
            pic.create_oval((x - NODE_DX, y - NODE_DY, x + NODE_DX, y + NODE_DY), fill=NODE_COLOR)
            pic.create_text((x, y), text=str(key), fill=TEXT_COLOR)
    
    foo(root, root_x, root_y,  0 )
    draw_edges(root)
    draw_nodes()

    y =  20 
    for ai in a:
        y +=  16 
        pic.create_text(( 60 , y), text=str(ai[ 0 ])+'   ->   '+str(ai[ 1 ]), fill='black')

    pic.update()
    rt.mainloop()


show_tree(t)
...
Рейтинг: 0 / 0
22.10.2009, 19:34
    #36267822
kamre
Гость
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
Интересные результаты в yEd :

и
...
Рейтинг: 0 / 0
22.10.2009, 19:47
    #36267838
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
> Интересные результаты в yEd:

ох ё.... 2-й вариант просто отпад
...
Рейтинг: 0 / 0
22.10.2009, 20:45
    #36267884
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
RT183.1> Интересные результаты в yEd:

ох ё.... 2-й вариант просто отпад
+1

Мне понравился скрин на оригинальном сайте, где рёбра как-бы "огибают" вершины и не пересекают другие рёбра (по возможности). Это то что я сам когда-то хотел закодить.
...
Рейтинг: 0 / 0
25.10.2009, 05:45
    #36270959
RT183.1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
junior idiot http://www.graphdrawing.org/literature/gd-constraints.pdf
шикарный документ
...
Рейтинг: 0 / 0
27.10.2009, 18:24
    #36275523
АСУ ТПшник
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
графы - тынц . осторожно вызывает привыкание :)
...
Рейтинг: 0 / 0
27.10.2009, 18:29
    #36275530
АСУ ТПшник
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
предлагаю заточить ручной труд программистов под ваши задачи , механизмы уже есть :)
...
Рейтинг: 0 / 0
Период между сообщениями больше года.
19.07.2016, 16:34
    #39276467
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
https://habrahabr.ru/post/302968/

D3.js. Визуализация графов
...
Рейтинг: 0 / 0
29.07.2016, 11:06
    #39282529
kealon(Ruslan)
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
tchingiz,

хорошая штука, спасибо за внятное изложение
...
Рейтинг: 0 / 0
29.07.2016, 17:51
    #39283055
tchingiz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Визуализация планарных графов
kealon(Ruslan),
это не мое изложение
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Визуализация планарных графов / 22 сообщений из 22, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]