// Breadth-First-Durchlauf eines Graphen
// (mit zählen, in BFS-Reihenfolge verketten und Tiefe eintragen)
//
// Aufruf: bfs knotenzahl startknoten
//
// Klaus Kusche, 2019

#include <stdio.h>
#include <stdlib.h>

typedef struct node node;
typedef struct edge edge;

// Knoten
struct node {
  int level;        // BFS-Tiefe vom Startknoten aus
  node *next;       // BFS-Listenverkettung
  edge *edges;      // Adjazenzliste (vom Knoten ausgehende Kanten)
};

// Kante
struct edge {
  node *neighbor;   // Zielknoten der Kante
  edge *next;       // Listenverkettug der Kanten-Liste
};

// bfs-Funktion
// wird mit dem Ausgangsknoten aufgerufen
// macht BFS-Durchlauf der Knoten, befüllt dabei "level" und "next"
// Voraussetzung: Bei Aufruf ist "level" in allen Knoten -1
// liefert Anzahl der verarbeiteten Knoten
int bfs(node *start)
{
  int nodecnt = 0;   // für Returnwert: Knotenzähler 
  node *current;     // aktueller Knoten
                     // = erster noch zu verarbeitender Knoten in der Quere
  node *tail;        // Tail der Queue der noch zu verarbeitenden Knoten
  edge *e;           // aktuelle Kante
  node *target;      // Zielknoten der aktuellen Kante e

  if (start == NULL) return 0;   // ... zur Sicherheit: Keine Knoten!

  // Besuche den Ausgangsknoten:
  // er wird erstes und vorläufig auch letztes Queue-Element
  current = tail = start;  
  current->level = 0;
  
  // nimm den nächsten Knoten aus der Quere, solange einer drin ist ...
  for ( ; current != NULL; current = current->next) {
    ++nodecnt;  // zähle ihn ... 
    // ... und besuche alle seine Nachbarn, die noch nicht in der Queue sind
    for (e = current->edges; e != NULL; e = e->next) {
      target = e->neighbor;
      if (target->level < 0) {
        // Knoten wurde noch nie gesehen:
        // Markiere ihn als gesehen
        // & als 1 Kante weiter entfernt vom Startknoten als der aktuelle Knoten 
        target->level = current->level + 1;
        // hänge ihn hinten in die Queue bzw. in die BFS-Reihenfolge-Liste
        tail = tail->next = target;
      }
    }
  }

  return nodecnt; 
}

int main(int argc, const char *argv[])
{
  unsigned int count, start;  // Knotenanzahl & Nummer des Ausgangsknotens
  node *nodes;      // Pointer auf dyn. Array aller Nodes
  int neighb;       // Eingelesene Nummer des Nachbar-Knotens
  edge **link;      // Zum hinten Anhängen an die Adjazenzliste mit **-Trick
  edge *e;
  node *startnode;  // Pointer auf Ausgangsknoten
  
  if (argc != 3) {
    fprintf(stderr, "Usage: %s node_count starting_node_number\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  count = (unsigned int) atoi(argv[1]);
  start = (unsigned int) atoi(argv[2]);

  if ((count < 1) || (start >= count)) {
    fprintf(stderr,
            "Usage: %s node_count starting_node_number\n"
            "       (node_count > 0, 0 <= starting_node_number < node_count\n",
            argv[0]);
    exit(EXIT_FAILURE);
  }

  nodes = (node *) (malloc(count * sizeof(node)));
  if (nodes == NULL) {
    fprintf(stderr, "%s: out of memory\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  for (node *p = nodes; p < nodes + count; ++p) {
    p->level = -1;
    p->next = NULL;
    p->edges = NULL;
    // link zeigt auf den Pointer, in dem die nächste Kante eingetragen wird
    link = &(p->edges);
    printf("Adjazenzen von Knoten %u eingeben (0...%u, -1 = Ende):\n",
           (unsigned int)(p - nodes), // liefert Nummer des Knotens in nodes
           count - 1);
    for (;;) {
      if (scanf("%d", &neighb) != 1) {
        fprintf(stderr, "%s: invalid input\n", argv[0]);
        exit(EXIT_FAILURE);
      }
      if (neighb < 0) break;
      if ((unsigned int) neighb >= count) {
        fprintf(stderr, "%s: invalid input\n", argv[0]);
        exit(EXIT_FAILURE);
      }
      e = (edge *) (malloc(sizeof(edge)));
      if (e == NULL) {
        fprintf(stderr, "%s: out of memory\n", argv[0]);
        exit(EXIT_FAILURE);
      }
      e->neighbor = &(nodes[neighb]);  // Pointer auf den Zielknoten
      e->next = NULL;                  // Kante wird letzter Knoten der Liste
      // hinten an Adjazenzliste anhängen, nicht vorne:
      // Reihenfolge der Nachbarn aus der Eingabe soll erhalten bleiben!
      *link = e;
      link = &(e->next);
    }
  }

  // Aufruf von bfs
  startnode = &(nodes[start]);
  printf("Verarbeitete Knoten: %d\n", bfs(startnode));

  // Ausgabe
  for (node *p = startnode; p != NULL; p = p->next) {
    printf("Knoten %u: Level %d\n",
           (unsigned int) (p - nodes), // liefert Nummer des Knotens in nodes
           p->level);
  }
}