← Back to branch summary

~ubuntu-branches/ubuntu/saucy/python-networkx/saucy

« 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: 2011-03-19 12:19:16 UTC
  • mfrom: (1.2.5 upstream)
  • Revision ID: james.westby@ubuntu.com-20110319121916-xrhlpiwc9sa5e028
Tags: 1.4-1
http://bugs.debian.org/617677
http://bugs.debian.org/608780
* New upstream release; thanks to Yaroslav Halchenko for the report;
  Closes: #617677
* debian/rules
  - don't compress objects.inv; thanks to Michael Fladischer for the report;
    Closes: #608780
* debian/watch
  - updated to point to PyPi
* debian/control
  - bump python-sphinx versioned b-d-i to 1.0.1 minimum
  - added python-pygraphviz to b-d-i, needed for doc building
* debian/copyright
  - bump upstream and packaging copyright years
* debian/patches/{40_add_networkxcss, 50_boundary-test-fix.patch
                  60_remove_svn_refs.diff 70_set_matplotlib_ps_backend.patch}
  - removed since merged upstream
* debian/patches/{10_doc_relocation, 20_example_dirs_remove,
                  30_use_local_objects.inv}
  - refreshed/adapted to new upstream code

Show diffs side-by-side

added added

removed removed

Lines of Context:
networkx/algorithms/flow/tests/test_mincost.py
147
147
        assert_equal(nx.min_cost_flow(G), soln)
148
148
        assert_equal(nx.cost_of_flow(G, H), 150)
149
149
 
 
150
    def test_digraph2(self):
 
151
        # Example from ticket #430 from mfrasca. Original source:
 
152
        # http://www.cs.princeton.edu/courses/archive/spr03/cs226/lectures/mincost.4up.pdf, slide 11.
 
153
        G = nx.DiGraph()
 
154
        G.add_edge('s', 1, capacity=12)
 
155
        G.add_edge('s', 2, capacity=6)
 
156
        G.add_edge('s', 3, capacity=14)
 
157
        G.add_edge(1, 2, capacity=11)
 
158
        G.add_edge(2, 3, capacity=9)
 
159
        G.add_edge(1, 4, capacity=5)
 
160
        G.add_edge(1, 5, capacity=2)
 
161
        G.add_edge(2, 5, capacity=4)
 
162
        G.add_edge(2, 6, capacity=2)
 
163
        G.add_edge(3, 6, capacity=31)
 
164
        G.add_edge(4, 5, capacity=18)
 
165
        G.add_edge(5, 5, capacity=9)
 
166
        G.add_edge(4, 't', capacity=3)
 
167
        G.add_edge(5, 't', capacity=7)
 
168
        G.add_edge(6, 't', capacity=22)
 
169
        flow = nx.max_flow_min_cost(G, 's', 't')
 
170
        soln = {1: {2: 5, 4: 5, 5: 2},
 
171
                2: {3: 6, 5: 3, 6: 2},
 
172
                3: {6: 20},
 
173
                4: {5: 2, 't': 3},
 
174
                5: {5: 0, 't': 7},
 
175
                6: {'t': 22},
 
176
                's': {1: 12, 2: 6, 3: 14},
 
177
                't': {}}
 
178
        assert_equal(flow, soln)
 
179
 
 
180
    def test_digraph3(self):
 
181
        """Combinatorial Optimization: Algorithms and Complexity,
 
182
        Papadimitriou Steiglitz at page 140 has an example, 7.1, but that
 
183
        admits multiple solutions, so I alter it a bit. From ticket #430
 
184
        by mfrasca."""
 
185
 
 
186
        G = G = nx.DiGraph()
 
187
        G.add_edge('s', 'a', {0: 2, 1: 4})
 
188
        G.add_edge('s', 'b', {0: 2, 1: 1})
 
189
        G.add_edge('a', 'b', {0: 5, 1: 2})
 
190
        G.add_edge('a', 't', {0: 1, 1: 5})
 
191
        G.add_edge('b', 'a', {0: 1, 1: 3})
 
192
        G.add_edge('b', 't', {0: 3, 1: 2})
 
193
 
 
194
        "PS.ex.7.1: testing main function"
 
195
        sol = nx.max_flow_min_cost(G, 's', 't', capacity=0, weight=1)
 
196
        flow = sum(v for v in sol['s'].values())
 
197
        assert_equal(4, flow)
 
198
        assert_equal(23, nx.cost_of_flow(G, sol, weight=1))
 
199
        assert_equal(sol['s'], {'a': 2, 'b': 2})
 
200
        assert_equal(sol['a'], {'b': 1, 't': 1})
 
201
        assert_equal(sol['b'], {'a': 0, 't': 3})
 
202
        assert_equal(sol['t'], {})
 
203
 
 
204