4

次の非効率的な疑似Pythonコードによって値が与えられるものを計算する必要があります。

def foo(a,b):
   tmp = 0
   for i in graph.nodes():
       for j in graph.nodes():
          tmp += c
          if (i and j are neighbors):
              tmp += a - c
          elif (i and j are next-neighbors):
              tmp += b - c
   return tmp

言い換えると、ノードのすべてのペアが与えられると、foo = a *（E =エッジの数）+ b *（EE =ネイバーではないが、共通のネイバーを持つペアの数）+ c *（N（N-1 ）/ 2-EE-E）。

ある種の幅優先探索を考えようとしましたが、できませんでした。

編集：詳細

  • グラフは静的ではありません。私は常にエッジを追加および削除しているので、これを一度だけ計算することはできません。私は常に「次の隣人のリスト」を更新しなければなりません。
  • グラフを隣接行列として保存します。
4

3 に答える 3

5

これが大まかなアイデアです。しかし、最初に、いくつかの仮定：1.無向グラフ2.一定の頂点数

グラフは常に変化します。したがって、ネイバー（エッジ）とセカンドネイバーの数を効率的に更新する必要があります。最初は些細なことなので、2番目の隣人を見てみましょう。

@Patrickの提案に従って、を使用してA^2、毎回最初から再計算することなく効率的に更新する方法を見てみましょう。 A^2_ijは、からの長さ2のパスの数です。頂点iからjそれ自体への長さ2のパスが常に存在するため、対角線のエントリも含まれることに注意してください。があれば、2番目の隣人の数を簡単に数えることができるので、グラフが変化する間、すべてを最新A^2の状態に保ちましょう。A^2

A^2効率的に更新する方法：

エッジを追加/削除すると、エントリが2つしかないAマトリックスによって変更されます。Bエッジを追加する（削除しない）と仮定します。次に(A+B)^2 = A^2 + AB + BA + B^2。

追加されたエッジがであったと仮定します(i,j)。

  • B^2些細なことです：(B^2)_ii = (B^2)_jj = 1、残りは0です。
  • AB = transpose(BA)したがって、2つのうちの1つを計算するだけで済みますBA。の行はの行であり、の行はの行iであり、残りはゼロであることがわかります。繰り返しになりますが、計算は高速です。BAjAjBAiA

エッジの削除も同様です。

2番目の隣人の数だけが必要なので、各ステップでゼロ以外の非対角エントリがいくつあるかを数える代わりに、追加するときにA^2ゼロ以外のエントリの数がどれだけ変化するかを数えることができます。 。A^2AB + BA

編集

このすべてが別の言語で説明されています：

長さの数を追跡しましょう-行列内の任意の2つの頂点間の2つのパスM。iとの間にエッジを追加（削除）するとj、長さ2のパスの数は、のすべてのネイバーとのすべてのネイバーの間で1つ増加（減少）するためi、に変更を加えるたびに時間内に更新するのは簡単です。グラフ。jjiMO(n)

于 2011-07-13T09:36:06.383 に答える
1

グラフを隣接行列 に格納する場合、これが要求しているのであればA、行列にそれ自体（）を乗算することにより、すべての長さ2のパスを見つけることができます。A^2

これは前処理にO（n ^ 3）時間かかりますが、その後、一定時間でネイバーと「ネクストネイバー」のルックアップを実行できます。

于 2011-07-12T15:44:04.647 に答える
0

ノードのネイバーのリストを取得します（node_main）。各隣人を訪問します。node_mainのネイバーの1つ（またはnode_main自体）でない限り、各ネイバーをネイバーオブネイバーリストに追加します。私は何かが足りないのですか？

于 2011-07-12T15:51:30.363 に答える