Benchmark NetworkX maximum flow implementations for connectivity algorithms.

benchmark_flow.py

import time
import math
from random import randrange, choice, shuffle

import networkx as nx
from networkx.utils import create_degree_sequence, powerlaw_sequence

def std(x):
    #http://stackoverflow.com/questions/1174984/how-to-efficiently-calculate-a-running-standard-deviation
    n = float(len(x))
    sum_x1 = sum(x)
    sum_x2 = sum([i**2 for i in x])
    mean = sum_x1 / n
    return math.sqrt(abs((sum_x2 / n) - (mean * mean)))

def mean(x):
    return sum(x) / float(len(x))

def add_capacity(G, random=False):
    size = G.size()
    if random:
        capacity = dict(((u, v), randrange(1, 100)) for (u, v) in G.edges())
    else:
        capacity = dict(((u, v), 1) for u, v in G.edges())
    nx.set_edge_attributes(G, 'capacity', capacity)
    return G

def non_connected_node_pairs(G, n=100):
    pairs = set()
    nodes = list(G)
    shuffle(nodes)
    for i in range(n):
        u = nodes.pop()
        v = choice(nodes)
        while v in G[u]:
            v = choice(nodes)
        pairs.add((u, v))
    return pairs

def time_pairs_flow(G, pairs, flow_func):
    times = []
    for pair in pairs:
        start = time.time()
        f = flow_func(G, pair[0], pair[1])
        times.append(time.time() - start)
    return mean(times), std(times)

def benchmark_flow_funcs(npairs=100):
    # Flow functions to test
    flow_funcs = dict(
        ford_fulkerson = nx.max_flow,
        preflow_push = nx.preflow_push_value,
    )
    # Build test graphs
    Gnp_sparse = nx.fast_gnp_random_graph(600, 0.02)
    Gnp_denser = nx.fast_gnp_random_graph(200, 0.2)
    deg_seq = create_degree_sequence(1000, powerlaw_sequence, 100)
    Gconf = nx.Graph(nx.configuration_model(deg_seq))
    Gconf.remove_edges_from(Gconf.selfloop_edges())
    Gconf = list(nx.connected_component_subgraphs(Gconf))[0]
    Gconf.name = 'Power law configuration model'
    test_graphs = [Gnp_sparse, Gnp_denser, Gconf]
    # Run the tests
    for G in test_graphs:
        print(nx.info(G))
        print("Mean and std of computing the maximum flow among {} pairs of nodes".format(npairs))
        pairs = non_connected_node_pairs(G, n=npairs)
        for kind in [False, True]:
            print("  Kind of capacity: {}".format('random ints' if kind else 'unit'))
            H = add_capacity(G, random=kind)
            for name, flow_func in flow_funcs.items():
                t = time_pairs_flow(G, pairs, flow_func)
                print(" " * 4 + "{0}:\t{1:.3f} ({2:.4f}) seconds".format(name, t[0], t[1]))
        print("Time computing node connectivity")
        for name, flow_func in flow_funcs.items():
            start = time.time()
            K = nx.node_connectivity(G, flow_func=flow_func)
            print(" " * 4 + "{0}:\t{1:.2f} seconds".format(name, time.time() - start))
        print("Time computing edge connectivity")
        for name, flow_func in flow_funcs.items():
            start = time.time()
            K = nx.edge_connectivity(G, flow_func=flow_func)
            print(" " * 4 + "{0}:\t{1:.2f} seconds".format(name, time.time() - start))
        print('')


if __name__ == '__main__':
    benchmark_flow_funcs(npairs=100)

output_benchmark.txt

jtorrents@saturn:~/projects/benchmark$ python2.7 benchmark_flow.py
Name: fast_gnp_random_graph(600,0.02)
Type: Graph
Number of nodes: 600
Number of edges: 3633
Average degree:  12.1100
Mean and std of computing the maximum flow among 100 pairs of nodes
  Kind of capacity: unit
    preflow_push:	0.022 (0.0033) seconds
    ford_fulkerson:	0.012 (0.0021) seconds
  Kind of capacity: random ints
    preflow_push:	0.024 (0.0039) seconds
    ford_fulkerson:	0.013 (0.0024) seconds
Time computing node connectivity
    preflow_push:	33.42 seconds
    ford_fulkerson:	9.68 seconds
Time computing edge connectivity
    preflow_push:	3.54 seconds
    ford_fulkerson:	1.69 seconds

Name: fast_gnp_random_graph(200,0.2)
Type: Graph
Number of nodes: 200
Number of edges: 3962
Average degree:  39.6200
Mean and std of computing the maximum flow among 100 pairs of nodes
  Kind of capacity: unit
    preflow_push:	0.020 (0.0031) seconds
    ford_fulkerson:	0.012 (0.0021) seconds
  Kind of capacity: random ints
    preflow_push:	0.021 (0.0033) seconds
    ford_fulkerson:	0.013 (0.0022) seconds
Time computing node connectivity
    preflow_push:	20.70 seconds
    ford_fulkerson:	7.68 seconds
Time computing edge connectivity
    preflow_push:	0.53 seconds
    ford_fulkerson:	0.29 seconds

Name: Power law configuration model
Type: Graph
Number of nodes: 970
Number of edges: 2413
Average degree:   4.9753
Mean and std of computing the maximum flow among 100 pairs of nodes
  Kind of capacity: unit
    preflow_push:	0.021 (0.0054) seconds
    ford_fulkerson:	0.008 (0.0024) seconds
  Kind of capacity: random ints
    preflow_push:	0.021 (0.0073) seconds
    ford_fulkerson:	0.008 (0.0019) seconds
Time computing node connectivity
    preflow_push:	49.52 seconds
    ford_fulkerson:	12.74 seconds
Time computing edge connectivity
    preflow_push:	13.25 seconds
    ford_fulkerson:	5.05 seconds

jtorrents@saturn:~/projects/benchmark$ python3.3 benchmark_flow.py
Name: fast_gnp_random_graph(600,0.02)
Type: Graph
Number of nodes: 600
Number of edges: 3585
Average degree:  11.9500
Mean and std of computing the maximum flow among 100 pairs of nodes
  Kind of capacity: unit
    ford_fulkerson:	0.011 (0.0020) seconds
    preflow_push:	0.021 (0.0025) seconds
  Kind of capacity: random ints
    ford_fulkerson:	0.013 (0.0022) seconds
    preflow_push:	0.022 (0.0032) seconds
Time computing node connectivity
    ford_fulkerson:	10.70 seconds
    preflow_push:	32.32 seconds
Time computing edge connectivity
    ford_fulkerson:	1.64 seconds
    preflow_push:	3.27 seconds

Name: fast_gnp_random_graph(200,0.2)
Type: Graph
Number of nodes: 200
Number of edges: 4100
Average degree:  41.0000
Mean and std of computing the maximum flow among 100 pairs of nodes
  Kind of capacity: unit
    ford_fulkerson:	0.012 (0.0019) seconds
    preflow_push:	0.020 (0.0024) seconds
  Kind of capacity: random ints
    ford_fulkerson:	0.014 (0.0020) seconds
    preflow_push:	0.021 (0.0030) seconds
Time computing node connectivity
    ford_fulkerson:	9.13 seconds
    preflow_push:	23.54 seconds
Time computing edge connectivity
    ford_fulkerson:	0.30 seconds
    preflow_push:	0.50 seconds

Name: Power law configuration model
Type: Graph
Number of nodes: 971
Number of edges: 2442
Average degree:   5.0299
Mean and std of computing the maximum flow among 100 pairs of nodes
  Kind of capacity: unit
    ford_fulkerson:	0.007 (0.0017) seconds
    preflow_push:	0.020 (0.0055) seconds
  Kind of capacity: random ints
    ford_fulkerson:	0.008 (0.0019) seconds
    preflow_push:	0.021 (0.0072) seconds
Time computing node connectivity
    ford_fulkerson:	14.65 seconds
    preflow_push:	48.64 seconds
Time computing edge connectivity
    ford_fulkerson:	5.03 seconds
    preflow_push:	14.66 seconds

jtorrents@saturn:~/projects/benchmark$ pypy benchmark_flow.py
Name: fast_gnp_random_graph(600,0.02)
Type: Graph
Number of nodes: 600
Number of edges: 3587
Average degree:  11.9567
Mean and std of computing the maximum flow among 100 pairs of nodes
  Kind of capacity: unit
    preflow_push:	0.018 (0.0110) seconds
    ford_fulkerson:	0.010 (0.0068) seconds
  Kind of capacity: random ints
    preflow_push:	0.017 (0.0087) seconds
    ford_fulkerson:	0.010 (0.0069) seconds
Time computing node connectivity
    preflow_push:	21.34 seconds
    ford_fulkerson:	8.00 seconds
Time computing edge connectivity
    preflow_push:	2.26 seconds
    ford_fulkerson:	1.21 seconds

Name: fast_gnp_random_graph(200,0.2)
Type: Graph
Number of nodes: 200
Number of edges: 4009
Average degree:  40.0900
Mean and std of computing the maximum flow among 100 pairs of nodes
  Kind of capacity: unit
    preflow_push:	0.016 (0.0096) seconds
    ford_fulkerson:	0.010 (0.0089) seconds
  Kind of capacity: random ints
    preflow_push:	0.016 (0.0096) seconds
    ford_fulkerson:	0.011 (0.0091) seconds
Time computing node connectivity
    preflow_push:	14.60 seconds
    ford_fulkerson:	6.18 seconds
Time computing edge connectivity
    preflow_push:	0.33 seconds
    ford_fulkerson:	0.19 seconds

Name: Power law configuration model
Type: Graph
Number of nodes: 980
Number of edges: 2629
Average degree:   5.3653
Mean and std of computing the maximum flow among 100 pairs of nodes
  Kind of capacity: unit
    preflow_push:	0.015 (0.0113) seconds
    ford_fulkerson:	0.008 (0.0083) seconds
  Kind of capacity: random ints
    preflow_push:	0.015 (0.0117) seconds
    ford_fulkerson:	0.007 (0.0083) seconds
Time computing node connectivity
    preflow_push:	33.23 seconds
    ford_fulkerson:	12.32 seconds
Time computing edge connectivity
    preflow_push:	8.40 seconds
    ford_fulkerson:	5.11 seconds