Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /* Soot - a J*va Optimization Framework
   * Copyright (C) 1999 Patrice Pominville, Raja Vallee-Rai, Patrick Lam
   * Copyright (C) 2007 Richard L. Halpert
   *
   * 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.toolkits.graph;
 
 
 import java.util.*;
 
 import soot.*;
 import soot.util.*;




HashMap based implementation of a MutableEdgeLabelledDirectedGraph.
 
 class DGEdge
 {
 	
 	public DGEdge(Object fromObject to)
 	{
 		this. = from;
 		this. = to;
 	}
 	
 	public Object from()
 	{
 		return ;
 	}
 	
 	public Object to()
 	{
 		return ;
 	}
 	
 	public boolean equals(Object o)
 	{
 		if(o instanceof DGEdge)
 		{
 			DGEdge other = (DGEdgeo;
 			return .equals(other.from) && .equals(other.to);
 		}
 		return false;
 	}
 	
 	public int hashCode()
 	{
 		return .hashCode() + .hashCode();
 	}
 }
 
 {
     protected HashMap<Object,ArrayListnodeToPreds = new HashMap();
     protected HashMap<Object,ArrayListnodeToSuccs = new HashMap();
     
     protected HashMap<DGEdge,ArrayList<Object>> edgeToLabels = new HashMap();
     protected HashMap<Object,ArrayList<DGEdge>> labelToEdges = new HashMap();
 
     protected Chain heads = new HashChain();
     protected Chain tails = new HashChain();
 
     {
     }

    
Removes all nodes and edges.
 
     public void clearAll() {
          = new HashMap();
          = new HashMap();
          = new HashMap();
          = new HashMap();
         = new HashChain();
         = new HashChain();
    }
    public Object clone() {
        g.nodeToPreds = (HashMap).clone();
        g.nodeToSuccs = (HashMap).clone();
        g.edgeToLabels = (HashMap).clone();
        g.labelToEdges = (HashMap).clone();
        g.heads = HashChain.listToHashChain(HashChain.toList());
        g.tails = HashChain.listToHashChain(HashChain.toList());
        return g;
    }
    /* Returns an unbacked list of heads for this graph. */
    public List getHeads()
    {
        ArrayList l = new ArrayList(); l.addAll();
        return Collections.unmodifiableList(l);
    }
    /* Returns an unbacked list of tails for this graph. */
    public List getTails()
    {
        ArrayList l = new ArrayList(); l.addAll();
        return Collections.unmodifiableList(l);
    }
    public List getPredsOf(Object s)
    {
        List l = .get(s);
        if (l != null)
            return Collections.unmodifiableList(l);
        else
            throw new RuntimeException(s+"not in graph!");
    }
    public List getSuccsOf(Object s)
    {
        List l = .get(s);
        if (l != null)
            return Collections.unmodifiableList(l);
        else
            throw new RuntimeException(s+"not in graph!");
    }
    public int size()
    {
        return .keySet().size();
    }
    public Iterator iterator()
    {
        return .keySet().iterator();
    }
    public void addEdge(Object fromObject toObject label)
    {
        if (from == null || to == null)
						throw new RuntimeException("edge from or to null");
		if (label == null)
						throw new RuntimeException("edge with null label");
        if (containsEdge(fromtolabel))
            return;
        List<ObjectsuccsList = .get(from);
        if (succsList == null)
            throw new RuntimeException(from + " not in graph!");
        List<ObjectpredsList = .get(to);
        if (predsList == null)
            throw new RuntimeException(to + " not in graph!");
        if (.contains(to))
            .remove(to);
        if (.contains(from))
            .remove(from);
		if(!succsList.contains(to))
	        succsList.add(to);
	    if(!predsList.contains(from))
	        predsList.add(from);
	    
	    DGEdge edge = new DGEdge(fromto);
			.put(edgenew ArrayList());
	    List<Objectlabels = .get(edge);
	    
	    if(!.containsKey(label))
	    	.put(labelnew ArrayList());
	    List<DGEdgeedges = .get(label);
//		if(!labels.contains(label))
			labels.add(label);
//		if(!edges.contains(edge))
			edges.add(edge);
    }
	public List<ObjectgetLabelsForEdges(Object fromObject to)
	{
		DGEdge edge = new DGEdge(fromto);
		return .get(edge);
	}
	{
		List<DGEdgeedges = .get(label);
		if(edges == null)
			return ret;
		for(DGEdge edge : edges)
		{
			if(!ret.containsNode(edge.from()))
				ret.addNode(edge.from());
			if(!ret.containsNode(edge.to()))
				ret.addNode(edge.to());
			ret.addEdge(edge.from(), edge.to());
		}
		return ret;
	}
    public void removeEdge(Object fromObject toObject label)
    {
        if (!containsEdge(fromtolabel))
            return;
            
        DGEdge edge = new DGEdge(fromto);
        List labels = .get(edge);
        iflabels == null )
        	throw new RuntimeException("edge " + edge + " not in graph!");
        
        List edges = .get(label);
        ifedges == null )
        	throw new RuntimeException("label " + label + " not in graph!");
		labels.remove(label);
		edges.remove(edge);
		// if this edge has no more labels, then it's gone!
		if(labels.isEmpty())
		{
	        List succsList = .get(from);
	        if (succsList == null)
	            throw new RuntimeException(from + " not in graph!");
	        List predsList = .get(to);
	        if (predsList == null)
	            throw new RuntimeException(to + " not in graph!");
	        succsList.remove(to);
	        predsList.remove(from);
	        if (succsList.isEmpty())
	            .add(from);
	        if (predsList.isEmpty())
	            .add(to);
	    }
	    
	    // if this label has no more edges, then who cares?
	    if(edges.isEmpty())
	    	.remove(label);
    }
    public void removeAllEdges(Object fromObject to)
	{
        if (!containsAnyEdge(fromto))
            return;
            
        DGEdge edge = new DGEdge(fromto);
        List labels = .get(edge);
        iflabels == null )
        	throw new RuntimeException("edge " + edge + " not in graph!");
        
        for(Object label : labels)
        {        
	        removeEdge(fromtolabel);
	    }
	}
    public void removeAllEdges(Object label)
    {
		if( !containsAnyEdge(label) )
			return;
		List<DGEdgeedges = .get(label);
		ifedges == null )
			throw new RuntimeException("label " + label + " not in graph!");
		for(DGEdge edge : edges)
		{
			removeEdge(edge.from(), edge.to(), label);
		}
	}
    public boolean containsEdge(Object fromObject toObject label)
    {
		DGEdge edge = new DGEdge(fromto);
		if(.get(edge) != null && .get(edge).contains(label))
			return true;
		return false;
    }
    public boolean containsAnyEdge(Object fromObject to)
    {
		DGEdge edge = new DGEdge(fromto);
		if(.get(edge) != null && .get(edge).isEmpty())
			return false;
		return true;
    }
    public boolean containsAnyEdge(Object label)
    {
		if(.get(label) != null && .get(label).isEmpty())
			return false;
		return true;
    }
    public boolean containsNode(Object node)
    {
        return .keySet().contains(node);
    }
    public List<ObjectgetNodes()
    {
        return Arrays.asList(.keySet().toArray());
    }
    public void addNode(Object node)
    {
				if (containsNode(node))
						throw new RuntimeException("Node already in graph");
				.put(nodenew ArrayList());
        .put(nodenew ArrayList());
        .add(node); 
				.add(node);
    }
    public void removeNode(Object node)
    {
        List succs = (List).get(node).clone();
        for (Iterator succsIt = succs.iterator(); succsIt.hasNext(); )
            removeAllEdges(nodesuccsIt.next());
        .remove(node);
        List preds = (List).get(node).clone();
        for (Iterator predsIt = preds.iterator(); predsIt.hasNext(); )
            removeAllEdges(predsIt.next(), node);
        .remove(node);
        if (.contains(node))
            .remove(node); 
        if (.contains(node))
            .remove(node);
    }
    public void printGraph()
    {
		for (Iterator it = iterator(); it.hasNext(); )
		{
		    Object node = it.next();
		    G.v()..println("Node = "+node);
		    G.v()..println("Preds:");
		    for (Iterator predsIt = getPredsOf(node).iterator(); predsIt.hasNext(); )
		    {
		    	Object pred = predsIt.next();
		        DGEdge edge = new DGEdge(prednode);
		        List labels = .get(edge);
				G.v()..println("     " + pred + " [" + labels + "]");
		    }
		    G.v()..println("Succs:");
		    for (Iterator succsIt = getSuccsOf(node).iterator(); succsIt.hasNext(); )
		    {
		    	Object succ = succsIt.next();
		        DGEdge edge = new DGEdge(nodesucc);
		        List labels = .get(edge);
				G.v()..println("     " + succ + " [" + labels + "]");
		    }
		}
    }
}

 
New to GrepCode? Check out our FAQ X