バックグラウンド：
テキスト処理のルールを書く必要があるプロジェクトに取り組んでいました。このプロジェクトに数日間取り組み、いくつかのルールを実装した後、ルールの順序を決定する必要があることに気付きました。問題ありません。トポロジカル ソートが役に立ちます。しかし、グラフが常にいっぱいになるとは期待できないことに気付きました。そこで、一連の依存関係 (または単一の依存関係) を持つ単一のルールが与えられた場合、依存関係の依存関係をチェックする必要があるという考えを思いつきました。おなじみですね。はい。この主題は、グラフの深さ優先検索に非常に似ています。
私は数学者ではありませんし、CS を勉強したこともありません。したがって、グラフ理論は私にとって新しい分野です。それにもかかわらず、私は機能するもの（以下を参照）を実装しました（非効率的だと思います）。
コード：
これが私の検索と利回りのアルゴリズムです。以下の例で実行すると、いくつかのノードに複数回アクセスすることがわかります。したがって、推測される非効率性。
インプットについて一言。私が書いたルールは基本的に、クラス プロパティを持つ python クラスdependsです。私は使用していないことで批判されましたinspect.getmro- しかし、クラスは互いに継承する必要があるため、これは事態を非常に複雑にします (こちらの例を参照)
def _yield_name_dep(rules_deps):
global recursion_counter
recursion_counter = recursion_counter +1
# yield all rules by their named and dependencies
for rule, dep in rules_deps.items():
if not dep:
yield rule, dep
continue
else:
yield rule, dep
for ii in dep:
i = getattr(rules, ii)
instance = i()
if instance.depends:
new_dep={str(instance): instance.depends}
for dep in _yield_name_dep(new_dep):
yield dep
else:
yield str(instance), instance.depends
OK、コードをじっと見つめたので、テストできる入力を次に示します。
demo_class_content ="""
class A(object):
depends = ('B')
def __str__(self):
return self.__class__.__name__
class B(object):
depends = ('C','F')
def __str__(self):
return self.__class__.__name__
class C(object):
depends = ('D', 'E')
def __str__(self):
return self.__class__.__name__
class D(object):
depends = None
def __str__(self):
return self.__class__.__name__
class F(object):
depends = ('E')
def __str__(self):
return self.__class__.__name__
class E(object):
depends = None
def __str__(self):
return self.__class__.__name__
"""
with open('demo_classes.py', 'w') as clsdemo:
clsdemo.write(demo_class_content)
import demo_classes as rules
rule_start={'A': ('B')}
def _yield_name_dep(rules_deps):
# yield all rules by their named and dependencies
for rule, dep in rules_deps.items():
if not dep:
yield rule, dep
continue
else:
yield rule, dep
for ii in dep:
i = getattr(rules, ii)
instance = i()
if instance.depends:
new_dep={str(instance): instance.depends}
for dep in _yield_name_dep(new_dep):
yield dep
else:
yield str(instance), instance.depends
if __name__ == '__main__':
# this is yielding nodes visited multiple times,
# list(_yield_name_dep(rule_start))
# hence, my work around was to use set() ...
rule_dependencies = list(set(_yield_name_dep(rule_start)))
print rule_dependencies
質問：
- 作品を分類してみましたが、DFSに似ていると思います。このように分類できますか？
- この機能を改善して、訪問したノードをスキップし、引き続きジェネレーターを使用するにはどうすればよいですか?
アップデート：
コードを実行する手間を省くために、上記の関数の出力は次のとおりです。
>>> print list(_yield_name_dep(rule_wd))
[('A', 'B'), ('B', ('C', 'F')), ('C', ('D', 'E')), ('D', None), ('E', None), ('F', 'E'), ('E', None)]
>>> print list(set(_yield_name_dep(rule_wd)))
[('B', ('C', 'F')), ('E', None), ('D', None), ('F', 'E'), ('C', ('D', 'E')), ('A', 'B')]
その間、私はより良い解決策を思いつきましたが、上記の質問はまだ残っています. したがって、私の解決策を自由に批判してください。
visited = []
def _yield_name_dep_wvisited(rules_deps, visited):
# yield all rules by their name and dependencies
for rule, dep in rules_deps.items():
if not dep and rule not in visited:
yield rule, dep
visited.append(rule)
continue
elif rule not in visited:
yield rule, dep
visited.append(rule)
for ii in dep:
i = getattr(grules, ii)
instance = i()
if instance.depends:
new_dep={str(instance): instance.depends}
for dep in _yield_name_dep_wvisited(new_dep, visited):
if dep not in visited:
yield dep
elif str(instance) not in visited:
visited.append(str(instance))
yield str(instance), instance.depends
上記の出力は次のとおりです。
>>>list(_yield_name_dep_wvisited(rule_wd, visited))
[('A', 'B'), ('B', ('C', 'F')), ('C', ('D', 'E')), ('D', None), ('E', None), ('F', 'E')]
ご覧のとおり、ノード E は 1 回だけ訪問されます。