Один алгоритм раскраски графа II
Недавно я переписал алгоритм субоптимальной правильной вершинной раскраски графа на Python. Решил выложить его сюда.
Вершина графа отождествляется с её индексом. Граф задаётся индексируемой последовательностью (tuple или list) наборов соседей (массив списков соседей). Раскраска — массив (list в терминах Python) цветов.
Итак, функция раскраски у меня имеет следующий вид:
## Построить правильную вершинную раскраску графа.
## \param graph -- граф в виде массива множеств номеров смежных вершин
## \param forbidden -- массив множеств запрещённых цветов для каждой вершины
## \param color -- массив цветов вершин
## \return массив (новых) цветов вершин
def coloring(graph, forbidden=None, color=None):
if forbidden is None: forbidden = []
if color is None: color = []
# Предусловия.
assert len(forbidden) == 0 or len(forbidden) == len(graph)
assert len(color) == 0 or len(color) == len(graph)
if len(forbidden) == 0:
forbidden = [frozenset()]*len(graph)
#...
Передав раскраску color, можно задать желаемые цвета, а алгоритм разрешит конфликты, если они есть. Если color уже содержит правильную раскраску, то она и будет возвращена функцией coloring. Массив forbidden позволяет запретить раскрашивать какие-то вершины в какие-то цвета: forbidden[v] есть множество запрещённых цветов (числовых меток) для вершины с индексом v.
Всё, что описано ниже, определено внутри функции coloring.
Если пользователь не передал некую начальную раскраску color, то построим её в два цвета поиском в глубину.
# Раскраска в два цвета поиском в глубину.
def coloring2():
color2 = [0]*len(graph)
def dfsColoring2(u, c=1):
if color2[u] == 0:
for d in range(c, len(graph)+1):
if d not in forbidden[u]:
color2[u] = d
break
c = 3 - c
for v in graph[u]:
dfsColoring2(v, c)
for start in range(0, len(graph)):
dfsColoring2(start)
return color2
# Построить начальную раскраску, если требуется.
if len(color) == 0:
color = coloring2()
Теперь собственно алгоритм. Он заключается в повторении пары действий: выявлении конфликтов цветов (listConflicts) и разрешении конфликтов цветов (resolveConflicts), пока все конфликты не будут разрешены.
# Перечислить текущие конфликты цветов.
def listConflicts():
conflicts = []
for u in range(0, len(graph)):
nc = [color[v] for v in graph[u]]
conflict_rank = nc.count(color[u])
if conflict_rank > 0:
nc = frozenset(nc) | forbidden[u]
new_color = max(nc) + 1
for c in range(1, new_color-1):
if c not in nc:
new_color = c
break
conflict = (conflict_rank, new_color, u)
conflicts.append(conflict)
conflicts.sort(
key=lambda c: (c[0], -c[1], c[2]), reverse=True)
return conflicts
# Разрешить конфликты цветов (потенциально не все).
def resolveConflicts(conflicts):
closed = set()
for _, new_color, u in conflicts:
if u in closed:
continue
color[u] = new_color
closed |= set(graph[u])
# Собственно алгоритм: начиная с некоторой раскраски,
# повторять обнаружение и разрешение конфликтов,
# пока список конфликтов не опустеет.
while True:
conflicts = listConflicts()
if len(conflicts) == 0:
return color
resolveConflicts(conflicts)
Цвет 0 не используется.
Пример:
g = ((1,2), (0,2), (0,1,3,6), (2,4,5), (3,5,6), (3,4), (2,4)) c = coloring(g) print(c) > [1, 2, 3, 2, 1, 3, 2]
Раскрашенный граф:
Вычисление массы молекулы по формуле вещества с помощью Python
Я привык писать на C++, и та задача, решение которой я собираюсь здесь продемонстрировать, сначала была мной решена на C++. Однако Python позволяет решить её с помощью намного более короткой программы (думаю, ряд других популярных языков в этом плане не хуже, но речь сейчас не о них). Это первая запись в моём блоге с использованием Python. Шапочное знакомство с этим языком у меня состоялось много лет назад, но пользоваться им не доводилось. Недавно я решил использовать его на занятиях, в первую очередь, из-за пакета модулей SciPy. В качестве первой задачки для себя я взял задачу, для которой достаточно стандартной функциональности.
Задача. Дана строка, содержащая формулу химического вещества. Требуется найти массу молекулы этого вещества в атомных единицах массы. Формула может содержать названия элементов вида K (одна заглавная латинская буква) или Mg (заглавная + строчная буква), круглые скобки (химики также используют и квадратные скобки, но упростим задачу), натуральные числа (количества атомов и групп атомов). Пример: «Ca (OH)2» (пробелы должны игнорироваться), масса равна сумме масс Ca и удвоенной суммы масс O и H.
Исходные данные: словарь (или файл) с массами элементов.
Первая идея была парсить формулу «руками» подряд, пропуская пробельные символы, выявляя названия элементов и числа, а скобочные формы обрабатывая рекурсивно. Подобная программа на C++ (с комментариями, циклом чтения в main и функцией чтения файла с массами элементов) вылилась примерно в 200 строк кода.
Вторая идея была использовать регулярное выражение для выявления частей формулы. Стандартная библиотека C++ включает поддержку регулярных выражений.
/// Break-up formula into tokens.
vector<string> tokenize_formula(const string &formula)
{
// Regex object used for tokenizing formulae.
static const regex tokens("[0-9]+|[A-Z][a-z]?|\\(|\\)");
vector<string> result;
sregex_iterator
from(begin(formula), end(formula), tokens), to;
for_each(from, to,
[&](auto &match) { result.push_back(match.str()); });
return result;
}
Дальше всё примерно так же, как при выделении лексем «руками». Такой вариант стал короче почти вдвое, но обзавёлся и важным недостатком — ошибки игнорировались, например, формула «N aHCO3» проходила, как если бы было написано «NHCO3», что неприятно.
Python позволяет записать то же самое ещё короче, но в нём есть возможность ещё сверх того ужать программу, не прибегая при этом к сторонним библиотекам. Причём, если в формуле есть ошибки, то мы это увидим. Впрочем, для начала я приведу вариант на основе предыдущего регэкспа, но уже с отловом ошибок (однако без чтения файла и main). Предполагается, что массы элементов заданы в словаре elements, скажем, так:
elements = {
'H' : 1.008,
'C' : 12.01,
'N' : 14.007,
'O' : 16,
'Na': 22.99,
'Mg': 24.306,
'P' : 30.974,
'S' : 32.068,
'Cl': 35.45,
'K' : 39.098,
'Ca': 40.078
}
Итак, код парсера, используещего методы findall и split:
import re
chemass_tokens = re.compile(r'[0-9]+|[A-Z][a-z]?|\(|\)|\[|\]')
def chemass(formula):
"""
Формула -- это строка, составленная из знаков элементов,
количеств и скобок вроде 'H2O' или 'Ca (OH)2'.
Пробелы и всё прочее игнорируется (о выброшенном выводится сообщение).
@return: масса
"""
# Получить список токенов:
tokens = chemass_tokens.findall(formula)
m, l = do_chemass(tokens)
# То, что не попало в токены, можно получить,
# разбив формулу на части, разделённые токенами:
unparsed = chemass_tokens.split(formula)
# split возвращает кучу пустых строк, а также пробелы -- выкинем их.
unparsed = [s for s in unparsed if s != '' and not str.isspace(s)]
if len(unparsed) > 0:
print('Chemass ignored the following formula parts:')
print(unparsed)
return m
def do_chemass(l):
"""
Отдельная функция нужна для рекурсивной обработки вложенных скобочных форм.
l -- список строк, где каждая строка --
либо имя элемента, либо число, либо скобка.
"""
mass = 0
cm = 0
while l:
if str.isdecimal(l[0]):
cm *= int(l[0])
elif l[0] == '(' or l[0] == '[':
mass += cm
cm, l = do_chemass(l[1:])
continue # чтобы не удалить голову списка l.
elif l[0] == ')' or l[0] == ']':
del l[0]
break
elif l[0] not in elements: # сообщить о неизвестном элементе.
print('Chemass: '+l[0]+' is unknown element, ignored.')
else:
mass += cm
cm = elements[l[0]]
del l[0] # удалить голову списка l.
mass += cm
return mass, l
Ну, а теперь, «коронный номер». В Python есть встроенная функция eval, вычисляющая значение выражения (программы) на Python… Преобразуем-ка формулу в выражение, в духе ‘Ca(OH)2’ → ‘Ca+(O+H)*2’ и вычислим его! Для этого можно использовать метод регэкспа sub (подстановка по образцу). Далее привожу полученный код:
import re
chemass_names = re.compile('([A-Z][a-z]?)')
chemass_open = re.compile('(\()')
chemass_num = re.compile('([0-9]+)')
def chemass(formula):
"""
Формула -- это строка, составленная из знаков элементов,
количеств и скобок вроде 'H2O' или 'Ca (OH)2'.
@return: масса
"""
return eval(chemass_formula(formula))
def chemass_formula(formula):
"""
Функция, преобразующая строковую формулу
к выражению на Python, вычисляющему массу.
"""
return chemass_num.sub(r'*\1',
chemass_names.sub(r'+elements["\1"]',
chemass_open.sub(r'+\1', formula)))
Это всего 20 строк. Если в формуле есть ошибки, о них сообщит сам парсер Python’а. Да, eval нельзя использовать в некоторых случаях, например, из соображений безопасности, но если это скрипт для личного пользования «по-быстрому», то это может быть очень удобно.
Addendum. Я использовал предварительную поддержку C++17 (g++ 7.2), и меня неприятно удивило отсутствие многих очевидных функций для работы со string_view. Например, его нельзя передать в конструктор fstream или в функцию stoi. Да, всегда можно явно сконвертировать в объект string, но это противоречит цели использования string_view: избежать создания лишних строк.
evetro 