Я пишу программное обеспечение для характеристики химических структур на основе их топологии графа и химических элементов каждого атома. Они должны быть однозначно отсортированы, чтобы оценить, равны ли два графика связей. Я представляю график массивом значений и массивом пар индексов в первом массиве, например,
vertices = {"C", "H", "H", "H", "H"};
edges = {{0, 1}, {0, 2}, {0, 3}, {0, 4}};
График сортируется по первым значениям вершин (позиция в периодической таблице), а вторымпо краям. Каждое ребро сначала отображается с более низким значением индекса, а ребра упорядочены лексикографически на основе 1) левого индекса и 2) правого индекса. Таким образом, упорядоченная форма молекулы метана выше:
vertices = {"H", "H", "H", "H", "C"};
edges = {{0, 4}, {1, 4}, {2, 4}, {3, 4}};
. Она сортируется, потому что замена двух вершин, перемаркировка ребер, ссылающихся на них, и приближение ребер, либо оставит представление неизменным, либо сделает его меньше. упорядоченный. Следуя этому соглашению, достаточно легко сравнивать два порядка графа, чтобы оценить, какой из них лучше, но придумать эффективный алгоритм сортировки сложнее, чем кажется, потому что каждый перестановка вершин приводит к перемаркировке ребер, а затемпутем возможной замены первого и второго элемента в каждом перемаркированном ребре и обращения к списку ребер. До сих пор я использовал метод грубой силы вхождения через все перестановки одинаковых вершин, но, поскольку он масштабируется с факториалом количества типов вершин, он попадает в вычислительную кирпичную стену уже для скромного числа вершин того же типа.
Мне кажется, что кто-то, должно быть, решил эту проблему, но все, что я могу найти при поиске решения, это топологический тип DAG, что является совершенно другой проблемой, и очень специализированные решения на основе органической химии, которыеслишком тяжелы для предметно-ориентированных знаний, которые кажутся ненужными и непродуктивными для моих целей.