1

我正在解决一个我想通过图表旅行的问题。但是，当我分析我的代码时，我可以看到图形的构建是最重要的部分。每个节点都应该有一个固定长度 M 的值。该图应该包含所有以 2 为底的组合。例如，对于 M = 3，我们有：“000”“001”“010”“011”“100”“101” “110”“111”，即2^M = 8个组合。

然后我想以一种非常具体的方式将节点链接在一起。每个节点都有两个出边，值为“0”和“1”。例如，“000”将连接到带有边 1 的“001”，因为如果我删除右边的第一个数字并在末尾添加边值，我最终会得到“001”。类似地，“111”通过边缘“0”连接到“110”。

需要帮助。请注意，节点不一定必须用 String 表示，但这是我实现的方式，但它似乎运行得太慢。这里重要的是节点连接正确。

我通过将节点存储在 HashTable 中，然后遍历整个集合以将节点相互连接来解决了这个问题。

建议赞赏如何使它更聪明。

4

2 回答 2

2

更新：

所以你基本上想取一个数字并从中得出两个数字

  • 将其向左移动一位并取消设置第一位，并让最后一位为零
  • 与上面相同，但将最后一位设置为 1

现在这个数字连接到上面描述的这两个数字。

这是我的理解。

这是我为计算这样的图表而编写的一些代码：

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 回答