// FordFulkerson algorithm for maximum flow problem, with/without EdmondKarp improvement
FordFulkerson algorithm for maximum flow problem, with/without EdmondKarp improvement
// FordFulkerson algorithm for maximum flow problem with / without EdmondKarp improvement
func FordFulkerson(f *flownetwork.FlowNetwork, edmondsKarp bool) flownetwork.EdgeFlowUnit {
	fmt.Printf("FordFulkerson, EmondsKarp %v\n", edmondsKarp)
	currFlow := newFlow(f)
	for {
		rn := calculateResidualNetwork(f, currFlow)
		var augmentingPath graph.Path
		if edmondsKarp { 
			bfs, err := bfs.NewBfs(rn.Graph, f.Source(), func(u graph.NodeID) bfs.SearchControlCondition {
				if u == f.Target() {
					return bfs.Break
				}
				return bfs.Continue
			})
			if err != nil {
				break 
			}
			_, path, err := bfs.Query(f.Target())
			if err != nil {
				break 
			}
			augmentingPath = path
		} else {
			dfs, _ := dfs.NewControllableDfs(rn.Graph, 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 
			}
			augmentingPath = path
		}
		augmentingFlow := newAugmentingFlow(rn.residualCapacities, augmentingPath)
		currFlow.minus(augmentingFlow)
	}
	return currFlow.value(f.Source())
}
func FordFulkerson ( f * flownetwork . FlowNetwork , edmondsKarp bool ) flownetwork . EdgeFlowUnit { fmt . Printf ( " \n " , edmondsKarp ) currFlow := newFlow ( f ) for { rn := calculateResidualNetwork ( f , currFlow ) var augmentingPath graph . Path if edmondsKarp { bfs , err := bfs . NewBfs ( rn . Graph , f . Source ( ) , func ( u graph . NodeID ) bfs . SearchControlCondition { if u == f . Target ( ) { return bfs . Break } return bfs . Continue } ) if err != nil { break } _ , path , err := bfs . Query ( f . Target ( ) ) if err != nil { break } augmentingPath = path } else { dfs , _ := dfs . NewControllableDfs ( rn . Graph , 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 } augmentingPath = path } augmentingFlow := newAugmentingFlow ( rn . residualCapacities , augmentingPath ) currFlow . minus ( augmentingFlow ) } return currFlow . value ( f . Source ( ) ) }
FordFulkerson algorithm for maximum flow problem, with/without EdmondKarp improvement
FordFulkerson algorithm for maximum flow problem with / without EdmondKarp improvement
//initialize flow //currFlow.print() // phase 1, construct residual network based on original flow network and current flow // pahse 2, try to find augmenting path in the residual network graph //EdmondsKarp use BFS to find a path, better effectiveness //fmt.Println(err) // bfs failed //fmt.Println(err) // no more agumenting path can be found //fmt.Println(err) // no more agumenting path can be found //fmt.Println(augmentingPath) // phase 3, generate augmenting flow from augmenting path // phase 4, current flow - augmenting flow