/*
* 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.