Revision history [back]

EDIT: here is a refined proposal, using a better spanning tree.

def BFS_custom(G, v):
    """
    Perform a BFS and return edges.

    Here G is a graph and v a vertex of G.

    (Code by Nathann Cohen)
    """
    seen = set([v] + G.neighbors(v))
    next_layer = [(v, u) for u in G.neighbors(v)]
    while next_layer:
        for e in next_layer:
            yield e
        next_next_layer = []
        for _, v in next_layer:
            for u in G.neighbors(v):
                if u in seen:
                    continue
                seen.add(u)
                next_next_layer.append((v, u))
        next_layer = next_next_layer

def plot_by_distance(G, v):
    """
    Plot the graph G using distance from vertex v as height function.
    """
    t = Graph([e for e in BFS_custom(G, v)])
    pos = t.layout_tree(tree_root=v)
    G.set_pos(pos)
    t.set_pos(pos)
    return G.plot() + t.plot(edge_color='red')