BFS.py

""" Applications of breadth-first search of (directed) graph G.
    
    Prints distances from starting vertex to all other vertices in G and prints distance from starting vertex to ending vertices.
    Tests if G is undirected.
    If G is undirected, counts connected components of G.
"""

from sys import argv
from collections import deque

def distances(G, s):
    seen = [False] * len(G)
    dists = [float('inf')] * len(G)
    seen[s - 1], dists[s - 1] = True, 0
    Q = deque([s])
    while len(Q) != 0:
        v = Q.popleft()
        for w in G[v]:
            if not seen[w - 1]:
                seen[w - 1], dists[w - 1] = True, dists[v - 1] + 1
                Q.append(w)
    return dists

def BFS(G, seen, start):
    seen[start - 1] = True
    Q = deque([start])
    while len(Q) != 0:
        v = Q.popleft()
        for w in G[v]:
            if not seen[w - 1]:
                seen[w - 1] = True
                Q.append(w)
    return seen

def BFS_distances_optional(G, seen, start, compute_distance=False):
    seen = [False] * len(G)
    seen[start - 1] = True
    if compute_distance:
        dists = [float('inf')] * len(G)
        dists[start - 1] = 0
    Q = deque([start])
    while len(Q) != 0:
        v = Q.popleft()
        for w in G[v]:
            if not seen[w - 1]:
                seen[w - 1] = True
                if compute_distance:
                    dists[w - 1] = dists[v - 1] + 1
                Q.append(w)
    return seen, dists

def count_connected_components(G):
    # only makes sense if G is undirected
    n = len(G)
    seen = [False] * n
    counter = 0
    for i in range(1, n + 1):
        if not seen[i - 1]:
            seen = BFS(G, seen, i)
            counter += 1
    return counter

def is_undirected(G):
    lookup = {}
    for vertex in G:
        lookup[vertex] = set(G[vertex])
    for vertex in G:
        for adj_vert in lookup[vertex]:
            if vertex not in lookup[adj_vert]:
                return False
    return True

def get_graph(filename):
    graph = {}
    with open(filename) as f:
        for line in f:
            x = map(int, line.split())
            vertex, out_verts = x[0], x[1:]
            graph[vertex] = out_verts
    return graph

def main():
    filename, ends = argv[1], map(int, argv[2:])
    start = ends.pop(0)
    G = get_graph(filename)
    dists = distances(G, start)
    print dists
    for end in ends:
        print "Distance from %s to %s is %.0f." % (start, end, dists[end - 1])
    if is_undirected(G):
        print "G is undirected and has %d connected components." % count_connected_components(G)
    else:
        print "G is a directed graph."

if __name__ == '__main__':
    main()