ndflow
n-dimensional network flow solver
npm install ndflow
Want to see pretty graphs? Log in now!
1 | downloads in the last week |
8 | downloads in the last month |
Last Published By | |
---|---|
Version | 0.0.0 last updated a year ago |
License | BSD |
Keywords | network, flow, simplicial, complex, graph, mesh, minimum, cost, linear, programming, algorithm, topology |
Repository | git://github.com/mikolalysenko/ndflow.git (git) |
Dependencies | cooriented, differential, numeric, simplicial-complex |
Dependents | mikolalysenko-hoarders |
ndflow
Network flow in the nth-dimension!
Usage
First install like this:
npm install ndflow
Then use it as follows:
require("ndflow")(
[[0,1,2], [1,2,3]], //Simplicial complex
[1, 1], //Capacities
[[0,1], [1,3], [3,2], [2,0]], //Boundary circulation
[1,1,1,1], //Boundary weights
[1,1]) //Cost function
require("ndflow")(cells, capacities, boundary_cells, boundary_weights, cost)
Solves for the flow from the boundary cells that minimizes the cost. This is the same thing as solving the linear program:
Minimize cost(flow)
Subject to D(flow) = boundary_cells * boundary_weights
0 <= flow <= capacities
In the case where the cell complex is one dimensional, this is the same as solving minimum cost network flow for a given capacity. Binary searching on the scale of the capacities lets one compute a maximum/min-cost flow.
Credits
(c) 2013 Mikola Lysenko. BSD License