// Dinic algorithm for maximum flow problem
Dinic algorithm for maximum flow problem
// Dinic algorithm for maximum flow problem
func Dinic(f *flownetwork.FlowNetwork) flownetwork.EdgeFlowUnit {
	fmt.Println("Dinic")
	currFlow := newFlow(f)
	for {
		rn := calculateResidualNetwork(f, currFlow)
		lg, err := bfs.NewLevelGraph(rn, f.Source(), func(u graph.NodeID) bfs.SearchControlCondition {
			if u == f.Target() {
				return bfs.Break
			}
			return bfs.Continue
		})
		if err != nil {
			fmt.Println(err)
			break 
		}
		ln := newLevelNetwork(lg, rn)
		blockingFlow := flowStorage{}
		for {
			dfs, _ := dfs.NewControllableDfs(lg, f.Source(), func(u graph.NodeID) dfs.SearchControlCondition {
				if u == f.Target() {
					return dfs.Break
				}
				return dfs.Continue
			})
			path, err := dfs.Query(f.Source(), f.Target())
			if err != nil {
				break 
			}
			augmentingFlow := ln.retrieveAndRemoveFlow(path)
			blockingFlow.plus(augmentingFlow)
		}
		if blockingFlow.empty() {
			break 
		}
		currFlow.minus(blockingFlow)
	}
	return currFlow.value(f.Source())
}
func Dinic ( f * flownetwork . FlowNetwork ) flownetwork . EdgeFlowUnit { fmt . Println ( " " ) currFlow := newFlow ( f ) for { rn := calculateResidualNetwork ( f , currFlow ) lg , err := bfs . NewLevelGraph ( rn , f . Source ( ) , func ( u graph . NodeID ) bfs . SearchControlCondition { if u == f . Target ( ) { return bfs . Break } return bfs . Continue } ) if err != nil { fmt . Println ( err ) break } ln := newLevelNetwork ( lg , rn ) blockingFlow := flowStorage { } for { dfs , _ := dfs . NewControllableDfs ( lg , f . Source ( ) , func ( u graph . NodeID ) dfs . SearchControlCondition { if u == f . Target ( ) { return dfs . Break } return dfs . Continue } ) path , err := dfs . Query ( f . Source ( ) , f . Target ( ) ) if err != nil { break } augmentingFlow := ln . retrieveAndRemoveFlow ( path ) blockingFlow . plus ( augmentingFlow ) } if blockingFlow . empty ( ) { break } currFlow . minus ( blockingFlow ) } return currFlow . value ( f . Source ( ) ) }
Dinic algorithm for maximum flow problem
Dinic algorithm for maximum flow problem
//initialize flow //currFlow.print() // phase 1, construct residual network based on original flow network and current flow // phase 2, construct level graph from residual network // can not construct a new level graph by BFS // phase 3, try to find blocking flow on the level graph //  here we use DFS as typical method //fmt.Println(err) // no more agumenting path can be found // no more blocking flow can be found // phase 4, current flow - augmenting flow (blocking flow)