bipartitegraphmatching.go

Documentation: github.com/onsi/gomega/matchers/support/goraph/bipartitegraph

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