#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);
}
void breadth_first_search (int a [N][N], int *component, int r) {
int pred [1024];
int w, v;
int i = 0;
for (i = 0; i < 1024; i++) {
pred [i] = -1;
component [i] = -1;
}
pred [r] = r;
component [r] = r;
Qput (r);
while (QIsNotEmpty ()) {
v = Qget ();
printf ("%c\n", v + 'a');
for (w = 0; w < N; w++) {
if (a [v][w]) {
if (pred [w] == -1) {
pred [w] = v;
component [w] = component [v];
Qput (w);
}
}
}
}
}
int _bfs (int a [N][N], int marked [N], int r) {
int i;
int retv;
if (marked [r] == -1) {
marked [r] = 1;
for (i = 0; i < N; i++)
if(retv = _bfs (a, marked, a [r][i]))
printf ("%c", r+'a');
return retv;
}
return 0;
}
void bfs (int a [N][N], int r) {
int i;
int marked [N];
for (i = 0; i < N; i++)
marked [i] = -1;
_bfs (a, marked, r);
}
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;
}
}
}
}
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");
bfs (a, 0);
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);
return 0;
}
