refactory flowGraph

Ubuntu · Ubuntu · commit d4d2eb7f94e3 · 2018-05-16T01:19:35.000-07:00
diff --git a/graph/flowGraph.go b/graph/flowGraph.go
@@ -4,7 +4,36 @@ import (
 	"math"
 )
 
-func augmentingPath(g flowGraph, s interface{}, t interface{}) (int, []edge) {
+type residualGraph interface {
+	flowGraph
+	RCap(edge) int
+}
+
+type adjacencyMatrixResidual struct {
+	adjacencyMatrixWithFlow
+}
+
+func (g *adjacencyMatrixResidual) init() *adjacencyMatrixResidual {
+	g.adjacencyMatrixWithFlow.init()
+	return g
+}
+
+func (g *adjacencyMatrixResidual) AddEdgeWithFlow(e edge, f int) {
+	g.adjacencyMatrixWithFlow.AddEdgeWithFlow(e, f)
+	if g.RCap(e) == 0 {
+		g.DeleteEdge(e)
+	}
+}
+
+func (g *adjacencyMatrixResidual) RCap(e edge) int {
+	return g.Cap(e) - g.Flow(e)
+}
+
+func newResidualGraph() residualGraph {
+	return new(adjacencyMatrixResidual).init()
+}
+
+func augmentingPath(g residualGraph, s interface{}, t interface{}) (int, []edge) {
 	augmentingEdges := make([]edge, 0, 0)
 	minRC := math.MaxInt32
 	handler := newBFSVisitHandler()
@@ -25,28 +54,18 @@ func augmentingPath(g flowGraph, s interface{}, t interface{}) (int, []edge) {
 	return minRC, augmentingEdges
 }
 
-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)
-		}
-	}
-
+func updateFlow(rg residualGraph, g flowGraph, rc int, edges []edge) {
 	for _, e := range edges {
 		flow := g.Flow(e) + rc
 		g.AddEdgeWithFlow(e, flow)
-		updateResidualGraph(rg, flow, e)
+		rg.AddEdgeWithFlow(e, flow)
+		re := edge{e.End, e.Start}
+		rg.AddEdgeWithFlow(re, 0-flow)
 	}
 }
 
 func edmondsKarp(g flowGraph, s interface{}, t interface{}) {
-	residualG := newFlowGraph()
+	residualG := newResidualGraph()
 	for _, e := range g.AllEdges() {
 		g.AddEdgeWithFlow(e, 0)
 		residualG.AddEdgeWithCap(e, g.Cap(e))
diff --git a/graph/graph.go b/graph/graph.go
@@ -203,7 +203,6 @@ type flowGraph interface {
 	graph
 	Cap(edge) int
 	Flow(edge) int
-	RCap(edge) int
 	AddEdgeWithCap(edge, int)
 	AddEdgeWithFlow(edge, int)
 }
@@ -214,7 +213,7 @@ type adjacencyMatrixWithFlow struct {
 	flow map[edge]int
 }
 
-func (g *adjacencyMatrixWithFlow) Init() *adjacencyMatrixWithFlow {
+func (g *adjacencyMatrixWithFlow) init() *adjacencyMatrixWithFlow {
 	g.adjacencyMatrix.init()
 	g.cap = make(map[edge]int)
 	g.flow = make(map[edge]int)
@@ -245,10 +244,6 @@ func (g *adjacencyMatrixWithFlow) Flow(e edge) int {
 	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)
@@ -264,5 +259,5 @@ func (g *adjacencyMatrixWithFlow) DeleteEdgeBi(e edge) {
 }
 
 func newFlowGraph() flowGraph {
-	return new(adjacencyMatrixWithFlow).Init()
+	return new(adjacencyMatrixWithFlow).init()
 }
diff --git a/heap/fibHeap.go b/heap/fibHeap.go
@@ -148,7 +148,7 @@ type FibHeap struct {
 	mixin FibHeapMixin
 }
 
-//Init : Cross package
+//init : Cross package
 func (h *FibHeap) Init(mixin FibHeapMixin) *FibHeap {
 	h.root = newFabHeapElementList(nil)
 	h.min = nil

Original file line number	Diff line number	Diff line change
`@@ -203,7 +203,6 @@ type flowGraph interface {`
`203`	`203`	`graph`
`204`	`204`	`Cap(edge) int`
`205`	`205`	`Flow(edge) int`
`206`		`- RCap(edge) int`
`207`	`206`	`AddEdgeWithCap(edge, int)`
`208`	`207`	`AddEdgeWithFlow(edge, int)`
`209`	`208`	`}`
`@@ -214,7 +213,7 @@ type adjacencyMatrixWithFlow struct {`
`214`	`213`	`flow map[edge]int`
`215`	`214`	`}`
`216`	`215`
`217`		`-func (g adjacencyMatrixWithFlow) Init() adjacencyMatrixWithFlow {`
	`216`	`+func (g adjacencyMatrixWithFlow) init() adjacencyMatrixWithFlow {`
`218`	`217`	`g.adjacencyMatrix.init()`
`219`	`218`	`g.cap = make(map[edge]int)`
`220`	`219`	`g.flow = make(map[edge]int)`
`@@ -245,10 +244,6 @@ func (g *adjacencyMatrixWithFlow) Flow(e edge) int {`
`245`	`244`	`return g.flow[e]`
`246`	`245`	`}`
`247`	`246`
`248`		`-func (g *adjacencyMatrixWithFlow) RCap(e edge) int {`
`249`		`- return g.Cap(e) - g.Flow(e)`
`250`		`-}`
`251`		`-`
`252`	`247`	`func (g *adjacencyMatrixWithFlow) DeleteEdge(e edge) {`
`253`	`248`	`g.adjacencyMatrix.DeleteEdge(e)`
`254`	`249`	`delete(g.cap, e)`
`@@ -264,5 +259,5 @@ func (g *adjacencyMatrixWithFlow) DeleteEdgeBi(e edge) {`
`264`	`259`	`}`
`265`	`260`
`266`	`261`	`func newFlowGraph() flowGraph {`
`267`		`- return new(adjacencyMatrixWithFlow).Init()`
	`262`	`+ return new(adjacencyMatrixWithFlow).init()`
`268`	`263`	`}`
Original file line number	Diff line number	Diff line change
`@@ -148,7 +148,7 @@ type FibHeap struct {`
`148`	`148`	`mixin FibHeapMixin`
`149`	`149`	`}`
`150`	`150`
`151`		`-//Init : Cross package`
	`151`	`+//init : Cross package`
`152`	`152`	`func (h FibHeap) Init(mixin FibHeapMixin) FibHeap {`
`153`	`153`	`h.root = newFabHeapElementList(nil)`
`154`	`154`	`h.min = nil`