powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Визуализация планарных графов
22 сообщений из 22, страница 1 из 1
Визуализация планарных графов
    #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
Визуализация планарных графов
    #36265454
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если выбрать случайные координаты вершин на плоскости,
то получается вот такая мешанина (это граф Татта). И как ее распутать?
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #36265552
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я щас изучаю библиотеку grappa. Насколько разобрался, она родственная с graphviz. Вот только успехов пока особых нету. Но если сегодня-завтра будет свободные минут 20 - попробую нарисовать чё-нить.
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #36265567
Фотография RT183.1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Бум ждать
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #36265592
junior  idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Вот здесь: http://www.graphdrawing.org/literature/gd-constraints.pdf очень хорошая статья на эту тему (кратко, сжато перечислены основные алгоритмы отрисовки разных графов в разных задачах, а дальше уже можно использовать гугл); я, правда, призняться, ничего кроме пары-тройки самых тривиальных алгоритмов не осваивал и не применял, но про отрисовку планарных графов без пересечений там рассказано.
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #36265617
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Модератор: Вложение удалено.
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #36265619
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
neato.exe

Модератор: Вложение удалено.
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #36265621
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЯ щас изучаю библиотеку grappa. Насколько разобрался, она родственная с graphviz. Вот только успехов пока особых нету. Но если сегодня-завтра будет свободные минут 20 - попробую нарисовать чё-нить.
а чем она лучше чем графиз?
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #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
Визуализация планарных графов
    #36265627
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
neato
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #36265628
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
dot
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #36265636
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tchingizа чем она лучше чем графиз?
А хрен его знает. Я первую не использовал. Просто grappa привлекает тем, что реализована на java.
...
Рейтинг: 0 / 0
Визуализация планарных графов
    #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
Визуализация планарных графов
    #36267822
kamre
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Интересные результаты в yEd :

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

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

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

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

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

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


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