在networkx中生成和执行处理图

Question

我有许多“进程”，每个进程都实现为一个类（实现一个接口-process）和许多“数据集”，同样由一个类-dataset表示。在

可以创建数据集及其依赖关系的有向无环图。它可能看起来像：

            root
           /   \
  dataset1a     dataset1b
     |              |
  dataset2      dataset2b
   /   |  \        /     \
dset3a | dset3b  dset4a dset4b
   \   |        /
    \  |       /
     \ |      /
     dataset3a4a

要获取每个数据集，必须应用一个进程（由process类表示）。目前我正在用networkx创建一个DiGraph，其中每个dataset对象都是一个节点，到达X节点的过程是指向process对象的节点上的一个属性。ROOT只是一个虚拟节点，用于提供起始节点。在

这是用networkx表示图形的好方法吗？ 假设dataset1a和dataset1b存在，并且必须创建它们的分散体（其中每个前一个数据集都是process类的输入）…那么什么是遍历图的好方法，以便：

• 在访问了节点的所有依赖项（并因此创建了数据集）之前，不会访问该节点
• 可以找到依赖的“节点”…例如，如果我在dataset3a4a节点，我必须能够发现所有的“输入”来创建数据集-dset3a、dset4a和{}。在

Answer 1

Python提供了一些可以代替networkx使用的内省工具。 __subclasses__方法返回给定类的直接子类的列表：

In [36]: Root.__subclasses__()
Out[38]: [__main__.DataSet1a, __main__.DataSet1b]
In [61]: DataSet2.__subclasses__()
Out[61]: [__main__.DSet3a, __main__.DSet3b, __main__.DataSet3a4a]
In [62]: DataSet3a4a.__subclasses__()
Out[62]: []

__bases__属性返回类的基（直接父类）：

^{pr2}$

__bases__属性提供了关于 如何查找输入以创建数据集。在

要回答第一个问题，可以使用__subclasses__和__bases__来 构建自己的遍历函数：

import collections
class Root(object): pass
class DataSet1a(Root): pass
class DataSet1b(Root): pass
class DataSet2(DataSet1a): pass
class DataSet2b(DataSet1b): pass
class DSet3a(DataSet2): pass
class DSet3b(DataSet2): pass
class DSet4a(DataSet2b): pass
class DSet4b(DataSet2b): pass
class DataSet3a4a(DSet3a, DataSet2, DSet4a): pass

def visit(cls):
    seen = set([cls])
    queue = collections.deque(cls.__subclasses__())
    while queue:
        subcls = queue.popleft()
        if subcls in seen: continue
        # check that all its bases have been seen
        for base in subcls.__bases__:
            if base not in seen:
                # if a base has not been seen, push subcls to the back of the queue
                queue.append(subcls)
                break
        else:
            # all the bases of subcls have already been seen
            seen.add(subcls)
            yield subcls
        # add all the subclasses of subcls to the queue
        queue.extend(subcls.__subclasses__())

for cls in visit(Root):
    print(cls.__name__)

收益率

DataSet1a
DataSet1b
DataSet2
DataSet2b
DSet3a
DSet3b
DSet4a
DSet4b
DataSet3a4a