// Järgnev näide kirjeldab mõned graafi jaoks vajalikud protseduurid 
// ja seejärel teeb graafi.
// Graafi andmestruktuur ehitatakse staatiliselt massiivile ja muutujatele mälu 
// eraldades.
#include <stdio.h>
#define VertMax 100
// Järgnev struktuur on graafi andmete ühte kogumisse koondamiseks
    struct graph {
           int V,E;                    // tippude ja kaarte arvud
           int Adj[VertMax][VertMax];  // naabrusmaatriks
           int Vert[VertMax];          // tippude info
    };
// Järgnev struktuur on ahela (loendi) jaoks. Kasutatakse tipu naabrite 
    struct list {
           int info;
           struct list *next;
    };

static int jrk = 0;    // sellega peetakse arvet tipu numbrite üle, kui neid Vert-massiivi kantakse

// Graafi algväärtustamine
struct graph *GraphInit(V) {
      int i,j;
      struct graph *graaf;
      graaf = malloc(sizeof *graaf);
      graaf->V = V;
      graaf->E = 0;
      for (i=0;i<V;i++){
          graaf->Vert[i] = 0;
          for (j=0;j<V;j++){
              graaf->Adj[i][j] = 0;
          }
      }
      return(graaf);
}
// Protseduur lisab graafi kaare tippude v1 ja v2 vahele      
InsertEdge(struct graph *graaf,int v1,int v2){
      graaf->Adj[v1][v2] = 1;
      graaf->Adj[v2][v1] = 1;
      graaf->E++;
}

// Protseduur tippude väärtuste lisamiseks (kui seda peaks vaja olema
InsertVertice(struct graph *graaf, int vert){
      graaf->Vert[jrk++] = vert;
}
           
// Protseduur kustutab gaarfist seose V1 ja V2 vahel.
RemoveEdge(struct graph *graaf,int v1,int v2){
      graaf->Adj[v1][v2] = 0;
      graaf->Adj[v2][v1] = 0;
      graaf->E--;
}

// Protseduur tagastab tipu v naabrid. Need esitatakse ahelana
struct list *GetAdjList(struct graph *graaf,int v) {
      struct list *adjlist, *abi;
      int i;
      adjlist = NULL;
      for (i=0; i<graaf->V; i++){
// Kui naabrusmaatriksis ei ole 0, siis lisatakse tipu number ahelasse
          if (graaf->Adj[v][i] != 0) {
              abi = malloc(sizeof *abi);
              abi->next = adjlist;
              abi->info = i;
              adjlist = abi;
          }
      }
      return(adjlist);
}

// Peaprogramm algab siit
main(void){
struct graph *graafike;
struct list *naabrid, *abi;
int i,j;
// Algväärtustame tühja graafi eeldusega, et tippe saba seal olema 10
     graafike = GraphInit(10);
// Kontrolliks trükime välja algväärtustatud olukorra
     for (i=0;i<10;i++){
          printf("%3d\n",graafike->Vert[i]);
     }
     for (i=0;i<10;i++){
          for (j=0;j<10;j++){
              printf("%3d",graafike->Adj[i][j]);
          }
          printf("\n");
     }
// Lisame prooviks 3 kaart
     InsertEdge(graafike,1,2);
     InsertEdge(graafike,1,4);
     InsertEdge(graafike,1,6);

     printf("Lisatud");

// Kontrolliks trükime välja olukorra, mis tekkinud peale kaarte lisamist
     for (i=0; i<graafike->V; i++){
          printf("%3d\n",graafike->Vert[i]);
     }
     for (i=0; i<graafike->V; i++){
          for (j=0; j<graafike->V; j++){
              printf("%3d",graafike->Adj[i][j]);
          }
          printf("\n");
     }
// Koostame naabrite nimekirja tipule 1
     naabrid = GetAdjList(graafike,1);
// Trükime tipu 1 naabrite nimekirja 
     abi = naabrid;
     while (abi != NULL) {
           printf("%d",abi->info);
           abi = abi->next;
     }
}