如何对服务依赖进行排序？（多服务，多依赖）

第一组：
x <--  y  // x 依赖 y

z <--  y  // z 依赖 y


第二组：

a <--  b     //a 依赖 b

c <--  b     // c 依赖 b

b <--  e, f  // b 依赖 e, f 两个服务。下面的服务关系类同， 不再写注释了。

g <--  b

a <--  e

最终排序为：

第一组：
y, [x, z]  // y 是第一批次。x 和 z 都属于第二批次，xz 不分先后

第二组：
[e, f],  b , [a, c, g] // e, f 属于第一批次，b 属于第二批次，a,c,g 属于第三批次

如何用 python 程序表达排序的逻辑呢？

第 1 条附言 · 2020-09-29 15:26:53 +08:00

我使用拓扑排序, 已经解决了部分问题, 可以把第一组和第二组服务排出顺序.
现在还有个问题, 如果第一组服务和第二组服务混在一起了, 如果将他们分成两组, 然后分别进行拓扑排序?

第 2 条附言 · 2020-09-29 17:30:15 +08:00

from functools import reduce as _reduce


class CircularDependencyError(ValueError):
    def __init__(self, data):
        s = "Circular dependencies exist among these items: {{{}}}".format(
            ", ".join(
                "{!r}:{!r}".format(key, value) for key, value in sorted(data.items())
            )
        )
        super(CircularDependencyError, self).__init__(s)
        self.data = data


def toposort(data):
    if len(data) == 0:
        return

    # Copy the input so as to leave it unmodified.
    data = data.copy()

    # Ignore self dependencies.
    for k, v in data.items():
        v.discard(k)
    # Find all items that don't depend on anything.
    extra_items_in_deps = _reduce(set.union, data.values()) - set(data.keys())
    # Add empty dependences where needed.
    data.update({item: set() for item in extra_items_in_deps})
    while True:
        ordered = set(item for item, dep in data.items() if len(dep) == 0)
        if not ordered:
            break
        yield ordered
        data = {
            item: (dep - ordered) for item, dep in data.items() if item not in ordered
        }
    if len(data) != 0:
        raise CircularDependencyError(data)


if __name__ == "__main__":
    group1 = {"A": {"B", "E"}, "C": {"B"}, "B": {"E", "F"}, "G": {"B"}}
    print(list(toposort(group1)))

    group2 = {"X": {"Y"}, "Z": {"Y"}}
    print(list(toposort(group2)))

    # 如果一开始给的数据, 是group1和2合并在一起的
    # 如何把数据分成两个组, 并且分别做拓扑排序
    init_data = {**group1, **group2}
    print(list(toposort(init_data)))

依赖

排序

服务

Java

6 条回复 • 2020-09-29 14:38:05 +08:00