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

Я переписываю устаревшее приложение, управляемое данными, на 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

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

Обновлено, чтобы добавить примеры других вариантов использования:

  • Учитывая строку «acs», вернуть («hrc», «wfc1») в качестве возможного следующего варианта

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

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

    • cos
    • акк, час
    • ас, wfc1, f606w
    • ас, wfc1, f550m
    • ас, wfc1, f555w

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

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


python graph
person Vicki Laidler    schedule 10.05.2009    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Определенно не подходит для библиотек графов общего назначения (независимо от того, что вы должны делать, если во входной строке присутствует более одного слова, имеющего смысл в узле - это ошибка? - или если нет и нет значения по умолчанию для узла, как для узла 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
person Alex Martelli    schedule 10.05.2009
comment
Спасибо Алекс! Это очень полезно для варианта использования обхода. Однако я не уверен в других случаях - см. обновления выше. В частности, мне интересно, будет ли графическая библиотека применима в случае проверки? - person Vicki Laidler; 12.05.2009
comment
У меня наконец-то появилась возможность снова поработать над этим проектом на этой неделе, и я понял, что никогда не принимал ваш очень полезный ответ! Спасибо еще раз. - person Vicki Laidler; 25.03.2010

arrow_upward
0
arrow_downward

Добавление ответа, чтобы ответить на новые требования, недавно отредактированные в...: я бы все равно не пошел на библиотеку общего назначения. Для «все узлы могут быть достигнуты и нет циклов», следует просто рассуждать с точки зрения наборов (игнорируя ключевые слова запуска): (опять же непроверенный код, но общий план должен помочь, даже если есть опечатка и т. д.):

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"

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

person Alex Martelli    schedule 12.05.2009