/*
 * Created on Aug 22, 2003
 *
 */
package edu.uci.ics.jung.algorithms.shortestpath;

import junit.framework.Assert;
import junit.framework.Test;
import junit.framework.TestCase;
import junit.framework.TestSuite;

import com.google.common.base.Supplier;
import com.google.common.collect.BiMap;

import edu.uci.ics.jung.algorithms.util.Indexer;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.DirectedSparseMultigraph;
import edu.uci.ics.jung.graph.UndirectedGraph;
import edu.uci.ics.jung.graph.UndirectedSparseMultigraph;

/**
 * @author Scott White
 */
public class TestUnweightedShortestPath extends TestCase
{
    private Supplier vertexFactory =
    	new Supplier() {
    	int count = 0;
    	public String get() {
    		return "V"+count++;
    	}};
    	
     private Supplier edgeFactory =
        	new Supplier() {
        	int count = 0;
        	public Integer get() {
        		return count++;
        	}};
    BiMap id;

    @Override
    protected void setUp() {
    }
	public static Test suite()
	{
		return new TestSuite(TestUnweightedShortestPath.class);
	}
	
	public void testUndirected() {
		UndirectedGraph ug = 
			new UndirectedSparseMultigraph();
		for(int i=0; i<5; i++) {
			ug.addVertex(vertexFactory.get());
		}
		id = Indexer.create(ug.getVertices());

//		GraphUtils.addVertices(ug,5);
//		Indexer id = Indexer.getIndexer(ug);
		ug.addEdge(edgeFactory.get(), id.inverse().get(0), id.inverse().get(1));
		ug.addEdge(edgeFactory.get(), id.inverse().get(1), id.inverse().get(2));
		ug.addEdge(edgeFactory.get(), id.inverse().get(2), id.inverse().get(3));
		ug.addEdge(edgeFactory.get(), id.inverse().get(0), id.inverse().get(4));
		ug.addEdge(edgeFactory.get(), id.inverse().get(4), id.inverse().get(3));
		
		UnweightedShortestPath usp = 
			new UnweightedShortestPath(ug);
		Assert.assertEquals(usp.getDistance(id.inverse().get(0),id.inverse().get(3)).intValue(),2);
		Assert.assertEquals((usp.getDistanceMap(id.inverse().get(0)).get(id.inverse().get(3))).intValue(),2);
		Assert.assertNull(usp.getIncomingEdgeMap(id.inverse().get(0)).get(id.inverse().get(0)));
		Assert.assertNotNull(usp.getIncomingEdgeMap(id.inverse().get(0)).get(id.inverse().get(3)));
	}
	
	public void testDirected() {
			DirectedGraph dg = 
				new DirectedSparseMultigraph();
			for(int i=0; i<5; i++) {
				dg.addVertex(vertexFactory.get());
			}
			id = Indexer.create(dg.getVertices());
			dg.addEdge(edgeFactory.get(), id.inverse().get(0), id.inverse().get(1));
			dg.addEdge(edgeFactory.get(), id.inverse().get(1), id.inverse().get(2));
			dg.addEdge(edgeFactory.get(), id.inverse().get(2), id.inverse().get(3));
			dg.addEdge(edgeFactory.get(), id.inverse().get(0), id.inverse().get(4));
			dg.addEdge(edgeFactory.get(), id.inverse().get(4), id.inverse().get(3));
			dg.addEdge(edgeFactory.get(), id.inverse().get(3), id.inverse().get(0));
		
			UnweightedShortestPath usp = 
				new UnweightedShortestPath(dg);
			Assert.assertEquals(usp.getDistance(id.inverse().get(0),id.inverse().get(3)).intValue(),2);
			Assert.assertEquals((usp.getDistanceMap(id.inverse().get(0)).get(id.inverse().get(3))).intValue(),2);
			Assert.assertNull(usp.getIncomingEdgeMap(id.inverse().get(0)).get(id.inverse().get(0)));
			Assert.assertNotNull(usp.getIncomingEdgeMap(id.inverse().get(0)).get(id.inverse().get(3)));

		}
}

 

Ads help maintain this website.