Package org.jacop.util
Class BipartiteGraphMatching
- java.lang.Object
-
- org.jacop.util.BipartiteGraphMatching
-
public class BipartiteGraphMatching extends java.lang.Object
-
-
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()
-
-
-
Field Detail
-
NIL
static final int NIL
- See Also:
- Constant Field Values
-
INF
static final int INF
- See Also:
- Constant Field Values
-
m
int m
-
n
int n
-
adj
int[][] adj
-
pairU
int[] pairU
-
pairV
int[] pairV
-
dist
int[] dist
-
-
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)
-
-