CODEWITHSUNDEEP
pythonnetworkx
hklel
hklel

Reputation: 1634

Save NetworkX tree in newick format

I've created a graph in networkx and get its bfs tree. 

G = nx.Graph()

# build a graph

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

Now I would like to save the tree in newick format to a file. What's the best way to do this?

Upvotes: 2

Views: 1544

Answers (2)

hklel
hklel

Reputation: 1634

Inspired by this answer, I do something like this:

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, n):
    tree = {n: {}}
    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')  #'1' being the root node of the graph
tree = tree_from_edge_lst(elst, '1')
newick = tree_to_newick(tree) + ';'

Upvotes: 2

winni2k
winni2k

Reputation: 1515

Inspired by @hklel's answer, I wrote this code:

import networkx as nx

def tree_to_newick(g, root=None):
    if root is None:
        roots = list(filter(lambda p: p[1] == 0, g.in_degree()))
        assert 1 == len(roots)
        root = roots[0][0]
    subgs = []
    for child in g[root]:
        if len(g[child]) > 0:
            subgs.append(tree_to_newick(g, root=child))
        else:
            subgs.append(child)
    return "(" + ','.join(subgs) + ")"

tree_to_newick(nx.Graph(), None)

It seems to work...

Upvotes: 1

Related Questions