Блог

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

Например:

         | - File2
File1  -
        | - File3
  

Это означает, что задача File1 должна быть выполнена перед File2 и File3.
Я написал следующий код :

 import json
    json_string = """
    {
        "file1": {
            "path_to_file": "file1.txt",
            "children": "file2,file3"
        },
        "file2": {
            "path_to_file": "file2.txt",
            "children": ""
        },
        "file3": {
            "path_to_file": "a/file3.txt",
            "children": ""
    }
"""


class Node(object):
    def __init__(self, name, path_to_file=None):
        self.name = name
        self.path_to_file = path_to_file
        self.children = []

    def add_child(self, obj):
        self.children.append(obj)

    def dump(self):
        print('%s' % (self.name))
        for obj in self.children:
            obj.dump()

name2info = json.loads(json_string)

def get_tree(name):
    info = name2info[name]
    root = Node(name, info['path_to_file'])
    for child in info['children'].split(","):
        if child:
            root.add_child(get_tree(child))
    return root

root = get_tree('file1')
root.dump()
  

Что дает мне:

 file1
file2
file3
  

В этом примере print — это execution function в узле.

Проблема в том, что этот код не работает для случая, подобного:

 File1  -
        | - File3
File2  -
  

Если у меня есть:

    json_string = """
    {
        "file1": {
            "path_to_file": "file1.txt",
            "children": "file3"
        },
        "file2": {
            "path_to_file": "file2.txt",
            "children": "file3"
        },
        "file3": {
            "path_to_file": "a/file3.txt",
            "children": ""
    }
  

Это даст мне:

 file1
file3
file2
  

Это должно быть:

 file1
file2
file3   #3 is child of 1 and 2 - it can be executed only after 1 amp; 2 are done.
  

В основном каждый Узел может выполнять функцию execute (печать) только после того, как все его родители завершат свою функцию execute (печать).
Как я могу решить эту проблему?

Ваше дерево зависимостей на самом деле не дерево — это DAG. Когда вы печатаете дерево по адресу file1 , file2 оно не должно быть напечатано.

Кстати, вы не должны хранить родительский файл в json, это заставит вашу систему быть деревом. (что может быть хорошо, в зависимости от ваших требований)

Алгоритм, который вам нужен, — это «топологическая сортировка»: список L элементов графика, такой, что если A предшествует B в L , то A не является потомком B . Это стандартная проблема с графом; существующие библиотеки должны справиться с ней. Вот один из них.

Обратите внимание, что в общем DAG такой порядок не всегда гарантируется.