图形库（如NetworkX）适合我的Python问题吗？

2 投票

2 回答

980 浏览

数据工程师

提问于 2025-04-15 11:29

我正在用Python重写一个基于数据的旧应用程序。这个应用程序有一个主要的表格，叫做“图表”，看起来确实像是一个有向图，所以我在考虑使用NetworkX这个库，看看能否用它来处理这个图表，而不是用一堆复杂的数组。

不过我开始怀疑，我们使用这个表格的方式可能不太适合真正的图形处理库。NetworkX的大部分功能似乎都是用来描述图本身，比如计算两个节点之间的最短距离等等。这些功能对我的应用程序来说都没什么用。

我希望如果我能描述一下实际的使用情况，可能会有人告诉我我是不是漏掉了什么——我之前从没真正接触过图形，所以这很有可能——或者我是否应该考虑其他的数据结构。（如果是的话，你有什么建议吗？）

我们主要用这个表格把用户提供的一串关键词转换成一个有序的组件列表。这占了95%的使用场景；剩下的5%是“给定一个部分关键词字符串，提供所有可能的补全”和“生成所有可能的合法关键词字符串”。哦，还有验证图形是否有畸形。

这是表格的一个编辑过的摘录。列包括：

关键词入节点出节点组件

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

我可以仅仅用这个表格的入节点和出节点来构建一个图，但我实在想不出怎么把关键词信息融入其中，以便在面对多个选择时决定该选哪个。

更新内容，添加了其他使用场景的例子：

给定字符串“acs”，返回（“hrc”，“wfc1”）作为可能的合法下一个选择
给定字符串“acs, wfc1, foo”，由于有未使用的关键词而抛出异常
返回所有可能的合法字符串：
- cos
- acs, hrc
- acs, wfc1, f606w
- acs, wfc1, f550m
- acs, wfc1, f555w
验证所有节点是否可达，并且没有循环。

我可以调整Alex的解决方案来处理前两个场景，但我不知道怎么处理后两个场景。

数据结构图形处理最短路径有向图关键词补全节点遍历组件列表验证图形

2 个回答

我来补充一下，针对新编辑的进一步要求：我还是不建议使用通用库。对于“所有节点都可以到达且没有循环”的情况，简单地用集合的概念来推理就可以了（这里的代码虽然没测试过，但大致思路应该能帮到你，即使有些小错误也没关系）：

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"

至于“合法字符串”，你需要一些其他的代码，但我不能为你写，因为我还没搞清楚什么样的字符串算是合法的，什么又不合法...！

回答于 2025-04-15 由 Python大师

分享举报

这个方法绝对不适合用在一般的图形库上。比如说，如果输入的字符串中有多个节点的有意义的词，那该怎么办？这是错误吗？或者如果没有任何有意义的词，并且这个节点没有默认值，比如你提供的例子中的节点30，那又该如何处理呢？

你可以把这个表格写成一个字典，从节点映射到一个元组（包含默认信息和一个从词到具体信息的字典），每个信息都是一个元组（目标节点，添加的词）。在这里，clear这个特殊的“添加的词”可以用None来表示。

这样处理这个表格和输入的用逗号分隔的字符串就简单多了，得益于集合操作，比如：

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

回答于 2025-04-15 由 Python大师

分享举报

图形库（如NetworkX）适合我的Python问题吗？

2 个回答

撰写回答