loom.flow
Algorithms for solving network flow
Algorithms for solving network flow
augment-along-pathclj/s
(augment-along-path flow capacity path increase)Given a flow represented as an adjacency map, returns an updated flow. Capacity is a function of two vertices, path is a sequence of nodes, and increase is the amount by which the flow should be augmented on this path. If at any point the increase exceeds forward capacity, the excess is pushed in the reverse direction. An exception is thrown if the augmentation is impossible given capacity constraints.
Given a flow represented as an adjacency map, returns an updated flow. Capacity is a function of two vertices, path is a sequence of nodes, and increase is the amount by which the flow should be augmented on this path. If at any point the increase exceeds forward capacity, the excess is pushed in the reverse direction. An exception is thrown if the augmentation is impossible given capacity constraints.
bf-find-augmenting-pathclj/s
(bf-find-augmenting-path successors predecessors capacity flow s t)Finds a shortest path in the flow network along which there remains residual capacity. Successors is a function which, given a vertex, returns the vertices connected by outgoing edges. Predecessors, similarly is a function to get vertices connected by incoming edges. Capacity is a function which takes two vertices and returns the capacity between them. Flow is an adjacency map which contains the current value of network flow. s is the source node, t the sink.
Finds a shortest path in the flow network along which there remains residual capacity. Successors is a function which, given a vertex, returns the vertices connected by outgoing edges. Predecessors, similarly is a function to get vertices connected by incoming edges. Capacity is a function which takes two vertices and returns the capacity between them. Flow is an adjacency map which contains the current value of network flow. s is the source node, t the sink.
edmonds-karpclj/s
(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-balanceclj/s
(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?clj/s
(is-admissible-flow? flow capacity source sink)Verifies that a flow satisfies capacity and mass balance constraints. Does verify that a flow is maximum.
Verifies that a flow satisfies capacity and mass balance constraints. Does verify that a flow is maximum.
min-weight-along-pathclj/s
(min-weight-along-path path weight-fn)Given a path, represented by a sequence of nodes, and weight-function, computes the minimum of the edge weights along the path. If an edge on the path is missing, returns 0.
Given a path, represented by a sequence of nodes, and weight-function, computes the minimum of the edge weights along the path. If an edge on the path is missing, returns 0.
residual-capacityclj/s
(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 the edge between them, if any. Flow is the adjacency map which represents the current flow in the network.
Computes the residual capacity between nodes v1 and v2. Capacity is a function that takes two nodes, and returns the capacity on the edge between them, if any. Flow is the adjacency map which represents the current flow in the network.
satisfies-capacity-constraints?clj/s
(satisfies-capacity-constraints? flow capacity)Given a flow map, and a capacity function, verifies that the flow on each edge is <= capacity of that edge.
Given a flow map, and a capacity function, verifies that the flow on each edge is <= capacity of that edge.
satisfies-mass-balance?clj/s
(satisfies-mass-balance? flow source sink)Given a flow, verifies whether at each node the sum of in edge weights is equal to the sum of out edge weights, except at the source and sink. The source should have positive net outflow, the sink negative, and together they should balance.
Given a flow, verifies whether at each node the sum of in edge weights is equal to the sum of out edge weights, except at the source and sink. The source should have positive net outflow, the sink negative, and together they should balance.
cljdoc is a website building & hosting documentation for Clojure/Script libraries
× close