← Back to branch summary

~ubuntu-branches/ubuntu/trusty/python-networkx/trusty-proposed

« back to all changes in this revision

Viewing changes to networkx/algorithms/flow/tests/test_mincost.py

  • Committer: Bazaar Package Importer
  • Author(s): Sandro Tosi
  • Date: 2010-12-10 23:50:27 UTC
  • mfrom: (1.2.4 upstream) (5.1.4 sid)
  • Revision ID: james.westby@ubuntu.com-20101210235027-b2supdwo0ad39d3s
Tags: 1.3-1
http://bugs.debian.org/567369
* New upstream release
* debian/patches/changeset_r1745.diff
  - dropped, available in upstream release
* debian/patches/10_doc_relocation
  - refreshed patch for new upstream code
* debian/control
  - upstream code is now compatible with 2.6 or later only
  - bump Standards-Version to 3.9.1 (no changes needed)
* debian/{control, rules}
  - run unittests at build time, b-d on python-nose added
* debian/copyright
  - removed reference to /usr/share/common-licenses/BSD
* Create a -doc package ; thanks to Yaroslav Halchenko for the report;
  Closes: #567369
  - (d/control) define a new binary package, and add depends on sphinx (>= 1)
  - (d/rules) build documentation, install it into the new -doc package
  - (d/patches/30_use_local_objects.inv) use local copy of remote objects.inv
* debian/{control, rules}
  - moved to dh7 and "reduced" rules file
* debian/rules
  - refer to built code when building doc
* debian/python-networkx-doc.doc-base
  - added doc-base information
* debian/patches/40_add_networkxcss
  - added as patch, since networkx.css is missing from the tarball, but needed
    to display properly HTML documentation
* debian/patches/50_boundary-test-fix.patch
  - upstream patch to restrict node boundary test cases to valid range
* debian/patches/60_remove_svn_refs.diff
  - upstream patch to remove references to old SVN repository (now Mercurial)
* debian/patches/70_set_matplotlib_ps_backend.patch
  - set matplotlib backend to 'PS', so a DISPLAY it's not required and the
    tests can be run in a "reduced" environment

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/flow/tests/test_mincost.py
 
1
# -*- coding: utf-8 -*-
 
2
 
 
3
import networkx as nx
 
4
from nose.tools import assert_equal, assert_raises
 
5
 
 
6
class TestNetworkSimplex:
 
7
    def test_simple_digraph(self):
 
8
        G = nx.DiGraph()
 
9
        G.add_node('a', demand = -5)
 
10
        G.add_node('d', demand = 5)
 
11
        G.add_edge('a', 'b', weight = 3, capacity = 4)
 
12
        G.add_edge('a', 'c', weight = 6, capacity = 10)
 
13
        G.add_edge('b', 'd', weight = 1, capacity = 9)
 
14
        G.add_edge('c', 'd', weight = 2, capacity = 5)
 
15
        flowCost, H = nx.network_simplex(G)
 
16
        soln = {'a': {'b': 4, 'c': 1},
 
17
                'b': {'d': 4},
 
18
                'c': {'d': 1},
 
19
                'd': {}}
 
20
        assert_equal(flowCost, 24)
 
21
        assert_equal(nx.min_cost_flow_cost(G), 24)
 
22
        assert_equal(H, soln)
 
23
        assert_equal(nx.min_cost_flow(G), soln)
 
24
        assert_equal(nx.cost_of_flow(G, H), 24)
 
25
 
 
26
    def test_negcycle_infcap(self):
 
27
        G = nx.DiGraph()
 
28
        G.add_node('s', demand = -5)
 
29
        G.add_node('t', demand = 5)
 
30
        G.add_edge('s', 'a', weight = 1, capacity = 3)
 
31
        G.add_edge('a', 'b', weight = 3)
 
32
        G.add_edge('c', 'a', weight = -6)
 
33
        G.add_edge('b', 'd', weight = 1)
 
34
        G.add_edge('d', 'c', weight = -2)
 
35
        G.add_edge('d', 't', weight = 1, capacity = 3)
 
36
        assert_raises(nx.NetworkXUnbounded, nx.network_simplex, G)
 
37
 
 
38
    def test_sum_demands_not_zero(self):
 
39
        G = nx.DiGraph()
 
40
        G.add_node('s', demand = -5)
 
41
        G.add_node('t', demand = 4)
 
42
        G.add_edge('s', 'a', weight = 1, capacity = 3)
 
43
        G.add_edge('a', 'b', weight = 3)
 
44
        G.add_edge('a', 'c', weight = -6)
 
45
        G.add_edge('b', 'd', weight = 1)
 
46
        G.add_edge('c', 'd', weight = -2)
 
47
        G.add_edge('d', 't', weight = 1, capacity = 3)
 
48
        assert_raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
 
49
 
 
50
    def test_no_flow_satisfying_demands(self):
 
51
        G = nx.DiGraph()
 
52
        G.add_node('s', demand = -5)
 
53
        G.add_node('t', demand = 5)
 
54
        G.add_edge('s', 'a', weight = 1, capacity = 3)
 
55
        G.add_edge('a', 'b', weight = 3)
 
56
        G.add_edge('a', 'c', weight = -6)
 
57
        G.add_edge('b', 'd', weight = 1)
 
58
        G.add_edge('c', 'd', weight = -2)
 
59
        G.add_edge('d', 't', weight = 1, capacity = 3)
 
60
        assert_raises(nx.NetworkXUnfeasible, nx.network_simplex, G)
 
61
 
 
62
    def test_transshipment(self):
 
63
        G = nx.DiGraph()
 
64
        G.add_node('a', demand = 1)
 
65
        G.add_node('b', demand = -2)
 
66
        G.add_node('c', demand = -2)
 
67
        G.add_node('d', demand = 3)
 
68
        G.add_node('e', demand = -4)
 
69
        G.add_node('f', demand = -4)
 
70
        G.add_node('g', demand = 3)
 
71
        G.add_node('h', demand = 2)
 
72
        G.add_node('r', demand = 3)
 
73
        G.add_edge('a', 'c', weight = 3)
 
74
        G.add_edge('r', 'a', weight = 2)
 
75
        G.add_edge('b', 'a', weight = 9)
 
76
        G.add_edge('r', 'c', weight = 0)
 
77
        G.add_edge('b', 'r', weight = -6)
 
78
        G.add_edge('c', 'd', weight = 5)
 
79
        G.add_edge('e', 'r', weight = 4)
 
80
        G.add_edge('e', 'f', weight = 3)
 
81
        G.add_edge('h', 'b', weight = 4)
 
82
        G.add_edge('f', 'd', weight = 7)
 
83
        G.add_edge('f', 'h', weight = 12)
 
84
        G.add_edge('g', 'd', weight = 12)
 
85
        G.add_edge('f', 'g', weight = -1)
 
86
        G.add_edge('h', 'g', weight = -10)
 
87
        flowCost, H = nx.network_simplex(G)
 
88
        soln = {'a': {'c': 0},
 
89
                'b': {'a': 0, 'r': 2},
 
90
                'c': {'d': 3},
 
91
                'd': {},
 
92
                'e': {'r': 3, 'f': 1},
 
93
                'f': {'d': 0, 'g': 3, 'h': 2},
 
94
                'g': {'d': 0},
 
95
                'h': {'b': 0, 'g': 0},
 
96
                'r': {'a': 1, 'c': 1}}
 
97
        assert_equal(flowCost, 41)
 
98
        assert_equal(nx.min_cost_flow_cost(G), 41)
 
99
        assert_equal(H, soln)
 
100
        assert_equal(nx.min_cost_flow(G), soln)
 
101
        assert_equal(nx.cost_of_flow(G, H), 41)
 
102
 
 
103
    def test_max_flow_min_cost(self):
 
104
        G = nx.DiGraph()
 
105
        G.add_edge('s', 'a', bandwidth = 6)
 
106
        G.add_edge('s', 'c', bandwidth = 10, cost = 10)
 
107
        G.add_edge('a', 'b', cost = 6)
 
108
        G.add_edge('b', 'd', bandwidth = 8, cost = 7)
 
109
        G.add_edge('c', 'd', cost = 10)
 
110
        G.add_edge('d', 't', bandwidth = 5, cost = 5)
 
111
        soln = {'s': {'a': 5, 'c': 0},
 
112
                'a': {'b': 5},
 
113
                'b': {'d': 5},
 
114
                'c': {'d': 0},
 
115
                'd': {'t': 5},
 
116
                't': {}}
 
117
        flow = nx.max_flow_min_cost(G, 's', 't', capacity = 'bandwidth',
 
118
                                    weight = 'cost')
 
119
        assert_equal(flow, soln)
 
120
        assert_equal(nx.cost_of_flow(G, flow, weight = 'cost'), 90)
 
121
 
 
122
    def test_digraph1(self):
 
123
        # From Bradley, S. P., Hax, A. C. and Magnanti, T. L. Applied
 
124
        # Mathematical Programming. Addison-Wesley, 1977.
 
125
        G = nx.DiGraph()
 
126
        G.add_node(1, demand = -20)
 
127
        G.add_node(4, demand = 5)
 
128
        G.add_node(5, demand = 15)
 
129
        G.add_edges_from([(1, 2, {'capacity': 15, 'weight': 4}),
 
130
                          (1, 3, {'capacity': 8, 'weight': 4}),
 
131
                          (2, 3, {'weight': 2}),
 
132
                          (2, 4, {'capacity': 4, 'weight': 2}),
 
133
                          (2, 5, {'capacity': 10, 'weight': 6}),
 
134
                          (3, 4, {'capacity': 15, 'weight': 1}),
 
135
                          (3, 5, {'capacity': 5, 'weight': 3}),
 
136
                          (4, 5, {'weight': 2}),
 
137
                          (5, 3, {'capacity': 4, 'weight': 1})])
 
138
        flowCost, H = nx.network_simplex(G)
 
139
        soln = {1: {2: 12, 3: 8},
 
140
                2: {3: 8, 4: 4, 5: 0},
 
141
                3: {4: 11, 5: 5},
 
142
                4: {5: 10},
 
143
                5: {3: 0}}
 
144
        assert_equal(flowCost, 150)
 
145
        assert_equal(nx.min_cost_flow_cost(G), 150)
 
146
        assert_equal(H, soln)
 
147
        assert_equal(nx.min_cost_flow(G), soln)
 
148
        assert_equal(nx.cost_of_flow(G, H), 150)
 
149