如何查找不會導致循環依賴的子包

我們有一條規則禁止包之間的循環依賴。如何查找不會導致循環依賴的子包

我們也有一個相當龐大的包，需要一些分割。

現在的問題是：如何確定一個/ all /最大子類的子類，它可以從包中提取到新包中而不創建循環依賴。

是否有一個衆所周知的算法呢？

一個變化會令人敬畏，其中可以定義算法可以忽略的最大數量的依賴關係。

顯而易見，子集應該與包不相同，也不是空的。在最大子集的情況下，它應該小於原始包的一半。

來源

2012-03-02 Jens Schauder

你是否只考慮分包中的類的數量？或者也是類的「重量」呢？ – 2012-03-02 12:57:47

只是類的數量很好 – 2012-03-02 12:58:47

基本上，您的類，對象或您有什麼都存儲在表示directed graph（有循環或無循環）的矩陣（稱爲adjacency matrix）中。請參閱下圖和相應的鄰接矩陣。

enter image description here

由此，我們可以計算出可達矩陣，其描述到哪些節點可從當前節點的一個行程。對於此圖中，可達矩陣是

enter image description here

您需要重新排列行和矩陣的列，讓所有非零元素均低於主對角線的算法。可以按照它們出現在矩陣中的順序來執行這種情況的一系列對象索引，並且可以滿足每個對象的所有必需的依賴關係。如果已知該圖是非循環圖，則可以通過topological sorting來實現。

當循環出現在有向圖中時，您將無法找到這種情況爲真的排序。

輸入Design/Dependency Structure Matrix（DSM）。可以實現所謂的劃分算法以將對象劃分爲級別。對於這些級別中的每一級，對象可以按任意順序執行，並且不依賴於其他級別。對於上面的圖，節點3,4和5不相互依賴，並且可以按任意順序執行。

在（Warfield 1973）中開發了一種分區算法，它能夠檢測和隔離DSM中的週期。這與拓撲排序算法類似，但是使用可達性矩陣來檢測和隔離循環。

該算法簡要：

創建一個新的分區等級

計算可達性和先行詞設定R（S）和（S）

對於在DSM的每個元素，計算設定產品R（S）A（S）

如果R（S）A（s）= R（S），則該元件s添加到當前水平

移除元件s從所有其他元素的可達性和先行集中引用它。

如果項目列表不爲空，則重複1。

的先行設定A（s）是設置在s柱非零元素的行索引，而可達性集合R（s）爲所述集合中的非零元素的列索引的的s。

最後，一些僞代碼（在VB.NET，不會少）：

CalculateInitialAntecedentSets() 
CalculateInitialReachabilitySets() 
While UnlabelledItems > 0 
    Sequence.AddNewPartitionLevel() 
    For Each s In ReachabilityMatrix 
     If NoDependencies(s) and AlreadyConsidered(s) Then 
      AddToLevel(CurrentLevel, s) 
     End If 
    Next 

    RemoveDependencies(ReachabilitySets, Sequence.Level(CurrentLevel)) 
    RemoveDependencies(AntecedentSets, Sequence.Level(CurrentLevel)) 

    UpdateConsideredList(Sequence.Level(CurrentLevel)) 
    Unlabelled = Unlabelled - Sequence.Level(CurrentLevel).Count 
    CurrentLevel = CurrentLevel + 1 
End While

（這是幾年前我的碩士論文的題目）

沃菲爾德，約翰N. （1973），「Binary matrices in system modeling」，IEEE Transactions on Systems，Man，and Cybernetics SMC-3（5），441-449。

來源

2012-03-02 13:38:37 mindcorrosive

看起來非常好。您的圖片鏈接已損壞（至少第一張未鏈接到圖片） – 2012-03-02 14:08:24

@Jens：我可以看到它們：http://i.stack.imgur.com/EDeI1.png，http：// i.stack.imgur.com/Knvdl.png – mindcorrosive 2012-03-02 14:09:46

「執行」是什麼意思？提取？ – 2012-03-02 14:11:10

只是一個想法：

構建向圖，其中的類節點和依賴是邊緣。檢測全部strongly connected components。計算它們的權重（=節點/類的數量）。現在您有balanced partition problem - 將一組組件權重分爲兩個子組，其總和之間的差異最小。

來源

2012-03-02 13:16:54

這聽起來像它應該工作。 – 2012-03-02 14:17:46

您正在尋找的算法是topological sorting。簡單地提取物品，直到遇到一個循環。

來源

2012-03-02 13:27:09 ltjax

這提供了一個可能的解決方案，但不是最好的或者甚至是好的。 – 2012-03-02 13:31:17

我基本上用於許多類/提取包。但是當一個循環包含第一個/最後一個項目時，真的很難判斷是否存在可以提取的羣集。（硬：對於看圖的人） – 2012-03-02 14:00:37

如何查找不會導致循環依賴的子包

回答

相關問題