python - 以 newick 格式保存 NetworkX 树

Question

我在 networkx 中创建了一个图并获取了它的 bfs 树。

G = nx.Graph()

# build a graph

tree = nx.bfs_tree(G, '1')

现在我想把树保存在newick format中到一个文件。执行此操作的最佳方法是什么？

Answer 1

灵感来自 this answer ，我做这样的事情:

import networkx as nx
import matplotlib.pyplot as plt

def recursive_search(dict, key):
    if key in dict:
        return dict[key]
    for k, v in dict.items():
        item = recursive_search(v, key)
        if item is not None:
            return item

def bfs_edge_lst(graph, n):
    return list(nx.bfs_edges(graph, n))

def load_graph(filename):
    G = nx.Graph()
    # build the graph
    return G

def tree_from_edge_lst(elst):
    tree = {'1': {}}
    for src, dst in elst:
        subt = recursive_search(tree, src)
        subt[dst] = {}
    return tree

def tree_to_newick(tree):
    items = []
    for k in tree.keys():
        s = ''
        if len(tree[k].keys()) > 0:
            subt = tree_to_newick(tree[k])
            if subt != '':
                s += '(' + subt + ')'
        s += k
        items.append(s)
    return ','.join(items)

g = load_graph('dataset.txt')
elst = bfs_edge_lst(g, '1')
tree = tree_from_edge_lst(elst)
newick = tree_to_newick(tree) + ';'