如何查找不会导致循环依赖的子包

我们有一条规则禁止包之间的循环依赖。如何查找不会导致循环依赖的子包

我们也有一个相当庞大的包，需要一些分割。

现在的问题是：如何确定一个/ 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

如何查找不会导致循环依赖的子包

回答

相关问题