python - 有向图并行排序

Question

我有这种有多个根的有向无环图：

我需要得到一个按方向排序并按步骤分组的节点列表，如下所示：

ordering = [
    [1, 3],
    [2],
    [4],
    [5, 6],
    [7]
]

也许有一些现成的算法呢？我试过networkx.algorithm了，但他们都只能返回一个平面列表而不按步骤分组。

Answer 1

nx.topological_sort几乎做你想做的；唯一的区别是它不会对同时进入队列的项目进行分组，但可以直接调整源以使其这样做：

def topological_sort_grouped(G):
    indegree_map = {v: d for v, d in G.in_degree() if d > 0}
    zero_indegree = [v for v, d in G.in_degree() if d == 0]
    while zero_indegree:
        yield zero_indegree
        new_zero_indegree = []
        for v in zero_indegree:
            for _, child in G.edges(v):
                indegree_map[child] -= 1
                if not indegree_map[child]:
                    new_zero_indegree.append(child)
        zero_indegree = new_zero_indegree

用你的例子：

In [21]: list(nx.topological_sort(G))
Out[21]: [3, 1, 2, 4, 6, 7, 5]

In [22]: list(topological_sort_grouped(G))
Out[22]: [[1, 3], [2], [4], [5, 6], [7]]

在实践中，我不得不想知道是否存在这种构造比直接使用nx.topological_sort(or nx.lexicographical_topological_sort) 更有用的情况？

Answer 2

使用 DFS 的拓扑排序将解决问题

from collections import defaultdict, deque


class Graph:
    def __init__(self, directed=False, nodes=None, edges=None):
        self.graph = defaultdict(list)
        self.directed = directed
        self.add_nodes(nodes)
        self.add_edges(edges)

    @property
    def nodes(self):
        if not self.directed:
            return list(self.graph.keys())
        elif self.directed:
            nodes = set()
            nodes.update(self.graph.keys())
            for node in self.graph.keys():
                for neighbor in self.graph[node]:
                    nodes.add(neighbor)
            return list(nodes)

    def add_node(self, node):
        if node not in self.nodes:
            self.graph[node] = list()

    def add_nodes(self, nodes):
        if nodes is None:
            return None
        for node in nodes:
            self.add_node(node)

    def remove_node(self, node):
        try:
            del self.graph[node]
        except KeyError:
            print(f'{node} is not in graph')
            return None
        # remove parallel edges, but keep other parallel edges untouched
        for source, adj_list in self.graph.items():
            empty = True
            while empty:
                if node in adj_list:
                    adj_list.remove(node)
                else:
                    empty = False

    def remove_nodes(self, nodes):
        for node in nodes:
            self.remove_node(node)

    @property
    def edges(self):
        edges = list()
        for source, neighbors in self.graph.items():
            for neighbor in neighbors:
                edges.append((source, neighbor))
        return edges

    def add_edge(self, edge):
        node1, node2 = edge
        self.graph[node1].append(node2)
        if not self.directed:
            self.graph[node2].append(node1)

    def add_edges(self, edges):
        if edges is None:
            return None
        for edge in edges:
            self.add_edge(edge)

    def remove_edge(self, edge):
        self.remove_nodes(edge)

    def remove_edges(self, edges):
        for edge in edges:
            self.remove_nodes(edge)

    def topological_util(self, node, visited, label):
        visited[node] = True
        for edge in self.graph[node]:
            if not visited[edge]:
                self.topological_util(edge, visited, label)
        label.appendleft(node)

    def topological_sort(self):
        visited = dict.fromkeys(self.nodes, False)
        # store all nodes in topological order, the index is the position
        label = deque()
        for node in self.nodes:
            if not visited[node]:
                self.topological_util(node, visited, label)
        return label

用python实现的类图和拓扑排序。希望这会帮助你。

Answer 3

您的问题由所谓的“拓扑排序”解决。这种排序确定了有向无环图中的依赖关系。我最近调整了这个问题的解决方案。这是一个演示其行为的简单 python 应用程序：

# adapted from https://gist.github.com/kachayev/5910538
from collections import deque
GRAY, BLACK = 0, 1


def topological(graph):
    order, enter, state = deque(), set(graph), {}

    dot = "digraph X {\r\n"
    for item in graph.keys():
        dep = graph[item]
        for d in dep:
            dot += item + " -> " + str(d) + '\r\n'
    dot += "}"
    print(dot)

    def dfs(node):
        state[node] = GRAY
        for k in graph.get(node, ()):
            sk = state.get(k, None)
            if sk == GRAY:
                raise ValueError("cycle")
            if sk == BLACK:
                continue
            enter.discard(k)
            dfs(k)
        #order.appendleft(node)  # show highest to lowest
        order.append(node)  # show lowest to highest
        state[node] = BLACK
    while enter:
        dfs(enter.pop())
    return order


def main():
    graph = {
        '1': ['2'],
        '2': ['4'],
        '3': ['4'],
        '4': ['5', '6'],
        '6': ['7'],
    }
    try:
        print(topological(graph))
    except ValueError:
        print("Cycle!")


if __name__ == "__main__":
    main()

输出是

deque(['5', '7', '6', '4', '2', '1', '3'])

另请注意，我的代码为 GraphVis 中的可视化创建了一个 DOT 'digraph' 字符串。一旦你对算法有了信心，你就可以放心地把它排除在外。append您可以反转靠近末尾的注释行和未注释行，以首先获取主要节点。另请注意，此解决方案确定满足图形的解决方案。可能还有其他的，它不能按照您的要求确定顺序，但图表满意度是一个正确答案。

Answer 4

我编写了这段代码来解决我的问题，但也许有一些更优雅的解决方案？

def process_cursor(G, passed, node_id):
    if set(G.predecessors(node_id)).issubset(passed):
        return True, list(G.successors(node_id))
    return False, None


def get_all_roots(G: nx.DiGraph):
    for node_id in G.nodes:
        if not any(G.predecessors(node_id)):
            yield node_id


def order_components(G: nx.DiGraph):
    nodes_amount = len(G.nodes)
    cursors = set(get_all_roots(G))
    passed = []
    iterations = 0
    while len(passed) != nodes_amount:
        iterations += 1
        if iterations > nodes_amount:
            raise ValueError("Could not create sequence of graph.")
        step = []
        next_cursors = []
        step_passed = []
        for node_id in cursors:
            can_process, tmp_cursors = process_cursor(G, passed, node_id)
            if can_process:
                next_cursors.extend(tmp_cursors)
                step_passed.append(node_id)
                node_data = G.nodes[node_id]
                step.append(node_id)
        cursors = set(next_cursors)
        passed.extend(step_passed)
        if step:
            yield step
    yield append