pretty_networks.py

""" script to visualize some random graphs that are nice to draw"""

import networkx as nx
import pylab as pl

n = 100 # number of vertices                                                                                                                                                     
rc = .25 # critical radius for geometric graph                                                                                                                                   
rr = .05 # repel radius for hard-core model                                                                                                                                      
p = .25 # edge percolation probability                                                                                                                                           

G = nx.random_geometric_graph(n, rc, repel=rr)
X = pl.array([G.pos[i] for i in range(n)])

## percolate edges of G                                                                                                                                                          
H = nx.Graph()
for u,v in G.edges():
    if pl.rand() <= p:
        H.add_edge(u,v)


## find shortest path tree                                                                                                                                                       
import random
from shortest_path_tree import shortest_path_tree
root = H.nodes()[0]
dests = random.sample(H.nodes(), 10)
T = shortest_path_tree(H, root, dests)


## plot networks                                                                                                                                                                 
pl.clf()
pl.subplots_adjust(left=.01,bottom=.01,right=.99,top=.99,wspace=0,hspace=0)

params = dict(x=.5, y=-.05, va='bottom', ha='center')

pl.subplot(2,2,1)
pl.text(s='a) random points, with minimum distance %.2f' % rr, **params)
pl.plot(X[:,0], X[:,1], 'o', mew=0)


pl.subplot(2,2,2)
pl.text(s='b) geometric graph, with connectivity distance %.2f' % rc, **params)
pl.plot(X[:,0], X[:,1], 'o', mew=0)
nx.draw_networkx_edges(G, G.pos, alpha=.5)

pl.subplot(2,2,3)
pl.text(s='c) edges percolated with probability %.2f' % p, **params)
pl.plot(X[:,0], X[:,1], 'o', mew=0)
nx.draw_networkx_edges(H, G.pos, alpha=.5)


pl.subplot(2,2,4)
pl.text(s='d) shortest path tree on random subset of random graph', **params)

pl.plot(X[root,0], X[root,1], 'o', mfc='b', mew=5, mec='k')
pl.plot(X[dests,0], X[dests,1], 'o', mfc='b', mew=5, mec='g')
nx.draw_networkx_edges(T, G.pos, width=3, alpha=1, edge_color='r')

pl.plot(X[:,0], X[:,1], 'bo', mew=0)
nx.draw_networkx_edges(H, G.pos, alpha=.5)


## clean up figures                                                                                                                                                              
for ii in range(4):
    pl.subplot(2,2,ii+1)
    pl.axis([-.05, 1.05, -.05, 1.05])
    pl.xticks([])
    pl.yticks([])

shortest_path_tree.py

from networkx import *
from pylab import *

def add_path(G, path):
    """                                                                         
    Add edges joining all vertices in path to G.                                
    """

    u = path[0]
    for v in path[1:]:
        G.add_edge(u,v)
        u=v

def shortest_path_tree(G, root, dests):
    """                                                                         
    Return a graph of edges that appear in the shortest paths from a            
    given root to nodes of G.                                                   
                                                                                
    If destination vector, dests, is given, then return the union of            
    the paths to these destination nodes, and otherwise return the              
    whole tree.                                                                 
    """

    T = Graph()
    T.add_nodes_from(G.nodes_iter())

    paths = single_source_dijkstra_path(G, root)

    for v in dests:
        if paths.has_key(v):
            add_path(T, paths[v])

    return T