Algorithms for solving network flow
Algorithms for solving network flow
(augment-along-path flow capacity path increase)Returns an updated flow from an adjacency map. Capacity takes two vertices. path is a sequence of nodes. increase is the amount to augment on this path. If increase exceeds forward capacity, the excess goes in the reverse direction. Throws an exception when the capacity constraints make augmentation impossible.
Returns an updated flow from an adjacency map. Capacity takes two vertices. path is a sequence of nodes. increase is the amount to augment on this path. If increase exceeds forward capacity, the excess goes in the reverse direction. Throws an exception when the capacity constraints make augmentation impossible.
(bf-find-augmenting-path successors predecessors capacity flow s t)Finds a shortest path with residual capacity in the flow network. Successors returns vertices connected by outgoing edges. Predecessors returns vertices connected by incoming edges. Capacity returns the capacity between two vertices. Flow is an adjacency map with the current network flow. s is the source node. t is the sink.
Finds a shortest path with residual capacity in the flow network. Successors returns vertices connected by outgoing edges. Predecessors returns vertices connected by incoming edges. Capacity returns the capacity between two vertices. Flow is an adjacency map with the current network flow. s is the source node. t is the sink.
(edmonds-karp successors predecessors capacity source sink)(edmonds-karp successors predecessors capacity source sink flow)Computes the maximum flow on a network, using the edmonds-karp algorithm. Successors is a function that returns the outgoing neighbor vertices of a vertex. Predecessors is a function that returns the incoming neighbor vertices for a vertex. Capacity is a function of two vertices that returns the capacity on the edge between them. Source and sink are the unique vertices which supply and consume flow respectively.
Returns a vector [flow value], where flow is an adjacency map that represents flows between vertices, and value is the quantity of flow passing from source to sink.
Computes the maximum flow on a network, using the edmonds-karp algorithm. Successors is a function that returns the outgoing neighbor vertices of a vertex. Predecessors is a function that returns the incoming neighbor vertices for a vertex. Capacity is a function of two vertices that returns the capacity on the edge between them. Source and sink are the unique vertices which supply and consume flow respectively. Returns a vector [flow value], where flow is an adjacency map that represents flows between vertices, and value is the quantity of flow passing from source to sink.
(flow-balance flow)Given a flow, returns a map of {node (sum(in weight) - sum(out weight))}
Given a flow, returns a map of {node (sum(in weight) - sum(out weight))}
(is-admissible-flow? flow capacity source sink)Checks that a flow satisfies capacity and mass-balance constraints. It does not check that a flow is maximum.
Checks that a flow satisfies capacity and mass-balance constraints. It does not check that a flow is maximum.
(min-weight-along-path path weight-fn)Computes the minimum edge weight along a path represented by a sequence of nodes. Returns 0 if an edge on the path is missing.
Computes the minimum edge weight along a path represented by a sequence of nodes. Returns 0 if an edge on the path is missing.
(residual-capacity capacity flow v1 v2)Computes the residual capacity between nodes v1 and v2. Capacity is a function that takes two nodes and returns the capacity on their edge. Flow is the adjacency map that represents the current network flow.
Computes the residual capacity between nodes v1 and v2. Capacity is a function that takes two nodes and returns the capacity on their edge. Flow is the adjacency map that represents the current network flow.
(satisfies-capacity-constraints? flow capacity)Checks that the flow on each edge is less than or equal to the edge capacity.
Checks that the flow on each edge is less than or equal to the edge capacity.
(satisfies-mass-balance? flow source sink)Checks the sum of incoming and outgoing edge weights at each node, except the source and sink. The source has positive net outflow. The sink has negative net outflow. Together, they balance.
Checks the sum of incoming and outgoing edge weights at each node, except the source and sink. The source has positive net outflow. The sink has negative net outflow. Together, they balance.
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |