1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
# -*- coding: utf-8 -*-
"""Max flow algorithm test suite on large graphs.
Run with nose: nosetests -v test_max_flow.py
"""
__author__ = """Loïc Séguin-C. <loicseguin@gmail.com>"""
# Copyright (C) 2010 Loïc Séguin-C. <loicseguin@gmail.com>
# All rights reserved.
# BSD license.
import networkx as nx
from nose.tools import *
def gen_pyramid(N):
# This graph admits a flow of value 1 for which every arc is at
# capacity (except the arcs incident to the sink which have
# infinite capacity).
G = nx.DiGraph()
for i in range(N - 1):
cap = 1. / (i + 2)
for j in range(i + 1):
G.add_edge((i, j), (i + 1, j),
capacity = cap)
cap = 1. / (i + 1) - cap
G.add_edge((i, j), (i + 1, j + 1),
capacity = cap)
cap = 1. / (i + 2) - cap
for j in range(N):
G.add_edge((N - 1, j), 't')
return G
class TestMaxflowLargeGraph:
def test_complete_graph(self):
N = 50
G = nx.complete_graph(N)
for (u, v) in G.edges():
G[u][v]['capacity'] = 5
assert_equal(nx.ford_fulkerson(G, 1, 2)[0], 5 * (N - 1))
def test_pyramid(self):
N = 10
# N = 100 # this gives a graph with 5051 nodes
G = gen_pyramid(N)
assert_almost_equal(nx.ford_fulkerson(G, (0, 0), 't')[0], 1.)
|
