addLinkedNode!(node::OneWayNodes, label::Int)

Add a node of type OneWayNodes with a link to another node Return the new node ::OneWayNodes

Arguments

• node::OneWayNodes: the node to link to
• label::Int: the label of the new node

findAugmentingPath(matching::Dict{Int,Int}, matched::BitVector, am::BitArray{2})

Find an augmenting path to improve a bipartite matching by performing a breadth first search on the unmatched column nodes, one at a time Return the path, or nothing if there isn't one ::Union{Vector{Int}, nothing}

Arguments

• matching::Dict{Int,Int}: the matching to augment, (row => col)
• matched::BitVector: a list of matched columns
• am::BitArray{2}: the bipartite graph

findgreedybipartitematching(am::BitArray{2})

Find a greedy bipartite matching by iteratively trying to pair each node in the first partition with a node in the second partition Return a matching of rows to columns, and a list of matched col values ::Dict{Int, Int}, ::BitVector

Arguments

• am::BitArray{2}: the bipartite graph

findmaxcardinalitybipartitematching(am::BitArray{2})

Find a maximum cardinality bipartite matching using a breadth first search for augmenting paths Return a matching of rows to columns and a list of matched col values ::Dict{Int, Int}, ::BitVector

Arguments

• am::BitArray{2}: the bipartite graph (as an adjacency matrix)

getPath(node::OneWayNodes)

Find the path from a node to its endPoint Return the path ::Vector{Int}

Arguments

• node::OneWayNodes: the end of the path

updateBipartiteMatching!(matching::Dict{Int,Int}, matched::BitVector, augmentingPath::Vector{Int})

Update a matching based on an augmenting path Return the new matching of rows to columns, and a list of matched col values ::Dict{Int, Int}, ::BitVector

Arguments

• matching::Dict{Int,Int}: the matching to update, (row => col)
• matched::BitVector: a list of matched columns
• augmentingPath::Vector{Int}: the augmenting path to use to update the matching