This is a java program to implement Edmond’s Algorithm for maximum cardinality matching. In graph theory, a branch of mathematics, Edmonds’ algorithm or Chu–Liu/Edmonds’ algorithm is an algorithm for finding a maximum or minimum optimum branchings. This is similar to the minimum spanning tree problem which concerns undirected graphs. However, when nodes are connected by weighted edges that are directed, a minimum spanning tree algorithm cannot be used.
Here is the source code of the Java Program to Implement the Edmond’s Algorithm for Maximum Cardinality Matching. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.
package com.maixuanviet.graph; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; public class EdmondsMaximumCardinalityMatching { static int lca(int[] match, int[] base, int[] p, int a, int b) { boolean[] used = new boolean[match.length]; while (true) { a = base[a]; used[a] = true; if (match[a] == -1) break; a = p[match[a]]; } while (true) { b = base[b]; if (used[b]) return b; b = p[match[b]]; } } static void markPath(int[] match, int[] base, boolean[] blossom, int[] p, int v, int b, int children) { for (; base[v] != b; v = p[match[v]]) { blossom[base[v]] = blossom[base[match[v]]] = true; p[v] = children; children = match[v]; } } static int findPath(List<Integer>[] graph, int[] match, int[] p, int root) { int n = graph.length; boolean[] used = new boolean[n]; Arrays.fill(p, -1); int[] base = new int[n]; for (int i = 0; i < n; ++i) base[i] = i; used[root] = true; int qh = 0; int qt = 0; int[] q = new int[n]; q[qt++] = root; while (qh < qt) { int v = q[qh++]; for (int to : graph[v]) { if (base[v] == base[to] || match[v] == to) continue; if (to == root || match[to] != -1 && p[match[to]] != -1) { int curbase = lca(match, base, p, v, to); boolean[] blossom = new boolean[n]; markPath(match, base, blossom, p, v, curbase, to); markPath(match, base, blossom, p, to, curbase, v); for (int i = 0; i < n; ++i) if (blossom[base[i]]) { base[i] = curbase; if (!used[i]) { used[i] = true; q[qt++] = i; } } } else if (p[to] == -1) { p[to] = v; if (match[to] == -1) return to; to = match[to]; used[to] = true; q[qt++] = to; } } } return -1; } public static int maxMatching(List<Integer>[] graph) { int n = graph.length; int[] match = new int[n]; Arrays.fill(match, -1); int[] p = new int[n]; for (int i = 0; i < n; ++i) { if (match[i] == -1) { int v = findPath(graph, match, p, i); while (v != -1) { int pv = p[v]; int ppv = match[pv]; match[v] = pv; match[pv] = v; v = ppv; } } } int matches = 0; for (int i = 0; i < n; ++i) if (match[i] != -1) ++matches; return matches / 2; } @SuppressWarnings("unchecked") public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.println("Enter the number of vertices: "); int v = sc.nextInt(); System.out.println("Enter the number of edges: "); int e = sc.nextInt(); List<Integer>[] g = new List[v]; for (int i = 0; i < v; i++) { g[i] = new ArrayList<Integer>(); } System.out.println("Enter all the edges: <from> <to>"); for (int i = 0; i < e; i++) { g[sc.nextInt()].add(sc.nextInt()); } System.out.println("Maximum matching for the given graph is: " + maxMatching(g)); sc.close(); } }
Output:
$ javac EdmondsMaximumCardinalityMatching.java $ java EdmondsMaximumCardinalityMatching Enter the number of vertices: 6 Enter the number of edges: 7 Enter all the edges: <from> <to> 0 1 1 2 1 3 3 4 4 5 5 3 5 2 Maximum matching for the given graph is: 3
Related posts:
Send email with SMTPS (eg. Google GMail)
Java Program to Implement Dijkstra’s Algorithm using Queue
Java Program to Implement Attribute API
Java Program to Generate All Subsets of a Given Set in the Gray Code Order
Java – File to Reader
Spring NoSuchBeanDefinitionException
Collect a Java Stream to an Immutable Collection
Convert Hex to ASCII in Java
Extract network card address
Java Program to Implement Treap
RestTemplate Post Request with JSON
Java Program to Perform Addition Operation Using Bitwise Operators
Spring Data MongoDB Transactions
Spring Data MongoDB – Indexes, Annotations and Converters
Uploading MultipartFile with Spring RestTemplate
JPA/Hibernate Persistence Context
A Guide to the finalize Method in Java
Java Program to Check if a Given Set of Three Points Lie on a Single Line or Not
Java Program to Implement Bucket Sort
Java Program to Implement Insertion Sort
An Intro to Spring Cloud Contract
Java Program to Encode a Message Using Playfair Cipher
Java Program to Solve TSP Using Minimum Spanning Trees
Quick Guide to Spring MVC with Velocity
Spring Boot - Servlet Filter
Java Program to implement Bi Directional Map
Spring Cloud AWS – Messaging Support
New Features in Java 11
Java Program to Perform Right Rotation on a Binary Search Tree
Intersection of Two Lists in Java
Java Program for Douglas-Peucker Algorithm Implementation
Limiting Query Results with JPA and Spring Data JPA