1 package bipartitegraph_test
2
3 import (
4 "reflect"
5
6 . "github.com/onsi/gomega/matchers/support/goraph/bipartitegraph"
7
8 . "github.com/onsi/ginkgo/v2"
9 . "github.com/onsi/gomega"
10 )
11
12 var _ = Describe("Bipartitegraph", func() {
13 Context("tiny graphs", func() {
14 var (
15 empty, _ = NewBipartiteGraph([]interface{}{}, []interface{}{}, func(x, y interface{}) (bool, error) { return true, nil })
16 oneLeft, _ = NewBipartiteGraph([]interface{}{1}, []interface{}{}, func(x, y interface{}) (bool, error) { return true, nil })
17 oneRight, _ = NewBipartiteGraph([]interface{}{}, []interface{}{1}, func(x, y interface{}) (bool, error) { return true, nil })
18 twoSeparate, _ = NewBipartiteGraph([]interface{}{1}, []interface{}{1}, func(x, y interface{}) (bool, error) { return false, nil })
19 twoConnected, _ = NewBipartiteGraph([]interface{}{1}, []interface{}{1}, func(x, y interface{}) (bool, error) { return true, nil })
20 )
21
22 It("Computes the correct largest matching", func() {
23 Ω(empty.LargestMatching()).Should(BeEmpty())
24 Ω(oneLeft.LargestMatching()).Should(BeEmpty())
25 Ω(oneRight.LargestMatching()).Should(BeEmpty())
26 Ω(twoSeparate.LargestMatching()).Should(BeEmpty())
27
28 Ω(twoConnected.LargestMatching()).Should(HaveLen(1))
29 })
30 })
31
32 Context("small yet complex graphs", func() {
33 var (
34 neighbours = func(x, y interface{}) (bool, error) {
35 switch x.(string) + y.(string) {
36 case "aw", "bw", "bx", "cy", "cz", "dx", "ew":
37 return true, nil
38 default:
39 return false, nil
40 }
41 }
42 graph, _ = NewBipartiteGraph(
43 []interface{}{"a", "b", "c", "d", "e"},
44 []interface{}{"w", "x", "y", "z"},
45 neighbours,
46 )
47 )
48
49 It("Computes the correct largest matching", func() {
50
51 Ω(graph.LargestMatching()).Should(HaveLen(3))
52 })
53
54 Describe("FreeLeftRight", func() {
55 When("all edges are given", func() {
56 It("returns correct free left and right values", func() {
57 freeLeft, freeRight := graph.FreeLeftRight(graph.Edges)
58 Expect(freeLeft).To(BeEmpty())
59 Expect(freeRight).To(BeEmpty())
60 })
61 })
62 When("largest matching edges are given", func() {
63 It("returns correct free left and right values", func() {
64 edges := graph.LargestMatching()
65 freeLeft, freeRight := graph.FreeLeftRight(edges)
66 Expect(freeLeft).To(ConsistOf("d", "e"))
67 Expect(freeRight).To(ConsistOf("z"))
68 })
69 })
70 })
71 })
72
73 When("node values are unhashable types", func() {
74 var (
75 neighbours = func(x, y interface{}) (bool, error) {
76 return reflect.DeepEqual(x, y), nil
77 }
78 graph, _ = NewBipartiteGraph(
79 []interface{}{[]int{1, 2}, []int{3, 4}},
80 []interface{}{[]int{1, 2}},
81 neighbours,
82 )
83 )
84 Describe("FreeLeftRight", func() {
85 It("returns correct free left and right values", func() {
86 edges := graph.LargestMatching()
87 freeLeft, freeRight := graph.FreeLeftRight(edges)
88 Expect(freeLeft).To(HaveLen(1))
89 Expect(freeLeft[0]).To(Equal([]int{3, 4}))
90 Expect(freeRight).To(BeEmpty())
91 })
92 })
93 })
94
95 Context("large yet simple graphs", func() {
96 var (
97 half = make([]interface{}, 100)
98 discreteNeighbours = func(x, y interface{}) (bool, error) { return false, nil }
99 completeNeighbours = func(x, y interface{}) (bool, error) { return true, nil }
100 bijectionNeighbours = func(x, y interface{}) (bool, error) {
101 return x.(int) == y.(int), nil
102 }
103 discrete, complete, bijection *BipartiteGraph
104 )
105
106 BeforeEach(func() {
107 for i := 0; i < len(half); i++ {
108 half[i] = i
109 }
110 discrete, _ = NewBipartiteGraph(half, half, discreteNeighbours)
111 complete, _ = NewBipartiteGraph(half, half, completeNeighbours)
112 bijection, _ = NewBipartiteGraph(half, half, bijectionNeighbours)
113 })
114
115 It("Computes the correct largest matching", func() {
116 Ω(discrete.LargestMatching()).Should(BeEmpty())
117 Ω(complete.LargestMatching()).Should(HaveLen(100))
118 Ω(bijection.LargestMatching()).Should(HaveLen(100))
119 })
120 })
121
122 Context("large graphs that are unpleasant for the algorithm", func() {
123 var (
124 half = make([]interface{}, 100)
125 neighbours1 = func(x, y interface{}) (bool, error) {
126 if x.(int) < 33 {
127 return x.(int) == y.(int), nil
128 } else if x.(int) < 66 {
129 return true, nil
130 } else {
131 return false, nil
132 }
133 }
134 neighbours2 = func(x, y interface{}) (bool, error) {
135 if x.(int) == 50 {
136 return true, nil
137 } else if x.(int) < 90 {
138 return x.(int) == y.(int), nil
139 } else {
140 return false, nil
141 }
142 }
143 neighbours3 = func(x, y interface{}) (bool, error) {
144 if y.(int) < x.(int)-20 {
145 return true, nil
146 } else {
147 return false, nil
148 }
149 }
150 graph1, graph2, graph3 *BipartiteGraph
151 )
152
153 BeforeEach(func() {
154 for i := 0; i < len(half); i++ {
155 half[i] = i
156 }
157 graph1, _ = NewBipartiteGraph(half, half, neighbours1)
158 graph2, _ = NewBipartiteGraph(half, half, neighbours2)
159 graph3, _ = NewBipartiteGraph(half, half, neighbours3)
160 })
161
162 It("Computes the correct largest matching", func() {
163 Ω(graph1.LargestMatching()).Should(HaveLen(66))
164 Ω(graph2.LargestMatching()).Should(HaveLen(90))
165 Ω(graph3.LargestMatching()).Should(HaveLen(79))
166 })
167 })
168 })
169
View as plain text