Является ли библиотека графов (например, NetworkX) правильным решением для моей проблемы с Python?

Question

Я переписываю управляемое данными старое приложение на Python. Одна из основных таблиц называется «графовой таблицей» и, по-видимому, является ориентированным графом, поэтому я изучал пакет NetworkX, чтобы выяснить, имеет ли смысл использовать его для манипуляций с графической таблицей, и действительно реализовать это как график, а не сложный набор массивов.

Однако я начинаю задаваться вопросом, подходит ли способ, которым мы используем эту таблицу, для реальной библиотеки манипулирования графами. Большая часть функциональности NetworkX, по-видимому, ориентирована на то, чтобы каким-то образом характеризовать сам график, определять кратчайшее расстояние между двумя узлами и тому подобное. Ничто из этого не имеет отношения к моему заявлению.

Я надеюсь, что если я смогу описать фактическое использование здесь, кто-то может посоветовать мне, если я просто что-то упустил - я никогда раньше не работал с графиками, так что это вполне возможно - или если мне следует исследовать некоторые другие структуры данных. (А если так, что бы вы предложили?)

Мы используем таблицу главным образом для преобразования предоставленной пользователем строки ключевых слов в упорядоченный список компонентов. Это составляет 95% случаев использования; остальные 5% «даны частичная строка ключевого слова, содержат все возможные дополнения» и «генерируют все возможные допустимые строки ключевого слова». Да, и проверьте график на наличие пороков развития.

Вот отредактированная выдержка из таблицы. Столбцы:

ключевое слово innode outnode component

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", return ("hrc", "wfc1") в качестве возможных допустимых следующих вариантов

• Учитывая строку "acs, wfc1, foo", вызвать исключение из-за неиспользуемого ключевого слова

• Вернуть все возможные юридические строки:

  • соз
  • ACS, HRC
  • ACS, WFC1, F606W
  • ACS, WFC1, F550M
  • ACS, WFC1, F555W

• Убедитесь, что все узлы доступны и петли отсутствуют.

Я могу настроить решение Алекса для первых двух из них, но я не вижу, как это сделать для последних двух.

Answer 1

Определенно не подходит для библиотек графов общего назначения (что бы вы ни делали, если во входной строке содержится более одного слова, значащего в узле, - это ошибка? не является значением по умолчанию для узла, как для узла 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

Answer 2

Добавление ответа для ответа на новые требования, вновь отредактированные в ...: Я все еще не пошел бы на библиотеку общего назначения. Поскольку «все узлы могут быть достигнуты и циклов нет», простое рассуждение с точки зрения наборов (игнорируя инициирующие ключевые слова) должно сделать: (опять непроверенный код, но общий план должен помочь, даже если есть некоторая опечатка & 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"

Для "допустимых строк" вам понадобится другой код, но я не могу написать его для вас, потому что я еще не понял, что делает строку допустимой или нет ...!