CODEWITHSUNDEEP
python
Luis
Luis

Reputation: 1465

How to walk through a dependency graph?

I have tasks that need to be executed according to set of rules.

For example:

        | - File2
File1  -
        | - File3

Which means that the task of File1 must be executed before File2 and File3. I wrote the following code :

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()

Which gives me:

file1
file2
file3

In this example the print is the execution function in the node.

The problem is that this code doesn't work for case like:

File1  -
        | - File3
File2  -

If I have:

   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": ""
    }

It will give me:

file1
file3
file2

It should be:

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

Basicly each Node can do the execute function (print) only once all it's parents have completed their execute function (print). How can I solve this?

Upvotes: 3

Views: 1320

Answers (2)

Jeffrey Benjamin Brown
Jeffrey Benjamin Brown

Reputation: 3709

The algorithm you want is "topological sort": A list L of the elements of the graph, such that if A precedes B in L, then A is not a descendant of B. It's a standard graph problem; existing libraries should handle it. Here's one of them.

Note that in a general DAG such an order is not always guaranteed to exist.

Upvotes: 0

rdas
rdas

Reputation: 21275

Your dependency tree isn't actually a tree - it's a DAG. When you print the tree at file1, file2 should not be printed.

BTW you should not store the parent in the json, that will force your system to be a tree. (which may be fine, depending on your requirements)

Upvotes: 1

Related Questions