TransportNetwork.java

package buffalo.transportNetwork;

import java.util.Vector;
import buffalo.util.Fifo;
import java.io.FileOutputStream;

/**
   Classe de modélisation d'un réseau de Transport, c'est-à-dire 
   tout graphe connexe orienté comportant un sommet-source, un sommet-puit, des 
   arcs valués ou de capacité infinie. Cette classe contient aussi une 
   méthode permettant de déterminer le flot max et la coupe min.
   Cet implantation ne fonctionne pas si il n'existe pas de coupe de capacité 
   finie.
 */

public class TransportNetwork
{
    /**
       Sommet source du réseau de transport
     */
    
    private FlowableVertex source;
    
    /**
       Sommet puits du réseau de transport
     */

    private FlowableVertex sink;

    /**
       Nombre de sommets
     */

    private int nbVertices = 0;
    
    /**
       Nombre d'arêtes
     */

    private int nbArcs = 0;
    
    /**
       Valeur du flot.
     */

    private double flowValue = 0.0;

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

    /**
       Pour réussir à mettre en place les références 
       croisées, on peut créer un réseau sans lui passer de 
       source et de puits en paramètre. Il faut par contre si on veut 
       faire tourner un algorithme de flot invoquer préalablement les 
       méthodes setSource() et setSink().
     */

    public TransportNetwork()
    {
	nbVertices = -1;
    }
    
    /*--------------------------------------------------*/

    /**
       Retourne la source du réseau de transport
     */

    public FlowableVertex getSource()
    {
	return source;
    }
    
    /*--------------------------------------------------*/

    /**
       Retourne le puits du réseau de transport
     */

    public FlowableVertex getSink()
    {
	return sink;
    } 

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

    /**
       Retourne la source du réseau de transport
     */

    public void setSource(FlowableVertex source)
    {
	this.source = source;
    }
    
    /*--------------------------------------------------*/

    /**
       Retourne le puits du réseau de transport
     */

    public void setSink(FlowableVertex sink)
    {
	this.sink = sink;
    }   

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

    /**
       Pour déterminer le nombre de sommets 
       du réseau;, cet indicateur intervient dans 
       la condition d'arrêt de l'algorithme et 
       doit par conséquent être exact.
     */

    public void setNbVertices(int nbVertices)
    {
	this.nbVertices = nbVertices;
    }   

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

    /**
       Pour déterminer le nombre d'arêtes du 
       réseau
     */

    public void setNbArcs(int nbArcs)
    {
	this.nbArcs = nbArcs;
    }   

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

    /**
       Retourne le nombre de sommets du réseau de transport.
     */

    public int getNbVertices()
    {
	return nbVertices;
    }   

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

    /**
       Retourne une représentation sous forme chaîne 
       de caractères du réseau de transport.
     */

    public String toString()
    {
	String result = "Le réseau comporte " + nbVertices + " sommets.";
	result += "\n La source est " + source;
	result += "\n et le puits est " + sink;	
	return result;
    } 

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

    /**
       Calcule le flot maximal.
     */

    public double runFlow()
    {
	flowValue = 0.0;				
	prepareFlow();
	FlowableVertex myVertex = getSource();
	if (myVertex.getMark()==null)
	    {
		System.out.println("Il n'existe aucun chemin de la " + 
				   "source au puits.");
		return 0.0;
	    }	
	myVertex.getMark().setFather(null, null);
	while (( getSource().getMark().getDistance() != -1 )&&
	       ( getSource().getMark().getDistance() < nbVertices))
	    {
		myVertex = improveFlow(myVertex);
		if (myVertex == null)
		    {
			myVertex = getSource();
		    }
		else
		    {
			backtrack(myVertex);
			if(myVertex!=getSource())
			    {
				myVertex = myVertex.getMark().getFather();
			    }
		    }
	    }
	defineCut();
	return flowValue;
    } 

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

    /**
       Pr&eacute;pare le graphe en effectuant un parcours en largeur.
     */

    private void prepareFlow()
    {
	Fifo myFifo = new Fifo(this.getNbVertices());
	myFifo.add(this.getSink());
	FlowableVertex oldVertex = (FlowableVertex)myFifo.get();
	sink.acceptMark(new FlowMark(0));
	FlowableVertex newVertex = null;
	Vector candidates;
	FlowableArc candidate;
	FlowMark myMark;
	while(oldVertex != null) 
	    {	
		candidates = oldVertex.getInArcs();
		if (candidates.size()!=0)
		    {
			for (int i = 0 ; i < candidates.size(); i++)
			    {
				candidate = (FlowableArc)candidates.get(i); 
				newVertex = candidate.getInVertex();
				if ((candidate.getConformResidualValue()!=0.0)&&
				    (newVertex.getMark()==null))
				    {
					myFifo.add(newVertex);					
					myMark = 
					    new FlowMark
					    (oldVertex.getMark().getDistance() + 1);
					newVertex.acceptMark(myMark);
				    }
			    }
		    }
		candidates = oldVertex.getOutArcs();
		if (candidates.size()!=0)
		    {
			for (int i = 0 ; i < candidates.size(); i++)
			    {
				candidate = (FlowableArc)candidates.get(i); 
				newVertex = candidate.getOutVertex();
				if ((candidate.getUnconformResidualValue()!=0.0)&&
				    (newVertex.getMark()==null))
				    {
					myFifo.add(newVertex);					
					myMark = new FlowMark
					    (oldVertex.getMark().getDistance() + 1);
					newVertex.acceptMark(myMark);
				    }
			    }
		    }
		myFifo.extract();
		oldVertex = (FlowableVertex)myFifo.get();
	    }
    } 

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

    /**
       Marque tous les sommets appartenant &agrave; la coupe.
     */

    private void defineCut()
    {
	Fifo myFifo = new Fifo(this.getNbVertices());
	myFifo.add(this.getSource());
	FlowableVertex oldVertex = (FlowableVertex)myFifo.get();
	FlowableVertex newVertex = null;
	Vector candidates;
	FlowableArc candidate;
	FlowMark myMark;
	while(oldVertex != null) 
	    {	
		if (!oldVertex.isInTheCut())
		    {
			oldVertex.addToTheCut();
			candidates = oldVertex.getOutArcs();
			if (candidates.size()!=0)
			    {
				for (int i = 0 ; i < candidates.size(); i++)
				    {
					candidate = (FlowableArc)candidates.get(i); 
					newVertex = candidate.getOutVertex();
					if (candidate.getConformResidualValue()!=0.0)
					    {
						myFifo.add(newVertex);					
					    }
				    }
			    }
			candidates = oldVertex.getInArcs();
			if (candidates.size()!=0)
			    {
				for (int i = 0 ; i < candidates.size(); i++)
				    {
					candidate = (FlowableArc)candidates.get(i); 
					newVertex = candidate.getInVertex();
					if (candidate.getUnconformResidualValue()!=0.0)
					    {
						myFifo.add(newVertex);					
					    }
				    }
			    }
		    }
		myFifo.extract();
		oldVertex = (FlowableVertex)myFifo.get();
	    }
    } 

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

    /**
       Recherche un plus court chemin am&eacute;liorant.
     */

    private FlowableVertex improveFlow(FlowableVertex startVertex)
    {
	FlowableVertex oldVertex = startVertex;
	FlowableVertex newVertex = null;
	FlowableArc arcBetweenThem;
	while(oldVertex!=getSink())
	    {
		arcBetweenThem = findCloserArc(oldVertex);
		if (arcBetweenThem==null)
		    {
			return oldVertex;
		    }
		else
		    {
			if (arcBetweenThem.getInVertex()==oldVertex)
			    {
				newVertex = arcBetweenThem.getOutVertex();
			    }
		else
			    {
				newVertex = arcBetweenThem.getInVertex();
			    }
		    }
		if (oldVertex.getMark().getDistance() == 
		    newVertex.getMark().getDistance()+1)
		    {
			newVertex.getMark().setFather(oldVertex, 
						      arcBetweenThem);
			oldVertex = newVertex;
		    }
		else
		    {			
			return oldVertex;
		    }
	    }
	augmentFlow();
	return null;
    }
    
    /*---------------------------------------------------*/
    
    /**
       Augmentation du flot.
     */
    
    private void augmentFlow()
    {
	double flowIncrement = getSink().getMark().getMaxFlowValue();
	if (flowIncrement == -1)
	    {
		System.out.println("Il n'existe pas de coupe de taille " + 
				   "finie, le flot est infini.");
		System.exit(0);
	    }
	flowValue += flowIncrement;	
	FlowableVertex myVertex = sink;
	FlowableArc myArc = null;
	FlowMark myMark;
	boolean isConform;
	int i = 0;
	while (myVertex != source)
	    {
		isConform = myVertex.getMark().isConform();
		myMark = myVertex.getMark();
		myArc = myMark.getArcBetweenFatherAndMe();
		if(isConform)
		    {
			myArc.increaseConformFlow(flowIncrement);		    
		    }
		else
		    {
			myArc.increaseUnconformFlow(flowIncrement);		    
		    }		 
		myVertex = myVertex.getMark().getFather();
	    }
    }
	
    /*---------------------------------------------------*/

    /**
       Cette m&eacute;thode recherche parmi toutes les ar&ecirc;tes non 
       satur&eacute;es adjcacentes &agrave; 
       myVertex celle dont la distance au puits st minimale.
     */

    private void backtrack(FlowableVertex myVertex)
    {
	FlowableArc myArc = findCloserArc(myVertex);
	if (myArc==null)
	    {
		myVertex.getMark().setSon(null);
	    }
	else
	    {
		if (myArc.getInVertex()==myVertex)
		    {
			myVertex.getMark().setSon(myArc.getOutVertex());
		    }
		else
		    {
			myVertex.getMark().setSon(myArc.getInVertex());
		    }
	    }
    }
    
    /*---------------------------------------------------*/
    
    /**
      Renvoie l'ar&ecirc;te la plus proche du puits parmi les 
      ar&ecirc;tes adjacentes &agrave; myVertex.
     */
    
    FlowableArc findCloserArc(FlowableVertex myVertex)
    {
	Vector inArcs =  myVertex.getInArcs();
	Vector outArcs = myVertex.getOutArcs();
	FlowableArc myArc = null;
	FlowableArc inShorter = null;    
	FlowableArc outShorter = null;
	int i = 0;
	if (inArcs != null)
	    {
		while ((inShorter == null)&&(i<inArcs.size()))
		    {
			myArc = (FlowableArc)inArcs.get(i++);
			if((myArc.getUnconformResidualValue()!=0.0)		   
			   &&(myArc.getInVertex().getMark().getDistance()!=-1))
			    {
				inShorter = myArc;
			    }
		    }
		for (; i < inArcs.size();  i++)	    
		    {
			myArc = (FlowableArc)inArcs.get(i);
			if ((myArc.getInVertex().getMark().getDistance() < 
			     inShorter.getInVertex().getMark().getDistance())
			    &&(myArc.getUnconformResidualValue()!=0.0)
			    &&(myArc.getInVertex().getMark().getDistance()!=-1))
			    {
				inShorter = myArc;
			    }
		    }
		i = 0;
	    }
	if (outArcs != null)
	    {
		while ((outShorter == null)&&(i<outArcs.size()))
		    {
			myArc = (FlowableArc)outArcs.get(i++);
			if((myArc.getConformResidualValue()!=0.0)
			   &&(myArc.getOutVertex().getMark().getDistance()!=-1))
			    {
				outShorter = myArc;
			    }
		    }
		for (; i < outArcs.size();  i++)	    
		    {
			myArc = (FlowableArc)outArcs.get(i);
			if ((myArc.getOutVertex().getMark().getDistance() < 
			     outShorter.getOutVertex().getMark().getDistance())
			    &&(myArc.getConformResidualValue()!=0.0)
			    &&(myArc.getOutVertex().getMark().getDistance()!=-1))
			    {
				outShorter = myArc;
			    }
		    }
	    }
	if ((inShorter==null)&&(outShorter==null))
	    {
		myArc = null;
	    }
	if ((inShorter==null)&&(outShorter!=null))
	    {	
		myArc = outShorter;
	    }	    	
	if ((inShorter!=null)&&(outShorter==null))
	    {
		myArc = inShorter;
	    }	    
	if ((inShorter!=null)&&(outShorter!=null))
	    {
		if (inShorter.getInVertex().getMark().getDistance() < 
		    outShorter.getOutVertex().getMark().getDistance())
		    {
			myArc = inShorter;
		    }
		else
		    {
			myArc = outShorter;
		    }
	    }	
	return myArc;
    }

}