об одном планаризаторе графов (деревьев)
все знают что дерево — эффективная структура для опреаций поиска в различных массивах данных.
B-Tree индексы (по структуре дерево) широко используются, скажу по секрету, ВЕЗДЕ. — да, буквально везде они уже есть.
но если ваша основная структура данных — дерево, то чтобы индексировать дерево нужно другое дерево. вот тут то и приходят на помощь R-Tree M-Tree и прочие X-Tree реализации.
мы попробовали решить свою задачу(о которой ниже) и сделали еще один шаг вперед в нелегком деле работы с деревьями. как говорится, построй дом, посади дерево… или наборот ?
будет интересно.
Решаемая задача:
— Есть дерево из узлов (по смыслу похожее на JCR, узлы со свойствами с информацией) с которым работает несколько пользователей, эти пользователи редактируют дерево и его узлы совместно друг с другом
— Пользвателям дерево представляется в виде MindMap — карты/графа где узлы можно сворачивать и разворачивать. Каждый пользователь свернул и развернул узлы по своему и видит дерево по своему, хотя структура дерева и котент узлов у всех должен быть близок одинаковый.
— Пользователь перетаскивает узлы, чтобы перенести их в другое место. т.е. мало расчитать позиции узла исходя из структуры дерева — надо расчитать целевые структуры исходя из позиции в которую перетаскивается узел.
— надо сделать такой планаризатор, который минимизировал бы операции, уведомлял других пользователей.
такой планаризатор мы и сделали.
вот некоторые элементы API
class MindMap(): def isMapExists(map_id): """ True если карта инициализирована """ def createEmpty(self): """ инициализация пустой карты """ def clearMap(self): """ очистка карты (рут тоже сбрасывается) если карты нет, она создается """ def removeMap(self): """ удаление карты """ def nodeCount(self): """ количество узлов в карте """ def getAllNodes(self): """ возвращает все ноды в карте """ def moveNode(self, node_for_move, new_parent=None, child=None, before=False, side=SIDE_AUTO): """ :param new_parent: Новый родитель. Если не указан вставка происходит в рут. Если родитель не меняется, выполняется простой реордеринг :param child: чилд относительно которого происходит вставка (по умолчаню вставляет ПОСЛЕ child), если child не указан, вставляет в конец(before==False) или в начало(before==True) выбранной стороны ( :param before: если == True, то вставка происходит ДО child. :param side: с какой стороны будет поддерево. ПОКА по умолчанию - SIDE_RIGHT, потом будет SIDE_AUTO """ def createNode(self, name, parent=None, child=None, before=False, side=SIDE_AUTO): """ Создает новый узел :param name: пока для теста, чтоб не видеть безликие хеши :param parent: если не указан, узел добавляется в корень :param child: чилд относительно которого происходит вставка (по умолчаню вставляет ПОСЛЕ child), если не указан, вставляет в конец(before==False) или в начало(before==True) :param before: если == True, то вставка происходит ДО child. :param side: с какой стороны будет нод. ПОКА по умолчанию - SIDE_RIGHT, потом будет SIDE_AUTO :return: Node """ def outNode(self, node): """ удалить узел node и все его подузлы """ def setTargetNodeId(self, target_node_id): """ пользователь сменил выделенный нод, setTargetNode ДОЛЖНА ВЫЗЫВАТЬСЯ ПОСЛЕ setViewedRect :param target_node_id: id нода, относительно которого обновляем координаты или None, если его нет """ def setViewedRect(self, rect): """ Пользователь установил/изменил просматриваемую прямоугольную область. :param rect: list - (x, y, w, h) """ def startView(self, rect): """ Юзер начал смотреть карту, делаем обновения, установки viewport итд """ def refresh(self, forceAll=True): """ Принудительное уведомление об размерах/позициях видимых узлов :param forceAll: если True обновляются ректы даже не измененных нодов """ def recalcRects(self): """ Пересчет планаризации, ничего не сбрасывается """ def resetRects(self): """ Пересчет планаризации, сброс размеров узлов и параметров свернутости (все узлы развернуты) """ def copyRectsFromUser(self, other_user_id): """ Пересчет планаризации, размеры узлов и параметры свернутости копируются c другого юзера """ def getNodeIdsInRect(self, rect, start_from=None, max=-1): """ запрос на узлы которые попадают в отображаемый Rect, :param rect: list/tuple - (x1, y1, w, h) :param start_from: Node с которого начинаем поиск, если None - начинаем с корня :param max: ограничение на максимально ожидаемое число узлов return [nodid1, nodeid2, ...], max_reached (найдено нодов больше чем max) """ def getMindMapContext(self, x_inches, y_inches, ignore_node): """ возвращает предпологаемое место в иерархии для вставки нода/поддерева для указаной точки :param x_inches: дюймы, координатная плоскость графа :param y_inches: дюймы, координатная плоскость графа :param ignore_node: Node, который в месте со всеми своими чилдами в поиске не участвует return { 'parent'= Node, 'prev'= Node | None, 'next'= Node | None } """
условно не показаны всякие штуки типа «getRoot» и без того свойственные дереву.
в этой системе есть логика минимизирующая число операций… а также либа может уведомлять внешний мир (PUSH COMET) о изменениях в карте, для этого предназначен специальный интерфейс:
class MindMapServiceInterface(): def startUpdateSerial(self, userid, mapid): print 'startUpdateSerial not implemented' def endUpdateSerial(self, userid, mapid): print 'endUpdateSerial not implemented' def newNodeCoord(self, mapid, userid, parent, node, rect): print 'newNodeCoord not implemented' def nodeInvisible(self, mapid, userid, nodeid): print 'nodeInvisible not implemented' def setViewPort(self, mapid, userid, x, y, w, h): print 'setViewPort not implemented' def setTargetNode(self, mapid, userid, nodeid): print 'setTargetNode not implemented' def nodeDeleted(self, mapid, nodeid): """ вызывать при удалении каждого узла в том числе и вложенных в удаляемый (у нас используется для удалении информации в Инфо Бд узла, иначе она продолжает искаться) """ print 'nodeDeleted not implemented' def nodeCreated(self, mapid, nodeid, userid): """ вызывается при успешном создании узла - пока не используется """ print 'nodeCreated not implemented' def nodeMoved(self, mapid, nodeid, oldParentid, newParentid, oldPrevid, newPrevid, oldNextid, newNextid): """ вызывается после успешного перемещении узла. """ print 'nodeMoved not implemented'
мы имеем например такие реализации: ServiceNull, ServiceDebug, ServiceNormal, ServiceZMQ
еще хочу заметить что вся реализация сделана поверх HDB key-value вся информация хранится в наборе хешей, которые работают O(1) и, сами поимаете, быстрее не может быть ничего…
еще мне удалось сконвертировать реализацию на JS с Python, и получить компактную реализацию, о том как я транслировал (копий сломано штук 5) будет отдельная заметка.
СУП — наша Система Управления Проектами — Блоги разработчиков {КБ ИТ, САТЭК}
13.07.2016 в 14:16[…] Раньше у нас планаризация жила на сервере, как и вся карта, я уже писал об этом чудо планаризаторе. […]