23

Pythonに組み込みのライブラリ（またはネット上の任意のライブラリ）があるかどうか疑問に思っていました。これにより、依存関係のグラフが作成されますか？私はそのようにフォーマットされたファイルを持っています

A::Requires         = ""
B::Requires     = A
C::Requires     = B
H::Requires     = A

AA::Requires         = ""
BB::Requires         = AA
C::Requires     = B

CC::Requires    = BB

理想的には、そのような木のようなものが欲しいです：

A
 +-B
   +-C
 +-H

AA
 +-BB
   +-CC

つまり、基本的に、タプル（A、B）または（A、H）を提供し、ツリーを構築するライブラリですか？そのようなライブラリが存在しない場合、そのようなことを達成するためのより簡単な方法は何でしょうか？

ありがとうございました

4

3 に答える 3

20

上記からの入力が の文字列として与えられると仮定しますraw:

import networkx as nx
import re

regex = re.compile(r'^([A-Z]+)::Requires\s+=\s([A-Z"]+)$')

G = nx.DiGraph()
roots = set()
for l in raw.splitlines():
    if len(l):
        target, prereq = regex.match(l).groups()
        if prereq == '""':
            roots.add(target)
        else:
            G.add_edge(prereq, target)

次に、ツリーを印刷します。

for s in roots:
    print s
    spacer = {s: 0}
    for prereq, target in nx.dfs_edges(G, s):
        spacer[target] = spacer[prereq] + 2
        print '{spacer}+-{t}'.format(
                                     spacer=' ' * spacer[prereq],
                                     t=target)
    print ''

これは次のように表示されます：

A
+-H
+-B
  +-C

AA
+-BB
  +-CC

これには、すべてのルートがroot::Requires = ""そのように識別されるために提示される必要があります。

于 2013-01-09T18:47:12.077 に答える
16

いくつかあるものの 1 つを試してください。

graph-tool のインストールは非常に困難です (コンパイルには大量のメモリが必要です。約 5GB の RAM と約 12 時間のコンパイルだったと思います)。

networkxはかなりまともです。

igraphのページからの引用: igraph は、無向グラフと有向グラフを作成および操作するためのフリー ソフトウェア パッケージです。これには、最小スパニング ツリーやネットワーク フローなどの古典的なグラフ理論の問題の実装が含まれており、コミュニティ構造検索などの最近のネットワーク分析手法のアルゴリズムも実装されています。

私はそれらすべてを使用してきました。それは本当に何が必要かによって異なります。依存関係のような単純なものにそれらが必要な場合は、どちらを使用するかは実際には重要ではありませんが、より短くて軽いものに必要な場合は、graph-tool を避けることをお勧めします。

于 2013-01-09T17:06:08.337 に答える