add push relabel; biograph max match support multiple max flow algorithms

Ubuntu · Ubuntu · commit b1887a334504 · 2018-05-17T07:35:23.000-07:00
diff --git a/graph/flowGraph.go b/graph/flowGraph.go
@@ -21,16 +21,21 @@ func (g *adjacencyMatrixResidual) init() *adjacencyMatrixResidual {
 func (g *adjacencyMatrixResidual) AddEdgeWithFlow(e edge, f int) {
 	g.adjacencyMatrixWithFlow.AddEdgeWithFlow(e, f)
 	if g.RCap(e) == 0 {
-		g.DeleteEdge(e)
+		//delete edge but keep cap and flow, because if residual flow (RCap) change, this edge should be added back
+		g.adjacencyMatrix.DeleteEdge(e)
 	}
 }
 
 func (g *adjacencyMatrixResidual) RCap(e edge) int {
 	return g.Cap(e) - g.Flow(e)
 }
 
-func newResidualGraph() residualGraph {
-	return new(adjacencyMatrixResidual).init()
+func newResidualGraph(g flowGraph) residualGraph {
+	residualG := new(adjacencyMatrixResidual).init()
+	for _, e := range g.AllEdges() {
+		residualG.AddEdgeWithCap(e, g.Cap(e))
+	}
+	return residualG
 }
 
 func augmentingPath(g residualGraph, s interface{}, t interface{}) (int, []edge) {
@@ -64,20 +69,135 @@ func updateFlow(rg residualGraph, g flowGraph, rc int, edges []edge) {
 	}
 }
 
-func edmondsKarp(g flowGraph, s interface{}, t interface{}) {
-	residualG := newResidualGraph()
-	for _, e := range g.AllEdges() {
-		g.AddEdgeWithFlow(e, 0)
-		residualG.AddEdgeWithCap(e, g.Cap(e))
-	}
+func edmondesKarp(g flowGraph, s interface{}, t interface{}) {
+	residualG := newResidualGraph(g)
 
 	for rc, edges := augmentingPath(residualG, s, t); len(edges) > 0; rc, edges = augmentingPath(residualG, s, t) {
 		updateFlow(residualG, g, rc, edges)
 	}
 
 }
 
-func bioGraphMaxMatch(g graph, l []interface{}) graph {
+type preFlowGraph interface {
+	residualGraph
+	SetHeight(interface{}, int)
+	SetExcess(interface{}, int)
+	Height(interface{}) int
+	Excess(interface{}) int
+	Push(edge) bool
+	Relabel(interface{}) bool
+	Overflow(interface{}) bool
+}
+
+type adjacencyMatrixPreFlow struct {
+	adjacencyMatrixResidual
+	height, excess map[interface{}]int
+	s, t           interface{}
+}
+
+func (g *adjacencyMatrixPreFlow) init(s, t interface{}) *adjacencyMatrixPreFlow {
+	g.adjacencyMatrixResidual.init()
+	g.height = make(map[interface{}]int)
+	g.excess = make(map[interface{}]int)
+	g.s = s
+	g.t = t
+	return g
+}
+
+func (g *adjacencyMatrixPreFlow) SetHeight(v interface{}, h int) {
+	g.height[v] = h
+}
+
+func (g *adjacencyMatrixPreFlow) Height(v interface{}) int {
+	if _, ok := g.height[v]; !ok {
+		return 0
+	}
+	return g.height[v]
+}
+
+func (g *adjacencyMatrixPreFlow) SetExcess(v interface{}, e int) {
+	g.excess[v] = e
+}
+
+func (g *adjacencyMatrixPreFlow) Excess(v interface{}) int {
+	if _, ok := g.excess[v]; !ok {
+		return 0
+	}
+	return g.excess[v]
+}
+
+func (g *adjacencyMatrixPreFlow) Push(e edge) bool {
+	if g.Overflow(e.Start) && g.RCap(e) > 0 && g.Height(e.Start) == g.Height(e.End)+1 {
+		d := g.RCap(e)
+		if g.Excess(e.Start) < d {
+			d = g.Excess(e.Start)
+		}
+		flow := g.Flow(e) + d
+		g.AddEdgeWithFlow(e, flow)
+		re := edge{e.End, e.Start}
+		g.AddEdgeWithFlow(re, 0-flow)
+		g.SetExcess(e.Start, g.Excess(e.Start)-d)
+		g.SetExcess(e.End, g.Excess(e.End)+d)
+		return true
+	}
+	return false
+}
+
+func (g *adjacencyMatrixPreFlow) Relabel(v interface{}) bool {
+	if !g.Overflow(v) {
+		return false
+	}
+	iter := g.IterConnectedVertices(v)
+	minH := math.MaxInt32
+	for end := iter.Value(); end != nil; end = iter.Next() {
+		if g.Height(end) < minH {
+			minH = g.Height(end)
+		}
+		if g.Height(v) > g.Height(end) {
+			return false
+		}
+	}
+	g.SetHeight(v, minH+1)
+	return true
+}
+
+func (g *adjacencyMatrixPreFlow) Overflow(v interface{}) bool {
+	//According to definition, start and target vertex never overflow
+	return v != g.s && v != g.t && g.Excess(v) > 0
+}
+
+func newPreFlowGraph(g flowGraph, s interface{}, t interface{}) preFlowGraph {
+	preFlowG := new(adjacencyMatrixPreFlow).init(s, t)
+	vertices := g.AllVertices()
+	for _, e := range g.AllEdges() {
+		preFlowG.AddEdgeWithCap(e, g.Cap(e))
+	}
+	preFlowG.SetHeight(s, len(vertices))
+	iter := g.IterConnectedVertices(s)
+	for v := iter.Value(); v != nil; v = iter.Next() {
+		c := g.Cap(edge{s, v})
+		preFlowG.AddEdgeWithFlow(edge{s, v}, c)
+		preFlowG.AddEdgeWithFlow(edge{v, s}, 0-c)
+		preFlowG.SetExcess(v, c)
+		preFlowG.SetExcess(s, preFlowG.Excess(s)-c)
+	}
+	return preFlowG
+}
+
+func pushRelabel(g flowGraph, s interface{}, t interface{}) {
+	preFlowG := newPreFlowGraph(g, s, t)
+	for stop := false; !stop; {
+		stop = true
+		for _, e := range preFlowG.AllEdges() {
+			stop = stop && !preFlowG.Push(e) && !preFlowG.Relabel(e.Start) && !preFlowG.Relabel(e.End)
+		}
+	}
+	for _, e := range g.AllEdges() {
+		g.AddEdgeWithFlow(e, preFlowG.Flow(e))
+	}
+}
+
+func bioGraphMaxMatch(g graph, l []interface{}, flowAlg func(g flowGraph, s interface{}, t interface{})) graph {
 	//build flow graph
 	fG := newFlowGraph()
 	s := struct{ start string }{"s"}
@@ -91,7 +211,7 @@ func bioGraphMaxMatch(g graph, l []interface{}) graph {
 		}
 	}
 
-	edmondsKarp(fG, s, t)
+	flowAlg(fG, s, t)
 	matchG := newGraph()
 	for _, e := range fG.AllEdges() {
 		if fG.Flow(e) > 0 && e.Start != s && e.End != t {
diff --git a/graph/flowGraph_test.go b/graph/flowGraph_test.go
@@ -37,6 +37,24 @@ func flowGraphGolden(g flowGraph) flowGraph {
 	return flowG
 }
 
+func pushRelabelGolden(g flowGraph) flowGraph {
+	flowG := newFlowGraph()
+	for _, e := range g.AllEdges() {
+		flowG.AddEdgeWithCap(e, g.Cap(e))
+	}
+	flowG.AddEdgeWithFlow(edge{"s", "v1"}, 13)
+	flowG.AddEdgeWithFlow(edge{"s", "v2"}, 10)
+	flowG.AddEdgeWithFlow(edge{"v2", "v1"}, -1)
+	flowG.AddEdgeWithFlow(edge{"v1", "v2"}, 1)
+	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 bioGraphMaxMatchSetup() (graph, []interface{}) {
 	g := newGraph()
 	g.AddEdgeBi(edge{"l0", "r0"})
@@ -50,14 +68,22 @@ func bioGraphMaxMatchSetup() (graph, []interface{}) {
 	return g, []interface{}{"l0", "l1", "l2", "l3", "l4"}
 }
 
-func bioGraphMaxMatchGolden() graph {
+func bioGraphMaxMatchGoldenByEdmondesKarp() graph {
 	g := newGraph()
 	g.AddEdgeBi(edge{"l0", "r0"})
 	g.AddEdgeBi(edge{"l1", "r2"})
 	g.AddEdgeBi(edge{"l2", "r1"})
 	return g
 }
 
+func bioGraphMaxMatchGoldenByPushRelabel() graph {
+	g := newGraph()
+	g.AddEdgeBi(edge{"l1", "r0"})
+	g.AddEdgeBi(edge{"l4", "r2"})
+	g.AddEdgeBi(edge{"l2", "r1"})
+	return g
+}
+
 func checkFlowGraphOutOfOrder(t *testing.T, g, gGolden flowGraph) {
 	comparator := func(t *testing.T, v, vExp []interface{}, e, eExp []edge) {
 		for _, e := range eExp {
@@ -74,15 +100,26 @@ func checkFlowGraphOutOfOrder(t *testing.T, g, gGolden flowGraph) {
 	checkGraphOutOfOrderInString(t, g, gGolden, comparator)
 }
 
-func TestEdmondsKarp(t *testing.T) {
+func TestEdmondesKarp(t *testing.T) {
 	g := flowGraphSetup()
-	edmondsKarp(g, "s", "t")
+	edmondesKarp(g, "s", "t")
 	gGolden := flowGraphGolden(g)
 	checkFlowGraphOutOfOrder(t, g, gGolden)
 }
 
+func TestPushRelabel(t *testing.T) {
+	g := flowGraphSetup()
+	pushRelabel(g, "s", "t")
+	gGolden := pushRelabelGolden(g)
+	checkFlowGraphOutOfOrder(t, g, gGolden)
+}
+
 func TestBioGraphMaxMatch(t *testing.T) {
-	g := bioGraphMaxMatch(bioGraphMaxMatchSetup())
-	gGolden := bioGraphMaxMatchGolden()
+	bioG, l := bioGraphMaxMatchSetup()
+	gGolden := bioGraphMaxMatchGoldenByEdmondesKarp()
+	g := bioGraphMaxMatch(bioG, l, edmondesKarp)
+	checkGraphOutOfOrderInString(t, g, gGolden, nil)
+	g = bioGraphMaxMatch(bioG, l, pushRelabel)
+	gGolden = bioGraphMaxMatchGoldenByPushRelabel()
 	checkGraphOutOfOrderInString(t, g, gGolden, nil)
 }
