python - 在python的链接列表中获取最长的链接

我有一个边缘列表，如下所示：

edges_1 = ['a::b::c', 'a::b', 'a', 'a::d','a::d::e', 'a::d::e::f']
edges_2 = ['a', 'b', 'c']

我试图编写一个函数，返回最长的链接对于上述情况，将返回

['a::b::c','a::d::e::f']

第二个案子

['a', 'b', 'c']

我的想法是使用networkx构建一个图表，然后遍历最长的序列。但我想知道是否还有另一种数据结构或方法可以解决这个问题。

最佳答案

考虑到你在评论中的注释，我修改了代码。
这假设图是DAG，目标是消除列表中其他图的子序列。
我们不必查看每个序列的长度，只需丢弃其他序列的子集为此，我们可以使用str子集运算符。

print(f"Initial list: {edges_1}")
keepers = []

for edge in edges_1:
    other_edges = edges_1[:]
    other_edges.remove(edge)
    print(f"Test {edge} against {other_edges}")
    for rest in other_edges:
        if edge in rest:
            # Discard any edges that are subsets an an edge in `other_edges`
            print(f"Found match {edge} -> {rest}")
            break
    else:
        # If the edge hasn't been discarded, it is a "longest edge"
        keepers.append(edge)
        print(f"No greater matches found for {edge}")

print(f"The longest edges: {keepers}")

这段代码不是最有效也不是最干净的，但是它强调了解决问题的基本机制。
旧答案：解决了没有更多来自OP的描述
如果始终可以假设顶点之间的边由“：：”表示，则可以使用一些简单的字符串处理来获取每个序列的长度。
此解决方案假设您始终需要最长的两个序列。

edges_1 = ['a::b::c', 'a::b', 'a', 'a::d','a::d::e', 'a::d::e::f']
edges_2 = ['a', 'b']

def print_longest_two_sequences(edges):
    links = [edge.split("::") for edge in edges]
    links.sort(key=len, reverse=True)
    links = ["::".join(edge) for edge in links]
    print(links[:2])

print_longest_two_sequences(edges_1)
print_longest_two_sequences(edges_2)