HMath.Graph.Flow¶

Description

Exact integral network flow and assignment. Capacities and costs use Integer; residual arcs preserve parallel and antiparallel edge identity. Each max-flow algorithm has a caller-supplied augmentationpushrelabel budget.

On this page¶

API	Purpose
Network	Opaque exact network-flow input with stable parallel/antiparallel edges, constructed with network.
NetworkEdge	Directed integral-capacity/unit-cost edge with stable identity.
NetworkEdge	Declaration and type contract below.
networkEdgeId	Stable original edge identity in network input order.
networkFrom	Source vertex of this directed network edge.
networkTo	Destination vertex of this directed network edge.
networkCapacity	Exact nonnegative Integer capacity of this edge.
networkCost	Exact Integer cost per unit flow; may be negative.
network	Given vertex count then (from,to,capacity,cost) edges, construct an exact integral network with stable edge IDs.
networkEdges	Return original network edges in input/ID order, retaining capacities and costs.
FlowResult	Exact net flow,total edge cost,and original-edge-order flows.
FlowResult	Declaration and type contract below.
flowValue	Exact net flow leaving the chosen source.
edgeFlows	Exact edge flows in original network edge order, preserving parallel and antiparallel identity.
flowCost	Sum of edge flow times edge unit cost; maximum-flow methods do not necessarily minimize this cost.
fordFulkerson	Given augmentation budget,network,source,sink, compute exact maximum flow using depth-first augmenting paths.
edmondsKarp	Given augmentation budget,network,source,sink, compute exact maximum flow using breadth-first shortest augmenting paths.
dinic	Given work budget,network,source,sink, compute maximum flow with level graphs and blocking-flow augmentation.
pushRelabel	Given push/relabel work budget,network,source,sink, compute exact maximum flow by preflow and relabel operations.
minimumCut	Source-side vertices and cut capacity, using Edmonds--Karp residual reach.
minimumCostMaximumFlow	Maximum flow followed by exact negative-residual-cycle cancellation.
hopcroftKarp	Hopcroft--Karp layered augmenting paths.
hungarian	Rectangular Hungarian primal-dual assignment, rows <= columns <= 256.

Documentation

Network

data Network Source #

Opaque exact network-flow input with stable parallel/antiparallel edges, constructed with network.

Instances

Instances details

Show Network Source #
Instance details Defined in HMath.Graph.Flow Methods showsPrec :: Int -> Network -> ShowS # show :: Network -> String # showList :: [Network] -> ShowS #
Eq Network Source #
Instance details Defined in HMath.Graph.Flow Methods (==) :: Network -> Network -> Bool # (/=) :: Network -> Network -> Bool #

NetworkEdge

data NetworkEdge Source #

Directed integral-capacity/unit-cost edge with stable identity. Capacities are nonnegative; costs may be negative.

Constructors

NetworkEdge
Fields networkEdgeId :: Int Stable original edge identity in network input order. networkFrom :: Int Source vertex of this directed network edge. networkTo :: Int Destination vertex of this directed network edge. networkCapacity :: Integer Exact nonnegative Integer capacity of this edge. networkCost :: Integer Exact Integer cost per unit flow; may be negative.

Instances

Instances details

Show NetworkEdge Source #
Instance details Defined in HMath.Graph.Flow Methods showsPrec :: Int -> NetworkEdge -> ShowS # show :: NetworkEdge -> String # showList :: [NetworkEdge] -> ShowS #
Eq NetworkEdge Source #
Instance details Defined in HMath.Graph.Flow Methods (==) :: NetworkEdge -> NetworkEdge -> Bool # (/=) :: NetworkEdge -> NetworkEdge -> Bool #

network

network :: Int -> [(Int, Int, Integer, Integer)] -> Either MathError Network Source #

Given vertex count then (from,to,capacity,cost) edges, construct an exact integral network with stable edge IDs. Require <=512 vertices, <=65536 edges, valid endpoints and nonnegative capacities. Costs may be negative.

networkEdges

networkEdges :: Network -> [NetworkEdge] Source #

Return original network edges in input/ID order, retaining capacities and costs.

FlowResult

data FlowResult Source #

Exact net flow,total edge cost,and original-edge-order flows. A maximum-flow result alone does not certify minimum cost.

Constructors

FlowResult
Fields flowValue :: Integer Exact net flow leaving the chosen source. edgeFlows :: [Integer] Exact edge flows in original network edge order, preserving parallel and antiparallel identity. flowCost :: Integer Sum of edge flow times edge unit cost; maximum-flow methods do not necessarily minimize this cost.

Instances

Instances details

Show FlowResult Source #
Instance details Defined in HMath.Graph.Flow Methods showsPrec :: Int -> FlowResult -> ShowS # show :: FlowResult -> String # showList :: [FlowResult] -> ShowS #
Eq FlowResult Source #
Instance details Defined in HMath.Graph.Flow Methods (==) :: FlowResult -> FlowResult -> Bool # (/=) :: FlowResult -> FlowResult -> Bool #

fordFulkerson

fordFulkerson :: Int -> Network -> Int -> Int -> Either MathError FlowResult Source #

Given augmentation budget,network,source,sink, compute exact maximum flow using depth-first augmenting paths. Invalid/non-distinct endpoints or negative budget fails; exhausted budget returns NonConvergence. Result retains per-edge flows and total cost.

edmondsKarp

edmondsKarp :: Int -> Network -> Int -> Int -> Either MathError FlowResult Source #

Given augmentation budget,network,source,sink, compute exact maximum flow using breadth-first shortest augmenting paths. Invalid input or exhausted budget fails; parallel/antiparallel edge flows retain identity.

dinic

dinic :: Int -> Network -> Int -> Int -> Either MathError FlowResult Source #

Given work budget,network,source,sink, compute maximum flow with level graphs and blocking-flow augmentation. Invalid sourcesinkbudget or exhausted work returns Left MathError; result includes flows in original edge order.

pushRelabel

pushRelabel :: Int -> Network -> Int -> Int -> Either MathError FlowResult Source #

Given push/relabel work budget,network,source,sink, compute exact maximum flow by preflow and relabel operations. Reject invalid endpoints/budget; work exhaustion returns NonConvergence.

minimumCut

minimumCut :: Int -> Network -> Int -> Int -> Either MathError ([Int], Integer) Source #

Source-side vertices and cut capacity, using Edmonds--Karp residual reach.

minimumCostMaximumFlow

minimumCostMaximumFlow :: Int -> Network -> Int -> Int -> Either MathError FlowResult Source #

Maximum flow followed by exact negative-residual-cycle cancellation. This supports negative costs (including disconnected cycles) and finds the minimum cost among all maximum flows. The same budget bounds each phase separately.

hopcroftKarp

hopcroftKarp :: BipartiteGraph -> [(Int, Int)] Source #

Hopcroft--Karp layered augmenting paths. Returns (left,right) matching; parallel edges are coalesced and weights are ignored.

hungarian

hungarian :: [[Integer]] -> Either MathError (Integer, [(Int, Int)]) Source #

Rectangular Hungarian primal-dual assignment, rows <= columns <= 256. Every row is assigned to a distinct column; exact integer costs may be negative.