概要
ある種の DFS 反復アルゴリズムを使用して、有向循環グラフをトラバースする方法を理解しようとしています。これは、私が現在実装しているものの小さな mcve バージョンです (サイクルは扱っていません)。
class Node(object):
def __init__(self, name):
self.name = name
def start(self):
print '{}_start'.format(self)
def middle(self):
print '{}_middle'.format(self)
def end(self):
print '{}_end'.format(self)
def __str__(self):
return "{0}".format(self.name)
class NodeRepeat(Node):
def __init__(self, name, num_repeats=1):
super(NodeRepeat, self).__init__(name)
self.num_repeats = num_repeats
def dfs(graph, start):
"""Traverse graph from start node using DFS with reversed childs"""
visited = {}
stack = [(start, "")]
while stack:
# To convert dfs -> bfs
# a) rename stack to queue
# b) pop becomes pop(0)
node, parent = stack.pop()
if parent is None:
if visited[node] < 3:
node.end()
visited[node] = 3
elif node not in visited:
if visited.get(parent) == 2:
parent.middle()
elif visited.get(parent) == 1:
visited[parent] = 2
node.start()
visited[node] = 1
stack.append((node, None))
# Maybe you want a different order, if it's so, don't use reversed
childs = reversed(graph.get(node, []))
for child in childs:
if child not in visited:
stack.append((child, node))
if __name__ == "__main__":
Sequence1 = Node('Sequence1')
MtxPushPop1 = Node('MtxPushPop1')
Rotate1 = Node('Rotate1')
Repeat1 = NodeRepeat('Repeat1', num_repeats=2)
Sequence2 = Node('Sequence2')
MtxPushPop2 = Node('MtxPushPop2')
Translate = Node('Translate')
Rotate2 = Node('Rotate2')
Rotate3 = Node('Rotate3')
Scale = Node('Scale')
Repeat2 = NodeRepeat('Repeat2', num_repeats=3)
Mesh = Node('Mesh')
cyclic_graph = {
Sequence1: [MtxPushPop1, Rotate1],
MtxPushPop1: [Sequence2],
Rotate1: [Repeat1],
Sequence2: [MtxPushPop2, Translate],
Repeat1: [Sequence1],
MtxPushPop2: [Rotate2],
Translate: [Rotate3],
Rotate2: [Scale],
Rotate3: [Repeat2],
Scale: [Mesh],
Repeat2: [Sequence2]
}
dfs(cyclic_graph, Sequence1)
print '-'*80
a = Node('a')
b = Node('b')
dfs({
a : [b],
b : [a]
}, a)
上記のコードはいくつかのケースをテストしています。最初のケースは、以下のグラフのある種の表現になります。
2 つ目は、1 つの「無限」ループを含む 1 つのグラフの最も単純なケースです。{a->b, b->a}
要件
- 「無限サイクル」のようなものは存在しません。たとえば、「無限サイクル」が1つ見つかった場合、それらの「疑似無限サイクル」のループをいつ停止するかを示す最大しきい値（グローバル変数）があります。
Repeatすべてのグラフ ノードはサイクルを作成できますが、サイクルをループする反復回数を指定できる特別なノードが存在します。- 私が投稿した上記の mcve は、巡回グラフの処理方法がわからないトラバーサル アルゴリズムの反復バージョンです。理想的には、ソリューションも反復的ですが、はるかに優れた再帰的ソリューションが存在する場合、それは素晴らしいことです
- ここで話しているデータ構造は、実際には「有向非巡回グラフ」と呼ばれるべきではありません。この場合、各ノードには順序付けられた子があり、グラフではノード接続に順序がないためです。
- すべてがエディター内の何にでも接続できます。任意のブロックの組み合わせを実行できますが、唯一の制限は実行カウンターです。これは、無限ループを作成したり、反復が多すぎたりするとオーバーフローします。
- アルゴリズムは、上記のスニペットと同様に、ノードのメソッド実行の開始/中間/後を保持します。
質問
無限/有限サイクルを横断する方法を知っている何らかのソリューションを提供できる人はいますか?
参考文献
この時点でまだ疑問が明確でない場合は、この記事でこの問題について詳しく読むことができます。全体的なアイデアは、トラバーサル アルゴリズムを使用して、その記事に示されているような同様のツールを実装することです。
これは、トラバースして実行する方法を理解したい、このタイプのデータ構造の全機能を示すスクリーンショットです。
