add Edmonds-Karp

Ubuntu · Ubuntu · commit 22dc62f01916 · 2018-05-15T00:56:51.000-07:00
diff --git a/graph/flowGraph.go b/graph/flowGraph.go
@@ -0,0 +1,71 @@
+package graph
+
+import (
+	"github.com/shady831213/algorithms/tree/disjointSetTree"
+	"math"
+)
+
+func augmentingPath(g flowGraph, s interface{}, t interface{}) (int, []edge) {
+	set := make(map[interface{}]*disjointSetTree.DisjointSet)
+	handler := newBFSVisitHandler()
+	handler.EdgeHandler = func(start, end *bfsElement) {
+		if _, ok := set[start.V]; !ok {
+			set[start.V] = disjointSetTree.MakeSet(start)
+		}
+		if _, ok := set[end.V]; !ok {
+			set[end.V] = disjointSetTree.MakeSet(end)
+		}
+		if g.RCap(edge{start.V, end.V}) > 0 {
+			disjointSetTree.Union(set[start.V], set[end.V])
+		}
+	}
+
+	bfsVisit(g, s, handler)
+
+	if _, ok := set[t]; ok && disjointSetTree.FindSet(set[t]) == disjointSetTree.FindSet(set[s]) {
+		augmentingEdges := make([]edge, 0, 0)
+		minRC := math.MaxInt32
+		for v := set[t].Value.(*bfsElement); v.P != nil; v = v.P {
+			currentEdge := edge{v.P.V, v.V}
+			augmentingEdges = append(augmentingEdges, currentEdge)
+			if rc := g.RCap(currentEdge); rc < minRC {
+				minRC = rc
+			}
+		}
+		return minRC, augmentingEdges
+	}
+	return 0, make([]edge, 0, 0)
+}
+
+func updateFlow(rg, g flowGraph, rc int, edges []edge) {
+	updateResidualGraph := func(g flowGraph, flow int, e edge) {
+		g.AddEdgeWithFlow(e, flow)
+		if g.RCap(e) == 0 {
+			g.DeleteEdge(e)
+		}
+		re := edge{e.End, e.Start}
+		g.AddEdgeWithFlow(re, 0-flow)
+		if g.RCap(re) == 0 {
+			g.DeleteEdge(re)
+		}
+	}
+
+	for _, e := range edges {
+		flow := g.Flow(e) + rc
+		g.AddEdgeWithFlow(e, flow)
+		updateResidualGraph(rg, flow, e)
+	}
+}
+
+func edmondsKarp(g flowGraph, s interface{}, t interface{}) {
+	residualG := createGraphByType(g).(flowGraph)
+	for _, e := range g.AllEdges() {
+		g.AddEdgeWithFlow(e, 0)
+		residualG.AddEdgeWithCap(e, g.Cap(e))
+	}
+
+	for rc, edges := augmentingPath(residualG, s, t); len(edges) > 0; rc, edges = augmentingPath(residualG, s, t) {
+		updateFlow(residualG, g, rc, edges)
+	}
+
+}
diff --git a/graph/flowGraph_test.go b/graph/flowGraph_test.go
@@ -0,0 +1,87 @@
+package graph
+
+import (
+	"sort"
+	"testing"
+)
+
+func flowGraphSetup(g flowGraph) {
+	g.AddEdgeWithCap(edge{"s", "v1"}, 16)
+	g.AddEdgeWithCap(edge{"s", "v2"}, 13)
+	g.AddEdgeWithCap(edge{"v2", "v1"}, 4)
+	g.AddEdgeWithCap(edge{"v1", "v2"}, 10)
+	g.AddEdgeWithCap(edge{"v1", "v3"}, 12)
+	g.AddEdgeWithCap(edge{"v3", "v2"}, 9)
+	g.AddEdgeWithCap(edge{"v2", "v4"}, 14)
+	g.AddEdgeWithCap(edge{"v4", "v3"}, 7)
+	g.AddEdgeWithCap(edge{"v3", "t"}, 20)
+	g.AddEdgeWithCap(edge{"v4", "t"}, 4)
+}
+
+func flowGraphGolden(g flowGraph) flowGraph {
+	flowG := createGraphByType(g).(flowGraph)
+	for _, e := range g.AllEdges() {
+		flowG.AddEdgeWithCap(e, g.Cap(e))
+	}
+	flowG.AddEdgeWithFlow(edge{"s", "v1"}, 12)
+	flowG.AddEdgeWithFlow(edge{"s", "v2"}, 11)
+	flowG.AddEdgeWithFlow(edge{"v2", "v1"}, 0)
+	flowG.AddEdgeWithFlow(edge{"v1", "v2"}, 0)
+	flowG.AddEdgeWithFlow(edge{"v1", "v3"}, 12)
+	flowG.AddEdgeWithFlow(edge{"v3", "v2"}, 0)
+	flowG.AddEdgeWithFlow(edge{"v2", "v4"}, 11)
+	flowG.AddEdgeWithFlow(edge{"v4", "v3"}, 7)
+	flowG.AddEdgeWithFlow(edge{"v3", "t"}, 19)
+	flowG.AddEdgeWithFlow(edge{"v4", "t"}, 4)
+	return flowG
+}
+
+func checkFlowGraphOutOfOrder(t *testing.T, g, gGolden flowGraph) {
+	edges := g.AllEdges()
+	//finish time increase order
+	vertexes := g.AllVertices()
+	sort.Slice(edges, func(i, j int) bool {
+		if edges[i].End.(string) == edges[j].End.(string) {
+			return edges[i].Start.(string) < edges[j].Start.(string)
+		}
+		return edges[i].End.(string) < edges[j].End.(string)
+	})
+
+	sort.Slice(vertexes, func(i, j int) bool {
+		return vertexes[i].(string) < vertexes[j].(string)
+	})
+
+	expEdges := gGolden.AllEdges()
+	expVertices := gGolden.AllVertices()
+
+	sort.Slice(expEdges, func(i, j int) bool {
+		if expEdges[i].End.(string) == expEdges[j].End.(string) {
+			return expEdges[i].Start.(string) < expEdges[j].Start.(string)
+		}
+		return expEdges[i].End.(string) < expEdges[j].End.(string)
+	})
+
+	sort.Slice(expVertices, func(i, j int) bool {
+		return expVertices[i].(string) < expVertices[j].(string)
+	})
+
+	compareGraph(t, vertexes, expVertices, edges, expEdges)
+	for _, e := range expEdges {
+		if g.Cap(e) != gGolden.Cap(e) {
+			t.Log(e, "Cap Error! exp :", gGolden.Cap(e), "actual: ", g.Cap(e))
+			t.FailNow()
+		}
+		if g.Flow(e) != gGolden.Flow(e) {
+			t.Log(e, "Flow Error! exp :", gGolden.Flow(e), "actual: ", g.Flow(e))
+			t.FailNow()
+		}
+	}
+}
+
+func TestEdmondsKarp(t *testing.T) {
+	g := newAdjacencyMatrixWithFlow()
+	flowGraphSetup(g)
+	edmondsKarp(g, "s", "t")
+	gGolden := flowGraphGolden(g)
+	checkFlowGraphOutOfOrder(t, g, gGolden)
+}
diff --git a/graph/graph.go b/graph/graph.go
@@ -203,6 +203,7 @@ type flowGraph interface {
 	graph
 	Cap(edge) int
 	Flow(edge) int
+	RCap(edge) int
 	AddEdgeWithCap(edge, int)
 	AddEdgeWithFlow(edge, int)
 }
@@ -226,23 +227,28 @@ func (g *adjacencyMatrixWithFlow) AddEdgeWithCap(e edge, c int) {
 }
 
 func (g *adjacencyMatrixWithFlow) AddEdgeWithFlow(e edge, f int) {
-	if _, ok := g.cap[e]; !ok {
-		panic(fmt.Sprintln("cap of edge ", e, "has not been set yet!"))
-	} else if f > g.cap[e] {
-		panic(fmt.Sprintln("flow of ", e, "is ", f, ", larger than cap ", g.cap[e]))
-	}
 	g.adjacencyMatrix.AddEdge(e)
 	g.flow[e] = f
 }
 
 func (g *adjacencyMatrixWithFlow) Cap(e edge) int {
+	if _, ok := g.cap[e]; !ok {
+		return 0
+	}
 	return g.cap[e]
 }
 
 func (g *adjacencyMatrixWithFlow) Flow(e edge) int {
+	if _, ok := g.flow[e]; !ok {
+		return 0
+	}
 	return g.flow[e]
 }
 
+func (g *adjacencyMatrixWithFlow) RCap(e edge) int {
+	return g.Cap(e) - g.Flow(e)
+}
+
 func (g *adjacencyMatrixWithFlow) DeleteEdge(e edge) {
 	g.adjacencyMatrix.DeleteEdge(e)
 	delete(g.cap, e)
