-2

グラフのクラスタリングに（Python経由で）igraphを使用しています。

重み付きエッジを持つツリー（幾何学的グラフの最小全域木）があり、エッジが削除された場合に、重みに2つのコンポーネントの少数の頂点を掛けたものを計算したいと思います。

def sep(graph, e):
    h = copy(graph)
    w = h.es[e]['weight']
    h.delete_edges(e)
    return w * min(h.components().sizes())

# 'graph' is the tree I am dealing with
ss = [sep(graph,x) for x in range(len(graph.es))]

私の質問は次のとおりです。

  1. これはグラフ理論で知られている（そして名前が付けられている）プロパティですか？もしそうなら、それは何ですか？

  2. 上記のように、すべてのエッジについてこれを計算すると、私のコードは非常に非効率的です。グラフが50000のエッジと頂点になると、メモリ消費量が膨大になります。最適化するための提案はありますか？

4

2 に答える 2

1

あなたの最初の質問についてはわかりませんが、2番目の質問については考えているかもしれません。
最小スパニングツリーを扱っているので、1つのエッジについて取得した情報を使用して、それに隣接するエッジに必要なプロパティを計算できます（以降、このプロパティをf（e）と呼びます。エッジe）。
エッジ（A、B）と（B、C）を見てみましょう。を計算するときf(A,B)、グラフからエッジを削除した後、小さい方のコンポーネントがA側のコンポーネントであることがわかったと仮定すると、次のことがわかります。
f(B,C) = (f(A,B) / weight(A,B) + 1) * weight(B,C)
これは、（B、C）が（A、B）に隣接しており、それを削除すると「ほぼ」同じ2つのコンポーネントが得られるためです。唯一の違いは、Bが大きい方のコンポーネントから小さい方のコンポーネントに移動したことです。このようにして、1つのエッジに対して完全な計算（dgeの削除とコンポーネントとそのサイズの検出を含む）を実行し、次にそれに接続されている他のすべてのエッジに対してのみ短い計算を実行できます。
小さい方のコンポーネント（エッジのチェーンに沿って進むにつれて大きくなる）が大きくなる場合には、特に注意する必要があります。

更新：
もう少し考えた後、ツリーでリーフノードを見つけることができれば、コンポーネントとそのサイズを検索する必要がまったくないことに気付きました。このノードに接続されているエッジのf（e）を計算することから始めます。リーフなので：
f(e) = weight(e) * 1（1はリーフノードであり、エッジを削除すると、リーフとグラフの残りの部分のみを含むコンポーネントが得られます。）
ここから、前述のように続行します...
リソースを除外します。リーフノードを見つけるのに必要な時間、残りの計算はO（m）（mはエッジの数）で、一定のメモリを使用して実行されます。

于 2011-05-30T11:55:23.973 に答える
1

yuribの答えについてもう少し詳しく説明すると、私は次のようなことをします（igraphメーリングリストにも投稿されています）。

2つの属性を使用します。1つは頂点用で、もう1つはエッジ用です。edge属性は単純で、呼び出され、探している値cut_valueであるか、その値が含まれています。None最初は、これらの値はすべてNonesです。cut_value=None 未処理のエッジと、``cut_valueがNone```で処理されていないエッジを呼び出します。

頂点属性はと呼ばれcut_size、未処理の入射エッジが1つだけ存在する頂点に対してのみ有効です。ツリーがあるので、すべてのエッジが処理されない限り（アルゴリズムを終了できる場合）、常に少なくとも1つのそのような頂点があります。最初は、cut_sizeすべての頂点に対して1になります（ただし、未処理の入射エッジが1つだけある頂点に対してのみ有効であることを忘れないでください）。

degまた、特定のノードで発生した未処理のエッジの数を含むリストもあります。最初はすべてのエッジが未処理であるため、このリストには頂点の次数が含まれています。

これまでのところ、これがあります：

n, m = graph.vcount(), graph.ecount()
cut_values = [None] * m
cut_sizes = [1] * n
deg = graph.degree()

常に、1つのインシデントの未処理のエッジを持つ頂点を処理します。最初に、これらをキューに入れます。

from collections import deque
q = deque(v for v, d in enumerate(deg) if d == 1)

次に、キューが空になるまで、キュー内の頂点を次のように1つずつ処理します。

  1. まず、キューから頂点vを削除し、未処理の唯一のインシデントエッジを見つけます。このエッジをeで表すとします

  2. eのはcut_value、eの重みに。を掛けたものです。min(cut_size[v], n - cut_size[v])

  3. eのもう一方の端点をuで表すとします。eが処理されるようになったため、 uに入射する未処理のエッジの数が1つ減少したため、1つ減らす必要がありdeg[u]ます。1になると、 uをキューdeg[u]に入れます。また、 vはグラフの一部であり、後でuに入射する最後のエッジを削除するときに分離されるため、これも1つ増やします。cut_size

Pythonでは、これは次のコードのようになります（テストされていません）。

weights = graph.es["weight"]
while q:
    # Step 1
    v = q.popleft()
    neis = [e for e in graph.incident(v) if cut_value[e] is None]
    if len(neis) != 1:
        raise ValueError("this should not have happened")
    e = neis[0]

    # Step 2
    cut_values[e] = weights[e] * min(cut_sizes[v], n - cut_sizes[v])

    # Step 3
    endpoints = graph.es[e].tuple
    u = endpoints[1] if endpoints[0] == v else endpoints[0]
    deg[u] -= 1
    if deg[u] == 1:
        q.append(u)
    cut_sizes[u] += 1
于 2011-05-30T13:13:18.567 に答える