add flow graph

Ubuntu · Ubuntu · commit 1cde356c121c · 2018-05-13T23:29:32.000-07:00
diff --git a/graph/graph.go b/graph/graph.go
@@ -2,6 +2,7 @@ package graph
 
 import (
 	"container/list"
+	"fmt"
 )
 
 const (
@@ -374,6 +375,122 @@ func newAdjacencyListWithWeight() *adjacencyListWithWeight {
 	return new(adjacencyListWithWeight).Init()
 }
 
+type flowGraph interface {
+	graph
+	Cap(edge) int
+	Flow(edge) int
+	AddEdgeWithCap(edge, int)
+	AddEdgeWithFlow(edge, int)
+}
+
+type adjacencyMatrixWithFlow struct {
+	adjacencyMatrix
+	cap  map[edge]int
+	flow map[edge]int
+}
+
+func (g *adjacencyMatrixWithFlow) Init() *adjacencyMatrixWithFlow {
+	g.adjacencyMatrix.init()
+	g.cap = make(map[edge]int)
+	g.flow = make(map[edge]int)
+	return g
+}
+
+func (g *adjacencyMatrixWithFlow) AddEdgeWithCap(e edge, c int) {
+	g.adjacencyMatrix.AddEdge(e)
+	g.cap[e] = c
+}
+
+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 {
+	return g.cap[e]
+}
+
+func (g *adjacencyMatrixWithFlow) Flow(e edge) int {
+	return g.flow[e]
+}
+
+func (g *adjacencyMatrixWithFlow) DeleteEdge(e edge) {
+	g.adjacencyMatrix.DeleteEdge(e)
+	delete(g.cap, e)
+	delete(g.flow, e)
+}
+
+func (g *adjacencyMatrixWithFlow) AddEdgeBi(e edge) {
+	panic(fmt.Sprintln("not valid in flow graph!"))
+}
+
+func (g *adjacencyMatrixWithFlow) DeleteEdgeBi(e edge) {
+	panic(fmt.Sprintln("not valid in flow graph!"))
+}
+
+func newAdjacencyMatrixWithFlow() *adjacencyMatrixWithFlow {
+	return new(adjacencyMatrixWithFlow).Init()
+}
+
+type adjacencyListWithFlow struct {
+	adjacencyList
+	cap  map[edge]int
+	flow map[edge]int
+}
+
+func (g *adjacencyListWithFlow) Init() *adjacencyListWithFlow {
+	g.adjacencyList.init()
+	g.cap = make(map[edge]int)
+	g.flow = make(map[edge]int)
+	return g
+}
+
+func (g *adjacencyListWithFlow) AddEdgeWithCap(e edge, c int) {
+	g.adjacencyList.AddEdge(e)
+	g.cap[e] = c
+}
+
+func (g *adjacencyListWithFlow) 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.adjacencyList.AddEdge(e)
+	g.flow[e] = f
+}
+
+func (g *adjacencyListWithFlow) Cap(e edge) int {
+	return g.cap[e]
+}
+
+func (g *adjacencyListWithFlow) Flow(e edge) int {
+	return g.flow[e]
+}
+
+func (g *adjacencyListWithFlow) DeleteEdge(e edge) {
+	g.adjacencyList.DeleteEdge(e)
+	delete(g.cap, e)
+	delete(g.flow, e)
+}
+
+func (g *adjacencyListWithFlow) AddEdgeBi(e edge) {
+	panic(fmt.Sprintln("not valid in flow graph!"))
+}
+
+func (g *adjacencyListWithFlow) DeleteEdgeBi(e edge) {
+	panic(fmt.Sprintln("not valid in flow graph!"))
+}
+
+func newAdjacencyListWithFlow() *adjacencyListWithFlow {
+	return new(adjacencyListWithFlow).Init()
+}
+
 func adjacencyList2AdjacencyMatrix(l *adjacencyList) *adjacencyMatrix {
 	m := newAdjacencyMatrix()
 	for v := l.matrix.frontKey(); v != nil; v = l.matrix.nextKey(v) {
@@ -395,6 +512,12 @@ func adjacencyMatrix2AdjacencyList(m *adjacencyMatrix) *adjacencyList {
 }
 
 func createGraphByType(g graph) graph {
+	if _, isList := g.(*adjacencyListWithFlow); isList {
+		return newAdjacencyListWithFlow()
+	}
+	if _, isMatrix := g.(*adjacencyMatrixWithFlow); isMatrix {
+		return newAdjacencyMatrixWithFlow()
+	}
 	if _, isList := g.(*adjacencyListWithWeight); isList {
 		return newAdjacencyListWithWeight()
 	}
