0

我正在识别方向图中的循环。我的函数返回一个列表列表，这些列表将节点存储在找到的任何循环中。

例如，在节点连接如下的图中：

(1,2)(2,3)(3,4)(3,5)(5,2)

在 2 - 3 - 5 处发现了一个循环，因此该函数将返回：

[[2,3,5]]

在某些情况下，有多个循环会返回如下内容：

[[2,3,4][6,7,8,9]]

这很好，但是如果图中有多个起点在不同点加入同一个循环，例如在图中：

(1,2)(2,3)(3,4)(3,5)(5,2)(6,3)

两个节点 1 和 6 在不同的点加入同一个循环，这将返回：

[[2,3,5][3,5,2]]

所以这里有两个相同的循环，它们不是相同的列表。我想识别这种重复并删除除一个之外的所有重复（哪个都没有关系）。

请注意，可能存在多个循环的情况，其中一个是重复的，例如：

[[2,3,5][3,5,2][7,8,9,6]]

我试过调查 itertools：

loops.sort()
list(loops for loops,_ in itertools.groupby(loops))

但这无济于事，而且我也不能 100% 确定这是否合适。有任何想法吗？我在 python 2.4 上。谢谢你的帮助。

4

3 回答 3

3

如果您只关心每个循环的元素，而不关心顺序，我会通过对每个循环进行排序来规范化每个循环，然后取集合：

>>> loops = [[2,3,5],[3,5,2],[7,8,9,6]]
>>> set(tuple(sorted(loop)) for loop in loops)
set([(2, 3, 5), (6, 7, 8, 9)])

为了在set此处使用，您需要转换为元组。您可以将元组转换回列表，或将最终集合转换回列表（甚至可能sorted用于获取规范顺序），但您是否真的需要取决于您将使用它做什么。

如果您需要保留路径顺序，我会以不同的方式规范化：

def rotated(l, n):
    return l[n:] + l[:n]

def canonicalize(l):
    m = min(l)
    where = l.index(m)
    return rotated(l, where)

接着

>>> loops = [[2,5,3], [5,3,2], [7,8,6,9]]
>>> set(tuple(canonicalize(loop)) for loop in loops)
set([(2, 5, 3), (6, 9, 7, 8)])

[编辑：请注意，这种简单的规范化仅在每个顶点只能在路径中访问一次时才有效。]

于 2012-09-13T13:56:27.197 回答
1

首先你需要定义什么是相似的，因为它比set：

def is_similar(X,Y):
    n = len(X)
    return len(Y) == n and any( all( X[i] == Y[(i+j)%n] 
                                     for i in range(n) )
                                for j in range(1,n) ) #the 1 here so that identical lists are not similar

区别很重要，因为路径 (1,2,3,4)与路径 (1,3,2,4)不同，它们不对应于同一个循环。

def remove_similars(L):
     new_L = []
     for item in L:
         if not any( is_similar(item, l) for l in new_L ):
             new_L.append(item)
     return new_L
于 2012-09-13T14:12:34.577 回答
0

你可以从你set的每一个列表中取一个。如果两组相等，则您有一个重复的循环。但是，您正在丢失循环中节点的顺序，但这对您有影响吗？

于 2012-09-13T14:10:14.423 回答