Find file
Fetching contributors…
Cannot retrieve contributors at this time
200 lines (152 sloc) 6.21 KB
from random import randint, choice
import math
import random
import networkx as nx
import pickle
from os import path
import sys
from algorithms import dijkstra
def print_header(name, n, m):
head = "%32s | %12s | %21s | %21s" % ('algorithm', 'distance', 'settled', 'relaxed')
print ''
print "Graph: %s (vertices: %d, edges: %d)" % (name, n, m)
print '-' * len(head)
print head
print '-' * len(head)
sys.stdout.flush()
def print_result(name, res, base_result, n, m):
d, _n, _m = res
_, n, m = base_result
print "%32s | %12.2f | %12d (%5.1f%%) | %12d (%5.1f%%)" %\
(name, d, _n, 100 * float(_n)/n, _m, 100 * float(_m)/m)
sys.stdout.flush()
def build_graph(size=0, expected_neighbors=0, reverse_chance=0.9, min_weight=1, max_weight=3):
"""Build the graph
Parameters:
*size*
The number of nodes to be in the graph
*expected_neighbors*
The expected degree of each node in the graph
"""
# Calculate the distance required to yield the expected # neighbors
if size == 1:
radius = 1
else:
radius = math.sqrt( (expected_neighbors / (size - 1.0)) / math.pi)
# Create bins in which to put node so we only check a fraction of
# candidate neighbors
num_bins = int(math.ceil(1/radius))
neighbor_bins = []
for i in range(num_bins):
neighbor_bins.append([])
for j in range(num_bins):
neighbor_bins[i].append([])
G = nx.DiGraph()
G.name = "Nice Digraph"
G.add_nodes_from(list(range(size)))
# Create the collection of nodes and put them into bins with
# candidate neighbors
_rndm = random.random
_rndint = random.randint
_flr = math.floor
for n in G.nodes():
xcoord = _rndm()
ycoord = _rndm()
G.node[n]['coords'] = (xcoord, ycoord)
# Put node into bin with candidate neighbors
bin_x = int(_flr(xcoord/radius))
bin_y = int(_flr(ycoord/radius))
neighbor_bins[bin_x][bin_y].append(n)
# Find actual neighbors and create edges between nodes
for x in range(num_bins):
for y in range(num_bins):
# Get all potential neighbors (those in adjacent bins)
potentials = []
for px in range(x-1, x+1+1):
if px < 0 or px >= num_bins:
continue
for py in range(y-y, y+1+1):
if py < 0 or py >= num_bins:
continue
potentials += neighbor_bins[px % num_bins][py % num_bins]
for node in neighbor_bins[x][y]:
node_coords = G.node[node]['coords']
for potential in potentials:
p_coords = G.node[potential]['coords']
dist = ((node_coords[0] - p_coords[0])**2 + (node_coords[1] - p_coords[1]) ** 2)**0.5
if dist < radius and node != potential:
weight = (min_weight + _rndm()* max_weight) * dist
G.add_edge(node, potential, weight=weight)
if _rndm() <= reverse_chance:
G.add_edge(potential, node, weight=weight)
if G.degree(node) == 0:
G.remove_node(node)
neighbor_bins[x][y].remove(node)
neighbor_bins[x][y] = []
return G
def generate_g(file_name, nodes=10000):
#seed = nx.generators.random_graphs.random_regular_graph(4, 80000)
seed = build_graph(nodes, 8)
edges = [ (u, v, data['weight'] * nodes) for (u, v, data) in seed.edges(data=True) ]
g = nx.DiGraph()
for (u, v, w) in edges:
g.add_edge(u,v, weight=w)
s = g.nodes()[0]
cover, distances = dijkstra(g, s)
t = choice(cover.nodes())
reachable = dict((node, True) for node in cover.nodes())
edges= [ (u, v, w) for (u,v,w) in edges if u in reachable and v in
reachable ]
nodes = [ (node, seed.node[node]['coords'][0] * nodes,
seed.node[node]['coords'][1] * nodes) for node in cover.nodes() ]
with open(file_name, 'a') as file:
pickle.dump((nodes, edges, s), file)
def get_graph(name, size=10000):
file_name = "graphs/graph_%s_%d" % (name, size)
g = nx.DiGraph()
# random.seed(5)
if not path.exists(file_name):
sys.stdout.write("generating ... ")
sys.stdout.flush()
generate_g(file_name, nodes=size)
sys.stdout.write("done\n")
sys.stdout.flush()
with open(file_name) as file:
sys.stdout.write("loading ... ")
sys.stdout.flush()
nodes, edges, s = pickle.load(file)
sys.stdout.write("done\n")
sys.stdout.flush()
sys.stdout.write("constructing ... ")
sys.stdout.flush()
g.add_nodes_from(((node, {'x': x, 'y': y}) for (node, x, y) in nodes))
for (u,v,w) in edges:
g.add_edge(u,v, weight=w)
n, m = len(g.nodes()), len(g.edges())
sys.stdout.write("done\n")
sys.stdout.flush()
return g, n, m, s
def get_targets(g, s, ranks):
_, distances = dijkstra(g, s)
distances = distances.items()
distances.sort(key=lambda (x,y): y)
targets = [ (distances[r][0], r) for r in ranks]
return targets
def draw(title, graph, s, ts, search_spaces=list()):
from matplotlib import pylab
fig = pylab.figure()
fig.canvas.set_window_title(title)
import matplotlib.pyplot as plt
#pos = nx.graphviz_layout(graph, prog='dot')
layout = dict(((node, (graph.node[node]['x'], graph.node[node]['y'])) for
node in graph.nodes()))
graph = nx.Graph(graph)
nx.draw(graph, layout, node_color='black', with_labels=False, node_size=2)
colors = [ 'cyan', 'orange', 'y', 'g', 'purple', 'brown']
for i, search_space in enumerate(search_spaces):
nx.draw_networkx_nodes(graph, layout, nodelist=search_space, node_color=colors[i], node_size=100)
nx.draw_networkx_nodes(graph, layout, nodelist=[s], node_color='r', node_size=40)
nx.draw_networkx_nodes(graph, layout, nodelist=ts, node_color=range(len(ts),0,-1), vmin=len(ts)/2, vmax=len(ts), cmap=plt.cm.Blues, node_size=50)
# edge_labels=dict([((u,v,),"%5.1f" % d['weight'])
# for u,v,d in graph.edges(data=True)])
# nx.draw_networkx_edge_labels(graph, layout, edge_labels=edge_labels)