vendor/github.com/onsi/gomega/matchers/support/goraph/bipartitegraph/bipartitegraphmatching.go

   1 package bipartitegraph
   2
   3 import . "github.com/onsi/gomega/matchers/support/goraph/node"
   4 import . "github.com/onsi/gomega/matchers/support/goraph/edge"
   5 import "github.com/onsi/gomega/matchers/support/goraph/util"
   6
   7 func (bg *BipartiteGraph) LargestMatching() (matching EdgeSet) {
   8         paths := bg.maximalDisjointSLAPCollection(matching)
   9
  10         for len(paths) > 0 {
  11                 for _, path := range paths {
  12                         matching = matching.SymmetricDifference(path)
  13                 }
  14                 paths = bg.maximalDisjointSLAPCollection(matching)
  15         }
  16
  17         return
  18 }
  19
  20 func (bg *BipartiteGraph) maximalDisjointSLAPCollection(matching EdgeSet) (result []EdgeSet) {
  21         guideLayers := bg.createSLAPGuideLayers(matching)
  22         if len(guideLayers) == 0 {
  23                 return
  24         }
  25
  26         used := make(map[Node]bool)
  27
  28         for _, u := range guideLayers[len(guideLayers)-1] {
  29                 slap, found := bg.findDisjointSLAP(u, matching, guideLayers, used)
  30                 if found {
  31                         for _, edge := range slap {
  32                                 used[edge.Node1] = true
  33                                 used[edge.Node2] = true
  34                         }
  35                         result = append(result, slap)
  36                 }
  37         }
  38
  39         return
  40 }
  41
  42 func (bg *BipartiteGraph) findDisjointSLAP(
  43         start Node,
  44         matching EdgeSet,
  45         guideLayers []NodeOrderedSet,
  46         used map[Node]bool,
  47 ) ([]Edge, bool) {
  48         return bg.findDisjointSLAPHelper(start, EdgeSet{}, len(guideLayers)-1, matching, guideLayers, used)
  49 }
  50
  51 func (bg *BipartiteGraph) findDisjointSLAPHelper(
  52         currentNode Node,
  53         currentSLAP EdgeSet,
  54         currentLevel int,
  55         matching EdgeSet,
  56         guideLayers []NodeOrderedSet,
  57         used map[Node]bool,
  58 ) (EdgeSet, bool) {
  59         used[currentNode] = true
  60
  61         if currentLevel == 0 {
  62                 return currentSLAP, true
  63         }
  64
  65         for _, nextNode := range guideLayers[currentLevel-1] {
  66                 if used[nextNode] {
  67                         continue
  68                 }
  69
  70                 edge, found := bg.Edges.FindByNodes(currentNode, nextNode)
  71                 if !found {
  72                         continue
  73                 }
  74
  75                 if matching.Contains(edge) == util.Odd(currentLevel) {
  76                         continue
  77                 }
  78
  79                 currentSLAP = append(currentSLAP, edge)
  80                 slap, found := bg.findDisjointSLAPHelper(nextNode, currentSLAP, currentLevel-1, matching, guideLayers, used)
  81                 if found {
  82                         return slap, true
  83                 }
  84                 currentSLAP = currentSLAP[:len(currentSLAP)-1]
  85         }
  86
  87         used[currentNode] = false
  88         return nil, false
  89 }
  90
  91 func (bg *BipartiteGraph) createSLAPGuideLayers(matching EdgeSet) (guideLayers []NodeOrderedSet) {
  92         used := make(map[Node]bool)
  93         currentLayer := NodeOrderedSet{}
  94
  95         for _, node := range bg.Left {
  96                 if matching.Free(node) {
  97                         used[node] = true
  98                         currentLayer = append(currentLayer, node)
  99                 }
 100         }
 101
 102         if len(currentLayer) == 0 {
 103                 return []NodeOrderedSet{}
 104         } else {
 105                 guideLayers = append(guideLayers, currentLayer)
 106         }
 107
 108         done := false
 109
 110         for !done {
 111                 lastLayer := currentLayer
 112                 currentLayer = NodeOrderedSet{}
 113
 114                 if util.Odd(len(guideLayers)) {
 115                         for _, leftNode := range lastLayer {
 116                                 for _, rightNode := range bg.Right {
 117                                         if used[rightNode] {
 118                                                 continue
 119                                         }
 120
 121                                         edge, found := bg.Edges.FindByNodes(leftNode, rightNode)
 122                                         if !found || matching.Contains(edge) {
 123                                                 continue
 124                                         }
 125
 126                                         currentLayer = append(currentLayer, rightNode)
 127                                         used[rightNode] = true
 128
 129                                         if matching.Free(rightNode) {
 130                                                 done = true
 131                                         }
 132                                 }
 133                         }
 134                 } else {
 135                         for _, rightNode := range lastLayer {
 136                                 for _, leftNode := range bg.Left {
 137                                         if used[leftNode] {
 138                                                 continue
 139                                         }
 140
 141                                         edge, found := bg.Edges.FindByNodes(leftNode, rightNode)
 142                                         if !found || !matching.Contains(edge) {
 143                                                 continue
 144                                         }
 145
 146                                         currentLayer = append(currentLayer, leftNode)
 147                                         used[leftNode] = true
 148                                 }
 149                         }
 150
 151                 }
 152
 153                 if len(currentLayer) == 0 {
 154                         return []NodeOrderedSet{}
 155                 } else {
 156                         guideLayers = append(guideLayers, currentLayer)
 157                 }
 158         }
 159
 160         return
 161 }