Создание диаграммы дерева.graphml из вложенного списка

Question

Я отчаянно ищу решение для создания хорошей бинарной древовидной диаграммы. Крайне важно, чтобы незавершенные узлы имели различимые ребра (если они есть).

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

То, к чему я стремлюсь, - это инструмент, который генерирует, например, формат.graphml из минималистических данных, таких как (A (B1 C1 C2) B2), где A - корневая метка, B1 - левый дочерний элемент корня с двумя другими дочерними элементами. Сложность, аналогичная.dot или.tgf, конечно, была бы приемлемой, но я не хочу писать сам компилятор для генерации.graphml.

Любые идеи приветствуются.

Маркус Р.

Answer 1

Предоставленные вами данные более или менее являются s-выражением. Учитывая, что это формат, который вы хотите принять, pyparsing (модуль Python) имеет синтаксический анализатор s-выражений.

Вам также понадобится библиотека графов. Я использую networkx для большей части моей работы. С помощью синтаксического анализатора pyparsing s-expression и networkx следующий код принимает данные и создает дерево в виде орграфа:

import networkx as nx

def build(g, X):
    if isinstance(X, list):
        parent = X[0]
        g.add_node(parent)
        for branch in X[1:]:
            child = build(g, branch)
            g.add_edge(parent, child)

        return parent

    if isinstance(X, basestring):
        g.add_node(X)
        return X

#-- The sexp parser is constructed by the code example at...
#-- http://http://pyparsing.wikispaces.com/file/view/sexpParser.py
sexpr = sexp.parseString("(A (B1 C1 C2) B2)", parseAll = True)

#-- Get the parsing results as a list of component lists.
nested = sexpr.asList( )

#-- Construct an empty digraph.
dig = nx.DiGraph( )

#-- build the tree
for component in nested:
    build(dig, component)

#-- Write out the tree as a graphml file.
nx.write_graphml(dig, 'tree.graphml', prettyprint = True)

Чтобы проверить это, я также написал дерево в виде файла.dot и использовал graphviz для создания следующего изображения:

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