Breadth First Search in Python

In [1]:

    

# this line makes the code compatible with Python 2 and 3
from __future__ import print_function, division

# this line makes Jupyter show figures in the notebook
%matplotlib inline


    

In [2]:

    

from collections import deque

def bfs(G, start):
    """A simple version of BFS that just computes distances.
    
    G: Graph
    start: int start node
    
    returns: map from node to distance
    """
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()         
        for child in G.neighbors(node):
            if child not in dist:                    
                dist[child] = dist[node] + 1
                queue.append(child)
    return dist


    

In [3]:

    

from networkx import DiGraph

def bfs(G, start):
    """A simple version of BFS that computes distances and
        paths back to start.
    
    G: Graph
    start: int start node
    
    returns: (map from node to distance,
        DiGraph containing paths from each node back to start)
    """
    dist = {start: 0}
    tree = DiGraph()
    queue = deque([start])
    while queue:
        node = queue.popleft()         
        for child in G.neighbors(node):
            if child not in dist:                    
                dist[child] = dist[node] + 1
                tree.add_edge(child, node) 
                queue.append(child)
    return dist, tree


    

In [4]:

    

from numpy.random import random

def flip(p):
    return random() < p


    

In [5]:

    

def random_pairs(nodes, p):
    """Generate random pairs of nodes."""
    for i, u in enumerate(nodes):
        for j, v in enumerate(nodes):
            if i<j and flip(p):
                yield u, v


    

In [6]:

    

import networkx as nx

def make_random_graph(n, p):
    """Generate a random graph.
    
    n: number of nodes
    p: probability of an edge between any pair of nodes
    
    returns: Graph
    """
    G = nx.Graph()
    nodes = range(n)
    G.add_nodes_from(nodes)
    G.add_edges_from(random_pairs(nodes, p))
    return G


    

In [7]:

    

random_graph = make_random_graph(10, 0.3)
len(random_graph.edges())


    

    
Out[7]:





12

In [8]:

    

import seaborn as sns
COLORS = sns.color_palette()

nx.draw_circular(random_graph, 
                 node_color=COLORS[2], 
                 node_size=1000, 
                 with_labels=True)


    

In [9]:

    

dist, tree = bfs(random_graph, 0)
dist


    

    
Out[9]:





{0: 0, 1: 3, 2: 3, 3: 1, 4: 3, 5: 2, 6: 2, 7: 1, 8: 2, 9: 1}

In [10]:

    

nx.draw_circular(tree, 
                 node_color=COLORS[2], 
                 node_size=1000, 
                 with_labels=True)


    

In [11]:

    

def fft(ys):
    N = len(ys)
    if N == 1:
        return ys
    
    He = fft(ys[::2])
    Ho = fft(ys[1::2])
    
    ns = np.arange(N)
    W = np.exp(-1j * PI2 * ns / N)
    
    return np.tile(He, 2) + W * np.tile(Ho, 2)


    

In [ ]: