/media/sda-magnetic/david/Dokumente-16-2024-08-01/informatikUmathematik/graph/generategraphs7.c

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

#define N       7


int Q [1024];
int Qtop = 0;
int Qbottom = 0;

void Qput (int v) {
    Q [Qtop] = v;
    Qtop ++;
}

int Qget (void) {
    int v = Q [Qbottom];
    Qbottom++;
return v;
}

int QIsNotEmpty () {
    return (Qbottom < Qtop);
}

int neighbours_index [N];

void init_neighbours_index () {
    int i;

    for (i = 0;  i < N;  i++)
        neighbours_index [i] = 0;
return;
}

void reset_neighbours_index (int i) {
    neighbours_index [i] = 0;
}

int neighbours_adjazenzmatrix (int a [N][N], int b [N], int v) {
    int i, j;

    for (i = 0, j = 0;  i < N;  i++) {
        if (a [v][i] != -1) {
            b [j] = a [v][i];
            j++;
        }
    }
return j;
}

int neighbour_adjazenzmatrix (int a [N][N], int v) {
    int t;

    while (neighbours_index [v] < N) {
        if (a [v][neighbours_index [v]] != 0) {
            t = neighbours_index [v];
            neighbours_index [v]++;
            return t;
        }
        neighbours_index [v]++;
    }
return -1;
}

int visited [N];

void init_visited (void) {
    int i;
    for (i = 0;  i < N;  i++)
        visited [i] = 0;
return;
}

int notAllVisited () {
    int i;

    for (i = 0;  i < N;  i++)
        if (visited [i] == 0)
            return 1;
return 0;
}

int ix;

int _bfs (int a [N][N], int b [N], int v) {
    int w;

    if (notAllVisited ()) {
        while ((w = neighbour_adjazenzmatrix (a, v)) != -1) {
            if (visited [w] == 0) {
                visited [w] = 1;
                b [ix] = w;
                ix++;
                _bfs (a, b, w);
                printf ("%c, ", w + 'a');
            }
        }
    }
}

int bfs (int a [N][N], int b [N], int v) {
    init_neighbours_index ();
    init_visited ();
    visited [v] = 1;
    ix = 0;
    b [ix] = v;
    ix = 1;
    _bfs (a, b, v);
    printf ("\n");
}


void generate_adjanzenzmatrix (int a [N][N], int n) {
    int i, j;

    for (i = 0;  i < n;  i++) {
        for (j = 0;  j < n;  j++) {
            a [i][j] = -1;
        }
    }


    for (i = 0;  i < n;  i++) {
        for (j = 0;  j < n;  j++) {
            if ((a [i][j] == -1) && (a [j][i] == -1)) {
                a[j][i] = a [i][j] = rand () % 2;
            }
            if (i == j)
                a [i][j] = a [j][i] = 1;

        }
    }
}

void print_csv_adjanzenzmatrix (int a [N][N], int n) {
    int i, j;

    printf ("%c,", ' ');
    for (i = 0;  i < n-1;  i++)
        printf ("%c,", i + 'a');
    printf ("%c\n", i+'a');
    for (i = 0;  i < n;  i++) {
        printf ("%c,", i+'a');
        for (j = 0;  j < n-1;  j++) {
            printf ("%c,", a [i][j] + '0');
        }
        printf ("%c\n", a [i][j] + '0');
    }
}

void read_csv_adjanzenzmatrix (int a [N][N], int n) {
    int i, j;
    int ch;

    scanf ("%c,", &ch);
    for (i = 0;  i < n-1;  i++)  {
        scanf ("%c,", &ch);
    }
    scanf ("%c\n", &ch);


    for (i = 0;  i < n;  i++) {
        scanf ("%c,", &ch);
        for (j = 0;  j < n-1; j++) {
            scanf ("%i,", &ch);
            a [i] [j] = ch;
        }
        scanf ("%i\n", &ch);
        a [i] [j] = ch;
    }

}

void convert_csv_adjanzenzmatrix_to_adjazensliste (int a [N][N], int b [N][N], int n) {
    int i, j, k;

    for (i = 0;  i < n;  i++) {
        for (j = 0, k = 0;  j < n;  j++) {
            if (a [i][j] == 1) {
                b [i][k] = j;
                k++;
            }
        }
        for (; k < n;  k++)
            b [i][k] = -1;
    }

}

void convert_csv_adjanzenzliste_to_adjazensmatrix (int a [N][N], int b [N][N], int n) {
    int i, j;

    for (i = 0;  i < n;  i++) {
        for (j = 0;  j < n;  j++)
            a [i][j] = 0;
    }

    for (i = 0;  i < n;  i++) {
        for (j = 0;  j < n;  j++)
            if (b [i][j] != -1)
                a [i][b[i][j]] = 1;
    }

}

void read_csv_adjanzenzliste (int b [N][N], int n) {
    int i, j, k;
    int ch = 0;

    scanf ("%c,", &ch);
    for (i = 0;  i < n-1;  i++)  {
        scanf ("%c,", &ch);
    }
    scanf ("%c\n", &ch);

    for (i = 0;  i < n;  i++) {
        scanf ("%c,", &ch);
        for (j = 0, k = 0;  j < n-1;  j++) {
            scanf ("%c,", &ch);
            if (ch == ' ')
                b [i][j] = -1;
            else
                b [i][j] = ch - 'a';

        }
        scanf ("%c\n", &ch);
        if (ch == ' ')
            b [i][j] = -1;
        else
            b [i][j] = ch - 'a';
    }
}

void print_csv_adjanzenzliste (int b [N][N], int n) {
    int i, j;
    printf ("%c,", ' ');
    for (i = 0;  i < n-1;  i++)
        printf ("%c,", i + 'a');
    printf ("%c\n", i+'a');
    for (i = 0;  i < n;  i++) {
        printf ("%c,", i+'a');
        for (j = 0;  j < n-1;  j++) {
            if (b [i][j] != -1)
                printf ("%c,", b [i][j] + 'a');
            else
                printf (" ,");
        }
        if (b [i][j] != -1)
            printf ("%c\n", b [i][j] + 'a');
        else
            printf (" \n");
    }

}



void print_tex (int a [N][N], int component [1024]) {
    int i, j;
    int codez = 8;
    printf("\\documentclass{article}\n");
    printf("\\usepackage[utf8]{inputenc}\n");
    printf("\\usepackage{pgf, tikz}\n");
    printf("\\usetikzlibrary{arrows , automata , positioning}\n");
    printf("\\begin{document}\n\n");


    printf("\\begin{center}\n");
    printf("\\begin{tikzpicture}[>=stealth',shorten >=1pt,auto,node distance=2.5cm]\n");
    printf("\%Knoten\n");

    printf("\\node (a) [state, thick] {a};\n");
    printf("\\node (b) [state, thick, right of= a, below of=a] {b};\n");
    printf("\\node (c) [state, thick, left of= a, below of=a] {c};\n");
    printf("\\node (d) [state, thick, below of=b, right of=b] {d};\n\n");
    printf("\\node (e) [state, thick, below of=c, left of=c] {e};\n\n");

    printf("\\node (g) [state, thick, below of=d, left of=d] {g};\n\n");
    printf("\\node (f) [state, thick, below of=e, right of=e] {f};\n\n");

    printf("\%Verbindungen\n");
    printf("\\path[thick,->]\n");



    char *leftright [] = {"left", "right"};
    char *abovebelow [] = {"above", "below"};

    for (i = 0;  i < N;  i++) {
        for (j = 0;  j < N; j++) {
            if (a [i] [j] == 1)
                printf ("(%c) edge [bend angle=20, bend left,below] (%c)\n", (char)('a' + i), (char)('a' + j));
        }
    }
    for (i = 0;  i < N-1;  i++)
        printf ("(%c) edge [bend angle=20, bend left,below, style thick] (%c)\n", component [i] + 'a', component [i+1] + 'a');
    printf(";\n");
    printf("\\end{tikzpicture}\n");
    printf("\\end{center}\n");
    printf("\\end{document}\n");

}


int main (int argc, char *argv []) {
    time_t t;
    int n = N;
    int a [N][N];
    int b [N][N];
    int component [1024];



    srand ((unsigned) time (&t));

    if (argc != 3) {
        printf ("Wrong Parameter!\ng: generete generate_adjanzenzmatrix\nr: read_csv_adjanzenzmatrix\ns: read_csv_adjanzenzliste\n\np: print_csv_adjanzenzmatrix\nq: print_csv_adjanzenzliste");
        return 1;
    }
    if (strcmp(argv [1], "r") == 0) {
        read_csv_adjanzenzmatrix (a, n);
        convert_csv_adjanzenzmatrix_to_adjazensliste (a, b, n);
    }
    else if (strcmp (argv [1], "g") == 0) {
        generate_adjanzenzmatrix (a, n);
        convert_csv_adjanzenzmatrix_to_adjazensliste (a, b, n);
    }
    else if (strcmp (argv [1], "s") == 0) {
        read_csv_adjanzenzliste (b, n);
        convert_csv_adjanzenzliste_to_adjazensmatrix (a, b, n);
    }
    else
        printf ("Wrong Parameter!\ng: generete generate_adjanzenzmatrix\nr: read_csv_adjanzenzmatrix\ns: read_csv_adjanzenzliste\n\np: print_csv_adjanzenzmatrix\nq: print_csv_adjanzenzliste");


    if (strcmp (argv [2], "p") == 0)
        print_csv_adjanzenzmatrix (a, n);
    else if (strcmp (argv [2], "q") == 0)
        print_csv_adjanzenzliste (b, n);
    else if (strcmp (argv [2], "t") == 0)
        print_tex (a, component);


    int i, x;

    init_neighbours_index ();
    for (i = 0;  i < N;  i++) {
        while ((x = neighbour_adjazenzmatrix (a, i)) != -1)
            printf ("%i, ", x);
        printf ("\n");
    }

    int c [N];

    bfs (a, c, 0);

    for (i = 0;  i < N;  i++)
        printf ("%c, ", c [i] + 'a');

return 0;
}