| package bipartitegraph |
| |
| import . "github.com/onsi/gomega/matchers/support/goraph/node" |
| import . "github.com/onsi/gomega/matchers/support/goraph/edge" |
| import "github.com/onsi/gomega/matchers/support/goraph/util" |
| |
| func (bg *BipartiteGraph) LargestMatching() (matching EdgeSet) { |
| paths := bg.maximalDisjointSLAPCollection(matching) |
| |
| for len(paths) > 0 { |
| for _, path := range paths { |
| matching = matching.SymmetricDifference(path) |
| } |
| paths = bg.maximalDisjointSLAPCollection(matching) |
| } |
| |
| return |
| } |
| |
| func (bg *BipartiteGraph) maximalDisjointSLAPCollection(matching EdgeSet) (result []EdgeSet) { |
| guideLayers := bg.createSLAPGuideLayers(matching) |
| if len(guideLayers) == 0 { |
| return |
| } |
| |
| used := make(map[Node]bool) |
| |
| for _, u := range guideLayers[len(guideLayers)-1] { |
| slap, found := bg.findDisjointSLAP(u, matching, guideLayers, used) |
| if found { |
| for _, edge := range slap { |
| used[edge.Node1] = true |
| used[edge.Node2] = true |
| } |
| result = append(result, slap) |
| } |
| } |
| |
| return |
| } |
| |
| func (bg *BipartiteGraph) findDisjointSLAP( |
| start Node, |
| matching EdgeSet, |
| guideLayers []NodeOrderedSet, |
| used map[Node]bool, |
| ) ([]Edge, bool) { |
| return bg.findDisjointSLAPHelper(start, EdgeSet{}, len(guideLayers)-1, matching, guideLayers, used) |
| } |
| |
| func (bg *BipartiteGraph) findDisjointSLAPHelper( |
| currentNode Node, |
| currentSLAP EdgeSet, |
| currentLevel int, |
| matching EdgeSet, |
| guideLayers []NodeOrderedSet, |
| used map[Node]bool, |
| ) (EdgeSet, bool) { |
| used[currentNode] = true |
| |
| if currentLevel == 0 { |
| return currentSLAP, true |
| } |
| |
| for _, nextNode := range guideLayers[currentLevel-1] { |
| if used[nextNode] { |
| continue |
| } |
| |
| edge, found := bg.Edges.FindByNodes(currentNode, nextNode) |
| if !found { |
| continue |
| } |
| |
| if matching.Contains(edge) == util.Odd(currentLevel) { |
| continue |
| } |
| |
| currentSLAP = append(currentSLAP, edge) |
| slap, found := bg.findDisjointSLAPHelper(nextNode, currentSLAP, currentLevel-1, matching, guideLayers, used) |
| if found { |
| return slap, true |
| } |
| currentSLAP = currentSLAP[:len(currentSLAP)-1] |
| } |
| |
| used[currentNode] = false |
| return nil, false |
| } |
| |
| func (bg *BipartiteGraph) createSLAPGuideLayers(matching EdgeSet) (guideLayers []NodeOrderedSet) { |
| used := make(map[Node]bool) |
| currentLayer := NodeOrderedSet{} |
| |
| for _, node := range bg.Left { |
| if matching.Free(node) { |
| used[node] = true |
| currentLayer = append(currentLayer, node) |
| } |
| } |
| |
| if len(currentLayer) == 0 { |
| return []NodeOrderedSet{} |
| } |
| guideLayers = append(guideLayers, currentLayer) |
| |
| done := false |
| |
| for !done { |
| lastLayer := currentLayer |
| currentLayer = NodeOrderedSet{} |
| |
| if util.Odd(len(guideLayers)) { |
| for _, leftNode := range lastLayer { |
| for _, rightNode := range bg.Right { |
| if used[rightNode] { |
| continue |
| } |
| |
| edge, found := bg.Edges.FindByNodes(leftNode, rightNode) |
| if !found || matching.Contains(edge) { |
| continue |
| } |
| |
| currentLayer = append(currentLayer, rightNode) |
| used[rightNode] = true |
| |
| if matching.Free(rightNode) { |
| done = true |
| } |
| } |
| } |
| } else { |
| for _, rightNode := range lastLayer { |
| for _, leftNode := range bg.Left { |
| if used[leftNode] { |
| continue |
| } |
| |
| edge, found := bg.Edges.FindByNodes(leftNode, rightNode) |
| if !found || !matching.Contains(edge) { |
| continue |
| } |
| |
| currentLayer = append(currentLayer, leftNode) |
| used[leftNode] = true |
| } |
| } |
| |
| } |
| |
| if len(currentLayer) == 0 { |
| return []NodeOrderedSet{} |
| } |
| guideLayers = append(guideLayers, currentLayer) |
| } |
| |
| return |
| } |