Simple maxflow/mincut algorithm, an implementation of Edmonds-Karp.
We will run the maxflow for two networks: a Mesa street network used as an example dataset in the GeoDaNet package and a Barcelona street network provided by Simon Planells-Struse.
This algorithm, in addition to needing the maxflow and maxflow_tools modules, requires pysal and networkx.
In [6]:
import maxflow as mx
import pysal as ps
import networkx as nx
import maxflow_tools as mft
In [22]:
shpf_a = ps.open('example_data/streets.shp')
Once the shapefile is opened, we will calculate arc lengths for the network and assign random capacities to each arc, as it doesn't currently contain capacities. The maximum random capacitiy is set at 45 and the lengths are calculated from the arclen method of pysal "chain" datatypes. Then, a start and end are randomly assigned, and a networkx graph constructed.
In [52]:
lens_a, caps_a = mx.genlenscaps(shpf_a, cap=45)
start_a, end_a = mx.genrandst(shpf_a, lens_a)
startgraph_a, resgraph_a = mx.gengraphs(shpf_a, lens_a, caps_a)
Then, the maxflow problem is solved using the Edmonds-Karp Algorithm.
In [54]:
startgraph_a, resgraph_a, maxflow_a = mx.maxflow(startgraph_a, resgraph_a, caps_a, start_a, end_a)
Now we will write the cell to file
In [55]:
nx.write_shp(startgraph_a, "./output_a/start")
nx.write_shp(resgraph_a, "./output_a/residual")
In [11]:
shpf_b = ps.open('example_data/barca/simon_maps/BCN_GrafVial_Trams_SHP.shp')
Once the shapefile is opened, we must generate lengths and capacities for the network. A maximum random capacity was set at 20, and the lengths are real lengths derived from the arclen method of pysal chains. Then, a start and end is picked randomly, and a network x graph generated.
In [12]:
lens_b, caps_b = mx.genlenscaps(shpf_b, cap=20)
start_b, end_b = mx.genrandst(shpf_b, lens_b)
startgraph_b, resgraph_b = mx.gengraphs(shpf_b, lens_b, caps_b)
Then, the Edmonds-Karp algorithm can be run
In [13]:
startgraph_b, resgraph_b, maxflow_b = mx.maxflow(startgraph_b, resgraph_b, caps_b, start_b, end_b)
Again, the graphs will be written to files
In [15]:
nx.write_shp(startgraph_b, "./output_b/start")
nx.write_shp(resgraph_b, "./output_b/residual")
In [ ]: