14
\$\begingroup\$

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.

enter image description here

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.enter image description here

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:

  1. The graph is connected (e.g. it is possible to reach any vertex given any starting vertex).
  2. There is at least one edge.
  3. 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).
  4. You may require that the input vertices start at any index (e.g. the first vertex can be 0, 1, -1, etc.).
  5. Vertex numbering is sequentially increasing from your chosen starting index (ex.: 1,2,3,4,..., or 0,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.

\$\endgroup\$
9
\$\begingroup\$

CJam (16 chars)

{M\{_2$&!*+}/2/}

Online demo

This is a greedy approach which accumulates edges which don't have any vertex in common with the previously accumulated edges.

\$\endgroup\$
  • \$\begingroup\$ I'm pretty sure this fails on the third example, giving [[0 1] [3 4]] instead of the maximal set [[0 2] [1 4] [3 5]]. (I'm ignoring the (1, 1) edge that seem to be in there by mistake) \$\endgroup\$ – ETHproductions Apr 26 '17 at 13:05
  • \$\begingroup\$ @ETHproductions, you're confusing maximal with maximum. \$\endgroup\$ – Peter Taylor Apr 26 '17 at 13:33
  • 3
    \$\begingroup\$ Dangit, sorry about that... I'll just leave my comment to help any others who are confused, if you don't mind, since this seems to be a recurring issue :-P \$\endgroup\$ – ETHproductions Apr 26 '17 at 14:09
7
\$\begingroup\$

Pyth, 8 bytes

ef{IsTty
       y  power set (gerenate all set of edges)
      t   remove the first one (the first one is
          empty and will cause problems)
 f        filter for sets T satisfying:
     T        T
    s         flatten
  {I          is invariant under deduplicate, i.e. contains no
              duplicating vertices, as the elements represent vertices
e         pick the last one (the power set is ordered from
          smallest to largest)

Try it online!

Specs

  • Input: [(0,1), (0,2), (1,3), (1,4), (2,3), (3,4), (3,5), (5,6)]
  • Output: [(1, 4), (2, 3), (5, 6)]
\$\endgroup\$
6
\$\begingroup\$

Wolfram Language, 25 22 bytes

Saved 3 bytes thanks to @MartinEnder

FindIndependentEdgeSet

This takes input as a Graph object (defined as Graph[{1<->2,2<->3,1<-3>}] etc.)

\$\endgroup\$
  • \$\begingroup\$ You don't need the @#&. \$\endgroup\$ – Martin Ender Apr 26 '17 at 5:45
  • \$\begingroup\$ @MartinEnder Thanks. \$\endgroup\$ – Scott Milner Apr 26 '17 at 13:36
  • \$\begingroup\$ Pfft. import solve_problem; run(). Now someone just needs to write a plugin for Wolfram that takes in a codegolf challenge URL and outputs the desired output. Call it Golf. \$\endgroup\$ – Draco18s Apr 26 '17 at 18:17
5
\$\begingroup\$

Brachylog, 5 bytes

 ⊇.c≠∧

?⊇.cL≠   implicit ? at the beginning;
         ∧ breaks implicit . at the end;
         temporary variable inserted.
?⊇.      input is a superset of output
  .cL    output concatenated is L
    L≠   L contains distinct elements

Try it online!

This is guaranteed to be maximal, since Brachylog searches from the largest subset.

\$\endgroup\$
  • \$\begingroup\$ I think that your explanation has different code than your actual code. \$\endgroup\$ – Erik the Outgolfer Apr 26 '17 at 12:15
  • \$\begingroup\$ @EriktheOutgolfer That is because I inserted characters that are implicit in my explanation. The original code is in the first line. Brachylog is quite terse in this aspect. \$\endgroup\$ – Leaky Nun Apr 26 '17 at 12:16
  • \$\begingroup\$ I don't mean that, but the first code ends in ≠∧, while the second code ends in L≠. \$\endgroup\$ – Erik the Outgolfer Apr 26 '17 at 12:17
  • \$\begingroup\$ Without , there would be an implicit . at the end. All means here is that the . is not to be inserted at the end. \$\endgroup\$ – Leaky Nun Apr 26 '17 at 12:18
  • \$\begingroup\$ The L is a temporary variable that is used nowhere, hence its ability to be omitted. \$\endgroup\$ – Leaky Nun Apr 26 '17 at 12:18
0
\$\begingroup\$

JavaScript (ES6), 67 bytes

let f =
a=>a.map(b=>r.some(c=>c.some(d=>~b.indexOf(d)))||r.push(b),r=[])&&r

let g = a => console.log("[%s]", f(a).map(x => "[" + x + "]").join(", "))
g([[0,1]])
g([[0,1], [0,2], [1,3], [1,4], [2,3], [3,4], [3,5], [5,6]])
g([[0,1], [0,2], [1,2], [1,3], [1,4], [1,5]])
g([[0,1], [0,2], [1,2], [1,3], [2,4], [3,4], [3,5]])

Uses the greedy approach for maximal golfiness.

\$\endgroup\$
0
\$\begingroup\$

JavaScript (ES6), 68 66 bytes

f=a=>a[0]?[a[0],...f(a.filter(b=>!a[0].some(c=>~b.indexOf(c))))]:a
f=([b,...a])=>b?[b,...f(a.filter(c=>!c.some(c=>~b.indexOf(c))))]:a

I thought I'd give the recursive approach a go, and by stealing @ETHproduction's set intersection trick I managed to undercut his answer!

I was not the first to misread the original question, and I was about to submit the following recursive function which finds a maximal set of matching edges, rather than a set of maximal matching edges. Subtle difference, I know!

f=a=>a.map(([b,c])=>[[b,c],...f(a.filter(([d,e])=>b-d&&b-e&&c-d&&c-e))]).sort((d,e)=>e.length-d.length)[0]||[]

Simple recursive approach. For each input element, deletes all conflicting edges from the set and finds the maximal set of matching edges of the remaining subset, then finds the maximal result over each input element. Somewhat inefficient for large sets (9-byte speed-up possible).

\$\endgroup\$
0
\$\begingroup\$

Jelly, 12 11 bytes

FQ⁼F
ŒPÇÐfṪ

Try it online!

Sample input: [0,1],[0,2],[1,3],[1,4],[2,3],[3,4],[3,5],[5,6]

Sample output: [[1, 4], [2, 3], [5, 6]]

How it works

FQ⁼F    - Helper function, returns 1 if a set of edges is non-matching
F       - Flatten input
 Q      - Remove repeated elements
  ⁼     - Return boolean value. Is this equal to
   F    - The flattened input list

ŒPÇÐfṪ - Main link.
ŒP     - Power set of input list of edges
   Ðf  - Remove all elements which return 1 if
  Ç    - (Helper function) it is a non-matching set
     Ṫ - Get the last element in the resultant list (the longest). 
           Always maximal because it is the longest, so any
           edge added would not be in this list (not matching)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.