coderxiaoma
diff --git a/‎graph/flowGraph.go
Lines changed: 85 additions & 0 deletions b/‎graph/flowGraph.go
Lines changed: 85 additions & 0 deletions
diff --git a/‎graph/flowGraph_test.go
Lines changed: 21 additions & 0 deletions b/‎graph/flowGraph_test.go
Lines changed: 21 additions & 0 deletions
diff --git a/‎temp/temp.go
Lines changed: 0 additions & 1 deletion b/‎temp/temp.go
Lines changed: 0 additions & 1 deletion
diff --git a/‎temp/temp_test.go
Lines changed: 0 additions & 1 deletion b/‎temp/temp_test.go
Lines changed: 0 additions & 1 deletion
diff --git a/‎temp2/temp.go
Lines changed: 0 additions & 1 deletion b/‎temp2/temp.go
Lines changed: 0 additions & 1 deletion
diff --git a/‎temp2/temp_test.go
Lines changed: 0 additions & 1 deletion b/‎temp2/temp_test.go
Lines changed: 0 additions & 1 deletion
@@ -277,3 +277,88 @@ func bipGraphMaxMatch(g graph, l []interface{}, flowAlg func(g flowGraph, s inte
 	}
 	return matchG
 }
+
+type hopcraftKarp struct {
+	g              graph // must be directed graph
+	dis            int
+	xMatch, yMatch map[interface{}]interface{}
+	xLevel, yLevel map[interface{}]int
+	matches        int
+}
+
+func (a *hopcraftKarp) init(g graph) *hopcraftKarp {
+	a.g = g
+	a.xMatch, a.yMatch = make(map[interface{}]interface{}), make(map[interface{}]interface{})
+	a.matches = 0
+	return a
+}
+
+func (a *hopcraftKarp) bfs() bool {
+	a.dis = math.MaxInt32
+	a.xLevel, a.yLevel = make(map[interface{}]int), make(map[interface{}]int)
+	//use queue
+	queue := list.New()
+	for _, x := range a.g.AllVertices() {
+		if _, ok := a.xMatch[x]; !ok {
+			queue.PushBack(x)
+			a.xLevel[x] = 0
+		}
+	}
+	for queue.Len() != 0 {
+		s := queue.Front().Value
+		queue.Remove(queue.Front())
+		if v, ok := a.xLevel[s]; ok && v > a.dis {
+			break
+		}
+		iter := a.g.IterConnectedVertices(s)
+		for y := iter.Value(); y != nil; y = iter.Next() {
+			if _, ok := a.yLevel[y]; !ok {
+				a.yLevel[y] = a.xLevel[s] + 1
+				if _, ok := a.yMatch[y]; !ok {
+					a.dis = a.yLevel[y]
+				} else {
+					a.xLevel[a.yMatch[y]] = a.yLevel[y] + 1
+					queue.PushBack(a.yMatch[y])
+				}
+			}
+		}
+	}
+	return a.dis != math.MaxInt32
+}
+
+func (a *hopcraftKarp) dfs(x interface{}, yVisit map[interface{}]bool) bool {
+	iter := a.g.IterConnectedVertices(x)
+	for y := iter.Value(); y != nil; y = iter.Next() {
+		//fmt.Println(x, y, yVisit, g.yLevel[y], g.xLevel[x], g.xMatch, g.yMatch)
+		if _, ok := yVisit[y]; !ok && a.yLevel[y] == a.xLevel[x]+1 {
+			yVisit[y] = true
+			if _, ok := a.yMatch[y]; ok && a.yLevel[y] == a.dis {
+				continue
+			}
+			if _, ok := a.yMatch[y]; !ok {
+				a.xMatch[x] = y
+				a.yMatch[y] = x
+				return true
+			} else if a.dfs(a.yMatch[y], yVisit) {
+				a.xMatch[x] = y
+				a.yMatch[y] = x
+				return true
+			}
+		}
+	}
+	return false
+}
+
+func (a *hopcraftKarp) maxMatch() int {
+	for a.bfs() {
+		yVisit := make(map[interface{}]bool)
+		for _, x := range a.g.AllVertices() {
+			if _, ok := a.xMatch[x]; !ok {
+				if a.dfs(x, yVisit) {
+					a.matches++
+				}
+			}
+		}
+	}
+	return a.matches
+}
@@ -84,6 +84,19 @@ func bipGraphMaxMatchGoldenByPushRelabel() graph {
 	return g
 }
 
+func hopcraftKarpSetup() graph {
+	g := newGraph()
+	g.AddEdge(edge{"l0", "r0"})
+	g.AddEdge(edge{"l1", "r0"})
+	g.AddEdge(edge{"l1", "r2"})
+	g.AddEdge(edge{"l2", "r1"})
+	g.AddEdge(edge{"l2", "r2"})
+	g.AddEdge(edge{"l2", "r3"})
+	g.AddEdge(edge{"l3", "r2"})
+	g.AddEdge(edge{"l4", "r2"})
+	return g
+}
+
 func bipGraphMaxMatchGoldenByRelabelToFront() graph {
 	g := newGraph()
 	g.AddEdgeBi(edge{"l0", "r0"})
@@ -143,3 +156,11 @@ func TestBipGraphMaxMatch(t *testing.T) {
 	gGolden = bipGraphMaxMatchGoldenByRelabelToFront()
 	checkGraphOutOfOrderInString(t, g, gGolden, nil)
 }
+
+func TestHopcraftKarp(t *testing.T) {
+	matches := new(hopcraftKarp).init(hopcraftKarpSetup()).maxMatch()
+	if matches != 3 {
+		t.Log("exp : 3 but get :", matches)
+		t.Fail()
+	}
+}