Package bipartitegraph

type BipartiteGraph ¶

type BipartiteGraph struct {
    Left  NodeOrderedSet
    Right NodeOrderedSet
    Edges EdgeSet
}

func NewBipartiteGraph ¶

func NewBipartiteGraph(leftValues, rightValues []interface{}, neighbours func(interface{}, interface{}) (bool, error)) (*BipartiteGraph, error)

func (*BipartiteGraph) FreeLeftRight ¶

func (bg *BipartiteGraph) FreeLeftRight(edges EdgeSet) (leftValues, rightValues []interface{})

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.