1

グラフを移動したいという問題に取り組んでいます。ただし、コードをプロファイリングすると、グラフの作成が重要な部分であることがわかります。すべてのノードには、固定長Mの値が必要です。グラフにはベース2のすべての組み合わせが含まれている必要があります。したがって、たとえばM = 3の場合、次のようになります。 "000" "001" "010" "011" "100" "101" "110" "111"、つまり2 ^ M=8の組み合わせ。

次に、非常に特殊な方法でノードをリンクします。すべてのノードには、値が「0」と「1」の2つの出力エッジがあります。たとえば、「000」はエッジ1で「001」に接続されます。これは、右側の最初の数値を削除し、最後にエッジ値を追加すると、「001」になるためです。同様に、「111」はエッジ「0」によって「110」に接続されます。

ヘルプが必要です。ノードは文字列で表す必要はないことに注意してください。これは私が実装した方法ですが、実行が遅すぎるようです。ここで重要なのは、ノードが正しく接続されていることです。

これを解決するには、ノードをHashTableに格納し、セット全体をループしてノードを相互に接続します。

提案は、これをよりスマートにする方法を高く評価しました。

4

2 に答える 2

2

アップデート：

したがって、基本的には、数値を取得して、そこから2つの数値を導き出す必要があります。

  • それを1ビット左にシフトし、最初のビットの設定を解除し、最後のビットをゼロにします
  • 上記と同じですが、最後のビットを1に設定します

これで、この番号は上記の2つの番号に接続されます。

それが私の理解です。

このようなグラフを計算するために私が書いたコードは次のとおりです。

import pygraphviz as pgv


# length of binary codes

for n in range(3,8):
  def b(x):
    return str(bin(x))[2:].zfill(n)
  G=pgv.AGraph(directed=True)

  for i in range(1,2**n):
    for j in range(1,2**n):
      I  = b(i)
      J  = b(j)
      # we make room for another bit (the zero bit)
      i1 = i << 1
      # we unset the first bit
      i1 = i1 & ~(1<<(n+1))

      # we copy the previous result
      i2 = i1
      # we set the last bit
      i2 = i2 | 1
      if    i1 == j :
        G.add_edge(I,J,label="0")
      elif  i2 == j:
        G.add_edge(I,J,label="1")

  G.layout(prog='dot')
  G.draw("graph"+str(n)+".png")

n = 3

ここに画像の説明を入力してください

n = 4

ここに画像の説明を入力してください

n = 5

ここに画像の説明を入力してください

n = 6

ここに画像の説明を入力してください

PS最初はnetworkxを使用してみましたが、すぐにpygraphvizの方がはるかに使いやすいことに気付きました。

于 2013-03-27T08:22:05.390 に答える
0

頂点が実際には数値であるとすると、列番号と行番号が頂点を表す隣接行列を使用してみませんか？

于 2013-03-27T07:36:00.927 に答える