Python networkx 模块，bfs_tree() 实例源码

def _get_initial_list(self, graph, root):
        """We initialize a skeleton list by placing the root alone in the
        first and last sets.  Each of its successors becomes the anchor
        and root for a 'subtree set' of an initially-computed spanning tree.
        These trees make up the other initial 'set' entries in the list.
        """

        root_subtree = nx.DiGraph()
        root_subtree.add_node(root)
        self._update_bookkeeping(root_subtree, root)
        _list = [root_subtree]

        # We don't care about weights for this tree so just use BFS
        # TODO: optionally care about weights?  this would require subgraphing
        # anywhere we create a new graph using e.g. bfs_tree
        tree = nx.bfs_tree(graph, root)

        # Need a list as generator will break during iteration due to modifications
        # ORDER is arbitrary here, as is the tree construction method
        for n in list(tree.successors(root)):
            subtree = self._trim_subtree(tree, n)
            _list.append(subtree)

        return _list + [root_subtree]

def skeleton_to_swc(skeleton, offset, resolution):
    import networkx as nx

    g = nx.Graph()
    g.add_nodes_from(skeleton.nodes())
    g.add_edges_from((e.u, e.v) for e in skeleton.edges())

    # Find a directed tree for mapping to a skeleton.
    if nx.number_of_nodes(g) > 1:
        # This discards cyclic edges in the graph.
        t = nx.bfs_tree(nx.minimum_spanning_tree(g), g.nodes()[0])
    else:
        t = nx.DiGraph()
        t.add_nodes_from(g)
    # Copy node attributes
    for n in t.nodes_iter():
        loc = skeleton.locations(n)
        # skeletopyze is z, y, x (as it should be).
        loc = np.array(loc)
        loc = np.multiply(loc + offset, resolution)
        t.node[n].update({'x': loc[0],
                          'y': loc[1],
                          'z': loc[2],
                          'radius': skeleton.diameters(n) / 2.0})

    # Set parent node ID
    for n, nbrs in t.adjacency_iter():
        for nbr in nbrs:
            t.node[nbr]['parent_id'] = n
            if 'radius' not in t.node[nbr]:
                t.node[nbr]['radius'] = -1

    return [[
        node_id,
        0,
        n['x'], n['y'], n['z'],
        n['radius'],
        n.get('parent_id', -1)] for node_id, n in t.nodes(data=True)]

def fit(self, X, y=None):
        if self.assert_tree:
                assert self.root is not None
                self.hierarchy = nx.bfs_tree(self.hierarchy, self.root)
        return self