グラフライブラリ（NetworkXなど）はPythonの問題の正しい解決策ですか？

Question

私はPythonでデータ駆動レガシーアプリケーションを書き直しています。プライマリテーブルの1つは「グラフテーブル」と呼ばれ、有向グラフのように見えるので、NetworkXパッケージを使用してグラフテーブルの操作に使用することが理にかなっているかどうかを調べています複雑な配列のセットではなく、グラフとして表示されます。

しかし私たちは、この表を使用する方法は、実際のグラフの操作ライブラリのためにあまり適していないかどうかを疑問に思い始めています。 NetworkXの機能性の大部分は、グラフ自体を何らかの形で特徴づけること、2つのノード間の最短距離を決定すること、およびそのようなものに向けられているようです。それは私のアプリケーションには関係しません。

私は願っています、私はここに実際の使用状況を記述することができる場合、私はちょうど何かが欠けてるかどうか、誰かが私に助言することができます - 私はべきかどうか - 私は本当にそう、これはかなり可能である前に、グラフで働いたことがありません他のデータ構造を探求しているかもしれません。 （もしそうなら、あなたは何を示唆している？）

私たちは、コンポーネントの順序付きリストにキーワードをユーザーが指定された文字列を変換するために、主にテーブルを使用します。これはユースケースの95％を占めます。残りの5％は「部分的なキーワード文字列を与えられ、すべての可能な補完を提供する」と「可能なすべての有効なキーワード文字列を生成する」である。ああ、奇形に対してグラフを検証する。

編集した表の抜粋です。列は次のとおりキーワード文字列 "ACS、wfc1、f555w" このテーブルを考える

キーワードinnodeのoutnode成分

acs 1 20 clear 
default 1 100 clear 
noota 20 30 clear 
default 20 30 hst_ota 
ota 20 30 hst_ota 
acs 30 10000 clear 
cos 30 11000 clear 
sbc 10000 10199 clear 
hrc 10000 10150 clear 
wfc1 10000 10100 clear 
default 10100 10101 clear 
default 10101 10130 acs_wfc_im123 
f606w 10130 10140 acs_f606w 
f550m 10130 10140 acs_f550m 
f555w 10130 10140 acs_f555w 
default 10140 10300 clear 
wfc1 10300 10310 acs_wfc_ebe_win12f 
default 10310 10320 acs_wfc_ccd1 

、トラバースロジックは：ノード1の

• スタート。 「ACSは、」文字列であるので、ノード20のために提示されたキーワードの20

• なし文字列にないノードに移動するので、デフォルトを選択し、hst_otaをピックアップして、ノードにアクセスしてください30.

• 「ACS」は文字列であり、そのノードに移動10000

• 「wfc1は」文字列であるので、ノードつだけ選択10100

• に移動します。ノード10101

• つだけ選択に行くので、acs_wfc_im123をピックアップし、ノードに移動10130.

• 「f555wは、」文字列であるので、acs_f555wをピックアップし、ノードに移動10140.

• は唯一の選択肢なので、10300.

• 「wfc1は」文字列であるので、acs_wfc_ebe_win12fをピックアップし、ノード10310.

• つだけ選択に行くので、選ぶのノードにアクセスしてくださいacs_wfc_ccd1を立ち上げ、存在しないノード10320に行きましょう。これで完了です。

したがって部品の最終的なリストは

hst_ota 
acs_wfc_im123 
acs_f555w 
acs_wfc_ebe_win12f 
acs_wfc_ccd1 

である私は、この表のちょうどinnodesとoutnodesからグラフを作ることができますが、私は私の人生のためにどのように見つけ出すことができませんでした複数の可能性に直面した場合にどの選択をするかを決めるキーワード情報を構築する。

は、他の使用例例を追加する更新：

• 与えられた文字列 "ACS"、リターン（ "HRC"、 "wfc1"）として可能な法的次の選択肢

• を考えます文字列 "ACS、wfc1、foo" という、原因未使用のキーワード

• 戻る可能なすべての法的な文字列に例外を発生させる：

  の
  • COS
  • ACS、
  • ACS、wfc1、f550m
  • ACS、wfc1、

• f555wすべてのノードに到達し、そこでそのすることができることを検証f606w HRC

• ACS、wfc1、ループはありません。

私はアレックスのソリューションを最初の2つについて微調整できますが、最後の2つの方法はわかりません。

Answer 1

一般的なグラフライブラリにはまったく適していません（ノード内で意味のある単語が入力文字列内に複数存在する場合は、それはエラーですか？あなたが提供する例ではノード30のように、ノードのデフォルトはありません）。ノードからタプルへのディクショナリとして表を書くだけです（デフォルトのもの、単語から特定のものへの指示）。それぞれのものはタプル（宛先、ワード・ツー・アド）です（特別な「ワード・ツー・アドオン"clear）。だから、例えば：

tab = {1: (100, None), {'acs': (20, None)}), 
     20: ((30, 'hst_ota'), {'ota': (30, 'hst_ota'), 'noota': (30, None)}), 
     30: ((None, None), {'acs': (10000,None), 'cos':(11000,None)}), 
     etc etc 

今すぐ操作を設定するには簡単ですが、おかげでこのテーブルと入力カンマ区切りの文字列を扱う - 例えば：

def f(icss): 
    kws = set(icss.split(',')) 
    N = 1 
    while N in tab: 
    stuff, others = tab[N] 
    found = kws & set(others) 
    if found: 
     # maybe error if len(found) > 1 ? 
     stuff = others[found.pop()] 
    N, word_to_add = stuff 
    if word_to_add is not None: 
     print word_to_add 

Answer 2

新しく編集された更なる要件に対応するための答えを追加しますin ...：私はまだ汎用ライブラリに行くつもりはありません。 「すべてのノードに到達してループがありません」という理由で、（テストされていないコードがありますが）一般的なアウトラインは、タイプが& cの場合でも役立ちます：

def add_descendants(someset, node): 
    "auxiliary function: add all descendants of node to someset" 
    stuff, others = tab[node] 
    othernode, _ = stuff 
    if othernode is not None: 
    someset.add(othernode) 
    for othernode, _ in others.values(): 
    if othernode is not None: 
     someset.add(othernode) 

def islegal(): 
    "Return bool, message (bool is True for OK tab, False if not OK)" 
    # make set of all nodes ever mentioned in the table 
    all_nodes = set() 
    for node in tab: 
    all_nodes.add(node) 
    add_desendants(all_nodes, node) 

    # check for loops and connectivity 
    previously_seen = set() 
    currently_seen = set([1]) 
    while currently_seen: 
    node = currently_seen.pop() 
    if node in previously_seen: 
     return False, "loop involving node %s" % node 
    previously_seen.add(node) 
    add_descendants(currently_seen, node) 

    unreachable = all_nodes - currently_seen 
    if unreachable: 
    return False, "%d unreachable nodes: %s" % (len(unreachable), unreachable) 
    else: 
    terminal = currently_seen - set(tab) 
    if terminal: 
     return True, "%d terminal nodes: %s" % (len(terminal), terminal) 
    return True, "Everything hunky-dory" 

"法的な文字列"については、他のコードが必要ですが、文字列を合法的にするかどうかまだ理解していないので、私はあなたのために書くことができません。