package bipartitegraph

import "github.com/onsi/gomega/matchers/support/goraph/bipartitegraph"

Index ¶

• type BipartiteGraph
• func NewBipartiteGraph(leftValues, rightValues []any, neighbours func(any, any) (bool, error)) (*BipartiteGraph, error)
• func (bg *BipartiteGraph) FreeLeftRight(edges EdgeSet) (leftValues, rightValues []any)
• func (bg *BipartiteGraph) LargestMatching() (matching EdgeSet)

Types ¶

type BipartiteGraph ¶

type BipartiteGraph struct {
	Left  NodeOrderedSet
	Right NodeOrderedSet
	Edges EdgeSet
}

func NewBipartiteGraph ¶

func NewBipartiteGraph(leftValues, rightValues []any, neighbours func(any, any) (bool, error)) (*BipartiteGraph, error)

func (*BipartiteGraph) FreeLeftRight ¶

func (bg *BipartiteGraph) FreeLeftRight(edges EdgeSet) (leftValues, rightValues []any)

FreeLeftRight returns left node values and right node values of the BipartiteGraph's nodes which are not part of the given edges.

func (*BipartiteGraph) LargestMatching ¶

func (bg *BipartiteGraph) LargestMatching() (matching EdgeSet)

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.

Source Files ¶

bipartitegraph.go bipartitegraphmatching.go