/* @author Søren Munk (u001614) & Mads Peter Lindberg (u001990)
 * @version 1 d. 7/5-2001
 */

import java.io.*;
import java.lang.*;
import java.util.*;
import java.awt.*;
public class MaxParring {
    private static int m = 0;
    private static int n1 = 0;
    private static int n2 = 0;
    private static Node[] v1;
    private static Node[] v2;
    private static int p = 0;
    private static int progress = 0;
    private static Stack farvedKnuder = new Stack();//oversigt over farvede knuder
    private static Node denSorteKnude;               
    
    /** main-metoden finder maximal parring for grafen specificeret i args[0]
     */
    public static void main(String args[]) {
	vis("");
	vis("-----------------------------");
	long tid = System.currentTimeMillis();
	vis("Henter filen fra disk");
	try {
	    if (args.length > 0) { getFile(args[0]); }
	    else {
		vis("Angiv filnavn, java <JavaKlassefil> <filnavn> <Udskrift>");
		vis("F.eks: java MaxParring mintest.gph 0");
		p = -1;
		vis("-----------------------------");
	    }
	}
	catch (IOException e) {
	    vis("Filen blev ikke fundet <"+args[0]+">");
	    vis("-----------------------------");
	    p = -1;
	}
	finally {
	    if (p >= 0) {
		vis("-----------------------------");
		vis("Finder maximal parring");
		
		findSkifteVej();
		while (findesSkifteVej()) {
		    //if (progress%2 == 0) {
		    //System.out.print((progress)+" gennemløb\r");
		    //}
		    opdaterGraf();
		    farvHvid();
		    findSkifteVej();
		}

		if (args.length > 1 ){
		    if (args[1].equals("0")) {printPairs(false);}
		}
		else printPairs(true);
		       
		vis("-----------------------------");
		vis("V1: "+n1 +"; V2: "+n2);
		vis("Antal kanter: "+m);
		vis("-----------------------------");
		vis("Størst mulig parringer for "+args[0]+" = "+p);
		vis("Gennemløb grafen "+progress+" gange på "+
		    "["+(System.currentTimeMillis()-tid)+ " milisekunder]");
	    }
	}
    }
    
    /**getFile henter en fil indeholdende en to-delt graf 
     * @param fileName filen der skal hentes ind 
     */ 
    public static void getFile(String fileName) throws IOException {
	BufferedReader infile = new BufferedReader( new FileReader(fileName) );
	vis("Indlæser fil <"+fileName+">");
	//læser fra filen n1,n2,m 
	n1 = new Integer(infile.readLine()).intValue();
	n2 = new Integer(infile.readLine()).intValue();
	m  = new Integer(infile.readLine()).intValue();
	v1 = new Node[n1];
	v2 = new Node[n2];
	
	for (int j=0; j<n1; j++)  { v1[j] = new Node(j+"",true); }
	for (int k=0; k<n2; k++)  { v2[k] = new Node(k+"",false); }
	//henter tallene ud
	for (int i=0; i<m; i++) {
	    if (i%5 == 0) {
		System.out.print(((i*100)/m)+"%\r");
	    }
	    StringTokenizer t = new StringTokenizer(infile.readLine()," ");
	    if (t.countTokens() == 2) {
		//laver kanterne
		new Edge(v1[new Integer(t.nextToken()).intValue()],
			 v2[new Integer(t.nextToken()).intValue()]);
	    }
	}
	vis("Færdig med at indlæse fil");
	vis("< "+m+" kanter oprettet>");
    }

    /**vis udskriver tekst til consolen
     * @param besked teksten der skal udskrives
     */
    public static void vis(String besked) { System.out.println(besked); }    

    /**findesSkifteVej undesøger om der er en skiftevej 
     * @return sandhedsværdi om der findes en skiftevej
     */
    public static boolean findesSkifteVej() { return !(denSorteKnude == null); }

    /**opdaterGraf finder vej til initialknude 
     */ 
    public static void opdaterGraf() { findKnude(denSorteKnude); }
    
    /**findKnude finder vej til initialknude rekursivt
     * @param knude en knude amen
     */
    public static void findKnude(Node knude) {
	if (!((knude.getColor() == 2) && knude.memberv1)) {
  	    //den følger vejen tilbage til initialknuden
	    findKnude(knude.visitedFrom.from);
	    //vender pilene på kanterne
	    knude.visitedFrom.skift();
	}
    }

    /**farvhvid farver alle farvede knuder hvide
     */ 
    public static void farvHvid() {
	denSorteKnude = null;	
        //sålænge der er farvede knuder
	while (!farvedKnuder.empty()) {
	    //kantens ender farves hvide
	    Edge tmpEdge = (Edge) farvedKnuder.pop();
	    tmpEdge.to.setColor(0);
	    tmpEdge.from.setColor(0);
	}
    }

    /**findSkifteVej finder alle initialknuder og farver ud fra dem
     */
    public static void findSkifteVej() {
	for (int i=0; i<n1; i++) {
	    if (v1[i].inDegree()==0) {
		v1[i].setColor(2);
		farvGraf(v1[i]);
		if (!(denSorteKnude == null)) {break;}
	    }
	}
    }
    
    /**farvGraf farver grafen
     * @param knude knuden der skal farves
     */ 
    public static void farvGraf(Node knude) {
	progress++;
	//alle knuder fra udgående kanter farves
	Enumeration j = knude.outEdges();
	while (j.hasMoreElements()) {
	    Edge kant = (Edge) j.nextElement();
	    Node tilKnude = kant.to;
	    
	    //farver iflg transitionssystemet
	    if (tilKnude.getColor() == 0) {
		if ( tilKnude.memberv1 ) {
		    tilKnude.setColor(1);
		    farvedKnuder.push(kant);
		    farvGraf(tilKnude);
		}
		else if ( !tilKnude.memberv1 && tilKnude.outDegree() > 0 ) {
		    tilKnude.setColor(1);
		    farvedKnuder.push(kant);
		    farvGraf(tilKnude);
		}
		else {
		    tilKnude.setColor(2);
		    farvedKnuder.push(kant);
		    denSorteKnude = tilKnude;
		}
		tilKnude.setVisitor(kant);
	    }
	}
    }
    
    /**printPairs udskriver alle parringerne
     */ 
    public static void printPairs(boolean udskriv) {
	vis("Færdig...           ");
	for (int i=0; i<v1.length; i++)
	    for (Enumeration e = v1[i].in.elements(); e.hasMoreElements();) {
		Edge edge = (Edge)e.nextElement();
		if (udskriv) { vis(edge.toString()); }
		p++;
	    }
    }
}