2

我正在用 Python 重写一个数据驱动的遗留应用程序。其中一个主表被称为“图形表”，并且看起来确实是有向图，所以我正在探索 NetworkX 包，看看将它用于图形表操作是否有意义，并真正实现它是一个图形，而不是一组复杂的数组。

但是，我开始怀疑我们使用此表的方式是否不适合实际的图形操作库。NetworkX 的大部分功能似乎都倾向于以某种方式表征图本身，确定两个节点之间的最短距离，诸如此类。这些都与我的申请无关。

我希望如果我可以在这里描述实际用法，有人可以告诉我我是否只是遗漏了一些东西——我以前从未真正使用过图表，所以这是很有可能的——或者我是否应该探索其他一些东西数据结构。（如果是这样，你有什么建议？）

我们主要使用该表将用户提供的关键字字符串转换为组件的有序列表。这构成了 95% 的用例；其他 5% 是“给定部分关键字字符串，提供所有可能的补全”和“生成所有可能的合法关键字字符串”。哦，并验证图表是否存在畸形。

这是该表的编辑摘录。列是：

关键字 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

给定关键字字符串“acs,wfc1,f555w”和这个表，遍历逻辑是：

  • 从节点 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”，由于未使用的关键字引发异常

  • 返回所有可能的合法字符串：

    • 因
    • acs, 人力资源委员会
    • acs, wfc1, f606w
    • acs, wfc1, f550m
    • acs, wfc1, f555w

  • 验证所有节点都可以到达并且没有循环。

我可以为其中的前两个调整 Alex 的解决方案，但我不知道如何为最后两个做。

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 回答