DiGraph параллельное упорядочение

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 (или 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

Класс Graph и топологическая сортировка, реализованные в 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'])

Обратите внимание, что мой код создает строку DOT 'digraph' для визуализации в GraphVis.Вы можете смело пропустить это, когда приобретете уверенность в алгоритме.Вы можете поменять местами закомментированные и некомментированные строки append ближе к концу, чтобы сначала получить основные узлы.Также обратите внимание, что это решение определяет a решение, которое удовлетворяет графу.Могут быть и другие, и это не определяет порядок в соответствии с вашими требованиями, но график удовлетворяет один правильный ответ.

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