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つの同一のループがありますが、これらは同一のリストではありません。そのような重複を特定し、1つを除いてすべて削除したいと思います（どちらでも構いません）。

次のように、複数のループが重複している場合があることに注意してください。

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

itertoolsを調べてみました：

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

しかし、それは助けにはならず、とにかくこれが適切であるかどうかは100％確信していません。何か案は？私はPython2.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)])

[編集：この単純な正規化は、各頂点がパス内で1回しかアクセスできない場合にのみ機能することに注意してください。]

于 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ます。2つのセットが等しい場合、ループが重複しています。ただし、ループ内のノードの順序が失われていますが、それは重要ですか？

于 2012-09-13T14:10:14.423 に答える