In [1]:

    

import networkx as nx
from random import random
import math, time


    

In [2]:

    

import json
from networkx.readwrite import json_graph


    

In [3]:

    

import vincent
from IPython.display import display
vincent.initialize_notebook()


    

In [4]:

    

import matplotlib.pyplot as plt
%matplotlib inline
%config InlineBackend.figure_format = 'svg'


    

In [5]:

    

%load_ext autoreload
%autoreload 2


    

In [6]:

    

from randomwalk import plotrwtraversal, randomwalk, edgetokey


    

In [7]:

    

def rungraph(G, k=2):
    # Convert to DiGraph if necessary
    if G.is_multigraph():
        if G.is_directed():
            Gm = G.copy()
            G = nx.DiGraph()
            G.graph['name'] = Gm.graph['name']
            for (u,v) in Gm.edges_iter():
                G.add_edge(u,v)

    # Randomize the expensive edges
    expensiveedges = []
    for e in G.edges_iter():
        if random() > 1/float(k):
            expensiveedges.append(edgetokey(e))
            G.edge[e[0]][e[1]]['expensive'] = True
        else:
            G.edge[e[0]][e[1]]['expensive'] = False

    get_ipython().run_cell_magic(u'html', u'', '<h2>Graph: '+G.graph['name']+'</h2>')
        
    if False:
        # Save and plot graph
        d = json_graph.node_link_data(G)
        for node in d['nodes']:
            node['name']=node['id']
            node['value']=G.degree(node['id'])

        d['adjacency'] = json_graph.adjacency_data(G)['adjacency']
        json.dump(d, open('graph.json','w'))

        time.sleep(1)

        get_ipython().run_cell_magic(u'html', u'', u'<div id="d3-example"></div>\n<style>\n.node {stroke: #fff; stroke-width: 1.5px;}\nmarker {stroke: #999;}\n.link {stroke: #999; stroke-opacity: .6;}\n</style>\n<script src="force.js"></script>')
        #nx.draw_graphviz(G)

    # Run algos
    G1 = G.copy()
    randomwalk(G1, frogs, P_die)
    G2 = G.copy()
    randomwalk(G2, frogs, P_die, 4, expensiveedges)

    # Make graphs
    (line1, df1) = plotrwtraversal(G1,expensiveedges, time=G2.graph['endtime']+1)
    (line2, df2) = plotrwtraversal(G2, expensiveedges)
    get_ipython().run_cell_magic(u'html', u'', '<h3>'+"Vanilla random walk. Cost: " + str(G1.graph['cost'])+'</h3>')
    display(line1)

    get_ipython().run_cell_magic(u'html', u'', '<h3>'+"Waiting random walk. Cost: " + str(G2.graph['cost'])
                                 + ', a ' + str( 100*(1 - G2.graph['cost'] / float(G1.graph['cost']) ) ) + '% gain</h3>')
    display(line2)

    (l, d) = plotrwtraversal(G2, countfrogs=True, expensiveedges = expensiveedges)
    get_ipython().run_cell_magic(u'html', u'', '<h4>'+"Waiting algorithm: What are the frogs up to?"+'</h4>')
    display(l)

    get_ipython().run_cell_magic(u'html', u'', '<h3>'+'Performance stats'+'</h3>')
    print "Stats normalized by equivalent vanilla random walk stats:"
    print
    print "Average death round (waiting/vanilla):", G2.graph['death_times_sum'] / float(L*frogs)
    print "Total duration in rounds (waiting/vanilla):", G2.graph['endtime'] / float(G1.graph['endtime'])
    print "Cost (waiting/vanilla):", G2.graph['cost'] / float(G1.graph['cost'])


    

In [8]:

    

n = 100
m = 2
p = 0.3


    

In [9]:

    

allG = []
#allG.append(nx.barbell_graph(50,0))
allG.append(nx.scale_free_graph(n))
allG.append(nx.powerlaw_cluster_graph(n=n, m=m, p=p))
#allG.append(nx.cycle_graph(n))


    

In [10]:

    

frogs = 1000
# Life expectancy L. L should be the mean of a geometric distribution
L = 6
# P_die is the probability that a frog dies at any given time
P_die = 1/float(L)


    

In [11]:

    

for k in [4]:
    get_ipython().run_cell_magic(u'html', u'', '<h1>Simulating ' + str(k) + ' machines.</h1>')
    for G in allG:
        rungraph(G, k=k)


    

    





Simulating 4 machines.






    





Graph: directed_scale_free_graph(100,alpha=0.41,beta=0.54,gamma=0.05,delta_in=0.2,delta_out=0)






    





Vanilla random walk. Cost: 639.0






    








        






    





Waiting random walk. Cost: 478.0, a 25.1956181534% gain






    








        






    





Waiting algorithm: What are the frogs up to?






    








        






    





Performance stats






    




Stats normalized by equivalent vanilla random walk stats:

Average death round (waiting/vanilla): 1.85766666667
Total duration in rounds (waiting/vanilla): 1.76744186047
Cost (waiting/vanilla): 0.748043818466






    





Graph: Powerlaw-Cluster Graph






    





Vanilla random walk. Cost: 1741.0






    








        






    





Waiting random walk. Cost: 1281.0, a 26.4215967835% gain






    








        






    





Waiting algorithm: What are the frogs up to?






    








        






    





Performance stats






    




Stats normalized by equivalent vanilla random walk stats:

Average death round (waiting/vanilla): 2.18433333333
Total duration in rounds (waiting/vanilla): 3.0
Cost (waiting/vanilla): 0.735784032165

In [ ]: