diff options
Diffstat (limited to 'vendor/github.com/onsi/gomega/matchers/support')
5 files changed, 0 insertions, 277 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 deleted file mode 100644 index 119d21e..0000000 --- a/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraph.go +++ /dev/null @@ -1,41 +0,0 @@ -package bipartitegraph - -import "errors" -import "fmt" - -import . "github.com/onsi/gomega/matchers/support/goraph/node" -import . "github.com/onsi/gomega/matchers/support/goraph/edge" - -type BipartiteGraph struct { - Left NodeOrderedSet - Right NodeOrderedSet - Edges EdgeSet -} - -func NewBipartiteGraph(leftValues, rightValues []interface{}, neighbours func(interface{}, interface{}) (bool, error)) (*BipartiteGraph, error) { - left := NodeOrderedSet{} - for i, _ := range leftValues { - left = append(left, Node{i}) - } - - right := NodeOrderedSet{} - for j, _ := range rightValues { - right = append(right, Node{j + len(left)}) - } - - edges := EdgeSet{} - for i, leftValue := range leftValues { - for j, rightValue := range rightValues { - neighbours, err := neighbours(leftValue, rightValue) - if err != nil { - return nil, errors.New(fmt.Sprintf("error determining adjacency for %v and %v: %s", leftValue, rightValue, err.Error())) - } - - if neighbours { - edges = append(edges, Edge{left[i], right[j]}) - } - } - } - - return &BipartiteGraph{left, right, edges}, nil -} 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 deleted file mode 100644 index 32529c5..0000000 --- a/vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraphmatching.go +++ /dev/null @@ -1,161 +0,0 @@ -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{} - } else { - 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{} - } else { - guideLayers = append(guideLayers, currentLayer) - } - } - - return -} 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 deleted file mode 100644 index 4fd15cc..0000000 --- a/vendor/github.com/onsi/gomega/matchers/support/goraph/edge/edge.go +++ /dev/null @@ -1,61 +0,0 @@ -package edge - -import . "github.com/onsi/gomega/matchers/support/goraph/node" - -type Edge struct { - Node1 Node - Node2 Node -} - -type EdgeSet []Edge - -func (ec EdgeSet) Free(node Node) bool { - for _, e := range ec { - if e.Node1 == node || e.Node2 == node { - return false - } - } - - return true -} - -func (ec EdgeSet) Contains(edge Edge) bool { - for _, e := range ec { - if e == edge { - return true - } - } - - return false -} - -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) { - return e, true - } - } - - return Edge{}, false -} - -func (ec EdgeSet) SymmetricDifference(ec2 EdgeSet) EdgeSet { - edgesToInclude := make(map[Edge]bool) - - for _, e := range ec { - edgesToInclude[e] = true - } - - for _, e := range ec2 { - edgesToInclude[e] = !edgesToInclude[e] - } - - result := EdgeSet{} - for e, include := range edgesToInclude { - if include { - result = append(result, e) - } - } - - return result -} 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 deleted file mode 100644 index 800c2ea..0000000 --- a/vendor/github.com/onsi/gomega/matchers/support/goraph/node/node.go +++ /dev/null @@ -1,7 +0,0 @@ -package node - -type Node struct { - Id int -} - -type NodeOrderedSet []Node diff --git a/vendor/github.com/onsi/gomega/matchers/support/goraph/util/util.go b/vendor/github.com/onsi/gomega/matchers/support/goraph/util/util.go deleted file mode 100644 index d76a1ee..0000000 --- a/vendor/github.com/onsi/gomega/matchers/support/goraph/util/util.go +++ /dev/null @@ -1,7 +0,0 @@ -package util - -import "math" - -func Odd(n int) bool { - return math.Mod(float64(n), 2.0) == 1.0 -} |