Mail.RuПочтаМой МирОдноклассникиИгрыЗнакомстваНовостиПоискВсе проекты

В какую структуру данных из STL лучше обернуть LSD?

Ученик (85), закрыт 1 год назад
Я хочу представить молекулярное строение известной кислоты LSD ( диэтиламид d-лизергиновой кислоты ) в структуре данных для работы в С++.

В целом, как я вижу картину. Строение молекулы для переноса в код, можно сделать так:
- представить вещ-во в виде графа ( G = <v,>; g - граф, v - вершина, edge - ребро ). Каким образом?

Атом - вершина графа, соединения между атомами - ребра графа ( тут кстати, встает вопрос, что делать с двойными или тройными химическими связями ).

Приведу графическое представление lsd для наглядности, чтобы посмотреть, как на вещ-во, как на граф:


Зная тот факт, что нужно учитывать возможные изменения lsd-кислоты с др. вещ-вом ( хим. структура распадается ). Нужно подобрать хорошую структуру данных, которая бы справлялась за O(log N), пока на ум приходят использование самобалансирующихся деревьев, как: Red-Black деревья ( как раз <map> контейнер из STL ) и В-семейство деревьев.

Но, есть моменты, где мне нужно обходить полностью граф ( каждую вершину ) для визуализации хим. формулы. И тут нужно подкрутить алгоритмы обхода всех вершин графа, как DFS/BFS ( поиски в глубину и ширину ).

В общем, посоветуйте решение. Есть ли какие-нибудь структуры данных для моей цели из STL ( или Boost ), т. к. проект четко будет на С++ только.
Порой идут мысли, что придется имплементировать с нуля структуры данных самому, как и алгоритмы, учитывая сложность задачи.
Дополнен 1 год назад
@Андрей, вещ-во взаимодействует с др. вещ-вом ( в этом случае хим. структура изменяется и могут рваться связи у бензольного кольца, к примеру и тд ). Цели: визуализация точная хим. структуры, передача данных о хим. структуре в виде строки, статистика химическая по атомам вещ-ва.
Дополнен 1 год назад
С матрицей смежности работает только алгоритм Флойда — Уоршелла в плане обхода вершин графа. Такие алгоритмы, как: А* или Алгоритм Дейкстры вообще не используют матрицы.

Помимо, алгоритм Флойда — Уоршелла и будет выполняться за O(n^3) из-за трех вложенных циклов.

По поводу визуализации: не все же алгоритмы рисуются медленно, если еще распараллелить тогда на delta(n) уменьшается скорость отрисовки.

По поводу поиска и передачи строки: поскольку нужно показывать все связи между атомами, т. е. ес-но нужно обходить все вершины графа. А RB-tree, как и алгоритмы B-семейства имеют неплохую асимптоту из-за того, что пропускают элементы, посему это не совсем подходит.
Дополнен 1 год назад
@Vladimir Sh, нет я из Москвы
Лучший ответ
Необходимо более точно описание того, что с этой структурой нужно делать. Что такое "структура распадается"?

Для визуализации можно хоть O(n^3), рисоваться всё равно медленнее будет.
Не очень понимаю, сложность каких алгоритмов должна быть O(logN). Поиск нужной вершины? Тогда RBTree, однозначно (map, как пример) .
Вообще, может помочь создание графа (обычными методами, типа списка инцидентности или матрицы) и дерева к нему, для быстрых алгоритмов.
Остальные ответы
Вы не из Петербурга случайно?
Похожие вопросы