GetBfsTree

GetBfsTree(Graph, StartNId, FollowOut, FollowIn)

Returns a directed Breadth-First-Search tree rooted at StartNId. The nodes in the tree correspond to those of Graph, and the edges represent the edges traversed by the breadth-first search on Graph starting from StartNId. The tree is created by traversing along out-links (parameter FollowOut = True) and/or in-links (parameter FollowIn = True).

Parameters:

  • Graph: graph (input)

    A Snap.py graph or a network.

  • StartNId: int (input)

    Id of the root node of the Breadth-First-Search tree.

  • FollowOut: bool (input)

    A bool specifying if the graph should be constructed by following the outward links.

  • FollowIn: bool (input)

    A bool specifying if the graph should be constructed by following inward links.

Return value:

  • directed graph

    A Snap.py directed graph whose nodes correspond to those of the original graph and whose edges represent the edges traversed by the breadth-first search.

The following examples show how to use GetBfsTree() with graphs of type TNGraph, TUNGraph, and TNEANet:

import snap

Graph = snap.GenRndGnm(snap.PNGraph, 100, 1000)
BfsTree = snap.GetBfsTree(Graph, 1, True, False)
for EI in BfsTree.Edges():
    print "Edge from %d to %d in generated tree." % (EI.GetSrcNId(), EI.GetDstNId())

UGraph = snap.GenRndGnm(snap.PUNGraph, 100, 1000)
BfsTree = snap.GetBfsTree(UGraph, 1, True, False)
for EI in BfsTree.Edges():
    print "Edge from %d to %d in generated tree." % (EI.GetSrcNId(), EI.GetDstNId())

Network = snap.GenRndGnm(snap.PNEANet, 100, 1000)
BfsTree = snap.GetBfsTree(Network, 1, True, False)
for EI in BfsTree.Edges():
    print "Edge from %d to %d in generated tree." % (EI.GetSrcNId(), EI.GetDstNId())