diff options
Diffstat (limited to 'vendor/github.com/onsi/gomega/matchers/support/goraph')
4 files changed, 48 insertions, 26 deletions
diff --git a/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraph.go b/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraph.go index 108f28586..830e30827 100644 --- a/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraph.go +++ b/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraph.go @@ -13,13 +13,13 @@ type BipartiteGraph struct { func NewBipartiteGraph(leftValues, rightValues []interface{}, neighbours func(interface{}, interface{}) (bool, error)) (*BipartiteGraph, error) { left := NodeOrderedSet{} - for i := range leftValues { - left = append(left, Node{Id: i}) + for i, v := range leftValues { + left = append(left, Node{ID: i, Value: v}) } right := NodeOrderedSet{} - for j := range rightValues { - right = append(right, Node{Id: j + len(left)}) + for j, v := range rightValues { + right = append(right, Node{ID: j + len(left), Value: v}) } edges := EdgeSet{} @@ -31,10 +31,26 @@ func NewBipartiteGraph(leftValues, rightValues []interface{}, neighbours func(in } if neighbours { - edges = append(edges, Edge{Node1: left[i], Node2: right[j]}) + edges = append(edges, Edge{Node1: left[i].ID, Node2: right[j].ID}) } } } return &BipartiteGraph{left, right, edges}, nil } + +// FreeLeftRight returns left node values and right node values +// of the BipartiteGraph's nodes which are not part of the given edges. +func (bg *BipartiteGraph) FreeLeftRight(edges EdgeSet) (leftValues, rightValues []interface{}) { + for _, node := range bg.Left { + if edges.Free(node) { + leftValues = append(leftValues, node.Value) + } + } + for _, node := range bg.Right { + if edges.Free(node) { + rightValues = append(rightValues, node.Value) + } + } + return +} diff --git a/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraphmatching.go b/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraphmatching.go index 8181f43a4..1c54edd8f 100644 --- a/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraphmatching.go +++ b/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraphmatching.go @@ -1,9 +1,14 @@ 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" - +import ( + . "github.com/onsi/gomega/matchers/support/goraph/edge" + . "github.com/onsi/gomega/matchers/support/goraph/node" + "github.com/onsi/gomega/matchers/support/goraph/util" +) + +// LargestMatching implements the Hopcroft–Karp algorithm taking as input a bipartite graph +// and outputting a maximum cardinality matching, i.e. a set of as many edges as possible +// with the property that no two edges share an endpoint. func (bg *BipartiteGraph) LargestMatching() (matching EdgeSet) { paths := bg.maximalDisjointSLAPCollection(matching) @@ -23,7 +28,7 @@ func (bg *BipartiteGraph) maximalDisjointSLAPCollection(matching EdgeSet) (resul return } - used := make(map[Node]bool) + used := make(map[int]bool) for _, u := range guideLayers[len(guideLayers)-1] { slap, found := bg.findDisjointSLAP(u, matching, guideLayers, used) @@ -43,7 +48,7 @@ func (bg *BipartiteGraph) findDisjointSLAP( start Node, matching EdgeSet, guideLayers []NodeOrderedSet, - used map[Node]bool, + used map[int]bool, ) ([]Edge, bool) { return bg.findDisjointSLAPHelper(start, EdgeSet{}, len(guideLayers)-1, matching, guideLayers, used) } @@ -54,16 +59,16 @@ func (bg *BipartiteGraph) findDisjointSLAPHelper( currentLevel int, matching EdgeSet, guideLayers []NodeOrderedSet, - used map[Node]bool, + used map[int]bool, ) (EdgeSet, bool) { - used[currentNode] = true + used[currentNode.ID] = true if currentLevel == 0 { return currentSLAP, true } for _, nextNode := range guideLayers[currentLevel-1] { - if used[nextNode] { + if used[nextNode.ID] { continue } @@ -84,17 +89,17 @@ func (bg *BipartiteGraph) findDisjointSLAPHelper( currentSLAP = currentSLAP[:len(currentSLAP)-1] } - used[currentNode] = false + used[currentNode.ID] = false return nil, false } func (bg *BipartiteGraph) createSLAPGuideLayers(matching EdgeSet) (guideLayers []NodeOrderedSet) { - used := make(map[Node]bool) + used := make(map[int]bool) currentLayer := NodeOrderedSet{} for _, node := range bg.Left { if matching.Free(node) { - used[node] = true + used[node.ID] = true currentLayer = append(currentLayer, node) } } @@ -113,7 +118,7 @@ func (bg *BipartiteGraph) createSLAPGuideLayers(matching EdgeSet) (guideLayers [ if util.Odd(len(guideLayers)) { for _, leftNode := range lastLayer { for _, rightNode := range bg.Right { - if used[rightNode] { + if used[rightNode.ID] { continue } @@ -123,7 +128,7 @@ func (bg *BipartiteGraph) createSLAPGuideLayers(matching EdgeSet) (guideLayers [ } currentLayer = append(currentLayer, rightNode) - used[rightNode] = true + used[rightNode.ID] = true if matching.Free(rightNode) { done = true @@ -133,7 +138,7 @@ func (bg *BipartiteGraph) createSLAPGuideLayers(matching EdgeSet) (guideLayers [ } else { for _, rightNode := range lastLayer { for _, leftNode := range bg.Left { - if used[leftNode] { + if used[leftNode.ID] { continue } @@ -143,7 +148,7 @@ func (bg *BipartiteGraph) createSLAPGuideLayers(matching EdgeSet) (guideLayers [ } currentLayer = append(currentLayer, leftNode) - used[leftNode] = true + used[leftNode.ID] = true } } diff --git a/vendor/github.com/onsi/gomega/matchers/support/goraph/edge/edge.go b/vendor/github.com/onsi/gomega/matchers/support/goraph/edge/edge.go index 4fd15cc06..8c38411b2 100644 --- a/vendor/github.com/onsi/gomega/matchers/support/goraph/edge/edge.go +++ b/vendor/github.com/onsi/gomega/matchers/support/goraph/edge/edge.go @@ -3,15 +3,15 @@ package edge import . "github.com/onsi/gomega/matchers/support/goraph/node" type Edge struct { - Node1 Node - Node2 Node + Node1 int + Node2 int } type EdgeSet []Edge func (ec EdgeSet) Free(node Node) bool { for _, e := range ec { - if e.Node1 == node || e.Node2 == node { + if e.Node1 == node.ID || e.Node2 == node.ID { return false } } @@ -31,7 +31,7 @@ func (ec EdgeSet) Contains(edge Edge) bool { func (ec EdgeSet) FindByNodes(node1, node2 Node) (Edge, bool) { for _, e := range ec { - if (e.Node1 == node1 && e.Node2 == node2) || (e.Node1 == node2 && e.Node2 == node1) { + if (e.Node1 == node1.ID && e.Node2 == node2.ID) || (e.Node1 == node2.ID && e.Node2 == node1.ID) { return e, true } } diff --git a/vendor/github.com/onsi/gomega/matchers/support/goraph/node/node.go b/vendor/github.com/onsi/gomega/matchers/support/goraph/node/node.go index 800c2ea8c..cd597a2f2 100644 --- a/vendor/github.com/onsi/gomega/matchers/support/goraph/node/node.go +++ b/vendor/github.com/onsi/gomega/matchers/support/goraph/node/node.go @@ -1,7 +1,8 @@ package node type Node struct { - Id int + ID int + Value interface{} } type NodeOrderedSet []Node |