-
Notifications
You must be signed in to change notification settings - Fork 1.8k
/
TurboMatching.java
110 lines (94 loc) · 4.04 KB
/
TurboMatching.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
package com.jwetherell.algorithms.graph;
import com.jwetherell.algorithms.data_structures.Graph;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
/**
* In the mathematical discipline of graph theory, a matching or independent edge set
* in a graph is a set of edges without common vertices. In some matchings, all the vertices
* may incident with some edge of the matching, but this is not required and can only occur
* if the number of vertices is even.
* <p>
* @see <a href="https://en.wikipedia.org/wiki/Matching_(graph_theory)">Matching (Wikipedia)</a>
* <br>
* @author Jakub Szarawarski <[email protected]>
* @author Justin Wetherell <[email protected]>
*/
public class TurboMatching {
/**
* Computes maximum matching, using turbomatching algorithm based on augmenting paths with O(EV) complexity.
*
* @param graph bipartite graph
* @param <T> parameter of graph on which network is based
* @return a MatchingResult class instance containg a map of mates for each paired vertex and number of pairs
*/
public static <T extends Comparable<T>> MatchingResult<T> getMaximumMatching(Graph<T> graph){
final Map<Graph.Vertex<T>, Graph.Vertex<T>> mate = new HashMap<Graph.Vertex<T>, Graph.Vertex<T>>();
while (pathset(graph, mate));
return new MatchingResult<T>(mate);
}
/**
* Searches for an augmenting path for each unmatched vertex.
*
* @param graph bipartite graph
* @param mate map containing a mate for each matched vertex
* @return information if any augmenting path was found
*/
private static <T extends Comparable<T>> boolean pathset(Graph<T> graph, Map<Graph.Vertex<T>, Graph.Vertex<T>> mate){
final Set<Graph.Vertex<T>> visited = new HashSet<Graph.Vertex<T>>();
boolean result = false;
for (Graph.Vertex<T> vertex : graph.getVertices()) {
if (mate.containsKey(vertex) == false) {
if (path(graph, mate, visited, vertex))
result = true;
}
}
return result;
}
/**
* Searches for an augmenting path for a vertex.
* Refreshes mates map appropriately.
*
* @param graph bipartite graph
* @param mate map containing a mate for each matched vertex
* @param visited set containing vertices visited in current pathset
* @param vertex regarded vertex
* @param <T> parameter of graph on which network is based
* @return information if an augmenting path was found
*/
private static <T extends Comparable<T>> boolean path(Graph<T> graph, Map<Graph.Vertex<T>, Graph.Vertex<T>> mate, Set<Graph.Vertex<T>> visited, Graph.Vertex<T> vertex){
if (visited.contains(vertex))
return false;
visited.add(vertex);
for (Graph.Edge<T> edge : vertex.getEdges()) {
final Graph.Vertex<T> neighbour = edge.getFromVertex().equals(vertex) ? edge.getToVertex() : edge.getFromVertex();
if (mate.containsKey(neighbour) == false || path(graph, mate, visited, mate.get(neighbour))) {
mate.put(vertex, neighbour);
mate.put(neighbour, vertex);
return true;
}
}
return false;
}
public static class MatchingResult<T extends Comparable<T>>{
private final Map<Graph.Vertex<T>, Graph.Vertex<T>> mate;
private final int size;
private MatchingResult(Map<Graph.Vertex<T>, Graph.Vertex<T>> mate){
this.mate = mate;
this.size = mate.size()/2;
}
/**
* @return the number of edges in independent edge set
*/
public int getSize(){
return this.size;
}
/**
* @return a symetric map that contains a mate for each matched vertex
*/
public Map<Graph.Vertex<T>, Graph.Vertex<T>> getMate(){
return this.mate;
}
}
}