Подсчет перед перечислением
Иногда хранение математических объектов, представляющих интерес, в списке
слишком амбициозный, потому что это заняло бы слишком много памяти.
Одним из первых шагов может быть подсчет количества таких графиков,
и сколько времени потребуется, чтобы перебрать их, прежде чем пытаться
хранить их.
Время ниже указано на одной конкретной машине; они могут отличаться
на других машинах.
Подсчет графов на 11 вершинах с 30 ребрами с кликой номер 4
заняло около двух часов.
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: %time nb_g_11_30_c4 = sum(1 for g in g_11_30_c4)
CPU times: user 2h 12min 9s, sys: 1min 9s, total: 2h 13min 18s
Wall time: 2h 13min 18s
sage: nb_cg_11_30_c4
58211868
Подсчет только подключенных занял примерно одинаковое время.
sage: cg_11_30 = graphs.nauty_geng('11 30:30 -c')
sage: cg_11_30_c4 = (g for g in cg_11_30 if g.clique_number() == 4)
sage: %time nb_cg_11_30_c4 = sum(1 for g in cg_11_30_c4)
CPU times: user 2h 13min 27s, sys: 1min 11s, total: 2h 14min 38s
Wall time: 2h 14min 39s
sage: nb_cg_11_30_c4
58182054
Мы видим, что существует около 58,2 миллионов графов на 11 вершинах с 30 ребрами
и клика № 4, большинство из них подключены - только 29814 нет.
Если мы заботимся только о неподключенных, это имеет большое значение!
Итерация, а не перечисление
Если сохранение этих графиков неосуществимо, мы знаем, что можем пройти через них
через два часа каждый раз, когда мы хотим что-то узнать о них.
Один хороший способ узнать об итерациях и списках - это запустить
Учебник по SageMath по пониманию .
Например, возьмите первый граф в коллекции и проверьте его ребра
и его граф6 строка
( больше в формате graph6 ):
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: g = next(g_11_30_c4)
sage: print(g.edges(labels=False))
[(0, 7), (0, 8), (0, 9), (0, 10), (1, 7), (1, 8), (1, 9), (1, 10),
(2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10),
(4, 8), (4, 9), (4, 10), (5, 8), (5, 9), (5, 10), (6, 8), (6, 9),
(6, 10), (7, 9), (7, 10), (8, 9), (8, 10), (9, 10)]
sage: g.graph6_string()
'J???Fb}~~~_'
и второй:
sage: g = next(g_11_30_c4)
sage: print(g.edges(labels=False))
[(0, 7), (0, 8), (0, 9), (0, 10), (1, 7), (1, 8), (1, 9), (1, 10),
(2, 7), (2, 8), (2, 9), (2, 10), (3, 7), (3, 8), (3, 9), (3, 10),
(4, 8), (4, 9), (4, 10), (5, 8), (5, 9), (5, 10), (6, 8), (6, 9),
(6, 10), (7, 8), (7, 9), (7, 10), (8, 10), (9, 10)]
sage: g.graph6_string()
'J???Fb~~v~_'
и т. Д.
Хранение меньших эквивалентных данных
Если сами графики слишком велики для хранения в списке, возможно, мы сможем
использовать более компактные представления этих графов, которые заняли бы
меньше памяти Например, список ребер позволяет нам легко восстановить
график; как и очень компактная «строка графа6».
Чтобы дать нам идею, давайте сравним размеры файлов для
список первых десяти тысяч графов в виде объекта Sage,
список их краевых списков в виде объекта Sage,
и строка graph6 для них в виде текстового файла:
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: graphs = [next(g_11_30_c4) for _ in range(10^4)]
sage: save(graphs, "g_11_30_c4_1e4_graph_bare")
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: edges = [next(g_11_30_c4).edges(labels=False) for _ in range(10^4)]
sage: save(edges, "g_11_30_c4_1e4_graph_edges")
sage: g_11_30 = graphs.nauty_geng('11 30:30')
sage: g_11_30_c4 = (g for g in g_11_30 if g.clique_number() == 4)
sage: s = '\n'.join(next(g_11_30_c4).graph6_string() for _ in range(10^4))
sage: with open('g_11_30_c4_graph_graph6.txt', 'w') as f:
....: f.write(s)
....:
119999
Сравните соответствующие размеры файлов:
g_11_30_c4_1e4_graph_bare.sobj: 971K g_11_30_c4_1e4_graph_edges.sobj: 775K g_11_30_c4_1e4_graph_graph6.txt: 117K
Очевидно, что формат graph6 выигрывает и сохраняет все 58.2 миллионов графов
в этом формате в текстовом файле потребуется ~ 5820 * 117K, т.е. ~ 680M.
Мы также можем сохранить его в 100 файлах с номерами от 0 до 99, как показано ниже:
sage: n = 100
sage: for k in range(N):
....: gk = graphs.nauty_geng('11 30:30 {}/{}'.format(k, n))
....: ggk = (g for g in gk if g.clique_number() == 4)
....: s = '\n'.join(g.graph6_string() for g in ggk)
....: with open('g_11_30_c4_graph_graph6_file_{}_of_{}.txt'
....: .format(k, n - 1), 'w') as f:
....: f.write(s)
Это позволит нам изучать эти графики в течение нескольких сессий, не делая
каждый день по два часа.
Рекомендуемое чтение, в зависимости от версии Python, на которой основан ваш Sage: