/**

  Einfache Implementierung eines gerichteten Graphen.
  
  Der Graph wird intern durch eine boolsche Adjazenzmatrix repraesentiert

  Mittels des Algorithmus von S. Warshall (1963) wird festgestellt, ob der Graph
  zusammenhaengend ist oder nicht.
  
*/

public class Graph
{

  /**
   * Die Adjazenzmatrix des Graphen
   */

  private boolean[][] adjazenzMatrix = null;

  /**
   * Die Kantenzahl soll extra mitgefuehrt werden, damit nicht bei jeder
   * Abfrage neu gezaehlt werden muss.
   */

  private int kantenZahl = 0;

  /**
   * Konstruktor
   *
   * Erstellt einen neuen Graphen mit der vorgegebenen Knotenzahl
   * @param knotenZahl
   */

  public Graph(int knotenZahl)
  {

    if (knotenZahl < 0)
      throw new IllegalArgumentException ("Graph mit negativer Knotenanzahl kann nicht erstellt werden.");

    /* Adjazenzmatrix anlegen */
    this.adjazenzMatrix = new boolean[knotenZahl][knotenZahl];

  }

  /**
   * Gibt die Anzahl der vorhandenen Kanten zurueck.
   * @return Anzahl der Kanten
   */

  public int getKantenZahl ()
  {

    return this.kantenZahl;

  } // getKantenZahl ()

  /**
   * Gibt die Anzahl der Knoten zurueck.
   * @return Anzahl der Knoten
   */
  public int getKnotenZahl ()
  {

    return this.adjazenzMatrix.length;

  } // getKnotenZahl ()

  /**
   * Fuegt eine Kante von quellKnoten zu zielKnoten ein. Wenn einer der beiden
   * Knoten nicht existiert oder die Kante bereits vorhanden ist, erfolgt keine
   * Aktion.
   *
   * @param quellKnoten Von welchem Knoten die Kante ausgeht.
   * @param zielKnoten Zu welchem Knoten die Kante geht.
   */

  public void kanteEinfuegen(int quellKnoten, int zielKnoten)
  {

    if (quellKnoten >= this.adjazenzMatrix.length || zielKnoten >= this.adjazenzMatrix.length)
      return;

    if (this.adjazenzMatrix[quellKnoten][zielKnoten] == false)
    {
      this.adjazenzMatrix[quellKnoten][zielKnoten] = true;
      this.kantenZahl++;
    }

  } // kanteEinfuegen ()

  /**
   * Entfernt eine durch Quell- und Zielknoten spezifizierte Kante.
   * @param quellKnoten Von welchem Knoten die Kante ausgeht.
   * @param zielKnoten Zu welchem Knoten die Kante geht.
   */
  public void kanteEntfernen (int quellKnoten, int zielKnoten)
  {

    if (quellKnoten > this.adjazenzMatrix.length || zielKnoten > this.adjazenzMatrix.length)
      return;

    if (this.adjazenzMatrix[quellKnoten][zielKnoten] == true)
    {
      this.adjazenzMatrix[quellKnoten][zielKnoten] = false;
      this.kantenZahl--;
    }

  } // kanteEntfernen ()

  /**
   * Fuegt einen weiteren Knoten ein, indem die Adjazenzmatrix neu (und vergroessert) angelegt wird.
   */

  public void knotenEinfuegen ()
  {
  
    boolean[][] neuMatrix = new boolean[this.adjazenzMatrix.length+1][this.adjazenzMatrix[0].length+1];

    for (int i = 0; i < this.adjazenzMatrix.length; i++)
      for (int j = 0; j < this.adjazenzMatrix[i].length; j++)
        neuMatrix[i][j] = this.adjazenzMatrix[i][j];

    this.adjazenzMatrix = neuMatrix;

  } // knotenEinfuegen ()

  /**
   * Entfernt einen gegebenen Knoten samt allen zugehoerigen Kanten.
   * @param knoten Der Knoten, der entfernt werden soll.
   */
  public void knotenEntfernen (int knoten)
  {

    this.adjazenzMatrix = loescheKnoten (this.adjazenzMatrix, knoten);

  } // knotenEntfernen ()

  /**
   * Gibt true zurueck, wenn der Graph zusammenhaengend ist. Zusammenhaengend
   * ist ein gerichteter Graph, wenn es einen Knoten gibt, von dem aus alle
   * anderen erreichbar sind.
   *
   * @return ob der Graph zusammenhaengend ist (boolean)
   */

  public boolean isZusammenhaengend ()
  {
    /* kopiere Adjazenzmatrix, um Warshall-Algorithmus starten zu koennen, */
    /* ohne die Adjazenzmatrix zu beschaedigen */
    boolean[][] transHuelle = kopiereMatrix (this.adjazenzMatrix);

    /* Algorithmus faengt damit an, dass er die Diagonaleintraege auf 1 setzt (trivial) */
    for (int i = 0; i < transHuelle.length; i++)
      transHuelle[i][i] = true;

    /* hier der eigentliche Algorithmus */
    for (int j = 0; j < transHuelle.length; j++)
      for (int i = 0; i < transHuelle[j].length; i++)
        if (transHuelle[i][j])
          for (int k = 0; k < transHuelle.length; k++)
            if (transHuelle[j][k])
              transHuelle[i][k] = true;

    /* stelle fest, ob es nun eine Zeile mit lauter Einsen gibt; */
    /* falls ja => gib true zurueck */

    for (int i = 0 ; i < transHuelle.length ; i++)
    {

      boolean temp = true;
      for (int j = 0 ; j < transHuelle[i].length ; j++)
        if (!transHuelle[i][j])
          temp = false;

      if (temp)
        return true;

    }

    return false; /* else */

  } // isZusammenhaengend ()

  /**
   * Gibt zurueck, ob der Graph zyklisch ist.
   * @return
   */
  public boolean isZyklisch ()
  {

    /* fuehre an einer Kopie der Adjazenzmatrix die topologische Sortierung durch */
    boolean[][] tempMatrix = kopiereMatrix (this.adjazenzMatrix);

    while (tempMatrix.length > 0)
    {
      int knoten = getIndegZeroKnoten (tempMatrix);
      if (knoten < 0)
        break;
      tempMatrix = loescheKnoten (tempMatrix, knoten);
    }

    /* falls noch mindestens ein Eintrag in der Matrix => Graph ist zyklisch */
    return (tempMatrix.length >= 1);

  }

  /**
   * Alle die Knoten, die indegree=0 haben, haben in ihrer Spalte in der Matrix
   * nur Nullen, woran man sie erkennt.
   * @return Knotennummer, die indeg=0 hat.
   */
  private int getIndegZeroKnoten (boolean[][] matrix)
  {

    for (int i = 0; i < matrix.length; i++)
    {
      boolean temp = true;
      for (int j = 0; j < matrix.length; j++)
        if (matrix[i][j])
          temp = false;
      if (temp)
        return i;
    }
    return -1;

  } // getIndegZeroKnoten ()

  /**
   * Gibt eine Kopie der uebergebenen Matrix zurueck.
   * @param matrix
   * @return Eine Kopie der uebergebenen Matrix
   */

  private boolean[][] kopiereMatrix (boolean[][] matrix)
  {
    boolean[][] neueMatrix = new boolean[matrix.length][matrix[0].length];


    for (int i = 0; i < matrix.length; i++)
      for (int j = 0; j < matrix[i].length; j++)
        neueMatrix[i][j] = matrix[i][j];

    return neueMatrix;

  } // kopiereMatrix ()

  /**
   * Loescht in der gegebenen Matrix den gegebenen Knoten, sofern er in der
   * Matrix liegt
   *
   * @param matrix Die Matrix, aus der entfernt werden soll.
   * @param knoten Der Knoten, der entfernt werden soll.
   * @return gibt die verkleinerte Matrix zurueck.
   */

  private boolean[][] loescheKnoten (boolean[][] matrix, int knoten)
  {
    if (knoten >= matrix.length || knoten < 0 || matrix == null || matrix.length < 1)
      return matrix;

    /* ausgehende Kanten des zu loeschenden Knotens loeschen */
    for (int j = 0; j < matrix.length; j++)
      kanteEntfernen(knoten, j);

    /* eingehende Kanten des zu loeschenden Knotens loeschen */
    for (int i = 0; i < matrix.length; i++)
      kanteEntfernen(i, knoten);

    boolean[][] neuMatrix = new boolean[matrix.length-1][matrix[0].length-1];

    /* andere Knoten verschieben sich durch die Loeschung */
    for (int i = 0 ; i < matrix.length ; i++)
      for (int j = 0 ; j < matrix[i].length ; j++)

        if (i > knoten && j < knoten)
          neuMatrix[i-1][j] = matrix[i][j];

        else if (i < knoten && j > knoten)
          neuMatrix[i][j-1] = matrix[i][j];

        else if (i > knoten && j > knoten)
          neuMatrix[i-1][j-1] = matrix[i][j];

        else if (i < knoten && j < knoten)
          neuMatrix[i][j] = matrix[i][j];

    return neuMatrix;
  }

  /**
   * Gibt den Graphen in Form einer Adjazenzmatrix als String zurueck
   * @return
   */

  public String toString ()
  {

    String retVal = "";
    for (int i = 0; i < this.adjazenzMatrix.length; i++)
    {
      for (int j = 0; j < this.adjazenzMatrix[i].length; j++)
        if (this.adjazenzMatrix[i][j] == true)
          retVal = retVal + "1 ";
        else
          retVal = retVal + "0 ";
      retVal = retVal + "\n";
    }
    return retVal;

  } // toString ()

  public static void main (String[] args)
  {
  
    Graph g = new Graph (6);

    System.out.println ("Graph nach der Erstellung:");
    System.out.print (g.toString());

    g.kanteEinfuegen (0,1);
    g.kanteEinfuegen (2,0);
    g.kanteEinfuegen (0,2); // remove for acyclic graph
    g.kanteEinfuegen (3,0);
    g.kanteEinfuegen (2,3);
    g.kanteEinfuegen (4,2);
    g.kanteEinfuegen (4,4); // remove for acyclic graph
    g.kanteEinfuegen (5,4);
    g.kanteEinfuegen (2,5); // remove for acyclic graph
    g.kanteEinfuegen (5,1);
    g.kanteEinfuegen (5,3);

    System.out.println ("");
    System.out.println ("Graph nach dem Einfuegen einiger Kanten:");
    System.out.print (g.toString());

    System.out.println ("");
    System.out.println ("Graph hat nun " + g.getKantenZahl() + " Kanten");
    System.out.println ("Graph hat nun " + g.getKnotenZahl() + " Knoten");

    if (g.isZusammenhaengend ())
      System.out.println ("Graph ist zusammenhaengend.");
    else
      System.out.println ("Graph ist nicht zusammenhaengend.");

    if (g.isZyklisch ())
      System.out.println ("Graph hat mindestens einen Zyklus.");
    else
      System.out.println ("Graph ist zyklenfrei.");

  } // main ()

} // Graph class