/**
 * AlgoDat SoSe2000, Aufgabe 66
 * Umwandlung von einer Darstellung eines Graphen in eine andere
 *
 * Achtung: Keine der Methoden prueft, ob die Knoten, die durch die Kanten
 * verbunden werden sollen, ueberhaupt existieren!
 *
 * @author Christian Semrau
 * <a href="mailto:gsemrau@cs.uni-magdeburg.de">gsemrau@cs.uni-magdeburg.de</a>
 */

import java.util.LinkedList;
class ChS_Aufg66{

/*
a) Kantenliste in Adjazenzmatrix:
*/
public int[][] kal2adm(int[] KaL){
  int[][] AdM;  // Adjazenzmatrix

  int n = KaL[0];  // Knotenzahl
  AdM = new int[n][n];  // Matrix anlegen

  // Matrix mit Nullen fuellen ist in JAVA nicht noetig
  // for (int i = 0; i<n; i++) for (int k = 0; k<n; k++) AdM[i][k] = 0;

  int m = KaL[1];  // Kantenzahl
  for (int i = 0; i<m; i++)  // alle Kanten durchgehen
    AdM[ KaL[i*2+2] ][ KaL[i*2+3] ] ++;
    // das erste Element einer Kante gibt an, von wo sie losgeht,
    // das zweite Element sagt uns, in welchen Knoten sie hineinfuehrt
    
    // Wenn eine Kante mehrmals in der Kantenliste enthalten ist,
    // dann ist auch in der Matrix ein Wert groesser als 1 gespeichert!

  return AdM;
}

/*
b) Kantenliste ind Adjazenzliste:
*/
public LinkedList[] kal2adl(int[] KaL){
  LinkedList[] AdL;  // Adjazenzliste

  int n = KaL[0];  // Knotenzahl
  int m = KaL[1];  // Kantenzahl
  AdL = new LinkedList[n];  // Liste anlegen

  // Liste initialisieren
  for (int i = 0; i<n; i++)
    AdL[i] = new LinkedList();

  for (int i = 0; i<m; i++)  // alle Kanten durchgehen
    AdL[ KaL[i*2+2] ]. addFirst(new Integer( KaL[i*2+3] ));
    // wir sagen der Liste, die zum Startknoten gehoert, dass der
    // Endknoten eingefuegt werden soll. Dass kann auch mehrmals
    // passieren, wenn die Kante mehrmals in der Liste ist!

  return AdL;
}

/*
c) Adjazenzmatrix in Knotenliste:
*/
public int[] adm2knl(int[][] AdM){
  int[] KnL;  // Knotenliste

  int n = AdM.length;  // Knotenzahl
  int m = 0;  // Gesamtzahl der Kanten

  int[] hilf = new int[n]; // Hilfsstruktur
  // speichert fuer jeden Knoten die Anzahl der ausgehenden Kanten

  for (int i=0; i<n; i++)
  for (int k=0; k<n; k++){
    hilf[i] += AdM[i][k];
    m += AdM[i][k];
    // Kantenzaehler erhoehen
  }

  // jetzt enthaelt m die Gesamtzahl der Kanten und hilf die Anzahl fuer
  // jeden Knoten

  KnL = new int[1+n+m];
  KnL[0] = n;

  int index = 1;  // wir haengen die Werte stets am Ende der Knotenliste an

  for (int i=0; i<n; i++){  // fuer alle Knoten
    KnL[index++] = hilf[i];  // speichern der Kantenzahl des Knoten
    for (int k=0; k<n; k++){  // alle moeglichen Zielknoten durchgehen
      for(int h = AdM[i][k]; h>0; h--)
      // wenn die Knoten gar nicht verbunden sind, ist h==0 und die
      // Schleife wird gar nicht betreten, ansonsten wird der Zielknoten
      // so oft angehaengt, wie der Wert in der Matrix angibt, das erlaubt 
      // es, zwei Knoten mehrmals zu verbinden (was laut Aufgabenstellung
      // nicht ausgeschlossen ist!)
        KnL[index++] = k;
    }
  }
  
  return KnL;
}

}