public class Merkelapp {
  
  private static int min(int a, int b) {
	 return (b > a)? a : b;
  }

  //Metoden utfoerer flytmaximering vha. merkelappmetoden.
  //Alle kommentarer med tall i parentes, er henvisninger til foileren som ble
  //vist i forelesningen.
  public void flytmax( Graf g, int start, int slutt) {
	 Kant tmp = null;
	 //Setter opp startflyt (1):
	 for(int i = 1; i <= g.antallKanter(); i++) {
		tmp = g.hentKant(i);
		tmp.settFlyt(0);
	 }
	 //Ytterste loekke (1-6):
	 while (true) {
		Node nodeN = g.hentNode(start);
		//Utfoerer (2)
		nodeN.marker(false, start, Integer.MAX_VALUE);
		NodeListe listeI = new NodeListe();
		listeI.leggTilNode(start);
		int n = start;
		//Indre loekke (2-3):
		do {
		  Kant testK = null;
		  Node nodeJ = null;
		  int nodeTest;
		  //Gaar igjennom alle nodene j (2)
		  for(int j = 1; j<= g.antallNoder(); j++) {
			 testK = g.hentFraTilKant(n, j);
			 nodeJ = g.hentNode(j);
			 //Dersom det er en kant fra n til j,... (2.1)
			 if (testK != null && !nodeJ.markert() && (testK.hentFlyt() < testK.hentKapasitet())) {
				nodeJ.marker(true, n, min(nodeN.hentMerkelappDelta(), (testK.hentKapasitet() - testK.hentFlyt())));
				listeI.leggTilNode( j);
			 }
			 testK = g.hentFraTilKant(j, n);
			 //Dersom det er en kant fra j til n,... (2.2)
			 if (testK != null && !nodeJ.markert() && (testK.hentFlyt() > 0)) {
				nodeJ.marker(false, n, min(nodeN.hentMerkelappDelta(), testK.hentFlyt()));
				listeI.leggTilNode( j);
			 }
		  }
		  nodeTest = listeI.hentNeste();
		  nodeN = g.hentNode(nodeTest);
		  if (nodeN != null && n != slutt)
			 n = nodeTest;

		//Sjekker for ubehandlede noder i I, samt om vi har kommet frem til slutten (3)
		} while (nodeN != null && n != slutt); 

		//Har vi funnet en optimal flyt? (4)
		if (n != slutt) //Vi har funnet den optimale flyten: Avslutter "while(true)"!
		  break;

		//Starter retrace for aa finne stroemforoekende vei/kjede(5):
		int retrace = slutt;
		int flytoekning = g.hentNode(slutt).hentMerkelappDelta();
		do {
		  Node retraceNode = g.hentNode( retrace);
		  Kant retraceKant = null;
		  if (retraceNode.hentMerkelappRetning()) { //Vi har en i->j - type (inn=true)
			 retraceKant = g.hentFraTilKant( retraceNode.hentMerkelappNode(), retrace);
			 retraceKant.settFlyt( retraceKant.hentFlyt() + flytoekning);
		  }
		  else { //Vi har en i<-j - type (inn=false)
			 retraceKant = g.hentFraTilKant( retrace, retraceNode.hentMerkelappNode());
			 retraceKant.settFlyt( retraceKant.hentFlyt() - flytoekning);		
		  }
		  retrace = retraceNode.hentMerkelappNode();
		} while (retrace != start);
		
		//Fjaerner merkelappene (6)
		g.fjaernMerkelapper();
	 }
  }
}


/* Klassene under er ikke ferdige, men kode for disse er ikke
   så relevant for å illustrere merkelapp-metoden.
   Det burde ikke være så alt for vanskelig å fylle inn
   kode der selv */
class Graf {
  public int antallNoder() {return 0;}
  public int antallKanter() {return 0;}
  public Node hentNode(int nr) {return null;}
  public Kant hentKant(int nr) {return null;}
  public Kant hentFraTilKant(int fraNode, int tilNode) {return null;}
  public void fjaernMerkelapper() {}
}

class NodeListe {
  public void leggTilNode( int n) {}
  public int hentNeste() {return 0;}
}

class Node {
  public boolean markert() {return false;}
  public void unmark() {}
  public void marker(boolean inn, int node, int delta ) {}
  public boolean hentMerkelappRetning() {return false;}
  public int hentMerkelappNode() {return 0;}
  public int hentMerkelappDelta() {return 0;}
}

class Kant {
  public int hentKapasitet() {return 0;}
  public int hentFlyt() {return 0;}
  public void settFlyt( int flyt) {}
}