Class BipartiteGraphMatching


  • public class BipartiteGraphMatching
    extends java.lang.Object
    • Field Summary

      Fields 
      Modifier and Type Field Description
      (package private) int[][] adj  
      (package private) int[] dist  
      (package private) static int INF  
      (package private) int m  
      (package private) int n  
      (package private) static int NIL  
      (package private) int[] pairU  
      (package private) int[] pairV  
    • 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

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      (package private) void addEdge​(int u, int v)  
      (package private) boolean bfs()  
      (package private) boolean dfs​(int u)  
      int hopcroftKarp()  
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • 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 Detail

      • hopcroftKarp

        public int hopcroftKarp()
      • bfs

        boolean bfs()
      • dfs

        boolean dfs​(int u)
      • addEdge

        void addEdge​(int u,
                     int v)