У меня есть информация, представляемая ввиде некоторого графа. В базе хранятся узлы этого графа с их 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 узллов на сетке
Скажем, информация в базе выглядит слеюущим образом:
В определенный момент может возникнуть необходимость сдвинуть один из узлов вниз - например пусть это будет узел 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. (На самом деле непосредственных родителей может быть больше одного. В этой ситуации я думаю, что не имеет большого значения, какой из них использовать для определения направления движения)
То есть в итоге должно получиться что-то вроде этого:
Я пытаюсь реализовать это сложным рекурсивным алгоритмом следующим образом:
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, думаю, тоже подойдет - они довольно похожи. Зарнее благодарю
Простой
