@toddbarry

Можно ли реализовать сдвиг узлов графа в базе данных одним запросом?

У меня есть информация, представляемая ввиде некоторого графа. В базе хранятся узлы этого графа с их id и координатами на сетке и грани графа, указывающие, как соединены узлы между собой. Декларация моделей выглядит следующим образом:
class Nodes(db.Model):
    __tablename__ = 'nodes'

    id = db.Column(db.Integer, primary_key=True)
    grid_y = db.Column(db.Integer)
    grid_x = db.Column(db.Integer)

    # _grid_idx = db.Index('grid_idx',  'grid_y', 'grid_x', unique=True)

    def __init__(self, *args, **kwargs):
        super(Nodes, self).__init__(*args, **kwargs)


class Edges(db.Model):
    __tablename__ = 'edges'

    id = db.Column(db.Integer, primary_key=True)
    source = db.Column(db.Integer, db.ForeignKey('nodes.id'))
    target = db.Column(db.Integer, db.ForeignKey('nodes.id'))

    _edge_idx = db.Index('edge_idx', 'source', 'target', unique=True)

    def __init__(self, *args, **kwargs):
        super(Edges, self).__init__(*args, **kwargs)


grid_x и grid_y - позиции по оси x и y узллов на сетке

Скажем, информация в базе выглядит слеюущим образом:
5c61a2a8b0556405945283.png

В определенный момент может возникнуть необходимость сдвинуть один из узлов вниз - например пусть это будет узел 1
Вместе с ним должны сдвинуться все его потомки, то есть узлы 2,3,4,5,6. Однако при сдвиге потомков вниз - они попадают на позиции, в которых узлы уже имеются - возникают конфликты. Так узел 2 смещается туда, гже уже стоит узел 7, узел 5 переходит на место имеющегося узла 8, 6 переходит к 10, 4 к 12.
Эти конфликты должны решаться следующим образом - потомки должны сдвигаться вниз в любом случае, а узлы, которые входят с ними в конфликт должны сдвигаться вбок. Причем вправо они должны двигаться или влево - зависит от того, правее или левее от конфликтующих узлов находится их непостредственный родитель (такой всегда имеется).
Таким образом непосредственным родителем узла 7 (который конфликтует с двигающимся вниз узлом 2) является узел 23 - он находится левее узла 7 - следовательно узел 7 должен съезжать влево. При этом позиция, на которую сдвигается узел 7 уже занята узлом 24. Конфликт между 7 и 24 можно решить сдвинув 24 в ту же сторону, куда двигался 7 - аналогично с конфликтом между 24 и 25. (На самом деле непосредственных родителей может быть больше одного. В этой ситуации я думаю, что не имеет большого значения, какой из них использовать для определения направления движения)

То есть в итоге должно получиться что-то вроде этого:
5c61a5b00f3db955627359.png

Я пытаюсь реализовать это сложным рекурсивным алгоритмом следующим образом:

async def move_successors(node_id):
	descendants = db.select([Nodes]).where(Nodes.id == node_id).cte(recursive=True) # выбираем узел,  который требуется сдвинуть вниз. В нашем случае в примере выше это 1

	parents = descendants.alias()
	edges = Edges.alias()
	descendants = descendants.union(db.select([Nodes]).where(edges.source == parents.c.id).where(Nodes.id == edges.target)) # Рекурсивно находим всех потомков узла 1
	query = db.select([descendants]).select_from(descendants).distinct('id')
	alias = query.alias()
	nodes=Nodes.alias()
	edge=Edges.alias()
	moving = db.select([nodes]).where(~nodes.id.in_(db.select([alias.c.id]))).where(nodes.id==edge.c.target).where(nodes.grid_y==alias.c.grid_y+1).where(nodes.grid_x==alias.c.grid_x).cte(recursive=True) #находим все конфликтующие узлы - в нашем случае это 7, 8, 10, 12
	prev_mov = moving.alias()
	moving = moving.union(db.select([Nodes]).where(~Nodes.id.in_(db.select([alias.c.id]))).where(Nodes.grid_y==prev_mov.c.grid_y).where(Nodes.grid_x==prev_mov.c.grid_x+db.func.sign(prev_mov.c.grid_x-edge.c.source))) # рекурсивно выбираем узлы,  которые требуется сдвигать вбок - например это 24, 25
	moving = db.select([moving]).select_from(moving).distinct('id')
	m=moving.alias()

	mov = Nodes.update.values(grid_x=Nodes.grid_x+db.func.sign(m.c.grid_x-edge.c.source)).where(Nodes.id==m.c.id).where(Nodes.grid_y==m.c.grid_y).where(nodes.c.id==edge.c.target) сдвигаем все найденные конфликтующие узлы в нужные стороны
	await mov.gino.all()


Однако алгоритм работает не совсем верно. например узел 8 (все остальные узлы, кажется, двигаются верно), хотя он и должен двигаться влево - почему-то сдвигается вправо. Кроме того реализация получилась запутанной.

Так же в модели Nodes можно видеть закомментированную строку, говорящую о том, что комбинации grid_x, grid_y должны быть уникальными для каждого узла. Закоментировать ее пришлось ввиду того что update выдавал ошибки связанные с уникальностью - при изменении координат узлов очевидно возникают конфликты, поскольку update происходит последовательно для набора выбранных узлов

+ ко всему сюда не получается добавить update для сдвига узлов 1,2,3,4,5,6 вниз, одним запросом получилось реализовать (довольно коряво) только сдвиг конфликтующих узлов в бока. А двигать элементы вниз придется отдельным запросом уже после

Прошу помочь с реализацией алгоритма. Хотелось бы выполнять все необходимые действия одним запросом к базе данных. Только вот не понятно, как такое сделать.
Я использую Gino, однако идея реализации на sqlalchemy, думаю, тоже подойдет - они довольно похожи. Зарнее благодарю
  • Вопрос задан
  • 117 просмотров
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы