об одном планаризаторе графов (деревьев)

все знают что дерево — эффективная структура для опреаций поиска в различных массивах данных.

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) будет отдельная заметка.