/*
* Copyright (c) 2003, The JUNG Authors 
*
* All rights reserved.
*
* This software is open-source under the BSD license; see either
* "license.txt" or
* https://github.com/jrtom/jung/blob/master/LICENSE for a description.
*/
package edu.uci.ics.jung.algorithms.shortestpath;

import java.util.HashMap;
import java.util.Map;

import edu.uci.ics.jung.graph.Hypergraph;

/**
 * Computes the shortest path distances for graphs whose edges are not weighted (using BFS).
 * 
 * @author Scott White
 */
public class UnweightedShortestPath 
    implements ShortestPath, Distance
{
	private Map> mDistanceMap;
	private Map> mIncomingEdgeMap;
	private Hypergraph mGraph;
    private Map distances = new HashMap();

	/**
	 * Constructs and initializes algorithm
	 * @param g the graph
	 */
	public UnweightedShortestPath(Hypergraph g)
	{
		mDistanceMap = new HashMap>();
		mIncomingEdgeMap = new HashMap>();
		mGraph = g;
	}

    /**
     * @see edu.uci.ics.jung.algorithms.shortestpath.Distance#getDistance(Object, Object)
     */
	public Number getDistance(V source, V target)
	{
		Map sourceSPMap = getDistanceMap(source);
		return sourceSPMap.get(target);
	}

    /**
     * @see edu.uci.ics.jung.algorithms.shortestpath.Distance#getDistanceMap(Object)
     */
	public Map getDistanceMap(V source)
	{
		Map sourceSPMap = mDistanceMap.get(source);
		if (sourceSPMap == null)
		{
			computeShortestPathsFromSource(source);
			sourceSPMap = mDistanceMap.get(source);
		}
		return sourceSPMap;
	}

	/**
	 * @see edu.uci.ics.jung.algorithms.shortestpath.ShortestPath#getIncomingEdgeMap(Object)
	 */
	public Map getIncomingEdgeMap(V source)
	{
		Map sourceIEMap = mIncomingEdgeMap.get(source);
		if (sourceIEMap == null)
		{
			computeShortestPathsFromSource(source);
			sourceIEMap = mIncomingEdgeMap.get(source);
		}
		return sourceIEMap;
	}


	/**
	 * Computes the shortest path distances from a given node to all other nodes.
	 * @param source the source node
	 */
	private void computeShortestPathsFromSource(V source)
	{
		BFSDistanceLabeler labeler = new BFSDistanceLabeler();
		labeler.labelDistances(mGraph, source);
        distances = labeler.getDistanceDecorator();
		Map currentSourceSPMap = new HashMap();
		Map currentSourceEdgeMap = new HashMap();

        for(V vertex : mGraph.getVertices()) {
            
			Number distanceVal = distances.get(vertex);
            // BFSDistanceLabeler uses -1 to indicate unreachable vertices;
            // don't bother to store unreachable vertices
            if (distanceVal != null && distanceVal.intValue() >= 0) 
            {
                currentSourceSPMap.put(vertex, distanceVal);
                int minDistance = distanceVal.intValue();
                for(E incomingEdge : mGraph.getInEdges(vertex)) 
                {
                	for (V neighbor : mGraph.getIncidentVertices(incomingEdge))
                	{
                		if (neighbor.equals(vertex))
                			continue;
	
	                    Number predDistanceVal = distances.get(neighbor);
	
	                    int pred_distance = predDistanceVal.intValue();
	                    if (pred_distance < minDistance && pred_distance >= 0)
	                    {
	                        minDistance = predDistanceVal.intValue();
	                        currentSourceEdgeMap.put(vertex, incomingEdge);
	                    }
                	}
                }
            }
		}
		mDistanceMap.put(source, currentSourceSPMap);
		mIncomingEdgeMap.put(source, currentSourceEdgeMap);
	}
    
    /**
     * Clears all stored distances for this instance.  
     * Should be called whenever the graph is modified (edge weights 
     * changed or edges added/removed).  If the user knows that
     * some currently calculated distances are unaffected by a
     * change, reset(V) may be appropriate instead.
     * 
     * @see #reset(Object)
     */
    public void reset()
    {
        mDistanceMap.clear();
        mIncomingEdgeMap.clear();
    }
    
    /**
     * Clears all stored distances for the specified source vertex 
     * source.  Should be called whenever the stored distances
     * from this vertex are invalidated by changes to the graph.
     * 
     * @see #reset()
     * 
     * @param v the vertex for which distances should be cleared
     */
    public void reset(V v)
    {
        mDistanceMap.remove(v);
        mIncomingEdgeMap.remove(v);
    }
}

 

Ads help maintain this website.