在元组列表中查找循环路线

Question

我有一个包含源和目标的元组列表我需要确保没有“循环路线”

例如：

[(1,2), (3,4), (2,3)]. is OK

但是

[(1,2), (3,4), (2,3), (3,1)].

不行，因为我们可以从 1 → 2 → 3 → 1

我怀旧了，想起了我的计算机科学学位，所以我想到了图数据结构。不幸的是，我无法使用 python 为它找到一个好的实现，并且我发现谷歌搜索（以及此处在 Whosebug 上）的所有示例仅用于查找最短路径。

有什么想法可以实现吗？

Answer 1

这是 Python 中的一个实现，效果很好（在 Java 和 C++ 中也可用，但我只尝试了第一种情况）。 https://www.techiedelight.com/check-given-digraph-dag-directed-acyclic-graph-not/

Answer 2

如果我没理解错，那么问题就是你什么时候可以到达起点。为了简单明了，我会从一个普通的 python 开始。显而易见的蛮力解决方案是检查数据中出现的每个来源的所有可能目的地。当然，您需要稍微组织一下数据。然后它只是一个链接。下面的代码实现了这种方法。

def get_all_sources(data):

    ans = dict()
    for src, dst in data:
        ans.setdefault(src, set()).add(dst)

    return ans


def get_all_possible_destinations(src, all_src, ans=None):

    ans = set() if ans is None else ans
    for dst in all_src.get(src, set()):
        if dst in ans:
            continue
        ans.add(dst)
        get_all_possible_destinations(dst, all_src, ans)

    return ans


def pipeline_source_by_source(data):

    all_src = get_all_sources(data)

    for src in all_src:
        all_possible_destiations = get_all_possible_destinations(src, all_src)
        if src in all_possible_destiations:
            print(f"found problem: {src} -> {src}")
            break
    else:
        print('no problems found')


if __name__ == '__main__':

    data_list = [
        [(1, 2)],
        [(1, 2), (2, 3)],
        [(1, 2), (3, 4), (2, 3)],
        [(1, 2), (3, 4), (2, 3), (3, 1)],
        [(5, 6), (5, 7), (5, 8), (5, 9), (9, 10), (10, 5)],
        [(5, 6), (5, 7), (5, 8), (5, 9), (9, 10), (10, 15)]
    ]

    for idx, data in enumerate(data_list):
        print(idx)
        pipeline_source_by_source(data)

结果：

0
no problems found
1
no problems found
2
no problems found
3
found problem: 1 -> 1
4
found problem: 5 -> 5
5
no problems found

Answer 3

这有点晚了，但给出了更短的解决方案（更少 Python 行）。基本原理是建立一个可从源直接到达的目的地字典（由源索引）。然后从任何来源浏览可能的目的地，并将任何已经看到的目的地存储在一个集合中。一旦看到新目的地，就会出现循环。

Python 代码可以是：

def build_dict(lst):
    d = dict()
    for src, dst in lst:
        if src not in d:
            d[src] = []
        d[src].append(dst)
    return d

def dict_loops(d, start=None, seen=None):
    if start is None:
        return any(dict_loops(d, elt, None) for elt in d.keys())
    if start not in d:
        return False
    if seen is None:
        seen = {start}
    for hop in d[start]:
        if hop in seen:
            return True
        if dict_loops(d, hop, seen):
            return True
    return False

def lst_loops(lst):
    return dict_loops(build_dict(lst))

它给出了预期的结果：

>>> lst_loops([(1,2), (3,4), (2,3)])
False
>>> lst_loops([(1,2), (3,4), (2,3), (3,1)])
True
>>>

表示第一个列表中没有循环，第二个列表中至少有一个循环。

Answer 4

您可以使用递归生成器函数：

def no_cycles(graph):
  def has_cycles(n, s = []):
     if n in s:
        yield (False, n)
     else:
        yield (True, n)
        yield from [i for a, b in graph for i in has_cycles(b, s+[n]) if a == n]
  return all(a for a, _ in has_cycles(graph[0][0]))

graphs = [[(1, 2)], [(1, 2), (2, 3)], [(1, 2), (3, 4), (2, 3)], [(1, 2), (3, 4), (2, 3), (3, 1)], [(5, 6), (5, 7), (5, 8), (5, 9), (9, 10), (10, 5)], [(5, 6), (5, 7), (5, 8), (5, 9), (9, 10), (10, 15)]]
result = [no_cycles(i) for i in graphs]

输出：

[True, True, True, False, False, True]

在元组列表中查找循环路线

Find round routes in a list of tuples

python

python-3.x

data-structures

computer-science