Packages

c

scalation.graphalytics

BipartiteMatcher

class BipartiteMatcher extends AnyRef

The BipartiteMatcher class provides an implementation of finding maximal Bipartite Matching.

See also

www.geeksforgeeks.org/maximum-bipartite-matching/

Linear Supertypes
AnyRef, Any
Ordering
  1. Alphabetic
  2. By Inheritance
Inherited
  1. BipartiteMatcher
  2. AnyRef
  3. Any
  1. Hide All
  2. Show All
Visibility
  1. Public
  2. All

Instance Constructors

  1. new BipartiteMatcher(bpGraph: Array[Array[Boolean]])

    bpGraph

    the bipartite graph

Value Members

  1. def bpm(u: Int, seen: Array[Boolean], matchR: Array[Int]): Boolean

    A DFS based recursive function that returns true if a matching for vertex u is possible.

    A DFS based recursive function that returns true if a matching for vertex u is possible.

    u

    vertex u to be check, whether matching is possible of u to any unmatched v

    seen

    array of vertex v, to keep track of whether v is already seen by some other u

    matchR

    array which contain information of vertex v is assigned to vertex u

  2. def maxBPM(): Int

    Returns maximum number of matching from 'M' to 'N'.

    Returns maximum number of matching from 'M' to 'N'. The value of 'matchR(i)' is the applicant number assigned to job 'i', the value -1 indicates nobody is assigned.