Consider a connected undirected graph. A matching set of edges on this graph is defined as a set of edges such that no two edges in the set share a common vertex. For example, the left figure denotes a matching set in green, while the right figure denotes a non-matching set in red.
A matching set is said to be maximally matching, or a maximal matching if it is impossible to add another edge of the graph to the matching set. So both examples above are not maximal matching sets, but both of the sets below in blue are maximal matchings. Note that maximal matchings are not necessarily unique. Furthermore, there's not requirement that the size of each possible maximal matching for a graph is equal to another matching.
The goal of this challenge is to write a program/function to find a maximal matching of a graph.
Input
Assume all vertices of the input graph have some consecutive integer numbering starting at any beginning integer value of your choice. An edge is described by an unordered pair of integers denoting the vertices the edge connects. For example, the graph shown above could be described with the following unordered set of edges (assuming the numbering of vertices starts at 0):
[(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]
An alternative way to describe a graph is via an adjacency list. Here is an example adjacency list for the above graph:
[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]
Your program/function must take as input a graph from any source (stdio, function parameter, etc.). You may use any notation desired so long as the no additional non-trivial information is communicated to your program. For example, having an extra parameter denoting the number of input edges is perfectly acceptable. Similarly, passing in an unordered multiset of edges, adjacency list, or adjacency matrix is fine.
You may assume:
- The graph is connected (e.g. it is possible to reach any vertex given any starting vertex).
- There is at least one edge.
- An edge never connects a vertex directly to itself (ex. the edge
(1,1)will not be given as input). Note that cycles are still possible (ex.: the above graphs). - You may require that the input vertices start at any index (e.g. the first vertex can be 0, 1, -1, etc.).
- Vertex numbering is sequentially increasing from your chosen starting index (ex.:
1,2,3,4,..., or0,1,2,3,...).
Output
Your program/function should output a list of edges denoting a maximal matching set. An edge is defined by the two vertices which that edge connects. Ex. output for the left blue set (using the example input vertex ordering):
[(1,4), (2,3), (5,6)]
Note that the order of the vertices are not important; So the following output describes the same matching set:
[(4,1), (2,3), (6,5)]
Output may be to stdout, a file, function return value, etc.
Examples
Here are a few example inputs (using the adjacency list format). These examples happen to start counting vertices at 0.
Note that no example outputs are given, instead I've included a Python 3 validation code.
[0:(1), 1:(0)]
[0:(1,2), 1:(0,3,4), 2:(0,3), 3:(1,2,4,5), 4:(1,3), 5:(3,6), 6:(5)]
[0:(1,2), 1:(0,2,3,4,5), 2:(0,1), 3:(1), 4:(1), 5:(1)]
[0:(1,2), 1:(0,2,3), 2:(0,1,4), 3:(1,4,5), 4:(2,3), 5:(3)]
Validation Python 3 code
Here's a Python 3 validation code which takes in a graph and set of edges and prints out whether that set is maximally matching or not. This code works with any vertex start index.
def is_maximal_matching(graph, edges):
'''
Determines if the given set of edges is a maximal matching of graph
@param graph a graph specified in adjacency list format
@param edges a list of edges specified as vertex pairs
@return True if edges describes a maximal matching, False otherwise.
Prints out some diagnostic text for why edges is not a maximal matching
'''
graph_vtxs = {k for k,v in graph.items()}
vtxs = {k for k,v in graph.items()}
# check that all vertices are valid and not used multiple times
for e in edges:
if(e[0] in graph_vtxs):
if(e[0] in vtxs):
vtxs.remove(e[0])
else:
print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[0]))
return False
else:
print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
return False
if(e[1] in graph_vtxs):
if(e[1] in vtxs):
vtxs.remove(e[1])
else:
print('edge (%d,%d): vertex %d is used by another edge'%(e[0],e[1],e[1]))
return False
else:
print('edge (%d,%d): vertex %d is not in the graph'%(e[0],e[1],e[0]))
return False
if(e[1] not in graph[e[0]]):
print('edge (%d,%d): edge not in graph'%(e[0],e[1]))
return False
# check that any edges can't be added
for v in vtxs:
ovtxs = graph[v]
for ov in ovtxs:
if(ov in vtxs):
print('could add edge (%d,%d) to maximal set'%(v,ov))
return False
return True
Example usage:
graph = {0:[1,2], 1:[0,3,4], 2:[0,3], 3:[1,2,4,5], 4:[1,3], 5:[3,6], 6:[5]}
candidate = [(0,1),(2,3)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6),(0,1)]
is_maximal_matching(graph, candidate) // False
candidate = [(0,1),(2,3),(5,6)]
is_maximal_matching(graph, candidate) // True
Scoring
This is code golf; shortest code wins. Standard loopholes apply. You may use any built-ins desired.
