Блог

Главная - Вопросы по программированию - Создайте и выполните рабочий процесс задач с помощью networkx (Python)

Создайте и выполните рабочий процесс задач с помощью networkx (Python)

#python #multithreading #graph #task #networkx

#python #многопоточность #График #задача #networkx

Вопрос:

Краткие сведения:

Цель состоит в том, чтобы запустить рабочий процесс, созданный из набора шагов (узлов графа) и их зависимостей (ребер графа).

Возможно ли создать networkx.DiGraph() и запустить обход, который выполняет обратный вызов на разных узлах?

Пример:

Пожалуйста, просмотрите пример графика:

Возможные порядки выполнения примера рабочего процесса

Для этого набора задач и зависимостей возможности выполнения следующие:

  1. шаг a в качестве точки входа
  2. шаг b сразу за шагом a
  3. шаги c и d параллельно сразу после шага b (шаг c завершается первым)
  4. шаг g сразу после шага c (пока шаг d еще выполняется)
  5. шаг e сразу после шага d (поскольку шаг c уже завершен)
  6. шаг f сразу за шагом e

или,

  1. шаг a в качестве точки входа
  2. шаг b сразу за шагом a
  3. шаги c и d параллельно сразу после шага b (шаг d завершается первым)
  4. шаги g и e параллельно (поскольку шаг d завершен до шага c )
  5. шаг f сразу за шагом e

Ниже, пожалуйста, найдите фрагмент кода для создания этого примера графика в networkx :

 import networkx as nx

W = nx.DiGraph()

nodes = ["a", "b", "c", "d", "e", "f"]
edges = [("a", "b"), ("b", "c"), ("c", "g"), ("b","d"), ("c", "e"), ("d", "e"), ("e", "f")]
W.add_nodes_from(nodes)
W.add_edges_from(edges)

Существуют ли известные решения для обхода графика описанным ранее способом, печати значения узла (название шага) и перехода в режим ожидания на случайное небольшое количество секунд, чтобы имитировать выполнение задачи и выполнение некоторых вычислений? (С использованием базовой многопоточности)

Спасибо.

Комментарии:

1. Не ясно, что вам нужно. В NetworkX есть несколько алгоритмов обхода, таких как BFS или DFS. Вы можете написать пользовательскую функцию обхода, в которой вы можете установить задержку.

2. Короче говоря, я пытаюсь имитировать выполнение иерархии зависимых задач. Моя идея заключалась в том, чтобы использовать график для представления рабочего процесса и посмотреть, возможно ли использовать networkx для построения графика и обхода его. Я думаю, что BFS ближе, чем DFS, к алгоритму обхода, который может выполнить это, но, боюсь, этого недостаточно. Я попытаюсь пересмотреть свою формулировку поста в надежде прояснить ее подробнее.

Ответ №1:

Топологическая сортировка (nx.topological_sort) вернет допустимую последовательность для задач.
Пример:

 >>> list(nx.topological_sort(W))
['a', 'b', 'd', 'c', 'e', 'f', 'g']

Если вам нужны группы задач, которые можно выполнять одновременно, вы можете немного изменить его, чтобы выполнить группировку.

 def topological_sort_grouping(g):
    # copy the graph
    _g = g.copy()
    res = []
    # while _g is not empty
    while _g:
        zero_indegree = [v for v, d in _g.in_degree() if d == 0]
        res.append(zero_indegree)
        _g.remove_nodes_from(zero_indegree)
    return res

Пример:

 >>> topological_sort_grouping(W)
[['a'], ['b'], ['c', 'd'], ['e', 'g'], ['f']]

Учитывая группы, вы можете выполнять итерации по ним и выполнять задачи в одних и тех же группах одновременно.