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

Question

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

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

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

Любые идеи оценили.

Маркус Р.

Answer 1

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

Вам также понадобится библиотека графов. Я использую networkx для большей части моей работы. С Pyparsing S-выражение, синтаксический анализатор и 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 хорошая библиотека график, и вы можете писать дополнительный код, который идет над деревом, чтобы пометить края или узлы с дополнительными метаданными, если это необходимо.