Python 初體驗 (2) - BATON 演算法撰寫

之前的文章提到了用 Python 與 Gnuplot 解決作業之後，我就大量的使用 Python 來解決各項課業上的問題。

最近正在實作 BATON 的演算法，當仁不讓的還是使用 Python 來解決這個問題。以下是我要實作演算法的虛擬碼：

Algorithm: join(node n)  
If (Full(LeftRoutingTable(n)) and  
Full(RightRoutingTable(n)) and  
((LeftChild(n)==null) or (RightChild(n)==null))  
Accept new node as child of n  
Else  
If ((Not Full(LeftRoutingTable(n))) or  
  (Not Full(RightRoutingTable(n))))  
 Forward the JOIN request to parent(n)  
Else  
 m=SomeNodesNotHavingEnoughChildrenIn  
      (LeftRoutingTable(n), RightRoutingTable(n))  
 If (there exists such an m)  
    Forward the JOIN request to m  
 Else  
    Forward the JOIN request to one of its  
    adjacent nodes  
 End If  
End If  
End If  

而下面的則是 Python 實作的程式碼：

def join(child, n):  
if Full(n\['LeftRoutingTable'\]) and \\  
Full(n\['RightRoutingTable'\]) and \\  
((n\['LeftChild'\] \== None) or (n\['RightChild'\] \== None)):  
 print '    ' + str(n\['Name'\]) + ' -- ' + str(child\['Name'\]) + ';'  
 accept(child, n)  
else:  
 if not Full(n\['LeftRoutingTable'\]) or not Full(n\['RightRoutingTable'\]):  
     join(child, n\['Parent'\])  
 else:  
     m \= NodesNotEnoughChildren(n\['LeftRoutingTable'\], n\['RightRoutingTable'\])  
     if(m != None):  
         join(child, m)  
     else:  
         \# Forward the JOIN request to one ofits adjacent nodes  
         if n\['LeftAdjacent'\] != None:  
             join(child, n\['LeftAdjacent'\])  
         else:  
             join(child, n\['RightAdjacent'\])  

是不是與虛擬碼非常相似呢？撰寫完演算法後，還有一個工作就是要視覺化的表達樹的結構。正巧這幾個禮拜在紅塵一隅間拾得的文章裡面提到了 graphviz 這個非常好用的工具，可以用來產生各種有向、無向圖形。所以就利用這個工具來產生圖形，而 Python 呼叫外部程式當然也是很簡單：

def node(name):  
return {  
    'Parent' : None,  
    'LeftChild' : None,  
    'RightChild' : None,  
    'LeftRoutingTable' : list(),  
    'RightRoutingTable' : list(),  
    'LeftAdjacent' : None,  
    'RightAdjacent' : None,  
    'Name' : name,  
    'Level' : 0  
}  
  
def travel(node, tstr):  
if node\['LeftChild'\] != None:  
    tstr += '    ' + str(node\['Name'\]) + ' -- ' + str(node\['LeftChild'\]\['Name'\]) + ';\\n'  
    tstr \= travel(node\['LeftChild'\], tstr)  
if node\['RightChild'\] != None:  
    tstr += '    ' + str(node\['Name'\]) + ' -- ' + str(node\['RightChild'\]\['Name'\]) + ';\\n'  
    tstr \= travel(node\['RightChild'\], tstr)  
return tstr  
  
root \= node('root')  
child \= node('child')  
join(child, root)  
  
for i in range(0, int(sys.argv\[1\])):  
c \= node(i)  
join(c, root)  
print 'Finish\\n'  
  
tstr \= travel(root, '')  
  
temp \= Template('graph G{\\n$info\\n}\\n')  
s \= temp.substitute(info\=tstr)  
  
file \= open('temp.dot', 'w')  
file.write(s)  
file.close()  
  
os.system('dot -Tsvg -o temp.svg temp.dot')  
os.system('eog temp.svg')  

執行完程式後 Eye of GNOME 就開啟了這張繪製好的 SVG 圖檔。

Python 是個好東西阿！