2

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

ただし、このテーブルの使用方法が実際のグラフ操作ライブラリにあまり適していないかどうか疑問に思い始めています。NetworkX機能のほとんどは、グラフ自体を何らかの方法で特徴付けたり、2つのノード間の最短距離を決定したりすることを目的としているようです。それは私のアプリケーションには関係ありません。

ここで実際の使用法を説明できれば、誰かが私に何かが足りないのかどうかを教えてくれることを願っています-私はこれまでグラフを実際に操作したことがないので、これはかなり可能です-または他の何かを探索する必要があるかどうかデータ構造。（もしそうなら、あなたは何を提案しますか？）

この表は主に、ユーザーが指定したキーワードの文字列をコンポーネントの順序付きリストに変換するために使用します。これはユースケースの95％を構成します。他の5％は、「部分的なキーワード文字列を指定し、可能なすべての補完を提供する」および「すべての可能な有効なキーワード文字列を生成する」です。ああ、そして奇形に対してグラフを検証します。

これが表の編集された抜粋です。列は次のとおりです。

キーワードinnodeoutnodeコンポーネント

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

キーワード文字列「acs、wfc1、f555w」とこのテーブルが与えられると、トラバーサルロジックは次のようになります。

  • ノード1から開始します。「acs」は文字列に含まれているため、ノード20に移動します。

  • ノード20に提示されたキーワードはいずれも文字列に含まれていないため、デフォルトを選択し、hst_otaを選択して、ノード30に移動します。

  • 「acs」は文字列に含まれているため、ノード10000に移動します。

  • 「wfc1」は文字列に含まれているため、ノード10100に移動します。

  • 唯一の選択肢。ノード10101に移動します。

  • 選択肢は1つだけなので、acs_wfc_im123を選択して、ノード10130に移動します。

  • 「f555w」は文字列に含まれているため、acs_f555wを取得して、ノード10140に移動します。

  • 選択肢は1つだけなので、ノード10300に移動します。

  • 「wfc1」は文字列に含まれているため、acs_wfc_ebe_win12fを取得して、ノード10310に移動します。

  • 選択肢は1つだけなので、acs_wfc_ccd1を選択して、ノード10320に移動します。これは存在しません。これで完了です。

したがって、コンポーネントの最終的なリストは次のようになります。

hst_ota
acs_wfc_im123
acs_f555w
acs_wfc_ebe_win12f
acs_wfc_ccd1

このテーブルのインノードとアウトノードだけからグラフを作成することはできますが、複数の可能性に直面したときにどちらを選択するかを決定するキーワード情報を組み込む方法を一生理解できませんでした。

他のユースケースの例を追加するために更新されました。

  • 文字列"acs"が与えられた場合、可能な正当な次の選択肢として（ "hrc"、 "wfc1"）を返します。

  • 文字列「acs、wfc1、foo」を指定すると、未使用のキーワードが原因で例外が発生します

  • 可能なすべての有効な文字列を返します。

    • cos
    • acs、hrc
    • acs、wfc1、f606w
    • acs、wfc1、f550m
    • acs、wfc1、f555w

  • すべてのノードに到達できること、およびループがないことを検証します。

これらの最初の2つについてはAlexのソリューションを微調整できますが、最後の2つについてはそれを行う方法がわかりません。

4

2 に答える 2

2

汎用のグラフ ライブラリには絶対に適していません (ノードで意味のある複数の単語が入力文字列に含まれている場合、何をすべきか - それはエラーですか? - または、エラーが発生せず、デフォルトがない場合)。ノードの場合、指定した例のノード 30 のように)。ノードからタプルへの辞書 (デフォルトのもの、単語から特定のものへの辞書) としてテーブルを書くだけです。ここで、各要素はタプル (宛先、追加する単語) です (そして、特別な「追加する単語」には None を使用します)。 " 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
于 2009-05-10T16:57:30.567 に答える
0

で新しく編集されたさらなる要件に対応するための回答を追加する...: 私はまだ汎用ライブラリには行きません。「すべてのノードに到達でき、ループがない」場合は、単にセットに関する推論 (トリガー キーワードを無視する) を行う必要があります: (ここでもテストされていないコードですが、タイプミス &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"

「正当な文字列」については、他のコードが必要になりますが、文字列が正当またはそうでない理由をまだ理解していないため、それを書くことはできません...!

于 2009-05-12T07:13:35.890 に答える