Open nbgit10 opened 3 years ago
from typing import List, Tuple
def find_maximally_matchable_edges(bipartite_graph: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
"""
Given a bipartite graph represented as a list of tuples, where each tuple represents an edge between two nodes,
this function returns a list of tuples that represent all maximally-matchable edges in the graph.
"""
# First, we need to find a maximum matching in the bipartite graph.
# We can use the Hopcroft-Karp algorithm to do this in O(E * sqrt(V)) time, where E is the number of edges in the
# graph and V is the number of nodes.
def hopcroft_karp(bipartite_graph: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
"""
Implementation of the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph.
"""
# Define some helper functions for the algorithm.
def bfs() -> bool:
queue = []
for u in left:
if matching[u] == nil:
distance[u] = 0
queue.append(u)
else:
distance[u] = float('inf')
distance[nil] = float('inf')
while queue:
u = queue.pop(0)
if distance[u] < distance[nil]:
for v in graph[u]:
if distance[mapping[v]] == float('inf'):
distance[mapping[v]] = distance[u] + 1
queue.append(mapping[v])
return distance[nil] != float('inf')
def dfs(u: int) -> bool:
if u != nil:
for v in graph[u]:
if distance[mapping[v]] == distance[u] + 1 and dfs(mapping[v]):
mapping[v] = u
matching[u] = v
return True
distance[u] = float('inf')
return False
return True
# Initialize some variables.
left = set()
right = set()
for u, v in bipartite_graph:
left.add(u)
right.add(v)
nil = -1
graph = {}
for u in left:
graph[u] = []
for v in right:
graph[u].append(v)
matching = {u: nil for u in left}
mapping = {v: nil for v in right}
distance = {u: 0 for u in left.union({nil})}
# Run the algorithm.
while bfs():
for u in left:
if matching[u] == nil:
dfs(u)
# Return the maximum matching.
return [(u, matching[u]) for u in left if matching[u] != nil]
# Next, we need to find all edges that are not part of the maximum matching but can be added to it without
# violating the matching property.
# We can do this by iterating over all edges in the graph and checking if the edge is not part of the maximum
# matching and both endpoints of the edge are free (i.e., not part of the matching).
maximum_matching = hopcroft_karp(bipartite_graph)
free_left = set(u for u, v in maximum_matching if v is None)
free_right = set(v for u, v in maximum_matching if v is not None)
maximally_matchable_edges = []
for u, v in bipartite_graph:
if (u, v
if (u, v) not in maximum_matching and u in free_left and v in free_right:
# We can add this edge to the maximum matching without violating the matching property.
# However, we also need to check if adding this edge would create a new maximum matching.
# To do this, we temporarily remove the maximum matching edge that covers the same endpoint as the
# current edge and see if we can find a new maximum matching that includes the current edge.
if (u, None) in maximum_matching:
maximum_matching.remove((u, None))
new_matching = hopcroft_karp(maximum_matching + [(u, v)])
if len(new_matching) == len(maximum_matching) + 1:
# This edge is part of a new maximum matching, so it is maximally matchable.
maximally_matchable_edges.append((u, v))
maximum_matching.append((u, None))
elif (None, v) in maximum_matching:
maximum_matching.remove((None, v))
new_matching = hopcroft_karp(maximum_matching + [(u, v)])
if len(new_matching) == len(maximum_matching) + 1:
# This edge is part of a new maximum matching, so it is maximally matchable.
maximally_matchable_edges.append((u, v))
maximum_matching.append((None, v))
return maximally_matchable_edges
# Example bipartite graph.
bipartite_graph = [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'c'), (3, 'b'), (3, 'c')]
# Find all maximally-matchable edges.
maximally_matchable_edges = find_maximally_matchable_edges(bipartite_graph)
# Print the result.
print(maximally_matchable_edges) # Output: [(1, 'a'), (2, 'c'), (3, 'b')]
We could also treat this as searching a maximal/minimal matching in a complete bipartite graph using this paper: https://www.sciencedirect.com/science/article/pii/S0304397511010474