Разделите граф так, чтобы каждый тип узла появлялся в каждом разделе только один раз с как можно меньшим количеством сок ⇐ Python

[Anonymous]

У меня есть таблица в BigQuery, представляющая края графа. Каждый узел графа имеет тип. Каждое ребро имеет свойство Create_at. Теперь я хочу разрезать граф на подкомпоненты. Ни один подкомпонент не имеет более одного узла выбранного типа (A). Я хочу сделать это с как можно меньшим количеством надрезов по краям. Предпочитаю обрезать более молодые края, а не старые.

• Каков эффективный способ сделать это?
• Можно ли это можно сделать в SQL с помощью рекурсии?
• Какой тип алгоритма мне нужно использовать?

Это является примером структуры таблицы.
Ни один подкомпонент не имеет более одного узла типа A в результирующем подкомпоненте.


Узлы:



node_id
node_type




1
A


2
B


3
A


4< /td>
C


5
A

6
B



Края
< table class="s-table">


edge_id
source_node
target_node
created_at
source_type
target_type
< /tr>



1
14
01.05.2024 20:43:00
A
C


2
2
< td>6
2024-05-02 06:43:00
B
B


3
3
6< /td>
03.05.2024 08:43:00
A
B


4
6
42024-05-04 19:43:00
B
C


5
4
5
< td>2024-05-05 21:43:00
C
A


перевернутые края сверху…







6< /td>
4
1
2024-05-01 20:43:00
C
A


76
2
2024-05-02 06:43:00
B
B


8
< td>6
3
03.05.2024 08:43:00
B
A


9
4< /td>
6
04.05.2024 19:43:00
C
B


10
54
05.05.2024 21:43:00
A
C



Это то, что я сейчас делаю, чтобы получить идентификаторы компонентов. Сейчас я застрял в том, как разрезать эти компоненты на подкомпоненты.

Код: Выделить всё

with recursive
connected_components as (
select
source_node as node_id,
source_node as front,
target_node,
source_type,
target_type,
1 as depth,
[source_node] as visited_nodes
from edges
union all
select
cc.node_id,
e.source_node,
e.target_node as front,
e.source_type,
e.target_type,
cc.depth + 1 as depth,
array_concat(cc.visited_nodes, [e.target_node]) as visited_nodes
from edges as e
inner join connected_components as cc on e.source_node = cc.target_node
where cc.depth < 50 and not e.target_node in unnest(cc.visited_nodes)
),

components as (
select node_id, min(front) as component_id from connected_components group by 1
)

select * from components

В результате я хотел бы иметь аналогичную таблицу поиска, но для поиска идентификатора подкомпонента для каждого узла.
Если это невозможно через sql также можно решить с помощью Python, а затем повторно импортировать таблицу поиска для компонентов в Bigquery.
Итак, учитывая приведенные выше данные, я ожидаю получить следующую таблицу:



id
comComponent_id
comComponent_id_from_pic (только для справки)


< tbody>

1
1
c2
< /tr>

4
1
c2


5
5
c1


6
2
c3


2
2
c3

3
2
c3




Подробнее здесь: https://stackoverflow.com/questions/785 ... artition-w