cvs commit: jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/dataflow DataFlowEquations.java DataFlowSolutions.java

[dd...@apache.org]

ddp         2002/07/26 07:53:53

  Added:       graph2/src/java/org/apache/commons/graph/algorithm/dataflow
                        DataFlowEquations.java DataFlowSolutions.java
  Log:
  Graph now has DataFlow solvers!
  
  Revision  Changes    Path
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/dataflow/DataFlowEquations.java
  
  Index: DataFlowEquations.java
  ===================================================================
  package org.apache.commons.graph.algorithm.dataflow;
  
  import java.util.BitSet;
  
  import org.apache.commons.graph.*;
  
  public interface DataFlowEquations {
      /**
       * This method shows when a definition is defined.
       */
      public BitSet generates( Vertex vertex );
  
      /**
       * This method shows when a definition is killed (or overwritten.)
       */
      public BitSet kills( Vertex vertex );
  }
  
  
  
  1.1                  jakarta-commons-sandbox/graph2/src/java/org/apache/commons/graph/algorithm/dataflow/DataFlowSolutions.java
  
  Index: DataFlowSolutions.java
  ===================================================================
  package org.apache.commons.graph.algorithm.dataflow;
  
  import java.util.Map;
  import java.util.BitSet;
  import java.util.HashMap;
  import java.util.Iterator;
  
  import org.apache.commons.graph.*;
  import org.apache.commons.graph.exception.*;
  import org.apache.commons.graph.domain.basic.*;
  
  
  public class DataFlowSolutions
  {
      private Map inValues = new HashMap(); // VERTEX X BITSET
      private Map outValues = new HashMap();
  
      public DataFlowSolutions( DirectedGraph graph,
  			      DataFlowEquations eq ) {
  	calculateDataFlow( graph, eq );
      }
  
      private void calculateDataFlow( DirectedGraph graph,
  				    DataFlowEquations eq ) {
  	Iterator vertices = graph.getVertices().iterator();
  	while (vertices.hasNext()) {
  	    Vertex v = (Vertex) vertices.next();
  	    inValues.put( v, new BitSet() );   // Initialize everything to 
  	    outValues.put( v, new BitSet() );  // empty
  	}
  
  	boolean isOK = true;
  	while (isOK) {
  	    vertices = graph.getVertices().iterator();
  	    isOK = false;
  	    while (vertices.hasNext()) {
  		Vertex v = (Vertex) vertices.next();
  
  		BitSet out = new BitSet();
  		out.or( (BitSet) inValues.get( v ));
  		out.or( eq.generates( v ));
  		out.andNot( eq.kills( v ));
  		
  		/*
  		System.err.println("Old Out: " + v + ":" + outValues.get( v ));
  		System.err.println("New Out: " + v + ":" + out);
  		*/
  		if (!out.equals( outValues.get( v ))) {
  		    isOK = true;
  		    outValues.put( v, out );
  
  		    Iterator outbound = graph.getOutbound( v ).iterator();
  		    while (outbound.hasNext()) {
  			Vertex target = 
  			    graph.getTarget( (Edge) outbound.next() );
  			
  			BitSet in = (BitSet) inValues.get( target );
  			in.or( out );
  			inValues.put( target, in );
  			/*
  			System.err.println("Old In: " + target + ":" + 
  					   inValues.get( target ));
  			System.err.println("New In: " + target + ":" + in );
  			*/
  		    }
  		}
  	    }
  	}
      }
  
      public BitSet reaches( Vertex vertex ) {
  	return (BitSet) inValues.get( vertex );
      }
  
      public BitSet leaves( Vertex vertex ) {
  	return (BitSet) outValues.get( vertex );
      }
  }
  
  
  

--
To unsubscribe, e-mail:   <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>