Вы можете сделать это с помощью множества типичных преобразований графиков. Прежде чем погрузиться в код, мы работаем с направленным ациклическим c графом с одним исходным узлом (то есть узлом без входящих ребер) в исходном фрейме данных. Эти свойства немного упрощают дело и гарантируют, что мы сможем создать уникальное дерево, как показано в желаемом выводе.
Плоским фреймворком данных не так уж и легко управлять как графиком, поэтому первым шагом, который я сделал, был чтобы превратить его в список смежности .
Затем нужно выполнить несколько подготовительных шагов:
- Найдите исходный узел (хотя я использовал общий c графическая функция, которая обрабатывает более одного источника, мы гарантируем, что будет только один источник, поэтому мы возьмем единственный элемент из возвращенного набора). Единственный узел-источник станет root нового дерева.
- Запустите функцию для извлечения всех путей в DAG, начиная с источника.
- Создайте dict, который отображает узел
- Создайте словарь переименования, который позволяет нам отслеживать, какие узлы были переименованы.
Построив эти структуры, выполните итерацию все возможные пути в графе для построения перемаркированного графа, форматирование узлов с несколькими входящими ребрами в соответствии с вашим spe c (список узлов с обратным путем) и сохранение новых имен в слове переименования.
Наконец, отсортируйте сплющенную версию этого перемаркированного графика и выгрузите ее во фрейм данных результата.
Вот код:
import pandas as pd
from collections import defaultdict
def find_source_nodes(graph):
sources = set(graph)
for neighbors in graph.values():
sources = sources - neighbors
return sources
def count_incoming_edges(graph):
counts = defaultdict(int)
for neighbors in graph.values():
for neighbor in neighbors:
counts[neighbor] += 1
return counts
def find_all_paths_in_dag(graph, src, path=[]):
path.append(src)
if src in graph and graph[src]:
for neighbor in graph[src]:
yield from find_all_paths_in_dag(graph, neighbor, path)
else:
yield path[:]
path.pop()
def flatten_adjacency_list(adj_list):
flat_graph = []
for parent, children in adj_list.items():
flat_graph.extend([(parent, child) for child in children])
return flat_graph
def relabel_dag(graph, root):
relabeled_graph = defaultdict(set)
all_paths = find_all_paths_in_dag(graph, root)
incoming_edge_counts = count_incoming_edges(graph)
renamed = {k: k for k in graph}
for path in all_paths:
for src, dst, i in zip(path, path[1:], range(len(path) - 1)):
if incoming_edge_counts[dst] > 1:
renamed[dst] = dst = f"{dst}_{''.join(path[:i+1][::-1])}"
relabeled_graph[renamed[src]].add(dst)
return relabeled_graph
if __name__ == "__main__":
df = pd.DataFrame(columns=["Parent", "Child"])
df["Parent"] = ["A", "A", "A", "B", "B", "B", "C", "C", "F", "G", "G"]
df["Child"] = ["B", "C", "E", "D", "E", "F", "F", "G", "H", "H", "I"]
graph = defaultdict(set)
for parent, child in zip(df["Parent"], df["Child"]):
graph[parent].add(child)
root = next(iter(find_source_nodes(graph)))
relabeled_tree = relabel_dag(graph, root)
flat_relabeled_tree = sorted(flatten_adjacency_list(relabeled_tree))
relabeled_df = pd.DataFrame(flat_relabeled_tree, columns=["Parent", "Child"])
print(relabeled_df)
Вывод:
Parent Child
0 A B
1 A C
2 A E_A
3 B D
4 B E_BA
5 B F_BA
6 C F_CA
7 C G
8 F_BA H_FBA
9 F_CA H_FCA
10 G H_GCA
11 G I