Class BipartiteGraphMatching

java.lang.Object
org.jacop.util.BipartiteGraphMatching

public class BipartiteGraphMatching extends Object
  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    (package private) int[][]
     
    (package private) int[]
     
    (package private) static final int
     
    (package private) int
     
    (package private) int
     
    (package private) static final int
     
    (package private) int[]
     
    (package private) int[]
     
  • Constructor Summary

    Constructors
    Constructor
    Description
    BipartiteGraphMatching(int[][] adj, int m, int n)
    Constructs data structure for Hopcroft Karp algorithm for maximum matching.
    BipartiteGraphMatching(int m, int n)
    Constructs empty data structure for Hopcroft Karp algorithm for maximum matching edges can be added by addEdge method.
  • Method Summary

    Modifier and Type
    Method
    Description
    (package private) void
    addEdge(int u, int v)
     
    (package private) boolean
    bfs()
     
    (package private) boolean
    dfs(int u)
     
    int
     

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • Field Details

  • Constructor Details

    • BipartiteGraphMatching

      public BipartiteGraphMatching(int m, int n)
      Constructs empty data structure for Hopcroft Karp algorithm for maximum matching edges can be added by addEdge method.
      Parameters:
      m - m is number of vertices on left side (u)
      n - n is a maximum number of vertices on right side (v)
    • BipartiteGraphMatching

      public BipartiteGraphMatching(int[][] adj, int m, int n)
      Constructs data structure for Hopcroft Karp algorithm for maximum matching.
      Parameters:
      adj - adjency matrix; adj stores adjacents vertices of vertex 'u'
      m - m is number of vertices on left side (u)
      n - n is a maximum number of vertices on right side (v)
  • Method Details

    • hopcroftKarp

      public int hopcroftKarp()
    • bfs

      boolean bfs()
    • dfs

      boolean dfs(int u)
    • addEdge

      void addEdge(int u, int v)