时间戳

首页 > 解决方案 > 如何从图形数据中标记作为循环中初始顶点的节点

python - 如何从图形数据中标记作为循环中初始顶点的节点

问题描述

我需要实现一种算法，以便在一组唯一且有序的图边中，我可以找到一个循环节点。

例如 for a ->b, b->c, c->a, then'a'是一个循环节点，因此我想在这条边上注释它，'a@'并且对其他人类似。

作为示例数据，我使用它：

a = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'a'), ('a', 'e'), ('e', 'a'), ('f', 'e')]

那么这将变成：

[('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'a@'), ('a', 'e'), ('e', 'a@'), ('f', 'e')]

我怎样才能在python中实现这一点？

这是我尝试过的：

collection = {}
data, result = [], []
for i, j in a:
    if i in collection.keys():
        collection[i].append(j)
    else:
        collection[i] = [j]
    if j in collection.keys():
        for item in range(len(collection[i])):
            if collection[i][item] == j:
                nr += 1
                collection[i][item] = j + '@'

print(collection)

它似乎适用于循环，但它也考虑了不是循环的强连接组件。所以我正在寻找类似 networkx 简单循环（无子循环）的东西，我也需要像上面这样以这种方式返回数据。

标签： pythonalgorithm

解决方案

该解决方案构建了它在边缘列表中遇到的所有可能路径，因为我们并不真正知道循环从哪里开始。如果您的图表很大，它还会修剪它创建的路径列表以防止一些内存膨胀。它很丑陋，但可以根据您的需要工作。

a = [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'a'), ('a', 'e'), ('e', 'a'), ('f', 'e')]

annotated = []
paths = []
for edge in a:
    new_paths = []
    paths.append(''.join(edge))
    annotated.append(edge)
    cycle = ''
    for path in paths[:]:
        if path.endswith(edge[0]):
            if path.startswith(edge[1]):
                annotated[-1] = (annotated[-1][0], annotated[-1][1]+'@')
                cycle = path + edge[1]
            else:
                new_paths.append(path + edge[1])
        else:
            new_paths.append(path)
    paths = [x for x in new_paths if x not in cycle]
    print(paths)
print(f'Result: {annotated}')

"""
Out:

['ab']
['abc', 'bc']
['abcd', 'bcd', 'cd']
[]
['ae']
[]
['fe']
Result: [('a', 'b'), ('b', 'c'), ('c', 'd'), ('d', 'a@'), ('a', 'e'), ('e', 'a@'), ('f', 'e')]
"""

推荐阅读