// sl-4-BA-Inf2: Datenstrukturen für Graphen (Adjazenzmatrix, Adjazenzliste)
// Graphalgorithmen: Tiefensuche, Breitensuche, kürzeste Wege (Dijkstra)

// Begriffe:
// gerichteter Graph G=(V,E) mit Knotenmenge V und Kantenmenge E aus VxV
// (ungerichteter Graph G=(V,E), Richtung der Kanten weglassen)
// Kante (x,y) ist inzident zu ihren Knoten x und y; x und y sind adjazent/benachbart
// S(x) Menge der Nachfolger = { y | (x,y) in E }
// P(x) Menge der Vorgänger = { y | (y,x) in E }
// N(x) Menge der Nachbarn = { y | (x,y) in E oder (y,x) in E }
// d+(x) = |S(x)| Ausgangsgrad, d-(x) = |P(x)| Eingangsgrad, d(x) = d+(x) + d-(x) Grad
// (x,x) heißt Schlinge
// Adjazenzmatrix A=(a(i,j)) zum Graphen G=(V,E) mit V={v1,...,vn},
// a(i,j)=1 gdw. (vi,vj) ist Kante in E
// gewichtete Graphen G=(V,E,c), c:E->R
// in diesem Programm Adjazenzmatrix eines gewichteten Graphen
// a(i,j)=x, x!=0 gdw. (vi,vj) ist Kante in E mit Gewicht c(vi,vj)=x
// Adjazenzliste: Liste von Knoten, jeder Knoten speichert Liste seiner Nachfolger

// In der Regel liegen Graphen als Adjazenzlisten vor, in diesem Programm wird
// Darstellung als Matrix hauptsächlich zur einfachen Generierung der
// Zufallsgraphen verwendet sowie als weitere Datenstruktur zur möglichen
// Darstellung von Graphen im Rechner

// Übungsaufg.: Wandeln Sie (von Hand) Adjazenzmatrizen in Adjazenzlisten um,
// "malen" Sie die Graphen und führen Sie eine Tiefen- und Breitensuche durch.
// Bestimmen Sie (von Hand) mit Dijkstras Algorithmus die kürzesten Wege
// zwischen allen Paaren von Knoten (wie oft muss dazu der Dijkstra-Algorithmus
// ausgeführt werden?)

#include "time.h"
#include <iostream>
using namespace std;

const int ANZ_KNOTEN = 7;

int ZufaZa() { 
  return rand()%9 + 1; // erzeugt eine 1-stellige Zufallszahl != 0
  // return rand()%90 + 10; // erzeugt eine 2-stellige Zufallszahl
}

int AdjMat[ANZ_KNOTEN][ANZ_KNOTEN];

void InitAdjMat(int mat[ANZ_KNOTEN][ANZ_KNOTEN]) {
  // sehr(!!!) einfacher Zufallsgraphgenerator
  for(int i=0; i<ANZ_KNOTEN; i++)
    for(int j=0; j<ANZ_KNOTEN; j++)
      mat[i][j] = (i!=j && rand()%100<35) ? ZufaZa() : 0 ;
  // keine Schlingen und restliche Kanten mit Wahrscheinlichkeit 35%
}

void CoutAdjMat(int mat[ANZ_KNOTEN][ANZ_KNOTEN]) {
  cout << "Adjazenzmatrix:" << endl;
  for(int i=0; i<ANZ_KNOTEN; i++) {
    for(int j=0; j<ANZ_KNOTEN; j++)
      cout << AdjMat[i][j] << ' ';
    cout << endl;
  }
}

struct Edge;

struct Node { // hier: id = Index im Array of Nodes
  int dfsnr; // Nummer, die der Knoten bei der Tiefensuche erhält
  int bfsnr; // Nummer, die der Knoten bei der Breitensuche erhält
  Edge* EIK; // Erste inzidente Kante = Beginn seiner Nachfolgerknotenverweisliste
  void init(int idfsnr, int ibfsnr, Edge* iEIK) {
    dfsnr=idfsnr; bfsnr=ibfsnr; EIK=iEIK;
  }
};

struct Edge {
  int cost; // Gewicht der Kante
  int EKn; // Index des Endknotens der Kante
  Edge* NKa; // nächste inzidente Kante
  void init(int icost, int iEKn, Edge* iNKa) {
    cost=icost; EKn=iEKn; NKa=iNKa;
  }
};

Node AdjLst[ANZ_KNOTEN]; // könnte etwas allgemeiner (und komplizierter)
// auch als Liste mit Pointern implementiert werden

void AdjMat2Lst(int mat[ANZ_KNOTEN][ANZ_KNOTEN], Node lst[ANZ_KNOTEN]){
  // jede Zeile der Adjazenzmatrix durchgehen und die
  // Einträge != 0 als Kanten einfügen
  for(int i=0;i<ANZ_KNOTEN;i++) {
    for(int j=ANZ_KNOTEN-1;j>=0;j--) { // Kanten werden jeweils vorne eingefügt,
      // so ist die Reihenfolge in der Liste gleich der in der Matrix
      if (mat[i][j]) {
	Edge* newedge = new Edge; newedge->init(mat[i][j],j,lst[i].EIK);
	lst[i].EIK=newedge;
      }
    }
  }
}

void CoutAdjLst(Node lst[ANZ_KNOTEN]) {
  cout << "Adjazenzliste:" << endl;
  for(int i=0;i<ANZ_KNOTEN;i++) {
    Edge* ptr = lst[i].EIK;
    while (ptr) {
      cout << "Kante von " << i << " nach " << ptr->EKn
	   << " mit Gewicht " << ptr->cost << endl;
      ptr=ptr->NKa;
    }
  }
}

int dfscount=1; // globaler Zähler für die Tiefensuche
// muss bei weiterer Tiefensuche neu initialisiert werden
// dito die "dfsnr" in der "AdjLst"

void Tiefensuche(int i) { // Schema: falls Knoten i noch nicht markiert ist,
  // markiere Knoten i und führe die Tiefensuche von allen Nachfolgern aus aus.
  if (!AdjLst[i].dfsnr) { // noch nicht markierte Knoten haben noch dfsnr=0
    AdjLst[i].dfsnr=dfscount++;
    Edge* ptr = AdjLst[i].EIK;
    while (ptr) {
      Tiefensuche(ptr->EKn);
      ptr=ptr->NKa;
    }
  }
}
  
void CoutDFSNumbers(Node lst[ANZ_KNOTEN]) {
  cout << "DFS-Nummern:" << endl;
  for(int i=0;i<ANZ_KNOTEN;i++) {
    cout << "Knoten " << i << " hat DFS-Nr. " << lst[i].dfsnr << endl;
  }
}

// für die Breitensuche werden Queues benötigt (vom Anfang des Semesters kopiert)

struct queue { // als Ringliste: zeigt auf letztes Element, queue->front auf erstes
        int inhalt;
        queue *front;
};

void enqueue (queue *& q, int value) {
        if(q==0) {
                q = new queue; // erstes Element in der Queue
                q->inhalt = value;
                q->front = q; // erstes und letztes Element sind identisch
        } else {
                queue * elem = new queue;
                elem->front = q->front;
                elem->inhalt = value;
                q->front = elem;
                q = elem;
        }
}

int dequeue (queue *& q) { // geht davon aus, dass die Queue q nicht leer ist
        // die aufrufende Funktion muss ggf. über is_empty(q) (also q==0)
        // testen, ob die Queue q leer ist
        int value = q->front->inhalt;
        if (q->front==q) { // ist es das letzte Element in der Queue?
                delete q;
                q=0;
        } else {
                queue *old = q->front;
                q->front=q->front->front;
                delete old;
        }
        return value;
}

bool is_empty (queue * q) {
  return q==0;
}

void Breitensuche(int i) { // Schema: beginne mit Knoten i
  // markiere Knoten i und merke in der Queue alle Nachfolger
  // entnehme jeweils den nächsten Knoten der Queue und merke,
  // falls dieser noch nicht markiert ist, alle Nachfolger in der Queue
  int bfscount=1; // Zähler für die Breitensuche
  int idx;
  queue* q=0;
  enqueue(q,i);
  while (!is_empty(q)) {
    idx=dequeue(q);
    if (!AdjLst[idx].bfsnr) { // noch nicht markierte Knoten haben noch bfsnr=0
      AdjLst[idx].bfsnr=bfscount++;
      Edge* ptr = AdjLst[idx].EIK;
      while (ptr) {
	enqueue(q,ptr->EKn);
	ptr=ptr->NKa;
      }
    }
  }
}

void CoutBFSNumbers(Node lst[ANZ_KNOTEN]) {
  cout << "BFS-Nummern:" << endl;
  for(int i=0;i<ANZ_KNOTEN;i++) {
    cout << "Knoten " << i << " hat BFS-Nr. " << lst[i].bfsnr << endl;
  }
}










// Datenstrukturen für Dijkstras Algorithmus

// Idee von Dijkstras Algorithmus (kürzeste Wege in Graphen mit Kantengewichten >=0):
// Die Knoten werden intern aufgeteilt in Baumknoten (Knoten, für die
// die kürzeste Entfernung garantiert gefunden wurde),
// Randknoten (Knoten, die nicht Baumknoten aber Nachfolger eines Baumknotens
// sind -- für diese ist ein Weg (nicht notwendigerweise der kürzeste) gefunden),
// sowie der Rest. Im Programm werden explizit nur die Randknoten verwaltet
// (die Baumknoten sind die Knoten, die nicht im Rand sind und für die schon ein Weg
// gefunden wurde; der Rest besteht aus den Knoten, die noch nicht erreicht wurden)
// Für jeden Knoten im Rand wird sich der bisher kürzeste gefundene Weg
// (genauer: dessen Entfernung) gemerkt.
// Ablauf: Zu Beginn ist der Startknoten in B und dessen Nachfolger in R, gefundene
// Entfernungen sind 0 zum Startknoten und das jeweilige Kantengewicht zu den Nachfolgern
// In jeder Iteration wähle den Knoten aus R, dessen gefundene Entfernung minimal ist
// und prüfe, ob über diesen Knoten dessen Nachfolger auf kürzerem Weg erreicht werden.
// Korrektheit: Vollständige Induktion über die Anzahl der Iterationen:
// Zu Beginn ist der kürzeste Weg zum Startknoten (Länge 0) gefunden.
// Bei jeder Auswahl des Knotens mit minimaler Entfernung aus R ist diese die
// garantiert kürzeste, weil über andere Knoten (Entfernung zu diesen ist mindestens
// genauso groß) und weitere Kanten (Gewichte >=0) der Weg höchstens länger werden kann.

// Um nicht nur die kürzesten Entfernungen zu bestimmen, sondern auch den zugehörigen
// Weg angeben zu können, kann man einen Kürzeste-Wege-Baum berechnen lassen.
// Dazu speichert man sich jedes Mal, wenn ein Knoten in den Baum eingefügt wurde
// oder sich die gefundene Entfernung verringert hat, den Knoten, über den dieser
// kürzere Weg gefunden wurde  (= der zuletzt über delete_min aus R entnommene Knoten)
// (-> Array int pred[ANZ_KNOTEN]) -- Beispiel: Führt der kürzeste Weg von
// 0 nach 3 über die Knoten 6, 2 und 5, so wurde beim für den Knoten 6 sich der
// Vorgänger 0 gemerkt, für den Knoten 2 der Vorgänger 6, für Knoten 5 der Vorgänger 2
// und für den Knoten 3 der Vorgänger 5. Die Vorgänger können nun ausgehend vom Knoten 3
// bestimmt werden (0 hat keinen Vorgänger, z.B. == -1) (also 3,5,2,6,0) und dann rückwärts
// ausgegeben werden -- Aufgabe: Implementieren Sie die Berechnung und Ausgabe der Wege

// 1. Variante: Verwaltung der Randmenge R als Liste (struct RLst)
// delete_min (Suche des Knotens mit minimaler Entfernung in R):
// -> Liste durchlaufen: Aufwand O(n) 
// insert (Einfügen eines neuen Knotens in R):
// -> Vorne in der Liste einfügen: Aufwand O(1)
// decrease_key (Verringern der Entfernung eines Knotens, der schon in R ist):
// -> direkter Zugriff auf das Element in der Liste: Aufwand O(1)
// Gesamtaufwand: n*delete_min + m*(insert oder decrease_key) = O(n^2)

struct RLst_Node {
  int node; // Index im Knotenarray
  int d; // Entfernung zum Startknoten
  RLst_Node* next; // nächstes Element in der Liste
};

struct RLst {
  RLst_Node* whereinR[ANZ_KNOTEN]; // Verweis, wo der Knoten in der Liste sich befindet
  RLst_Node* lst; // erstes Element in der Liste
  void init() { lst=0; for(int i=0;i<ANZ_KNOTEN;i++) whereinR[i]=0; }
  bool is_empty() { return (lst==0); }
  bool member(int node) { return (whereinR[node]!=0); }
  void insert(int node, int d) { // fügt Knoten i mit Wert d am Anfang von lst ein
    RLst_Node *elem = new RLst_Node;
    elem->node = node; elem->d = d; elem->next = lst;
    lst = elem; whereinR[node]=lst;
  }
  int delete_min() { // gibt Index des Knotens mit kleinstem Wert d in lst zurück
    // kleinstes Element finden
    RLst_Node *min = lst; // Zeiger auf Listenelement mit bisher kleinstem Wert
    RLst_Node *ptr = lst->next; // Pointer zum Durchlaufen der Liste
    while (ptr) {
      if (ptr->d < min->d) min=ptr; // Minimum merken
      ptr=ptr->next;
    }
    int rueckgabewert = min->node;
    // Element löschen
    if (min==lst) { // erstes und/oder einziges Element
      lst=lst->next;
      delete min;
      whereinR[rueckgabewert]=0;
    } else { // Vorgänger von min finden und min rauslöschen
      ptr=lst;
      while (ptr->next!=min) ptr=ptr->next;
      ptr->next=min->next;
      delete min;
      whereinR[rueckgabewert]=0;
    }
    // Index zurückgeben
    return rueckgabewert;
  }
  void decrease_key(int node, int d) { // verringert den Wert von Knoten node auf d
    whereinR[node]->d=d;
  }
  void debug() { cout << "R="; RLst_Node* ptr=lst; 
    while (ptr) { cout << " " << ptr->node << ":" << ptr->d; ptr=ptr->next; }
    cout << endl;
  }
};

// 2. Variante: Verwaltung der Randmenge R als Heap (struct RHeap)
// delete_min (Suche des Knotens mit minimaler Entfernung in R):
// -> in der Wurzel des Heaps, Heapeigenschaft wieder herstellen: Aufwand O(log(n)) 
// insert (Einfügen eines neuen Knotens in R):
// -> Am Ende vom Heap einfügen und aufsteigen lassen: Aufwand O(log(n))
// decrease_key (Verringern der Entfernung eines Knotens, der schon in R ist):
// -> Element im Heap aufsteigen lassen: Aufwand O(log(n))
// Gesamtaufwand: n*delete_min + m*(insert oder decrease_key) = O(m*log(n))
// In Straßengraphen ist m<=c*n -> Aufwand mit Heaps deutlich geringer als mit Listen

struct RHeap {
  int whereinR[ANZ_KNOTEN]; // Index, an dem sich der Knoten im Heap befindet
  int last; // letzter Index, der zum Heap gehört
  struct { int node; int d; } heap[ANZ_KNOTEN];
  // min-Heap!: Vater <= Soehne bzgl. der d-Werte
  void init() { last=-1; for(int i=0;i<ANZ_KNOTEN;i++) whereinR[i]=-1;
  } // heap wird beim Einfügen initialisiert
  bool is_empty() { return (last==-1); }
  bool member(int node) { return (whereinR[node]!=-1); }
  void insert(int node, int d) { // fügt Knoten i mit Wert d als neues Element im Heap ein
    // und lässt ihn an die richtige Stelle aufsteigen
    last++;
    int sohn=last; // Index des Sohnknotens
    int vater=(sohn-1)/2; // Index des Vaterknotens
    while (sohn>0 && heap[vater].d > d) { // sohn = Index der "freien Stelle"
      // wenn sohn==0, dann gibt es keinen Vater, der noch runterrutschen kann
      heap[sohn].node=heap[vater].node;
      heap[sohn].d   =heap[vater].d   ;
      whereinR[heap[vater].node]=sohn;
      sohn=vater; vater=(sohn-1)/2;
    }
    heap[sohn].node=node; heap[sohn].d=d; whereinR[node]=sohn;
  }
  int delete_min() { // gibt Index des Knotens mit kleinstem Wert d im Heap zurück
    // kleinstes Element ist in der Wurzel, dieses löschen und Element von
    // Position last auf die Wurzel kopieren und in Heap[0..--last] einsinken lassen
    int rueckgabewert = heap[0].node; whereinR[rueckgabewert]=-1;
    int node=heap[last].node; int d=heap[last].d; // (node,d) sinkt ein
    last--; // Heapgröße um 1 verkleinert
    int vater=0; int links=2*vater+1; int rechts=links+1;
    while (links<=last) { // es existiert noch mind. 1 Kind
      if (rechts<=last) { // beide Kinder existieren
	if (heap[links].d>heap[rechts].d) links=rechts;
	// heap[links].d ist jetzt der "kürzere" Sohn
	if (heap[links].d<d) { // Element sinkt weiter
	  heap[vater].node=heap[links].node;
	  heap[vater].d   =heap[links].d   ;
	  whereinR[heap[vater].node]=vater;
	  vater=links; links=2*vater+1; rechts=links+1;
	} else break; // Element sinkt nicht weiter
      } else { // links=last und das linke Kind ist ein Blatt
	if (heap[links].d<d) {
	  heap[vater].node=heap[links].node;
	  heap[vater].d   =heap[links].d   ;
	  whereinR[heap[vater].node]=vater;
	  vater=links;
	}
	break; // Element sinkt nicht weiter
      }
    }
    // heap[vater] ist jetzt der freie Platz
    heap[vater].node=node;
    heap[vater].d   =d   ;
    whereinR[heap[vater].node]=vater;
    // Index zurückgeben
    return rueckgabewert;
  }
  void decrease_key(int node, int d) { // verringert den Wert von Knoten node auf d
    heap[whereinR[node]].d=d;
    int sohn=whereinR[node]; // Index des Sohnknotens
    int vater=(sohn-1)/2; // Index des Vaterknotens
    while (sohn>0 && heap[vater].d > d) { // sohn = Index der "freien Stelle"
      // wenn sohn==0, dann gibt es keinen Vater, der noch runterrutschen kann
      heap[sohn].node=heap[vater].node;
      heap[sohn].d   =heap[vater].d   ;
      whereinR[heap[vater].node]=sohn;
      sohn=vater; vater=(sohn-1)/2;
    }
    heap[sohn].node=node; heap[sohn].d=d; whereinR[node]=sohn;
  }
  void debug() { cout << "R="; for(int i=0;i<=last;i++)
				 cout << " " << heap[i].node << ":" << heap[i].d;
    cout << endl; }
};

void Dijkstra(Node lst[ANZ_KNOTEN], int s) { // berechnet die kürzesten Entfernungen
  // vom Knoten s zu allen anderen Knoten
  int d[ANZ_KNOTEN]; // Entfernungen von s zu .
  int u,v; // Knoten-Indizes
  int c; // Weglänge
  Edge* nachfolger;
  const int infty=ANZ_KNOTEN*10; // 10>größtes Gewicht, maximal ANZ_KNOTEN-1 Kanten pro Weg
  // Initialisierung
  for (int i=0;i<ANZ_KNOTEN;i++) d[i]=infty; // = noch unbekannt = unendlich
  d[s]=0;
  // RLst R;  // EINE DER BEIDEN ZEILEN AUSKOMMENTIEREN
  RHeap R; // UM ZWISCHEN R ALS LISTE UND R ALS HEAP ZU WÄHLEN 
  R.init();
  R.insert(s,0); // vereinfachte Initialisierung, im ersten Schritt
  // wird s aus R ausgewählt und die Nachfolger in R eingefügt
  // Berechnung
  while (!R.is_empty()) { // solange noch neue Knoten erreichbar sind
    u=R.delete_min(); // wähle den Knoten mit kleinster Entfernung zum Startknoten
    nachfolger=lst[u].EIK;
    while (nachfolger!=0) { // teste für alle ausgehenden Kanten
      v = nachfolger->EKn; c = d[u]+nachfolger->cost; // Weglänge nach v über u 
      if (c<d[v]) {
	d[v]=c;
	if (!R.member(v)) R.insert(v,c);
	// falls der Nachfolger noch nie betrachtet wurde, füge ihn in R ein
	else R.decrease_key(v,c);
	// falls der Weg zum Nachfolger über u kürzer ist, verringere die Entfernung
	// zum Nachfolger auf den entsprechend kleineren Wert
      }
      nachfolger=nachfolger->NKa;
    }
  }
  // Ausgabe
  cout << "Errechnete Entfernungen:" << endl;
  for (int i=0;i<ANZ_KNOTEN;i++)
    if (d[i]==infty)
      cout << "Knoten " << i << " ist von Knoten " << s << " aus nicht erreichbar!" << endl;
    else
      cout << "Entfernung von Knoten " << s << " zum Knoten " << i << " betraegt " << d[i] << endl;
}





int main(void)
{
  srand((unsigned) time(NULL)); // Initialisierung des Zufallszahlengenerators

  InitAdjMat(AdjMat);
  CoutAdjMat(AdjMat);

  AdjMat2Lst(AdjMat,AdjLst);
  CoutAdjLst(AdjLst);

  Tiefensuche(0);
  CoutDFSNumbers(AdjLst);

  Breitensuche(0);
  CoutBFSNumbers(AdjLst);

  Dijkstra(AdjLst,0);

#ifdef _WIN32
  system("Pause");
#endif
  return EXIT_SUCCESS;
}