Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 2000 Feng Qian
   *
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Lesser General Public
   * License as published by the Free Software Foundation; either
   * version 2.1 of the License, or (at your option) any later version.
   *
   * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  * Lesser General Public License for more details.
  *
  * You should have received a copy of the GNU Lesser General Public
  * License along with this library; if not, write to the
  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  * Boston, MA 02111-1307, USA.
  */
 
 /*
  * Modified by the Sable Research Group and others 1997-1999.  
  * See the 'credits' file distributed with Soot for the complete list of
  * contributors.  (Soot is distributed at http://www.sable.mcgill.ca/soot)
  */
 
 package soot.jimple.toolkits.annotation.arraycheck;
 
 import java.util.*;
 
 {
     private boolean isUnknown;
 
     /* The graph is in linked list structure. */
 
     /* vertex set, may contain superious nodes. */
     private HashSet vertexes = new HashSet();
 
     public WeightedDirectedSparseGraph(HashSet vertexset)
     {
 	this(vertexsetfalse);
     }
 
     public WeightedDirectedSparseGraph(HashSet vertexsetboolean isTop)
     {
 	this. = vertexset;
 	this. = !isTop;
     }
 
     public void setTop()
     {
 	this. = false;
 	this..clear();
     }
 
     public HashSet getVertexes()
     {
 	return this.;
     }
 
     public void setVertexes(HashSet newset)
     {
 	this. = newset;
 	this..clear();
     }
    
Add an edge with weight to the graph
 
     public void addEdge(Object fromObject toint w)
     {
 	if (this.)
 	    throw new RuntimeException("Unknown graph can not have edges");
 
 	Hashtable<ObjectIntContainertargets = .get(from);
 
 	if (targets == null)
 	{
 	    /* a new node was added to the graph */
 	    targets = new Hashtable<ObjectIntContainer>();
 	    .put(fromtargets);
 	}
 
         IntContainer weight = targets.get(to);
 
 	if (weight == null)
 	{
 	    weight = new IntContainer(w);
 	    targets.put(toweight);
 	}
 	else
 	{
 	    if (weight.value > w)
 		weight.value = w;
 	}
     }

    
addMutualEdge adds bi-direct edges between two nodes. for example, i = j + 1; generates two directed edges. one from j to i with weight 1, another from i to j with weight -1
    public void addMutualEdges(Object fromObject toint weight)
    {
	addEdge(fromtoweight);
	addEdge(tofrom, -weight);
    }
    /* removeEdge removes all edges from source to target.
     */
    public void removeEdge(Object fromObject to)
    {
	Hashtable targets = .get(from);
	if (targets == null)
	    return;
	targets.remove(to);
	if (targets.size() == 0)
	{
	    .remove(from);
	}
    }
    public boolean hasEdge(Object fromObject to)
    {
	Hashtable targets = .get(from);
	if (targets == null)
	    return false;
	return targets.containsKey(to);
    }
    /* return back the weight of the edge from source to target */
    public int edgeWeight(Object fromObject to)
    {
	Hashtable targets = .get(from);
	if (targets == null)
	    throw new RuntimeException("No such edge ("+from+" ,"+to+") exists.");
	IntContainer weight = (IntContainer)targets.get(to);
	if (weight == null)
	    throw new RuntimeException("No such edge ("+from+", "+to+") exists.");
	return weight.value;
    }
    /* If other graph is unknown, keep current one. 
    * If current graph is unknown, copy the other.
    And if both are not unknown, union each edge.
    */
    public void unionSelf(WeightedDirectedSparseGraph other)
    {
	if (other == null)
	    return;
	    other;
	if (othergraph.isUnknown)
	    return;
	if (this.)
	    addAll(othergraph);
	List<ObjectsourceList = new ArrayList<Object>(this..keySet());
	Iterator<ObjectfirstSrcIt = sourceList.iterator();
	while (firstSrcIt.hasNext())
	{
	    Object srcKey = firstSrcIt.next();
	    Hashtable src1 = this..get(srcKey);
	    Hashtable src2 = othergraph.sources.get(srcKey);
	    /* other is unbounded */
	    if (src2 == null)
	    {
		this..remove(srcKey);
		continue;
	    }
	    List targetList = new ArrayList(src1.keySet());
	    Iterator targetIt = targetList.iterator();
	    
	    while (targetIt.hasNext())
	    {
		Object target = targetIt.next();
		IntContainer w1 = (IntContainer)src1.get(target);
		IntContainer w2 = (IntContainer)src2.get(target);
		/* other is unbounded */
		if (w2 == null)
		{
		    src1.remove(target);
		    continue;
		}
		if (w2.value > w1.value)
		    w1.value = w2.value;
	    }
	    if (src1.size() == 0)
		this..remove(srcKey);
	}
    }
    /* it was used to compare with former graph, if the edge weight is increasing,
       the edge is removed (unlimited distance).
    */
    public void widenEdges(WeightedDirectedSparseGraph othergraph)
    {
	    othergraph;
	if (other.isUnknown)
	    return;
	Hashtable<ObjectHashtable<ObjectIntContainer>> othersources = other.sources;
	List<ObjectsourceList = new ArrayList<Object>(this..keySet());
	Iterator<ObjectsrcIt = sourceList.iterator();
	while (srcIt.hasNext())
	{
	    Object src = srcIt.next();
	    Hashtable thistargets = this..get(src);
	    Hashtable othertargets = othersources.get(src);
	    /* the former is unbounded */
	    if (othertargets == null)
	    {
		this..remove(src);
		continue;
	    }
	    List targetList = new ArrayList(thistargets.keySet());
	    Iterator targetIt = targetList.iterator();
	    while (targetIt.hasNext())
	    {
		Object target = targetIt.next();
		IntContainer thisweight = (IntContainer)thistargets.get(target);
		IntContainer otherweight = (IntContainer)othertargets.get(target);
		/* the former edge is unbounded. */
		if (otherweight == null)
		{
		    thistargets.remove(target);
		    continue;
		}
		if (thisweight.value > otherweight.value)
		{
		    thistargets.remove(target);
		}
	    }
	    
	    if (thistargets.size()==0)
		this..remove(src);
	}
    }
    /* It is necessary to prune the graph to the shortest path. */
    /* it could be replaced by a ShortestPathGraph */
    /* kill a node. */
    public void killNode(Object tokill)
    {
	if (!this..contains(tokill))
	    return;
       	this.makeShortestPathGraph();
	List<ObjectsourceList = new ArrayList<Object>(.keySet());
	Iterator<ObjectsrcIt = sourceList.iterator();
	while (srcIt.hasNext())
	{
	    Object src = srcIt.next();
	    Hashtable targets = .get(src);
	    /* delete the in edge */
	    targets.remove(tokill);
	    if (targets.size() == 0)
	}
	.remove(tokill);
        this.makeShortestPathGraph();
    }
    /* when met i=i+c, it is necessary to update the weight of in and out edges */
    public void updateWeight(Object whichint c)
    {
	/* for the in edge, the weight + c. for the out edge, the weight - c */
	while (srcIt.hasNext())
	{
	    Object from = srcIt.next();
	    
	    Hashtable targets = .get(from);
	    IntContainer weight = (IntContainer)targets.get(which);
	    if (weight != null)
		weight.value += c;
	}
	/* update out edges */
	Hashtable toset = .get(which);
	if (toset == null)
	    return;
	Iterator toIt = toset.keySet().iterator();
	while (toIt.hasNext())
	{
	    Object to = toIt.next();
	    
	    IntContainer weight = (IntContainer)toset.get(to);
	    
	    weight.value -= c;
	}
    }
    public void clear()
    {
    }
    public void replaceAllEdges(WeightedDirectedSparseGraph other)
    {
	this. = other.isUnknown;
	this. = other.vertexes;
	this. = other.sources;
    }
    /* add edges that belong to this vertex set */
    public void addBoundedAll(WeightedDirectedSparseGraph another)
    {
	this. = another.isUnknown;
	Hashtable<ObjectHashtable<ObjectIntContainer>> othersources = another.sources;
	Iterator thisnodeIt = this..iterator();
	while (thisnodeIt.hasNext())
	{
	    Object src = thisnodeIt.next();
	    Hashtable othertargets = othersources.get(src);
	    if (othertargets == null)
		continue;
	    Hashtable<ObjectIntContainerthistargets = new Hashtable<ObjectIntContainer>();
	    Iterator othertargetIt = othertargets.keySet().iterator();
	    while (othertargetIt.hasNext())
	    {
		Object key = othertargetIt.next();
		if (this..contains(key))
		{
		    IntContainer weight = (IntContainer)othertargets.get(key);
		    thistargets.put(keyweight.dup());
		}
	    }
	    if (thistargets.size() > 0)
		this..put(srcthistargets);
	}
    }
    /* add another graph's edge and weight to this graph,
       it simply replace the edge weight.
       When used with clear, it can copy a graph to a new graph
    */
    public void addAll(WeightedDirectedSparseGraph othergraph)
    {
	    othergraph;
	this. = another.isUnknown;
	this.clear();
	Hashtable<ObjectHashtable<ObjectIntContainer>> othersources = another.sources;
	Iterator<ObjectothersrcIt = othersources.keySet().iterator();
	while (othersrcIt.hasNext())
	{
	    Object src = othersrcIt.next();
	    Hashtable othertargets = othersources.get(src);
	    Hashtable<ObjectIntContainerthistargets = new Hashtable<ObjectIntContainer>(othersources.size());
	    this..put(srcthistargets);
	    Iterator targetIt = othertargets.keySet().iterator();
	    while (targetIt.hasNext())
	    {
		Object target = targetIt.next();
		IntContainer otherweight = (IntContainer)othertargets.get(target);
		thistargets.put(targetotherweight.dup());
	    }
	}
    }
    public boolean equals(Object other)
    {
	if (other == null)
	    return false;
	if (!(other instanceof WeightedDirectedSparseGraph)) 
	    return false;
	if (this. != othergraph.isUnknown)
	    return false;
	if (this.)
	    return true;
	// compare each edges. It is not always true, only when shortest path graph can be guaranteed.
	Hashtable<ObjectHashtable<ObjectIntContainer>> othersources = othergraph.sources;
	if (this..size() != othersources.size())
	    return false;
	Iterator<ObjectsourceIt = this..keySet().iterator();
	while (sourceIt.hasNext())
	{
	    Object src = sourceIt.next();
	    Hashtable thistarget = .get(src);
	    Hashtable othertarget = othersources.get(src);
	    
	    if (othertarget == null)
		return false;
	    if (thistarget.size() != othertarget.size())
		return false;
	    Iterator targetIt = thistarget.keySet().iterator();
	    while (targetIt.hasNext())
	    {
		Object target = targetIt.next();
		IntContainer thisweight = (IntContainer)thistarget.get(target);
		IntContainer otherweight = (IntContainer)othertarget.get(target);
		if (otherweight == null)
		    return false;
		if (thisweight.value != otherweight.value)
		    return false;
	    }
	}
	return true;
    }
    public String toString()
    {
	String graphstring="WeightedDirectedSparseGraph:\n";
	graphstring = graphstring+this.+"\n";
	while (srcIt.hasNext())
	{
	    Object src = srcIt.next();
	    graphstring = graphstring + src +" : ";
	    Hashtable targets = .get(src);
	    
	    Iterator targetIt = targets.keySet().iterator();
	    while (targetIt.hasNext())
	    {
		Object target = targetIt.next();
		IntContainer weight = (IntContainer)targets.get(target);
		graphstring = graphstring + target +"("+weight.value+")  ";
	    }
	    graphstring +="\n";
	}
	return graphstring;
    }
    {
	newone.addAll(this);
	return newone;
    }
    public boolean makeShortestPathGraph()
    {
	boolean nonegcycle = true;
	List<ObjectsrcList = new ArrayList<Object>(.keySet());
	Iterator<ObjectsrcIt = srcList.iterator();
	while (srcIt.hasNext())
	{
	    Object src = srcIt.next();
	    
	    if (!SSSPFinder(src))
	    {
		nonegcycle = false;
	    }
	}
	return nonegcycle;
    }
    private final HashSet<ObjectreachableNodes = new HashSet<Object>();
    private final Hashtable<ObjectIntContainerdistance = new Hashtable<ObjectIntContainer>();
    private final Hashtable<ObjectObjectpei = new Hashtable<ObjectObject>();
    
    private boolean SSSPFinder(Object src)
    {
	Hashtable<ObjectIntContaineroutedges = .get(src);
	if (outedges == null)
	    return true;
	if (outedges.size() == 0)
	    return true;
	// relaxation
	int vSize = .size();
	for (int i=0; i<vSizei++)
	{
	    while (edgeIt.hasNext())
	    {
		    edgeIt.next();
		Relax(edge.fromedge.toedge.weight);
	    }
	}
	// check negative cycle
	{
	    while (edgeIt.hasNext())
	    {
		    edgeIt.next();
		IntContainer dfrom = .get(edge.from);
		if (dfrom == null)
		    continue;
		IntContainer dto = .get(edge.to);
		if (dto == null)
		    continue;
		if (dto.value > (dfrom.value + edge.weight))
		    return false;	
	    }    
	}
	// update the graph
	outedges.clear();
	while (targetIt.hasNext())
	{
	    Object to = targetIt.next();
	    IntContainer dist = .get(to);
	    outedges.put(todist.dup());	    
	}
	return true;
    }
    private void InitializeSingleSource(Object src)
    {
	.put(srcnew IntContainer(0));
    }
    private void getReachableNodesAndEdges(Object src)
    {
	LinkedList<Objectworklist = new LinkedList<Object>();
	worklist.add(src);
	while (!worklist.isEmpty())
	{
	    Object from = worklist.removeFirst();
	    Hashtable targets = .get(from);
	    if (targets == null)
		continue;
	    Iterator targetIt = targets.keySet().iterator();
	    while (targetIt.hasNext())
	    {
		Object target = targetIt.next();
		if (!.contains(target))
		{
		    worklist.add(target);
		    .add(target);
		}
		IntContainer weight = (IntContainer)targets.get(target);
		.add(new WeightedDirectedEdge(fromtargetweight.value));
	    }
	}
    }
    private void Relax(Object fromObject toint weight)
    {
	IntContainer dfrom = .get(from);
	if (dfrom != null)
	{
	    int vfrom = dfrom.value;
	    int vnew = vfrom+weight;
	    if (dto == null)
	    {
		.put(tonew IntContainer(vnew));
		.put(tofrom);
	    }
	    else
	    {
		int vto = dto.value;
		if (vto > vnew)
		{
		    .put(tonew IntContainer(vnew));
		    .put(tofrom);
		}
	    }
	}
    }
New to GrepCode? Check out our FAQ X