/usr/lib/python2.7/dist-packages/networkx/algorithms/flow/tests/test_maxflow_large_graph.py is in python-networkx 1.8.1-0ubuntu3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
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 | # -*- 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.)
|