Safe Haskell	None
Language	Haskell2010

Dinic

Description

Dinic's algorithm, or Dinitz's algorithm

An algorithm to find the maximum flow in a flow network.

Sources:

Y. Dinitz, "Dinitz' Algorithm: The Original Version and Even's Version", 2006 https://www.cs.bgu.ac.il/~dinitz/Papers/Dinitz_alg.pdf
AC Library https://github.com/atcoder/ac-library/blob/master/atcoder/maxflow.hpp

Synopsis

data FlowEdge = FlowEdge {
- from_ :: !Vertex
- to_ :: !Vertex
- cap_ :: !Flow
}
data FlowResult = FlowResult {
- getFlow :: !Flow
- getFlows :: [Flow]
- getMinCut :: [Bool]
}
data ToEdge = ToEdge {
- to__ :: !Vertex
- edgeIndex_ :: !EdgeIndex
}
type Flow = Int
type EdgeIndex = Int
dinic :: Bounds -> [FlowEdge] -> Vertex -> Vertex -> FlowResult

Documentation

data FlowEdge Source #

Constructors

FlowEdge
Fields from_ :: !Vertex to_ :: !Vertex cap_ :: !Flow

Instances

Instances details

Eq FlowEdge Source #
Instance details Defined in Dinic Methods (==) :: FlowEdge -> FlowEdge -> Bool # (/=) :: FlowEdge -> FlowEdge -> Bool #
Show FlowEdge Source #
Instance details Defined in Dinic Methods showsPrec :: Int -> FlowEdge -> ShowS # show :: FlowEdge -> String # showList :: [FlowEdge] -> ShowS #
NFData FlowEdge Source #
Instance details Defined in Dinic Methods rnf :: FlowEdge -> () #

data FlowResult Source #

Constructors

FlowResult
Fields getFlow :: !Flow getFlows :: [Flow] getMinCut :: [Bool]

data ToEdge Source #

Constructors

ToEdge
Fields to__ :: !Vertex edgeIndex_ :: !EdgeIndex

type Flow = Int Source #

type EdgeIndex = Int Source #

dinic :: Bounds -> [FlowEdge] -> Vertex -> Vertex -> FlowResult Source #

Runs Dinic's algorithm on the graph made up of the given FlowEdges. Returns a FlowResult, describing a max flow configuration with 1. the max flow value 2. flow values of the edges in the order in which they were given 3. a list of Bools for each edge indicating whether the edge is in a min-cut O(V^2 E) in the general case. O(min(V^(23), E^(12)) E) for unit capacity graphs. O(V^(1/2) E) for unit networks, such as in maximum bipartite matching.