package tw.edu.ncnu.im.cnclab.Algor;

import tw.edu.ncnu.im.cnclab.UI.*;
import tw.edu.ncnu.im.cnclab.DataStru.*;
import tw.edu.ncnu.im.cnclab.Tools.*;
import tw.edu.ncnu.im.cnclab.JGAP.*;
import tw.edu.ncnu.im.cnclab.JGAP.UI.*;
import java.util.*;
import java.awt.*;


/**
 *  The <code> MF_FordFulkerson </code> class is used to find maximum flow using FordFulkerson method.
 *  <p>
 *  Flow edge can be identified as edges with state = <code> FLOW_EDGE </code>
 *
 *  @version 0.4  Jul 8, 1999
 *  @author <A HREF=http://cnclab.im.ncnu.edu.tw/person/definite/> Ding-Yi Chen </A>
 */
public class MF_FordFulkerson extends Algorithm {
   protected int verts;
   private int counter=0;

   /**
    *  Indicate the edges does not containes non-zero flow.
    */
   public static final Color OTHER=Edge.untouchedColor;

   /**
    *  Indicate the edges containes non-zero flow.
    */
   public static final Color FLOW_EDGE=Edge.normalColor;
   /**
    *  The residual graph of <code> graph </code>
    */
   private Graph resG;

   /**
    * Constructor of algorithm Ford-Fulkerson.
    */
   public MF_FordFulkerson() {
      legendPrompt=new String[]{"Other","Flow"};
      legendColor=new Color[]{OTHER,FLOW_EDGE};
      resG=new Graph();
   }

  /**
   * Set arguments from the argument list.
   * <p>
   * Valid args: <code> null </code>, <code> Object[]{Integer(int <I>sourceNode</I>),Integer(int <I>sinkNode</I>)} </code>
   * @param args        The list of arguments.
   * @exception IllegalArgumentException Illegal argument defined.
   */
   protected void setArg(Object args[]) throws IllegalArgumentException{
      Enumeration enum=graph.verticesElements();
      Vertex v=(Vertex) enum.nextElement();
      startNode=v.getID();
      if (!enum.hasMoreElements()){
         throw new InvalidGraphTypeException("Graph must contain more than 2 vertices.");
      }
      v=(Vertex) enum.nextElement();
      endNode=v.getID();

      if (args==null)
         return;
      if (args.length!=2)
         throw new IllegalArgumentException("Wrong number of arguments");
      switch(args.length){
         case 2:
            try{
               startNode=((Integer) args[0]).intValue();
            }catch(Exception e){
               throw new IllegalArgumentException("Wrong format of arguments[0]");
            }
            try{
               endNode=((Integer) args[1]).intValue();
            }catch(Exception e){
               throw new IllegalArgumentException("Wrong format of arguments[1]");
            }
            break;

      }
   }

   /**
    *  Preferred dialog: Ask2VertexDialog.
    *  @param graph The Graph.
    *  @param fr    The parent Frame.
    *  @return the preferred dialog.
    */
   public GenericDialog getPreferredDialog(Graph graph,Frame fr){
      return new Ask2VertexDialog(graph,fr,"Vertex Dialog","Input the source vertex and sink vertex?",true);
   }


   private boolean augmentingPathExist(Graph graph){
      counter++;
      resG=(Graph) graph.clone();
      ResidualGraph rg=new ResidualGraph();
      rg.execute(resG,new Object[]{new Integer(startNode),new Integer(endNode)});
/*
      ShowGraphWindow showGraphWindow=new ShowGraphWindow(resG,resG,legendPrompt,legendColor);
      showGraphWindow.setTitle("Residual ["+counter +"] result");
      showGraphWindow.setVisible(true);
*/
      BFS bfs=new BFS();
      bfs.execute(resG,new Object[]{new Integer(startNode),new Boolean(false)});
      if (resG.getPredecessorNode(endNode)==resG.NUL){
         return false;
      }
      return true;

   }

   private void addAugmenting(Graph graph){
      double cf=Double.POSITIVE_INFINITY;
      double d;
      int u,v;
      v=endNode;
      for(u=resG.getPredecessorNode(v);u!=Graph.NUL;
       u=resG.getPredecessorNode(v)){
         d=graph.getEdge(u,v).getWeight()-graph.getEdge(u,v).getFlow();
         if (cf>d)
            cf=d;
         v=u;
      }

      v=endNode;
      for(u=resG.getPredecessorNode(v);u!=Graph.NUL;
       u=resG.getPredecessorNode(v)){
         graph.getEdge(u,v).setFlow(graph.getEdge(u,v).getFlow()+cf);
         v=u;
      }
   }

   private void colorFlow(Graph graph){
      graph.reset();
      for(Enumeration e=graph.allEdgesElements();e.hasMoreElements();){
         Edge edge=(Edge) e.nextElement();
         if (edge.getFlow()>0.0){
            edge.setColor(FLOW_EDGE);
         } else{
            edge.setColor(OTHER);
         }

      }
      graph.getVertex(startNode).setColor(Color.green);
      graph.getVertex(endNode).setColor(Color.yellow);
   }

   private double flowOut(Graph graph,int node){
      Edge edge;
      double flow=0.0;
      for(Enumeration e=graph.edgesElements(node);e.hasMoreElements();){
         edge=(Edge) e.nextElement();
         flow+=edge.getFlow();
      }
      return flow;
   }


   /**
    * Implementation of this algorithm.
    * @return <code> Double(double <I> flow_of_the_graph</I>) </code>
    */
   protected Object algorImpl() {

      Vertex v;
      Edge edge;
      int from;
      int to;
      int node;
      int counter=0;
      double flow;

      graph.setShowFlow(true);
      for(Enumeration e=graph.allEdgesElements();e.hasMoreElements();){
         edge=(Edge) e.nextElement();
         edge.setFlow(0.0);
      }

      while(augmentingPathExist(graph)){
         addAugmenting(graph);
      }
      colorFlow(graph);
      flow=flowOut(graph,startNode);
      outputMessage="Maximum flow: "+StringTool.doubleToString(flow,2)+"  ";
      return new Double(flow);
   }

}