Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / flow / tests / test_maxflow_large_graph.py @ 5cef0f13

History | View | Annotate | Download (5.02 KB)

1
# -*- coding: utf-8 -*-
2
"""Maximum flow algorithms test suite on large graphs.
3
"""
4

    
5
__author__ = """Loïc Séguin-C. <loicseguin@gmail.com>"""
6
# Copyright (C) 2010 Loïc Séguin-C. <loicseguin@gmail.com>
7
# All rights reserved.
8
# BSD license.
9
import os
10
from nose.tools import *
11

    
12
import networkx as nx
13
from networkx.algorithms.flow import build_flow_dict, build_residual_network
14
from networkx.algorithms.flow import boykov_kolmogorov
15
from networkx.algorithms.flow import dinitz
16
from networkx.algorithms.flow import edmonds_karp
17
from networkx.algorithms.flow import preflow_push
18
from networkx.algorithms.flow import shortest_augmenting_path
19

    
20
flow_funcs = [
21
    boykov_kolmogorov,
22
    dinitz,
23
    edmonds_karp,
24
    preflow_push,
25
    shortest_augmenting_path,
26
]
27

    
28
msg = "Assertion failed in function: {0}"
29

    
30

    
31
def gen_pyramid(N):
32
    # This graph admits a flow of value 1 for which every arc is at
33
    # capacity (except the arcs incident to the sink which have
34
    # infinite capacity).
35
    G = nx.DiGraph()
36

    
37
    for i in range(N - 1):
38
        cap = 1. / (i + 2)
39
        for j in range(i + 1):
40
            G.add_edge((i, j), (i + 1, j),
41
                       capacity=cap)
42
            cap = 1. / (i + 1) - cap
43
            G.add_edge((i, j), (i + 1, j + 1),
44
                       capacity=cap)
45
            cap = 1. / (i + 2) - cap
46

    
47
    for j in range(N):
48
        G.add_edge((N - 1, j), 't')
49

    
50
    return G
51

    
52

    
53
def read_graph(name):
54
    dirname = os.path.dirname(__file__)
55
    path = os.path.join(dirname, name + '.gpickle.bz2')
56
    return nx.read_gpickle(path)
57

    
58

    
59
def validate_flows(G, s, t, soln_value, R, flow_func):
60
    flow_value = R.graph['flow_value']
61
    flow_dict = build_flow_dict(G, R)
62
    assert_equal(soln_value, flow_value, msg=msg.format(flow_func.__name__))
63
    assert_equal(set(G), set(flow_dict), msg=msg.format(flow_func.__name__))
64
    for u in G:
65
        assert_equal(set(G[u]), set(flow_dict[u]),
66
                     msg=msg.format(flow_func.__name__))
67
    excess = {u: 0 for u in flow_dict}
68
    for u in flow_dict:
69
        for v, flow in flow_dict[u].items():
70
            ok_(flow <= G[u][v].get('capacity', float('inf')),
71
                msg=msg.format(flow_func.__name__))
72
            ok_(flow >= 0, msg=msg.format(flow_func.__name__))
73
            excess[u] -= flow
74
            excess[v] += flow
75
    for u, exc in excess.items():
76
        if u == s:
77
            assert_equal(exc, -soln_value, msg=msg.format(flow_func.__name__))
78
        elif u == t:
79
            assert_equal(exc, soln_value, msg=msg.format(flow_func.__name__))
80
        else:
81
            assert_equal(exc, 0, msg=msg.format(flow_func.__name__))
82

    
83

    
84
class TestMaxflowLargeGraph:
85

    
86
    def test_complete_graph(self):
87
        N = 50
88
        G = nx.complete_graph(N)
89
        nx.set_edge_attributes(G, 5, 'capacity')
90
        R = build_residual_network(G, 'capacity')
91
        kwargs = dict(residual=R)
92

    
93
        for flow_func in flow_funcs:
94
            kwargs['flow_func'] = flow_func
95
            flow_value = nx.maximum_flow_value(G, 1, 2, **kwargs)
96
            assert_equal(flow_value, 5 * (N - 1),
97
                         msg=msg.format(flow_func.__name__))
98

    
99
    def test_pyramid(self):
100
        N = 10
101
        # N = 100 # this gives a graph with 5051 nodes
102
        G = gen_pyramid(N)
103
        R = build_residual_network(G, 'capacity')
104
        kwargs = dict(residual=R)
105

    
106
        for flow_func in flow_funcs:
107
            kwargs['flow_func'] = flow_func
108
            flow_value = nx.maximum_flow_value(G, (0, 0), 't', **kwargs)
109
            assert_almost_equal(flow_value, 1.,
110
                                msg=msg.format(flow_func.__name__))
111

    
112
    def test_gl1(self):
113
        G = read_graph('gl1')
114
        s = 1
115
        t = len(G)
116
        R = build_residual_network(G, 'capacity')
117
        kwargs = dict(residual=R)
118

    
119
        # do one flow_func to save time
120
        flow_func = flow_funcs[0]
121
        validate_flows(G, s, t, 156545, flow_func(G, s, t, **kwargs),
122
                       flow_func)
123
#        for flow_func in flow_funcs:
124
#            validate_flows(G, s, t, 156545, flow_func(G, s, t, **kwargs),
125
#                           flow_func)
126

    
127
    def test_gw1(self):
128
        G = read_graph('gw1')
129
        s = 1
130
        t = len(G)
131
        R = build_residual_network(G, 'capacity')
132
        kwargs = dict(residual=R)
133

    
134
        for flow_func in flow_funcs:
135
            validate_flows(G, s, t, 1202018, flow_func(G, s, t, **kwargs),
136
                           flow_func)
137

    
138
    def test_wlm3(self):
139
        G = read_graph('wlm3')
140
        s = 1
141
        t = len(G)
142
        R = build_residual_network(G, 'capacity')
143
        kwargs = dict(residual=R)
144

    
145
        # do one flow_func to save time
146
        flow_func = flow_funcs[0]
147
        validate_flows(G, s, t, 11875108, flow_func(G, s, t, **kwargs),
148
                       flow_func)
149
#        for flow_func in flow_funcs:
150
#            validate_flows(G, s, t, 11875108, flow_func(G, s, t, **kwargs),
151
#                           flow_func)
152

    
153
    def test_preflow_push_global_relabel(self):
154
        G = read_graph('gw1')
155
        R = preflow_push(G, 1, len(G), global_relabel_freq=50)
156
        assert_equal(R.graph['flow_value'], 1202018)