- 拓樸排列程式
拓樸排列程式
花了一些時間寫了一個排列拓樸程式，將概念寫在這邊。
在論壇爬文時，看到作者自己推薦的 Python 樹狀結構模組 anytree，看了說明文件後決定使用此模組協助樹狀管理。
以一個四連桿 (4,) 的樹狀拓樸如下，只有一種排列方法：
L0(2)
├── L1(2)
│ └── L3(2)
│ └── [L2](2)
└── L2(2)
└── [L3](2)
-------
Answer count: 1
需要的模組有：
from anytree import Node, RenderTree
from anytree.search import findall
from itertools import permutations
from typing import Tuple
接著是印出上面樹狀結構的函式，anytree 的 RenderTree 搜尋函式會朝下列出節點的階級字元。
這邊用 noname 這個 bool 變數決定是否顯示名稱。
show_tree = lambda root: '\n'.join("{}{}({})".format(pre, n.name, n.limit) for pre, fill, n in RenderTree(root))
接下來是主函式，稱為 make_link，接收內含 int 的可迭代物件。
def make_link(iter: Tuple[int,]):
...
return answer
第一部分是創出連桿的數量，數字則是接頭數。
link_type = []
for i, num in enumerate(iter):
i += 2
for j in range(num):
link_type.append(i)
如輸入 (4,)，可以得到 [2, 2, 2, 2]；輸入 (5, 4) 可得 [2, 2, 2, 2, 2, 3, 3, 3, 3]。
使用 Python 迭代工具模組的 permutations 函式來創造排列組合的迴圈。
相符無誤的項目會將 root 節點加入答案，有錯誤則用 continue 關鍵字跳過。
answer = [] for all_link in list(set(permutations(link_type))): ... answer.append(links[0])
首先轉換 link_type 的內容成為 anytree 模組的 Node 類型。
其中 limit 屬性是此節點的接頭上限，僅用於比對，並無程式上的限制。
all_link = [Node("L{}".format(i), limit=v) for i, v in enumerate(all_link)]
接著將第一項當作 root 節點，加入 links。
這裡 links 清單的最後一項 links[-1] 是接下來的搜索法準備填入的項目。
links = []
links.append(all_link.pop(0))
然後使用廣度優先搜索法 (Breadth-First-Search, BFS) 填入所有節點，使用 list 類型的 pop 方法配上 while 迴圈可以確保用光所有節點。
當指派一個節點的 parent 屬性時，anytree 模組會自動將節點連上父節點，父節點可以透過 children 屬性取得一個裝有所有子節點指標的 tuple 物件。
while all_link:
link = all_link.pop(0)
if (len(links[-1].children) + bool(links[-1].parent))==links[-1].limit:
links.append(links[-1].children[0])
link.parent = links[-1]
由於數學定義的「樹 (tree)」結構中，子節點只能擁有一個父項，否則為迴路 (Loop)，anytree 模組會在連接成迴路時自動回擲 LoopError 錯誤。
但是我們的運動鍊為 close chain，因此必須再創立一個配對流程，這次使用類似連結的概念，同時為「主體」連結一個虛擬節點。
虛擬節點的樣式使用中括弧 [ ] 辨識，不用指派名稱。
創立 get_no_done 函式回傳使用 anytree 的 findall 模組過濾沒配對完成的節點。
get_no_done = lambda: findall(links[0], filter_=lambda n: '[' not in n.name and (len(n.children) + bool(links[-1].parent)) < n.limit)
error = False
while get_no_done():
nodes = get_no_done()
try:
l_1, l_2 = nodes[0], nodes[1]
except (ValueError, IndexError):
error = True
break
else:
Node("[{}]".format(l_1.name), limit=str(l_1.limit), parent=l_2)
Node("[{}]".format(l_2.name), limit=str(l_2.limit), parent=l_1)
最後檢查是否在上述迴圈出現沒閉合狀況。
if error:
continue
或是兩對連桿之間有連到一個以上的接頭。
if findall(links[0], filter_=lambda n: len([c.name for c in n.children])!=len(set(c.name for c in n.children))):
continue
最後可以進行測試：
if __name__=='__main__':
print("Topologic test")
answer = topo([5, 4])
#Show tree
for root in answer:
print(show_tree(root))
print('-'*7)
print("Answer count: {}".format(len(answer)))
可得：
...
-------
L0(2)
├── L1(3)
│ ├── L3(2)
│ │ └── L5(3)
│ │ ├── L6(3)
│ │ │ ├── L8(3)
│ │ │ │ ├── [L6](3)
│ │ │ │ └── [L7](2)
│ │ │ └── [L8](3)
│ │ └── L7(2)
│ │ └── [L8](3)
│ └── L4(2)
│ └── [L2](2)
└── L2(2)
└── [L4](2)
-------
Answer count: 60
經驗證，所有接頭都有連接。