Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
""" 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([])
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.