Package org.jacop.util
Class BipartiteGraphMatching
java.lang.Object
org.jacop.util.BipartiteGraphMatching
-
Field Summary
Fields -
Constructor Summary
ConstructorsConstructorDescriptionBipartiteGraphMatching
(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
-
Field Details
-
NIL
static final int NIL- See Also:
-
INF
static final int INF- See Also:
-
m
int m -
n
int n -
adj
int[][] adj -
pairU
int[] pairU -
pairV
int[] pairV -
dist
int[] dist
-
-
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)
-