如何从图数据中标记一个周期中的初始顶点的节点 [英] How can I label a node that is the initial vertex in a cycle from graph data

问题描述

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

I need to implement an algorithm such that in a collection of unique and ordered graph edges, I can find a cyclic node.

例如对于 a-> b，b-> c，c-> a ，则'a'是一个循环节点，因此我想在此边缘用'a @'进行注释，并为其他人使用simillar.

E.g. for a ->b, b->c, c->a, then 'a' is a cyclic node and thus I want to annotate it in this edge with 'a@' and simillar for others.

我使用以下示例数据:

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中实现呢?

How can I achieve this in 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简单循环(无子循环)之类的东西，我也需要像上面这样返回的数据

It seems to work for cycles but it also takes into account strong connected components that are not cycles.. So I am looking for something similar like networkx simple cycles (no subcycles), also I need data returned in this way like above.

推荐答案

此解决方案将构建它在边缘列表中遇到的所有可能路径，因为我们实际上并不知道循环从何处开始.如果图形很大，它还会修剪它创建的路径列表，以防止某些内存膨胀.这很丑陋，但可以根据您的需求进行工作.

This solution builds all possible paths that it encounters in the edge list, since we don't really know where a cycle starts. It also prunes the path list that it creates to prevent some memory bloat if your graph is large. It is ugly but works based on your needs.

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')]
"""

这篇关于如何从图数据中标记一个周期中的初始顶点的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！