依存関係のあるものを順に並べる。

python

やりたいこと

A -B -> C
  -D -> E

というような依存関係がある時、依存関係の解決したものから順に利用したい。上の例だと例えばこんな感じ。

C , B , E , D , A

DAG -> トポロジカルソート -> 反転と同じような感じ。

たぶん、探せば絶対あるけど、とりあえず必要なので作ってみる。

  • node.py
  • node_serializer.py

node.pyは依存関係の木を作るためのもの。
node_serializerはそれを上のような順序で取り出すためのもの。

node.py
# -*- coding: utf-8 -*-
import sys

class Node(object):
    def __init__(self, k, v=None):
        self.k = k
        self.v = v
        self._children = {}

    @property
    def children(self):
        return self._children.values()

    def add(self, child):
        self._children[child.k] = child

    def __getattr__(self, k):
        return self._children.get(k)

    def __str__(self):
        return "%s: %s" % (self.k, self.v)

    def inspect(self, indent=0):
        sys.stdout.write(" "*indent)
        sys.stdout.write(str(self))
        sys.stdout.write("\n")

        indent_ = indent + 2
        for child in self._children.values():
            child.inspect(indent_)
        
if __name__ == "__main__":
    x = Node("x", "x")
    xx = Node("xx", "y")
    x.add(xx)
    xy = Node("xy", "z")
    x.add(xy)
    xxx = Node("xxx", "α")
    x.xx.add(xxx)
    x.inspect()

実行例

$ python node.py 
x: x
  xx: y
    xxx: α
  xy: z
node_serializer.py
# -*- coding:utf-8 -*-
from node import Node
import copy

class NodeSerializer(object):
    def __init__(self, keyfn= lambda x : x):
        self.keyfn = keyfn
        self.candidates = []
        self.consumed = set()

    def add(self, node):
        self.candidates.append(node)
        return self

    def _children_are_consumed(self, node):
        for child in node.children:
            if not self.keyfn(child) in self.consumed:
                return False
            if not self._children_are_consumed(child):
                return False
        return True
        

    def _reset(self):
        self.consumed = set()

    def __iter__(self): #手抜き
        self._reset()

        xs = copy.copy(self.candidates)

        while xs:
            x = xs.pop(0)

            if self._children_are_consumed(x):
                yield x
                self.consumed.add(self.keyfn(x))
            else:
                xs.append(x)

if __name__ ==  "__main__":
    a = Node("a")
    b = Node("b")
    c = Node("c")
    a.add(b)

    ns = NodeSerializer(lambda n : n.k).add(a).add(b).add(c)
    for e in ns:
        print e

実行結果

python node_serializer.py
# [a -> b, c] という依存関係
b: None
c: None
a: None

もうちょっと増やした。

a = Node("a")
b = Node("b")
c = Node("c")
d = Node("d")
e = Node("e")
f = Node("f")
g = Node("g")
h = Node("h")
i = Node("i")
j = Node("j")
a.add(b)
a.add(c)
a.add(g)
d.add(e)
d.add(g)
c.add(f)
e.add(f)
h.add(i)
i.add(j)

xs = [a, b, c, d, e, f, g, h, i, j]
ns = reduce(lambda ns, x: ns.add(x), xs, NodeSerializer())

print [i.k for i in ns]

 > ['b', 'f', 'g', 'j', 'c', 'e', 'i', 'a', 'd', 'h']