Быстрый способ построить дерево, используя Networkx в Python?

Question

Быстрый способ построить дерево, используя Networkx в Python?

Есть ли более быстрый и приятный способ построения дерева Networkx? В настоящее время мой код

for numb in range(0,len(previous)):

    nodos = list(chunks(current,3))

        for i in range(0,3):

            G.add_edge(previous[numb],nodos[numb][i])

Это работает следующим образом: 1. Дерево имеет 3 ветви (или края). У меня есть два массива:

previous = [x,y,z] #These nodes have already been added to the graph

current = [xx,xy,xz, xy,yy,yz, xz,yz,zz] #This nodes need to be added.

В идеале я должен сделать следующее:

1. Start with x in previous:

1.1 Pick the first 3 nodes in current (i.e. xx,xy,xz)

1.1.1 Add the nodes-edges: x->xx, x->xy, x->xz

Пока мои коды делают:

1. Start with x in previous

2. Partition current into chunks of 3 items: [[xx,xy,xz], [xy,yy,yz], [xz,yz,zz]]

3. Loop through all the nodes in these chunks:

4. Add x->xx, loop again, add x->xy... etc.

Моя реализация крайне неэффективна. Как бы вы это сделали эффективно? СПАСИБО

577 1

python numpy networkx

1 ответ:

Comments

Ничего не найдено.

Aric · Accepted Answer · 2014-11-14 06:15:09

Можно использовать вспомогательную функцию из https://github.com/networkx/networkx/blob/master/networkx/generators/classic.py#L50

def _tree_edges(n,r):
    # helper function for trees
    # yields edges in rooted tree at 0 with n nodes and branching ratio r
    nodes=iter(range(n))
    parents=[next(nodes)] # stack of max length r
    while parents:
        source=parents.pop(0)
        for i in range(r):
            try:
                target=next(nodes)
                parents.append(target)
                yield source,target
            except StopIteration:
                break

print list(_tree_edges(13,3))
#[(0, 1), (0, 2), (0, 3), (1, 4), (1, 5), (1, 6), (2, 7), (2, 8), (2, 9), (3, 10), (3, 11), (3, 12)]
import networkx as nx
G = nx.Graph(_tree_edges(13,3))

Если вам нужны узлы, отличные от целых чисел, вы можете либо переставить метки, либо указать их на входе, как это

def _tree_edges(nodes,r):
    # helper function for trees
    # yields edges in rooted tree with given nodes and branching ratio r
    nodes=iter(nodes)
    parents=[next(nodes)] # stack of max length r
    while parents:
        source=parents.pop(0)
        for i in range(r):
            try:
                target=next(nodes)
                parents.append(target)
                yield source,target
            except StopIteration:
                break

nodes = list('abcdefghijklm')
print list(_tree_edges(nodes,3))