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

import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;

import junit.framework.TestCase;

import com.google.common.base.Function;
import com.google.common.base.Functions;
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.Graph;
import edu.uci.ics.jung.graph.UndirectedGraph;
import edu.uci.ics.jung.graph.UndirectedSparseMultigraph;


/**
 * @author Joshua O'Madadhain
 */
public class TestShortestPath extends TestCase
{
    private DirectedGraph dg;  
    private UndirectedGraph ug;
    // graph based on Weiss, _Data Structures and Algorithm Analysis_,
    // 1992, p. 292
    private static int[][] edges = 
        {{1,2,2}, {1,4,1}, // 0, 1
            {2,4,3}, {2,5,10}, // 2, 3
            {3,1,4}, {3,6,5},  // 4, 5
            {4,3,2}, {4,5,2}, {4,6,8}, {4,7,4}, // 6,7,8,9
            {5,7,6}, // 10
            {7,6,1}, // 11
            {8,9,4}, // (12) these three edges define a second connected component
            {9,10,1}, // 13
            {10,8,2}}; // 14

    private static Integer[][] ug_incomingEdges = 
    {
        {null, new Integer(0), new Integer(6), new Integer(1), new Integer(7), new Integer(11), new Integer(9), null, null, null},
        {new Integer(0), null, new Integer(6), new Integer(2), new Integer(7), new Integer(11), new Integer(9), null, null, null},
        {new Integer(1), new Integer(2), null, new Integer(6), new Integer(7), new Integer(5), new Integer(9), null, null, null},
        {new Integer(1), new Integer(2), new Integer(6), null, new Integer(7), new Integer(11), new Integer(9), null, null, null},
        {new Integer(1), new Integer(2), new Integer(6), new Integer(7), null, new Integer(11), new Integer(10), null, null, null},
        {new Integer(1), new Integer(2), new Integer(5), new Integer(9), new Integer(10), null, new Integer(11), null, null, null},
        {new Integer(1), new Integer(2), new Integer(5), new Integer(9), new Integer(10), new Integer(11), null, null, null, null},
        {null, null, null, null, null, null, null, null, new Integer(13), new Integer(14)},
        {null, null, null, null, null, null, null, new Integer(14), null, new Integer(13)},
        {null, null, null, null, null, null, null, new Integer(14), new Integer(13), null},
    };      
    
    private static Integer[][] dg_incomingEdges = 
        {
            {null, new Integer(0), new Integer(6), new Integer(1), new Integer(7), new Integer(11), new Integer(9), null, null, null},
            {new Integer(4), null, new Integer(6), new Integer(2), new Integer(7), new Integer(11), new Integer(9), null, null, null},
            {new Integer(4), new Integer(0), null, new Integer(1), new Integer(7), new Integer(5), new Integer(9), null, null, null},
            {new Integer(4), new Integer(0), new Integer(6), null, new Integer(7), new Integer(11), new Integer(9), null, null, null},
            {null, null, null, null, null, new Integer(11), new Integer(10), null, null, null},
            {null, null, null, null, null, null, null, null, null, null},
            {null, null, null, null, null, new Integer(11), null, null, null, null},
            {null, null, null, null, null, null, null, null, new Integer(12), new Integer(13)},
            {null, null, null, null, null, null, null, new Integer(14), null, new Integer(13)},
            {null, null, null, null, null, null, null, new Integer(14), new Integer(12), null}
    };      
    
    private static double[][] dg_distances = 
    {
        {0, 2, 3, 1, 3, 6, 5, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {9, 0, 5, 3, 5, 8, 7, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {4, 6, 0, 5, 7, 5, 9, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {6, 8, 2, 0, 2, 5, 4, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 0, 7, 6, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 0, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 1, 0, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 0, 4, 5},
        {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 3, 0, 1},
        {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 2, 6, 0}
    };

    private static double[][] ug_distances = 
    {
        {0, 2, 3, 1, 3, 6, 5, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {2, 0, 5, 3, 5, 8, 7, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {3, 5, 0, 2, 4, 5, 6, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {1, 3, 2, 0, 2, 5, 4, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {3, 5, 4, 2, 0, 7, 6, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {6, 8, 5, 5, 7, 0, 1, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {5, 7, 6, 4, 6, 1, 0, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY},
        {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 0, 3, 2},
        {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 3, 0, 1},
        {Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY, 2, 1, 0}
    };
    

    private static Integer[][] shortestPaths1 = 
    {
    	null,
        {new Integer(0)},
        {new Integer(1), new Integer(6)},
        {new Integer(1)},
        {new Integer(1), new Integer(7)},
        {new Integer(1), new Integer(9), new Integer(11)},
        {new Integer(1), new Integer(9)},
        null,
        null,
        null
    };
    
    private Map,Integer[]> edgeArrays;
    
    private Map edgeWeights;
    
    private Function nev;
    
    private Supplier vertexFactoryDG =
    	new Supplier() {
    	int count = 0;
    	public String get() {
    		return "V"+count++;
    	}};
    	private Supplier vertexFactoryUG =
    		new Supplier() {
    		int count = 0;
    		public String get() {
    			return "U"+count++;
    		}};
    		
    BiMap did;
    BiMap uid;

    @Override
    protected void setUp() {
    	edgeWeights = new HashMap();
        nev = Functions.forMap(edgeWeights);
		dg = new DirectedSparseMultigraph();
		for(int i=0; icreate(dg.getVertices(), 1);
        Integer[] dg_array = new Integer[edges.length];
		addEdges(dg, did, dg_array);
        
        ug = new UndirectedSparseMultigraph();
		for(int i=0; icreate(ug.getVertices(),1);
//        GraphUtils.addVertices(ug, ug_distances.length);
//        Indexer.newIndexer(ug, 1);
        Integer[] ug_array = new Integer[edges.length];
        addEdges(ug, uid, ug_array);
        
        edgeArrays = new HashMap,Integer[]>();
        edgeArrays.put(dg, dg_array);
        edgeArrays.put(ug, ug_array);
    }
    
    @Override
    protected void tearDown() throws Exception {
    }

    public void exceptionTest(Graph g, BiMap indexer, int index)
    {
        DijkstraShortestPath dsp = 
        	new DijkstraShortestPath(g, nev);
//        Indexer id = Indexer.getIndexer(g);
        String start = indexer.inverse().get(index);
        Integer e = null;

        String v = "NOT IN GRAPH";
        
        try
        {
            dsp.getDistance(start, v);
            fail("getDistance(): illegal destination vertex");
        }
        catch (IllegalArgumentException iae) {}
        try
        {
            dsp.getDistance(v, start);
            fail("getDistance(): illegal source vertex");
        }
        catch (IllegalArgumentException iae) {}
        try
        {
            dsp.getDistanceMap(v, 1);
            fail("getDistanceMap(): illegal source vertex");
        }
        catch (IllegalArgumentException iae) {}
        try
        {
            dsp.getDistanceMap(start, 0);
            fail("getDistanceMap(): too few vertices requested");
        }
        catch (IllegalArgumentException iae) {}
        try
        {
            dsp.getDistanceMap(start, g.getVertexCount()+1);
            fail("getDistanceMap(): too many vertices requested");
        }
        catch (IllegalArgumentException iae) {}

        try
        {
            dsp.getIncomingEdge(start, v);
            fail("getIncomingEdge(): illegal destination vertex");
        }
        catch (IllegalArgumentException iae) {}
        try
        {
            dsp.getIncomingEdge(v, start);
            fail("getIncomingEdge(): illegal source vertex");
        }
        catch (IllegalArgumentException iae) {}
        try
        {
            dsp.getIncomingEdgeMap(v, 1);
            fail("getIncomingEdgeMap(): illegal source vertex");
        }
        catch (IllegalArgumentException iae) {}
        try
        {
            dsp.getIncomingEdgeMap(start, 0);
            fail("getIncomingEdgeMap(): too few vertices requested");
        }
        catch (IllegalArgumentException iae) {}
        try
        {
            dsp.getDistanceMap(start, g.getVertexCount()+1);
            fail("getIncomingEdgeMap(): too many vertices requested");
        }
        catch (IllegalArgumentException iae) {}

        try
        {
            // test negative edge weight exception
            String v1 = indexer.inverse().get(1);
            String v2 = indexer.inverse().get(7);
            e = g.getEdgeCount()+1;
         	g.addEdge(e, v1, v2);
         	edgeWeights.put(e, -2);
//            e.addUserDatum("weight", new Double(-2), UserData.REMOVE);
            dsp.reset();
            dsp.getDistanceMap(start);
//            for (Iterator it = g.getEdges().iterator(); it.hasNext(); )
//            {
//                Edge edge = (Edge)it.next();
//                double weight = ((Number)edge.getUserDatum("weight")).doubleValue();
//                Pair p = edge.getEndpoints();
//                int i = id.getIndex((Vertex)p.getFirst());
//                int j = id.getIndex((Vertex)p.getSecond());
//                System.out.print("(" + i + "," + j + "): " + weight);
//                if (weight < 0)
//                    System.out.print(" *******");
//                System.out.println();
//            }
            fail("DijkstraShortestPath should not accept negative edge weights");
        }
        catch (IllegalArgumentException iae) 
        {
            g.removeEdge(e);
        }
    }
    
    public void testDijkstra()
    {
        setUp();
        exceptionTest(dg, did, 1);
        
        setUp();
        exceptionTest(ug, uid, 1);
        
        setUp();
        getPathTest(dg, did, 1);
        
        setUp();
        getPathTest(ug, uid, 1);
                
        for (int i = 1; i <= dg_distances.length; i++)
        {
            setUp();
            weightedTest(dg, did, i, true);

            setUp();
            weightedTest(dg, did, i, false);
        }
        
        for (int i = 1; i <= ug_distances.length; i++)
        {
            setUp();
            weightedTest(ug, uid, i, true);
            
            setUp();
            weightedTest(ug, uid, i, false);
        }
        
    }

    private void getPathTest(Graph g, BiMap indexer, int index)
    {
        DijkstraShortestPath dsp = 
        	new DijkstraShortestPath(g, nev);
//        Indexer id = Indexer.getIndexer(g);
        String start = indexer.inverse().get(index);
        Integer[] edge_array = edgeArrays.get(g);
        Integer[] incomingEdges1 = null;
        if (g instanceof DirectedGraph)
            incomingEdges1 = dg_incomingEdges[index-1];
        if (g instanceof UndirectedGraph)
            incomingEdges1 = ug_incomingEdges[index-1];
        assertEquals(incomingEdges1.length, g.getVertexCount());
        
         // test getShortestPath(start, v)
        dsp.reset();
        for (int i = 1; i <= incomingEdges1.length; i++)
        {
          List shortestPath = dsp.getPath(start, indexer.inverse().get(i));
            Integer[] indices = shortestPaths1[i-1];
            for (ListIterator iter = shortestPath.listIterator(); iter.hasNext(); )
            {
                int j = iter.nextIndex();
                Integer e = iter.next();
                if (e != null)
                    assertEquals(edge_array[indices[j].intValue()], e);
                else
                    assertNull(indices[j]);
            }
        }
    }
    
    private void weightedTest(Graph g, BiMap indexer, int index, boolean cached) {
//        Indexer id = Indexer.getIndexer(g);
        String start = indexer.inverse().get(index);
        double[] distances1 = null;
        Integer[] incomingEdges1 = null;
        if (g instanceof DirectedGraph)
        {
            distances1 = dg_distances[index-1];
            incomingEdges1 = dg_incomingEdges[index-1];
        }
        if (g instanceof UndirectedGraph)
        {    
            distances1 = ug_distances[index-1];
            incomingEdges1 = ug_incomingEdges[index-1];
        }
        assertEquals(distances1.length, g.getVertexCount());
        assertEquals(incomingEdges1.length, g.getVertexCount());
        DijkstraShortestPath dsp = 
        	new DijkstraShortestPath(g, nev, cached);
        Integer[] edge_array = edgeArrays.get(g);
        
        // test getDistance(start, v)
        for (int i = 1; i <= distances1.length; i++) {
            String v = indexer.inverse().get(i);
            Number n = dsp.getDistance(start, v);
            double d = distances1[i-1];
            double dist;
            if (n == null)
                dist = Double.POSITIVE_INFINITY;
            else
                dist = n.doubleValue();
            
            assertEquals(d, dist, .001);
        }

        // test getIncomingEdge(start, v)
        dsp.reset();
        for (int i = 1; i <= incomingEdges1.length; i++)
        {
            String v = indexer.inverse().get(i);
            Integer e = dsp.getIncomingEdge(start, v);
            if (e != null)
                assertEquals(edge_array[incomingEdges1[i-1].intValue()], e);
            else
                assertNull(incomingEdges1[i-1]);
        }
        
        // test getDistanceMap(v)
        dsp.reset();
        Map distances = dsp.getDistanceMap(start);
        assertTrue(distances.size() <= g.getVertexCount());
        double d_prev = 0; // smallest possible distance
        Set reachable = new HashSet();
        for (Iterator d_iter = distances.keySet().iterator(); d_iter.hasNext(); )
        {
            String cur = d_iter.next();
            double d_cur = ((Double)distances.get(cur)).doubleValue();
            assertTrue(d_cur >= d_prev);

            d_prev = d_cur;
            int i = indexer.get(cur);
            assertEquals(distances1[i-1], d_cur, .001);
            reachable.add(cur);
        }
        // make sure that non-reachable vertices have no entries
        for (Iterator v_iter = g.getVertices().iterator(); v_iter.hasNext(); )
        {
            String v = v_iter.next();
            assertEquals(reachable.contains(v), distances.keySet().contains(v));
        }
        
        // test getIncomingEdgeMap(v)
        dsp.reset();
        Map incomingEdgeMap = dsp.getIncomingEdgeMap(start);
        assertTrue(incomingEdgeMap.size() <= g.getVertexCount());
        for (Iterator e_iter = incomingEdgeMap.keySet().iterator(); e_iter.hasNext(); )
        {
            String v = e_iter.next();
            Integer e = incomingEdgeMap.get(v);
            int i = indexer.get(v);
//            if (e != null)
//            {    
//                Pair endpoints = e.getEndpoints();
//                int j = id.getIndex((Vertex)endpoints.getFirst());
//                int k = id.getIndex((Vertex)endpoints.getSecond());
//                System.out.print(i + ": (" + j + "," + k + ");  ");
//            }
//            else
//                System.out.print(i + ": null;  ");
            if (e != null)
                assertEquals(edge_array[incomingEdges1[i-1].intValue()], e);
            else
                assertNull(incomingEdges1[i-1]);
        }
        
        // test getDistanceMap(v, k)
        dsp.reset();
        for (int i = 1; i <= distances1.length; i++)
        {
            distances = dsp.getDistanceMap(start, i);
            assertTrue(distances.size() <= i);
            d_prev = 0; // smallest possible distance

            reachable.clear();
            for (Iterator d_iter = distances.keySet().iterator(); d_iter.hasNext(); )
            {
                String cur = d_iter.next();
                double d_cur = ((Double)distances.get(cur)).doubleValue();
                assertTrue(d_cur >= d_prev);

                d_prev = d_cur;
                int j = indexer.get(cur);

                assertEquals(distances1[j-1], d_cur, .001);
                reachable.add(cur);
            }
            for (Iterator v_iter = g.getVertices().iterator(); v_iter.hasNext(); )
            {
                String v = v_iter.next();
                assertEquals(reachable.contains(v), distances.keySet().contains(v));
            }
        }
                
        // test getIncomingEdgeMap(v, k)
        dsp.reset();
        for (int i = 1; i <= incomingEdges1.length; i++)
        {
            incomingEdgeMap = dsp.getIncomingEdgeMap(start, i);
            assertTrue(incomingEdgeMap.size() <= i);
            for (Iterator e_iter = incomingEdgeMap.keySet().iterator(); e_iter.hasNext(); )
            {
                String v = e_iter.next();
                Integer e = incomingEdgeMap.get(v);
                int j = indexer.get(v);
                if (e != null)
                    assertEquals(edge_array[incomingEdges1[j-1].intValue()], e);
                else
                    assertNull(incomingEdges1[j-1]);
            }
        }
    }
    
    public void addEdges(Graph g, BiMap indexer, Integer[] edge_array)
    {
    	
//        Indexer id = Indexer.getIndexer(g);
        for (int i = 0; i < edges.length; i++)
        {
            int[] edge = edges[i];
            Integer e = i;
            g.addEdge(i, indexer.inverse().get(edge[0]), indexer.inverse().get(edge[1]));
            edge_array[i] = e;
            if (edge.length > 2) {
            	edgeWeights.put(e, edge[2]);
//                e.addUserDatum("weight", edge[2]);
            }
        }
    }

    
//    private class UserDataEdgeWeight implements NumberEdgeValue
//    {
//        private Object ud_key;
//        
//        public UserDataEdgeWeight(Object key)
//        {
//            ud_key = key;
//        }
//        
//		/**
//		 * @see edu.uci.ics.jung.utils.NumberEdgeValue#getNumber(edu.uci.ics.jung.graph.ArchetypeEdge)
//		 */
//		public Number getNumber(ArchetypeEdge e)
//		{
//            return (Number)e.getUserDatum(ud_key);
//		}
//
//		/**
//		 * @see edu.uci.ics.jung.utils.NumberEdgeValue#setNumber(edu.uci.ics.jung.graph.ArchetypeEdge, java.lang.Number)
//		 */
//		public void setNumber(ArchetypeEdge e, Number n)
//		{
//            throw new UnsupportedOperationException();
//		}
//    }
}

 

Ads help maintain this website.