bipartitegraph

Documentation

Index

• type BipartiteGraph
  • func NewBipartiteGraph(leftValues, rightValues []interface{}, ...) (*BipartiteGraph, error)
  • func (bg *BipartiteGraph) FreeLeftRight(edges EdgeSet) (leftValues, rightValues []interface{})
  • func (bg *BipartiteGraph) LargestMatching() (matching EdgeSet)

Types

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.