Discussion 11: Using DFS for Bipartite Matching

Solutions

Download Solution Code download

Exercise 1: Bipartite Graphs

(a)

Draw the graph of this scenario:

Pilots: Alpha, Bravo, Charlie, Delta, Echo
Planes: P1, P2, P3, P4, P5
Alpha can fly P1 & P2
Bravo can fly P1 & P3
Charlie can fly P2 & P4
Delta can fly P3 & P4
Echo can fly P4 & P5

Exercise 2: Finding Matchings

Using the example bipartite graph from Exercise 1, find these matchings:

(a)

Find a matching contains the edge (Charlie, P4).

\(\{\) (Charlie, P4) \(\}\) is such a matching. Adding other edges with distinct endpoints results in other such matchings.

(b)

Find a matching with size 3 (i.e., that contains 3 edges) that contains the edge (Echo, P4).

\(\{\) (Echo, P4), (Alpha, P1), (Bravo,P3) \(\}\) is one such matching.

(c)

Find a matching that has the largest possible size (i.e., a maximum matching). What is the maximum number of flights able to run (size of the maximum matching)? Which pilots would fly which planes? (If you have extra time, try to find a second maximum matching)

There are two maximum matchings that allow for 5 flights, utilizing all of the pilots and all of the planes:

\(\{\) (Alpha, P1), (Bravo, P3), (Charlie, P2), (Delta, P4), (Echo, P5) \(\}\)

\(\{\) (Alpha, P2), (Bravo, P1), (Charlie, P4), (Delta, P3), (Echo, P5) \(\}\)

Exercise 3: Augmenting Paths

Let's apply it to our graph from Exercise 1. Let’s say our matching edge set already contains: {(Alpha, P2), (Bravo, P3), (Delta, P4), (Echo, P5)}

(a)

Which pilot(s) are currently unmatched?

Charlie is currently unmatched.

(b)

Which plane(s) are currently unmatched?

P1 is currently unmatched.

(c)

Find an augmenting path for this matching.

Charlie \(\to\) P2 \(\to\) Alpha \(\to\) P1

or

Charlie \(\to\) P4 \(\to\) Delta \(\to\) P3 \(\to\) Bravo \(\to\) P1

(d)

Now, update the matching by taking the augmenting path (reversing the edges from matched to unmatched and vice versa). What is your new matching? How does this affect the number of pairings?

The resulting matching is:

\(\{\) (Alpha, P1), (Bravo, P3), (Charlie, P2), (Delta, P4), (Echo, P5) \(\}\)

or

\(\{\) (Alpha, P2), (Bravo, P1), (Charlie, P4), (Delta, P3), (Echo, P5) \(\}\)

depending on which augmenting path was chosen in part (c). In either case, the size of the matching increased by 1 from 4 to 5.

(e)

Implement the augment() method, which takes in the augmenting path and the matching and returns the bigger matching gained from taking the augmenting path.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/** Updates the given `matching` using the given `augmentingPath`. */
private static void augment(Matching matching, Path augmentingPath) {
  for (int i = 0; i < augmentingPath.size(); i++) {
    Edge edge = augmentingPath.get(i);
    if (i % 2 == 0) {
      assert !matching.contains(edge);
      matching.add(edge);
    } else {
      assert matching.contains(edge.reverse());
      matching.remove(edge.reverse());
    } 
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/** Updates the given `matching` using the given `augmentingPath`. */
private static void augment(Matching matching, Path augmentingPath) {
  for (int i = 0; i < augmentingPath.size(); i++) {
    Edge edge = augmentingPath.get(i);
    if (i % 2 == 0) {
      assert !matching.contains(edge);
      matching.add(edge);
    } else {
      assert matching.contains(edge.reverse());
      matching.remove(edge.reverse());
    } 
  }
}

Exercise 4: Find Augmenting Paths with DFS

Next, we'll write code to locate a maximum matching in a bipartite graph by repeatedly finding augmenting paths and using the `augment()` method. We can use a DFS traversal to locate augmenting paths

(a)

dfsRecursive()

Implement dfsRecursive(), a helper method for findAugmentingPath() that leverages DFS (for more info on DFS, refer to Lecture 22) to locate an augmenting path starting at a particular vertex. We encourage you to make use of the provided scaffolding for this method.

 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


/**
 * Returns a path from the left vertex `current` to a right vertex that is not present in the
 * given `matching`, traversing visiting only un`discovered` vertices (besides `current`).
 * Returns `null` if no such path exists.
 */
private static Path dfsRecursive(Vertex current, Matching matching, HashSet<Vertex> discovered) {
  for (Vertex neighbor : current.neighbors()) {
    if (discovered.contains(neighbor)) {
      continue; // already visited this neighbor earlier in the traversal
    }
    Path path;
    Vertex nextLeftVertex = matchOfRightVertex(neighbor, matching);
    if (nextLeftVertex == null) {
      // we've located an unmatched right vertex, ending the augmenting path
      path = new Path();
      path.add(new Edge(current, neighbor));
      return path;
    }
    // we've located a matched right vertex, so continue the search from there
    discovered.add(neighbor);
    path = dfsRecursive(nextLeftVertex, matching, discovered);
    if (path != null) { // found a path from `nextLeftVertex`
      path.addFirst(new Edge(neighbor, nextLeftVertex));
      path.addFirst(new Edge(current, neighbor));
      return path;
    }
  }
  return null;
}

 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


/**
 * Returns a path from the left vertex `current` to a right vertex that is not present in the
 * given `matching`, traversing visiting only un`discovered` vertices (besides `current`).
 * Returns `null` if no such path exists.
 */
private static Path dfsRecursive(Vertex current, Matching matching, HashSet<Vertex> discovered) {
  for (Vertex neighbor : current.neighbors()) {
    if (discovered.contains(neighbor)) {
      continue; // already visited this neighbor earlier in the traversal
    }
    Path path;
    Vertex nextLeftVertex = matchOfRightVertex(neighbor, matching);
    if (nextLeftVertex == null) {
      // we've located an unmatched right vertex, ending the augmenting path
      path = new Path();
      path.add(new Edge(current, neighbor));
      return path;
    }
    // we've located a matched right vertex, so continue the search from there
    discovered.add(neighbor);
    path = dfsRecursive(nextLeftVertex, matching, discovered);
    if (path != null) { // found a path from `nextLeftVertex`
      path.addFirst(new Edge(neighbor, nextLeftVertex));
      path.addFirst(new Edge(current, neighbor));
      return path;
    }
  }
  return null;
}

(b)

maxMatching()

Implement maxMatching(). This method contains the main loop that iteratively locates augmenting paths and calls the augment helper method described above.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


/** Returns a maximum cardinality matching in the given bipartite `graph`. */
public static Matching maxMatching(BipartiteGraph graph) {
  Matching matching = new Matching();
  for (Vertex v : graph.leftVertices()) {
    Path augmentingPath = findAugmentingPath(graph, v, matching);
    if (augmentingPath != null) {
      augment(matching, augmentingPath);
    }
  }
  return matching;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


/** Returns a maximum cardinality matching in the given bipartite `graph`. */
public static Matching maxMatching(BipartiteGraph graph) {
  Matching matching = new Matching();
  for (Vertex v : graph.leftVertices()) {
    Path augmentingPath = findAugmentingPath(graph, v, matching);
    if (augmentingPath != null) {
      augment(matching, augmentingPath);
    }
  }
  return matching;
}