标签: topological-sort

我有一个集合:

List<VPair<Item, List<Item>> dependencyHierarchy;

对中的第一项是某个对象(项),第二项是第一项依赖的相同类型对象的集合.我希望得到一个List<Item>依赖顺序,所以没有依赖于第一个元素的项目等等(没有循环依赖!).

输入:

Item4 depends on Item3 and Item5
Item3 depends on Item1
Item1 does not depend on any one
Item2 depends on Item4 
Item5 does not depend on any one 

结果:

Item1
Item5
Item3
Item4
Item2

谢谢.

解:

拓扑排序(感谢LoïcFévrier的想法)

和

例如在C#中,例如Java的 (感谢xcud伟大的例子)

我的女朋友在接受采访时得到了这个问题,我非常喜欢它,我以为我会分享它......写一个接收字典的算法(字数组).数组按字典顺序排序,但abc顺序可以是任何内容.例如,它可以是z,y,x,..,c,b,a.或者它可能完全搞砸了:d,g,w,y,......它甚至不需要包含所有的abc字母,最后它根本不必是字母.它可以是形成字符串的任何符号.例如,它可以由5,？,!,@,？组成......你明白了.由您的算法决定发现字母是什么(简单部分).

算法应返回符号的正确词典顺序.

注意事项/需要考虑的事项:1.对于给定的字典,您是否总能发现所有字母的完整顺序？考虑一个只有1个单词,多于1个符号的字典...... 2.你不能认为字典是没有错误的.该算法应确定字典是否包含矛盾并输出存在错误.3.提示:想一个好的数据结构来表示你在符号之间发现的关系.这应该使问题更容易.

我明天可能会发布我的解决方案.我绝不会声称它是最有效的.我想先看看其他人的想法.希望你喜欢这个问题

PS我认为发布解决方案的最佳格式是使用伪代码,但我将此留待您考虑

我正在尝试在ocaml中编写拓扑排序,但我是初学者(在OCaml和图算法中),我不能自己做.

我更容易考虑拓扑排序,例如C++(并且在互联网上有很多关于C++拓扑排序的例子),但我想学习一些新东西.此外,我已经找到了一些用OCaml编写的拓扑排序的例子,坦率地说,我不明白它们.

假设我有一个列表(int * int list) list,例如:

myList = [(1, [2]); (5, [6; 7]); (3, [2]); (6, [3; 7]); (8, [7]); (4, [3; 1])];;

这意味着,我需要"做"任务1任务之前2,任务4任务之前3和1等

我想,这个列表的输出应该是:

[8; 5; 6; 7; 4; 3; 1; 2]

(但我不确定,因为我刚刚做了这个例子,所以如果我错了,请纠正我)

另外,我已经读过,拓扑排序对于图中的循环不起作用,因此循环必须有某种条件 - 当给定图形有循环时,我们引发异常(我认为这是一个好主意) .

AFAIK,我需要在算法中使用DFS进行拓扑排序,其中(DFS)我不知道如何在OCaml中实现(我理解主要思想,但我不觉得,这在OCaml /函数编程中是如何工作的).

我非常感谢你帮助我理解这个概念(我的意思是拓扑排序,OCaml /函数编程中的DFS).如果可以的话,如果您向我展示示例代码,那将会很棒,因为阅读代码(对我来说)是理解算法概念的最佳方法.

我知道,对于大多数人来说,这是一个简单的问题,但我希望,它不会阻止你帮助我.

PS:我自己学习OCaml(我在高中),所以我没有扎实的理论背景(在OCaml或算法中).我开始学习OCaml,因为我想理解递归概念,现在这种语言看起来很有趣,因为它与C++真的不同,所以我还在尝试学习OCaml中的新东西.

从这里提取我们得到了一个最小的迭代dfs例程,我把它称为最小,因为你很难进一步简化代码:

def iterative_dfs(graph, start, path=[]):
    q = [start]
    while q:
        v = q.pop(0)
        if v not in path:
            path = path + [v]
            q = graph[v] + q

    return path

graph = {
    'a': ['b', 'c'],
    'b': ['d'],
    'c': ['d'],
    'd': ['e'],
    'e': []
}
print(iterative_dfs(graph, 'a'))

这是我的问题,您如何将此例程转换为拓扑排序方法,其中例程也变为"最小"？我看过这个视频,这个想法非常聪明,所以我想知道是否可以在上面的代码中应用相同的技巧,所以topological_sort的最终结果也变得"最小".

不要求拓扑排序的版本,这不是对上述例程的微小修改,我已经看过很少.问题不是"如何在python中实现拓扑排序",而是找到上述代码的最小可能调整集成为topological_sort.

附加评论

在原文中,作者说:

不久之前,我读了Guido van Rossen的图表实现,看似简单.现在,我坚持使用复杂性最低的纯python最小系统.我们的想法是能够探索算法.稍后,您可以优化和优化代码,但您可能希望以编译语言执行此操作.

这个问题的目标不是优化iterative_dfs,而是提出一个从它派生的topology_sort的最小版本(只是为了更多地了解图论算法).其实,我想一个更一般的问题可以像给一组最小的算法,{ iterative_dfs,recursive_dfs,iterative_bfs,recursive_dfs},这将是他们的topological_sort推导？虽然这会使问题变得更长/更复杂,但是从iterative_dfs中找出topology_sort就足够了.

我有一个具有部分订单关系的项目列表,i.e,该列表可以被认为是部分有序的集合.我想以与此问题相同的方式对此列表进行排序.正如那里正确回答的那样,这被称为拓扑排序.

有一个相当简单的已知算法来解决这个问题.我想要一个类似LINQ的实现.

我已经尝试使用OrderBy扩展方法,但我很确定它无法进行拓扑排序.问题是IComparer<TKey>界面无法表示部分订单.之所以会发生这种情况,是因为该Compare方法基本上可以返回3种值:零,负和正,意味着 分别等于,小于,然后大于.只有返回无关的方法才能实现有效的解决方案.

从我偏见的角度来看,我正在寻找的答案可能是由一个IPartialOrderComparer<T>接口和一个扩展方法组成的,如下所示:

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IPartialOrderComparer<TKey> comparer
);

这将如何实施？IPartialOrderComparer<T>界面如何？你会推荐一种不同的方法吗？我很想看到它.也许有一种更好的方式来表示偏序,我不知道.

比如说,我们有一些项目,每个都定义了一些部分排序规则,如下所示:

我A和我想要在此之前B

我C和我想要追求 A但之前D

所以我们有A,B,C,D这些规则的项目:

• A>B
• C<A, C>D
• 没有其他的!所以,B和D有没有排序的偏好",被认为是相等的.

如您所见,传递关系规则在这里不起作用.但是,如果A>B它仍然意味着B<A.因此,排序可能有多种可能的结果:

1. A B C D
2. ACDB
3. ACBD
4. A B C D

如何实现处理这种情况的排序算法？

原因是:有多个可加载模块,其中一些模块在某种程度上"依赖"其他模块.相对于其他模块,每个模块都可以声明简单的规则:

在模块A之前加载我

在模块B之后加载我

在模块A之前但在模块B之后加载我

现在我需要以某种方式实现这个排序.. :)

答案:Paddy McCarthy(麻省理工学院)的代码

## {{{ http://code.activestate.com/recipes/577413/ (r1)
try:
    from functools import reduce
except:
    pass

data = {
    'des_system_lib':   set('std synopsys std_cell_lib des_system_lib dw02 dw01 ramlib ieee'.split()),
    'dw01':             set('ieee dw01 dware gtech'.split()),
    'dw02':             set('ieee dw02 dware'.split()), …

我有一个带有N个节点的DAG,即1, 2, ..., N每个节点都有一个权重(我们可以称之为时间)x_1, x_2, ..., x_N.我想进行拓扑排序,但难点在于排序时我有一个目标函数.我的目标函数是最小化几对节点之间的总时间.

例如,我有一个包含6个节点的DAG,我想要一个特定的拓扑排序,这样(1,3) + (2,4)最小化,其中(A,B)表示两个节点A和B之间的时间.例如,如果我们有一个排序[1, 6, 3, 2, 5, 4, 7],(1,3) = x_6和(2,4) = x_5.基于DAG,我想找到一个最小化的排序(1,3) + (2,4).

我一直在想这个问题.生成所有可能的拓扑排序(参考链接)并逐个计算目标函数始终是一种可能的解决方案,但如果N很大则需要花费太多时间.我还建议在生成所有可能的排序时使用分支绑定修剪(我不是非常熟悉的分支绑定但我认为这不会大大降低复杂性).

针对此类问题的任何(最佳或启发式)算法？如果算法也可以应用于其他目标函数,例如最小化某些节点的总开始时间,那将是完美的.任何建议表示赞赏.

PS:或者,是否有可能将此问题表述为线性整数优化问题？

我正在努力研究如果我的问题可以使用内置的sorted()函数解决,或者如果我需要自己做 - 使用cmp的旧学校会相对容易.

我的数据集看起来像:

x = [
('business', Set('fleet','address'))
('device', Set('business','model','status','pack'))
('txn', Set('device','business','operator'))
....

排序规则基本上应该是N和Y的所有值,其中Y> N,x [N] [0]不在x [Y] [1]

虽然我正在使用Python 2.6,其中cmp参数仍然可用,但我正在尝试使这个Python 3安全.

那么,这可以使用一些lambda魔法和关键参数来完成吗？

- ==更新== -

谢谢Eli&Winston!我真的不认为使用钥匙会起作用,或者如果我怀疑它会是一个不太理想的鞋拔解决方案.

因为我的问题是数据库表依赖项,所以我不得不对Eli的代码进行一些小的补充,以从依赖项列表中删除一个项目(在一个设计良好的数据库中,这不会发生,但是谁住在那个神奇的完美世界？)

我的解决方案

def topological_sort(source):
    """perform topo sort on elements.

    :arg source: list of ``(name, set(names of dependancies))`` pairs
    :returns: list of names, with dependancies listed first
    """
    pending = [(name, set(deps)) for name, deps in source]        
    emitted = []
    while pending:
        next_pending = []
        next_emitted = []
        for entry in pending:
            name, …

我正在寻找一种方法来对给定的定向未加权图执行拓扑排序,其中包含循环.结果不仅应包含顶点的排序,还应包含给定排序违反的边集.这组边缘应该是最小的.

由于我的输入图可能很大,我不能使用指数时间算法.如果在多项式时间内无法计算最优解,那么对于给定的问题,什么启发式算法是合理的？

一些编程语言(如haskell)允许模块之间的循环依赖.由于编译器需要知道在编译一个模块时导入的所有模块的所有定义,如果某些模块相互导入或发生任何其他类型的循环,它通常必须做一些额外的工作.在这种情况下,编译器可能无法像没有导入周期的模块那样优化代码,因为可能尚未分析导入的函数.通常只有一个循环的一个模块必须以这种方式编译,因为二进制对象没有依赖性.我们称之为模块环路断路器

特别是如果导入周期是交错的,那么在编译由数百个模块组成的大项目时,如何最大限度地减少环路断路器的数量是很有趣的.

是否有一个算法给出一组依赖性输出最少数量的模块需要编译为循环断路器才能成功编译程序？

例

我试着澄清我在这个例子中的含义.

考虑与四个模块项目A,B,C和D.这是这些模块之间的依赖关系列表,输入X y方式y取决于x:

A C
A D
B A
C B
D B

可视化为ASCII图的相同关系:

D ---> B
^    / ^
|   /  |
|  /   |
| L    |
A ---> C

此依赖关系图中有两个循环:ADB和ACB.要打破这些循环,可以编译模块C和D循环断路器.显然,这不是最好的方法.编译A为一个环路断路器完全足以打破两个环路,你需要编译一个较少的模块作为一个环路断路器.