package dap2.blatt3;

import java.util.ArrayList;
import java.util.List;

public class Tiefensuche {

	private static List<Kante> treeKanten = new ArrayList<Kante>();

	private static List<Kante> forwardKanten = new ArrayList<Kante>();

	private static List<Kante> crossKanten = new ArrayList<Kante>();

	private static List<Kante> backKanten = new ArrayList<Kante>();

	private static int besuchsZaehler = 0;

	public static boolean hatKreis(Knoten[] knoten) {
		for (int i = 0; i < knoten.length; i++) {
			if (knoten[i].getBesucht() == 0) {
				tiefensuche(knoten[i]);
			}
		}
		return backKanten.size() != 0;
	}

	public static void tiefensuche(Knoten knoten) {
		System.out.println("Tiefensuche.tiefensuche(" + knoten.getName() + ")");
		knoten.setAlpha(1);
		knoten.setBesucht(besuchsZaehler);
		Knoten[] nachfolger = knoten.getNachfolger();
		if (nachfolger != null)
			for (int i = 0; i < nachfolger.length; i++) {
				if (nachfolger[i].getBesucht() == 0) {
					System.out.println("TREE("
							+ neueKante(treeKanten, knoten, nachfolger[i])
							+ ")");
					besuchsZaehler++;
					tiefensuche(nachfolger[i]);
				} else if (nachfolger[i].getBesucht() > knoten.getBesucht()) {
					System.out.println("FORWARD("
							+ neueKante(forwardKanten, knoten, nachfolger[i])
							+ ")");
				} else if (nachfolger[i].getAlpha() == 1) {
					System.out.println("BACKWARD("
							+ neueKante(backKanten, knoten, nachfolger[i])
							+ ")");
				} else if (nachfolger[i].getAlpha() == 2) {
					System.out.println("CROSS("
							+ neueKante(crossKanten, knoten, nachfolger[i])
							+ ")");
				}
			}
		knoten.setAlpha(2);
	}

	public static Kante neueKante(List<Kante> typ, Knoten v, Knoten w) {
		Kante k = new Kante(v.getName(), w.getName());
		typ.add(k);
		return k;
	}

	public static void main(String[] args) {
		System.out.println(hatKreis(getAdjazenzlistenGraph()));
	}

	public static Knoten[] getAdjazenzlistenGraph() {

		Knoten a = new Knoten("A");
		Knoten b = new Knoten("B");
		Knoten c = new Knoten("C");
		Knoten d = new Knoten("D");
		Knoten e = new Knoten("E");
		Knoten f = new Knoten("F");
		Knoten g = new Knoten("G");
		Knoten h = new Knoten("H");

		a.setNachfolger(new Knoten[] { b, c, h });
		b.setNachfolger(new Knoten[] { e });
		c.setNachfolger(new Knoten[] { d });
		d.setNachfolger(new Knoten[] { e, g, h });
		e.setNachfolger(new Knoten[] { f });
		f.setNachfolger(new Knoten[] { b });

		Knoten[] knoten = new Knoten[] { a, b, c, d, e, f, g, h };

		return knoten;
	}
}