查找通过图中特定节点的路径

Question

问题是：给定一个约束条件和一个图，我能否找到一种有效的方法来验证我是否能够满足它？

我有 graph/trees 喜欢的论文：

我对每个图都有特定的约束，例如“UUB？”为一个）。 约束询问图中是否有路径通过约束中指定的每个字母。

对于约束“UUB？”我们想要一条至少通过两个 U 和一个 B 的路径。对于第一个图“UUB？”路径 U->B->U 是可能的。 “红黑军团？”这是不可能的，因为其中一个 B 与 R 在同一层上，你不能同时拥有两者。我没有找到任何有效的方法来检查是否可以满足约束..

约束精度：约束包含的字母不能多于层数。约束的顺序不相关（UBB 与 BUB 和 BBU 相同）。

图表精度：这些图表是有方向的，每一层（列）都完全连接到下一层。它们最多可以有 5 层（列）和 5 行（U,B,R,G,W）。

它们可以像向量一样表示（分别）：

A)
U 1 0 1
B 1 1 0
R 1 0 0

B)
U 1 0 1 0
B 1 1 0 1
R 1 0 1 0
G 1 1 0 0

C)
U 1 0 1 0 0
B 1 1 0 1 0
R 1 0 1 0 0
G 1 1 0 0 0
W 0 0 1 0 1

算法精度：此验证将在 Monte Carlo 模拟数百万步的每一步进行，它需要尽可能快（这意味着我可以' t 提取所有路径并检查它们是否包含所需的节点..)

我找到了检查图形是否不能满足约束的简单方法，但相反的方法似乎很难（至少对我来说，我远不是图形专家，但我可以理解关键概念）。

感谢您的阅读和帮助！

Answer 1

您可以使用递归生成器函数，在每次调用时构建可能的路径，检查运行组合的字母频率与可能路径的字母频率：

from collections import Counter
def check_paths(d, p, c=[], f={}):
    if not d and any(all(j in i and i[j] == k for j, k in f.items()) for i in p):
       yield c #produce a path if all the layers have been examined and all the letter frequencies from the path match a possible path
    elif d:
       for x in d[0]:
          _c = Counter(c+[x])
          #check if the current path, with the addition of a new letter, is below or equals the frequency threshold of any of the target paths
          if any(all(j in i and i[j] >= k for j, k in _c.items()) for i in p):
              yield from check_paths(d[1:], p, c=c+[x], f=_c)

l = ['U', 'B', 'R', 'G', 'W']
def path_exists(m, p):
   v = [[j for j, k in zip(l, i) if k] for i in zip(*m)]
   return next(check_paths(v, [Counter(i) for i in p]), None) is not None

print(path_exists([[1, 0, 1], [1, 1, 0], [1, 0, 0]], ['UUB', 'RBB', 'UBR']))
print(path_exists([[1, 0, 1, 0], [1, 1, 0, 1], [1, 0, 1, 0], [1, 1, 0, 0]], ['UBBB', 'RGRR', 'UBRG']))
print(path_exists([[1, 0, 1, 0, 0], [1, 1, 0, 1, 0], [1, 0, 1, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 1]], ['UBRGW', 'RGRGG', 'WWRUB']))

输出：

True
True
True

查找通过图中特定节点的路径

Find a path passing through specific nodes in a graph

python

graph