TwoTasksAnalysis.java

package buffalo.twoTasksAnalysis; 

import java.util.Vector;
import buffalo.dataStructures.*;
import buffalo.transportNetwork.*;

/** 
    Ensemble de méthodes qui permettent d'effectuer sur un graphe 
    partiel à deux <CODE>t&acirc;ches</CODE> une 
    r&eacute;duction polynomiale vers un probl&egrave;me de 
    coupe minimale dans un r&eacute;seau de Transport. 
    On se retrouve à la derni&egrave;re &eacute;tape avec un 
    <CODE>TransportNetwork</CODE> sur lequel il n'est 
    n&eacute;cessaire que de faire 
    un <CODE>runFlow()</CODE>.
 */

public class TwoTasksAnalysis
{
    /**
      Si <CODE>print</CODE>, une trace de l'algorithme est affich&eacute;e 
      sur <CODE>stdout</CODE>.
     */
    
    public static boolean print = false;

    /*-------------------------------------------------------*/
    
    /**
       Retourne une condition n&eacute;cessaire de non-blocage entre 
       <CODE>firstBuffer</CODE> et <CODE>secondBuffer</CODE>
       de m&ecirc;me orientation. Il trace les contraintes
       de buffer vide de <CODE>secondBuffer</CODE> et 
       cherche la dimension &agrave; donner &agrave; 
       <CODE>secondBuffer</CODE> pour ne pas bloquer.
    */

    public static BufferPairExpression getOneWayBufferPairExpression
	(Buffer firstBuffer, Buffer secondBuffer)
    {
	TraceTracer.traceEmptyBufferConstraints(secondBuffer);
	BufferPairExpression myExpression = 
	    new BufferPairExpression(firstBuffer, secondBuffer);
	BufferPairCondition myCondition = 
	    getOneWayBufferPairCondition(firstBuffer);
	myExpression.addBufferPairCondition(myCondition);
	return myExpression;
    }


    /*-------------------------------------------------------*/
    
    /**
       Retourne une condition n&eacute;cessaire de non-blocage entre 
       <CODE>firstBuffer</CODE> et <CODE>secondBuffer</CODE>.  
       Les arcs des <CODE>op&eacute;rations</CODE> li&eacute;es &agrave 
       <CODE>secondBuffer</CODE> sont suppos&eacute;s 
       d&eacute;j&agrave; trac&eacute;s.       
    */

    private static BufferPairCondition getOneWayBufferPairCondition
	(Buffer firstBuffer)
    {
	firstBuffer.setSize(1);
	TraceTracer.traceFullBufferConstraints(firstBuffer);
	TwoTasksCircuit myCircuit;
	myCircuit = TraceTracer.findTwoTasksCircuit
	    (firstBuffer.getWritingTask(), firstBuffer.getReadingTask());
	while(myCircuit != null)
	    {
		adjustSizeOf(firstBuffer, myCircuit);
		TraceTracer.traceFullBufferConstraints(firstBuffer);
		myCircuit = TraceTracer.findTwoTasksCircuit
		    (firstBuffer.getWritingTask(), firstBuffer.getReadingTask());					
	    }	
	return new BufferPairCondition(firstBuffer.getSize(), 1);
    }


    /*-------------------------------------------------------*/
    
    /**
       Ajuste la capacit&eacute; de <CODE>myBuffer</CODE> 
       de sorte &agrave; briser <CODE>myCircuit</CODE>.
    */

    private static void adjustSizeOf(Buffer myBuffer, TwoTasksCircuit myCircuit)
    {
	int formerSize = myBuffer.getSize();	
	Operation myOperation;
	int n_o_p;
	if (myCircuit.getNorthWest().getBuffer() == myBuffer)
	    {
		myOperation = myCircuit.getNorthEast();
		n_o_p = myCircuit.getNorthWest().getN();
	    }
	else
	    {
		myOperation = myCircuit.getSouthEast();
		n_o_p = myCircuit.getSouthWest().getN();		
	    }	
	while(myOperation.getBuffer()!=myBuffer)
	    {
		myOperation = myOperation.getPreviousFixedOperation();
	    }
	int n_o_r = myOperation.getN();
	myBuffer.setSize(formerSize + n_o_r - n_o_p + 1);
    }

    /*-------------------------------------------------------*/
    
    /**
       Retourne une disjonction de conditions suffisantes 
       de non-blocage entre <CODE>northBuffer</CODE> et 
       <CODE>southBuffer</CODE>.       
    */

    public static BufferPairExpression getTwoWaysBufferPairExpression
	(Buffer firstBuffer, Buffer secondBuffer)
    {
	secondBuffer.setSize(1);
	BufferPairExpression myExpression = new BufferPairExpression	    
	    (firstBuffer, secondBuffer);
	BufferPairCondition myCondition;
	do
	    {
		TraceTracer.traceFullBufferConstraints(secondBuffer);
		myCondition = getOneWayBufferPairCondition
		    (firstBuffer);
		myCondition.setSecondSize(secondBuffer.getSize());
		myExpression.addBufferPairCondition(myCondition);
		secondBuffer.setSize(secondBuffer.getSize()+1);
		TraceTracer.removeAllConstraints(firstBuffer);
		TraceTracer.removeAllConstraints(secondBuffer);
	    }
	while(myCondition.getFirstSize()!=1);
	return myExpression;
    }


    /*-------------------------------------------------------*/

    /**
       Retourne un <CODE>BufferPairCollection</CODE> contenant 
       les conditions n&eacute;cessaires et suffisantes de 
       non-blocage dans le graphe partiel induit par 
       <CODE>task1</CODE> et <CODE>task2</CODE>
       sous forme canonique disjonctive.
     */
    
    public static BufferPairCollection getBufferCollectionVee
	(Task task1, Task task2)
    {
	TwoTasksCircuit empty = emptyBufferCircuit(task1, task2);
	if (empty==null)
	    {
		BufferPairCollection myCollection = 
		    new BufferPairCollection(task1, task2);
		Vector oneWayBuffers = myCollection.getOneWayBuffers();
		Vector twoWaysBuffers = myCollection.getTwoWaysBuffers();
		Buffer firstBuffer; 
		Buffer secondBuffer; 
		BufferPairExpression myExpression;
		int sizeOfVector = oneWayBuffers.size(); 
		for(int i = 0 ; i < sizeOfVector - 1 ; i ++)
		    {
			firstBuffer = (Buffer)oneWayBuffers.get(i);
			i++;		
			secondBuffer = (Buffer)oneWayBuffers.get(i); 
			myExpression = getOneWayBufferPairExpression
			    (firstBuffer, secondBuffer);
			myCollection.addBufferPairExpression
			    (myExpression);
			TraceTracer.removeAllConstraints(firstBuffer);
			TraceTracer.removeAllConstraints(secondBuffer);
		    }
		sizeOfVector = twoWaysBuffers.size(); 
		for(int i = 0 ; i < sizeOfVector - 1 ; i ++)
		    {
			firstBuffer = (Buffer)twoWaysBuffers.get(i);
			i++;		
			secondBuffer = (Buffer)twoWaysBuffers.get(i); 
			myExpression = getTwoWaysBufferPairExpression
			    (firstBuffer, secondBuffer);
			myCollection.addBufferPairExpression
			    (myExpression);
		    }
		return myCollection;
	    }
	else
	    {
		System.out.println("A Circuit made of empty buffer constraints " + 
				   " has been found, it's impossible to continue." + 
				   empty);
		return null;
	    }
    }
    /*-------------------------------------------------------*/

    /**
       Met <CODE>nonClausalBufferPairExpression</CODE> sous forme clausale 
       (canonique conjonctive).
     */
    
    public static BufferPairExpression twoWaysBufferExpressionWedgeOfBufferExpressionVee
	(BufferPairExpression nonClausalBufferPairExpression)
    {
	int l = nonClausalBufferPairExpression.getNbConditions();
	BufferPairExpression clausalBufferPairExpression = 
	    new BufferPairExpression(nonClausalBufferPairExpression.getFirstBuffer(),
				     nonClausalBufferPairExpression.getSecondBuffer());
	BufferPairCondition firstCondition = 
	    new BufferPairCondition
	    (nonClausalBufferPairExpression.getBufferPairCondition
	     (l-1).getFirstSize(),
	     nonClausalBufferPairExpression.getBufferPairCondition(0).getSecondSize()
	     );
	clausalBufferPairExpression.addBufferPairCondition(firstCondition);
	for(int i = 0 ; i < l - 1 ; i++)
	    {
		clausalBufferPairExpression.addBufferPairCondition
		    (new BufferPairCondition
		     (nonClausalBufferPairExpression.getBufferPairCondition(i).getFirstSize(),
		      nonClausalBufferPairExpression.getBufferPairCondition(i+1).getSecondSize())
		     );
	    }
	return clausalBufferPairExpression;
    }

    /*-------------------------------------------------------*/

    /**
       Met <CODE>nonClausalBufferPairCollection</CODE> sous forme clausale 
       (canonique conjonctive).
     */
    
    public static void bufferCollectionWedgeOfBufferCollectionVee
	(BufferPairCollection nonClausalBufferPairCollection)
    {
	Vector twoWaysBuffers = 
	    nonClausalBufferPairCollection.getTwoWaysBuffers();
	Buffer firstBuffer; 
	Buffer secondBuffer; 
	BufferPairExpression myExpression;
	int sizeOfVector = twoWaysBuffers.size(); 
	for(int i = 0 ; i < sizeOfVector - 1 ; i ++)
	    {
		firstBuffer = (Buffer)twoWaysBuffers.get(i);
		i++;		
		secondBuffer = (Buffer)twoWaysBuffers.get(i); 
		nonClausalBufferPairCollection.addBufferPairExpression
		    (twoWaysBufferExpressionWedgeOfBufferExpressionVee
		     (nonClausalBufferPairCollection.getBufferPairExpression
		      (firstBuffer, secondBuffer))
		     );
		
	    } 
    }

    /*-------------------------------------------------------*/

    /**
       Renvoie <CODE>true</CODE> si il existe dans 
       la trace d'ex&eacute;cution partielle induite par 
       <CODE>task1</CODE> et <CODE>task2</CODE>
       un <CODE>TwoTasksCircuit</CODE> 
       form&eacute; par des contraintes de buffer vide. 
     */
    
    public static TwoTasksCircuit emptyBufferCircuit(Task task1, Task task2)
    {
	TraceTracer.traceAllEmptyBufferConstraints();
	TwoTasksCircuit answer = TraceTracer.findTwoTasksCircuit(task1, task2);
	TraceTracer.removeAllConstraints();
	return answer;
    }
    
    /*-------------------------------------------------------*/

    /**
       Extrait de la collection sous forme clausale 
       </CODE>clausalBufferPairCollection</CODE>
       les sommets du <CODE>BufferBipartiteGraph</CODE> form&eacute;
       par les domaines de d&eacute;finition des capacit&eacute;s 
       des buffers.
     */
    
    public static BufferBipartiteGraph bufferBipartiteGraphOfClausalBufferPairCollection
	(BufferPairCollection clausalBufferPairCollection)
    {
	BufferBipartiteGraph myBufferBipartiteGraph = 
	    new BufferBipartiteGraph
	    (clausalBufferPairCollection.getFirstTask(),
	     clausalBufferPairCollection.getSecondTask());
	extractMinimums
	    (myBufferBipartiteGraph,
	     clausalBufferPairCollection);
	Vector twoWaysBuffers = 
	    clausalBufferPairCollection.getTwoWaysBuffers();
	int nbBuffers = twoWaysBuffers.size();	
	BufferPairExpression myBufferPairExpression;
	BufferPairCondition myBufferPairCondition;
	Buffer firstBuffer;
	Buffer secondBuffer;
	int firstValue;
	int secondValue;
	int nbConditions;
	BufferDomain firstBufferDomain;
	BufferDomain secondBufferDomain;
	for(int i = 1 ; i < nbBuffers ; i+=2)
	    {
		firstBuffer = (Buffer)twoWaysBuffers.get(i-1);
		secondBuffer = (Buffer)twoWaysBuffers.get(i);
		myBufferPairExpression = 
		    clausalBufferPairCollection.getBufferPairExpression
		    (firstBuffer, secondBuffer);		
		nbConditions = myBufferPairExpression.getNbConditions();
		firstBufferDomain = myBufferBipartiteGraph.getBufferDomain(firstBuffer);
		secondBufferDomain = myBufferBipartiteGraph.getBufferDomain(secondBuffer);
		for(int j = 0 ; j < nbConditions ; j++)
		    {			
			myBufferPairCondition = 
			    myBufferPairExpression.getBufferPairCondition(j);
			firstValue = myBufferPairCondition.getSizeOf(firstBuffer);
			secondValue = myBufferPairCondition.getSizeOf(secondBuffer);
			firstBufferDomain.getHeap().add(new Integer(firstValue));
			secondBufferDomain.getHeap().add(new Integer(secondValue));
		    }
	    }
	myBufferBipartiteGraph.load();	
	return myBufferBipartiteGraph;
    }    

    /*-------------------------------------------------------*/

    /**
       Trace les ar&ecirc;tes du graphe biparti &agrave; partir     
       de <CODE>clausalBufferPairCollection</CODE> et
       de <CODE>edgeLessBufferBipartiteGraph</CODE>.
     */
    
    public static void traceBufferBipartiteGraphEdges
	(BufferPairCollection clausalBufferPairCollection, 
	 BufferBipartiteGraph edgeLessBufferBipartiteGraph)
    {
	Vector twoWaysBuffers = clausalBufferPairCollection.getTwoWaysBuffers();
	int nbTwoWaysBuffers = twoWaysBuffers.size();
	Buffer firstBuffer; 
	Buffer secondBuffer;
	int firstValue;
	int secondValue;
	BufferPairExpression myBufferPairExpression;
	BufferPairCondition myBufferPairCondition;
	int nbBufferPairCondition;
	for (int i = 1 ; i < nbTwoWaysBuffers ; i += 2)
	    {
		firstBuffer = (Buffer)twoWaysBuffers.get(i-1); 
		secondBuffer = (Buffer)twoWaysBuffers.get(i); 		
		myBufferPairExpression = clausalBufferPairCollection.
		    getBufferPairExpression(firstBuffer, secondBuffer);
		nbBufferPairCondition = myBufferPairExpression.getNbConditions();
		for(int j = 0 ; j < nbBufferPairCondition ; j++)
		    {
			myBufferPairCondition = 
			    myBufferPairExpression.getBufferPairCondition(j);
			firstValue = myBufferPairCondition.getFirstSize();
			secondValue = myBufferPairCondition.getSecondSize();
			edgeLessBufferBipartiteGraph.addEdge
			    (firstBuffer, secondBuffer, 
			     firstValue, secondValue);
		    }
	    }
    }

    /*-------------------------------------------------------*/

    /**
       Tranforme le graphe biparti 
       <CODE>completeBufferBipartiteGraph</CODE> en
       <CODE>TransportNetwork</CODE>.
     */
    
    public static TransportNetwork transportNetworkOfBufferBipartiteGraph
	(BufferBipartiteGraph completeBufferBipartiteGraph)
    {
	TransportNetwork myTransportNetwork = new TransportNetwork();
	myTransportNetwork.setNbVertices
	    (completeBufferBipartiteGraph.getNbVertices());
	Vertex source = new Vertex(myTransportNetwork, 1);
	Vertex sink = new Vertex(myTransportNetwork, 2);
	myTransportNetwork.setSource(source);
	myTransportNetwork.setSink(sink);
	Vector leftVerticesSet = completeBufferBipartiteGraph.
	    getLeftVerticesSet();
	int nbVertices = leftVerticesSet.size();
	BufferValue myVertex;
	for(int i = 0 ; i < nbVertices ; i++ )    
	    {
		myVertex = (BufferValue)leftVerticesSet.get(i);
		new Arc(source, myVertex, 
			0, myVertex.getWeight());
	    }
	Vector rightVerticesSet = completeBufferBipartiteGraph.
	    getRightVerticesSet();
	nbVertices = rightVerticesSet.size();
	for(int i = 0 ; i < nbVertices ; i++ )    
	    {
		myVertex = (BufferValue)rightVerticesSet.get(i);
		new Arc(myVertex, sink,
			0, myVertex.getWeight());
	    }
	return myTransportNetwork;
    }

    /*-------------------------------------------------------*/

    /**
       R&eacute;cup&egrave;re &agrave; partir de la coupe dans le r&eacute;seau de transport 
       <CODE>cuttedTransportNetwork</CODE>
       les dimensions &agrave; attribuer aux buffers pour ensuite les placer dans les 
       champs <CODE>size</CODE> de ces derniers.
     */
    
    public static void defineBuffersSizes
	(BufferBipartiteGraph cuttedTransportNetwork)
    {
	cuttedTransportNetwork.defineBuffersSizes();
    }

    /*-------------------------------------------------------*/

    /**
       Extrait de <CODE>clausalBufferPairCollection</CODE> 
       les plus petites capacit&eacute;s admissibles 
       pour chaque <CODE>Buffer</CODE> et les consigne 
       dans leur <CODE>BufferBipartiteGraph</CODE>. 
    */
    
    public static void extractMinimums
	(BufferBipartiteGraph myBufferBipartiteGraph,
	 BufferPairCollection clausalBufferPairCollection) 
    {
	Vector oneWayBuffers = 
	    clausalBufferPairCollection.getOneWayBuffers();
	int nbBuffers = Buffer.getNbBuffers();
	nbBuffers = oneWayBuffers.size();	
	BufferPairExpression myBufferPairExpression;
	BufferPairCondition myBufferPairCondition;
	Buffer firstBuffer;
	Buffer secondBuffer;
	int firstValue;
	int secondValue;
	for(int i = 1 ; i < nbBuffers ; i+=2)
	    {
		firstBuffer = (Buffer)oneWayBuffers.get(i-1);
		secondBuffer = (Buffer)oneWayBuffers.get(i);
		myBufferPairExpression = 
		    clausalBufferPairCollection.getBufferPairExpression
		    (firstBuffer, secondBuffer);		
		myBufferPairCondition = 
		    myBufferPairExpression.getBufferPairCondition(0);
		firstValue = myBufferPairCondition.getSizeOf(firstBuffer);
		secondValue = myBufferPairCondition.getSizeOf(secondBuffer);
		myBufferBipartiteGraph.getBufferDomain(firstBuffer).updateMaximin(firstValue);
		myBufferBipartiteGraph.getBufferDomain(secondBuffer).updateMaximin(secondValue);
	    }	
    }


    /*-------------------------------------------------------*/
    
    /**
       Calcule la solution optimale à deux 
       tâches et place les résultats dans 
       les champs <CODE>size</CODE> des buffers 
       concernés.
    */
    
    public static void go(Task task1, Task task2)
    {
	BufferPairCollection bpc = getBufferCollectionVee
	    (task1, task2);
	if (print)
	    {
		System.out.println(bpc);
	    }
	bufferCollectionWedgeOfBufferCollectionVee(bpc);
	if (print)
	    {
		System.out.println("Sous forme clausale : \n" + bpc);
	    }
	BufferBipartiteGraph bbg = bufferBipartiteGraphOfClausalBufferPairCollection
	    (bpc);
	if (print)
	    {
		System.out.println("Extraction des domaines de définition : \n" + bbg);
		System.out.print("Tracé du graphe biparti");
	    }
	traceBufferBipartiteGraphEdges(bpc, bbg);
	if (print)
	    {
		System.out.println(".\n");
		System.out.print("Transformation en réseau de transport");
	    }
	TransportNetwork tn = transportNetworkOfBufferBipartiteGraph(bbg);
	if (print)
	    {
		System.out.println(".\n");
		System.out.print("Flot maximal = ");
		System.out.println(tn.runFlow());	
	    }
	if (print)
	    {
		
		System.out.println("Dimensions des buffers : ");	
	    }
	tn.runFlow();
	defineBuffersSizes(bbg);
    }
    
    /*-------------------------------------------------------*/
    
    /**
       Un exemple d'utilisation de cette classe.
     */

    public static void main(String[] args)
    {
        try
            {
                Loader.run(args[0]);
            }
        catch(Loader.ScriptErrorException e)
            {
                System.out.println(e);
            }
        catch(Exception e)
            {
                System.out.println(e);
            }
	print = true;
	go(Task.get(0), Task.get(1));
    }    
    
}