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

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

// struct "node" für einen Knoten:
// "level" für die Tiefe vom Startknoten aus gesehen
// "next" für die Verkettung in BFS-Reihenfolge
// "edges" für die Kantenliste
/*** missing ***/

// struct "edge" für eine Kante (mit "neighbor" und "next")
/*** missing ***/

// 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
/*** missing ***/


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);
  }
}