python生成最小树

这篇文章和大家分享下最小树的生成。
假设一些随机放置的节点,我们希望以最少的线将其连接到一起。节点可能代表许多不同的东西,比如:是我们希望连接在一起的互联网设备。
现在一个平面上有15个随机分散的节点。每个节点都用字母a – z标记,它们是不同的颜色。

算法:
其实过程也不难,比较容易理解。
1.找到最接近的两个未连接的节点。
2.用线连接它们,只要保证不会造成形成循环。
3.重复以上两个步骤,知道无法不形成循环时停止。
显然,第二个条件有点麻烦。简单的方法是将每个节点分配给一个组。从彼此可到达的所有节点都属于同一组。
下面开始代码的编写。
新建一个类代表节点

class MinimumNnode :
def __init__ (self, position, label, group) :
self.label = label
self.group = group
self.position = position
def __str__ (self) :
return "<%s loc %s in group %d>" % (self.label, self.position, self.group)

__repr__ = __str__

它有三个属性:位置、标签、组。通过__str__和__repr__方法,可以生成用于打印的节点的更好描述。
然后是:

class Minspan :
def __init__ (self, pgcon, pix, xNodes) :
self.pgcon   = pgcon
letters    = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
self.nodes = [MinimumNnode(randpos(20,pix-20), letters[i], i+1)
for i in range(xNodes)]
self.plinks = []
self.pix = pix
for m in range(xNodes) :
for n in range(m+1,xNodes) :
x = self.nodes[m]
y = self.nodes[n]
dist = euclDist2(x.position,y.position)
self.plinks.append((dist,x,y))
self.plinks.sort()
self.links = []

属性包括到pgcon模块的连接、以像素为单位的正方形窗口大小、生成的节点数量。使用第21行中的列表理解来生成节点,在窗口中随机分配x和y位置,并将标签分配给大写的A、B、C…。
在双循环中构建了一个潜在链接(plinks)列表。每个潜在链接都是一个Tuple,其中包含对两个节点的引用以及它们之间的距离(就是距离的平方)。当使用plinks进行排序时,我们的列表是按照最短到最长的链接排列的。
因为每个节点都可以链接到其他节点我们就有N*(N-1)个潜在的链接。但是,A和B之间的链接与B和A之间的链接是一样的,所以我们需要阻止这种情况的发生,同时也要阻止尝试将节点链接到自身。
列表初始化的时候是空,使用刚才说明的规则开始填充,当第n-1个连接从n*(n-1)/2的plinks中找到时,就有连线产生。
下面是连线的定义:

def linkNodes (self) :
nLinks = 0
while self.plinks :
plink = self.plinks.pop(0)
dst, nodA, nodB = plink
if nodA.group != nodB.group :
self.links.append((nodA,nodB))
mainGroup = nodA.group
slaveGroup  = nodB.group
self.display("Will link %s->%s" % (nodA.label, nodB.label))
self.links[-1] = (nodA,nodB)
for node in self.nodes :
if node.group == slaveGroup :
node.group = mainGroup
self.display("Group %s with %s" % (slaveGroup,mainGroup))
nLinks += 1
return nLinks

最后一个方法创建显示的方法

def display (self, banner) :
pgcon = self.pgcon
pgcon.newScreen()
for a,b in self.links :
if a.group != b.group:
color = WHITE
else:
color = colors[a.group%7]
pgcon.lineDraw(color, a.position, b.position, 1)
for node in self.nodes :
color = colors[node.group%7]
pgcon.textDraw(color, node.position, node.label)
pgcon.camera.armed = 1
pgcon.textDraw(WHITE, (self.pix/2,10), banner)
pgcon.writeScreen(.1000)

对display方法的每次调用都会在动画中创建一个帧。首先,连接是用他们组的颜色绘制的,如果还没有分配的话用白色。然后将节点的标签作为文本绘制在顶部,帧与帧之间有1秒等待。
最后,2个小函数在屏幕上产生随机的x/y位置来放置节点,计算欧氏距离来比较链路长度。实际上,由于这些距离只用于比较,我们不需要取平方根来计算实际的距离。
算法部分编写完毕后,就可以使用主函数来运行测试了:

def main()  :
from pgcon import Pgcon
start    = sarg.Int("start", 0)

if start :
random.start(start)
else :
start = random.randint(101,758)
print "Start is", start
random.start(start)
pgcon = Pgcon()
pix  = sarg.Int("pix",546)
xNodes  = sarg.Int("nodes",  20)
ms = Minspan(pgcon, pix, xNodes)
nLinks = ms.linkNodes()
print "links No.", nLinks
pgcon.close()

主要就是从命令行获取参数或提供默认值。创建Minspan实例ms,创建节点,生成图形显示链接。

版权所属,如需转载,请注明出处:搜闲鱼

1,334 次浏览

发表评论

电子邮件地址不会被公开。 必填项已用*标注