examples/org.eclipse.compare.examples.xml/tests/org/eclipse/compare/examples/xml/TestMinCostBipartiteMatching.java

/*******************************************************************************
 * Copyright (c) 2000, 2004 IBM Corporation and others.
 * All rights reserved. This program and the accompanying materials 
 * are made available under the terms of the Common Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/cpl-v10.html
 * 
 * Contributors:
 *     IBM Corporation - initial API and implementation
 *******************************************************************************/
package org.eclipse.compare.examples.xml;

import junit.framework.*;
import org.eclipse.compare.examples.xml.HungarianMethod;

public class TestMinCostBipartiteMatching extends TestCase {

	int[][] fA; //matrix that represents instance of matching problem
	int[] fC; //solution returned by HungarianMethod
	int fT; //cost of solution returned by HungarianMethod
	int[] fC2; //actual solution of matching
	int fT2; //actual cost of matching
	HungarianMethod fH;

	public TestMinCostBipartiteMatching(String name) {
		super(name);
	}
	public static void main(String[] args) {
		//junit.textui.TestRunner.run (suite());
		//TestRunner.run(suite());
	}

	protected void setUp() {
		System.out.println("TestMinCostBipartiteMatching.name()==" + getName()); //$NON-NLS-1$
		fH= new HungarianMethod();
	}

	protected void tearDown() throws Exception {
		//remove set-up
	}

	public static Test suite() {
		return new TestSuite(TestMinCostBipartiteMatching.class);
	}

	public void test0() {
		fA= new int[][] { { 0, 0, 0, 0, 0, 0, 0 }, {
				0, 7, 2, 1, 9, 4, 0 }, {
				0, 9, 6, 9, 5, 5, 0 }, {
				0, 3, 8, 3, 1, 8, 0 }, {
				0, 7, 9, 4, 2, 2, 0 }, {
				0, 8, 4, 7, 4, 8, 0 }
		};
		fC= new int[6];

		fT2= 15;
		//optimal matching: {(1,3), (2,5), (3,1), (4,4), (5,2)}
		fC2= new int[] { 0, 3, 5, 1, 4, 2 };

		fT= fH.solve(fA, fC);

		for (int J= 1; J <= 5; J++) {
			assertTrue(fC[J] == fC2[J]);
		}
		assertTrue(fT == fT2);
	}

	public void test1() {
		/* checks case where number of vertices on the two sides are not equal
		 * and dummy vertices (here, 2nd right vertice (see 3rd column)) are introduced
		 * with dummy cost
		 */
		fA= new int[][] { { 0, 0, 0, 0 }, {
				0, 2, 3, 0 }, {
				0, 0, 3, 0 }
		};
		fC= new int[3];

		fT2= 3;
		//optimal matching: {(1,2), (2,1)}
		fC2= new int[] { 0, 2, 1 };

		fT= fH.solve(fA, fC);

		for (int J= 1; J < fC.length; J++) {
			assertTrue(fC[J] == fC2[J]);
		}
		assertTrue(fT == fT2);
	}

	public void test2() {
		fA= new int[][] { { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, {
				0,
					1542,
					3533,
					2787,
					1891,
					3833,
					3558,
					1173,
					2187,
					3307,
					2836,
					3792,
					2106,
					1444,
					1924,
					0 },
					{
				0,
					1510,
					3766,
					3186,
					1815,
					4931,
					3221,
					1478,
					2107,
					3344,
					2830,
					4816,
					2359,
					1223,
					1936,
					0 },
					{
				0,
					1160,
					3901,
					2100,
					1545,
					4484,
					3326,
					1355,
					1824,
					3088,
					2563,
					3627,
					2197,
					1354,
					1689,
					0 },
					{
				0,
					1203,
					4049,
					2295,
					1586,
					3556,
					4009,
					1110,
					2282,
					3990,
					2692,
					3751,
					2399,
					1691,
					1786,
					0 },
					{
				0,
					1426,
					3163,
					2242,
					1659,
					4617,
					3240,
					1712,
					1987,
					3637,
					3037,
					4471,
					2166,
					1356,
					1878,
					0 },
					{
				0,
					1172,
					3912,
					1951,
					1469,
					4272,
					3239,
					1546,
					1924,
					3560,
					2513,
					4694,
					2127,
					1951,
					1693,
					0 },
					{
				0,
					1647,
					3889,
					2097,
					1646,
					3749,
					3656,
					970,
					1957,
					3373,
					2678,
					3711,
					1788,
					1279,
					1752,
					0 },
					{
				0,
					1219,
					3754,
					2348,
					1686,
					4297,
					3677,
					1364,
					1995,
					4133,
					2888,
					3643,
					1993,
					1481,
					1880,
					0 },
					{
				0,
					1637,
					3895,
					2165,
					1575,
					4512,
					3903,
					1499,
					1935,
					2760,
					3151,
					3162,
					2306,
					1493,
					1710,
					0 },
					{
				0,
					1391,
					3992,
					1942,
					1846,
					4450,
					3211,
					1626,
					1952,
					3495,
					2951,
					4541,
					2014,
					1639,
					1932,
					0 },
					{
				0,
					1282,
					4292,
					3048,
					2074,
					4458,
					3460,
					1300,
					1952,
					3495,
					2951,
					4541,
					2014,
					1639,
					1932,
					0 },
					{
				0,
					1598,
					3721,
					2457,
					1880,
					4073,
					3164,
					1829,
					1952,
					3495,
					2951,
					4541,
					2014,
					1639,
					1932,
					0 },
					{
				0,
					1384,
					1742,
					2447,
					1858,
					4367,
					3189,
					1774,
					1699,
					3040,
					2499,
					3911,
					2203,
					1433,
					1676,
					0 },
					{
				0,
					1474,
					3815,
					2214,
					1997,
					4515,
					3202,
					1352,
					1942,
					3274,
					2502,
					5138,
					2395,
					1767,
					2136,
					0 }
		};

		fT2= 29858;
		//optimal matching: {(8,1) (13,2) (10,3) (6,4) (4,5) (12,6) (1,7) (11,8) (3,9) (14,10) (9,11) (7,12) (2,13) (5,14)}
		fC2= new int[] { 0, 8, 13, 10, 6, 4, 12, 1, 11, 3, 14, 9, 7, 2, 5 };

		fC= new int[15];

		fT= fH.solve(fA, fC);

		//		for (int J=1; J<fC.length; J++) {
		//		    System.out.print("("+fC[J]+","+J+") ");
		//		}
		//		System.out.println();
		//		System.out.println("Cost: "+fT);

		for (int J= 1; J < fC.length; J++) {
			assertTrue(fC[J] == fC2[J]);
		}
		assertTrue(fT == fT2);
	}
}